- It is important to know the design patterns for algorithms,
since a large part of application programs is composed of instances
of standard design patterns. sublis can be used to instantiate
design patterns to form working programs.
The test file contains the Lisp design pattern for binary tree recursion
(class notes,
page 47).
Make substitution lists (in the list
substitutions) to instantiate this
design pattern to make the following functions; an example for the function
addnums is provided.
- countstrings Count the number of strings
in a tree.
- copytree Make a copy of a tree structure.
- mintree Find the smallest numeric value
in a tree.
You may assume a function (min x y) that returns the lesser of x and y,
and that all values in the tree are less than 999999.
- conses Find the number of conses in a tree.
You may assume
an auxiliary function (add1 x y) that adds 1 to the sum of x and y.
- Pattern matching and substitution together can transform an
expression into a new expression. This is a powerful form of computation.
Write a recursive function (solve e v) that
solves the equation e for variable v,
which we assume occurs at most once in e.
This function does the same thing as the earlier version of
solve; in this version, use patterns to rewrite the given
expression. The base cases are the same as before, and you
can copy your previous code for those cases.
- If the left-hand side (lhs) of e is v, return e.
(solve '(= f (* m a)) 'f) => (= f (* m a))
- If the right-hand side (rhs) of e is v, return e
with its arguments reversed.
(solve '(= (* m a) f) 'f) => (= f (* m a))
- If the rhs is not v and not a cons, return null.
- If the rhs of e is a cons (i.e. an operation), try to
solve the equation by applying algebraic transformations from a list
of patterns, algpats. For each pattern in the list, try
to transform the expression e using the pattern.
If the transformation works (is not nil), call solve
recursively on the transformed version of e; if the result of
solve is not nil,
return that result. Otherwise, continue through the list of patterns.
If all patterns have been tried without success, return nil.
-
Add patterns to the list optpats to perform optimization
of algebraic expressions. Some examples of expressions to be optimized
are given in the test file. You will find that the derivative patterns
for the next part of the assignment produce a lot of things that need
to be optimized; add patterns to get good results for derivatives.
- Add patterns to the list derivpats to perform differentiation
of algebraic expressions. Calculus books contain lists of derivative
formulas; you can also consult
http://www.mathsisfun.com/calculus/derivatives-rules.html or
http://en.wikipedia.org/wiki/Differentiation_rules or
http://www.cs.utexas.edu/users/novak/asg-symdif.html for a list
of formulas.
- Programming languages are usually described using context-free
grammars, which generate trees. Since Lisp programs are trees made of list
structure using cons cells, it is fairly easy to transform Lisp
code into code in a language such as Java using patterns. In effect, the
patterns are a grammar for Java. We will use a set of restructuring
patterns (provided) and a list of patterns to transform Lisp code
to Java syntax. Add patterns to the list javapats
to translate the code examples given in the test file. A printing program
is provided to print the output from list structure.
You may use the following special codes for printing of special characters:
- \tab Tabs are cumulative, and can be used to indent the code
- zuntab Decrements the number of tabs (put it before
\return)
- \return Return or new line
-
The test program calls the Java translator on the functions made
using the tree recursion design pattern above. This illustrates
how transformations on trees using substitutions and patterns can
be used to produce code in a standard programming language.
-
The minimum or maximum of a mathematical function occurs where
the derivative of the function is zero. Write a program
(findminmax equation var) to find a formula for the minimum
or maximum of a given equation with respect to a variable, as follows:
- Find the derivative of the rhs of the equation with respect
to the variable.
- Make a new equation, (= 0 derivative).
- Solve this equation for the variable.
- Make a new version of the latter equation in which the rhs is
simplified.
Use your function to solve the following problem:
A cannonball is fired at a velocity v at angle θ above
the horizontal. Find the time t at which the cannonball reaches its
maximum height y.
(def cannonball '(= y (- (* (* v (sin theta)) t)
(* (/ g 2) (expt t 2)))) )