CS 257: Intro to Non-Imperative Programming: Scheme!

TAPY 201, MWF, 9:00-9:50


Pascal is for building pyramids - imposing, breathtaking, static structures built by armies pushing heavy blocks into place. Lisp is for building organisms.
-Alan J. Perlis

In this course you will learn to program in a new way. This new style emphasizes beauty and generality, and uses programming languages that allow you to express computations simply and elegantly. It emphasizes interactive programming and rapid prototyping. It is done using languages that, like the game of go, are very simple to learn the rules to but take a lifetime to master.

The Scheme language is a higher level language than FORTRAN or C++. It frees the programmer from the details of memory management, storage layout, and word size. It provides facilities like first class functions, true lexical scoping, and surprising simplicity. It allows itself to be extended easily, to create new more powerful languages. Yet is is very simple in both syntax and semantics.

Programming a computer is about controlling complexity by using abstraction. As you learn a lot of powerful new abstractions (composition of functions, functions as data, recursion, higher order functions, tail recursion, functions as objects), you will find that you are able to implement things much more quickly and succinctly and elegantly than you ever thought possible.

There is no royal road to mathematics.

-Menaechmus, 380-320 BC.

You can learn to play the piano only by sitting down at a keyboard and pressing the keys. And you can learn to program in Scheme only by sitting down at a keyboard and pressing the keys. You cannot learn Scheme solely by listening and reading. You will need to devote a lot of time to programming. We will try to make that time not only instructive and productive, but also a lot of fun.


Your guides in the discovery of your inner lambda nature are:


For your convenience as well as that of the the rain forests, much of the class will be conducted electronically. In addition to e-mail to the individual instructors, you should use the following:
The entire class
Get yourself added to or deleted from the above list
The instructors (all of them)

Related Material

We will use the STk Scheme implementation, which although dog slow provides convenient access to the Tk graphics library. (When speed becomes a concern, eg for final projects, some students may wish to use rscheme, a much zippier implementation.) For help programming, have a look at this list of Scheme idioms. Also you will want to use the R4RS Manual, which describes the Scheme standard.

You probably will want to use GNU Emacs as your editor. I do. Or use XEmacs if you prefer.

The primary text is Simply Scheme by Brian Harvey and Matthew Wright (MIT Press, 1994). This text will be supplemented by lecture notes made available on the web.

Those born with a silver left parenthesis in their mouth may enjoy The Little Schemer by Daniel P. Friedman and Matthias Felleisen (4th edition, MIT Press, 1995), a delightful supplementary text. And if you're really hard core, check out The Structure and Interpretation of Computer Programs by Harold Abelson and Gerald Jay Sussman with Julie Sussman (2nd edition, MIT Press, 1996).

Sometimes quizzes and exams from years past are helpful in studying. In the past Jim Hollan taught this course, and his materials are available for your perusal.


For relevant add/drop dates consult the UNM Academic Calendar.
I think that it's extraordinarily important that we in computer science keep fun in computing. When it started out, it was an awful lot of fun. Of course, the paying customers got shafted every now and then, and after a while we began to take their complaints seriously. We began to feel as if we really were responsible for the successful, error-free perfect use of these machines. I don't think we are. I think we are responsible for stretching them, setting them off in new directions, and keeping fun in the house. I hope the field of computer science never loses its sense of fun.
-Alan J. Perlis
Mon Aug 25
My idiosyncratic view of programming languages
Wed Aug 27
Scheme expressions (ch 3); using Emacs and STk (notes on web)
Fri Aug 29

Wed Sep 3
Quiz 1 answers
+ defining procedures (ch 4)
Fri Sep 5
words and sentences; if (ch 5,6) Problem set 2 answers

Mon Sep 8
cond, and, or (ch 6)
Wed Sep 10
Quiz 2 answers
Fri Sep 12
Functions as data I (ch 7,8) Problem set 3 answers

Mon Sep 15
Wed Sep 17
Quiz 3 answers
Fri Sep 19
Functions as data II (ch 9,10)

Mon Sep 22
Wed Sep 24
Quiz 4 answers
Fri Sep 26
Recursion I (ch 11,12) Problem set 4 answers

Mon Sep 29
Wed Oct 1
Recursion II (ch 13,14) helper functions with something extra
Fri Oct 3

Mon Oct 6
Go over PS4, more recursion (maybe start on ch 15,17,19)
Wed Oct 8
Quiz 5 answers
Fri Oct 10
Recursion III (ch 15,17,19) Problem set 5 answers

Mon Oct 13
Wed Oct 15
(continued) + Review

Mon Oct 20
Review + Project I Design
Wed Oct 22
Exam I answers
Fri Oct 24
(continued) Problem set 6 answers

Mon Oct 27
symbolic arithmetic (notes on web)
Wed Oct 29
Fri Oct 31

Mon Nov 3
cool thing: tail recursion and goto-less programming
Wed Nov 5
Fri Nov 7
Quiz 6 answers

Mon Nov 10
under the hood: environments and eval
Wed Nov 12
(continued) Project One diff.scm
Fri Nov 14
implementing objects with procedures

Mon Nov 17
(continued) Problem set 7 answers
Wed Nov 19
cool thing: implementing assignment with procedures (notes on web)
Fri Nov 21
Macros: cond, switch, quasiquote

Mon Nov 24
Project II design
Wed Nov 26

Mon Dec 1
Macros + such
Wed Dec 3
Fri Dec 5
Quiz 7 answers

Mon Dec 8
Exam II answers
Wed Dec 10
Project II presentations
Fri Dec 12
Return Exam II + review

Wed Dec 17
Final exam: 7:30-9:30am, TAPY 201


Programmers are not to be measured by their ingenuity and their logic but by the completeness of their case analysis.
-Alan J. Perlis
There will be seven quizzes, a series of programming problem sets, two programming projects, and a final exam. Your grade will be determined by the following program:
  (define your-grade
    (lambda (exam1 exam2 average-best-6-quizzes average-problem-sets
             project1 project2 final-part1 final-part2 style

        (+ (* .25 (max exam1 final-part1))
           (* .25 (max exam2 final-part2))
           (* .125 average-best-6-quizzes)
           (* .125 average-problem-sets)
           (* .05 project1)
           (* .1 project2))
           (* .1 style)
	   (- missed-mandatory-office-hours)))
Quizzes and tests are cumulative. That means that material on earlier quizzes or tests may be repeated on later ones, especially if a lot of people get it wrong the first time. Learn from your mistakes, or you'll make them again.

Quizzes and tests will also depend on knowledge you'll get from programming assignments. Doing the programming assignments on time is the best way to be ready to take the short quizzes and tests which may follow very shortly thereafter.

In programming, as in everything else, to be in error is to be reborn.
-Alan J. Perlis

Everyone must come to office hours (mine or the TAs) when they need help. If your score on any problem set, quiz, or exam is below the announced ``low water mark'' you are required to come to office hours within five days.

Barak Pearlmutter <>
Computer Science Department
FEC 355C
505 277-9425