\documentclass[11pt]{handout}
\usepackage{6044}
%\documentclass[11pt]{article}
%\usepackage{6001}
\usepackage{time,fullpage}
\usepackage{amsmath}

\begin{document}
\handout{ps1}{Problem Set 1}{18 September 1995}

\due 22 September 1995.

\medskip
Reading:  Handout 5, ``A Term Rewriting Model for Scheme, I.''
\medskip

\problem Do Problem 1 from the Term Rewriting handout.

\problem Do Problem 2 from the handout.

\problem For each numbered step in the sample rewriting of
\Code{(factorial 4)} in the Appendix of the handout, indicate the
subexpression which gets rewritten and the rules applied (``P''--primitive
application, ``C''--conditional, ``I''--instantiation, ``L''--lambda
application, ``G''--garbage collection)

\problem Load the submodel implementation in the 6.044 ftp directory and evaluate
\begin{lisp}
(smeval
 '((define (factorial_0 n)
     (if (= n 0)
         1
         (* (factorial_0 (dec n)) n)))
   (factorial_0 4)))
\end{lisp}
Turn in the final 10 steps of output.  What can you conclude about the
order of evaluation of the operands in a combination in this
implementation of the term rewriting model?

\problem Write a ``self-reproducing'' Scheme expression, $M$: evaluation
of $M$ in the initial Scheme environment ({\em without} any prior
user-created definitions) returns a value which prints as $M$.  (\hint
Letting $M$ be the combination
\[\Code{(make-quoted-self-application 'make-quoted-self-application)}\]
would work if the definition of \Code{make-quoted-self-application} given
in class was part of the initial environment.)

\end{document}
