ch3.tex

\chapter{Modularity, Objects, and State}

\section{Assignment and Local State}

\subsection{Local State Variables}

\begin{exe}[3.1]
    The procedure \vscm{make-accumulator} can be written:
    \scm{ch3/3.01.scm}
\end{exe}

\begin{exe}[3.2]
    The \vscm{make-monitored} procedure can be written:
    \scm{ch3/3.02.scm}
\end{exe}

\begin{exe}[3.3]
    The \vscm{make-account} procedure can be modified in the following way:
    \scm{ch3/3.03.scm}
\end{exe}

\begin{exe}[3.4]
    The procedure can be rewritten as:
    \scm{ch3/3.04.scm}
\end{exe}

\subsection{The Benefits of Introducing Assignment}

\begin{exe}[3.5]
    Using Gambit Scheme’s \vscm{random-real} procedure, that generates a random 
    real number between 0 and 1, \vscm{random-in-range} and the other procedures 
    can be written:
    \scm{ch3/3.05.scm}
\end{exe}

\begin{exe}[3.6]
    The \vscm{rand} procedure can be rewritten as:
    \scm{ch3/3.06.scm}
\end{exe}

\subsection{The Costs of Introducing Assignment}

\begin{exe}[3.7]
    I simply added a \vscm{join} action to the account returned by 
    \vscm{make-account} that creates an access with another password. I also 
    make \vscm{incorrect-password} throw an error instead of simply returning 
    a string, otherwise a call such as
    \vscm{(define new-acc (make-join account curr-pass new-pass))} with an 
    incorrect current password will affect a string value to \vscm{new-acc} 
    without reporting an error, and subsequent uses of the account will throw 
    errors because \vscm{"Incorrect password"} is not a procedure.
    \scm{ch3/3.07.scm}
\end{exe}

\begin{exe}[3.8]
    The procedure \vscm{f} returns:
    \begin{itemize}
        \item 0 if it is the first time it is called;
        \item the previous argument it was called with otherwise.
    \end{itemize}
    Thus, if we evaluate \vscm{(f 0)}, then \vscm{(f 1)}, we get 0 both times, 
    but if we evaluate \vscm{(f 1)}, then \vscm{(f 0)}, we get 0 the first 
    time and 1 the second.
    \scm{ch3/3.08.scm}
\end{exe}

\section{The Environment Model of Evaluation}

\subsection{The Rules for Evaluation}

This subsection contains no exercises.

\subsection{Applying Simple Procedures}

\var{\envtonext}{3mm}
\begin{exe}[3.9]
    \begin{figure}
        \begin{tikzpicture}[>=Stealth, thick]
            \node[text width=1cm, align=right] (ge) {global\\ env};
            \node[global env, right=\nametoenv of ge] (g) {factorial};
            \node[text width=1cm, align=right, below=of ge] (e1) {E1};
            \node[env, right=\nametoenv of e1] (n1) {n:\,6};
            \node[right=\envtonext of n1] (e2) {E2};
            \node[env, right=\nametoenv of e2] (n2) {n:\,5};
            \node[right=\envtonext of n2] (e3) {E3};
            \node[env, right=\nametoenv of e3] (n3) {n:\,4};
            \node[right=\envtonext of n3] (e4) {E4};
            \node[env, right=\nametoenv of e4] (n4) {n:\,3};
            \node[right=\envtonext of n4] (e5) {E5};
            \node[env, right=\nametoenv of e5] (n5) {n:\,2};
            \node[right=\envtonext of n5] (e6) {E6};
            \node[env, right=\nametoenv of e6] (n6) {n:\,1};

            \draw[->] (ge) -- (ge.west -| g.west);
            \foreach \i in {1, ..., 6} {
                \draw[->] (e\i) -- (n\i);
                \draw[->] (n\i.north) -- (n\i.north|-g.south);
                \node[code,below=2mm of n\i] { \vscm{(if ...)} };
            }
        \end{tikzpicture}
        \caption{Environments created by evaluating \vscm{(factorial 6)} with 
        the recursive procedure. In all the environments created, the code to 
        evaluate corresponds to the body of the \vscm{factorial} procedure.}
        \label{fact_rec}
    \end{figure}

    \begin{figure}
        \begin{tikzpicture}[>=Stealth, thick]
            \node[text width=1cm, align=right] (ge) {global\\ env};
            \node[global env, right=\nametoenv of ge] (g)
            {factorial\\ fact-iter};
            \node[text width=1cm, align=right, below=of ge] (e1) {E1};
            \node[env, right=\nametoenv of e1] (n1) {n:\,6};
            \node[right=\envtonext of n1] (e2) {E2};
            \node[env, right=\nametoenv of e2] (n2) {p:\,1\\ c:\,1\\ m:\,6};
            \node[right=\envtonext of n2] (e3) {E3};
            \node[env, right=\nametoenv of e3] (n3) {p:\,2\\ c:\,2\\ m:\,6};
            \node[right=(\envtonext+.6cm) of n3] (e4) {E4};
            \node[env, right=\nametoenv of e4] (n4) {p:\,6\\ c:\,3\\ m:\,6};
            \node[right=(\envtonext+.3cm) of n4] (e5) {E5};
            \node[env, right=\nametoenv of e5] (n5) {p:\,24\\ c:\,4\\ m:\,6};
            \node[below=1.9cm of n3] (e6) {E6};
            \node[env, right=\nametoenv of e6] (n6) {p:\,24\\ c:\,5\\ m:\,6};
            \node[right=\envtonext of n6] (e7) {E7};
            \node[env, right=\nametoenv of e7] (n7) {p:\,120\\ c:\,6\\ m:\,6};
            \node[right=\envtonext of n7] (e8) {E8};
            \node[env, right=\nametoenv of e8] (n8) {p:\,720\\ c:\,7\\ m:\,6};

            \draw[->] (ge) -- (ge.west -| g.west);
            \foreach \i in {1, ..., 8} {
                \draw[->] (e\i) -- (n\i);
                \draw[->] (n\i.north) -- (n\i.north|-g.south);
            }

            \node[code, below = 2mm of n1] { \vscm{(fact-iter 1 1 n)} };
            \foreach \i in {2, ..., 8} {
                \node[code, below = 2mm of n\i] { \vscm{(if ...)} };
            }
        \end{tikzpicture}
        \caption{Environments created by evaluating \vscm{(factorial 6)} with 
        the iterative procedure. In environments E2 to E8, the code to evaluate 
        corresponds to the body of the \vscm{fact-iter} procedure.}
        \label{fact_iter}
    \end{figure}

    The environment structure created by evaluating \vscm{(factorial 6)} with 
    both versions of the procedure are shown in figures~\ref{fact_rec} 
    and~\ref{fact_iter}.
\end{exe}

\subsection{Frames as the Repository of Local State}

\begin{exe}[3.10]
    \label{3.10}
    \begin{figure}
        \begin{tikzpicture}[>=Stealth, thick]
            \matrix[matrix anchor=north west, column sep=2\nametoenv, column 
            2/.style={anchor=base west}] at (0,0) {
            \node[text width=1cm, align=right] (ge) {global\\ env}; &
            \node[code] (mkw) {make-withdraw: ...}; \\[-8pt]
            & \node[code] (w1) {W1: }; \\
            };
            \begin{scope}[on background layer]
                \coordinate (w1b) at ($ (w1.south) - (0, 10pt) $);
                \node[global env, fit=(mkw) (w1b), right=\nametoenv of ge] (g) 
                {};
            \end{scope}
            \node[text width=1cm, align=right, below=of g] (e1) {E1};
            \node[env, right=\nametoenv of e1] (n1) {initial-amount:\,100};
            \node[env, below=of n1] (n2) {balance:\,100};
            \node[left=\nametoenv of n2] (e2) {E2};
            \node[env, below=of n2] (n3) {amount:\,50};

            \coordinate[left=3cm of e1] (p1);
            \procedure{p1}{c1}{c2}
            \node[code, below=of p1] (code) {
            parameters: amount\\
            body: (if ...)
            };
            \node[code, below=1ex of n3] { (if ...) };

            \draw[->] (c1) -- (c1 |- code.north);
            \draw[->] (c2) -- ++(0, -8mm) -| ($ (n2.north) - (.5cm, 0) $);

            \draw[->] (ge) -- (ge.west -| g.west);
            \foreach \i in {1, 2}
                \draw[->] (e\i) -- (n\i);
            \draw[->] (n1.north) -- (n1.north |- g.south);
            \draw[->] (n2) -- (n1);
            \draw[->] (n3) -- (n2);
            \draw[->] (w1) -| ($ (p1) + (0, \circleradius) $);
        \end{tikzpicture}
        \caption{Environments created when executing
        \vscm{(W1 50)} after executing
        \vscm{(define (W1 (make-withdraw 100))}. The environment E1 is created 
        by the call to \vscm{make-withdraw}, E2 is created when the lambda 
        procedure created by the \vscm{let} is executed. E2 is referenced by the 
        procedure returned by \vscm{make-withdraw}. When \vscm{(W1 50)} is 
        called, a new environment pointing to E2 is created, in which the body 
        of \vscm{W1} is evaluated.}
        \label{3.10figa}
    \end{figure}

    \begin{figure}
        \begin{tikzpicture}[>=Stealth, thick]
            \matrix[matrix anchor=north west, column sep=2\nametoenv, column 
            2/.style={anchor=base west}] at (0,0) {
            & \node[code] (mkw) {make-withdraw: ...}; \\
            \node[text width=1cm, align=right] (ge) {global\\ env};& \node[code] 
            (w1) {W1: }; \\[-8pt]
            & \node[code] (w2) {W2: }; \\
            };
            \begin{scope}[on background layer]
                \coordinate (mkwb) at ($ (mkw.north) + (0, 20pt) $);
                \node[global env, fit=(mkwb) (w1), right=\nametoenv of ge] (g) 
            {};
            \end{scope}
            \coordinate (e1pos) at ($ (g.south west)!.65!(g.south east) $);
            \node[text width=1cm, align=right, below=of e1pos] (e1) {E1};
            \node[env, right=\nametoenv of e1] (n1) {initial-amount:\,100};
            \node[env, below=of n1] (n2) {balance:\,50};
            \node[left=\nametoenv of n2] (e2) {E2};

            \coordinate[left=.8cm of e1] (p1);
            \procedure{p1}{c1}{c2}
            \node[code, below=of p1] (code) {
            parameters: amount\\
            body: (if ...)
            };

            \coordinate (e3pos) at (ge |- g.south east);
            \node[text width=1cm, align=right, below=of e3pos] (e3) {E3};
            \node[env, right=\nametoenv of e3] (n3) {initial-amount:\,100};
            \node[env, below=of n3] (n4) {balance:\,100};
            \node[left=\nametoenv of n4] (e4) {E4};

            \draw[->] (c1) -- (c1 |- code.north);
            \draw[->] (c2) -- ++(0, -8mm) -| ($ (n2.north) - (.5cm, 0) $);
            \draw[->] (w1) -| ($ (p1) + (0, \circleradius) $);

            \coordinate[left=2cm of p1] (p2);
            \procedure{p2}{c3}{c4}
            \draw[->] (c3) |- (code.west);
            \draw[->] (c4) -- ++(0, -8mm) -| ($ (n4.north) + (.5cm, 0) $);
            \draw[->] (w2) -| ($ (p2) + (0, \circleradius) $);

            \draw[->] (ge) -- (ge.west -| g.west);
            \foreach \i in {1, ..., 4}
                \draw[->] (e\i) -- (n\i);
            \draw[->] (n1.north) -- (n1.north |- g.south);
            \draw[->] (n3.north) -- (n3.north |- g.south);
            \draw[->] (n2) -- (n1);
            \draw[->] (n4) -- (n3);
        \end{tikzpicture}
        \caption{Environments created after the execution of
        \vscm{(define W1 (make-withdraw 100))}, followed by \vscm{(W1 50)}, then 
        \vscm{(define W2 (make-withdraw 100))}. The call to \vscm{W1} modified 
        the value of \vscm{balance} in E2, but \vscm{W2} uses the \vscm{balance} 
        variable of environment E4.}
        \label{3.10figb}
    \end{figure}

    The environments created after the execution of the three commands are shown 
    in figures~\ref{3.10figa} and~\ref{3.10figb}, see the captions for some 
    details. As with the first version of \vscm{make-version}, each object 
    created with a call to \vscm{make-version} uses a \vscm{balance} binding 
    situated in an environment specific to the object.

    In the second version, two environments are created instead of one, and the 
    value of \vscm{initial-value} is unchanged.
\end{exe}

\subsection{Internal Definitions}

\begin{exe}[3.11]
    \begin{figure}
        \begin{tikzpicture}[>=Stealth, thick]
            \matrix[matrix anchor=base west, column sep=2\nametoenv, column 
            2/.style={anchor=base west}] at (0,0) {
            \node[text width=1cm, align=right] (ge) {global\\ env};
            & \node[code] (mkw) {make-account: ...}; \\[-8pt]
            & \node[code] (acc) {acc: }; \\
            };
            \coordinate (e1pos) at ($ (g.south west)!.15!(g.south east) $);
            \matrix[matrix anchor=north west, column sep=2\nametoenv,
            below=1mm of e1pos, column 2/.style={anchor=base west}] {
            \node[text width=1cm, align=right] (e1) {E1};
            & \node[code] (balance) { balance: 50}; \\[-11pt]
            & \node[code] { withdraw: ... }; \\
            & \node[code] { deposit: ... }; \\
            & \node[code] (dispatch) { dispatch: }; \\
            };
            \begin{scope}[on background layer]
                \coordinate (accb) at ($ (acc.south) - (0, 20pt) $);
                \node[global env, fit=(mkw) (accb), right=\nametoenv of ge] (g) 
                    {};
                \node[env, minimum width=4cm, fit=(balance) (dispatch), 
                right=\nametoenv of e1, yshift=-3mm] (n1) {};
            \end{scope}

            \coordinate (xp1) at ($ (n1.south)!.50!(n1.south east) $);
            \coordinate[below=of xp1] (p1);
            \procedure{p1}{c1}{c2}
            \node[code, below=of p1] (code) {
            parameters: m\\
            body: (cond ...)
            };

            \draw[->] (c1) -- (c1 |- code.north);
            \draw[->] (c2) -| ($ (n1.south east) - (3mm, 0) $);

            \draw[->] (ge) -- (ge.west -| g.west);
            \draw[->] (e1) -- (e1.east -| n1.west);
            \draw[->] (n1.north) -- (n1.north |- g.south);
            \draw[->] (dispatch) -| ($ (p1) + (0, \circleradius) $);

            \draw[->] (acc) -- ($ (acc) + (1cm, 0) $)
                |- ($ (p1) + (-2\circleradius, 0) $);

            % Evaluation of ((acc 'deposit) 40)
            \coordinate[right=2cm of n1.east] (middle);
            \node[env, above=1em of middle] (m)
            {m: 'deposit};
            \node[env, below=1em of middle] (amount) {amount: 40};
            \node[right=of m] (e2) {E2};
            \node[right=of amount] (e3) {E3};
            \draw[->] (e2) -- (m);
            \draw[->] (e3) -- (amount);
            \draw[->] (m) -- (m -| n1.east);
            \draw[->] (amount) -- (amount -| n1.east);
        \end{tikzpicture}

        \caption{Environments when evaluating \vscm{((acc 'deposit) 40)}
        after evaluating \vscm{(define acc (make-account 50))}. E1 is created 
        when defining \vscm{acc}, then the evaluation of \vscm{(acc 'deposit)}
        causes the creation of an environment referencing E1, and since the 
        result of the evaluation is the procedure \vscm{deposit}, \vscm{(deposit 
        40)} is then evaluated in a new environment.}
        \label{3.11figa}
    \end{figure}

    \begin{figure}
        \begin{tikzpicture}[>=Stealth, thick]
            \matrix[matrix anchor=base west, column sep=2\nametoenv, column 
            2/.style={anchor=base west}] at (0,0) {
            \node[text width=1cm, align=right] (ge) {global\\ env};
            & \node[code] (mkw) {make-account: ...}; \\[-8pt]
            & \node[code] (acc) {acc: }; \\
            };
            \coordinate (e1pos) at ($ (g.south west)!.15!(g.south east) $);
            \matrix[matrix anchor=north west, column sep=2\nametoenv,
            below=1cm of e1pos, column 2/.style={anchor=base west}] {
            \node[text width=1cm, align=right] (e1) {E1};
            & \node[code] (balance) { balance: 90}; \\[-11pt]
            & \node[code] { withdraw: ... }; \\
            & \node[code] { deposit: ... }; \\
            & \node[code] (dispatch) { dispatch: }; \\
            };
            \begin{scope}[on background layer]
                \coordinate (accb) at ($ (acc.south) - (0, 20pt) $);
                \node[global env, fit=(mkw) (accb), right=\nametoenv of ge] (g) 
                    {};
                \node[env, minimum width=4cm, fit=(balance) (dispatch), 
                right=\nametoenv of e1, yshift=-3mm] (n1) {};
            \end{scope}

            \coordinate (xp1) at ($ (n1.south)!.50!(n1.south east) $);
            \coordinate[below=of xp1] (p1);
            \procedure{p1}{c1}{c2}
            \node[code, below=of p1] (code) {
            parameters: m\\
            body: (cond ...)
            };

            \draw[->] (c1) -- (c1 |- code.north);
            \draw[->] (c2) -| ($ (n1.south east) - (3mm, 0) $);

            \draw[->] (ge) -- (ge.west -| g.west);
            \draw[->] (e1) -- (e1.east -| n1.west);
            \draw[->] (n1.north) -- (n1.north |- g.south);
            \draw[->] (dispatch) -| ($ (p1) + (0, \circleradius) $);

            \draw[->] (acc) -- ($ (acc) + (1cm, 0) $)
                |- ($ (p1) + (-2\circleradius, 0) $);

            % Evaluation of ((acc 'withdraw) 60)
            \coordinate[right=2cm of n1.east] (middle);
            \node[env, above=1em of middle] (m)
            {m: 'withdraw};
            \node[env, below=1em of middle] (amount) {amount: 60};
            \node[right=of m] (e4) {E4};
            \node[right=of amount] (e5) {E5};
            \draw[->] (e4) -- (m);
            \draw[->] (e5) -- (amount);
            \draw[->] (m) -- (m -| n1.east);
            \draw[->] (amount) -- (amount -| n1.east);
        \end{tikzpicture}

        \caption{Environments during the evaluation of
        \vscm{((acc 'withdraw) 60)}.}
        \label{3.11figb}
    \end{figure}

    The environments generated by the evaluation of
    \vscm{(define acc (make-account 50))},\linebreak
    \vscm{((acc 'deposit) 40)} and \vscm{((acc 'withdraw) 60)} are shown in 
    figures~\ref{3.11figa} and~\ref{3.11figb}. The local state for \vscm{acc} is 
    kept in the local environment referenced by the procedure object referenced 
    by \vscm{acc}.

    If a second environment is created, its local state is kept in a new 
    environment created when evaluating the \vscm{make-account} procedure, so it 
    does not interfere with \vscm{acc}’s local environment.

    The environment structures of \vscm{acc} and \vscm{acc2} share the global 
    environment.
\end{exe}

\section{Modeling with Mutable Data}

\subsection{Mutable List Structure}

\begin{exe}[3.12]
    \begin{figure}
        \centering
        \begin{tikzpicture}[box and pointer]
            \matrix[cell matrix] {
            % x
            \node[struct name] (x) {x}; &[+2\boxsize]
            \node[car] (carx) {}; & \node[cdr] (cdrx) {}; &[+\boxsize]
            \node[car] (cadrx) {}; & \node[cdr] (cddrx) {}; \\

            % Values
            & \node[box] (a) {a}; &&
            \node[box] (b) {b}; &&[+2\boxsize]
            \node[box] (c) {c}; &&[+\boxsize]
            \node[box] (d) {d}; & \\

            % z and y
            \node[struct name] (z) {z}; &[+2\boxsize]
            \node[car] (carz) {}; & \node[cdr] (cdrz) {}; &
            \node[car] (cadrz) {}; & \node[cdr] (cddrz) {}; &
            \node[car] (cary) {}; & \node[cdr] (cdry) {}; &
            \node[car] (cadry) {}; & \node[cdr] (cddry) {}; &
            \\
            };

            \draw[pointer] (x) -- (carx);
            \link{carx}{a}
            \link{cdrx}{cadrx}
            \link{cadrx}{b}
            \nil{cddrx}

            \draw[pointer] (z) -- (carz);
            \link{carz}{a}
            \link{cdrz}{cadrz}
            \link{cadrz}{b}
            \link{cddrz}{cary}
            \link{cary}{c}
            \link{cdry}{cadry}
            \link{cadry}{d}
            \nil{cddry}

            \coordinate(ypos) at ($ (cary.north west)!.4!(cary.west) $);
            \node[struct name, left=1.5\boxsize of ypos] (y) {y};
            \draw[pointer] (y) -- (ypos);
        \end{tikzpicture}
        \caption{The lists \vscm{x}, \vscm{y} and \vscm{z} right after the 
        definition of \vscm{z}.}
        \label{3.12z}
    \end{figure}

    \begin{figure}
        \centering
        \begin{tikzpicture}[box and pointer]
            \matrix[cell matrix] {
            % z and y
            \node[struct name] (x) {x}; &[+2\boxsize]
            \node[car] (carx) {}; & \node[cdr] (cdrx) {}; &[+\boxsize]
            \node[car] (cadrx) {}; & \node[cdr] (cddrx) {}; &[+3\boxsize]
            \node[car] (cary) {}; & \node[cdr] (cdry) {}; &[+\boxsize]
            \node[car] (cadry) {}; & \node[cdr] (cddry) {}; & \\

            % Values
            & \node[box] (a) {a}; &&
            \node[box] (b) {b}; &&[+2\boxsize]
            \node[box] (c) {c}; &&[+\boxsize]
            \node[box] (d) {d}; & \\
            };

            \draw[pointer] (x) -- (carx);
            \link{carx}{a}
            \link{cdrx}{cadrx}
            \link{cadrx}{b}
            \link{cddrx}{cary}

            \link{cary}{c}
            \link{cdry}{cadry}
            \link{cadry}{d}
            \nil{cddry}

            \coordinate(wpos) at ($ (carx.north west)!.4!(carx.west) $);
            \node[struct name, left=3\boxsize of wpos] (w) {w};
            \draw[pointer] (w) -- (wpos);

            \coordinate(ypos) at ($ (cary.north west)!.4!(cary.west) $);
            \node[struct name, left=1.5\boxsize of ypos] (y) {y};
            \draw[pointer] (y) -- (ypos);
        \end{tikzpicture}
        \caption{The lists \vscm{x}, \vscm{y} and \vscm{w} right after the 
        definition of \vscm{w}.}
        \label{3.12w}
    \end{figure}
    The first response is \vscm{(b)}, the second response is \vscm{(b c d)}. 
    \autoref{3.12z} shows the lists \vscm{x}, \vscm{y} and \vscm{z} right after 
    the definition of \vscm{z}. \autoref{3.12w} shows the lists \vscm{x}, 
    \vscm{y} and \vscm{w} after the definition of \vscm{w}.
\end{exe}

\begin{exe}[3.13]
    \label{3.13}
    \begin{figure}
        \centering
        \begin{tikzpicture}[box and pointer]
            \matrix[cell matrix] {
            \node[car] (carz) {}; & \node[cdr] (cdrz) {}; &[+\boxsize]
            \node[car] (cadrz) {}; & \node[cdr] (cddrz) {}; &[+\boxsize]
            \node[car] (caddrz) {}; & \node[cdr] (cdddrz) {}; \\

            % Values
            \node[box] (a) {a}; &&
            \node[box] (b) {b}; &&[+\boxsize]
            \node[box] (c) {c}; \\
            };

            \link{carz}{a}
            \link{cdrz}{cadrz}
            \link{cadrz}{b}
            \link{cddrz}{caddrz}
            \link{caddrz}{c}

            \coordinate(zpos) at ($ (carz.north west)!.6!(carz.west) $);
            \node[struct name, left=2\boxsize of zpos] (z) {z};
            \draw[pointer] (z) -- (zpos);

            \coordinate(in) at ($ (carz.south west)!.6!(carz.west) $);
            \draw[box pointer] (cdddrz.base) -- ++(0, -3.5\boxsize) -|
                ($ (in) - (\boxsize, 0) $) -- (in);
        \end{tikzpicture}
        \caption{The structure created by
        \vscm{(define z (make-cycle (list 'a 'b 'c))}.}
        \label{3.13fig}
    \end{figure}
    The structure \vscm{z} is shown in \autoref{3.13fig}.

    If we try to compute \vscm{(last-pair z)}, we get an infinite loop since 
    \vscm{z} has a cycle.
\end{exe}

\begin{exe}[3.14]
    \begin{figure}
        \centering
        \begin{tikzpicture}[box and pointer]
            \matrix[cell matrix] {
            \node[struct name] (v) {v}; &[+2\boxsize]
            \node[car] (c11) {}; & \node[cdr] (c12) {}; &[+\boxsize]
            \node[car] (c21) {}; & \node[cdr] (c22) {}; &[+\boxsize]
            \node[car] (c31) {}; & \node[cdr] (c32) {}; &[+\boxsize]
            \node[car] (c41) {}; & \node[cdr] (c42) {}; & \\

            % Values
            & \node[box] (a) {a}; &&
            \node[box] (b) {b}; &&[+\boxsize]
            \node[box] (c) {c}; &&[+\boxsize]
            \node[box] (d) {d}; & \\
            };

            \draw[pointer] (v) -- (c11);
            \link{c11}{a}
            \link{c12}{c21}
            \link{c21}{b}
            \link{c22}{c31}
            \link{c31}{c}
            \link{c32}{c41}
            \link{c41}{d}
            \nil{c42}
        \end{tikzpicture}
        \caption{The list to which \vscm{v} is bound initially.}
        \label{3.14v}
    \end{figure}

    \begin{figure}
        \centering
        \begin{tikzpicture}[box and pointer]
            \matrix[cell matrix] {
            \node[struct name] (w) {w}; &[+2\boxsize]
            \node[car] (c11) {}; & \node[cdr] (c12) {}; &[+\boxsize]
            \node[car] (c21) {}; & \node[cdr] (c22) {}; &[+\boxsize]
            \node[car] (c31) {}; & \node[cdr] (c32) {}; &[+3\boxsize]
            \node[car] (c41) {}; & \node[cdr] (c42) {}; & \\

            % Values
            & \node[box] (d) {d}; &&
            \node[box] (c) {c}; &&[+\boxsize]
            \node[box] (b) {b}; &&[+3\boxsize]
            \node[box] (a) {a}; & \\
            };

            \draw[pointer] (w) -- (c11);
            \link{c11}{d}
            \link{c12}{c21}
            \link{c21}{c}
            \link{c22}{c31}
            \link{c31}{b}
            \link{c32}{c41}
            \link{c41}{a}
            \nil{c42}

            \coordinate(vpos) at ($ (c41.north west)!.6!(c41.west) $);
            \node[struct name, left=2\boxsize of vpos] (v) {v};
            \draw[pointer] (v) -- (vpos);
        \end{tikzpicture}
        \caption{The lists \vscm{v} and \vscm{w} after calling \vscm{mystery}.}
        \label{3.14w}
    \end{figure}
    The \vscm{mystery} procedure reverses the elements of the list. 
    \autoref{3.14v} shows the list \vscm{v} as it is initially, and 
    \autoref{3.14w} shows the lists \vscm{v} and \vscm{w} after evaluating 
    \vscm{(define w (mystery v))}. The values of \vscm{v} and \vscm{w} would be 
    \vscm{(a)} and \vscm{(d c b a)}.
\end{exe}

\subsubsection{Sharing and identity}

\begin{exe}[3.15]
    \begin{figure}
        \centering
        \begin{tikzpicture}[box and pointer]
            \matrix[cell matrix] {
            \node[struct name] (z1) {z1}; &[+2\boxsize]
            \node[car] (c11) {}; & \node[cdr] (c12) {}; \\

            &
            \node[car] (c21) {}; & \node[cdr] (c22) {}; &[+\boxsize]
            \node[car] (c23) {}; & \node[cdr] (c24) {}; \\

            &
            \node[box] (wow) {wow}; &&
            \node[box] (b) {b}; \\
            };

            \draw[pointer] (z1) -- (c11);
            \link{c11}{c21}
            \link{c12}{c22}
            \link{c21}{wow}
            \link{c22}{c23}
            \link{c23}{b}
            \nil{c24}
        \end{tikzpicture}
        \caption{The list \vscm{z1} after applying \vscm{set-to-wow!} to it.}
        \label{3.15z1}
    \end{figure}

    \begin{figure}
        \centering
        \begin{tikzpicture}[box and pointer]
            \matrix[cell matrix] {
            \node[struct name] (z2) {z2}; &[+2\boxsize]
            \node[car] (c11) {}; & \node[cdr] (c12) {}; &[+\boxsize]
            \node[car] (c13) {}; & \node[cdr] (c14) {}; &[+\boxsize]
            \node[car] (c15) {}; & \node[cdr] (c16) {}; \\

            &&&
            \node[box] (a) {a}; &&
            \node[box] (b) {b}; \\

            &&&
            \node[car] (c21) {}; & \node[cdr] (c22) {}; &
            \node[car] (c23) {}; & \node[cdr] (c24) {}; \\

            &&&
            \node[box] (wow) {wow}; \\
            };

            \draw[pointer] (z2) -- (c11);
            \draw[box pointer] (c11.base) |- (c21);
            \link{c12}{c13}
            \link{c13}{a}
            \link{c14}{c15}
            \link{c15}{b}
            \nil{c16}
            \link{c21}{wow}
            \link{c22}{c23}
            \link{c23}{b}
            \nil{c24}
        \end{tikzpicture}
        \caption{The list \vscm{z2} after applying \vscm{set-to-wow!} to it.}
        \label{3.15z2}
    \end{figure}
    Figures~\ref{3.15z1} and~\ref{3.15z2} show the effect of \vscm{set-to-wow!} 
    on \vscm{z1} and \vscm{z2}.
\end{exe}

\begin{exe}[3.16]
    \begin{figure}
        \centering
        \begin{tikzpicture}[box and pointer,
            every label/.style={font=\sffamily}]
            \hspace{-1.3cm} % To center the figure better.
            % Example returning 3.
            \matrix[cell matrix, label=below:{List structure returning 3.}] (e1) 
            {
            \node[struct name] (x) {x}; &[+\boxsize]
            \node[car] (x11) {}; & \node[cdr] (x12) {}; &[+\boxsize]
            \node[car] (x21) {}; & \node[cdr] (x22) {}; &[+\boxsize]
            \node[car] (x31) {}; & \node[cdr] (x32) {}; \\

            & \node[box] (xa) {a}; &&
            \node[box] (xb) {b}; &&[+\boxsize]
            \node[box] (xc) {c}; \\
            };

            \draw[pointer] (x) -- (x11);
            \link{x11}{xa}
            \link{x12}{x21}
            \link{x21}{xb}
            \link{x22}{x31}
            \link{x31}{xc}
            \nil{x32}

            % Example returning 4.
            \matrix[cell matrix, right=of e1, label=below:{List structure 
            returning 4.}] (e2) {
            \node[struct name] (y) {y}; &[+\boxsize]
            \node[car] (y11) {}; & \node[cdr] (y12) {}; &[+\boxsize]
            \node[car] (y21) {}; & \node[cdr] (y22) {}; &[+\boxsize]
            \node[car] (y31) {}; & \node[cdr] (y32) {}; \\

            &&&
            \node[box] (ya) {a}; &&[+\boxsize]
            \node[box] (yb) {b}; \\
            };

            \draw[pointer] (y) -- (y11);
            \draw[box pointer] (y11.base) -- ++(0, 1.2\boxsize) -| (y31);
            \link{y12}{y21}
            \link{y21}{ya}
            \link{y22}{y31}
            \link{y31}{yb}
            \nil{y32}

            % Example returning 7.
            \matrix[cell matrix, below=4em of e1, label=below:{List structure 
            returning 7.}] (e3) {
            \node[struct name] (z) {z}; &[+\boxsize]
            \node[car] (z11) {}; & \node[cdr] (z12) {}; &[+\boxsize]
            \node[car] (z21) {}; & \node[cdr] (z22) {}; &[+\boxsize]
            \node[car] (z31) {}; & \node[cdr] (z32) {}; \\

            &&&&&
            \node[box] (za) {a}; \\
            };

            \draw[pointer] (z) -- (z11);
            \draw[box pointer] (z11.base) -- ++(0, -1.2\boxsize) -| (z21);
            \link{z12}{z21}
            \draw[box pointer] (z21.base) -- ++(0, 1.2\boxsize) -| (z31);
            \link{z22}{z31}
            \link{z31}{za}
            \nil{z32}

            % Example never returning.
            \matrix[cell matrix, right=of e3, label=below:{List structure never 
            returning.}] (e4) {
            \node[struct name] (t) {t}; &[+\boxsize]
            \node[car] (t11) {}; & \node[cdr] (t12) {}; &[+\boxsize]
            \node[car] (t21) {}; & \node[cdr] (t22) {}; &[+\boxsize]
            \node[car] (t31) {}; & \node[cdr] (t32) {}; \\

            & \node[box] (ta) {a}; &&
            \node[box] (tb) {b}; &&[+\boxsize]
            \node[box] (tc) {c}; \\
            };

            \draw[pointer] (t) -- (t11);
            \link{t11}{ta}
            \link{t12}{t21}
            \link{t21}{tb}
            \link{t22}{t31}
            \link{t31}{tc}
            \draw[box pointer] (t32.base) -- ++(0, 1.2\boxsize) -| (t11);
        \end{tikzpicture}
        \caption{Structures made of exactly three pairs for which Ben’s 
            procedure returns different values.}
        \label{3.16ex}
    \end{figure}
    \autoref{3.16ex} shows examples of list structures made up of exactly three 
    pairs for which Ben’s procedure returns 3, 4, 7, or never at all.
    These structures can be defined in the following way, using 
    \vscm{make-cycle} from \autoref{3.13} for the last one.
    \scm{ch3/3.16.scm}
\end{exe}

\begin{exe}[3.17]
    A possible solution is:
    \scm{ch3/3.17.scm}
\end{exe}

\begin{exe}[3.18]
    Here is a possible solution:
    \scm{ch3/3.18.scm}
\end{exe}

\begin{exe}[3.19]
    We go through the list with two pointers: one advancing one step at a time, 
    the other advancing two steps at a time. If the list contains a cycle, 
    they’ll end up pointing to the same pair after a while. Otherwise, the 
    second one will reach the end of the list.
    \scm{ch3/3.19.scm}
\end{exe}

\subsubsection{Mutation is just assignment}

\begin{exe}[3.20]
    \begin{figure}
        \begin{tikzpicture}[>=Stealth, thick]
            \matrix[matrix anchor=base west, column sep=2\nametoenv, column 
            2/.style={anchor=base west}] at (0,0) {
            & \node[code] (cons) {cons: ...}; \\[-3pt]
            \node[text width=1cm, align=right] (ge) {global\\ env};
            & \node[code] (z) {z: }; \\[-8pt]
            & \node[code] (x) {x: }; \\
            };

            % E1
            \coordinate (e1pos) at ($ (g.south west)!.10!(g.south east) $);
            \matrix[matrix anchor=north west, column sep=2\nametoenv,
            below=of e1pos, column 2/.style={anchor=base west}] {
            \node[text width=1cm, align=right] (e1) {E1};
            & \node[code] (x1) { x: 1}; \\[-11pt]
            & \node[code] (y1) { y: 2}; \\
            & \node[code] { set-x!: ... }; \\
            & \node[code] { set-y!: ... }; \\
            & \node[code] (dispatch1) { dispatch: }; \\
            };

            % E2
            \coordinate (e2pos) at ($ (g.south west)!.55!(g.south east) $);
            \matrix[matrix anchor=north west, column sep=2\nametoenv,
            below=of e2pos, column 2/.style={anchor=base west}] {
            \node[text width=1cm, align=right] (e2) {E2};
            & \node[code] (x2) { x: x}; \\[-11pt]
            & \node[code] (y2) { y: x}; \\
            & \node[code] { set-x!: ... }; \\
            & \node[code] { set-y!: ... }; \\
            & \node[code] (dispatch2) { dispatch: }; \\
            };

            % Backgrounds
            \begin{scope}[on background layer]
                \node[global env, fit=(cons) (x), right=\nametoenv of ge, 
                yshift=1mm] (g) {};
                \node[env, minimum width=4cm, fit=(x1) (dispatch1), 
                right=\nametoenv of e1, yshift=-6mm] (n1) {};
                \node[env, minimum width=4cm, fit=(x2) (dispatch2), 
                right=\nametoenv of e2, yshift=-6mm] (n2) {};
            \end{scope}

            \coordinate (xp1) at ($ (n1.south)!.50!(n1.south east) $);
            \coordinate[below=of xp1] (p1);
            \procedure{p1}{c1}{c2}
            \node[code, below=of p1] (code) {
            parameters: m\\
            body: (cond ...)
            };

            \coordinate (xp2) at ($ (n2.south)!.50!(n2.south east) $);
            \coordinate[below=of xp2] (p2);
            \procedure{p2}{c3}{c4}

            \draw[->] (c1) -- (c1 |- code.north);
            \draw[->] (c2) -| ($ (n1.south east) - (3mm, 0) $);

            \draw[->] (ge) -- (ge.west -| g.west);
            \draw[->] (e1) -- (e1.east -| n1.west);
            \draw[->] (n1.north) -- (n1.north |- g.south);
            \draw[->] (dispatch1) -| ($ (p1) + (0, \circleradius) $);

            \draw[->] (e2) -- (e2.east -| n2.west);
            \draw[->] (c3) |- (code);
            \draw[->] (c4) -| ($ (n2.south east) - (3mm, 0) $);
            \draw[->] (n2.north) -- (n2.north |- g.south);
            \draw[->] (dispatch2) -| ($ (p2) + (0, \circleradius) $);
            \draw[->] (x) -- ($ (x) + (1cm, 0) $)
                |- ($ (p1) + (-2\circleradius, 0) $);
            \draw[->] (z) -- ($ (z) + (7cm, 0) $)
                |- ($ (p2) + (-2\circleradius, 0) $);
        \end{tikzpicture}
        \caption{Environment structure after the definitions of \vscm{x} and 
        \vscm{z}. In E2, the values of \vscm{x} and \vscm{y} correspond to the 
        \vscm{x} defined in the global environment.}
        \label{3.20fig}
    \end{figure}
    \autoref{3.20fig} shows the environments created by the definitions of 
    \vscm{x} and \vscm{z}. When\\
    \vscm{(set-car! (cdr z) 17)} is evaluated, \vscm{(cdr z)} is evaluated 
    first. This creates an environment E3 pointing to E2, where \vscm{(z 'cdr)} 
    is evaluated, returning the \vscm{x} defined in the global environment. So 
    the expression becomes \vscm{(set-car! x 17)}, evaluated in the global 
    environment. The expression
    \vscm{((x 'set-car!) 17)} is then evaluated. The evaluation of
    \vscm{(x 'set-car!)} leads to the creation of an environment E4 pointing to 
    E1, in which the evaluation returns the \vscm{set-x!} procedure from 
    environment E1. The evaluation of the expression obtained \vscm{(set-x! 17)} 
    leads to the modification of the value of \vscm{x} in environment E1. 
    Lastly, \vscm{(car x)} is evaluated in an environment pointing to E1, so the 
    value returned is 17.
\end{exe}

\subsection{Representing Queues}

\begin{exe}[3.21]
    The elements actually contained in the queue are only the contents of the 
    queue’s \vscm{car}. The queue’s \vscm{cdr} points to the last element of the 
    queue, so it is printed twice. The rear pointer is not updated when the last 
    element from the queue is deleted, so the former last element is still 
    printed although the queue is empty.
    \scm{ch3/3.21.scm}
\end{exe}

\begin{exe}[3.22]
    The constructor, selectors and mutators can be defined in the following way. 
    The implementation of the queue operations doesn’t need to be modified.
    \scm{ch3/3.22.scm}
\end{exe}

\begin{exe}[3.23]
    To respect the requirement that all operations should be accomplished in 
    $\Theta(1)$ steps, it’s necessary to use a doubly-linked list instead of 
    a singly-linked list. The deque is represented as a pair containing 
    a pointer to the first element of a list and a pointer to the last element 
    of this list just like the queue. Each element of the list is a pair 
    containing the value and a pointer to the previous element of the list. 
    Since such a structure can’t be printed since it contains infinite loops as 
    soon as the deque contains at least 2 elements, the insertion and deletion 
    procedures return a list representation of the contents of the deque.
    \scm{ch3/3.23.scm}
\end{exe}

\subsection{Representing Tables}

\begin{exe}[3.24]
    The only necessary change is to define an \vscm{assoc} procedure that uses 
    the provided \vscm{same-key?} instead of \vscm{equal?}. The code below is 
    a possible solution for a one-dimensional table. For multi-dimensional 
    tables, there is no reason to assume that the successive keys are of the 
    same type or that the same equality test must be used at every level, so 
    multiple comparison procedures should be provided, and the right procedure 
    should be passed as an argument to \vscm{assoc} at each level of the table.
    \scm{ch3/3.24.scm}
    \scm{ch3/3.24test.scm}
\end{exe}

\begin{exe}[3.25]
    It would be possible to use the lists as keys directly but I don’t think 
    that’s the point of the exercise. The solution I implemented allows 
    different numbers of keys for different records, however it does not allow 
    keys that are prefixes of each other: if a value is stored under the key
    \vscm{'(a b c)} and another value is then stored under \vscm{'(a b)}, the 
    record for \vscm{'(a b c)} is silently deleted, and vice versa. It would 
    also be inefficient for large tables since it checks whether the record 
    found really contains a table by going through the whole record before 
    looking for the following key in it.
    \scm{ch3/3.25.scm}
\end{exe}

\begin{exe}[3.26]
    Here is an example of a one-dimensional table where the keys are ordered 
    with the given comparison procedure \vscm{<?}. The local table is stored as 
    a binary tree of records instead of a headed list. I used mutable trees 
    instead of using the \vscm{adjoin-set} procedure for binary trees of 
    \secref[Sets-as-binary-trees]{2.3.3} to avoid stacking recursive calls and 
    creating multiple intermediate trees.
    \scm{ch3/3.26.scm}
\end{exe}

\begin{exe}[3.27]
    \begin{figure}
        \begin{tikzpicture}[>=Stealth, thick]
            \matrix[matrix anchor=base west, column sep=2\nametoenv, column 
            2/.style={anchor=base west}] at (0,0) {
            \node[text width=1cm, align=right] (ge) {global\\ env};
            & \node[code] (memoize) {memoize: ...}; \\[-8pt]
            & \node[code] (memo-fib) {memo-fib: }; \\
            };
            \coordinate (e1pos) at ($ (g.south west)!.25!(g.south east) $);
            \matrix[matrix anchor=north west, column sep=2\nametoenv,
            below=1cm of e1pos, column 2/.style={anchor=base west}] {
            \node[text width=1cm, align=right] (e1) {E1};
            & \node[code] (f) { f: ...}; \\[-11pt]
            & \node[code] (table) { table: ... }; \\
            };
            \begin{scope}[on background layer]
                \node[global env, fit=(memoize) (memo-fib),
                right=\nametoenv of ge, yshift=-1mm] (g) {};
                \node[env, minimum width=3cm, fit=(f) (table),
                right=\nametoenv of e1, yshift=1mm] (n1) {};
            \end{scope}

            \coordinate (xp1) at ($ (n1.south west)!.50!(n1.south east) $);
            \coordinate[below=of xp1] (p1);
            \procedure{p1}{c1}{c2}
            \node[code, below=of p1] (code) {
            parameters: x\\
            body: (let ...)
            };

            \draw[->] (c1) -- (c1 |- code.north);
            \draw[->] (c2) -- (c2 |- n1.south);

            \draw[->] (ge) -- (ge.west -| g.west);
            \draw[->] (e1) -- (e1.east -| n1.west);
            \draw[->] (n1.north) -- (n1.north |- g.south);

            \draw[->] (memo-fib) -- ($ (memo-fib) + (2cm, 0) $)
                |- ($ (p1) + (-2\circleradius, 0) $);

            % Evaluation of (memo-fib 3)
            \node[env, right=of n1] (n3) {n: 3};
            \node[below=of n3] {$\vdots$};
            \node[right=of n3] (e4) {E4};
            \draw[->] (e4) -- (n3);
            \draw[->] (n3) -- (n3 -| n1.east);
        \end{tikzpicture}

        \caption{Environments created during the evaluation of
        \vscm{(memo-fib 3)}.}
        \label{3.27fig}
    \end{figure}
    \autoref{3.27fig} shows some of the environments created during the 
    evaluation of \vscm{(memo-fib 3)}.
    The call to \vscm{memoize} creates a local environment E1 containing 
    a table, and the procedure returned by \vscm{memoize} points to this 
    environment. When \vscm{memo-fib} is called for the first time with a value, 
    it puts the computed result into the table. When it is called again with the 
    same value, it simply returns the value stored in the table instead of 
    making recursive calls. So \vscm{memo-fib} computes the $n$th Fibonacci 
    number in linear time because it never computes the value for the same 
    number twice.

    If we had defined \vscm{memo-fib} to be \vscm{(memoize fib)}, it would not 
    have worked because \vscm{fib} calls itself rather than \vscm{memo-fib} 
    recursively.
\end{exe}

\subsection{A Simulator for Digital Circuits}

\subsubsection{Primitive function boxes}

\begin{exe}[3.28]
    Here is a definition of an or-gate similar to the definiton of the and-gate:
    \scm{ch3/3.28.scm}
\end{exe}

\begin{exe}[3.29]
    Using the logical equivalency between $a \lor b$ and $\lnot (\lnot a \land 
    \lnot b)$, we can build an or-gate from and-gates and inverters. The delay 
    for an or-gate built this way is the and-gate delay plus twice the inverter 
    delay.
    \scm{ch3/3.29.scm}
\end{exe}

\begin{exe}[3.30]
    The ripple-carry-adder can be defined using the following procedure:
    \scm{ch3/3.30.scm}

    Let’s use the following notations: $o = \textrm{or-delay}, 
    a = \textrm{and-delay}, i = \textrm{inverter-delay}$.
    Let’s call $R_{Ci}$ the delay to obtain $C_i$ in a ripple-carry adder, 
    $R_{Si}$ the delay to obtain $S_i$ in a ripple-carry adder, $F_s$ the delay 
    to obtain the sum bit in a full-adder, $F_c$ the delay to obtain the carry 
    bit in a full-adder, $H_s$ the delay to obtain the carry in a half-adder, 
    $H_c$ the delay to obtain the carry in a half-adder.

    For the half-adder we have $H_c = a$ and
    $H_s = \max(2a + i, o + a)$.

    For the full-adder, we have $F_s = 2 H_s = 2 \max(2a + i, o + a)$, and $F_c 
    = H_s + H_c + o = a + o + \max(2a + i, o + a)$, from where
    $F_s \geq F_c$.

    For the full-carry adder, we have:
    $R_{Ci} = (n - i) \times F_c$ and $R_{Si} = R_{Ci} + F_s$ because only the 
    carry is transmitted to the following full-adders.

    The delay to obtain the complete output from an $n$-bit ripple-carry adder 
    is $R_{C1} + \max(F_s, F_c) = R_{C1} + F_s = (n - 1) F_c + F_s$. In terms of 
    the delays for and-gates, or-gates and inverters, the delay for the 
    ripple-carry adder is
    $ (n - 1) (a + o) + (n + 1) \max(2a + i, o + a) $.
\end{exe}

\subsubsection{Representing wires}

\begin{exe}[3.31]
    The initialization is necessary to compute correctly all the signals with 
    the initial values of the inputs. Since there are inverters, not all signals 
    are 0 even if all inputs and outputs are 0, and if they are not initialized 
    properly, the values computed after changing the inputs could be wrong as 
    well.

    In the case of the half-adder example, without the initialization, the 
    output of the inverter would have a signal of 0 instead of 1 initially. 
    Since setting the first input to 1 does not trigger a change to the 
    inverter’s input, the sum would remain 0 after the propagation. After 
    setting the second input to 1, the sum would still remain 0 and the carry 
    would become 1.
\end{exe}

\subsubsection{Implementing the agenda}

\begin{exe}[3.32]
    If the (last in, first out) order is used, the values set by the actions 
    executed last in a segment could set incorrect values because they are not 
    taking into account all the changes that occurred in that segment.

    If the inputs $a_1$ and $a_2$ are $0$ and $1$ are both changed in the same 
    segment, if the action triggered by the change of $a_2$ is executed first, 
    an action setting the output value to $0$ is scheduled, than when the change 
    to $a_1$ is taken into account, the same action is scheduled again at the 
    same time, so the order of execution of these two actions does not matter.

    However, if the change to $a_1$ is treated first, an action setting the 
    output signal to $1$ is scheduled, and when $a_2$ switches to $0$ an action 
    setting the output signal to $0$ is scheduled at the same time. If these 
    actions are executed (last in, first out), the final output value will be 
    $1$ instead of $0$ because the scheduled action executed last used stale 
    values for some signals.
\end{exe}

\subsection{Propagation of Constraints}

\begin{exe}[3.33]
    The averager can be defined in the following way, since we want 
    $ a + b = 2c$:
    \scm{ch3/3.33.scm}
\end{exe}

\begin{exe}[3.34]
    The squarer defined in this way works only in one direction because the 
    multiplier needs two of its three connectors to have a value to be able to 
    set the third connector’s value. If the value of \vscm{a} is set, the value 
    of \vscm{b} will be set correctly, but if the value of \vscm{b} is set, the 
    value of \vscm{a} won’t be set because only one connector has a value.
\end{exe}

\begin{exe}[3.35]
    The squarer can be defined in the following way:
    \scm{ch3/3.35.scm}
\end{exe}

\begin{exe}[3.36]
    \begin{figure}
        \hspace{-1cm}
        \begin{tikzpicture}[>=Stealth, thick]
            % Global environment
            \matrix[matrix anchor=base west, column sep=2\nametoenv, column 
            2/.style={anchor=base west}] at (0,0) {
                & \node[code] (fee) {for-each-except: ...}; \\[-8pt]
                \node[text width=1cm, align=right] (ge) {global\\ env};
                & \node[code] (mc) {make-connector: ...}; \\[-9pt]
                & \node[code] (sv) {set-value!: ...}; \\
                & \node[code] {inform-about-value: ...}; \\
                & \node[code] (b) {b:}; \\
                & \node[code] (a) {a:}; \\
            };

            % E1
            \coordinate (e1pos) at ($ (g.south west)!.05!(g.south east) $);
            \matrix[column sep=2\nametoenv, below=of e1pos] (env1m) {
                \node[text width=1cm, align=right] (env1n) {E1};
                & \node[env, minimum width=3cm, minimum height=1em] (env1) {}; 
            \\
            };

            % E2
            \matrix[column sep=2\nametoenv, below=of env1m, column 
                2/.style={anchor=base west}] (env2m) {
                \node[text width=1cm, align=right] (env2n) {E2};
                & \node[code] (value1) { value: 10}; \\[-11pt]
                & \node[code] { informant: 'user}; \\
                & \node[code] { constraints: '() }; \\
                & \node[code] { set-my-value: ... }; \\
                & \node[code] { forget-my-value: ... }; \\
                & \node[code] { connect: ... }; \\
                & \node[code] (me1) { me: }; \\
            };

            % E3
            \coordinate (e3pos) at ($ (g.south west)!.85!(g.south east) $);
            \matrix[column sep=2\nametoenv, below=of e3pos] (env3m) {
                \node[text width=1cm, align=right] (env3n) {E3};
                & \node[env, minimum width=3cm, minimum height=1em] (env3) {}; 
            \\
            };

            % E4
            \matrix[column sep=2\nametoenv, below=of env3m, column 
            2/.style={anchor=base west}] {
                \node[text width=1cm, align=right] (env4n) {E4};
                & \node[code] (value2) { value: false}; \\[-11pt]
                & \node[code] { informant: false}; \\
                & \node[code] { constraints: '() }; \\
                & \node[code] { set-my-value: ... }; \\
                & \node[code] { forget-my-value: ... }; \\
                & \node[code] { connect: ... }; \\
                & \node[code] (me2) { me: }; \\
            };

            % E5 (set-value! a 10 'user)
            \coordinate (e5pos) at ($ (g.north west)!.05!(g.north east) $);
            \matrix[column sep=2\nametoenv, above=6.5em of e5pos, column 
                2/.style={anchor=west}] (env5m) {
                & \node[code] (conn5) {connector: a}; \\[-9pt]
                \node (env5n) {E5};
                & \node[code] {new-value: 10}; \\
                & \node[code] (inf5) {informant: 'user}; \\
            };

            % E6 (a 'set-value)
            \node[code, right=3cm of value1, env] (env6) {request: 'set-value};
            \node[above=of env6] (env6n) {E6};

            % E7 (set-my-value 10 'user)
            \node[below=1em of env6] (env7n) {E7};
            \matrix[below=of env7n, nodes={anchor=west}] {
                \node[code] (nv7) {newval: 10}; \\
                \node[code] (setter7) {setter: 'user}; \\
            };

            % E8 (for-each-except ...)
            \matrix[column sep=2\nametoenv, yshift=1em, right=of env5m, column 
                2/.style={anchor=west}] (env8m) {
                & \node[code] (ex8) {exception: 'user}; \\
                \node[align=right] (env8n) {E8};
                & \node[code] (proc8) {procedure: inform-about-value}; \\
                & \node[code] (list8) {list: '()}; \\
                & \node[code] (loop8) {loop: ...}; \\
            };

            % Backgrounds (global environment, E2, E4, E5, E7, E8)
            \begin{scope}[on background layer]
                \node[global env, fit=(fee) (a), right=\nametoenv of ge, 
                yshift=-1.5em] (g) {};
                \node[env, minimum width=4cm, fit=(value1) (me1), below=of env1, 
                yshift=-1mm] (env2) {};
                \node[env, minimum width=4cm, fit=(value2) (me2), below=of env3, 
                yshift=-1mm] (env4) {};
                \node[env, fit=(conn5) (inf5)] (env5) {};
                \node[env, fit=(nv7) (setter7)] (env7) {};
                \node[env, fit=(ex8) (proc8) (list8) (loop8)] (env8) {};
            \end{scope}

            % E9 (loop ...)
            \node[env, code, above=of env8] (env9) {list: list}; \\
            \node[left=of env9] (env9n) {E9};
            \draw[->] (env9n) -- (env9);
            \draw[->] (env9) -- (env8);

            \coordinate[below=of env2] (p1);
            \procedure{p1}{c1}{c2}
            \node[code, below=of p1] (code) {
            parameters: request\\
            body: (cond ...)
            };

            \coordinate[below=of env4] (p2);
            \procedure{p2}{c3}{c4}

            \draw[->] (c1) -- (c1 |- code.north);
            \draw[->] (c2) -| ($ (env2.south east) - (1cm, 0) $);

            \draw[->] (ge) -- (ge.west -| g.west);
            \draw[->] (env1n) -- (env1n.east -| env1.west);
            \draw[->] (env2n) -- (env2n.east -| env2.west);
            \draw[->] (env3n) -- (env3n.east -| env3.west);
            \draw[->] (env4n) -- (env4n.east -| env4.west);
            \draw[->] (env1.north) -- (env1.north |- g.south);
            \draw[->] (me1) -| ($ (p1) + (0, \circleradius) $);
            \draw[->] (env2) -- (env1);

            \draw[->] (env5n) -- (env5n.east -| env5.west);
            \draw[->] (env5) -- (env5.south |- g.north);

            \draw[->] (env6n) -- (env6n |- env6.north);
            \draw[->] (env6) -- (env6 -| env2.east);
            \draw[->] (env7n) -- (env6n |- env7.north);
            \draw[->] (env7) -- (env7 -| env2.east);

            \draw[->] (env8n) -- (env8n -| env8.west);
            \draw[->] (env8) -- (env8 |- g.north);

            \draw[->] (c3) |- (code);
            \draw[->] (c4) -| ($ (env4.south east) - (1cm, 0) $);
            \draw[->] (env3.north) -- (env3.north |- g.south);
            \draw[->] (env4) -- (env3);
            \draw[->] (me2) -| ($ (p2) + (0, \circleradius) $);
            \draw[->] (a) -- ($ (a) - (2.3cm, 0) $)
                |- ($ (p1) + (-2\circleradius, 0) $);
            \draw[->] (b) -- ($ (b) + (8cm, 0) $)
                |- ($ (p2) + (-2\circleradius, 0) $);
        \end{tikzpicture}
        \caption{Environment structure in which the expresion
        \vscm{(for-each-except setter inform-about-value constraints)} is 
        evaluated.}
        \label{3.36fig}
    \end{figure}

    \autoref{3.36fig} shows the environment structure in which the expression is 
    evaluated. The environments created when defining \vscm{a} and \vscm{b} are 
    similar to those created in \autoref{3.10}: an environment E1 (resp. E3) is 
    created for the evaluation of \vscm{(make-connector)}, then since 
    \vscm{(make-connector)} contains a \vscm{let}, a new environment E2 (resp. 
    E4) pointing to E1 (resp. E3) is created. The variables \vscm{value}, 
    \vscm{informant}, \vscm{constraints} and the local procedures 
    \vscm{set-my-value}, \vscm{forget-my-value}, \vscm{connect} and \vscm{me} 
    are defined in E2 (resp. E4). The local procedure \vscm{me} pointing to E2 
    (resp. E4) is returned and bound to \vscm{a} (resp. \vscm{b}).

    The following environments are created during the evaluation of 
    \vscm{(set-value! a 10 'user)}:
    \begin{itemize}
        \item E5: for the evaluation of \vscm{(set-value! a 10 'user)}. It 
            points to the global environment since \vscm{set-value!} is defined 
            there.
        \item E6: for the evaluation of \vscm{(a 'set-value!)}. It points to E2 
            since \vscm{a} is a procedure pointing to E2. The evaluation returns 
            the \vscm{set-my-value} procedure from E2.
        \item E7: for the evaluation of \vscm{(set-my-value 10 'user)}. It 
            points to E2 since \vscm{set-my-value} is the procedure returned at 
            the previous step.
        \item E8: After \vscm{(has-value? me)} is evaluated (environments 
            omitted) the values of \vscm{value} and \vscm{informant} are changed 
            in \vscm{set-my-value}, \vscm{for-each-except} is called, which 
            leads to the creation of environment E8 pointing to the global 
            environment since that’s where \vscm{for-each-except} was defined. 
            The \vscm{loop} procedure is defined in E8, so the evaluation of 
            \vscm{(loop list)} leads to the creation of E9 pointing to E8.

            There are no constraints here so no further environments are 
            created. Otherwise, for each constraint, an environment pointing to 
            the global environment would be created, in which 
            \vscm{(inform-about-value construint)} would be evaluated. Then 
            \newline
            \vscm{(constraint 'I-have-a-value)} would be evaluated in an 
            environment pointing to the constraint’s local environment.
    \end{itemize}
\end{exe}

\begin{exe}[3.37]
    The procedures can be defined in the following way:
    \scm{ch3/3.37.scm}
\end{exe}

\section{Concurrency: Time Is of the Essence}

\subsection{The Nature of Time in Concurrent Systems}

\begin{exe}[3.38]
    \ \vspace{-20pt}
    \begin{enumerate}
        \item If no interleaving is possible, the possible final values are 
            \$35, \$40, \$45 and \$50:
            \begin{itemize}
                \item Peter, Paul, Mary: \$45;
                \item Paul, Peter, Mary: \$45;
                \item Mary, Peter, Paul: \$40;
                \item Mary, Paul, Peter: \$40;
                \item Peter, Mary, Paul: \$35;
                \item Paul, Mary, Peter: \$50.
            \end{itemize}
        \item Some of the possible other values are \$110, \$80, \$55, \$90. 
            Figures~\ref{3.38.1} and~\ref{3.38.2} show timing diagrams 
            explaining how the value \$110 and \$90 can occur.
    \end{enumerate}

    \begin{figure}
        \small
        \centering
        \begin{tikzpicture}[>=Stealth]
            \matrix[time matrix] {
                \node (Peter) {Peter}; &
                \node (Mary) {Mary}; &
                \node (Bank) {Bank}; &
                \node (Paul) {Paul}; \\

                && \node[bank] (b100) {\$100}; & \\
                \node[action] (peacc) {Access balance: \$100}; &&& \\
                & \node[action] (macc) {Access balance: \$100}; && \\
                &&& \node[action] (paacc) {Access balance: \$100}; \\
                \node[action] (penv) {new value: $100 + 10 = 110$}; &&& \\
                & \node[action] (mnv) {new value: $100 / 2 = 50$}; && \\
                &&& \node[action] (panv) {new value: $100 - 20 = 80$}; \\
                & \node[action] (mset) {set! balance to \$50}; && \\
                && \node[bank] (b50) {\$50}; &\\
                &&& \node[action] (paset) {set! balance to \$80}; \\
                && \node[bank] (b80) {\$80}; &\\
                \node[action] (peset) {set! balance to \$110}; &&& \\
                && \node[bank] (b110) {\$110}; &\\
            };

            \draw[arrow] (b100) -| (peacc);
            \draw[arrow] (peacc) -- (penv);
            \draw[arrow] (penv) -- (peset);
            \draw[arrow] (peset) |- (b110);

            \draw[arrow] (b100) -| (macc);
            \draw[arrow] (macc) -- (mnv);
            \draw[arrow] (mnv) -- (mset);
            \draw[arrow] (mset) |- (b50);

            \draw[arrow] (b100) -| (paacc);
            \draw[arrow] (paacc) -- (panv);
            \draw[arrow] (panv) -- (paset);
            \draw[arrow] (paset) |- (b80);

            \draw[<-, line width=.8mm] (current bounding box.south west) 
            --node[sloped,above]{time} (current bounding box.north west);
        \end{tikzpicture}
        \caption{A timing diagram showing how the final value can be \$110.}
        \label{3.38.1}
    \end{figure}

    \begin{figure}
        \small
        \centering
        \begin{tikzpicture}[>=Stealth]
            \matrix[time matrix] {
                \node (Peter) {Peter}; &
                \node (Mary) {Mary}; &
                \node (Bank) {Bank}; &
                \node (Paul) {Paul}; \\

                && \node[bank] (b100) {\$100}; & \\
                \node[action] (peacc) {Access balance: \$100}; &&& \\[+1.5em]
                \node[action] (penv) {new value: $100 + 10 = 110$}; &&& 
                \\[+1.5em]
                \node[action] (peset) {set! balance to \$110}; &&& \\
                && \node[bank] (b110) {\$110}; &\\
                & \node[action] (macc) {Access balance: \$110}; && \\[+1.5em]
                & \node[action] (mnv) {new value: $110 / 2 = 55$}; && \\
                &&& \node[action] (paacc) {Access balance: \$110}; \\[+1.5em]
                &&& \node[action] (panv) {new value: $110 - 20 = 90$}; \\
                & \node[action] (mset) {set! balance to \$55}; && \\
                && \node[bank] (b55) {\$55}; &\\
                &&& \node[action] (paset) {set! balance to \$90}; \\
                && \node[bank] (b90) {\$90}; &\\
            };

            \draw[arrow] (b100) -| (peacc);
            \draw[arrow] (peacc) -- (penv);
            \draw[arrow] (penv) -- (peset);
            \draw[arrow] (peset) |- (b110);

            \draw[arrow] (b100) -| (macc);
            \draw[arrow] (macc) -- (mnv);
            \draw[arrow] (mnv) -- (mset);
            \draw[arrow] (mset) |- (b55);

            \draw[arrow] (b100) -| (paacc);
            \draw[arrow] (paacc) -- (panv);
            \draw[arrow] (panv) -- (paset);
            \draw[arrow] (paset) |- (b90);

            \draw[<-, line width=.8mm] (current bounding box.south west) 
            --node[sloped,above]{time} (current bounding box.north west);
        \end{tikzpicture}
        \caption{A timing diagram showing how the final value can be \$90.}
        \label{3.38.2}
    \end{figure}
\end{exe}

\subsection{Mechanisms for Controlling Concurrency}

\subsubsection{Serializers in Scheme}

\begin{exe}[3.39]
    The remaining possibilities are 101, 121 and 100. The value of \vscm{x} 
    can’t change between the two times that $P_1$ accesses it to evaluate
    \vscm{(* x x)} so 110 is not possible anymore. The value of \vscm{x} can’t 
    change during the execution of $P_2$ so 11 is not possible anymore. The 
    final value can be 100 if $P_1$ accesses \vscm{x} and computes the final 
    value as 100 but $P_2$ accesses it and sets it to 11 before $P_1$ can set it 
    to 100.
\end{exe}

\begin{exe}[3.40]
    The possible values are:
    \begin{itemize}
        \item $100$: $P_1$ accesses \vscm{x} twice and $P_2$ accesses \vscm{x} 
            thrice, then \vscm{x} $P_2$ sets \vscm{x} to 1000 before $P_1$ sets 
            it to 100.
        \item $1000$: $P_1$ accesses \vscm{x} twice and $P_2$ accesses \vscm{x} 
            thrice, then \vscm{x} $P_1$ sets \vscm{x} to 100 before $P_2$ sets 
            it to 1000.
        \item $10\,000$: either $P_1$ accesses \vscm{x} once before $P_2$ sets 
            it to 1000, or $P_2$ accesses \vscm{x} twice before $P_1$ sets it to 
            100.
        \item $100\,000$: $P_2$ accesses \vscm{x} once before $P_1$ sets it to 
        100.
        \item $1\,000\,000$: the two procedures execute sequentially in any 
    order.
    \end{itemize}

    If the procedures are serialized the only possible value is $100\,000$.
\end{exe}

\begin{exe}[3.41]
    I don’t think serializing access to balance is necessary because both 
    \vscm{withdraw} and \vscm{deposit} make a single assignment to 
    \vscm{balance}, so accessing \vscm{balance} concurrently with one of these 
    procedures will reflect the state of the account either before or after the 
    withdrawal or deposit, but it will correspond to a real state of the 
    account.
\end{exe}

\begin{exe}[3.42]
    The change proposed by Ben Bitdiddle is safe to make. The two versions of 
    \vscm{make-account} allow the same concurrency.
\end{exe}

\subsubsection{Complexity of using multiple shared resources}

\begin{exe}[3.43]
    \begin{figure}
        \centering
        \begin{tikzpicture}[>=Stealth]
            \matrix[time matrix] {
                &
                \node (a1) {a1}; &
                \node (a2) {a2}; &
                \node (a3) {a3}; & \\

                & \node[bank] (a130) {\$30}; &
                \node[bank] (a220) {\$20}; &
                \node[bank] (a310) {\$10}; & \\
                \node[action] (p1aa1) {Access balance a1: \$30}; &&& \\
                &&&& \node[action] (p2aa2) {Access balance a2: \$20}; \\
                \node[action] (p1aa2) {Access balance a2: \$20}; &&& \\
                &&&& \node[action] (p2aa3) {Access balance a3: \$10}; \\
                \node[action] (p1diff) {Difference: \$10}; &&& \\
                &&&& \node[action] (p2diff) {Difference: \$10}; \\
                \node[action] (p1w) {\vscm{((a1 'withdraw) 10)}}; &&& \\
                & \node[bank] (a120) {\$20}; &&& \\
                &&&& \node[action] (p2w) {\vscm{((a2 'withdraw) 10)}}; \\
                && \node[bank] (a210) {\$10}; && \\
                \node[action] (p1d) {\vscm{((a2 'deposit) 10)}}; &&& \\
                && \node[bank] (a220b) {\$20}; && \\
                &&&& \node[action] (p2d) {\vscm{((a3 'deposit) 10)}}; \\
                &&& \node[bank] (a320) {\$20}; & \\
            };

            \draw[arrow] (a130) -| (p1aa1);
            \draw[arrow] (a220) |- (p1aa2);
            \draw[arrow] (p1aa1) -- (p1aa2);
            \draw[arrow] (p1aa2) -- (p1diff);
            \draw[arrow] (p1diff) -- (p1w);
            \draw[arrow] (p1w) -- (p1d);
            \draw[arrow] (p1w) |- (a120);
            \draw[arrow] (p1d) |- (a220b);

            \draw[arrow] (a220) |- (p2aa2);
            \draw[arrow] (a310) |- (p2aa3);
            \draw[arrow] (p2aa2) -- (p2aa3);
            \draw[arrow] (p2aa3) -- (p2diff);
            \draw[arrow] (p2diff) -- (p2w);
            \draw[arrow] (p2w) -- (p2d);
            \draw[arrow] (p2w) |- (a210);
            \draw[arrow] (p2d) |- (a320);

            \draw[<-, line width=.8mm] (current bounding box.south west) 
            --node[sloped,above]{time} (current bounding box.north west);
        \end{tikzpicture}
        \caption{A timing diagram showing how the account balances can all three 
        be \$20 after exchanging concurrently \vscm{a1} and \vscm{a2} on one 
        side, \vscm{a2} and \vscm{a3} on the other side.}
        \label{3.43.1}
    \end{figure}

    \begin{figure}
        \centering
        \begin{tikzpicture}[>=Stealth]
            \matrix[time matrix] {
                &
                \node (a1) {a1}; &
                \node (a2) {a2}; &
                \node (a3) {a3}; & \\

                & \node[bank] (a130) {\$30}; &
                \node[bank] (a220) {\$20}; &
                \node[bank] (a310) {\$10}; & \\
                \node[action] (p1aa1) {Access balance a1: \$30}; &&& \\
                &&&& \node[action] (p2aa2) {Access balance a2: \$20}; \\
                \node[action] (p1aa2) {Access balance a2: \$20}; &&& \\
                &&&& \node[action] (p2aa3) {Access balance a3: \$10}; \\
                \node[action] (p1diff) {Difference: \$10}; &&& \\
                &&&& \node[action] (p2diff) {Difference: \$10}; \\
                \node[action] (p1w) {\vscm{((a1 'withdraw) 10)}}; &&& \\
                & \node[bank] (a120) {\$20}; &&& \\
                &&&& \node[action] (p2w1) {Access balance a2: \$20}; \\[+1.2em]
                &&&& \node[action] (p2w2) {New value for a2: \$10}; \\
                \node[action] (p1d) {\vscm{((a2 'deposit) 10)}}; &&& \\
                && \node[bank] (a220b) {\$20}; && \\
                &&&& \node[action] (p2w3) {set! balance for a2 to \$10}; \\
                && \node[bank] (a210) {\$10}; && \\
                &&&& \node[action] (p2d) {\vscm{((a3 'deposit) 10)}}; \\
                &&& \node[bank] (a320) {\$20}; & \\
            };

            \draw[arrow] (a130) -| (p1aa1);
            \draw[arrow] (a220) |- (p1aa2);
            \draw[arrow] (p1aa1) -- (p1aa2);
            \draw[arrow] (p1aa2) -- (p1diff);
            \draw[arrow] (p1diff) -- (p1w);
            \draw[arrow] (p1w) -- (p1d);
            \draw[arrow] (p1w) |- (a120);
            \draw[arrow] (p1d) |- (a220b);

            \draw[arrow] (a220) |- (p2aa2);
            \draw[arrow] (a220) |- (p2w1);
            \draw[arrow] (a310) |- (p2aa3);
            \draw[arrow] (p2aa2) -- (p2aa3);
            \draw[arrow] (p2aa3) -- (p2diff);
            \draw[arrow] (p2diff) -- (p2w1);
            \draw[arrow] (p2w1) -- (p2w2);
            \draw[arrow] (p2w2) -- (p2w3);
            \draw[arrow] (p2w3) -- (p2d);
            \draw[arrow] (p2w3) |- (a210);
            \draw[arrow] (p2d) |- (a320);

            \draw[<-, line width=.8mm] (current bounding box.south west) 
            --node[sloped,above]{time} (current bounding box.north west);
        \end{tikzpicture}
        \caption{A timing diagram showing how the sum of the balances in the 
        accounts is not preserved if the transactions on individual accounts are 
        not serialized.}
        \label{3.43.2}
    \end{figure}

    Since each exchange run individually exchanges the balances of two of the 
    accounts, if any number of exchanges happen sequentially the balances of the 
    accounts will still be \$10, \$20 and \$30 in some order.

    \autoref{3.43.1} shows how the account balances can be different than \$10, 
    \$20 and \$30 with the first version of the account-exchange program. The 
    \vscm{withdraw} and \vscm{deposit} procedures from each account are 
    serialized, so each of them is an atomic operation. Each exchange operation 
    removes an amount from an account and adds the same amount to another 
    account, and these operations are serialized, so the sum of the balances is 
    preserved.

    \autoref{3.43.2} shows a case where the sum of the balances of the accounts 
    is not preserved after exchanges between \vscm{a1} and \vscm{a2} on one 
    side, \vscm{a2} and \vscm{a3} on the other side. Compared to the version 
    from \autoref{3.43.1}, the only transaction for a single account that does 
    not happen as if it were serialized is \vscm{((a2 'withdraw) 10)}: the first 
    exchange procedure sets the account’s balance to \$20 before the second 
    procedure can set it to \$10, and the final sum is \$50 instead of \$60.
\end{exe}

\begin{exe}[3.44]
    Louis is wrong, there is no problem with Ben Bitdiddle’s procedure: at the 
    end of the transfer, \vscm{amount} has been withdrawn from 
    \vscm{from-account} and deposited on \vscm{to-account}, it does not matter 
    whether other procedures access the accounts in-between. The fundamental 
    difference with the exchange problem is that for the transfer the amount is 
    an argument to the procedure, so there are only two atomic operations, one 
    on each account. In the case of exchange there are two atomic operations for 
    each account: an access to the balance and then either a deposit or 
    a withdrawal.
\end{exe}

\begin{exe}[3.45]
    The problem with Louis’ reasoning is that when a procedure serialized with 
    an account’s serializer attempts to withdraw or deposit to that account, it 
    calls a procedure serialized with the same serializer and it gets stuck 
    forever waiting for the mutex it holds to be available. In the case of 
    \vscm{serialized-exchange}, it’ll wait forever while trying to execute 
    \linebreak
    \vscm{((account1 'withdraw) difference)}.
\end{exe}

\subsubsection{Implementing serializers}

\begin{exe}[3.46]
    \autoref{3.46fig} shows how the implementation of \vscm{test-and-set!} can 
    fail if two procedures access the cell and find its contents at false before 
    both set its contents to true.
    \begin{figure}
        \centering
        \begin{tikzpicture}[>=Stealth]
            \matrix[time matrix] {
                & \node (cell) {mutex cell}; & \\

                & \node[bank] (cfalse) {false}; & \\
                \node[action] (p1acc) {Access cell: false}; && \\
                && \node[action] (p2acc) {Access cell: false}; \\
                \node[action] (p1set) {set! cell to true}; && \\
                & \node[bank] (ctrue1) {true}; & \\
                && \node[action] (p2set) {set! cell to true}; \\
                & \node[bank] (ctrue2) {true}; & \\
            };

            \draw[arrow] (cfalse) -| (p1acc);
            \draw[arrow] (p1acc) -- (p1set);
            \draw[arrow] (p1set) |- (ctrue1);

            \draw[arrow] (cfalse) -| (p2acc);
            \draw[arrow] (p2acc) -- (p2set);
            \draw[arrow] (p2set) |- (ctrue2);

            \draw[<-, line width=.8mm] (current bounding box.south west) 
            --node[sloped,above]{time} (current bounding box.north west);
        \end{tikzpicture}
        \caption{A timing diagram showing how the mutex implementation can allow 
        to processes to acquire the mutex at the same time.}
        \label{3.46fig}
    \end{figure}
\end{exe}

\begin{exe}[3.47]
    \ \vspace{-20pt}
    \begin{enumerate}
        \item The following implementation of semaphores uses a mutex to guard 
            a variable holding the number of available accesses to the 
            semaphore:
            \scm{ch3/3.47a.scm}
        \item The following implementation uses a cell holding the number of 
            available accesses, and an atomic \vscm{test-and-set!} operation to 
            change the value of that cell:
            \scm{ch3/3.47b.scm}
    \end{enumerate}
\end{exe}

\subsubsection{Deadlock}

\begin{exe}[3.48]
    The \vscm{serialized-exchange} and \vscm{make-account-and-serializer} 
    procedures can be modified in the following way to incorporate the numbering 
    technique. It works because if two procedures need to access the same two 
    accounts, they will both attempt to access the same account first and one of 
    them will wait until the other one is done with no deadlock. More generally, 
    if one procedure P1 already holds a lock L1 and waits to acquire a lock L2 
    held by another procedure P2, we know that P2 won’t attempt to acquire L1, 
    otherwise it would have done so before acquiring L2, so the lock held by P1 
    can’t prevent P2 from completing.
    \scm{ch3/3.48.scm}
\end{exe}

\begin{exe}[3.49]
    If the resources to lock are not all known in advance, it’s of course 
    impossible to order the locks. For instance, let’s assume that we must 
    change a field in a row of a table in a database, and then find rows in 
    other tables that contain the new value of the field to update these rows. 
    (Not sure of a concrete example, but it’s the idea…)
\end{exe}

\section{Streams}

\begin{comp}
    In order to make the code in this section work with Gambit scheme, it’s 
    necessary to define \vscm{the-empty-stream} and \vscm{stream-null?}, as well 
    as the macros \vscm{delay} and \vscm{cons-stream}. This can be done with the 
    following:
    \scm{ch3/3.50pre.gambc.scm}
\end{comp}

\subsection{Streams Are Delayed Lists}

\begin{exe}[3.50]
    The generalized version of \vscm{stream-map} is:
    \scm{ch3/3.50.scm}
\end{exe}

\begin{exe}[3.51]
    After the first expression, the interpreter prints \vscm{0}. This is the 
    result of applying \vscm{show} to the first element of the stream in 
    \vscm{stream-map}, in \vscm{(cons-stream (proc (stream-car s)) ...)}.

    After the second expression, it prints \vscm{1 2 3 4 5 5} (one value per 
    line). Each call to \vscm{stream-cdr} on the result of \vscm{stream-map} 
    causes a call to \vscm{show} as the following value is evaluated. Then the 
    value returned by \vscm{stream-ref} is returned.

    After the third expression, it prints \vscm{6 7 7} (one value per line). 
    Since \vscm{delay} uses \vscm{memo-proc}, \vscm{show} is only called for the 
    elements of the stream not visited during the previous evaluation. Then the 
    value \vscm{7} is returned.
\end{exe}

\begin{exe}[3.52]
    Since \vscm{delay} uses \vscm{memo-proc}, \vscm{accum} is called only once 
    for each element of the enumerated interval, so the elements of \vscm{seq} 
    are the sums of successive integers: $1, 3, 6, 10, 15, ...$. Furthermore, 
    \vscm{sum} is equal to the sum of the integers from 1 to $n + 1$, where $n$ 
    is the maximum of the indices of the elements already visited in the stream 
    \vscm{seq}.

    After the definition of \vscm{seq}, the value of \vscm{sum} is 1 because 
    \vscm{accum} was applied to the first element of the enumeration by 
    \vscm{stream-map} ($n = 0$).

    The definition of \vscm{y} causes \vscm{stream-cdr} to be called on 
    \vscm{seq} until the first even element is found. This happens for the third 
    element of the stream interval, and then the value of \vscm{sum} is 6 ($n 
    = 2$).

    The definition of \vscm{y} causes \vscm{stream-cdr} to be called on 
    \vscm{seq} until the first multiple of 5 is found. This is the fourth 
    element of the stream, which is 10 ($n = 3$).

    The eighth even element of \vscm{seq} is 136, so after evaluationg
    \vscm{(stream-ref y 7)}, \vscm{sum} will be equal to 136, which is also the 
    printed response to the evaluation.

    The evaluation of \vscm{display-stream} causes the stream \vscm{seq} to be 
    fully evaluated, so at the end the value of \vscm{sum} is the last value of 
    that stream: 210. The evaluation of \vscm{(display-stream z)} displays the 
    elements of \vscm{seq} that are multiples of 5, followed by \vscm{done}, one 
    element per line:
    \vscm{10 15 45 55 105 120 190 210 done}.

    \vspace{\baselineskip}

    The responses would differ if \vscm{delay} were implemented without using 
    \vscm{memo-proc}. Since the result of \vscm{accum} depends on the value of 
    a variable that changes with every call to \vscm{accum}, the stream 
    \vscm{seq} would be completely different each time it is used. It becomes 
    a lot harder to reason about what \vscm{seq}, \vscm{sum}, \vscm{y}, \vscm{z} 
    represent since they don’t correspond to something clearly definable.
\end{exe}

\subsection{Infinite Streams}

\begin{exe}[3.53]
    The elements of this stream are the powers of 2.
\end{exe}

\begin{exe}[3.54]
    The procedure \vscm{mul-streams} and the stream \vscm{factorials} can be 
    defined as:
    \scm{ch3/3.54.scm}
    We use \vscm{(stream-cdr integers)} rather than \vscm{integers}, otherwise 
    the $n$th element would be $n!$ and not $(n + 1)!$.
\end{exe}

\begin{exe}[3.55]
    The procedure \vscm{partial-sums} can be defined as:
    \scm{ch3/3.55.scm}
\end{exe}

\begin{exe}[3.56]
    The required stream can be constructed as:
    \scm{ch3/3.56.scm}
\end{exe}

\begin{exe}[3.57]
    Only $n - 1$ additions are performed to compute the $n$th Fibonacci number 
    since the values already computed are not computed again.

    If \vscm{memo-proc} is not used, the values are recomputed every time they 
    are needed, so the number of additions is exponential.
\end{exe}

\begin{exe}[3.58]
    The given stream computes the expansion of the ratio of \vscm{num} and 
    \vscm{den} in basis \vscm{radix}. More precisely, if we call $n$, $d$ and 
    $b$ the values of \vscm{num}, \vscm{den} and \vscm{radix}, $q_i$ the $i$th 
    element of the stream, and $n_i$ the value of \vscm{num} during the $i$th 
    recursive call to \vscm{expand} (with $n = n_0$), we can prove by induction 
    that for any $k \geq 0$:
    \[
    n = \sum_{i = 0}^{k} \frac{q_i d}{b^{i + 1}} + \frac{n_{k + 1}}{b^{k + 1}}
    \]
    so by taking the limit when $k$ tends to $+\infty$:
    \[
	\frac{n}{d} = \sum_{i \geq 0} \frac{q_i}{b^{i + 1}}
    \]
    The streams \vscm{(expand 1 7 10)} and \vscm{(expand 3 8 10)} give the 
    decimal expansions of $\sfrac{1}{7}$ and $\sfrac{3}{8}$ respectively: in the 
    first case the elements are 1, 4, 2, 8, 5 and 7 repeating indefinitely, in 
    the second case the elements are 3, 7 and 5 followed by zeroes.
\end{exe}

\begin{exe}[3.59]
    \ \vspace{-20pt}
    \begin{enumerate}
        \item The procedure \vscm{integrate-series} can be written:
	    \scm{ch3/3.59a.scm}
        \item The series for sine and cosine can be defined with:
	    \scm{ch3/3.59b.scm}
    \end{enumerate}
\end{exe}

\begin{exe}[3.60]
    If we write the two power series to multiply as $S_1 = a_0 + x A_1$ and $S_2 
    = b_0 + x B_1$, where $A_1$ and $B_1$ are the power series represented by
    \vscm{(stream-cdr s1)} and \vscm{(stream-cdr s2)}, we have
    $S_1 S_2 = a_0 b_0 + x (b_0 A_1 + a_0 B_1 + x A_1 B_1)
    = a_0 b_0 + x (a_0 B_1 + A_1 S_2)$, so \vscm{mul-series} can be defined as:
    \scm{ch3/3.60.scm}
\end{exe}

\begin{exe}[3.61]
    The formula given in the text leads to the definition of 
    \vscm{invert-unit-series} in the following way:
    \scm{ch3/3.61.scm}
    I defined a local variable rather than calling recursively 
    \vscm{invert-unit-series}, otherwise the computation does not benefit from 
    the optimization provided by \vscm{memo-proc} and is a lot slower.
\end{exe}

\begin{exe}[3.62]
    If $F$ and $G$ are two power series with $G = c_0 + \sum_{i > 0} c_i x^i$ 
    and $c_0 \neq 0$, we can write $G = c_0 H$ where $H = \frac{1}{c_0} G$ is 
    a power series with a constant term equal to $1$. We have:
    \[
    \frac{F}{G} = \frac{F}{c_0 H} = \frac{1}{c_0} \times F \times \frac{1}{H}
    \]
    Since \vscm{invert-unit-series} can be used to compute the power series for 
    $\frac{1}{H}$, \vscm{div-series} can be defined as shown belown, and the 
    power series for tangent can be defined using $\tan x = \frac{\sin x}{\cos 
    x}$.
    \scm{ch3/3.62.scm}
\end{exe}

\subsection{Exploiting the Stream Paradigm}

\subsubsection{Formulating iterations as stream processes}

\begin{exe}[3.63]
    If we don’t use a local variable, each recursive call to \vscm{sqrt-stream} 
    produces a new stream, so if the $n$ first elements of the result have been 
    computed, to get the next element, the $n$ first elements are computed again 
    before the final mapping can be applied, so the time needed to compute the 
    $(n + 1)$-th element is at least twice the time needed to compute the $n$th 
    element, the time complexity is in $\Theta(2^n)$.

    With a local variable and \vscm{memo-proc}, the complexity is linear, but 
    without \vscm{memo-proc} the complexity would still be exponential since all 
    the previous elements of the stream must be recomputed to obtain the next 
    element.
\end{exe}

\begin{exe}[3.64]
    The procedure \vscm{stream-limit} can be defined as shown below, assuming 
    the stream is infinite or at least is guaranteed not to end before the 
    number is found:
    \scm{ch3/3.64.scm}
\end{exe}

\begin{exe}[3.65]
    Three sequences analogous to those defined for $\pi$ can be defined with:
    \scm{ch3/3.65.scm}
    As was the case for the approximations of $\pi$, the first sequence 
    converges slowly: with 10 terms, the value of $\ln 2$ is bound between $.63$ 
    and $.75$. The second sequence converges already more quickly: the first 10 
    terms give a value between $.6930$ and $.6933$. The third sequence converges 
    even more quickly: the first 10 terms give a correct value to 14 decimal 
    places.
\end{exe}

\subsubsection{Infinite streams of pairs}

\begin{exe}[3.66]
    Intuitively, since \vscm{interleave} produces a stream where half of the 
    elements come from the first stream and half from the second stream, about 
    one out of two elements of \vscm{int-pairs} comes from the first line, and 
    more generally, the interval between two pairs starting with $i$ is about 
    $2^i$.

    To give more precise results, let’s call $S_i$ the stream produced by 
    \vscm{pairs} with integers greater than or equal to $i$, so that 
    \vscm{int-pairs} is equal to $S_1$.
    Because of the order of the arguments of \vscm{interleave} in \vscm{pairs}, 
    the elements at index 0 and at odd indices of $S_i$ start with $i$. The 
    pairs with even indices $\geq 2$ are elements of $S_{i + 1}$.

    Using this, we can show that the index of $(i, i)$ in $S_1$ is equal to $2^i 
    - 2$, and the index of
    $(i, j)$ with $j > i$ is $(j - i) 2^{i} + 2^{i - 1} - 2$.

    \begin{proof}
        This is true for $i = 1$.

        Let’s assume that it’s true for some $i \geq 1$. We can prove the 
        formulas for $i + 1$ by using the two following facts: 1) the index of 
        $(i + 1, j)$ in $S_2$ is the same as the index of $(i, j - 1)$ in $S_1$ 
        since these streams are constructed in the same way, 2) the $k$th 
        element of $S_2$ has index $2k + 2$ in $S_1$.

        From the induction hypothesis, the index of $(i + 1, i + 1)$ in $S_2$ is 
        $2^i - 2$. Since the $k$th element of $S_2$ has index $2k + 2$ in $S_1$, 
        the index of $(i + 1, i + 1)$ is $S_1$ is $2(2^i - 2) + 2 = 2^{i + 1} 
        - 2$.

        In the same way, the index of $(i + 1, j)$ with $j > i + 1$ in $S_2$ is 
        equal to the index of $(i, j - 1)$ in $S_1$, that is, to
        $(j - i - 1) 2^{i} + 2^{i - 1} - 2$. So the index of $(i + 1, j)$ in 
        $S_1$ is equal to $2((j - i - 1) 2^{i} + 2^{i - 1} - 2) + 2 = (j 
        - i - 1)2^{i + 1} + 2^i - 2$, which is the result wanted.
    \end{proof}

    By applying this result, we find that the pair $(1, 100)$ has index 197, so 
    it is preceded by 197 pairs. The pair $(99, 100)$ has index $2^{99} + 2^{98} 
    - 2$, and the pair $(100, 100)$ has index $2^{100} - 2$.
\end{exe}

\begin{exe}[3.67]
    We can divide the stream \vscm{(all-pairs S T)} containing all pairs of 
    elements from the two streams into four parts: the first pair $(S_0, T_0)$, 
    the rest of the first line, the rest of the first column, and the stream
    \vscm{(all-pairs (stream-cdr S) (stream-cdr T))}. We only need to add the 
    stream corresponding to the rest of the first column to the previous 
    definition.
    \scm{ch3/3.67.scm}
\end{exe}

\begin{exe}[3.68]
    \label{3.68}
    Louis’ definition of \vscm{pairs} causes an infinite loop when it is called 
    with infinite streams because \vscm{interleave} is called directly, it is 
    not put in an argument to \vscm{cons-stream}, which uses delayed evaluation. 
    So the arguments of \vscm{interleave} are evaluated, which causes infinite 
    recursive calls to \vscm{pairs}.
\end{exe}

\begin{exe}[3.69]
    \label{3.69}
    The stream of triples can be generated similarly to the stream of pairs as 
    shown below. Once \vscm{triples} is defined, applying a filter is enough to 
    define a stream of all Pythagorean triples.
    \scm{ch3/3.69.scm}
\end{exe}

\begin{exe}[3.70]
    \label{3.70}
    The \vscm{merge-weighted} procedure is very similar to \vscm{merge}, except 
    that if multiple elements have the same weight, they are all kept, whereas 
    \vscm{merge} removed duplicates.
    \scm{ch3/3.70.scm}
    \begin{enumerate}
        \item The ordered pairs can be defined as follows:
            \scm{ch3/3.70a.scm}
        \item The required stream can be defined as:
            \scm{ch3/3.70b.scm}
    \end{enumerate}
\end{exe}

\begin{exe}[3.71]
    I used a procedure \vscm{group-by} that takes as arguments an infinite 
    stream and a test procedure \vscm{same-group?} that tests whether two 
    successive elements of the stream belong to the same group, and returns 
    a stream where the elements are grouped into lists according to the given 
    procedure. To find all Ramanujan number, we first generate the stream of 
    pairs of integers ordered by the sum of their cubes, then group the pairs 
    with the same cube sum, and keep only the groups with more than one element.
    \scm{ch3/3.71.scm}

    The 6 first Ramanujan numbers are 1729, 4104, 13832, 20683, 32832 and 39312. 
    The procedure given above returns them with their decompositions:
    \begin{cscm}
        > (print-n ramanujan 6)
        (1729 (1 12) (9 10))
        (4104 (2 16) (9 15))
        (13832 (2 24) (18 20))
        (20683 (10 27) (19 24))
        (32832 (4 32) (18 30))
        (39312 (2 34) (15 33))
    \end{cscm}
\end{exe}

\begin{exe}[3.72]
    Thanks to the definition of \vscm{group-by} in the previous exercise, the 
    stream can be defined by applying a few stream operations in a way very 
    similar to the definition of the stream of Ramanujan numbers.
    \scm{ch3/3.72.scm}
    The first 10 such numbers found are:
    \begin{cscm}
        > (print-n three-square-sums 10)
        (325 (1 18) (6 17) (10 15))
        (425 (5 20) (8 19) (13 16))
        (650 (5 25) (11 23) (17 19))
        (725 (7 26) (10 25) (14 23))
        (845 (2 29) (13 26) (19 22))
        (850 (3 29) (11 27) (15 25))
        (925 (5 30) (14 27) (21 22))
        (1025 (1 32) (8 31) (20 25))
        (1105 (4 33) (9 32) (12 31) (23 24))
        (1250 (5 35) (17 31) (25 25))
    \end{cscm}
\end{exe}

\subsubsection{Streams as signals}

\begin{exe}[3.73]
    The RC circuit can be modeled with the following procedure:
    \scm{ch3/3.73.scm}
\end{exe}

\begin{exe}[3.74]
    \ \vspace{-20pt}
    \begin{comp}
        To test the code from the book, let’s first define a procedure to 
        transform a list into a stream, as well as the 
        \vscm{sign-change-detector} procedure from the book. Note that because 
        of the way \vscm{make-zero-crossings} is defined, 
        \vscm{sign-change-detector} works backwards: it returns 1 when its first 
        argument is positive and the second is negative and vice-versa.
        \scm{ch3/3.74sup.scm}
    \end{comp}
    With the suggestion from the book, the stream of zero crossing can be 
    defined as:
    \scm{ch3/3.74.scm}
    However, it would be better to avoid adding an arbitrary initial value of 
    0 by defining \vscm{zero-crossings} instead in the following way:
    \scm{ch3/3.74b.scm}
\end{exe}

\begin{exe}[3.75]
    The “last-value” to use to compute the average should be the last value from 
    the \vscm{sense-data} stream, and the value to use to detect the sign change 
    should be the last average. Louis uses the last average for both. The 
    solution is to pass both the last value and the last average as arguments to 
    \vscm{zero-crossings}.
    \scm{ch3/3.75.scm}
\end{exe}

\begin{exe}[3.76]
    The \vscm{smooth} procedure can be written as shown below, which allows us 
    to redefine \vscm{make-zero-crossings} so that it takes it as an argument:
    \scm{ch3/3.76.scm}
\end{exe}

\subsection{Streams and Delayed Evaluation}

\begin{comp}
    The \vscm{solve} procedure does not work with Gambit Scheme, I used the 
    variation:
    \scm{ch3/3.77pre.gambc.scm}
\end{comp}

\begin{exe}[3.77]
    The \vscm{integral} procedure given in the exercise with a delayed 
    \vscm{integrand} argument becomes:
    \scm{ch3/3.77.scm}
\end{exe}

\begin{exe}[3.78]
    The \vscm{solve-2nd} procedure can be defined in the following way, using 
    \vscm{let} and \vscm{set!} instead of \vscm{define} so it works with Gambit 
    Scheme:
    \scm{ch3/3.78.scm}
\end{exe}

\begin{exe}[3.79]
    The generalization of \vscm{solve-2nd} is:
    \scm{ch3/3.79.scm}
\end{exe}

\begin{exe}[3.80]
    The procedure to model the circuit and the example of streams can be defined 
    as:
    \scm{ch3/3.80.scm}
\end{exe}

\subsection{Modularity of Functional Programs and Modularity of Objects}

\begin{exe}[3.81]
    We assume that the elements of the stream of requests are either the string 
    \vscm{generate} or a pair \vscm{(reset . new-value)} with the new value for 
    the seed of the random numbers. The generator can thus be written as:
    \scm{ch3/3.81.scm}
\end{exe}

\begin{exe}[3.82]
    We can rewrite Monte Carlo integration in terms of streams as shown below.
    \scm{ch3/3.82.scm}
\end{exe}