CS 378 Assignment 4: Patterns

Due: March 30, 2021.

Files: cs378.clj   patm.clj   pats.clj   test4.clj   answer4.clj

Some functions that you may need are provided in the files cs378.clj and patm.clj, and you will need some of your functions from previous assignments.

Copy the file pats.clj to a new file asg4.clj and edit asg4.clj for your assignment.

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

    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.

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

    1. If the left-hand side (lhs) of e is v, return e.
         (solve '(= f (* m a)) 'f)  =>  (= f (* m a))
      
    2. If the right-hand side (rhs) of e is v, return e with its arguments reversed.
         (solve '(= (* m a) f) 'f)  =>  (= f (* m a))
      
    3. If the rhs is not v and not a cons, return null.

    4. 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, return nil.

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

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

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

    1. Find the derivative of the rhs of the equation with respect to the variable.

    2. Make a new equation, (= 0 derivative).

    3. Solve this equation for the variable.

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