SICP has been a great classic of computer science for more than two decades and is likely to remain so for many more. It’s reputation has grown throughout the 90s and continued to do so ‘posthumously’: the 6.001 course (which SICP served as the textbook of) is now a Python oriented course to accommodate shifting computing trends. SICP’s broad strokes remain as vibrant as the day it was written however. The real soul of this book is in it’s exercises: a powerful graphics language, a computer algebra system, a Scheme and “JIT” evaluator, a Prolog-like langauge and more. This expansive coverage of so many topics of computing spawned a long tradition of hackers studying it and writing solutions to it’s exercises.

An exhaustive reading of the book was unlikely for it’s target audience. SICP contains statements and source code that are redundant or ambiguous. Asking readers to consider code and structures whose details are described in principle, only later introducing their implementation. This pedagogical approach is maybe more sensible in the lecture hall, but is inefficient for the enthusiast.

SICP makes it your responsibility to learn what the book has to teach, and part of that duty is ensuring you’ll actually finish it by eliminating the details like dredging it’s contents to clarify a remark or realizing in hindsight that a few minutes when starting a chapter could’ve saved hours down the road.

If you get absolutely stuck, this repository also contains unique solutions to almost all of the exercises in Guile & PLT Scheme.

If you are interested in exploit writing, assembly or reverse engineering “proper” you can also check out my ”Practical Reverse Engineering w/ x86 and the Windows Kernel” study guide and solutions as well.

Although the original is available online, I’d recommend you strip down to the texinfo basics or gear up to a fully-featured experience on the web.

• Sara Bander’s SICP (Web)
• My Own Instructions (Emacs/Texinfo)

SICP can be more than didactic, it can be fun. The easiest way to do this is to have a great and pain free environment and REPL. I couldn’t imagine doing it with anything except Emacs. If you are a vim user, you can be at home in Emacs too.

SICP recommends MIT Scheme itself, however many readers since have used various Schemes, Lisps and languages pretending to be either. I’ve seen the following used and have tried to approximate their fitness for the task with some features I’ve found useful:

• Object system is not requried but can save you lots of time
• Being able to redefine a function in the same file is extremely useful in doing SICP.
• A few subchapters of Chapter 3 require a ‘real’ concurrency system in order to tell if you are doing the right things
• Several chapters more-or-less require mutable lists. Languages like Racket support mutable lists but use different method names and so will require you rewrite some code from the book.
• Some chapters, particularly those dealing with changes to the evaluator, are made much easier with the introduction of tests beyond assert.

I’ve left out two very popular choices: Common Lisp and Chicken Scheme, both I’ve heard are servicable.

Some online commentators have described SICP as stressing homoiconicicity, but if such implicit emphasis exists I couldn’t detect any (although the concept itself is referenced obliquely).

It is completely possible, if unhinged, to entirely do SICP in a language like Javascript or Ruby. I personally have reimplemented several challenges in JS and did get a dash of enlightenment that is usually very remote in Javascript (as well as learning something about JS that few JS textbooks teach).

Chapter 4’s implementation would be the first major hurdle for an nonlisp effort, fortunately Martin Henz has rewritten virtually the entire book to accommodate Javascript. Others have used techniques solely from an earlier chapters to write Sexp parsers to write a Scheme interpreter inside JS.

All of this carries the risk of getting completely different message than the book intended to convey.

Caveat Emptor.

If you’ve got experience programming in any functional programming language, this chapter will be pretty straitforward for you.

Even if you feel like the foundational material is old news to your, there are many numerical routines that you might be exposed to for the first time here.

A quick review:

• Implementing loops with recursive functions
• car/cdr/cons and other lisp list manipulation functions
• Some ‘highlight’ results from Computability theory (Ackermann’s function et al)
• Numerous Monte Carlo methods for approximating PI
• A Change Counting “machine”
• Euclid’s method for greatest common denominator
• High Level Functions
• Fermat’s Triangle
• Define, convert and calculate fixed points of lots of common functions
• Convert reals to rationals
• Approximate trigonometric functions

The chapter covers a lot of ground and doesn’t stay put in any one place for long. It’s highly rewarding and warmed me up to the rest of the book.

Some things covered include

• Lambda calculus
• Symbolic Computation & computer algebra systems with automatic integration & differentiation
• Encoding, Decoding and all around learning everything about Huffman Trees from the ground up
• The universality of the (list) datastructure in Lisp
• Dynamic Programming and hierarchical data structures
• Different ways to achieve language features like type-dispatch, message passing and inheritance

This book starts to give you a few nuggets of profound realization that the book is known for. It gets even better.

This chapter is unusual. It’s the least and the most important for practice of programming at large. The chapter justifies and presents simplified summaries of the implementation details of important programming language features and why they are useful.

There are only 4 exercises, so you can mostly relax and focus on the content, although both 2.73 and 2.75 show up later.

This chapter is the beginning of the end of standard computing textbook and the beginning of SICP. If you are already a programmer, Chapter 3 presents some huge temptations to skip content, the first paragraphs of some chapters give the impression of covering what seems like already well-worn ground as a programmer - the content of the chapters differ wildly from whats “on the tin”.

Even if you are familiar, SICP has something of a reputation for taking the well-worn concepts and turning them inside out to expose their “true” structure [fn:2].

An important tip for chapter 3 is DO NOT USE A LANGUAGE WITHOUT MUTABLE LISTS: If you are working with languages without convienent mutable data: I started out with Racket but was forced to rewrite my work after realizing that Racket’s mlists were not going to cut it for a chapter focused on the use and danger of mutable structures.

Another important consideration is the parallel programming facilities of your language, the book demands a true concurrency environemtn in order for some exercises and examples to work right.

The center of 3.34 is the constraint solver. Following the books implementation is slower but does remove any function-to-function mapping confusion. On the other hand, writing your own saves you some time but requires a bit more non-SICP effort.

The book implements the primary classes of the constraint-solver as straitforward Lisp functions with closures. Classes let you solve exercises faster, write fewer lines and be more satisfied with your final result.

The following are example base-classes for the primary classes along with their entire implementation, which allow method introduced later later in the chapter such as process-new-value and process-forget-value to share implementation details regardless of if they are operating on an adder or multiplier.

Implementation

(define-class <constraint> ()
  (lhs #:getter lhs
       #:init-keyword #:lhs)
  (rhs #:getter rhs
       #:init-keyword #:rhs)
  (total #:getter total
         #:init-keyword #:total)
  (operator #:getter constraint-operator)
  (inverse-operator #:getter constraint-inv-operator))

Implementation

(define-class <connector> ()
  (value #:init-value #f
         #:accessor connector-value
         #:setter set-connector-value)

  (informant #:init-value #f
             #:accessor informant
             #:setter set-informant)

  (constraints #:accessor constraints
               #:setter set-constraints
               #:init-form '()))

(define (make-connector)
  (make <connector>))

Implementation

(define-class <probe> (<constraint>)
  (name #:getter name
        #:setter set-name
        #:init-keyword #:name)
  (connector #:getter connector
             #:setter set-connector
             #:init-keyword #:connector))

(define (probe name connector)
  (let ((cs (make <probe> #:name name #:connector connector)))
    (connect connector cs) cs))

This chapter centers around the creation of a number of Scheme evaluators and is widely regarded as the most substantial chapter. The regularity with which it revises it’s own ideas make a testing framework and toolbelt a profitable use of your time.

If you’ve chosen a language that stresses immutability (like Racket or Clojure) you’ll have a fair amount of extra work ahead of you - The default evaluator uses a stack that is manipulated with the use of set!.

Don’t take my word on it though:

I’m close the finishing the last major chunk of the book. Working with two colleagues for around two hours a week, its taken us nearly a year to get this far. Of course, we did every exercise, and lost a lot of time trying to work around incompatibilities between standard Scheme and the interesting corners of DrScheme [now DrRacket - mcons, I’m looking at you]. Now we use mit-scheme and I wish we had done so from the very beginning.

I don’t think the book is perfect. I found the structure of Chapter 4, where a Scheme interpreter is built, confusing and irritating. The exercises are interspersed with the text in a way that doesn’t allow you to test any of your solutions unless you read ahead to get more infrastructure. This seems deeply unREPLy to me. Once I had typed in enough of the supporting code to actually run my proposed solutions, and pulled some hair out debugging my broken code, I had some marvellous moments of epiphany. That Ahah! is what maks [sic] the book’s reputation, and what makes the effort worthwhile. But it could have been better.

You’ll accomplish the following here:

• Simple Evaluator
  • Implement a variable-only ’stack’ without stored function pointers.
  • Implement Type-Dispatching Evaluator
  • Implement all major features of scheme used thus far
    • Various forms of let
    • letrec
    • cond
    • Predicates
    • etc.
  • Simultaneous vs. Ordered define
  • The Implementation of Closures
• Just-in-Time Interpreter/Compiler (the ‘analyzer’)
  • Challenges of a JIT
• Lazy Evaluator
  • Differences between lazy variables and a lazy interpreter
  • Relationship to the promise functions force and delay
  • Build a model of side-effects in lazy (or otherwise) evaluators
  • Implementation and use of ’thunks’
  • Permitting choice by adding lazy features to basic eval
• “Nondeterministic” & Logic Evaluator
  • Apply our earlier DFS with backtracking knowledge to build logic solvers
  • Implement a system of closures for tracking logic unification state
  • Understanding rule-oriented (as opposed to procedure-oriented) computing
  • Simplify problems to their essential logical form (and solve them)
  • Implementation of ‘Pattern Matching’ ala Erlang
  • A “true” parser
    • Specify a grammar for natural language
    • …and then writing something that emits all possible sentences
  • Use a random evaluator to explore choices in a truly nondeterministic fashion

Some evaluator exercises occur prior to their implementation, most frequently taking the following form:

1. Talk about the motivation and abstract concepts employed by an evaluator
2. Discuss Implementation
3. Exercises asking for implementation of various features
4. Actual scheme code defining the implementation

Instead of following the book linearly, I think that having a working implementation is extremely important throughout the book, so I’d recommend you include the entire evaluator prior to completing exercises related to it. The Complete Code from SICP 2/e is available and can be used directly if you are using a mainline scheme distribution.

Starting with a testing strategy is essential to preserving sanity here; I recommend using the input → result REPL ‘dialogues’ listed in the text to ensure that you are conforming to the features that the authors expect you to use in the coming exercises.

The default Guile test runner will output a .log file to your current directory instead of printing errors to stdout. This is an example test-runner that allows for more immediate testing.

(use-modules (srfi srfi-64))
(define (sicp-evaluator-runner)
  (let* ((runner (test-runner-null))
         (num-passed 0)
         (num-failed 0))
    (test-runner-on-test-end! runner
      (lambda (runner)
        (case (test-result-kind runner)
          ((pass xpass) (set! num-passed (+ num-passed 1)))
          ((fail xfail)
           (begin
             (let
                 ((rez (test-result-alist runner)))
               (format #t
                       "~a::~a\n Expected Value: ~a | Actual Value: ~a\n Error: ~a\n Form: ~a\n"
                       (assoc-ref rez 'source-file)
                       (assoc-ref rez 'source-line)
                       (assoc-ref rez 'expected-value)
                       (assoc-ref rez 'actual-value)
                       (assoc-ref rez 'actual-error)
                       (assoc-ref rez 'source-form))
               (set! num-failed (+ num-failed 1)))))
          (else #t))))
    (test-runner-on-final! runner
      (lambda (runner)
        (format #t "Passed: ~d || Failed: ~d.~%"
                num-passed num-failed)))
    runner))

(test-runner-factory
 (lambda () (sicp-evaluator-runner)))

This simple macro allows you to directly extract the expected/result pairs from the REPL excerpts.

 ;; Standard Evaluator Tests
(define-syntax test-eval
  (syntax-rules (=> test-environment test-equal)
    ((test-eval expr =>)
     (syntax-error "no expect statement"))
    ((test-eval expr => expect)
     (test-eqv  expect (test-evaluator 'expr test-environment)))
    ((test-eval expr expect)
     (test-eqv  expect (test-evaluator 'expr test-environment)))))

Now just add tests! The next section of this guide will show you how to automatically run tests at sensible points as part of the driver-loop.

(test-begin "Tests") ; Begin our tests
(test-begin "Evaluator") ; Begin evaluator tests
(test-begin "Basic") ; The basic (4.1) evaluator
(define test-environment (setup-environment)) ; Initialize the test environment
(define test-evaluator eval) ; Set the evaluator you wish to use

;; You can choose to use `=>' or not
(test-eval (and 1 2) => 2)

(test-eval
 (let fib-iter ((a 1) (b 0) (count 4))
   (if (= count 0) b
       (fib-iter (+ a b) a (- count 1))))
 => 3)

;; cleanup
(set! test-environment '())

(test-end "Basic")
(test-end "Evaluator")
(test-end "Tests")

Features common to

• An evaluator function driven by a switch statement
• An application function that extends the frame
• A driver loop that makes both accessible in the form of a REPL

Exercise 4.3 asks you to implement a type-dispatch scheme for the base evaluator, allowing you to incrementally introduce functionality rather than rewrite eval with each new feature. This turns out to be very useful and I wrote all my evaluators in this style.

The concept is demonstrated here:

(define-class <dispatch-table> ()
  (method-table #:init-value  (make-hash-table)
                #:getter      method-table))

(define (table-ordinal op type)
  (let ((opstr  (symbol->string op))
        (typestr (symbol->string type)))
    (string-append opstr "/" typestr)))

(define-method (get (dt <dispatch-table>) op type)
  (if (and (symbol? op) (symbol? type))
      (hash-ref (method-table dt) (table-ordinal op type))
      #f))

(define-method (put (dt <dispatch-table>) op type item)
  (hash-set! (method-table dt) (table-ordinal op type) item))

(define dispatch-tt (make <dispatch-table>))

(define (install-procedure p)
  "Install a procedure to the base evaluator"
  (put dispatch-tt 'eval ; instead of 'eval
                   (car p) 
                   (cadr p))

...

(install-procedure `(and ,eval-and))

(install-procedure `(let* ,(λ (exp env) (zeval (let*->nested-lets exp) env))))

(install-procedure `(undefine ,eval-undefinition))

(install-procedure `(while ,(λ (exp env) (zeval (make-while exp) env))))

Just as you dispatched a procedure specific to an evaluator above, you can do the same with the driver-loop implementation provided to each evaluator.

1. You’ll want to be able to quickly switch the evaluator invoked by driver-loop as you progress through the chapter and later chapters have a radically different loop.
2. Geiser is a very popular scheme integration module for Emacs Lisp that you will probably use. Like many IDE-integrated IDE’s it doesn’t deal well with a program that requests user input on stdin.
3. You can share more code, even between radically different implementations.

My approach is simple - add an entry to a table of driver-loop implementations which are chosen at runtime.

;; This function is what actually gets called to invoke your evaluator's REPL
(define (driver-loop evaluator)
  ((get dispatch-tt 'driver-loop evaluator)))

(define (install-driver-loop evaluator fn)
  "Install a new `driver-loop' REPL"
  (put dispatch-tt 'driver-loop evaluator fn))

; base evaluator implementation from 4.14
(define (base-driver-loop)
  (prompt-for-input ";;; Base(zeval) input:")
  (let ((input (read)))
    (let ((output
           (zeval input
                 the-global-environment)))
      (announce-output output-prompt)
      (user-print output)))
  (base-driver-loop))

;; install the base driver loop
(install-driver-loop 'eval base-driver-loop)

(define inside-repl?
  "A method to determine if we are inside a REPL or being executed directly"
  (eq? #f (assq-ref (current-source-location) 'filename)))

...

;; at the end of the file, you can specify which loop you want to invoke when
;; you run.
(if inside-repl? 'ready ;; we want the repl available ASAP if were inside emacs
    (begin
      ;; load our tests
      (load "test/evaluator.scm")
      ;; start the REPL
      (driver-loop 'amb)))
;;; EOF

Many code excerpts from the text cannot be directly used in the evaluator provided by the book itself. Before you initialize your evaluators environment, be sure to add the following to your primitive-procedures

(append! primitive-procedures
         `((+ ,+) (- ,-) (* ,*) (/ ,/) (abs ,abs)
           (= ,=) (< ,<) (<= ,<=) (> ,>) (> ,>=)
           (not ,not)
           (list ,list)
           (member ,member)
           (display ,display)))

Additionally, let is missing from the `amb` interpreter as well. Just add the one used by the analyze evaluator.

The `amb` evaluator presented in 4.3 is far from simple and requires patience and an eye for detail to work out whats really going on.

The query evaluator may be the most difficult material yet, particularly if you aren’t previously familiar with a language like Prolog.

This material requires very careful reading to grasp it’s operation and the book frequently spends more time on it’s consequences over it’s content.

If you want to grasp it’s implementation, you will have to read and reread chapter 4.4.4.

The unification step, which the book itself describes as the most unintuitive aspect, should be read thoroughly: It’s the material that actually does the process of generating deductions from premises.

It’s also important to remember that much of the rest of the material is devoted to various ‘optimizations’ and implementation details that can easily derail you.

The query evaluator presented as is cannot compute rules of the form (?x rule ?y) as many questions ask to, simply translate them to the postfix form and you will be fine.

(rule (?x next-to ?y in (?x ?y . ?u)))
                ⇩
(rule (next-to ?x ?y in (?x ?y . ?u)))

Here is a macro and runner function for generating a quick register machine definition as follows:

(define-register-machine newtons
  #:registers (x guess)
  #:ops       ((good-enough ,newton/good-enough?)
               (improve ,newton/improve))
  #:assembly  ((assign guess (const 1.0))
               improve
               (test (op good-enough) (reg guess) (reg x))
               (branch (label end-newton))
               (assign guess (op improve) (reg guess) (reg x))
               (goto (label improve))
               end-newton))

(define (machine-run mach init)
  "Run a machine with the registers initialized to the alist in `init' and
then dumps the values of all registers"
  (map (λ (el) (set-register-contents! mach (car el) (cdr el))) init)
  (start mach)
  (map
   (λ (reg) (cons (car reg)
                  (get-contents (get-register mach (car reg)))))
   (mach 'dump-registers)))

(define-syntax define-register-machine
  (syntax-rules ()
    ((define-register-machine var #:registers registers #:ops ops #:assembly assembly)
     (define var (build-rmachine
                  #:registers 'registers
                  #:ops       `ops
                  #:assembly  'assembly)))))

Everyone has regrets, let’s hope you have fewer by reading mine.

So many books have irrelevant exercises, SICP doesnt. I sped through the end of SICP Chapter 3 - I won’t do it again.

Permutations and the generation thereof are one of those strange backwaters of computer programming that never really manages to fit into the broader scheme (ha) of knowledge. I’ve come up with no less than 3 ways to do them over the years, including counting in base-N (where N is the number of permuted items), the traditional map-n-slap and other mundane methods.

I always feel guilty not giving an honest effort before looking up an algorithm online and I always feel somewhat stumped on permutation problems. Sure, I know the “classic” swap algorithm, I’ve (obviously) implemented the method for permuting a list in Chapter 2, but something essential feels like it’s getting left out.

Take Exercise 4.39, which (loosely) is to solve the floor puzzle without using amb AND take advantage of knowledge about the puzzle to make it perform better than ‘depth first’.

I ended up looking at someone elses solution here - This one is hard to solve without resorting “tricks”, such as applying eliminative logic beforehand to solve the problem. This mixes all sorts of different kinds of representations of data and many solutions are incorrect.

The parse words exercises give you the feeling that something really essential is being left out. I completed the exercises but I started to get to a really uncomfortable point, especially in Exercise 4.49 that this was some deep metaphor for parsing fully-specified grammars.

This is a list of exercises I haven’t completed for some reason or another.

• 4.32
• 4.33
• 4.34
• 4.44
• 4.47 (started to get unbelievably bored of these exercises)
• 4.48 (started to get unbelievably bored of these exercises)
• 4.49 (started to get unbelievably bored of these exercises)
• 4.69 (This is both tricky and somewhat irrelevant)
• 4.71
• 4.74

[fn:1] Including all exercises asking you to draw with pen and paper as well as those specified above. [fn:2] Ever wonder how people make calculators and webservers using ONLY type-inference without ANY instructions specified? Turns out thats actually fairly simple and you are just going to have to read the whole thing to find ou.