Assignment 5: Yet More Recursion and Functions

Before you tackle the homework, remind yourself of our General Advice, Advice on Homeworks, and Grading Guidelines. Above all, keep your work neat and honest.

1. (6pts) A Scheme program can evaluate a Scheme program. To do that, we first need a representation of Scheme programs; after all, programs work on representations of information, not on information itself.

   Representing expressions: Consider the following table:

   Scheme expression	representation of Scheme expression
   (* 3 10)	(make-time 3 10)
   (+ (* 3 3) (* 4 4))	(make-plus (make-time 3 3) (make-time 4 4))
   (+ (* x x) (* y y))	(make-plus (make-time 'x 'x) (make-time 'y 'y))
   (* 1/2 (* 3 3))	(make-time 1/2 (make-time 3 3))

   It suggests a representation of numbers, variables, additions, and products via structures.

   1. Provide a rigorous data definition for this collection of data.
   2. Develop the program numeric?. The program consumes (the representation of) a Scheme expression. It produces false, if the expression contains a (representation of a) variable. Otherwise, it produces true.
   3. Develop the program subst. The program consumes (the representation of) a variable (V), a number (N), and (the representation of) a Scheme expression. It produces an structurally equivalent expression in which all occurrences of V are substituted by N.
   4. Develop the program value. The program consumes (the representation of) a Scheme expression. If the expression is numeric (see above), it produces the number that DrScheme would produce for the actual Scheme expression. Otherwise, it returns false.

   Note: If you wish to understand Scheme even better, invent a representation for Scheme function definitions of one argument:

     (define (function variable) expression)

   Furthermore, extend the data definition for expressions so that you can represent function applications:

     (function expression)

   Now, modify the function value so that it consumes an expression and a list of (representations of) definitions. It still computes the numeric value of numeric expressions, and returns false if the expression is not numeric.

   You must adjust the definition of numeric?.

   Hint: You will need a function to lookup the definition of a (representation of a) defintion. But you have seen this before.

   You will not receive credit for any of the problems mentioned in this note. If, however, you choose to solve these problems, you will begin to understand why the design recipes and the templates lead to good code. Enjoy! End of note

2. (1pt) Exercise 22.0.8.
   
   
3. (1pt) Exercise 22.0.12.
   
   
4. (2pts) Exercise 23.0.17. Include the template with your documentation.
   
   
5. (Extra credit: 2pts) Exercise 24.1.2.