Discussion forum for David Beazley

Structure and Interpretation of Computer Programs (Fall 2017)


#1

Well, I’m in the process of preparing the inaugural run of the SICP course for fall 2017. The plan is to go through most of the famous “Structure and Interpretation of Computer Programs” by Abelson, Sussman, and Sussman in four days. I must be crazy.

Anyways, I’m going to use this topic to discuss preparation, organization, and other details for anyone who’s interested (especially those taking it).

The book can be found online at https://mitpress.mit.edu/sicp/full-text/book/book.html and multiple other places.


#2

Some thoughts on mathematical preparation… many of the early parts of the book use examples from math courses including:

  • Newton’s Method
  • Rational numbers
  • Complex numbers
  • Polynomials
  • Symbolic differentiation
  • Numerical differential and integration

I think I’m going to retain all of this, but will offer a brief math refresher as needed.


#3

We will be writing our own LISP/Scheme interpreter for the course. It turns out it’s not so hard to do it. For example, you can look at this article http://norvig.com/lispy.html. Most of the course will be taught in Scheme, but with parallels drawn to similar ideas in Python.


#4

Soooo pumped for this course! Really impressed by the Hylang project but feel like we could do one better! Tons of questions!!

Think we’ll be getting into macros at all?
Will we be doing purely interpeter stuff or will we be going into compiler optimization stuff at all?
Recursive descent parser or some kind of token stream situation?
Error handling, stack traces?


#5

OH! Tail recursion hacking with loop/recur macro stolen from Clojure? :smiley:


#6

Well, I can’t speak to macros specifically (or Hylang). I’d say the course is going to stay pretty faithful to the SICP book in content and flow. Writing a Scheme interpreter is not terribly difficult as far as parsing/tokenizing is concerned. I wouldn’t expect to see a lot of advanced tricks there unless you decide to tackle it as an optional feature.

Tail recursion would be an interesting challenge to think about. I’ll keep that open as possibility for now.


#7

Curious if you could comment briefly on the major differences between this and your compilers course?


#8

The compilers course is strongly focused on the specific engineering task of building a compiler for an actual programming language. We take a small language based on Go and compile it to fully executable object code via LLVM. This involves a variety of problems including tokenization, parsing, abstract syntax trees, static analysis/type checking, intermediate code generation, etc. A variety of tools and libraries are used in the process. It is a substantial coding project consisting of 3000-4000 lines of Python code when it’s all done.

The SICP course is more focused on two deeper questions: “What is computation?” and “What is programming?” That first question (computation) is explored in the context of functional programming and mathematics. The latter question (programming) is explored in the context of abstraction–procedural abstraction, data abstraction, linguistic abstraction, etc. A lot of this intersects the core of computer science itself. Admittedly, all of this might sound a bit fuzzy, but after going through SICP, I don’t think you’ll ever look at programming languages in the same way again. A lot of things will be made clear. You’ll look at programming problems in a different way. You might walk away with more questions than you had when you started. That said, this course is focused much less on cranking out code and more on thinking, Most of the coding will be in LISP/Scheme. We will write a LISP interpreter in Python, but that is a very small amount of code compared to the compilers project.


#9

Very, very excited - I studied SICP in college in 1996 & it was a huge influence - solving 8 Queens for homework blew my young mind. Haven’t touched LISP since, but I will bring my original print copy :slight_smile: A few questions & thoughts:

  1. Suggestions on a LISP-friendly editor that works on Linux (for sinners who don’t use Emacs)?
  2. Sounds like this will be more in line with typical classes in terms of amount of coding (vs. compilers) - is that right? Just concerned about ergonomics…
  3. I’m eager to brush up on calculus in class, but it’s been likewise a long time since I’ve really used it.

Topics of interest off the top of my head:

  1. infinite streams
  2. state, concurrency & I/O in functional programming
  3. lexical vs. dynamic scope
  4. macros

Some friends here recently went through SICP & said the last bits on implementing a virtual machine got kind of long in the tooth.

As a practical goal, I’ve been wanting to get into Clojure professionally, hoping this helps on that front.


#10

Well, the course has come and go. It was truly a great experience in my completely unbiased opinion ;-). Should anyone wonder what we covered in 4 days, we managed to work through topics in the first 4 chapters of the book ending with with the implementation of the metacircular evaluator.

Overall, I’d say the focus was probably a bit different than what you would find in a typical “intro” college course. Everyone attending had prior programming experience. As such, we didn’t spend so much time working through tricky programming puzzles (i.e., solving 8-queens puzzles and stuff). We spent much more time on the programming language semantics. For example, the difference between different evaluation models and getting to the core of some central ideas in functional programming. We also did a brief half-day diversion into lambda calculus and how that related to the material.

As part of the course, everyone implemented a Scheme interpreter in Python. That was an interesting approach as it required everyone to think much more about the computational model earlier than what is presented in the text. A number of people also tried making some customization features not part of standard Scheme. One unanticipated effect of writing Scheme in Python first is that when we got to the final project of writing the metacircular evaluator (Scheme in Scheme), everyone had already written one Scheme interpreter. Thus, a number of us decided to accept a new challenge and give it a go from scratch without looking at the solution given in SICP. On the whole I’d say that was an interesting exercise, punctuated by difficult debugging, and the realization that none of us were particularly graceful Lispers. Nevertheless, I certainly learned a lot by doing that. I think everyone else did too.

In any event, look for this course to run again in January. It will probably be even more insane!