## CSE3401.03, Fall 2005 Report 2 Specification

### Due: October 28, 5 PM

What you hand in:
• The first page of the report is a standard cover page.
• The body part of the report is a hardcopy of your answers in exercise order. For each exercise for which you develop Lisp functions you submit the following:

Note: partnering is not permitted.

1. A printout of your documented functions. Use one file per exercise named exercise-n.lsp, where n corresponds to the exercise number. For an example, look at the file exercise-N.lsp in the course directory. You must use the command enscript to print the file.
enscript exercise-N.lsp
2. A printout of the output file exercise-N.test created by executing the file exercise-N.lsp using the following command.

As an example, look at the file exercise-N.test, in the course directory, which is created by executing the file exercise-N.lsp:
clisp exercise-N.lsp >! exercise-N.test
enscript exercise-N.test

You can submit the report to your instructor in class or to the assignment boxes accessible outside the main Computer Science office.

• Before the deadline, submit a directory called report2 that should contain one *.lsp file and one *.test file for each exercise for which you wrote Lisp functions. Use the following Prism command:
submit 3401 r2 report2

### 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)`
is
`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```
into
`(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