ch1.tex

\chapter{Building Abstractions with Procedures}

\section{The Elements of Programming}

\subsection{Expressions}

This subsection contains no exercises.

\subsection{Naming and the Environment}

This subsection contains no exercises.

\subsection{Evaluationg Combinations}

This subsection contains no exercises.

\subsection{Compound Procedures}

This subsection contains no exercises.

\subsection{The Substitution Model for Procedure Application}

This subsection contains no exercises.

\subsection{Conditional Expressions and Predicates}

\begin{exe}[1.1]
    Check with a scheme interpreter.
\end{exe}

\begin{exe}[1.2]
    A minimally indented version:
    \scm{ch1/1.02a.scm}
    A heavily indented version:
    \scm{ch1/1.02b.scm}
\end{exe}

\begin{exe}[1.3]
    \ \vspace{-20pt}
    \scm{ch1/1.03.scm}
\end{exe}

\begin{exe}[1.4]
    If $b > 0$, \vscm{(a-plus-abs-b a b)} returns $a + b$; otherwise it returns 
    $a - b$. In other words, \vscm{(a-plus-abs-b a b)} returns $a + |b|$.
\end{exe}

\begin{exe}[1.5]
    With applicative-order evaluation, the interpreter tries to evaluate 
    \vscm{(p)}, which results in an infinite loop, so the interpreter never 
    returns (or returns an error).

    With normal-order evaluation, the interpreter doesn't try to evaluate 
    \vscm{(p)} until it's really needed, but that never happens since
    \vscm{(= x 0)} returns true, so the call returns 0.
\end{exe}

\subsection{Example: Square Roots by Newton’s Method}

\begin{exe}[1.6]
    When Alyssa attempts to use this to compute square roots, the program never 
    returns.

    Explication: \vscm{new-if} is an ordinary procedure, so each time it is 
    called, the evaluator tries to evaluate all of its arguments. In particular, 
    each call to \vscm{sqrt-iter} will cause one more call to \vscm{sqrt-iter}, 
    whether \vscm{(good-enough? guess x)} returns true or not, so the evaluator 
    ends up in an infinite loop.
\end{exe}

\begin{exe}[1.7]
    \label{1.7}
    A possible solution:
    \scm{ch1/1.07.scm}

    Let's call $x$ the number whose root we want to compute.

    With the initial \vscm{good-enough?} test:
    \begin{itemize}
        \item If $x$ is very small, the difference between the guess and $x$ 
        becomes smaller than $0.001$ (or any number we would replace $0.001$ 
        with, for small enough numbers) while the guess is still several times 
        larger than $\sqrt{x}$, or even orders of magnitude away from it.
        \begin{example}
            \vscm{(sqrt 0.0001)} returns $0.03230844833048122$ instead of $0.01$ 
            because\linebreak
            \vscm{(abs (- (square 0.03230844833048122) 0.0001))} 
            returns\linebreak
            $9.438358335233747e-4$.
        \end{example}
    \item If $x$ is very large, the difference between the guess and $x$ will 
        always be found to be larger than $0.001$ (or any number we would 
        replace $0.001$ with, for large enough numbers) because
        ($x - \text{any number}$) can not be expressed to the precision required 
        to compare it to $0.001$, so the call never returns.
        \begin{example}
            \vscm{(sqrt 1e+129)} does not return, while \vscm{(sqrt 1e+128)} 
            returns a correct answer almost instantly\footnote{These values are 
            implementation-dependent.}.
        \end{example}
    \end{itemize}

    With the modified versions of \vscm{good-enough?} and \vscm{sqrt-iter}, the 
    above examples work.
\end{exe}

\begin{exe}[1.8]
    Here is a solution based on the solution of \autoref{1.7}.
    \scm{ch1/1.08.scm}
\end{exe}

\subsection{Procedures as Black-Box Abstractions}

This subsection contains no exercises.

\section{Procedures and the Processes They Generate}

\subsection{Linear Recursion and Iteration}

\begin{exe}[1.9]
    With the first procedure:
    \scm{ch1/1.09a.scm}

    With the second procedure:
    \scm{ch1/1.09b.scm}

    The first process is recursive, the second is iterative.
\end{exe}

\begin{exe}[1.10]
    Using the interpreter, we obtain $1024 = 2^{10}$ for \vscm{(A 1 10)}, and 
    $65536 = 2^{16}$ for \vscm{(A 2 4)} and \vscm{(A 3 3)}.

    By definition of the Ackermann function, \vscm{(A 0 n)}, i.e.
    \vscm{(f n)} computes $2n$.

    \medskip

    If $n > 0$, \vscm{(g n)} computes $2^n$.

    \begin{proof}
        By definition, \vscm{(g 1)} equals $2$, and for $n > 1$, \vscm{(A 1 n)} 
        equals \vscm{(A 0 (A 1 (- n 1)))}. Since \vscm{(A 0 n)} computes $2n$,
        the result follows by mathematical induction.
    \end{proof}

    \medskip

    If $n > 0$, \vscm{(h n)} computes $2 \uparrow \uparrow n$, that is, 
    $2^{2^{2^{…}}}$ with $n$ copies of $2$.

    \begin{proof}
        This is true for $n = 1$ by definition. For $n > 1$, \vscm{(A 2 n)} is 
        equal to\linebreak
        \vscm{(A 1 (A 2 (- n 1)))}. The result follows by mathematical induction 
        using the previous result.
    \end{proof}

    \medskip

    \begin{remark}
        \vscm{(A 3 3)} returns $2^{16} = 2^{2^{2^2}}$ as well. The recursion 
        beginning with \vscm{(A 3 n)} with\linebreak
        $n > 1$ gives \vscm{(A 2 (A 3 (- n 1)))}, so according to the previous 
        result, \vscm{(A 3 n)} is obtained from \vscm{(A 3 (- n 1))} by 
        computing $2^{2^{2^{…}}}$ with a tower of
        \vscm{(A 3 (- n 1))} 2s, so since \vscm{(A 3 1)} is $2$, \vscm{(A 3 2)} 
        is $2^2 = 4$, and \vscm{(A 3 3)} is $2^{2^{2^2}}$. The general value of 
        \vscm{(A 3 n)} can be noted $2 \uparrow \uparrow \uparrow n$, or $2 
        \uparrow^3 n$.

        This notation can be extended for all $m$s, so \vscm{(A m n)} computes 
        $2 \uparrow^m n$.
    \end{remark}
\end{exe}

\subsection{Tree Recursion}

\subsubsection{Example: Counting change}

\begin{exe}[1.11]
    Procedure computing $f$ by means of a recursive process :
    \scm{ch1/1.11a.scm}
    Procedure computing $f$ by means of an iterative process :
    \scm{ch1/1.11b.scm}
\end{exe}

\begin{exe}[1.12]
    Here is an example of a solution :
    \scm{ch1/1.12.scm}
    The argument $n$ is the line number from the top starting from $0$, and 
    $k$ is the column number from the left starting from $0$.
\end{exe}

\begin{exe}[1.13]
    \label{1.13}
    Let’s prove that for any $n \geq 0$, $\Fib(n) = \sfrac{\left( \phi^n 
    - \psi^n \right)}{\sqrt{5}}$, where $\phi = \sfrac{\left( 1 + \sqrt{5} 
    \right)}{2}$ and $\psi = \sfrac{\left( 1 - \sqrt{5} \right)}{2}$.

    It’s true for $n = 0$ and $n = 1$.

    Let’s assume that it’s true for any $k < n$. We have :

    \begin{align*}
        \Fib(n) &= \Fib(n - 1) + \Fib(n - 2) \\
        &= \frac{\phi^{n - 1} - \psi^{n - 1}}{\sqrt{5}} + \frac{\phi^{n - 2} 
        - \psi^{n - 2}}{\sqrt{5}} \\
        &= \frac{1}{\sqrt{5}}\left(\phi^{n - 2}\left(\phi + 1\right) - \psi^{n 
        - 2}\left(\psi + 1\right) \right) \\
    \end{align*}

    But $\phi$ and $\psi$ are the roots of the equation $x^2 - x - 1 = 0$, in 
    other words, $\phi^2 = \phi + 1$ and $\psi^2 = \psi + 1$, hence $\Fib(n) 
    = \sfrac{\left(\phi^n - \psi^n \right)}{\sqrt{5}}$.

    Furthermore, $ \lvert 1 - \sqrt{5} \rvert < 2 $, so for any $n \geq 0$, 
    $ \lvert 1 - \sqrt{5} \rvert^n < 2^n $, so dividing by $2^n$, we get 
    $ \lvert \psi^n \rvert < 1 $, and by dividing by $\sqrt{5}$, $ \lvert 
    \sfrac{\psi^n}{\sqrt{5}} \rvert < \sfrac{1}{\sqrt{5}} $. Since 
    $ \sfrac{1}{\sqrt{5}} < \sfrac{1}{2} $, we have $ \lvert 
    \sfrac{\psi^n}{\sqrt{5}} \rvert < \sfrac{1}{2} $ for any $n \geq 0$, which 
    means that $\Fib(n)$ is the closest integer to $\sfrac{\phi^n}{5}$.

\end{exe}

\subsection{Orders of Growth}

\begin{exe}[1.14]
    The space required is proportional to the maximum depth of the tree, so it 
    grows as $\Theta(n)$.

    For the time complexity, let’s use the mathematical notation $\text{cc}(n, 
    k)$ rather than \vscm{(cc n k)}.

    The time complexity for $\text{cc}(n, 1)$ grows as $\Theta(n)$.

    If we note $v$ the denomination of the $k$-th coin, we have:
    \begin{align*}
        \text{cc}(n, k) &= \text{cc}(n - v, k) + \text{cc}(n, k - 1) \\
                        &= \text{cc}(n - 2v, k) + 2\, \text{cc}(n, k - 1) \\
                        &= … \\
                        &= \text{cc}(n - \left\lceil \frac{n}{v} \right\rceil v, 
                        k) + \left\lceil \frac{n}{v} \right\rceil \text{cc}(n, 
                        k - 1)
    \end{align*}

    Since $n - \left\lceil \frac{n}{v} \right\rceil v \leq 0$, the time 
    complexity of $\text{cc}(n, k)$ is proportional to $n$ times the time 
    complexity of $\text{cc}(n, k - 1)$. As a consequence, the time complexity 
    for $5$ kinds of coins grows as $\Theta(n^5)$.
\end{exe}

\begin{exe}[1.15]
    \ \vspace{-20pt}
    \begin{enumerate}
        \item If the argument is greater than $0.1$, \vscm{p} is called once, 
            and the argument is divided by three. So the number of steps 
            required is the smallest integer $n$ such that $\sfrac{12.15}{3^n} 
            < 0.1$, or equivalently $121.5 < 3^n$. The smallest such $n$ is 5, 
            so \vscm{p} is called 5 times when \vscm{(sine 12.15)} is evaluated.
        \item By the same calculation as above, if $a > 0.1$, the number of 
            steps is the smallest $n$ such that $10 \, a < 3^n$. By taking the 
            logarithm, we get $\log(10) + \log(a) < n \log(3)$, so $n 
            = \left\lceil \sfrac{(\log(10) + \log(a))}{\log(3)} \right\rceil$.

            Therefore, the number of steps has order of growth 
            $\Theta(\log(n))$. The space required is proportional to the number 
            of steps, so its order of growth is the same.
    \end{enumerate}
\end{exe}

\subsection{Exponentiation}

\begin{exe}[1.16]
    A possible solution to compute exponentials in a logarithmic number of steps 
    iteratively:
    \scm{ch1/1.16.scm}
\end{exe}

\begin{exe}[1.17]
    A recursive process that multiplies two non-negative integers using 
    a logarithmic number of steps.
    \scm{ch1/1.17.scm}
\end{exe}

\begin{exe}[1.18]
    An iterative process that multiplies two non-negative integers using 
    a logarithmic number of steps.

    We keep a state variable $c$ such that $ab + c$ is constant at each call 
    of the inner function.
    \scm{ch1/1.18.scm}
\end{exe}

\begin{exe}[1.19]
    By calculation, we get $p' = p^2 + q^2$ and $q' = q^2 + 2pq$, so the 
    procedure becomes:
    \scm{ch1/1.19.scm}
\end{exe}

\subsection{Greatest Common Divisors}

\begin{exe}[1.20]
    With normal-order evaluation, \vscm{(gcd 206 40)} expands to
    \vscm{(gcd 40 (remainder 206 40))}, a \vscm{remainder} operation is 
    performed to test whether the remainder is null, then the expression expands 
    to \vscm{(gcd (remainder 206 40) (remainder 40 (remainder 206 40)))}. Two 
    \vscm{remainder} operations are performed to test whether the second 
    argument is null, and the expression expands to
    \begin{cscm}
        (gcd (remainder 40 (remainder 206 40))
             (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
    \end{cscm}
    Four new executions of \vscm{remainder} are necessary to determine that the 
    second argument is not null, and the expression becomes:
    \begin{cscm}
        (gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
             (remainder (remainder 40 (remainder 206 40))
                        (remainder (remainder 206 40)
                                   (remainder 40 (remainder 206 40)))))
    \end{cscm}
    Seven executions of \vscm{remainder} are necessary to determine that the 
    second argument is null, and the GCD is computed with four executions of 
    \vscm{remainder}. In total, 18 \vscm{remainder} operations are performed in 
    the normal-order evaluation.

    \bigskip

    With applicative-order evaluation, \vscm{(gcd 206 40)} expands to
    \vscm{(gcd 40 6)}, then to \vscm{(gcd 6 4)}, \vscm{(gcd 4 2)},
    \vscm{(gcd 2 0)} and to 2. One \vscm{remainder} operation is performed each 
    time \vscm{b} is not null, so four such operations are performed.
\end{exe}

\subsection{Example: Testing for Primality}

\begin{exe}[1.21]
    The smallest divisors of 199, 1999 and 19999 are 199, 1999 and 
    7 respectively.
\end{exe}

\begin{exe}[1.22]
    Example solution:
    \scm{ch1/1.22.scm}

    Nowadays, it’s necessary to use numbers much larger than those suggested in 
    the book to test the prediction about the timing, but the data support the 
    $\sqrt{n}$ prediction.

    The result is compatible with the notion that programs run in time 
    proportional to the number of steps required for the computation.
\end{exe}

\begin{exe}[1.23]
    The next procedure is:
    \scm{ch1/1.23a.scm}
    and \vscm{smallest-divisor} becomes:
    \scm{ch1/1.23b.scm}

    The modified version does not run twice as fast, but only about 1.7 times 
    as fast as the original version. This is because time is necessary to 
    apply the \vscm{next} procedure at each step.
\end{exe}

\begin{exe}[1.24]
    The only change needed is to replace \vscm{prime?} with \vscm{fast-prime?} 
    using an arbitrary number of tests (100 here) in \vscm{start-prime-test}.
    \scm{ch1/1.24.scm}

    When the number of digits is doubled, the time needed should be doubled as 
    well since the Fermat test has logarithmic growth. This is what is found 
    experimentally, though again, it’s necessary to use numbers much larger 
    than 1000 and 1,000,000 to get significant results.
\end{exe}

\begin{exe}[1.25]
    Alyssa’s procedure computes the correct result but it is much slower 
    because it deals with huge numbers, whereas by taking the remainder at 
    each recursion step, the numbers remain smaller than the tested number.
\end{exe}

\begin{exe}[1.26]
    If we use an explicit multiplication rather than calling square, 
    \vscm{(expmod base (/ exp 2) m)} is computed twice rather than once at 
    each recursive call with \vscm{exp} even, so that the process becomes 
    linear again.
\end{exe}

\begin{exe}[1.27]
    Here is an example of a procedure that tells whether $a^n$ is congruent to 
    $a$ modulo $n$ for every $a < n$:
    \scm{ch1/1.27.scm}

    It returns true for the given Carmichael numbers.
\end{exe}

\begin{exe}[1.28]
    A possible way to implement the Miller-Rabin test is:
    \scm{ch1/1.28.scm}
    It returns false on the Carmichael numbers listed in footnote 47.
\end{exe}

\section{Formulating Abstractions with Higher-Order Procedures}

\subsection{Procedures as Arguments}

\begin{exe}[1.29]
    Here is a solution:
    \scm{ch1/1.29.scm}
\end{exe}

\begin{exe}[1.30]
    A sum procedure generating an iterative process:
    \scm{ch1/1.30.scm}
\end{exe}

\begin{exe}[1.31]
    \ \vspace{-20pt}
    \begin{enumerate}
        \item Here is a procedure analogous to \vscm{sum} that computes 
            a product, generating a recursive process, and examples of its use 
            to define \vscm{factorial} and to compute approximations of $\pi$. 
            In the latter case, we use $\sfrac{(i - 1)(i + 1)}{i^2} = \sfrac{i^2 
            - 1}{i^2}$ as the general term.
            \scm{ch1/1.31a.scm}
        \item A \vscm{product} procedure generating an iterative process.
            \scm{ch1/1.31b.scm}
    \end{enumerate}
\end{exe}

\begin{exe}[1.32]
    \ \vspace{-20pt}
    \begin{enumerate}
        \item A recursive \vscm{accumulate} procedure and the definition of 
            \vscm{sum} and \vscm{product} using that procedure:
            \scm{ch1/1.32a.scm}
        \item An iterative version of \vscm{accumulate}:
            \scm{ch1/1.32b.scm}
    \end{enumerate}
\end{exe}

\begin{exe}[1.33]
    A \vscm{filtered-accumulate} procedure generating a recursive process:
    \scm{ch1/1.33.1.scm}
    A \vscm{filtered-accumulate} procedure generating an iterative process:
    \scm{ch1/1.33.2.scm}
    \begin{enumerate}
        \item Assuming \vscm{prime?} is already written, the sum of the squares 
            of the prime numbers in the interval $a$ to $b$ can be computed 
            with:
            \scm{ch1/1.33a.scm}
        \item The product of all positive integers less than $n$ that are 
            relatively prime to $n$ can be computed with:
            \scm{ch1/1.33b.scm}
    \end{enumerate}
\end{exe}

\subsection{Construction Procedures Using \vscm{Lambda}}

\begin{exe}[1.34]
    If we try to evaluate \vscm{(f f)}, we get an error saying that the operator 
    is not a procedure. The reason is that \vscm{(f f)} evaluates to
    \vscm{(f 2)}, which itself evaluates to \vscm{(2 2)}, and this operation is 
    impossible since 2 is not a procedure.
\end{exe}

\subsection{Procedures as General Methods}

\begin{exe}[1.35]
    We already noticed in \autoref{1.13} that $\phi^2 = \phi + 1$. By dividing 
    this equation by $\phi$, we get $\phi = 1 + \sfrac{1}{\phi}$.

    We can then compute $\phi$ with the command:
    \scm{ch1/1.35.scm}
\end{exe}

\begin{exe}[1.36]
    Modified version of \vscm{fixed-points}:
    \scm{ch1/1.36a.scm}
    We can find a solution to $x^x = 1000$ with, for instance, without average 
    damping:
    \scm{ch1/1.36b.scm}
    And with average damping:
    \scm{ch1/1.36c.scm}

    The former takes 35 steps while the latter takes 9 steps, so average damping 
    makes the search much faster here.
\end{exe}

\begin{exe}[1.37]
    \ \vspace{-20pt}
    \begin{enumerate}
        \item A procedure \vscm{cont-frac} generating an iterative process, 
            doing the computation starting from \vscm{k}:
            \scm{ch1/1.37a.scm}

            11 steps are necessary to get an approximation that is accurate to 
            4 decimal places.

        \item A procedure \vscm{cont-frac} generating a recursive process, doing 
            the computation starting from 1:
            \scm{ch1/1.37b.scm}
    \end{enumerate}
\end{exe}

\begin{exe}[1.38]
    The following procedure computes an approximation of $e$ using a $k$-term 
    finite continued fraction.
    \scm{ch1/1.38.scm}
\end{exe}

\begin{exe}[1.39]
    A possible solution for \vscm{(tan-cf x k)}:
    \scm{ch1/1.39.scm}
\end{exe}

\subsection{Procedures as Returned Values}

\begin{exe}[1.40]
    The procedure \vscm{cubic} is:
    \scm{ch1/1.40.scm}
\end{exe}

\begin{exe}[1.41]
    The procedure \vscm{double}:
    \scm{ch1/1.41.scm}

    \vscm{(double double)} is a procedure that takes a procedure of one argument 
    as argument and returns a procedure that applies the original procedure four 
    times.

    \vscm{((double (double double)) f)} evaluates to
    \vscm{((double double) ((double double) f))}, so it returns a procedures 
    that applies \vscm{f} $4 \times 4 = 16$ times.

    So the value returned by \vscm{(((double (double double)) inc) 5)} is 21.
\end{exe}

\begin{exe}[1.42]
    Here is a procedure \vscm{compose}:
    \scm{ch1/1.42.scm}
\end{exe}

\begin{exe}[1.43]
    \label{1.43}
    A solution generationg a recursive process:
    \scm{ch1/1.43a.scm}

    A solution generationg an iterative process:
    \scm{ch1/1.43b.scm}
\end{exe}

\begin{exe}[1.44]
    A possible solution is:
    \scm{ch1/1.44.scm}

    The $n$-fold smoothed function of a function \vscm{f} can be obtained with
    \vscm{((repeated smooth n) f)}.
\end{exe}

\begin{exe}[1.45]
    Experimentally, we find that the number of average dampings necessary to 
    compute $n$th roots in this way is $\lfloor \log n \rfloor$, so the 
    procedure to compute $n$th roots is:
    \scm{ch1/1.45.scm}
\end{exe}

\begin{exe}[1.46]
    A solution for \vscm{iterative-improve}:
    \scm{ch1/1.46a.scm}

    The \vscm{sqrt} procedure of \secref{1.1.7} becomes:
    \scm{ch1/1.46b.scm}

    The \vscm{fixed-point} procedure of 
    \secref[Finding-fixed-points-of-functions]{1.3.3} becomes:
    \scm{ch1/1.46c.scm}
\end{exe}

% vim:filetype=tex:set expandtab