ch4.tex

\chapter{Metalinguistic Abstraction}

\section{The Metacircular Evaluator}

\subsection{The Core of the Evaluator}

\begin{exe}[4.1]
    We can put the value to evaluate first inside a \vscm{let} expression. Since 
    the \vscm{let} is transformed into a \vscm{lambda} internally, we know that 
    its argument will be evaluated before the body of the \vscm{let}.
    \scm{ch4/4.01.scm}
\end{exe}

\subsection{Representing Expressions}

\begin{exe}[4.2]
    \ \vspace{-20pt}
    \begin{enumerate}
        \item The test to determine whether an expression is a procedure just 
            checks whether it is a pair, so it will return true for all list 
            expressions: \vscm{if}, \vscm{cond}, \vscm{begin}, \vscm{define}, 
            \vscm{set!}, etc., and the evaluator will try to apply the procedure 
            \vscm{if}, \vscm{cond}, etc. to the rest of the arguments. It’s not 
            possible to transform the special forms into procedures because all 
            the arguments of a procedure are evaluated before evaluation.
        \item The only required change to \vscm{eval} is to put the 
            \vscm{application?} test first. Then we only need changing the 
            definition of the \vscm{application?} predicate and the associated 
            selectors so they reflect the new syntax.
	    \scm{ch4/4.02.scm}
    \end{enumerate}
\end{exe}

\begin{exe}[4.3]
    As in \autoref{2.73}, a few cases can’t be assimilated to the data-directed 
    dispatch because they correspond to untagged data: here it’s the case of 
    \vscm{variable?}, \vscm{self-evaluating?} and \vscm{application?}. If we had 
    kept Louis’ idea from the previous exercise to start procedure applications 
    with \vscm{call}, \vscm{application?} could have been assimilated into the 
    dispatch. Since we don’t keep this idea, we have to redefine the 
    \vscm{application?} predicate: if we keep it as \vscm{pair?} we can’t put it 
    before the dispatch because all the special forms will be considered as 
    procedure applications, and we can’t put it after the dispatch either 
    because the procedure won’t be found in the table and it will cause an 
    error. So I consider that every expression for which no procedure of the 
    correct type is found in the table is a procedure application. I used 
    a two-dimensional table as in chapter 2, though a one-dimensional table 
    would be enough if we don’t do any other dispatch on the expressions’ type.
    \scm{ch4/4.03.scm}
\end{exe}

\begin{exe}[4.4]
    \label{4.4}
    If we define specific evaluation procedures \vscm{eval-and} and 
    \vscm{eval-or}, we have to add the following two lines to the definition of 
    \vscm{eval}
    \scm{ch4/4.04a.scm}
    Then we can implement the predicates, selectors and the evaluation 
    procedures in the following way:
    \scm{ch4/4.04b.scm}
    If \vscm{and} and {or} are implemented as derived expressions, the 
    predicates and selectors don’t change, but the lines regarding \vscm{and} 
    and \vscm{or} in \vscm{eval} are replaced by:
    \scm{ch4/4.04c.scm}
    And the procedures transforming \vscm{and} and \vscm{or} expressions into 
    \vscm{if} expressions can be defined as:
    \scm{ch4/4.04d.scm}
\end{exe}

\begin{exe}[4.5]
    \label{4.5}
    We only need to add the appropriate predicate and selectors for this type of 
    clause so that the appropriate action is taken if the predicate evaluates to 
    a true value.
    \scm{ch4/4.05.scm}
\end{exe}

\begin{exe}[4.6]
    \label{4.6}
    The only necessary modification to \vscm{eval} is to add the line:
    \scm{ch4/4.06b.scm}
    Then we can define the appropriate predicate and selectors and the 
    transformation procedure \vscm{let->combination} in the following way:
    \scm{ch4/4.06.scm}
\end{exe}

\begin{exe}[4.7]
    \label{4.7}
    A \vscm{let*} expression can be rewritten as a set of nested \vscm{let} 
    expressions defining only one binding at a time, so that the second binding 
    is defined in the body of the first \vscm{let} etc. For instance, the 
    example from the book becomes:
    \scm{ch4/4.07b.scm}
    If we have already implemented \vscm{let}, it is sufficient to rewrite 
    \vscm{let*} expressions in terms of \vscm{let} expressions to handle them. 
    This can be done in the following way:
    \scm{ch4/4.07.scm}
\end{exe}

\begin{exe}[4.8]
    \label{4.8}
    To support named \vscm{let}, we modify the selectors for \vscm{let} so they 
    handle both named \vscm{let}s and ordinary \vscm{let}s, and 
    \vscm{let->combination} so the generated code creates a procedure with the 
    given name instead of a lambda.
    \scm{ch4/4.08.scm}
\end{exe}

\begin{exe}[4.9]
    \label{4.9}
    I chose to implement three iterative control structures: a \vscm{while} 
    loop, an \vscm{until} loop, and a \vscm{for} loop. The return value of all 
    the expressions described is \vscm{false}, so they are useful only for their 
    side effects. The \vscm{until} and the \vscm{for} constructs are derived 
    from \vscm{while}.
    \begin{itemize}
        \item[\emph{while}] The syntax of the \vscm{while} loop is
            \vscm{(while <predicate> <body>)}. The predicate must consist of 
            a single expression. The body can consist of several expressions. 
            The body is executed while the predicate is true. If the predicate 
            is false from the beginning, the body is never evaluated.

            For instance, the evaluation of the following code prints the 
            numbers from 0 to 5 inclusive, each on a new line:
            \begin{cscm}
                (define x 0)
                (while (<= x 5)
                    (display x)
                    (newline)
                    (set! x (+ x 1)))
            \end{cscm}
            The transformation procedure for \vscm{while} expressions turns them 
            into the definition of a recursive procedure that uses the predicate 
            to decide whether to execude the body of the \vscm{while} or not, 
            followed by a call to this procedure. The procedure name is 
            generated by \vscm{gensym}, so it does not conflict with other names 
            in the program, and if two \vscm{while} are evaluated in the same 
            environment, the generated procedures will have different names.
            \scm{ch4/4.09while.scm}
        \item[\emph{until}] The syntax of the \vscm{until} loop is
            \vscm{(until <predicate> <body>)}, and such an expression is 
            equivalent to \vscm{(while (not <predicate>) <body>)}. For instance, 
            the following code prints the numbers from 0 to 4 inclusive, each on 
            a new line:
            \begin{cscm}
                (define x 0)
                (until (= x 5)
                    (display x)
                    (newline)
                    (set! x (+ x 1)))
            \end{cscm}
            \vscm{Until} expressions are easily derived from \vscm{while} 
            expressions in the following way:
            \scm{ch4/4.09until.scm}
        \item[\emph{for}] The general syntax of the \vscm{for} loop is
            \vscm{(for (<var> <start> <end-test> [<inc-exp>]) <body>)}. The body 
            can consist of several expressions. The other parts are:
            \begin{itemize}
                \item \vscm{<var>}: the name of the variable whose value is 
                    bound by the \vscm{for} loop.
                \item \vscm{<start>}: an expression giving the initial value of 
                    the variable.
                \item \vscm{<end-test>} can be either:
                    \begin{itemize}
                        \item an expression where \vscm{<var>} appears as a free 
                            variable, for instance \vscm{(< <var> 3)}. The body 
                            of the \vscm{for} is evaluated as long as the 
                            evaluation of this expression with the current value 
                            of \vscm{<var>} returns \vscm{true}.
                        \item an expression not depending on the variable bound 
                            by the \vscm{for}, whose evaluation must return 
                            a number. This is equivalent to either
                            \vscm{(<= <var> <end-test>)} or
                            \vscm{(>= <var> <end-test>)}, depending on whether 
                            the returned value is greater or smaller than the 
                            initial value.
                    \end{itemize}
                \item \vscm{<inc-exp>} can be either:
                    \begin{itemize}
                        \item an expression where \vscm{<var>} appears as a free 
                            variable, for instance \vscm{(+ <var> 2)}. It is 
                            evaluated to update the value of \vscm{<var>} before 
                            evaluating (or not) the body of the \vscm{for} 
                            again.
                        \item an expression not depending on the variable bound 
                            by the \vscm{for}, whose evaluation must return 
                            a number. This is equivalent to specifying
                            \vscm{(+ <var> <inc-exp>)}.
                        \item empty, in which case it will be assumed to be 1.
                    \end{itemize}
            \end{itemize}
            For instance, the following expressions all print the numbers from 
            0 to 5:
            \begin{cscm}
                (for (x 1 (<= x 5) (+ x 1)) (display x) (newline))

                (for (x 1 (<= x 5) 1) (display x) (newline))

                (for (x 1 (<= x 5)) (display x) (newline))

                (for (x 1 5 (+ x 1)) (display x) (newline))

                (for (x 1 5 1) (display x) (newline))

                (for (x 1 5) (display x) (newline))
            \end{cscm}
            Using a step other than one, we can print 1, .8, .6, .4, .2 and 
            0 with:
            \begin{cscm}
                (for (x 1 -.1 -.2)
                    (display x) (newline))
            \end{cscm}
            With an update function that is not simply an addition or 
            subtraction, the following prints 16, 8, 4, 2 and 1.
            \begin{cscm}
                (for (x 16 1 (/ x 2))
                    (display x) (newline))
            \end{cscm}
            It’s possible to use nested \vscm{for}s, for instance:
            \begin{cscm}
            (for (x 0 5)
                (for (y (+ x 1) (+ x 2))
                    (display x)
                    (display ", ")
                    (display y)
                    (newline)))
            \end{cscm}
            The output is:
            \begin{cscm}
                0, 1
                0, 2
                1, 2
                1, 3
                2, 3
                2, 4
                3, 4
                3, 5
                4, 5
                4, 6
                5, 6
                5, 7
            \end{cscm}
    \end{itemize}
    The implementation is more complex than that of \vscm{while}, because 
    several cases have to be considered. I had to write a procedure that checks 
    whether a given variable appears as a free variable in a given expression. 
    Then the different cases have to be considered when constructing the 
    predicate that tests whether to interrupt the loop or not, and the procedure 
    that updates the value of the variable. The \vscm{for} expression is then 
    transformed in a \vscm{let} expression containing a \vscm{while}.
    \scm{ch4/4.09for.scm}
\end{exe}

\begin{exe}[4.10]
    It’s easy to modify the symbol used as the \vscm{car} of an expression to 
    define its type: we only need changing the predicate (and the associated 
    constructor if any was defined) for this type of expression. For instance, 
    we can replace \vscm{cond} with \vscm{case}, \vscm{and} with \vscm{&&}, and 
    \vscm{or} with \vscm{||} with the following code:
    \scm{ch4/4.10a.scm}

    We can replace \vscm{not} with \vscm{!} by replacing
    \vscm{(list 'not not)} with \vscm{(list '! not)} in the list of primitive 
    procedures and redefining the \vscm{make-not} procedure defined in 
    \autoref{4.9}:
    \scm{ch4/4.10b.scm}

    I also modified the selectors for procedure application so that
    \vscm{(proc args)} becomes \vscm{(proc (args))}. This change actually makes 
    the syntax more complex since e.g. \vscm{(not (> x 3))} has to be written 
    \vscm{(! ((> (x 3))))}, it’s just for the sake of the example.
    \scm{ch4/4.10c.scm}

    I think that more dramatic changes such as replacing the parentheses with 
    brackets would require a lot of work since currently we rely on the 
    underlying Scheme for list processing.
\end{exe}

\subsection{Evaluator Data Structures}

\begin{exe}[4.11]
    If each binding is represented as a name-value pair, each frame represents 
    a table, so we can simplify the implementation by using \vscm{assoc}. We can 
    change the implementation by rewriting the following procedures:
    \scm{ch4/4.11.scm}
\end{exe}

\begin{exe}[4.12]
    \label{4.12}
    We can define a procedure that recursively traverses the environment 
    structure and executes the given action when a binding is found for the 
    given variable as shown below. By default, the procedure goes to the 
    enclosing environment if the procedure is not found in the first frame, but 
    a second procedure can be passed as an argument to specify another behavior.

    Implementation for the representation of frames as a pair of lists:
    \scm{ch4/4.12a.scm}
    Implementation for the reperesentation of frames as a list of pairs:
    \scm{ch4/4.12b.scm}
\end{exe}

\begin{exe}[4.13]
    The solutions I read on the internet unbind variables only from the first 
    frame of the environment because modifying the enclosing environment seemed 
    too risky or similar reasons. I chose to delete the first binding found even 
    if it’s not in the first frame: the interpreter implementation already 
    allows us to change bindings in the enclosing environments, e.g. if I define 
    a function
    \vscm{(define (f x) (set! + -) x)}, the sequence of interactions:
    \begin{cscm}
	(+ 2 1)
	(f 2)
	(+ 2 1)
    \end{cscm}
    produces 3, 2 and 1. This choice is thus coherent with the rest of the 
    implementation.

    To add the \vscm{make-unbound!} operation, we add to \vscm{eval} the line:
    \begin{cscm}
	((unbind? exp) (eval-unbind exp env))
    \end{cscm}
    The necessary procedures with the implementation of frames as a pair of 
    lists are:
    \scm{ch4/4.13a.scm}

    The implementation of \vscm{delete-binding-from-frame} is simpler with 
    a list of pairs than with a pair of lists because there is only one list to 
    modify, and the list is headed, so the case where the variable to unbind is 
    the first in the frame need not be handled separately:
    \scm{ch4/4.13b.scm}
\end{exe}

\subsection{Running the Evaluator as a Program}

\begin{exe}[4.14]
    \label{4.14}
    Louis’ \vscm{map} fails because the \vscm{map} procedure from the underlying 
    Scheme is called with a procedure representation from the interpreter as the 
    procedure to apply with the underlying Scheme’s \vscm{apply}, and it 
    considers that representation as a list and not as a procedure.
\end{exe}

\subsection{Data as Programs}

\begin{exe}[4.15]
    Let’s assume that \vscm{(halts? try try)} returns true. Then 
    \vscm{(run-forever)} is executed so \vscm{(try try)} does not halt.

    Let’s assume that on the contrary, \vscm{(halts? try try)} returns false. 
    Then \vscm{(try try)} halts.

    Both assumptions lead to a contradiction, so such a \vscm{halts?} procedure 
    can’t exist.
\end{exe}

\subsection{Internal Definitions}

\begin{exe}[4.16]
    \label{4.16}
    \ \vspace{-20pt}
    \begin{enumerate}
        \item Here is the updated version of \vscm{lookup-variable-value} for 
	    the frame representation as a list of pairs, with the abstractions 
	    defined in \autoref{4.12}:
            \scm{ch4/4.16a.scm}
        \item The \vscm{scan-out-defines} procedure can be defined as:
            \scm{ch4/4.16b.scm}
            No transformation must be done if no definition is found because 
            \vscm{let} expressions are transformed into procedure applications, 
            so this would lead to infinite loops. The \vscm{*unassigned*} symbol 
            has to be quoted twice so that the returned code contains a quoted 
            symbol.
        \item It is better to install \vscm{scan-out-defines} in 
            \vscm{make-procedure} than in \vscm{procedure-body}, because the 
            latter is called every time the procedure is applied, while the 
            former is called only when it is defined.
            \scm{ch4/4.16c.scm}
    \end{enumerate}
\end{exe}

\begin{exe}[4.17]
    \begin{figure}
        \begin{tikzpicture}[>=Stealth, thick,
            code/.append style={font=\ttfamily},
            label distance=5mm]
            % Sequential evaluation
            \matrix[column sep=2\nametoenv, column 2/.style={anchor=west},
            label=below:{Sequential evaluation}] (gem1) {
            \node[text width=1cm, align=right] (ge1) {global\\ env};
            & \node[env,minimum width=4cm, minimum height=1cm] (geb1) 
            {};\\[+1.5cm]

            & \node[code] (vars1) {\ <vars>: <vals>}; \\
            \node[text width=1cm, align=right] (e11) {E1};
            & \node[code] (u1) {\ u: <e1>}; \\
            & \node[code] (v1) {\ v: <e2>}; \\
            };

            \begin{scope}[on background layer]
                \node[env, minimum width=4cm, fit=(vars1) (u1) (v1), below=of 
                geb1,yshift=-2mm] (e1b) {};
            \end{scope}

            \draw[->] (ge1) -- (ge1.west -| geb1.west);
            \draw[->] (e11) -- (e11.east -| e1b.west);
            \draw[->] (e1b) -- (geb1);

            % After scanning out defines
            \matrix[column sep=2\nametoenv, column 2/.style={anchor=west},
            right=of gem1, label=below:{After scanning out}] {
            \node[text width=1cm, align=right] (ge2) {global\\ env};
            & \node[env,minimum width=4cm, minimum height=1cm] (geb2) 
            {};\\[+1.5cm]

            \node[text width=1cm, align=right] (e12) {E1};
            & \node[code] (vars2) {\ <vars>: <vals>}; \\[+1.5cm]

            \node[text width=1cm, align=right] (e2) {E2};
            & \node[code] (u2) {\ u: <e1>}; \\
            & \node[code] (v2) {\ v: <e2>}; \\
            };

            \begin{scope}[on background layer]
                \node[env, minimum width=4cm, fit=(vars2), below=of 
                geb2,yshift=-2.5mm] (e12b) {};
                \node[env, minimum width=4cm, fit=(u2) (v2), below=of 
                e12b,yshift=-1mm] (e2b) {};
            \end{scope}

            \draw[->] (ge2) -- (ge2.west -| geb2.west);
            \draw[->] (e12) -- (e12.east -| e12b.west);
            \draw[->] (e12b) -- (geb2);
            \draw[->] (e2) -- (e2.east -| e2b.west);
            \draw[->] (e2b) -- (e12b);
        \end{tikzpicture}
        \caption{Environment structures in which \vscm{<e3>} is evaluated when 
        the definitions are interpreted sequentially and after scanning out.}
        \label{4.17fig}
    \end{figure}
    \autoref{4.17fig} shows the environment structures in which \vscm{<e3>} is 
    evaluated when the definitions are interpreted sequentially and when they 
    are scanned out. In the latter case, there is an extra frame because 
    \vscm{let} corresponds to a \vscm{lambda} application.

    This difference in environment structure makes no difference in a correct 
    program’s behavior because the same bindings are accessible when the body of 
    the procedure is evaluated, and since the inner \vscm{let} contains the 
    whole body of the outer lambda, both frames in the latter case always go 
    together: if the outer lambda returns a procedure, its environment will be 
    E2, it can never be E1, so there can be no lost bindings.

    A possible solution would be to move all the inner definitions to the top of 
    the procedure body. This will work only if the values of the defined 
    variables don’t use the value of a variable defined later. This can be 
    implemented in the following way:
    \scm{ch4/4.17.scm}
\end{exe}

\begin{exe}[4.18]
    This procedure won’t work if internal definitions are scanned out as in this 
    exercise because the value of \vscm{y} is needed to evaluate the value of 
    \vscm{dy}, and in the exercise the value has been computed but not yet 
    assigned to \vscm{y}.

    It works if internal definitions are scanned out as shown in the text.
\end{exe}

\begin{exe}[4.19]
    Inner definitions should be simultaneous, so Eva is right, but if it’s too 
    difficult to implement internal definitions so they behave that way, it’s 
    better to signal an error than to use an incorrect value as Ben suggests.

    To implement Eva’s idea, we would have to sort the definitions so that if 
    the value of a defined variable is needed to compute another’s value, it 
    should come first. However, it won’t always be possible, definitions such as
    \begin{cscm}
	(define (f x)
	    (define a (+ b 5))
	    (define b (+ a 1))
	    <exps>)
    \end{cscm}
    should result in an error. But there are cases of mutual recursion that 
    work, so it’s not enough to scan the defined symbols’ names in other defined 
    symbols’ values to order the definitions: mutually recursive procedure 
    definitions are not problematic as long as neither procedure is called 
    before both are defined. Mutual recursion is not problematic either in cases 
    where evaluation is delayed, as in the \vscm{solve} example. A symbol could 
    also appear at a place where it will never be evaluated, for instance:
    \begin{cscm}
	(define (f x)
	    (define a (if (> 0 1) (* b 2) 3))
	    (define b 5)
	    <exps>)
    \end{cscm}
    So it seems difficult to implement a general solution that does what Eva 
    prefers.

    \medskip

    Another possible solution is to make definitions and assignments lazy by 
    automatically delaying their values’ evaluation, and forcing them only when 
    a variable’s value is looked up. This is a big change to Scheme’s evaluation 
    order, but since we have already seen how to use \vscm{delay} and 
    \vscm{force} in \secref{3.5} this is not difficult to implement. We need to 
    redefine \vscm{eval-definition} and \vscm{eval-assignment} so they delay the 
    values’ evaluation:
    \scm{ch4/4.19a.scm}
    Then we must call \vscm{force} when we look up a variable’s value, for 
    instance by modifying the \vscm{variable?} case in \vscm{eval}:
    \scm{ch4/4.19b.scm}
\end{exe}

\begin{exe}[4.20]
    \label{4.20}
    \ \vspace{-20pt}
    \begin{figure}
        \begin{tikzpicture}[>=Stealth, thick,
            code/.append style={font=\ttfamily},
	    label distance=5mm,
	    env/.append style={minimum width=3cm, minimum height=1cm}]
	    % With letrec
	    \matrix[column sep=2\nametoenv, column 2/.style={anchor=west}, 
	    label={[xshift=1cm]above:{With letrec}}] (gem1) {
            \node[text width=1cm, align=right] (ge1) {global\\ env};
	    & \node[code] (gec1) {\ f: ...};\\[+1.5cm]

	    \node[text width=1cm, align=right] (e111) {E1};
	    & \node[code] (x1) {\ x: 5}; \\[+1.5cm]

	    \node[text width=1cm, align=right] (e11) {E2};
	    & \node[code] (even1) {\ even?:}; \\
	    & \node[code] (odd1) {\ odd?:}; \\
	    };

            \begin{scope}[on background layer]
		\node[env, fit=(gec1), xshift=2\nametoenv] (geb1) {};
		\node[env, fit=(x1), below=of geb1, yshift=-2mm] (e21b) {};
		\node[env, fit=(even1) (odd1), below=of e21b] (e1b) {};
            \end{scope}

	    \coordinate (odd1px) at ($ (e1b.south west)!.5!(e1b.south) $);
	    \coordinate[below=of odd1px] (odd1p);
	    \procedure{odd1p}{oc1}{oe1}
	    \draw[->] (oe1) -- (oe1 |- e1b.south);
	    \draw[->] (odd1.south -| odd1p) -- ($ (odd1p) + (0, \circleradius) 
	    $);

	    \coordinate (even1px) at ($ (e1b.south)!.5!(e1b.south east) $);
	    \coordinate[below=of even1px] (even1p);
	    \procedure{even1p}{ec1}{ee1}
	    \draw[->] (ee1) -- (ee1 |- e1b.south);
	    \draw[->] (even1.east) -| ($ (even1p) + (0, \circleradius) $);

            \draw[->] (ge1) -- (ge1.west -| geb1.west);
            \draw[->] (e11) -- (e11.east -| e1b.west);
	    \draw[->] (e111) -- (e111.east -| e21b.west);
	    \draw[->] (e21b) -- (geb1);
	    \draw[->] (e1b) -- (e21b);

	    % With let
	    \matrix[right=3cm of gem1, column sep=2\nametoenv, column 
	    2/.style={anchor=west},
	    label={[xshift=1cm]above:{With let}}] {
	    \node[text width=1cm, align=right] (ge2) {global\\ env};
	    & \node[code] (gec2) {\ f: ...};\\[+1.5cm]

	    \node[text width=1cm, align=right] (e112) {E1};
	    & \node[code] (x2) {\ x: 5}; \\[+1.5cm]

	    \node[text width=1cm, align=right] (e12) {E2};
	    & \node[code] (even2) {\ even?:}; \\
	    & \node[code] (odd2) {\ odd?:}; \\
	    };

            \begin{scope}[on background layer]
		\node[env, fit=(gec2), xshift=2\nametoenv] (geb2) {};
		\node[env, fit=(x2), below=of geb2, yshift=-2mm] (e22b) {};
		\node[env, fit=(even2) (odd2), below=of e22b] (e2b) {};
            \end{scope}

	    \coordinate (odd2px) at ($ (e2b.south west)!.5!(e2b.south) $);
	    \coordinate[below=of odd2px] (odd2p);
	    \procedure{odd2p}{oc2}{oe2}
	    \draw[->] (oe2) -- ($ (oe2) + (0,-.8cm) $) -- ++(3cm,0) |-
	    ($ (e22b.east)!.4!(e22b.north east) $);
	    \draw[->] (odd2.south -| odd2p) -- ($ (odd2p) + (0, \circleradius) 
	    $);

	    \coordinate (even2px) at ($ (e2b.south)!.5!(e2b.south east) $);
	    \coordinate[below=of even2px] (even2p);
	    \procedure{even2p}{ec2}{ee2}
	    \draw[->] (ee2) -- ($ (ee2) + (1cm,0) $) |-
	    ($ (e22b.east)!.4!(e22b.south east) $);
	    \draw[->] (even2.east) -| ($ (even2p) + (0, \circleradius) $);

            \draw[->] (ge2) -- (ge2.west -| geb2.west);
            \draw[->] (e12) -- (e12.east -| e2b.west);
	    \draw[->] (e112) -- (e112.east -| e22b.west);
	    \draw[->] (e22b) -- (geb2);
	    \draw[->] (e2b) -- (e22b);
	\end{tikzpicture}
	\caption{Environment structures in which \vscm{<rest of body of f>} is 
	evaluated during evaluation of the expression \vscm{(f 5)}.}
	\label{4.20fig}
    \end{figure}
    \begin{enumerate}
	\item \vscm{Letrec} can be implemented as shown below. This is very 
	    similar to \autoref{4.16}, so the code could be mutualized:
	    \scm{ch4/4.20.scm}
	\item \autoref{4.20fig} shows the environment structures in which the 
	    \vscm{<rest of body of f>} is evaluated during evaluation of the 
	    expression \vscm{(f 5)}, first with \vscm{letrec}, then with 
	    \vscm{let}. With \vscm{letrec}, the values of \vscm{odd?} and 
	    \vscm{even?} are evaluated in an environment where the bindings 
	    already exist, so the procedures created point to an environment 
	    where the other is defined. With \vscm{let}, the values of 
	    \vscm{even?} and \vscm{odd?} are evaluated before the bindings 
	    exist, so they point to an environment where they are undefined and 
	    the recursive calls won’t work.
    \end{enumerate}
\end{exe}

\begin{exe}[4.21]
    \ \vspace{-20pt}
    \begin{enumerate}
        \item The trick used here is to modify the recursive procedure 
            (\vscm{(lambda (ft k) ...)} in the exercise) so it takes as an 
            additional parameter the procedure to call where a recursive call 
            would be used otherwise, and the argument used is the modified 
            procedure itself. The first inner \vscm{lambda}
	    (\vscm{(lambda (fact) ...)}) is used to do the initial call to the 
	    modified (derecursified?) procedure.

	    The Fibonacci numbers can be computed similarly:
	    \scm{ch4/4.21a.scm}

        \item This time, since there are two mutually recursive procedures, two 
            procedure parameters are needed to pass around the procedures to 
            call when we are not in the terminal case.
	    \scm{ch4/4.21b.scm}
    \end{enumerate}
\end{exe}

\subsection{Separating Syntactic Analysis from Execution}

\begin{exe}[4.22]
    Since \vscm{let} is a derived form, all that’s needed to support it is to 
    add the following line to \vscm{analyze}:
    \scm{ch4/4.22a.scm}
    \begin{comp}
        We can just as easily add support for all the derived forms implemented 
        in the previous exercises:
        \scm{ch4/4.22b.scm}
        We need to implement \vscm{analyze} procedures to support the versions of 
        \vscm{or} and \vscm{and} defined with special evaluation functions, as 
        well as \vscm{make-unbound!}:
        \scm{ch4/4.22c.scm}
	Lastly, we can implement scanning out of internal definitions as in 
	\autoref{4.16} by calling \vscm{scan-out-defines} in 
	\vscm{analyze-lambda}:
        \scm{ch4/4.22d.scm}
    \end{comp}
\end{exe}

\begin{exe}[4.23]
    If the sequence has just one expression, the procedure produced by Alyssa’s 
    program tests the \vscm{cdr} of \vscm{procs}, finds that it’s null and then 
    calls the first procedure. The program in the text does the test during 
    analysis and returns the result of analyzing the expression directly, so the 
    only work done during evaluation is to call it.

    For a sequence with two expressions, Alyssa’s procedure will loop through 
    the procedures each time the sequence is evaluated, while the procedure from 
    the text loops through them only once during analysis.
\end{exe}

\begin{exe}[4.24]
    I wrote a small procedure to interpret code with the interpreter without 
    using the REPL (I should probably have done that some time ago…):
    \scm{ch4/4.24a.scm}
    I then ran the following two tests: one with a recursive procedure and the 
    other with a non-recursive procedure:
    \scm{ch4/4.24b.scm}
    With the evaluator in this section, the first test evaluates in 7877~ms, the 
    second one in 36~ms.

    With the original version, the first test evaluates in 16024~ms, the second 
    one in 79~ms.

    Separating analysis from execution speeds up execution by a factor of more 
    than two, so we can estimate that about half the time was spent in analysis 
    with the original version of the evaluator.
\end{exe}

\section{Variations on a Scheme―Lazy Evaluation}

\subsection{Normal Order and Applicative Order}

\begin{exe}[4.25]
    If we attempt to evaluate \vscm{(factorial 5)}, we will get an infinite loop 
    since Scheme attempts to evaluate the second argument to \vscm{unless} 
    recursively.

    It would work in a normal-order language.
\end{exe}

\begin{exe}[4.26]
    Ben is right that it’s possible to define \vscm{unless} as a derived 
    expression:
    \scm{ch4/4.26a.scm}
    Then we just have to have the following line to \vscm{eval}:
    \scm{ch4/4.26b.scm}
    or the following line to \vscm{analyze} for the evaluator from 
    \secref{4.1.7}:
    \scm{ch4/4.26c.scm}

    It would be useful to have \vscm{unless} available as a procedure rather 
    than a special form to use it as a parameter to higher-order procedures, for 
    instance in \vscm{(map unless bools list1 list2)}, which returns a list 
    where the element of index $i$ is:
    \begin{itemize}
	\item the element of index $i$ of \vscm{list2} if the element of index 
	    $i$ in the list \vscm{bools} is true;
	\item the element of index $i$ of \vscm{list1} otherwise.
    \end{itemize}
\end{exe}

\subsection{An Interpreter with Lazy Evaluation}

\begin{exe}[4.27]
    The value of \vscm{count} the first time is 1 because the body of the outer 
    \vscm{id} in the definition of \vscm{w} was evaluated. Then the value of 
    \vscm{w} is 10 as expected, and once \vscm{w} has been forced the value of 
    \vscm{count} is 2 because the inner \vscm{id} in the definition of \vscm{w} 
    was evaluated as well.
\end{exe}

\begin{exe}[4.28]
    This forcing is needed if the operator has been passed as an argument to 
    a higher-order procedure, for instance in \vscm{map}.
\end{exe}

\begin{exe}[4.29]
    Recursive procedures such as \vscm{factorial}, defined as usual as:
    \scm{ch4/4.29.scm}
    run much more slowly without memoization. Let’s compare what happens when we 
    evaluate, for intance \vscm{(factorial 10)} with and without memoization:
    \begin{itemize}
	\item With memoization, the argument is evaluated when the value of 
	    \vscm{(= n 0)} is needed in the \vscm{if} expression. Then 
	    \vscm{(factorial (- n 1))} is evaluated, and the argument passed to 
	    factorial is a thunk containing the expression \vscm{(- n 1)}, where 
	    \vscm{n} is an evaluated thunk with value 10. This new thunk is 
	    transformed into an evaluated thunk with value 9 when testing the 
	    predicate in the \vscm{if}, and this evaluated thunk’s value is 
	    immediately accessible in the evaluation of the argument of the next 
	    call to \vscm{factorial}. And so on until 0 is reached. The time 
	    complexity of the computation is linear, the same as with 
	    applicative-order.
	\item Without memoization, the thunk with value 10 is evaluated in the 
	    \vscm{if} predicate, but it is not transformed into an evaluated 
	    thunk. So the recursive call to \vscm{factorial} has as its argument 
	    a thunk containing \vscm{(- n 1)}, where \vscm{n} is an unevaluated 
	    thunk. Two evaluations are needed to find that the value of this 
	    thunk is 9. Then, for the next recursive call, 3 evaluations are 
	    needed to find that the value of the argument is 8. During the 
	    terminal call, 11 thunk evaluations are needed each time the 
	    argument’s value is needed. As a consequence, the time complexity of 
	    \vscm{factorial} with a lazy evaluator that does not memoize is 
	    quadratic instead of linear.
    \end{itemize}
    Of course, the same happens with any recursive procedure running in linear 
    time, such as \vscm{length} to compute a list’s length.

    \medskip

    The value of \vscm{(square (id 10))} is 100 both when the evaluator memoizes 
    and when it does not. When the evaluator memoizes, the value of \vscm{count} 
    after evaluating \vscm{(square (id 10))} is 1 because \vscm{(id 10)} has 
    been evaluated only once. When the evaluator does not memoize, the value of 
    \vscm{count} is 2 because \vscm{(id 10)} has been evaluated twice.
\end{exe}

\begin{exe}[4.30]
    \ \vspace{-20pt}
    \begin{enumerate}
        \item Ben is right about the behavior of \vscm{for-each} because each 
            expression in the body of the \vscm{begin} expression is evaluated 
            with \vscm{eval}, which causes each expression in the body of 
            \vscm{proc} to be evaluated with each item in turn, so the 
            side-effects they cause do take place.

	    The only case where a side effect could not take place is when the 
	    expression defining it is delayed and then never forced, which can 
	    happen only if that expression was passed as an argument to 
	    a compound procedure, as in b. below.
        \item With the original \vscm{eval-sequence}, the value of
	    \vscm{(p1 1)} is \vscm{(1 2)} because the \vscm{set!} expression in 
	    the body of \vscm{p1} was evaluated. The value of \vscm{(p2 1)} is 
	    \vscm{1} because during the evaluation of \vscm{e} in the body of 
	    \vscm{p}, \vscm{e} is a variable whose value is a thunk containing 
	    an expression defining a side effect, but this expression is never 
	    actually evaluated because \vscm{e}’s value is not used.

	    With Cy’s proposed change to \vscm{eval-sequence}, the values would 
	    be \vscm{(1 2)} for both \vscm{(p1 1)} and \vscm{(p2 1)}.
        \item The proposed change does not affect the behavior of the example in 
            part a. because if the result of \vscm{eval} is not a thunk, 
            applying \vscm{force-it} to it does nothing.
        \item I prefer the approach in the text. I don’t think the change 
            proposed by Cy is necessary because, as noticed in part a., the only 
            case when a side effect could not take place is when the expression 
            causing it―not a procedure containing that expression, unless said 
            procedure is not called of course—is passed as an argument to 
            a compound procedure\footnote{It could also happen if an argument is 
            the result of a procedure application that produces side effects and 
            returns a value. If this argument’s value is not needed in the body 
            of the procedure, the side effects won’t happen, but this is to be 
            expected with normal-order evaluation and this is not directly 
            related to the evaluation of sequences.}, which I don’t think should 
            be done anyway: an expression passed as an argument should be there 
            for its value, not for its side effects, and it does not make much 
            sense to use an expression defining only side effects where a value 
            should be used. For the example of \vscm{p2} in the exercise, if we 
            want to use a parameter of \vscm{p} to define a side-effect before 
            returning \vscm{x}, it is better to use a procedure, and it works 
            without changing the evaluator’s behavior:
	    \scm{ch4/4.30.scm}
	    When reading the definition above, we can tell that the parameter 
	    \vscm{e} should be a procedure, and that it is expected to cause 
	    side-effects because its return value is not used. From reading the 
	    definition of \vscm{p2}, it is not clear at all what the evaluation 
	    of \vscm{e} is expected to do. It would be even less clear with 
	    applicative-order since \vscm{e} would already have been evaluated 
	    before applying \vscm{p}, so evaluating it again in the body of 
	    \vscm{p} would do absolutely nothing.

	    To sum it up, it can indeed happen that some side effects do not 
	    take place with the approach taken in the text, but I think that the 
	    programs where this happens can be modified in a straightforward way 
	    to fix the problem, and furthermore the modification is likely to 
	    make them clearer.
    \end{enumerate}
\end{exe}

\begin{exe}[4.31]
    In order to have both memoized and non memoized thunks, we define a new type 
    of thunk with an associated delay procedure. I chose to define a new type 
    for non memoized thunks. Then we redefine \vscm{force-it} so it handles the 
    three types of thunks―unevaluated non memoized, unevaluated to memoize, and 
    already evaluated—instead of two. And lastly we modify \vscm{apply} so it 
    delays each argument or not as appropriate.
    \scm{ch4/4.31.scm}
\end{exe}

\subsection{Streams as Lazy Lists}

\begin{exe}[4.32]
    With the streams of \secref{3.5}, there were places where we had to define 
    the first element of a stream separately to avoid infinite loops. With the 
    lazy evaluator, we can simplify some of the definitions. For instance, the 
    following definition of \vscm{pairs} taken from \autoref{3.68}, where it 
    caused an infinite loop, works for lazy lists:
    \scm{ch4/4.32a.scm}
    Similar simplifications can be applied to the answers to 
    exercises~\ref{3.69} and~\ref{3.70}.

    \medskip

    As noticed in the text, the values of the elements of the lazy list won’t 
    actually be computed until they are absolutely needed, so that for instance, 
    if we define the lazy lists:
    \scm{ch4/4.32b.scm}
    we get no error, while this would cause an error with streams.

    \medskip

    And if we define a \vscm{length} procedure:
    \scm{ch4/4.32c.scm}
    we can compute \vscm{l2}’s length without trouble since the values of the 
    elements are not used.

    \medskip

    As noted in the book’s footnote, lazy lists allow us to define arbitrary 
    lazy data structures which can’t be defined with the streams of 
    \secref{3.5}, such as trees where all branches could potentially be 
    infinite.
\end{exe}

\begin{exe}[4.33]
    We need to convert the lists from the underlying Scheme to lazy lists using 
    a series of \vscm{cons}. We now need to call \vscm{eval} when evaluating 
    quotations, so the statement for quotations in \vscm{eval} is replaced with:
    \scm{ch4/4.33a.scm}
    and the \vscm{eval-quotation} procedure can be defined as:
    \scm{ch4/4.33b.scm}
\end{exe}

\begin{exe}[4.34]
    My initial idea was to implement \vscm{cons}, \vscm{car} and \vscm{cdr} as 
    special forms. In the end, I decided to find a solution where they are 
    ordinary procedures so that they can be used in higher-order procedures.

    I redefined \vscm{cons} so that it produces a pair with the tag 
    \vscm{lazy-pair}, the actual pair being represented by the same procedure as 
    in the text. But the tagged pair must be produced with the \vscm{cons} 
    procedure from the underlying Scheme, because it needs to be recognized by 
    the implementation language. So we first save the values of \vscm{cons}, 
    \vscm{car} and \vscm{cdr} as initial procedures before redefining them in 
    the interpreter as shown below:
    \scm{ch4/4.34e.scm}
    I also defined a \vscm{lazy-struct->pairs} procedure in the implemented 
    language to transform a structure built from lazy pairs into a structure 
    built from ordinary pairs. It uses the value of the global variables 
    \vscm{*max-depth*} and \vscm{*max-breadth*} to limit the number of items 
    included in the result. The advantage of defining the transformation in the 
    implemented language rather than in the evaluator is that the values of 
    \vscm{*max-depth*} and \vscm{*max-breadth*} can be changed from the driver 
    loop.
    \scm{ch4/4.34f.scm}
    Then we need to define \vscm{lazy-pair?} in the underlying language so that
    the evaluator can identify them:
    \scm{ch4/4.34b.scm}
    Then we can rewrite \vscm{user-print} so it applies 
    \vscm{lazy-struct->pairs} to lazy pairs before printing the result:
    \scm{ch4/4.34d.scm}
    The last step is to modify the evaluator so it treats lazy pairs as 
    self-evaluating values, for instance by adding:
    \scm{ch4/4.34c.scm}
\end{exe}

\section{Variations on a Scheme―Nondeterministic Computing}

\subsection{Amb and Search}

\begin{exe}[4.35]
    \label{4.35}
    The procedure \vscm{an-integer-between} can be defined as:
    \scm{ch4/4.35tex.scm}
\end{exe}

\begin{exe}[4.36]
    Replacing \vscm{an-integer-between} by \vscm{an-integer-starting-from} in 
    the procedure in \autoref{4.35} wouldn’t work because the interpreter would 
    pick the lowest possible value for $i$ and $j$ and would then try all the 
    possible values for $k$ without ever finding a successful triple.

    We can generate all Pythagorean triples by first picking $j$, and then 
    picking $i \leq j$. We can then define $k$ as $\sqrt{i^2 + j^2}$ and check 
    if it’s an integer. To define a procedure more similar to the one in 
    \autoref{4.35}, we could choose $k$ between finite bounds, for instance $j$ 
    and $2j$. Either way, once $j$ has been picked, there are only a finite 
    number of possibilities to test for $i$ and $k$, and these possibilities 
    contain all the Pythagorean triples for the given value of $j$, so all 
    Pythagorean triples could in principle be generated by typing 
    \vscm{try-again}.
    \scm{ch4/4.36tex.scm}
\end{exe}

\begin{exe}[4.37]
    Ben is correct. The procedure in \autoref{4.35} systematically searches all 
    possible triples $(i, j, k)$ with $low \leq i \leq j \leq k \leq high$. 
    Ben’s version eliminates the pairs $(i, j)$ for which $i^2 + j^2 > high^2$ 
    since there is no possible value of $k$ within the bounds in this case, and 
    then instead of trying all possible values for $k$, it tests only whether 
    $\sqrt{i^2 + j^2}$ is an integer, since this is necessarily the value of $k$ 
    if $(i, j, k)$ is a Pythagorean triple.
\end{exe}

\subsection{Examples of Nondeterministic Programs}

\subsubsection{Logic Puzzles}

\begin{exe}[4.38]
    The only modification needed is to remove the line:
    \begin{cscm}
        (require (not (= (abs (- smith fletcher)) 1)))
    \end{cscm}
    Without this requirement, there are five possible solutions:
    \begin{cscm}
        ((baker 1) (cooper 2) (fletcher 4) (miller 3) (smith 5))
        ((baker 1) (cooper 2) (fletcher 4) (miller 5) (smith 3))
        ((baker 1) (cooper 4) (fletcher 2) (miller 5) (smith 3))
        ((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))
        ((baker 3) (cooper 4) (fletcher 2) (miller 5) (smith 1))
    \end{cscm}
\end{exe}

\begin{exe}[4.39]
    The order of the restrictions does not affect the answer. It does affect the 
    time to find an answer but in a limited way: the original procedure takes 
    about 370~ms on my computer, and I can’t do better than about 270~ms with 
    the following order:
    \scm{ch4/4.39tex.scm}

    The only influence of the order of restrictions is that a possibility that 
    leads to a dead end can be rejected after less computation time depending on 
    that order. However, the real reason why the procedure is slow is that a lot 
    of possibilities are explored though they could be ruled out from the start 
    (as shown in the following exercise). For instance, \vscm{cooper} must not 
    be equal to 1, but for a given value of \vscm{baker}, the procedure will 
    explore and eliminate all the $5^3 = 75$ possibilities where \vscm{cooper} 
    is 1 before setting \vscm{cooper} to 2.
\end{exe}

\begin{exe}[4.40]
    Before the requirement that floor assignments be distinct, there are $5^5 
    = 3125$ sets of assignments of people to floors. After that requirement, 
    there are $5! = 120$ such sets.

    The following procedure finds the answer in about 40~ms:
    \scm{ch4/4.40a.scm}
    We can make it even faster by breaking up the
    \vscm{(require (distinct? ...))} requirement into a series of
    \vscm{(require (not (= ...)))} so that any case where two values are not 
    distinct is ruled out as soon as possible. The following procedure solves 
    the problem in about 20~ms:
    \scm{ch4/4.40b.scm}
    It would also be more efficient to modify the list of possibilities in 
    \vscm{amb} for the people with floor restrictions, for instance using 
    \vscm{(amb 2 3 4)} for \vscm{fletcher}. But this could be considered as 
    solving part of the problem for the evaluator instead of stating the 
    solution’s requirements.
\end{exe}

\begin{exe}[4.41]
    Each assignment of people to floors where each floor has a unique person 
    corresponds to a permutation of the set \vscm{(1 2 3 4 5)}, where we can 
    consider that the first number is Baker’s floor, the second number is 
    Cooper’s floor and so on. We can solve the puzzle by generating all the 
    permutations and then filtering the set to keep only those that verify the 
    puzzle’s requirements.

    We already defined a \vscm{permutations} procedure in 
    \secref[Nested-Mappings]{2.2.3}, but I rewrote a different procedure to 
    generate them before remembering that, and then I noticed that my version 
    was faster so I kept it. To generate the permutations of a set $S$, 
    I generate all the permutations of the set minus the first element, and then 
    for each permutation I insert the removed element at each possible position 
    in the returned list. The version in \secref[Nested-Mappings]{2.2.3} 
    generated all permutations of $S - x$ for \emph{each} element $x$ of $S$ and 
    adjoined $x$ at the front of each permutation, whereas I generate all 
    permutations of $S - x$ only for one $x$ and the adjoin $x$ at all possible 
    positions.
    \scm{ch4/4.41.scm}
\end{exe}

\begin{exe}[4.42]
    We can solve the puzzle by defining a \vscm{liars} procedure in the amb 
    evaluator as shown below. It uses the helper procedure \vscm{xor} to 
    simplify the expression of the requirements.
    \scm{ch4/4.42tex.scm}
    The procedure’s output is:
    \begin{cscm}
        ((Betty 3) (Ethel 5) (Joan 2) (Kitty 1) (Mary 4))
    \end{cscm}
    so the order in which the girls were placed was: Kitty, Joan, Betty, Mary, 
    and Ethel.
\end{exe}

\begin{exe}[4.43]
    The puzzle can be solved by the following procedure, where we define lists
    containing the daughter’s name and the boat’s name for each father.
    \scm{ch4/4.43tex.scm}
    Some of the requirements are redundant, for instance since we know the name 
    of Barnacle’s boat and of his daughter, it’s not strictly necessary to check 
    that they are distinct. Keeping these requirements makes it easier to modify 
    the procedure if some constraints are removed.

    The procedure returns a single possible solution, which is
    \begin{cscm}
        ((Moore (Mary-Ann Lorna))
         (Downing (Lorna Melissa))
         (Hall (Gabrielle Rosalind))
         (Barnacle (Melissa Gabrielle))
         (Parker (Rosalind Mary-Ann)))
    \end{cscm}
    so Lorna’s father is Colonel Downing.

    If we are not told that Mary Ann’s father is Moore, the problem has two 
    solutions. The first one is the same as above, the second one is:
    \begin{cscm}
        ((Moore (Gabrielle Lorna))
         (Downing (Rosalind Melissa))
         (Hall (Mary-Ann Rosalind))
         (Barnacle (Melissa Gabrielle))
         (Parker (Lorna Mary-Ann)))
    \end{cscm}
\end{exe}

\begin{exe}[4.44]
    We use the same idea as in \autoref{2.42}: we place a queen in each column 
    successively. Once we have placed $k - 1$ queens in the first $k - 1$ 
    columns, we place a queen in the $k$th column and require that it is safe 
    with respect to the others. The \vscm{safe?} procedure is the same as in 
    \autoref{2.42}.
    \scm{ch4/4.44tex.scm}
\end{exe}

\subsubsection{Parsing natural language}

\begin{exe}[4.45]
    The five ways in which the sentence can be parsed are:
    \begin{itemize}
        \item The professor lectures with the cat, in the class, to the student.
            \scm{ch4/4.45a.scm}
        \item The professor lectures to the student, in the class that has the 
            cat.
            \scm{ch4/4.45b.scm}
        \item The professor lectures with the cat, to the student who is in the 
            class.
            \scm{ch4/4.45c.scm}
        \item The professor lectures to the student in the class, the student 
            has the cat.
            \scm{ch4/4.45d.scm}
        \item The professor lectures to the student, who is in the class that 
            has the cat.
            \scm{ch4/4.45e.scm}
    \end{itemize}
\end{exe}

\begin{exe}[4.46]
    The \vscm{parse-word} procedure looks for the required part of speech at the 
    beginning of the contents of \vscm{*unparsed*}. So with 
    \vscm{parse-sentence} defined as:
    \begin{cscm}
        (define (parse-sentence)
          (list 'sentence
                (parse-noun-phrase)
                (parse-word verbs)))
    \end{cscm}
    when we try to parse \vscm{(the cat eats)}, if \vscm{(parse-word verbs)} is 
    evaluated first, it will fail since \vscm{the} is not in the list of verbs, 
    and there are no alternatives to try.
\end{exe}

\begin{exe}[4.47]
    The change suggested by Louis does not work because the second branch of the 
    \vscm{amb} contains an infinite loop. For instance, if we parse the sentence 
    “The cat eats.”, we get the correct result, but if we then type 
    \vscm{try-again}, there is an infinite loop as the evaluator tries the 
    second branch of the \vscm{amb} in \vscm{parse-verb-phrase}: the recursive 
    call to \vscm{parse-verb-phrase} succeeds as it finds the verb \vscm{eats}, 
    then the call to \vscm{parse-prepositional-phrase} fails since there is 
    nothing left to parse, which causes the second branch of \vscm{amb} to be 
    explored in the recursive call, and so on to infinity.

    If we interchange the order of the expressions in the \vscm{amb}, the 
    infinite loop is immediately apparent.
\end{exe}

\begin{exe}[4.48]
    \label{4.48}
    I decided to allow an arbitrary number of adjectives in front of a noun, and 
    an adverb after a verb. This is done by running the following code in the 
    interpreter:
    \scm{ch4/4.48tex.scm}
    We can then parse sentences sentences such as “The big black cat eats fast.” 
    with as result:
    \scm{ch4/4.48s.scm}
\end{exe}

\begin{exe}[4.49]
    We make \vscm{parse-word} return a random element of the given list by 
    redefining it as:
    \scm{ch4/4.49tex.scm}
    The first sentences I get using \vscm{(parse '())} (the input is ignored) 
    are:
    \begin{itemize}
        \item The students eats.
        \item A class sleeps.
        \item A student eats.
        \item The cat studies.
        \item A class studies.
        \item A cat eats.
    \end{itemize}
    Every time, the evaluator selects the first choice in \vscm{amb} to generate 
    the sentence, so all the sentences have the same structure.

    The result is not much better if I type \vscm{(parse '())} and then type 
    \vscm{try-again} several times:
    \begin{itemize}
        \item A professor studies.
        \item A professor studies by the student.
        \item A professor studies by the student by a student.
        \item A professor studies by the student by a student by the professor.
        \item A professor studies by the student by a student by the professor 
            in the cat.
        \item A professor studies by the student by a student by the professor 
            in the cat for the professor.
    \end{itemize}
    A sentence consists of a noun phrase followed by a verb phrase, and a verb 
    phrase is a verb optionally followed by one or more prepositional phrases. 
    Each use of \vscm{try-again} causes the evaluator to go back to the choice 
    point in the \vscm{amb} in \vscm{parse-verb-phrase}, which adds a new 
    prepositional phrase at the end of the sentence.
\end{exe}

\subsection{Implementing the \vscm{Amb} Evaluator}

\begin{exe}[4.50]
    We can define \vscm{ramb} by adding the following dispatch clause to 
    \vscm{analyze}:
    \scm{ch4/4.50a.scm}
    and defining the following procedures:
    \scm{ch4/4.50b.scm}
    Alyssa can replace \vscm{amb} with \vscm{ramb} in \vscm{parse-verb-phrase} 
    and \vscm{parse-noun-phrase} so that her generator will use a random 
    sentence structure. The sentences generated by \vscm{(parse '())} exhibit 
    various structures:
    \begin{itemize}
        \item A professor with the student for the class for a student in 
            a student in a student to the student by the class to a class to the 
            cat with a class for a student with the class in a professor with 
            a student by a class to the cat by the class by a cat in a cat for 
            the class with a class by a cat for a professor by the professor for 
            a cat by the student for the professor in a student for the class 
            with a class with a professor to the student in the class by the 
            class for the professor in the cat in a professor to the cat by 
            a class with a student for a class in a professor to a student to 
            the professor for the professor for a student by a cat with the 
            student by the student in the cat by a class by the class to a cat 
            by a student for a class by a student to the professor with 
            a student with the professor with the cat to the student eats.
        \item The cat to the class lectures.
        \item The cat sleeps in a class by the cat by a student for the student 
            by a professor with a student for a class.
        \item The class to the student by the student eats.
        \item A student eats to a class in a student.
        \item A professor sleeps.
    \end{itemize}
    Some generated sentences if we also include the adjectives and adverbs added 
    in \autoref{4.48}:
    \begin{itemize}
        \item A class studies.
        \item The student for the cat to a beautiful student by the student with 
            a class for a class eats by the professor to the cat in the big 
            student in the class for the student in a professor for the class in 
            a lazy professor by the lazy student in a lazy black clever lazy 
            clever class in a lazy class by the student to the cat in a class in 
            the clever cat by the lazy cat in the lazy professor by the clever 
            professor for the big beautiful big cat to the big clever lazy big 
            cat with the student with a class by the class by the beautiful 
            beautiful beautiful class with the student with the beautiful big 
            black cat by the clever clever professor for a clever clever 
            professor in a black big clever student for the cat for the 
            professor with a big student to the student to the cat in the 
            professor with a black student to the cat for a professor.
        \item A cat lectures fast to a professor to a professor.
        \item The black professor eats well by the beautiful beautiful 
            professor.
    \end{itemize}
\end{exe}

\begin{exe}[4.51]
    The \vscm{permanent-set!} assignement can be defined similarly to 
    \vscm{set!}, except that it simply passes along the failure continuation 
    instead of intercepting it to undo the change in case of failure:
    \scm{ch4/4.51.scm}
    If we had used \vscm{set!} rather than \vscm{permanent-set!}, the displayed 
    values would have been \vscm{(a b 1)}, since the increment of \vscm{count} 
    done during the first trial would have been undone before the second trial.
\end{exe}

\begin{exe}[4.52]
    The \vscm{if-fail} construct can be defined in the following way, after 
    adding the appropriate clause to \vscm{analyze} as usual:
    \scm{ch4/4.52.scm}
\end{exe}

\begin{exe}[4.53]
    The result is \vscm{((8 35) (3 110) (3 20))}. When \vscm{(amb)} is 
    evaluated, it causes the interpreter to go back to the previous choice 
    point, in \vscm{prime-sum-pair}, and the \vscm{let} expression fails only 
    when \vscm{prime-sum-pairs} has no more alternative to explore, after the 
    three pairs whose sum is prime have been permanently added to \vscm{pairs}.
\end{exe}

\begin{exe}[4.54]
    The \vscm{analyze-require} procedure could have been defined as:
    \scm{ch4/4.54.scm}
\end{exe}

\section{Logic Programming}

\subsection{Deductive Information Retrieval}

\subsubsection{Simple queries}

\begin{exe}[4.55]
    The queries that retrieve the required information are:
    \begin{enumerate}
        \item \scm{ch4/4.55a.scm}
        \item \scm{ch4/4.55b.scm}
        \item \scm{ch4/4.55c.scm}
    \end{enumerate}
\end{exe}

\subsubsection{Compound queries}

\begin{exe}[4.56]
    The queries that retrieve the required information are:
    \begin{enumerate}
        \item \scm{ch4/4.56a.scm}
        \item \scm{ch4/4.56b.scm}
        \item \scm{ch4/4.56c.scm}
    \end{enumerate}
\end{exe}

\subsubsection{Rules}

\begin{exe}[4.57]
    The rule \vscm{can-replace} can be defined as:
    \scm{ch4/4.57tex.scm}
    \begin{enumerate}
        \item The people who can replace Cy D. Fect can be found with the query:
            \scm{ch4/4.57a.scm}
        \item The people who can replace someone who is being paid more than 
            they are can be found thanks to the query:
            \scm{ch4/4.57b.scm}
    \end{enumerate}
\end{exe}

\begin{exe}[4.58]
    The rule can be defined as:
    \scm{ch4/4.58tex.scm}
\end{exe}

\begin{exe}[4.59]
    \ \vspace{-20pt}
    \begin{enumerate}
        \item Ben should use the query:
            \scm{ch4/4.59a.scm}
        \item Alyssa’s rule can be defined as:
            \scm{ch4/4.59b.scm}
        \item Alyssa should run the query:
            \scm{ch4/4.59c.scm}
    \end{enumerate}
\end{exe}

\begin{exe}[4.60]
    Each pair appears twice because the rule’s body is symmetric in the 
    variables \vscm{?person-1} and \vscm{?person-2}, so that if none of them is 
    bound by the query, if a frame where \vscm{?person-1} is bound to person 
    A and \vscm{?person-2} is bound to person B appears in the result, the frame 
    where \vscm{?person-1} is bound to person B and \vscm{?person-2} is bound to 
    person A appears in the result too.

    The obvious idea is to define an order on the variables’ values and modify 
    the rule so that, for instance, the value of \vscm{?person-1} is smaller 
    than that of \vscm{?person-2}. The trouble is that it would not work with 
    queries where one of the variables \vscm{?person-1} or \vscm{?person-2} is 
    already bound: the expected behavior is that the two queries:
    \begin{cscm}
        (lives-near (Hacker Alyssa P) ?x)
        (lives-near ?x (Hacker Alyssa P))
    \end{cscm}
    lead to the same set of possible values for \vscm{?x}, which won’t be the 
    case if \vscm{lives-near} is not symmetric, so the idea of sorting the 
    variables’ values does not work. The solution would involve defining a rule 
    that behaves differently depending on whether one of the variables 
    \vscm{?person-1} and \vscm{?person-2} has a value imposed by the query, 
    which does not seem possible, or at least not easily.
\end{exe}

\subsubsection{Logic as programs}

\begin{exe}[4.61]
    The response to the query \vscm{(?x next-to ?y in (1 (2 3) 4))} is:
    \begin{cscm}
        ((2 3) next-to 4 in (1 (2 3) 4))
        (1 next-to (2 3) in (1 (2 3) 4))
    \end{cscm}
    The response to the query \vscm{(?x next-to 1 in (2 1 3 1)} is:
    \begin{cscm}
        (3 next-to 1 in (2 1 3 1))
        (2 next-to 1 in (2 1 3 1))
    \end{cscm}
\end{exe}

\begin{exe}[4.62]
    \label{4.62}
    The operation can be implemented with the following rules:
    \scm{ch4/4.62.scm}
    They give the expected results with queries such as
    \vscm{(last-pair (3) ?x)},\linebreak
    \vscm{(last-pair (1 2 3) ?x)} or
    \vscm{(last-pair (2 ?x) (3))}.

    With queries such as \vscm{(last-pair ?x (3))}, the behavior depends on the 
    rules’order because of the evaluator’s implementation: if they are entered 
    as written above, the rule corresponding to lists with one element is 
    checked first (since new rules are added at the beginning of the stream of 
    rules and the stream is checked sequentially), and the evaluator displays 
    the elements of an infinite stream of results with unbound variables:
    \begin{cscm}
        (last-pair (3) (3))
        (last-pair (?u-2 3) (3))
        (last-pair (?u-2 ?u-6 3) (3))
        (last-pair (?u-2 ?u-6 ?u-10 3) (3))
        (last-pair (?u-2 ?u-6 ?u-10 ?u-14 3) (3))
        (last-pair (?u-2 ?u-6 ?u-10 ?u-14 ?u-18 3) (3))
        (last-pair (?u-2 ?u-6 ?u-10 ?u-14 ?u-18 ?u-22 3) (3))
        (last-pair (?u-2 ?u-6 ?u-10 ?u-14 ?u-18 ?u-22 ?u-26 3) (3))
        (last-pair (?u-2 ?u-6 ?u-10 ?u-14 ?u-18 ?u-22 ?u-26 ?u-30 3) (3))
        (last-pair (?u-2 ?u-6 ?u-10 ?u-14 ?u-18 ?u-22 ?u-26 ?u-30 ?u-34 3) (3))
        (last-pair (?u-2 ?u-6 ?u-10 ?u-14 ?u-18 ?u-22 ?u-26 ?u-30 ?u-34 ?u-38 3) 
                (3))
        (last-pair (?u-2 ?u-6 ?u-10 ?u-14 ?u-18 ?u-22 ?u-26 ?u-30 ?u-34 ?u-38 
                ?u-42 3) (3))
        (last-pair (?u-2 ?u-6 ?u-10 ?u-14 ?u-18 ?u-22 ?u-26 ?u-30 ?u-34 ?u-38 
                ?u-42 ?u-46 3) (3))
        [...]
    \end{cscm}
    If the rules are entered in reverse order, the rule corresponding to lists 
    of several elements is checked first and the evaluator enters an infinite 
    loop as it tries to build an infinite list ending in 3, so no result is 
    displayed.
\end{exe}

\begin{exe}[4.63]
    The rules can be defined as:
    \scm{ch4/4.63.scm}
\end{exe}

\subsection{How the Query System Works}

This subsection contains no exercises.

\subsection{Is Logic Programming Mathematical Logic?}

\begin{exe}[4.64]
    \label{4.64}
    The evaluator unifies the query with the conclusion of the rule for 
    \vscm{outranked-by} by binding the variable \vscm{?staff-person} to 
    \vscm{(Bitdiddle Ben)} and \vscm{?boss} to \vscm{?who}. It then evaluates 
    the rule’s body and finds the assertion in the database corresponding to 
    Ben’s supervisor. This produces the first frame of the result stream, and an 
    answer corresponding to this frame’s binding is displayed. The interpreter 
    then processes the first part of the \vscm{and} query:
    \vscm{(outranked-by ?middle-manager ?boss)}, with both variables unbound 
    (more precisely, \vscm{?boss} is bound to an unbound variable). The 
    recursive rule evaluation leads again to a recursive evaluation of an 
    \vscm{outranked-by} rule, which leads to an infinite loop.

    With the initial version of \vscm{outranked-by}, when evaluating the 
    compound \vscm{and} query, the query
    \vscm{(supervisor ?staff-person ?boss)}, with \vscm{?staff-person} bound to 
    a constant, would have been evaluated first, and it would have produced 
    either an empty stream, which would have ended the proccessing for the given 
    frame, or a stream containing a single frame with a binding for 
    \vscm{?middle-manager}, which would have caused the processing of \linebreak
    \vscm{(outranked-by ?staff-person ?boss)} with \vscm{?staff-person} bound to 
    the name of someone higher in the hierarchy than in the previous processing 
    of the rule. Since the tower of hierarchy is not infinite, the evaluation of 
    the rule’s body terminates eventually.
\end{exe}

\begin{exe}[4.65]
    Oliver Warbucks is listed four times because the interpreter found four sets 
    of bindings for the variables appearing in the body of the rule for 
    \vscm{wheel} with \vscm{?who} bound to \vscm{(Warbucks Oliver)}. We can 
    understand the result better if we evaluate the rule’s body at the driver 
    loop:
    \begin{cscm}
        (and (supervisor (Scrooge Eben) (Warbucks Oliver))
             (supervisor (Cratchet Robert) (Scrooge Eben)))
        (and (supervisor (Hacker Alyssa P) (Bitdiddle Ben))
             (supervisor (Reasoner Louis) (Hacker Alyssa P)))
        (and (supervisor (Bitdiddle Ben) (Warbucks Oliver))
             (supervisor (Tweakit Lem E) (Bitdiddle Ben)))
        (and (supervisor (Bitdiddle Ben) (Warbucks Oliver))
             (supervisor (Fect Cy D) (Bitdiddle Ben)))
        (and (supervisor (Bitdiddle Ben) (Warbucks Oliver))
             (supervisor (Hacker Alyssa P) (Bitdiddle Ben)))
    \end{cscm}
\end{exe}

\begin{exe}[4.66]
    Ben has just realized that some values could appear multiple times in the 
    result stream. For instance, if we try to sum all the wheels’ salaries 
    using:
    \begin{cscm}
        (sum ?amount
             (and (wheel ?w)
                  (salary ?w ?amount)))
    \end{cscm}
    the result will be the sum of Ben’s salary and four times Oliver Warbucks’ 
    salary instead of being the sum of Ben’s and Oliver Warbucks’ salaries.

    Ben could filter the frames so that each possible set of values for the 
    variables appearing in the query appears only once in the filtered stream 
    before extracting the value of the designated variable. With the example 
    above, the unfiltered stream contains five frames. In one of them, \vscm{?w} 
    is bound to \vscm{(Bitdiddle Ben)} and \vscm{?amount} is bound to 
    \vscm{60000}, and in four of them \vscm{?w} is bound to
    \vscm{(Warbucks Oliver)} and \vscm{?amount} is bound to \vscm{150000}, but 
    the values of some other variables bound in these frames differ. The 
    filtered stream would contain only one frame for Ben Bitdiddle and one for 
    Oliver Warbucks.

    Keeping unique frames would not work because in the example above, the five 
    frames in the result stream are distinct if we take all the bindings they 
    define into account. Keeping unique values of the extracted variable would 
    not work either because there can be legitimate duplicates: several 
    employees can have the same salary for instance.
\end{exe}

\begin{exe}[4.67]
    A possible way to detect loops it to define a global history that is reset 
    at the beginning of \vscm{query-driver-loop}. This history contains pairs 
    with a query and a frame containing the bindings defined before the given 
    query was processed. We modify \vscm{simple-query} to check whether the 
    given query has already been processed before going forward. If a loop is 
    detected, \vscm{simple-query} returns the empty stream. Otherwise it adds an 
    entry to the history before computing the result.

    To check whether a query has already been processed, we check whether the 
    instantiation of the query in the current frame (with the numbers in unbound 
    variables removed) is equal to the instantiation of the stored query in the 
    associated stored frame (with the numbers in unbound variables removed as 
    well). If that’s the case, we check whether the stored frame is reachable 
    from the current frame: if that’s not the case, the stored history entry 
    does not belong to the current chain of deductions so we would detect a loop 
    where there is none and lose potential results.

    The problem with this implementation is that, though it does prevent 
    infinite loops, it also cuts off some computations that would have 
    terminated. For instance, with the version of \vscm{outranked-by} from 
    \autoref{4.64}, when evaluating
    \vscm{(outranked-by (Reasoner Louis) ?x)}, an answer with Alyssa P.~Hacker 
    is found from the first branch of the \vscm{or}. Then the recursive 
    evaluation of \vscm{outranked-by} (which is not eliminated because both 
    variables are unbound whereas one of them was bound in the query) allows the 
    interpreter to find that Louis is outranked by Ben Bitdiddle. But the second 
    recursion on \vscm{outranked-by} with both variables unbound is eliminated, 
    so the third answer with Oliver Warbucks is not found. The evaluation of 
    \vscm{(outranked-by ?x ?y)} is even worse since the second branch is 
    completely eliminated so we only get the supervisors. With \vscm{last-pair} 
    from \autoref{4.62}, where we got an infinite stream of results by 
    evaluating \vscm{(last-pair ?x (3))}, we only get the first two results 
    because the rest of the computation is eliminated.

    I spent some time trying to find a better solution without much success: 
    either the system cut too much or not enough. After a look at some research 
    articles on the subject, it seems that it is really difficult to find 
    a system that both eliminates all infinite loops and does not eliminate 
    valid computations. From what I understood (which is not much), it is 
    certainly not easily feasible, so I decided to stick with this version.

    The modified implementation of \vscm{simple-query} and the other procedures 
    needed can be defined as:
    \scm{ch4/4.67.scm}

    It’s also necessary to add \vscm{(reset-history!)} at the beginning of 
    \vscm{query-driver-loop}.
\end{exe}

\begin{exe}[4.68]
    My initial rules were:
    \scm{ch4/4.68atex.scm}
    These rules can answer \vscm{(reverse (1 2 3) ?x)} but not
    \vscm{(reverse ?x (1 2 3))} because in this case
    \vscm{(reverse ?rest ?reverse-rest)} is evaluated with both variables 
    unbound and it leads to an infinite loop.

    The second query can be solved by the rule:
    \scm{ch4/4.68btex.scm}
    but then it’s the first one that leads to an infinite loop.

    If we add the infinite loop detector from the previous exercise and use all 
    three rules above, both queries are solved, and also queries like
    \vscm{(reverse (1 2 ?x) (3 . ?y))} and
    \vscm{(reverse (1 2  . ?x) (3 . ?y))}. However,
    \vscm{(reverse (1 2 . ?x) (4 3 . ?y))} returns no answer because the 
    computation is interrupted by the loop detector.
\end{exe}

\begin{exe}[4.69]
    The rules can be defined in the following way:
    \scm{ch4/4.69.scm}
    Without the loop detector, queries such as \vscm{(?rel Adam Irad)} cause an 
    infinite loop. With the loop detector, there are no infinite loops but 
    queries such as \vscm{((great great grandson) ?x ?y)} return no result 
    (though \vscm{((great grandson) ?x ?y)} works).
\end{exe}

\subsection{Implementing the Query System}

\begin{exe}[4.70]
    It’s necessary to use \vscm{let} because the second argument of 
    \vscm{cons-stream} is evaluated lazily, which implies that after evaluating
    \vscm{(set! THE-ASSERTIONS (cons-stream assertion THE-ASSERTIONS))}, 
    \vscm{THE-ASSERTIONS} is an infinite stream and all its elements are 
    \vscm{assertion}.
\end{exe}

\begin{exe}[4.71]
    The use of explicit delays postpones the apparition of some infinite loops 
    caused by the rules’ evaluation and allows the interpreter to display some 
    answers. For instance, with explicit delays, the query
    \vscm{(married Minnie ?who)} displays an infinite stream of answers, but 
    with the simpler version of \vscm{simple-query} no answer is displayed 
    because the infinite loop appears during the evaluation of the second 
    argument of \vscm{stream-append}. In the same way, with Louis’ version of 
    \vscm{outranked-by} from \autoref{4.64}, with explicit delays the query
    \vscm{(outranked-by (Bitdiddle Ben) ?x)} displays an answer before going 
    into a loop. With the simple version of \vscm{disjoin} no answer is 
    displayed because the loop happens during the evaluation of the second 
    argument of \vscm{interleave}.
\end{exe}

\begin{exe}[4.72]
    If one of the streams resulting from the evaluation of a disjunct or from 
    the application of the mapped function to the stream of frames is infinite, 
    with append no element of any ulterior stream would appear in the result. 
    With \vscm{interleave} we are guaranteed that any element from a partial 
    result stream will appear in the global merged stream eventually.
\end{exe}

\begin{exe}[4.73]
    Without \vscm{delay}, \vscm{flatten-stream} is called on the input stream’s 
    \vscm{cdr} before any element of the flattened stream can be displayed, so 
    if the value of \vscm{(flatten-stream (stream-cdr stream))} is infinite 
    (either because \vscm{stream} is infinite or because one of its elements is 
    an infinite stream), \vscm{flatten-stream} will never return.
\end{exe}

\begin{exe}[4.74]
    \ \vspace{-20pt}
    \begin{enumerate}
        \item The program can be completed simply by filtering out the empty 
            streams and taking the first and only element of non-empty streams:
            \scm{ch4/4.74a.scm}
        \item The query system’s behavior does not change.
    \end{enumerate}
\end{exe}

\begin{exe}[4.75]
    The \vscm{uniquely-asserted} procedure can be defined as:
    \scm{ch4/4.75.scm}
    The query that lists all people who supervise precisely one person is 
    similar to the query that lists all jobs that are filled by only one person:
    \scm{ch4/4.75b.scm}
\end{exe}

\begin{exe}[4.76]
    We can define a \vscm{merge-frames} procedure that merges two frames as 
    indicated in the text, a \vscm{merge-frame-streams} procedure that applies 
    \vscm{merge-frames} to each possible pair of frames from two input streams, 
    and rewrite \vscm{conjoin} using these two procedures.
    \scm{ch4/4.76.scm}
    There are problems caused by the separate evaluation of the clauses of the 
    \vscm{and} however: we have seen previously that in some cases, the 
    evaluation of the second clause works correctly only because some bindings 
    have been provided by the evaluation of the previous clause, such as in the 
    \vscm{outranked-by} rule, or when using \vscm{not} or \vscm{lisp-value}. 
    This new implementation won’t give the expected results in such cases, it 
    works only when the clauses can be evaluated in any order.
\end{exe}

\begin{exe}[4.77]
    First, let’s define a procedure to check whether a query contains an unbound 
    variable in a given frame:
    \scm{ch4/4.77a.scm}
    Then I modified the procedures \vscm{negate} and \vscm{lisp-value} so that 
    they check if the query contains unbound variables. If so, they add 
    a promise to filter to the frame. If not, they do the filtering directly. 
    A promise is a pair consisting of a query and a predicate applying to 
    a frame that returns true if the frame must be kept and false if it must be 
    filtered out. It is added to the frame as a special binding. Since 
    \vscm{not} and \vscm{lisp-value} queries are necessarily part of an 
    \vscm{and} expression, I then modified \vscm{conjoin} so that it filters out 
    the stream of frames produced by the evaluation of the first subquery if any 
    promises are found. The disadvantage of this method is that if the frame is 
    kept, the same promise will be checked multiple times.
    \scm{ch4/4.77b.scm}
\end{exe}

\begin{exe}[4.78]
    To implement the query language as a nondeterministic program, we first 
    replace the driver loop with two procedures: \vscm{assert!} to add 
    assertions and rules to the database and \vscm{request} to run queries.
    \scm{ch4/4.78b.scm}
    All the procedures on frame streams now operate on a single frame. 
    \vscm{Qeval} is unchanged except that the \vscm{frame-stream} argument will 
    now be a single frame, but \vscm{simple-query}, \vscm{conjoin}, 
    \vscm{disjoin}, \vscm{negate} and \vscm{lisp-value} have to be modified:
    \scm{ch4/4.78c.scm}
    For \vscm{negate}, we need to succeed if the evaluation of the negated query 
    fails without producing any result, and I found no other way to do that than 
    to define a new special form \vscm{require-fail} that succeeds (with the 
    value \vscm{true}) if its argument fails:
    \scm{ch4/4.78a.scm}
    The procedures used for pattern matching and unification must be adapted as 
    well. By using \vscm{amb} instead of returning the \vscm{failed} symbol in 
    \vscm{pattern-match} and \vscm{unify-match}, we can simplify the procedures 
    a little since it’s not necessary to check for the \vscm{failed} symbol 
    anymore.
    \scm{ch4/4.78d.scm}
    I also rewrote the code for maintaining the data base so that it uses lists 
    instead of streams (not included here).

    \medskip

    There are differences in the answers’ order due to my use of \vscm{ramb} in 
    \vscm{disjoin} where the stream-based version used 
    \vscm{interleave-delayed}.

    The main differences regard infinite loops. Because I used \vscm{ramb} in 
    \vscm{disjoin}, elements from all the disjuncts will appear eventually but 
    it’s impossible to predict when. If the computation of one element causes 
    an infinite loop, it may appear at the start or after some answers have 
    been displayed. For instance, with Louis’ version of \vscm{outranked-by} 
    from \autoref{4.64}, sometimes the query
    \vscm{(outranked-by (Bitdiddle Ben) ?x)} loops without displaying anything, 
    sometimes it answers first. But most of the time
    \vscm{(outranked-by ?x ?y)} displays several answers before going into 
    a loop, whereas the stream-based version always displayed only the first 
    answer.

    With the query \vscm{(last-pair ?x (3))} from \autoref{4.62}, the successive 
    results displayed show an increment of one only in the ids of the unbound 
    variables, where the increment was of 4 in the stream version. The first 
    results are:
    \begin{cscm}
	(last-pair (3) (3))
	(last-pair (?u-1 3) (3))
	(last-pair (?u-1 ?u-2 3) (3))
	(last-pair (?u-1 ?u-2 ?u-3 3) (3))
	(last-pair (?u-1 ?u-2 ?u-3 ?u-4 3) (3))
    \end{cscm}
    The reason is that the rule-counter is decreased when the evaluator 
    backtracks after a rule application fails (there are 4 rules in the test 
    database).
\end{exe}