CS 315 Assignment 8: Patterns
Due: November 2, 2011.
Files: Cons.java   patmatch.lsp
Some functions that you may need are provided in the file
Cons.java, and you will need some of your functions from the
last assignment. This assignment may be done in Java or in Lisp.
- Physical principles often are described by sets of equations.
Since the solve function from the previous assignment is able
to solve a single equation, we would like to extend it to solve problems
involving multiple equations.
Write a function Double solveqns(Cons eqns, Cons vals, String v) that
attempts to solve the list of equations eqns for variable v
given an association list of values vals.
- If the desired variable has a value defined in vals,
the problem is solved, and the value can be returned.
- Otherwise, look through the list of equations to see if there
is an equation that has exactly one unknown. If so, the equation
can be solved for that variable using solve, and the value of the
variable can be found using eval. Add the new variable and value
to vals and call solveqns recursively to try again.
- If all the equations have been examined and none of them can be
solved, return null.
Use your program to answer the following questions. Input data is
provided in the test file.
- What is the terminal voltage of a battery with a current of 0.3 amp
and internal resistance of 4 ohms and voltage of 12 volts ?
- What is the angular momentum of a circular motion with radius 4 m
and mass 2 kg and velocity 3 m/s ?
- What is the magnification of a converging lens with
subject distance = 6 cm and focal length = 9 cm ?
- What is the power of a lift with weight 700 nt and height 8 m and
time 10 sec ?
- 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 125). Make substitution lists (in the list
substitutions) to instantiate this
design pattern to make the following functions:
- 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.
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.cs.utexas.edu/users/novak/asg-symdif.html for a list
- 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:
- zspace Space
- zlparen Left parenthesis
- zrparen Right parenthesis
- ztab Tabs are cumulative, and can be used to indent the code
- zuntab Decrements the number of tabs
- zreturn Return or new line
- znothing does nothing, but can prevent unwanted matching
of a pattern.
The final part of the driver program calls the Java translator on the
functions made using the design pattern in question 2. This illustrates
how transformations on trees using substitutions and patterns can
be used to produce code in a standard programming language.