Due: before lecture (14:00) on Monday 22-Oct-2007.

Hand in: please turn in a printout when you come to class, and also email your solution (as a plain text file!) to barak+cs351hw2@cs.nuim.ie

Teamwork: is encouraged! Please work in teams of up to three (3) people. Just turn in one (1) solution set, with the entire team listed at the top, sorted by how much each person contributed. (The order will not affect grades; it will be used only for my own consistency checking of scores at the end of the course.)

Hints: Start early! Don't be afraid to ask for help! And, it is okay to define auxiliary functions to be shared by solutions to multiple problems.

NUIM/CS351 Assignment 2

Manipulating Expressions

The objective of this assignment is to (a) become comfortable with manipulating s-expressions that represent hunks of code in some language, and (b) be sure you really understand what a tail recursive call is.

Definition: a mini restricted scheme expression or MRSE is either:

A number, denoting that number.
#t or #f.
A two-element list whose first element is the symbol quote and whose second element can be anything. This denotes a constant.
A symbol (other than if, let, or quote)
A four-element list whose first element is the symbol if and whose second, third, and fourth elements are MRSEs. This denotes a conditional expression, in the fashion with which we are familiar.
A three-element list whose first element is the symbol let, whose second element is a (possibly empty) list of two-element lists whose first element is a symbol denoting a local variable and whose second element is a MRSE, and whose third element is a MRSE. The is just like a Scheme let.
A list whose first element is a symbol denoting a global variable and whose remaining elements are MRSEs, denoting a procedure call. Note that, unlike in real Scheme, only a global variable can be used as the procedure. It is not permitted to use a local variable (bound by a let expression) as the procedure in a procedure call.
Note that define, lambda, cond, and, or, etc, are not MRSE special forms; those symbols have no particular special meaning in an MRSE.

Define all-calls which takes a MRSE and returns a list of symbols that correspond to targets of procedure calls.
Define tail-calls which takes a MRSE and returns a list of symbols that correspond to targets of tail recursive procedure calls.

Define non-tail-calls which takes a MRSE and returns a list of symbols that correspond to targets of non-tail-recursive procedure calls.

The lists returned by the above are interpreted as sets, so the order of elements is arbitrary. However, each element should appear only once. You may find it useful to write a utility function union that takes the union of two such sets.

Examples:

	(all-calls '(quote foo))                       ; ()
	(all-calls '(car (cdr (car 17))))              ; (CAR CDR) or (CDR CAR)
	(all-calls '(car x y (cons) (foo bar)))        ; (CAR FOO CONS)
	(all-calls '(car (if foo bar (baz))))          ; (CAR BAZ)
	(all-calls '(car (if (foo) (bar) (baz))))      ; (CAR FOO BAR BAZ)
	(tail-calls '(car (if (foo) (bar) (baz))))     ; (CAR)
	(non-tail-calls '(car (if (foo) (bar) (baz)))) ; (FOO BAR BAZ)
	(tail-calls '(if (foo) (bar (fu)) (baz)))      ; (BAR BAZ)
	(non-tail-calls '(if (foo) (bar (fu)) (baz)))  ; (FOO FU)
	(tail-calls '(let ((x (foo))) x))              ; ()
	(all-calls '(let ((x (foo))) x))               ; (FOO)
	(all-calls '(foo (foo)))                       ; (FOO)
	(tail-calls '(foo (foo)))                      ; (FOO)
	(non-tail-calls '(foo (foo)))                  ; (FOO)

Define ddx which takes a SE and returns an SE corresponding to its derivative with respect to x. (Derivative in the Newton/Liebnitz calculus sense.) An SE is a simple expression consisting of
- a number
- a symbol, either x or some other symbol which we take to be an unknown constant.
- a three-element list whose first element is one of the symbols +, * or / denoting addition, multiplication or division, and whose remaining two elements are SEs.
- a two-element list whose first element is one of the symbols sin, cos, exp or log and whose remaining element is an SE.
Note that there are many correct SEs that can be output by ddx for the same input. I will measure the size of the output of your ddx when given some big input SEs and give extra points to solutions that manage to give small but correct outputs. Also note the subtraction can be expressed as addition in combination with multiplication by -1.

Examples:
```
	(ddx 'x)                  ; 1
	(ddx 'c)                  ; 0
	(ddx '(* x (* 3 x)))      ; (* 2 (* x 3))  or  (* x 6)
	(ddx '(sin (* x x)))      ; (* x (* 2 (cos (* x x))))
	(ddx '(cos (* x x)))      ; (* x (* 2 (* -1 (sin (* x x)))))
	(ddx '(log (* x x)))      ; (* 2 (* x (/ 1 (* x x)))) or (/ 2 x)
	(ddx '(* x (+ y 3)))      ; (+ y 3)
      
```

Define eval-se which takes two arguments, an SE and an association list pairing symbols with numbers, which is guaranteed to include every symbol used as a constant in the SE and to also include x if it occurs, and returns the numberic value of the SE under the given assignment of values.

Examples:

	  (eval-se 'x '((a 1) (b 2) (x 3)))                         ; 3
	  (eval-se '(exp (* b x)) '((a 1) (b 2) (x 3)))             ; 403.4287934927351
	  (eval-se '(+ 2 2) '())                                    ; 4
	  (eval-se '100 '((a 1) (b 2) (x 3)))                       ; 100
	  (eval-se '(+ 2 (sin (/ pi 2))) '((pi 3.141592653589793))) ; 3.0