COM 1358 Assignment #4.
Due: Thursday, 4 May 2000

To help with exercises 1 and 2 below, an interpreter for the
language of Section 3.5 (with comparison predicates and proc
expressions but without letrec) can be loaded into an
R5RS-compliant implementation of Scheme as follows.

    % scheme
    > (load "/course/com1358/pub/r5rs.scm")
    > (load "/course/com1358/pub/define-datatype.scm")
    > (load "/course/com1358/pub/sllgen.scm")
    > (load "/course/com1358/pub/assignment4.scm")

If you are using Chez Scheme, Larceny, or DrScheme, you can substitute
"chez.scm", "larceny.scm", or "drscheme.scm" for "r5rs.scm".  If you
are using DrScheme, you may also have to substitute
"define-datatype-drscheme.scm" for "define-datatype.scm".


Exercise 1.  In the language of Section 3.5 (with comparison
predicates and proc expressions but without letrec), write a proc
expression that evaluates to a procedure that takes a non-negative
integer n and returns the factorial of n.  [Hint:  Here is a Scheme
lambda expression that computes the factorial of n.]

    (lambda (n)
      (letrec ((f (lambda (n)
                    (if (zero? n)
                        1
                        (* n (f (- n 1)))))))
        (f n)))


Exercise 2.  In the language of Section 3.5 (with comparison
predicates and proc expressions but without letrec), write a proc
expression that evaluates to a procedure that takes a procedure f
as its argument and returns the least non-negative integer n such
that (f n) returns a nonzero value.  If (f 0), ..., (f -(n,1))
all return zero and (f n) does not terminate, then your procedure
is not required to return a value.

[Hint:  proc (f) for (int n = 0;; n = n + 1) if (f(n)) return n; ]


Exercise 3.  Write a Scheme literal that evaluates to itself.


Exercise 4.  Write a non-literal Scheme expression that evaluates
to the list representation of itself.


Exercise 5.  [For extra credit!]  Write a complete Java application
that takes no inputs and writes its own source code to System.out.
This program should not perform any i/o except for printing to
System.out.