% -*- Mode: Tex -*-

%\input /home/welg/6001mac.tex
%\input /homes/welg/6001/6001mac.tex
%\input /zu/scheme/6001ARCHIVE/fall89/6001mac.tex
\input ./6001mac.tex

{\obeyspaces\gdef {\ }}

\def\brule#1{\vrule width#1 height -1.1pt depth 1.5pt\relax}

\def\fbox#1{%
  \vtop{\vbox{\hrule%
              \hbox{\vrule\kern3pt%
                    \vtop{\vbox{\kern3pt#1}\kern3pt}%
                    \kern3pt\vrule}}%
        \hrule}}

\def\emptybox#1#2{\fbox{\vbox to #2{\hbox to #1 {\null}}}}

\def\pscenter#1{\hbox to\hsize{\hss\psadobenomag{#1}\hss}}

\setlength{\textheight}{9.2in}

\begin{document}

\psetheader{Spring Semester, 1998}{Recitation -- Friday, April 24}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf 1. Student Presentation}

Yesterday, we saw a language that incorporates choice and search into
its control structure. Do Exercise 4.44 (Write a program to solve the
eight queens problem). Show your solution and explain it to the class.

\vskip .08in

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf 2. A Puzzle}

Let's take a look at Exercise 4.42 from the text (page 420):

Five schoolgirls sat for an examination.  Their parents - so they
thought - showed an undue degree of interest in the result.  They
therefore agreed that, in writing home about the examination, each
girl should make one true statement and one untrue one.  The following
are the relevant passages from their letters:

\begin{itemize}
\vspace{-0.12in}
\item Betty: ``Kitty was second.  I was third.''
\vspace{-0.07in}
\item Ethel: ``I was first.  Joan was second.''
\vspace{-0.07in}
\item Joan:  ``I was third.  Ethel was last.''
\vspace{-0.07in}
\item Kitty: ``I was second.  Mary was fourth.''
\vspace{-0.07in}
\item Mary:  ``I was fourth.  Betty was first.''
\end{itemize}

Write a Amb-Scheme program to determine the order in which the five
girls placed.

\beginlisp
(define (solve-liars)
%   (let ((betty (amb 1 2 3 4 5))
%         (ethel (amb 1 2 3 4 5))
%         (joan (amb 1 2 3 4 5))
%         (kitty (amb 1 2 3 4 5))
%         (mary (amb 1 2 3 4 5)))
%     (require (distinct (list betty ethel joan kitty mary)))
%     (require (one-lie (= kitty 2) (= betty 3)))
%     (require (one-lie (= ethel 1) (= joan 2)))
%     (require (one-lie (= kitty 3) (= ethel 5)))
%     (require (one-lie (= kitty 2) (= mary 4)))
%     (require (one-lie (= mary 4) (= betty 1)))
%     (list (list 'betty betty)
%           (list 'ethel ethel)
%           (list 'joan joan)
%           (list 'kitty kitty)
%           (list 'mary mary)))
\null
\null
\null
\null
\null
\null
\null
\null
\null
\null
)
\null
(define (one-lie x y)
%  (if x (not y) y)
\null
)
\endlisp

\beginlisp
;;; Amb-Eval input:
(solve-liars)
;;; Starting a new problem 
;;; Amb-Eval value:
((betty 3) (ethel 5) (joan 2) (kitty 1) (mary 4))

;;; Amb-Eval input:
try-again
;;; There are no more values of
(solve-liars)
\endlisp


{\Large\bf 3. Continuations -- You Never Return!}

\beginlisp
(define (ambeval exp env succeed fail)
  ((analyze exp) env succeed fail))
\endlisp

An execution procedure is of the form 
\beginlisp
 (lambda (env succeed fail) ...)
\endlisp

A succeed procedure is of the form 
\beginlisp
    (lambda (value fail) ...)
\endlisp

A fail procedure is of the form 
\beginlisp
        (lambda () ...)
\endlisp

What do we mean when we say ``Nothing Ever Returns?''
Take a look at any of the {\tt analyze-foo} definitions.  They never
return a value.  Instead they call either the success or failure
continuation.

\beginlisp
(define (analyze-self-evaluating exp)
  (lambda (env succeed fail)
     (succeed exp fail)))
\endlisp

Consider what happens when we evaluate {\tt (not x)} in the {\bf
normal} way:

\beginlisp
(eval '(not x) tge)
      --> (eval 'not tge)
\{not\} <--
      --> (eval 'x tge)
\#t    <--
      --> (apply \{not\} \#t)
\#f    <--
\endlisp

Now consider what happens when we evaluate 
\beginlisp
(ambeval '(not x) tge s f)
\endlisp

\beginlisp
(ambeval 'not tge
  (lambda (prim f2)
    (ambeval 'x tge
      (lambda (arg f3)
        (s (prim arg)))
      f2)
  f))
\endlisp

\vspace{0.1in}

{\Large\bf 4. Adding {\tt require}}

Let's take a look at Exercise 4.54 from the text:

If we had not realized that {\tt require} could be implemented as an
ordinary procedure that uses {\tt amb}, we would have had to implement
it as a special form.  

{\bf (1) Add Data Abstraction}

\beginlisp
(define (require? exp)  \brule{1.5in})
% (tagged-list? exp 'require)
(define (require-predicate exp)  \brule{1.5in})
% (cadr exp)
\endlisp

{\bf (2) Add a new clause in {\tt analyze}}

\beginlisp
% ((require? exp) (analyze-require exp))
\null
\endlisp

{\bf (3) Write {\tt analyze-require}}

\beginlisp
(define (analyze-require exp)
  (let ((pproc (analyze (require-predicate exp))))
    (lambda (env succeed fail)
      (pproc env
             (lambda (pred-value fail2)
               (if \brule{1in}
% not pred-value)
                   \brule{1in}
%                   (fail2)
                   (succeed 'ok fail2)))
             fail))))
\endlisp
        


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
