SICP-Solutions.tex

\documentclass{scrreprt}

% Language-specific settings
\usepackage{polyglossia}
\setdefaultlanguage{american}

% Fonts
\usepackage{fontspec,microtype}
\setmainfont{Linux Libertine O}
\setsansfont{Linux Libertine O}
\setmonofont[Scale=MatchLowercase]{Fira Code}

% Hyperlinks
\usepackage{xcolor}
\definecolor{darkblue}{rgb}{0,0,0.5}
\definecolor{darkgreen}{rgb}{0,0.3,0}
\usepackage[unicode,
pdftitle={Solutions to Structure and Interpretation of Computer Programs},
pdfauthor={Fabienne Ducroquet},
urlcolor=darkblue,
linkcolor=darkgreen,
breaklinks,
colorlinks]{hyperref}

% Headers
\usepackage{fancyhdr}
\pagestyle{fancy}
\fancyhead[RO,LE]{\thepage}
\fancyhead[LO]{\rightmark}
\fancyhead[RE]{\leftmark}

% Source code highlighting
\usepackage{minted}
\newminted[cscm]{scheme}{autogobble,style=lovelace}
\newmintedfile[scm]{scheme}{style=lovelace}
\newmintinline[vscm]{scheme}{style=bw}

% Show subsubsections in the table of contents.
\setcounter{tocdepth}{4}
% Show a less detailed table of contents first.
\usepackage{shorttoc}

% External links to parts of the text on sarabander.github.io.
\usepackage{xstring,xifthen}
% \secref{<sectionnumber>} links to the given section or subsection.
% \secref[<anchor>]{<sectionnumber>} links to the anchor in the given section, 
% and still shows “section <sectionnumber>” as the link text.
\newcommand*\secref[2][]{%
    \StrCut[2]{#2}{.}{\sectionpart}{\rest}%
    \StrSubstitute{\sectionpart}{.}{_002e}[\pagepart]%
    \ifthenelse{\isempty{#1}}%
	{\StrSubstitute{#2}{.}{_002e}[\anchorpart]%
	 \href{https://sarabander.github.io/sicp/html/\pagepart.xhtml\#g_t\anchorpart}{section~#2}}%
	{\href{https://sarabander.github.io/sicp/html/\pagepart.xhtml\##1}{section~#2}}
}

% Use letters in enumerate.
\usepackage{enumitem}
\setenumerate[0]{label=\alph*.}

% Theorem environments
\usepackage{amssymb,amsmath,amsthm}
\newtheoremstyle{example}{}{}{}{}{\itshape}{:}{ }
{\thmname{#1}\thmnumber{ #2}\thmnote{ (#3)}}
\theoremstyle{example}
\newtheorem*{example}{Example}

\newtheoremstyle{remark}{}{}{}{}{\bfseries}{.}{ }
{\thmname{#1}\thmnumber{ #2}\thmnote{ (#3)}}
\theoremstyle{remark}
\newtheorem*{remark}{Remark}

\newtheoremstyle{comp}{}{}{\small}{}{\itshape}{:}{\newline}
{\thmname{#1}\thmnumber{ #2}\thmnote{ (#3)}}
\theoremstyle{comp}
\newtheorem*{comp}{Complement}

\newtheoremstyle{sicp-exe}{}{}{}{-12pt}{\bfseries}{}{\newline}
{\href{https://sarabander.github.io/sicp/html/\thechapter\_002e\arabic{section}.xhtml\#Exercise-\thechapter\_002e\arabic{exeaux}}
{\thmname{#1}\thmnumber{ #2}\thmnote{ (#3)}}}
\theoremstyle{sicp-exe}
\newtheorem{exeaux}{Exercise}[chapter]

% For hyperref's autoref.
\newcommand\exeauxautorefname{exercise}

% Include the exercises in the table of contents.
\NewDocumentEnvironment{exe}{o}
{\IfNoValueTF{#1}
    {\exeaux\addcontentsline{toc}{paragraph}%
        {Exercise}}
    {\exeaux\addcontentsline{toc}{paragraph}%
        {Exercise #1}}%
        \ignorespaces}
{\endexeaux}

% For inline fractions
\usepackage{xfrac}

% For Fibonacci numbers.
\DeclareMathOperator{\Fib}{Fib}

% For tables.
\usepackage{tabls, array, longtable}

% For exercise 2.24, and some exercises in chapter 3
\usepackage{tikz}
\usetikzlibrary{positioning, arrows.meta, calc, fit, matrix, backgrounds, 
decorations.markings, shapes.misc, shapes.geometric}
\newcommand*\var[2]{%
    \newlength{#1}
    \setlength{#1}{#2}
}

% Definitions for the box-and-pointer diagrams.
\var{\boxsize}{2em}
\var{\round}{3pt}

\tikzset{
    box/.style={
        minimum size = \boxsize,
        rectangle,
        rounded corners=\round,
        draw,
        fill=brown!15,
    },
    struct name/.style={
        minimum height=\boxsize,
    },
    car/.style={
        minimum size = \boxsize,
        append after command={
        \pgfextra
        \draw[sharp corners,fill=brown!15]
            (\tikzlastnode.south)
            -| (\tikzlastnode.east)
            |- (\tikzlastnode.north)
            [rounded corners=\round]
            -| (\tikzlastnode.west)
            |- (\tikzlastnode.south east);
        \endpgfextra},
    },
    cdr/.style={
        minimum size = \boxsize,
        append after command={
        \pgfextra
            \draw[sharp corners,fill=brown!15] (\tikzlastnode.south)
                -| (\tikzlastnode.west) |- (\tikzlastnode.north)
                [rounded corners=\round] -| (\tikzlastnode.east)
                |- (\tikzlastnode.south west);
        \endpgfextra},
    },
    cell matrix/.style={
        row sep = 1.2\boxsize,
        column sep = {\boxsize,between origins}
    },
    box and pointer/.style={
        very thick,
        font = \ttfamily,
        decoration = {markings,
            mark = at position 0 with { \fill circle (3pt); }
        },
    },
    pointer/.style = {
        -Stealth
    },
    box pointer/.style = {
        pointer,
        postaction = decorate
    },
    nil/.style = {
        Triangle Cap[]-,
        shorten >=.8pt,
    }
}

\newcommand*\nil[1]{
    \draw[nil] (#1.south west) -- (#1.north east);
}
\newcommand*\link[2]{
    \draw[box pointer] (#1.base) -- (#2);
}
% Box-and-pointer end.

% Tikz styles and commands for the environments of section 3.2.
\var{\nametoenv}{4mm}
\tikzset{
    env/.style={
        rectangle,
        rounded corners=2pt,
        % border
        very thick,
        draw=teal!80!black,
        % filling
        fill=teal!10,
        inner sep = 2mm,
        font=\ttfamily\small,
        align=left,
    },
    global env/.style={
        env,
        align=left,
        inner xsep=1ex,
        text width=13cm-2*\pgfkeysvalueof{/pgf/inner xsep},
        minimum width=13cm,
        minimum height=1.5cm
    },
    code/.style={
        align=left,
        font=\ttfamily\small,
    }
}

\var{\circleradius}{3mm}
\var{\smallcircleradius}{.8mm}
\newcommand*\pointer[1]{
    \draw (#1) circle (\circleradius);
    \filldraw (#1) circle (\smallcircleradius);
}
\newcommand*\procedure[3]{
    \coordinate[left=\circleradius of #1]  (#2);
    \coordinate[right=\circleradius of #1]  (#3);
    \pointer{#2}
    \pointer{#3}
}
% Environments end.

% Settings for timing diagrams in section 3.4.
\tikzset{
    bank/.style={
        circle,
        draw,
        minimum size=1.2cm,
        fill=orange!10,
    },
    action/.style={
        rounded rectangle,
        draw,
        minimum height=1.5em,
        fill=blue!5,
    },
    time matrix/.style={
        column sep=1em,
    },
    arrow/.style={
        rounded corners=10pt,
        thick,
        ->,
    },
}

% Settings for the data-path and controller diagrams in section 5.1.
\var{\regheight}{1cm}
\var{\push}{1.5ex}
\tikzset{
    % Node matrix
    data matrix/.style={
        column sep=1.5em,
        row sep=2.5em,
        nodes = { anchor = center, align = center },
    },
    controller matrix/.style={
        data matrix,
        column sep = 3em,
    },
    % Nodes
    data/.style={
        draw,
        thick,
        rounded corners=2pt,
        minimum height=\regheight,
    },
    reg/.style={
        data,
        rectangle,
        inner xsep=.5cm,
        fill=gray!12!blue!5,
    },
    const/.style={
        data,
        regular polygon,
        regular polygon sides=3,
        fill=gray!12!green!5,
        minimum height=1.7\regheight,
    },
    op/.style={
        data,
        trapezium,
        trapezium left angle=120,
        trapezium right angle=120,
        fill=pink!22!yellow!20
    },
    test/.style={
        data,
        circle,
        fill=gray!12!pink!15,
    },
    % Controller diagrams
    cio/.style={
        thick,
        rounded corners=2pt,
    },
    ctest/.style={
        cio,
        draw,
        inner xsep=.4cm,
        diamond,
        fill=gray!12!pink!15,
    },
    cbutton/.style={
        cio,
        draw,
        inner xsep=.5cm,
        rectangle,
        fill=gray!12!blue!5,
        minimum height=\regheight,
    },
    % Paths
    path/.style={
        thick,
        rounded corners=3pt,
    },
    button/.style={
        path,
        decoration = {markings,
            mark = at position #1 with {
                \fill[white] circle (.7071\push);
                \draw[-] ++(-.5\push, -.5\push) -- ++(\push, \push);
                \draw[-] ++(-.5\push, .5\push) -- ++(\push, -\push);
                \clip[draw] circle (.7071\push); }
        },
        postaction = decorate,
        ->,
        font=\ttfamily,
    },
    arg/.style={
        path,
        ->,
    },
    flow/.style={
        arg,
    },
}

\title{Solutions to Structure and Interpretation of Computer Programs}
\author{Fabienne \textsc{Ducroquet}}

\begin{document}

\maketitle

\pdfbookmark[1]{Short Contents}{shorttoc}
\shorttoc{Short Contents}{1}

\clearpage
\pdfbookmark[1]{\contentsname}{toc}
\tableofcontents

\chapter*{Introduction}

Solutions to most of the exercises of \emph{Structure and Interpretation of 
Computer Programs}, second edition, by Harold \textsc{Abelson} and Gerald Jay 
\textsc{Sussman} with Julie \textsc{Sussman}.

The answers to these exercises have been tested with the Scheme interpreter from 
\href{http://gambitscheme.org}{Gambit Scheme}, at the exception of the exercises 
from \secref{2.2.4} about the picture language, which have been written with 
\href{http://racket-lang.org}{Racket}, using the \vscm{graphics.ss} library.

\include{ch1}
\include{ch2}
\include{ch3}
\include{ch4}
\include{ch5}

\end{document}