Com Sci 221 --- Programming Languages
Assignment #7 --- Autumn 2000
Due Monday, 20 November

1. Example 13.5 on pages 532-533 of the text shows a function f that produces different results under dynamic and static scope rules. Write another pure functional program defining a function that distinguishes the two scope rules, using only lambda, and no let. You may redefine the same function from the book, or design your own simpler example (e.g., without the multiplication). You may define your function f using define, but don't use additional defines within the definition of the f. Run your program to demonstrate that Scheme has static scope. Do a hand calculation for the same program from McCarthy's equations for the eval function in the pages of the LISP manual that I copied for you. Show that the old fashioned LISP had dynamic scope.




2. reduce is the mother of all higher-order functions to produce list operations:

   (define (reduce f v)
   
     (letrec ((r
   
                (lambda (listin)
   
                  (cond ((null? listin) v)
   
                        (#t             (f (car listin) (r (cdr listin))))
                  )
                )
              ))
   
           r
     )
   )
   

   My reduce function is very similar to the one defined in Figure 10.5 on page 397 of the text, but mine is slightly more higher-order (pardon the grammar---I didn't make up the terminology).

   reduce-tree is the mother of all higher-order functions to produce operations on binary trees:

   (define (reduce-tree op atomval)
   
     (letrec ((rt
   
                (lambda (treein)
   
                  (cond ((pair? treein)  (op (rt (car treein))
                                             (rt (cdr treein))
                                         )
                        )
   
                        (#t              (atomval treein))
   
                  )
                )
              ))
   
           rt
     )
   )
   

   Since every list is represented by a tree, there is a simple definition of reduce from reduce-tree. Redefine reduce using reduce-tree with no explicit recursion (i.e., all of the recursion required is provided by executing reduce-tree). Demonstrate your definition by defining the identity function in the form (reduce f v), using a fiendishly clever and very simple choice of f and v. Then you need to run the identity function on (), (1), (1 2), and (1 2 3) to demonstrate its correctness. Think about why producing the identity function is the perfect way to test functions such as reduce and reduce-tree (you don't need to hand in your thoughts, but you may post them online if you like).




3. Look at the weird higher-order examples that I did in Scheme. Translate them into ML and run them, observing the types. Notice which Scheme definitions fail in ML.

Optional challenge problems (from the graduate course)

As before, I'm only interested in work that shows serious understanding of these advanced problems. Please don't submit wild guesses.

1. reduce-nested-lists is a close approximation reduce-tree. Define reduce-nested-lists using reduce and one recursion. There is one interesting way to do this, and part of the problem is to see what makes an interesting definition. In particular, the interesting definition of reduce-nested-lists from reduce uses the recursion built in to reduce, and adds on an explicit recursion corresponding to the one that's in reduce-tree and reduce-nested-lists, but missing from reduce).



2. Atomic symbols, lambda and function application are sufficient to define everything in LISP. We don't really need integers, lists, .... Redefine cons, car, cdr, the booleans T and F, and the special form if in terms of lambda and function application. Demonstrate your definitions on a few very simple examples.