CS 314 Assignment 8: Patterns

Due: November 6, 2014.

Files: Cons.java   patmatch.lsp   patterns.lsp   patm.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.

  1. 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.

    1. If the desired variable has a value defined in vals, the problem is solved, and the value can be returned.

    2. 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.

    3. 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.

    1. 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 ?
    2. What is the angular momentum of a circular motion with radius 4 m and mass 2 kg and velocity 3 m/s ?
    3. What is the magnification of a converging lens with subject distance = 6 cm and focal length = 9 cm ?
    4. What is the power of a lift with weight 700 nt and height 8 m and time 10 sec ?
    See http://www.cs.utexas.edu/users/novak/cgi/physdemo.cgi.

  2. 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 135). Make substitution lists (in the list substitutions) to instantiate this design pattern to make the following functions:

    1. countstrings     Count the number of strings in a tree.
    2. copytree     Make a copy of a tree structure.
    3. 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.
    4. 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.

  3. 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.

  4. 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.

  5. 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:

    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.