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: Note that define, lambda, cond, and, or, etc, are not MRSE special forms; those symbols have no particular special meaning in an MRSE.
  1. Define all-calls which takes a MRSE and returns a list of symbols that correspond to targets of procedure calls.

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

  3. 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.


    	(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)

  4. 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

    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.


    	(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)

  5. 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.


    	  (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