Cmput 325 Assignment 2
Update Feb 2: fixed typo in Question 2, (0 * Exp) changed to (* Exp 0). Added test cases 2.8, 3.9. 3.10 in a2-public-tests.lisp to cover more variations of multiply by zero.
This assignment is due Feb 25 at 23:55pm. Submit through the button on eClass. NO LATE SUBMISSIONS. This assignment should be submitted as a single text file named assignment2.lisp .
All our examples, which are also our public test cases, are in file a2-public-tests.lisp. Also see the comments in that file.
Overview
In this assignment, you implement a restricted form of the classic problem of simplifying arithmetic expressions. You first implement two simplification operations, then a general algorithm to transform such expressions into a normal form.
The main restriction is that we only deal with the operations +, -, and *, and that the arguments are only integers and a single variable symbol x. Therefore, all expressions eventually simplify to a polynomial in x, with integer coefficients.
TYPES OF EXPRESSIONS IN THIS ASSIGNMENT
We have two main types of expressions in this assignment: Assignment 2 expressions or A2Expr are built as explained above, and polynomials in x or PExpr are represented in a specific short form.
A2Expr – a more formal definition
An integer is an A2Expr
x is an A2Expr
If E1 and E2 are A2Expr, then (+ E1 E2), (- E1 E2) and (* E1 E2) are A2Expr Nothing else is an A2Expr
#1 (2 marks)
Write a Lisp function:
(remove-identities E)
The input E can be any valid A2Expr. This function should replace any term of the form (+ 0 Exp), (+ Exp 0), (* 1 Exp), (* Exp 1) by Exp. It should apply this simplification recursively to all nested expressions. It should not change E in any other way, and return the simplified A2Expr.
See remove-identities Examples in public tests. #2 (2 marks)
Write a Lisp function:
(simplify-zeroes E)
The input E can be any valid A2Expr. This function should replace any term of the form (* 0 Exp), (* Exp 0) or (- Exp Exp) by 0. It should apply this simplification recursively into all nested expressions. It should not
change E in any other way, and return the simplified A2Expr. See simplify-zeroes Examples in public tests.
#3 (1 mark + 1 possible bonus mark) #3.1 (1 MARK)
Write a Lisp function:
(simplify E)
This function should repeatedly call
1. remove-identities, followed by
2. simplify-zeroes,
until no more simplification is possible in either step 1 or 2.
See simplify Examples in public tests.
#3 BONUS QUESTION (1 BONUS MARK)
Does the order of calls to remove-identities and simplify-zeroes in simplify matter? Could we get a different final result in simplify if we called these two functions in a different order?
If your answer is yes, give an example with two different call sequences with different results. If your answer is no, give a good logical argument for why.
Discussion: How to get More Simplifications?
The simplify function above is still very limited in what it can do. For example, the A2Expr
(- (* (+ x 5) (- x 5) ) (* x x))
is mathematically equivalent to -25. However, our simplify cannot see that. We could add more and more simplification rules similar to the cases above, and hope to catch more and more cases that way. Fortunately, we do not have to do that. There is a nice general way to simplify all A2Expr.
PExpr as a Compact Representation of Polynomials
A polynomial in variable x is a function of x. In mathematics, it is usually written in the form
anxn+an-1xn-1+… +a2x2+a1x+a0
We call the ak the coefficients and the powers of x the exponents.
In principle, we can write any polynomial as an A2Expr. However, it gets messy and hard to read pretty quickly. For example, an A2Expr corresponding to 5×2+3x+7 would be (+ (* 5 (* x x)) (+ (* 3 x) 7)).
PExpr are a compact way of representing polynomials in Lisp as a list of dotted pairs of coefficients and exponents, (ak . k).
For example, 5×2+3x+7 written as a PExpr is ((5 . 2) (3 . 1) (7 . 0)). A PExpr P is said to be in normal form if:
The dotted pairs in P are in strictly decreasing order of exponent (this implies there are no duplicate exponents in the list).
There are no zero coefficients
An empty list represents the constant polynomial of value 0.
For example, ((5 . 10) (3 . 4) (7 . 0)) is in normal form, but the following are not:
((5 . 2) (7 . 0) (3 . 1)) – exponents not in decreasing order
((5 . 3) (0 . 2) (3 . 1) (7 . 0)) – zero coefficient in (0 . 2)
((0 . 0)) – zero coefficient
#4 (2 marks)
Write a Lisp function:
(normalize P)
The input P is an arbitrary PExpr. The output is the normal form of P. See the normalize examples in public tests. #5 (5 marks)
Write a Lisp function:
(polynomial E)
The input E is an arbitrary A2Expr. The output is the equivalent PExpr of E in normal form. First implement the three helper functions in 5.1 and 5.2.
#5.1 (1 MARK)
Write two Lisp functions:
(poly-add P1 P2)
(poly-subtract P1 P2)
For these two functions, the inputs P1 and P2 are PExpr in normal form. The output should be the sum (for poly- add) or difference (for poly-subtract) of the two PExpr, also in normal form. See poly-add, poly-subtract examples in public tests.
Hints:
normalize is your friend…
If n is an integer, then (- n) computes its negative value. Note the space.
#5.2 (2 MARKS)
Write a Lisp function:
(poly-multiply P1 P2)
Again, the inputs P1 and P2 as well as the output are PExpr in normal form. See poly-multiply examples in public tests.
Hints: To compute the product of two PExpr, “multiply them out” and normalize the result. Example for illustration only in math-like syntax:
(x+1)*(x-1) = x^2 – x + x – 1 = x^2 + (-1 + 1)x -1 = x^2 – 1
Real examples in PExpr for the assignment: see public tests.
The function cartesian in sample code list-functions.lisp is an example with similar structure, which may help you with the recursion over both P1 and P2.
#5.3 (2 MARKS)
Implement polynomial, using the three helper functions.
Hint: use recursion, with the base cases: 1. integer n – represent by (n . 0)
2. atom x – represent by (1 . 1)
See polynomial examples in public tests.
#6 (2 marks) Printing a PExpr in normal form
Write a Lisp function:
(print-pexpr P)
The input P is a PExpr in normal form. Output a string representing P in the following “common sense” format:
Print terms in the form cx^n, where c and n are integer
Print ” + ” (space plus space) or ” – ” (space minus space) between the terms, depending on whether the next term has a positive or negative coefficient
Print terms in sorted order from highest to lowest exponent
Do not print the 1 if the coefficient is 1, except for the constant term
Print -, not -1 if the coefficient is -1, except for the constant term
Do not print *x^0 for a constant term
Print x instead of x^1
Print 0 if the PExpr is nil.
See print-pexpr Examples in public tests, and string functions.
MARKING
Your solutions have to be general to get any marks, i.e. you cannot just hardcode the public test cases and their answers.
There is a total of 15 marks + 1 bonus mark. The assignment counts for 7.5% of your course total (plus bonus). In question 5, there will be some partial marks for solving simple expressions, e.g. those without x or those without multiplications.
HINTS AND DETAILS – READ THEM ALL
Before submitting, make sure your program runs correctly on our lab machines.
For commenting and organizing your code, follow the programming style and marking guideline and also the detailed explanations at the start of Assignment 1.
Restrictions: There are no restrictions on the use of built-in Lisp functions and special forms in this assignment. That said, there are still style marks, so do your comments properly, and stay true to the spirit of pure functional programming: avoid non-pure idioms such as destructive assignments, global variables, explicit loop constructs etc.
Exception for sort: you are allowed to use sort, even though it destructively changes the argument to be sorted. Also see https://stackoverflow.com/questions/29712654/destructive-sorting-in-lisp and Using sort with a custom comparison function.
To test whether a s-expr is an integer, use integerp.
Examples:
(integerp 22) and (integerp (+ 3 4)) return T
(integerp 23.5), (integerp ‘a), (integerp ‘(+ 3 4)), (integerp nil) all return NIL.
Using sort with a custom comparison function
Example:
(defun longer-list (L1 L2)
(> (length L1) (length L2))
)
(defun sort-by-longer-list (L)
(sort L ‘longer-list)
)
(sort-by-longer-list ‘((a b) (c) (d e) (f g h) nil (1 2 3 4)))
((1 2 3 4) (F G H) (A B) (D E) (C) NIL)
String functions
Convert an integer to a string: (write-to-string int).
Example: (write-to-string -23)
Concatenate strings: (concatenate ‘string string1 string2).
Note that ‘string is required. You can define a little convenience function
(defun concat (S1 S2) (concatenate ‘string S1 S2))
Examples: (concatenate ‘string “ab” “cd”), (concat “ab” “cd”) End of Assignment 2.