CSE3401.03, Fall 2005

Report 2 Specification

Due: October 28, 5 PM

Be sure to read On Academic Honesty and Reports from the home page for the course.

What you hand in:

Question 1. Solving simple 1-variable arithmetic equations

  1. Define and demonstrate a function solver() which solves arithmetic equations containing a single variable, occuring once in the left-hand side of an equation. The variable is represented in a Lisp expression as a list of one element -- for example, (zz).

    Write solver as a tail-recursive function that uses the READ function to read in and solve an equation entered at the terminal, prints the solution (if there is one), and repeats until the input is NIL.

    An equation is to be represented as a pair of arithmetic expressions expressed in Lisp. For example, the equation
    2*sqrt(x)/7 = 53
    is represented by
    ((/ (* 2 (SQRT (x))) 7) (EXPT 5 3))

    solver should at least validate that the input has the form of a list of two lists, before trying to solve the equation. How you handle the case in which the input is not an equation or is unsolvable is up to you. Make sure you document this in your report.

    The solver function successively transforms an equation by eliminating arithmetic operators on the left side while building up the right side of the equation until the equation has the form:

    (variable expression).
    If the expression is purely numeric, it should be evaluated to give the solution (variable value), i. e. variable = value.

    For example, solver should successively transform ((/ (* 2 (SQRT (x)) 7) (EXPT 5 3)) to:
            --> ((* 2 (SQRT (x))) (* (EXPT 5 3) 7))  
            --> ((SQRT (x))) (/ (* (EXPT 5 3) 7) 2)) 
            --> ((x) (EXPT (/ (* 7 (EXPT 5 3)) 2) 2))
    which evaluates to ((x) 765625/4). Your function should be able to handle the following arithmetic operations in the left-hand side of the equation:
    + - (both (- x) and (- x y)) * / sqrt log.
    (Log functions come in different flavours - natural, base 10, etc. It's up to you to decide how you want to handle this - just make sure it's documented in your report.)

    You are free to use LET-scopes, LAMBDA-blocks and additional support functions to simplify your code. Built-in functions which may be useful are MEMBER, EVERY, and NUMBERP.

  2. Construct at least two examples which demonstrate that your function can handle correctly all the specified operators.

  3. Modify your solution to part 1 to allow non-numeric atoms in the equation, replacing purely numeric sub-expressions in the solution with their values. Example: ((+ a (zz)) (/ (+ 2 3) q)) has the solution ((zz) (- (/ 5 q) a))

Question 2:

    A multinomial is a polynomial in one or more variables, e. g.
    1 - xy2 + 3z.
    A term in a multinomial consists of a coefficient and zero or more variables, each with an exponent. (In ordinary mathematical notation, coefficients and exponents which are 0 or 1 are not shown.) To represent a term in Lisp, we can use the following format:
    (coefficient factors)
    where coefficient is a numeric or algebraic expression (but does not contain any variables), and factors is a (possibly empty) list of factors, each of which are in the form
    (variable exponent)
    The variable is an atom whose name begins with a letter and the exponent is a numeric or algebraic expression. Thus the term (a+3)x2nz

    would be represented by the Lisp expression:

    ((+ a 3) ((x (* 2 n)) (z 1)))
    As in ordinary mathematical notation, the multiplication operation in a term is not explicitly represented.

    A constant term has no variables--it would be represented by

    (coefficient ())

    A multinomial is a list of terms interpreted as a sum. To simplify matters, we express a difference between terms as a sum using a negative coefficient. Thus ax - b is represented as

    ((a (x 1)) ((- b) ())).

  1. Define and demonstrate a Lisp function term-mult which multiplies a multinomial by a term. For example, in ordinary notation, the product of
    2yx and (ax2 + ya + 1)
    2ax3y + 2xy(a+1) + 2xy.

    Your function is to produce a Lisp presentation of the product multinomial, given Lisp representations of a term and multinomial as arguments.

    Suggestion: sort the factor lists in each argument to make it easier to detect if there is a common variable whose exponents need to be summed. See page 93 in the text for details on comparing atoms by name.

  2. Define and demonstrate a Lisp function multi-mult which multiplies two multinomials, and collects like terms (like terms have identical factor lists and the coefficents should be added.)

Question 3: tweaking DEFUN

  1. Some people don't like the format of the DEFUN form since it doesn't match the way the function being defined is actually called. Define a macro deffun which uses the back-quote, comma and splice operators to transform
    (function-name arg1 . . . argn) body
    (DEFUN function-name (arg1 . . . argn) body)
    In defining deffun, the symbol &REST will be useful. See "Macro Examples" for an example. (Chapter 5 of Peter Seibel's Practical Common Lisp is also recommended reading.)

  2. Use MACROEXPAND to give an example of what a call to the deffun macro expands to, and use DESCRIBE to show that deffun does what it is supposed to do.

Last Updated: October 24, 2005