# CS59/259 - Homework 2

Consider a polynomial with integer coefficients. It can be written directly as a LISP expression. For example:

| Math                        | LISP                                   |
|-----------------------------|----------------------------------------|
| `3x² + 5x + 7`              | `(+ (* 3 (expt x 2)) (* 5 x) 7)`       |
| `3x² + 5x + 7` (no `expt`)  | `(+ (* 3 x x) (* 5 x) 7)`              |
| `x²y - 2xy + y`             | `(+ (* (expt x 2) y) (* -2 x y) y)`    |
| `(x + 1)²`, unexpanded      | `(expt (+ x 1) 2)`                     |
| `4`                         | `4`                                    |


In the following problems, you will write functions that deal with these polynomials.
These are the rules:
  * Make your functions recursive, do not use loops.
  * Do not use EVAL or similar in your solutions. You may use EVAL to test your solutions.
  * Write solutions to Problems 1--3 by hand. You may use AI on Problem 4 and onward, but you will need to thoroughly understand the design and the code you turn in. You will be asked to explain it.

To gain fluency and the ability to understand the design and the code, you need to encounter enough of your own mistakes and the system reactions to them. So stick to hand-coding in 1--3, and only use AI for definition look-ups and explanations, not emitting code. 

## Submission
 
Submit a single file with all your functions: `hw2-<NetID>.lisp` (GCL or SBCL) or `hw2-<NetID>.scm` (Scheme), using your full NetID in the filename. Email the file as an attachment to Claudia (Claudia.M.Pacori.Palomino.GR@dartmouth.edu). For the explanation in Problem 4(c), you can either write it as a comment at the end of your file (with enough detail) or attach a PDF if you need more space. 

## Problem 1: Is it a polynomial? (5 points)

Write `(is_polynomial expr)`. It should return `T` if the LISP expression`expr` is a polynomial with integer coefficients, and `NIL` if it isn't.

```lisp
(is_polynomial 5)                            ; => T
(is_polynomial 'x)                           ; => T
(is_polynomial '(+ (* 3 x x) (* 5 x) 7))     ; => T
(is_polynomial '(expt x 2))                  ; => T
(is_polynomial '(expt x -1))                 ; => NIL, negative exponent
(is_polynomial '(expt x y))                  ; => NIL, exponent isn't a literal
(is_polynomial '(/ x 2))                     ; => NIL, no division allowed
(is_polynomial '(* x "oops"))                ; => NIL
```

## Problem 2: Get polynomial variables (5 points)

Write `(get_variables expr)`. It returns a list with the distinct variables in `expr`.

```lisp
(get_variables 7)                                  ; => NIL
(get_variables '(+ (* 3 (expt x 2)) (* 5 x y) 7))  ; => (X Y)
(get_variables '(expt (+ a b) 3))                  ; => (A B)
```

## Problem 3: Evaluate polynomial (6 points)

Write `(evaluate_pol expr bindings)`. It should substitute `bindings` (list of `(variable . value)` pairs) into `expr` and return the result.

```lisp
(evaluate_pol '(+ (* 3 (expt x 2)) (* 5 x) 7) '((x . 2)))  ; => 29
(evaluate_pol '(* x y) '((x . 3) (y . 4)))                 ; => 12
(evaluate_pol '(* x y) '((x . 3)))                         ; => :ERROR
```

## Problem 4: Canonical form (9 points)

Two polynomial expressions can be the same polynomial even though they look different, for example: `x*y` and `y*x`, or `2xy + 3xy` and `5xy`. Canonicalizing turns any polynomial expression into one fixed form, so equal polynomials always print out the same way: everything gets multiplied out, and matching terms get merged into one.

Write this as three pieces:

**(a) `(multiply_out expr)`, 3 points.** Distribute every `*` over any `+` inside it, and expand every `(expt base k)` into `k` copies of `base` multiplied together. What you get back should be a flat sum of monomials.

**(b) `(merge_terms monomials)`, 3 points.** Takes the output of `multiply_out` and
merges the monomials that have the same variables raised to the same powers (make sure
cases like `x*y` and `y*x` are considered the same), adding up their coefficients. Drop
anything whose combined coefficient comes out to `0`.

**(c) `(canonicalize_pol expr)`, 3 points.** Uses both previous functions to print the final result. Order terms by total degree descending, breaking ties alphabetically by the lowest-named variable and then by descending exponent. Choose one of the examples below and explain in your own words the detailed process from what each sub-function produces to the final result.

```lisp
(canonicalize_pol '(+ (* 3 x x) (* 5 x) 7))
;; => (+ (* 3 (expt x 2)) (* 5 (expt x 1)) 7)

(canonicalize_pol '(expt (+ x 1) 2))
;; => (+ (* 1 (expt x 2)) (* 2 (expt x 1)) 1)        (x+1)^2 = x^2 + 2x + 1

(canonicalize_pol '(+ (* 2 x y) (* 3 y x) (* -5 x y)))
;; => 0                                              2xy + 3yx - 5xy cancels out

(canonicalize_pol '(* (+ x 1) (+ x -1)))
;; => (+ (* 1 (expt x 2)) -1)                        (x+1)(x-1) = x^2 - 1
```

## Extra Credit: two more algebra laws (5 points)

A full canonicalizer uses three laws: commutative, associative, and distributive. The
distributive law is already in `multiply_out` from Problem 4. Write the other two as
their own small functions.

- `(associative_flatten expr)`: collapse nested `+` inside `+` (or `*` inside `*`) into one call.
- `(commute_sort expr)`: put the arguments of every `+` and `*` in a fixed order (numbers first, then symbols alphabetically).

```lisp
(associative_flatten '(+ (+ a b) c))       ; => (+ a b c)
(associative_flatten '(+ a (+ b c)))       ; => (+ a b c)
(associative_flatten '(* (* x y) z))       ; => (* x y z)
(associative_flatten '(* (+ a b) c))       ; => (* (+ a b) c), different operators, nothing to flatten

(commute_sort '(+ y x 3))                  ; => (+ 3 x y)
(commute_sort '(* y 2 x))                  ; => (* 2 x y)
```