6.037 - Structure and Interpretation of Computer Programs

Introduction

This fast-paced course covers the material in the classic book Structure and Interpretation of Computer Programs — a class previously known at MIT as 6.001. It uses Scheme to introduce students to principles of computation, and to teach thought patterns for computer science. Students are taught to apply structural, procedural, and meta-linguistic abstraction to solve computational problems. Five projects will be assigned and graded.

Prerequisites: some programming experience; high confusion threshold.

This class is not meant as an introduction to programming; some programming experience is assumed. If you are looking for a preparatory class for 6.01, we suggest either 6.149 (for those with no programming experience) or 6.177 (for those with some) as more likely the correct IAP class to take.

6.037 focuses on higher-level concepts and abstraction in Scheme, an interesting but esoteric language which is infrequently seen in the wild; The language is light on practicality, but lends itself well to discussing computational theory. The class attempts to cram the entire material of a semester-long MIT course into eight two-hour lectures, with accompanying individual weekly projects, and as such is rather information-dense.

Your tour guides for this adventure are: Alex Vandiver, Mike Phillips, Benjamin Barenblat, Zev Benjamin, Ben Vandiver, and Chelsea Voss. To contact them, you can email 6.001-zombies at the obvious domain.

Logistics

• Class meets TR7-9pm throughout IAP, in 32-044
• 6 units of P/D/F credit are available; only the projects are graded.
• To sign up for our e-mail list, use this form.

Projects

There will be five projects assigned. Projects should be saved as plain text, and emailed to 6.037-psets at the obvious domain.

• Project 0: Basic scheme. Due by 7pm on Thursday, January 7th.
  • Handout
  • Code: simple-integration.scm
• Project 1: Higher-order procedures and symbols. Due by 7pm on Tues, January 12th.
  • Handout
  • Code: calculus.scm
• Project 2: Mutable objects and procedures with state. Due by 7pm on Thurs, January 14th.
  • Handout
  • Code: memoize.scm, table-tests.scm
• Project 3: Meta-circular evaluator. Due by 7pm on Thurs, January 21st.
  • Handout
  • Code: eval.scm
• Project 4: OOP evaluator (The Adventure Game). Due by 7pm on Fri, January 29th.
  • Handout
  • p4-scheme-files.zip - all of the scheme files below
  • Code: oo-eval.scm - Run this from DrRacket; rest will be pulled in
  • Code: oo-eval-extras.scm
  • Code: alyssa-tests.scm
  • Code: oo-world.scm
  • Code: oo-types.scm
  • Code: oo-util.scm

Lectures

Slides presented in class will be linked below. For each, we've noted which SICP chapters and which Spring 2007 lectures we've drawn the material from, in case you want to delve deeper, get a second opinion, read ahead, etc. Please note that the book covers a lot of additional material, and we are mostly tracking the old lectures, not the textbook.

• Lecture 1: Syntax of Scheme, procedural abstraction, and recursion [Printable] [With slide transitions]
  (SICP chapter 1; Spring 2007 lectures 1, 2, and 3)
  • Recitation material: Part 1, Part 2, and Solutions
• Lecture 2: Data abstractions, higher order procedures, symbols, and quotation [Printable] [With slide transitions]
  (SICP chapter 2; Spring 2007 lectures 5, 7, and 9)
  • Recitation material: Handout, and Solutions
• Lecture 3: Mutation, and the environment model [Printable] [With slide transitions]
  (SICP chapters 3.1 - 3.3; Spring 2007 lectures 11, 14; Optional online tutor exercises: Problem set 6.)
  • Recitation material: Handout, and Solutions
• Lecture 4: Interpretation and evaluation [Printable] [With slide transitions]
  (SICP chapters 4.1)
  • Recitation material: Evaluator, Handout, and Solutions
• Lecture 5: Debugging [Printable] [With slide transitions]
  • Recitation material: eval-broken.scm
• Lecture 6: Language design and implementation [Printable] [LibreOffice slides]
  • Object system #2 from lecture: Scheme code
  • Recitation material: Handout, and Solutions
• Lecture 7: Continuations, lazy evalutation, and streams
[Continuations printable] [Continuations with slide transitions] [Lazy evaluation/streams printable] [Lazy evaluation/streams slides] (SICP chapter 3.5. Optional online tutor exercises: Problem set 9 (part 2).)
• Recitiation material: Handout, Solutions, and code for trying this out in Racket.
• Lecture 8: Concurrency, 6.001 in perspective, and the Lambda Calculus
[Concurrency printable] [Concurrency with slide transitions] [6.001 in perspective printable] [6.001 with perspective with slide transitions] [ The Magic Lecture Code from lecture]

Calendar

Resources

• Racket (previously DrScheme), the scheme evaluator we will be using
  • Also available on Athena machines: add drracket; drracket
  • For language selection, select "The Racket Language" (a.k.a. "Determine language from source"). Hit the Show Details button, and set the Output Style to "write." Use the Language menu to make these changes.
• Structure and Interpretation of Computer Programs, the textbook written for 6.001. A PDF version is also available.
• Lecture notes from 6.001, Spring 2007 might be useful for getting extra exposition on some topics as well, or to look ahead before the Caffeinated slides for those topics are posted.
• 6.001 online tutor, from the MIT iCampus XTutor project. This contains online problem sets you can do and get instant feedback (you will grow to love the "check" button as much as students of yore). We won't grade these — so ignore the due dates associated with them! — but some people may find it a useful way to do little exercises to check their understanding of the topics presented. It also contains online versions of the lectures, with synchronized audio and slides.
• The Revised⁵ Report on the Algorithmic Language Scheme: PDF | HTML

Getting help

• You can e-mail the course staff at: 6.001-zombies at the obvious domain.
• Students are also welcome to join the staff on Zephyr, MIT's messaging system. Subscribe to the class named "6.037". If you're new to Zephyr, we recommend the excellent Barnowl Zephyr client.

Acknowledgments

Since this course is a heavily condensed version of 6.001, we owe thanks to all who have ever taught or otherwise supported 6.001 over its long run. While these people are too numerous to list here, there are definitely some names we would be remiss to omit:

• Eric Grimson, who taught 6.001 a total of 27 times, and from whose lecture slides and projects we have borrowed heavily.
• Gerry Sussman and Hal Abelson, the original architects of the course and authors of the SICP text.
• Anne Hunter, Course 6's fairy godmother, for taking an interest and helping make sure 6.037 happened.