CS 491/591: Advanced Scheme Programming and Implementation *

Instructor: Lance Williams <williams@cs.unm.edu>
Time: Tues. Thurs. 5:00-6:00
Location: FEC 349
Office Hours: Mon. 4:00-5:00, Tues. 2:00-3:00.
Office: FEC 349

Description

I'd rather write programs to write programs than write programs. -D. Sites

What I cannot create I do not understand. - R. Feynman

After a quick review of the basic features of the Scheme programming language, we will explore advanced language features not normally covered in CS 257. These include macros, lazy evaluation, streams, continuation passing style, and call/cc. We'll also look at the lambda calculus and the Y-combinator. The bulk of the course will focus on implementation of Scheme interpreters and compilers. Topics will include scanning, parsing, evaluation, macro-expansion, compilation, and garbage collection. Each student will write a working Scheme interpreter or compiler in a non-garbage-collected language (e.g., C). Undergraduates who have taken CS 257, and who want to learn more about Scheme and its implementation are welcome to take CS 491. Graduate students who have taken CS 257 (or have equivalent proficiency in Scheme) are welcome to take CS 591.

Textbooks

The text for the course will be Scheme and the Art of Programming by George Springer and Daniel P. Friedman (MIT Press, 1989). You may purchase a copy of the text at the Engineering Copy Center which is located on the first floor of Farris Engineering Center. You might also want to look at The Structure and Interpretation of Computer Programs by Harold Abelson and Gerald Jay Sussman with Julie Sussman (2nd edition, MIT Press, 1996) which is available online in its entirety. This is the introductory programming text used at MIT.

Related Material

The R⁵RS Manual describes the Scheme standard. Teach Yourself Scheme in Fixnum Days by Dorai Sitaram is also useful. The Scheme Programming Language: ANSI Scheme by R. Kent Dybvig, (2nd Edition, Prentice Hall, 1996) is available online in its entirety. So is On Lisp by Paul Graham. Finally, if you are going to program in C, you will probably need a copy of The C Programming Language by Kernighan and Richie.

Course Topics

review
scanning and parsing
backtracking search
lambda calculus
Y-combinator
macros
lazy-evaluation and streams
file i/o
continuation passing style
call/cc
non-determinism
multiple value return
symbol tables and hashing
interpretation
compilation
closures and object-oriented programming
garbage collection

Programming Projects**

s-expression reading and printing
symbol table
expression evaluator/compiler
syntactic sugar
garbage collector

Readings

Steele, G.L., and R.P. Gabriel, The Evolution of Lisp
Friedman, D.P., Applications of Continuations
Bawden, A., Quasiquotation in Lisp
Dybvig, R.K., Three Implementation Models for Scheme
Wilson, P.R., An Introduction to Scheme and its Implementation

Scheme Interpreter/Compiler Contest

Speed benchmark (code)
Most R⁵RS compliant
Coolest non-standard language extension
Best garbage collector***

Homework

Grading

Homeworks (approx. 5): 25%
Programming Projects (approx. 5): 50%
Class Participation: 25%

Miscellany

* This page can be found at http://www.cs.unm.edu/~williams/cs491s06.html
** There will be LOTS of hacking to do! Don't take this course if you don't like to code!
*** This prize provided courtesy of Prof. Stefanovic.