CSE 413 Autumn 2007

Assignment 2 -- More Scheme Programming

All of these problems should be done without using side effects (i.e. redefining variables or using set!) and without using any explicit Scheme looping constructs (do).  Be sure to test your functions on various cases, including empty lists, simple lists with no sublists, complex lists, etc.

Part I.  Written (paper) problems

1.  Suppose we enter the following definitions at the top-level of a Scheme environment:

(define x 3)
(define y 7)
(define z 12)

What are the results when you evaluate the following expressions starting with just the above definitions?

1. (let ((x 0)
      (z (* x z)))
    (+ x y z))
     
2. (let ((x 2)
      (y (- x 4))
      (z (* y 2)))
    (+ x y z))
  
3. (let* ((x 2)
       (y (- x 4))
       (z (* y 2)))
     (+ x y z))
  

2. Consider the following definitions:

(a) Describe the result of evaluating (make-thing 3 double). What is it? (Your answer should be something like "the number 17", or "a function that adds 1 to its argument", or "a function that takes another function as an argument and ...".) If it is a function, describe the values bound in the closure as well as the code (expression) that is part of the function value.

(b) What is the value of (mystery 4)?  Explain how you arrived at your answer.  (For full credit, your answer should explain what happens when (mystery 4) is evaluated, not just report an answer that you got when you used DrScheme to evaluate these expressions.)

Part II.  Higher Order Functions

General hint: Take advantage of map and other higher-order functions when appropriate.

1. Write a function called apply-all that, when given a list of functions and a number, will produce a list of the values of the functions when applied to the number. For example,

   (apply-all (list sqrt square cube) 4) => (2 16 64))

2. Given a predicate that tests a single item, such as positive?, we can construct an "all are" version of it for testing whether all elements of the list satisfy the predicate. Define a procedure all-are that does this; that is, it should be possible to use it in ways like the following:

   ((all-are positive?) '(1 2 3 4)) => #t

   ((all-are even?) '(2 4 5 6 8)) => #f

all-are takes a predicate as an argument and returns a new function that can be applied to a list of elements (as is done above).

Part III. More Data Structures in Scheme

In this part of the assignment, you will create some functions to manipulate expression trees, using functions similar to the binary tree functions from the previous assignment. Here are some basics about expression trees:

Consider an arithmetic expression, such as one we would write in Scheme as (+ 1 (* 2 (- 3 5))). We can think of this as being a tree-like structure with numbers at the leaves and operator symbols at the interior nodes.

     +
   /   \
  1     *
       /  \
      2    -
          /  \
         3    5

1. Operators in the tree are all binary (i.e., have two operands)
2. All of the leaves (operands) are numbers

Each node in the tree can be represented by a three-element list:

        (left-operand  operator  right-operand)

Write and test Scheme functions to solve the following problems.  You should save all of your function definitions for this part of the assignment in a single source file.

General observation (hint): Binary trees have an elegant, recursive structure.  Take advantage of this to structure your code.

1. Write functions to create new expression tree nodes and extract fields from them.  The functions you should create are:
   
           (make-expr left-op operator right-op) => (left-op operator right-op)
    (operator '(left-op operator right-op)) => operator
    (left-op '(left-op operator right-op)) => left-op
    (right-op '(left-op operator right-op)) => right-op
   
   Notice that unlike in assignment 1, the leaf values are simple integers, not leaf nodes with null subtrees (e.g., 4 and not (4 () ())). A few examples:

   (make-expr 4 '+ 5) => (4 + 5)

   (make-expr '(6 * 3) '+ '(5 - 2)) => ((6 * 3) + (5 - 2)) 

   Quoting the operator will prevent it from being evaluated to a #<primitive:+>.
     
2. Write functions that traverse expression trees using inorder, preorder, and postorder traversals and return a list of the items encountered during the traversal in the order encountered.  You should use the functions from question 1 to access the components of the tree.
   
           (preorder  expr-tree)
    (inorder   expr-tree)
    (postorder expr-tree)

Test your functions by creating a few trees using nested make-expr function calls and then using these as arguments to the traversal functions.
     
3. Write a function
   
           (eval-tree expr-tree)
   
   that evaluates an expression tree by traversing it and returning the value that it represents.  You may assume that the only operators present in the tree are +, -, *, and /.  You also can ignore the possibility of division by 0.
     
4. Write a higher-order function
   
           (map-leaves f expr-tree)
   
   that returns a copy of the given expression tree that is the same as the original tree except that each leaf node v is replaced by the result of applying the higher order function f to the value in the leaf node, e.g., each node v is replaced by (f v).
   

What to Hand In

Electronic Submission

Turn in a copy of your Scheme source files from parts II and III using this online turnin form.

Paper Submission

Hand in the following:

1. Written answers to the problems from Part I.
2. A printed copy of your scheme functions from parts II and III.
3. A printout showing the transcript of a Scheme session demonstrating the results produced by your functions for suitable test cases.  This should contain enough to show that your functions work, but no more than necessary to do that. Part of your grade will be determined by the quality of the test cases you use for this.  (Don't worry if there are some minor typos in the transcript - just draw a line through anything we should ignore.)