The Spirit in the Computer

Schedule

Wed, 10 Oct 2007 06:42:05 Z

Who does or did what is no longer explicitly listed here even though the group remains active. We’ve just reached the end of Chapter 3, and will recommence with Chapter 4 on January 1st 2007, according to the following schedule.


(define (who-does-exercise exercise)
    (let ((ex-mod-5 (modulo exercise 5)))
      (cond 
        ((= ex-mod-5 0) "Thomas, Friday")
        ((= ex-mod-5 1) "Martin, Monday")
        ((= ex-mod-5 2) "Holger (substituting until others come back), Tuesday")
        ((= ex-mod-5 3) "Pal, Wednesday")
        ((= ex-mod-5 4) "Mike, Thursday")
        (else "Error -- I don't know about exercise" exercise))))

History

M 7th Martin 2.93
T 8th open 2.94
W 9th Pal 2.95
T 10th Mike 2.96
F 11th Thomas 2.97

M 31st Martin 2.88
T 1st open 2.89
W 2nd Pal 2.90
T 3rd Mike 2.91
F 4th Thomas 2.92

M 24th Martin 2.83
T 25th open 2.84
W 26th Pal 2.85
T 27th Mike 2.86
F 28th Thomas 2.87

M 17th Martin 2.78
T 18th open 2.79
W 19th Pal 2.80
T 20th Mike 2.81
F 21st Thomas 2.82

M 10th Martin 2.73
T 11st open 2.74
W 12nd Pal 2.75
T 13rd Mike 2.76
F 14th Thomas 2.77

(skipping 2.67)

M 3rd Martin 2.68
T 4th open 2.69
W 5th Pal 2.70
T 6th Mike 2.71
F 7th Thomas 2.72

M 26th Martin 2.62
T 27th open 2.63
W 28th Pal 2.64
T 29th Mike 2.65
F 30th Thomas 2.66

M 19th Martin 2.57
T 20th open 2.58
W 21st Pal 2.59
T 22nd Mike 2.60
F 23rd Thomas 2.61

M 12nd Martin 2.52
T 13rd open 2.53
W 14th Pal 2.54
T 15th Mike 2.55
F 16th Thomas 2.56

M 5th Martin 2.47
T 6th open 2.48
W 7th Pal 2.49
T 8th Mike 2.50
F 9th Thomas 2.51

M 29th Martin 2.42
T 30th open 2.43
W 31st Pal 2.44
T 1st Mike 2.45
F 2nd Thomas 2.46

M 22nd Martin 2.37
T 23rd Jan 2.38
W 24th Pal 2.39
T 25th Mike 2.40
F 26th Thomas 2.41

M 15th Martin 2.32
T 16th open 2.33
W 17th Pal 2.34
T 18th Mike 2.35
F 19th Thomas 2.36

M 8th Martin 2.27
T 9th Jan 2.28
W 10th Pal 2.29
T 11th Mike 2.30
F 12nd Thomas 2.31

M 1st Martin 2.22
T 2nd Jan 2.23
W 3rd Pal 2.24
T 4th Mike 2.25
F 5th Thomas 2.26

M 24th Martin 2.17
T 25th Jan 2.18
W 26th Pal 2.19
T 27th Mike 2.20
F 28th Thomas 2.21

M 17th Martin 2.12
T 18th Jan 2.13
W 19th Pal 2.14
T 20th Mike 2.15
F 21st Thomas 2.16

M 10th Martin 2.7
T 11th Jan 2.8
W 12th Pal 2.9
T 13th Mike 2.10
F 14th Thomas 2.11

F 31st Jan? 2.1
M 3rd Tim 2.2
T 4th Pal? 2.3
W 5th Mike? 2.4
T 6th Thomas 2.5
F 7th Martin? 2.6

T 23rd Tim 1.41
F 24th Pal? 1.42
M 27th Jan? 1.43
T 28th Mike? 1.44
W 29th Thomas 1.45
T 30th Martin? 1.46

W 15th Pal? 1.35
T 16th Jan? 1.36
F 17th Mike? 1.37
M 20th Thomas 1.38
T 21st Tim 1.39
W 22nd Martin? 1.40

More Resources

Fri, 26 Jan 2007 09:36:08 Z

SICP at Berkeley

Berkeley also run a course based on Structure and Interpretation of Computer Programs. http://www-inst.eecs.berkeley.edu/~cs61a/sp06/

The Lectures are Available online here

Some interesting stuff on queues

Here are two interesting papers regarding the implementation of queues:

Termite Scheme

Functional programming seems a good starting point for parallelisation—that is, exploiting multiple processor architectures. Termite Scheme tries to implement Erlang style parallel programming in Scheme. Try googling for termite scheme

Here are a couple of links Holger found earlier:

Co-routines in Scheme

The Scheme Programming Language provides an elegant implementation of co-routines implemented entirely in Scheme.

http://www.scheme.com/tspl3/examples.html#./examples:h11

How’s this for an exercise?

Exercise 9.11.4 Implement the kernel of a small operating system using engines for processes. Processes should request services (such as reading input from the user) by evaluating an expression of the form (trap ‘request). Use call/cc and engine-return from the preceding exercise to implement trap.

Adding syntax to Scheme (defining macros)

Some examples of / tutorials on define-syntax:

Scheme in Scheme

Regarding stuff from chapter 4 (implementing a scheme interpreter):

Henriy Baker had an article in Lisp Pointers Vol.5, No. 4 (1992) “Metacircular Semantics for Common Lisp Special Forms” http://home.pipeline.com/~hbaker1/MetaCircular.html (or http://home.pipeline.com/~hbaker1/MetaCircular.ps.gz for the Post Script? version) in which he shows how the Common Lisp special forms can be implemented via other Common Lisp special forms. Quite an interesting read, although you will have to learn about back-quotes to understand the implementations.

Scratch Pad

Thu, 04 Jan 2007 09:29:34 Z

Try out Instiki markup here. This Wiki uses Textile markup, so, alternatively, you can click across to Textism and try things out there.
You can do preformatted text like this:

                           .,ad88888888baa,
                  _    ,d8P"""        ""9888ba.      _
                 /  .a8"          ,ad88888888888a   |\
               /   aP'          ,88888888888888888a   \
              /  ,8"           ,88888888888888888888,  \
             |  ,8'            (888888888888888888888, |
            /  ,8'             `8888888888888888888888  \
            |  8)               `888888888888888888888, |
Procedure,  |  8                  "88888 Apply 8888888) | Expression
Arguments   |  8     Eval          `888888888888888888) | Environment
            |  8)                    "8888888888888888  |
            \  (b                     "88888888888888'  /
             | `8,                     8888888888888)  |
             \  "8a                   ,888888888888)  /
              \   V8,                 d88888888888"  /
              _\| `8b,             ,d8888888888P' _/
                     `V8a,       ,ad8888888888P'
                        ""88888888888888888P" 
                             """""""""""" 
                              [graphic by Normand Veillux, modified]

Blockquotes work just fine! User error on my part.

Heading1

You can reference footnotes¹

Heading2

Heading3

italics bold

¹ This is footnote 1

Language Wars
Peter Norvig

Home Page

Wed, 13 Dec 2006 09:43:44 Z

Welcome

Welcome to the “The Spirit in the Computer”. This Wiki has been set up in support of an ACCU mentored project. You’re most welcome to edit pages but you’ll have to log in first. Contact Thomas for the password.

The Project

The project is a study group for the book Structure and Interpretation of Computer Programs. This is a famous book which has been used in undergraduate courses in many universities to teach students general principles of programming. The language used in the text is Scheme, a dialect of Lisp, which the authors claim to be a perfect teaching language since it allows them to concentrate on fundamental concepts they want to present without having to teach very much syntax.

Quick Links

Why “The Spirit in the Computer”?

Because The Wizard Book is dedicated: “in respect and admiration, to the spirit that lives in the computer.”

Tim

Sun, 15 Oct 2006 13:22:51 Z

More Books

Tue, 10 Oct 2006 08:34:38 Z

The Scheme Programming Language

The Scheme Programming Language by R. K. Dybvig—you’ll notice his name is also on R5RS —describes all the features of standard Scheme. SICP won’t be using every feature of the language, so you may find this book useful if you use Scheme outside the project. The third edition is available online.

The Little Schemer

An excellent book for getting the feel of the language is The Little Schemer by Friedman and Felleisen. It’s quite different from any other programming text I’ve read (although the cover reminds me of The Fortran Colouring Book by Roger Kaufman), but it’s very useful. In the foreward, Gerald Sussman describes it as something that can “perform the same service that Hanon’s finger exercises or Czerny’s piano studies perform for the student of piano.” There’s no other way to describe it without showing it to you.

Practical Common Lisp

Peter Seibel’s book is also available online. This book looks particularly interesting since it contains several practical Lisp applications—rather than the more academic ones we find in The Wizard Book.

Hackers & Painters

Paul Graham’s book is really a collection of essays, many of which promote Lisp in one way or another. They’ve certainly convinced me the language is worth exploring. Here’s the book’s homepage.

Holger

Fri, 22 Sep 2006 09:58:29 Z

Holger Durer

I am just lurking on the list occasionally making the odd comment.

I used scheme in a previous life (read: before getting a job and family) and am following this project as I never got around to studying SICP in university.

Standards

Fri, 15 Sep 2006 14:57:18 Z

The IEEE Standard (R5RS)

Scheme has an IEEE standard as well as a series of revisions to that standard, the latest of which is named “The Revised(5) Report on the Algorithmic Language Scheme.” The latter is available at the link below. It’s a fairly readable reference and, depending on how well your interpreter’s documentation makes the distinction, you’ll want to refer to it so you’ll know the difference between standard parts of the language and extra features added by your interpreter.

http://www.schemers.org/Documents/Standards/R5RS/HTML/

I’d like to draw your attention to this section in particular, since one of the early exercises concerns numeric representations, and also this next section because the idea of tail recursion comes up early in the text (and as C++ programmers many of us are probably going to be concerned about performance with all the recursion going on):

Scheme Requests for Implementation (SRFIs)

Besides R5RS there are a set of proposed features for standard Scheme called the SRFIs (Scheme Requests for Implementation). I think of these as similar to the Boost libraries for C++: better to use than a vendor specific feature or library by being defacto standards and because they may one day become part of the actual standard:

http://srfi.schemers.org/

R6RS

A draft of the next version of the Scheme standard is available at http://www.r6rs.org.

Frequently Asked Questions

Sat, 29 Jul 2006 13:25:15 Z

What’s Currying?

It sounds like you’re interested in functional programming. The comp.lang.functional FAQ answers this question and many more.

What’s an ACCU Mentored Developers Project?

The project centres on an email reflector. People sign up as either observers or students, and start receiving emails—typically it seems to be three or four a day. Students are assigned exercises from The Wizard Book and submit their answers to the reflector for comment.

Mentors and observers are on the list to offer expert advice.

Sounds Interesting—Can I Join?

Yes, if you’re a member of the ACCU. Head over to the mentored developers page on the website and follow the instructions.

Can you supply an implementation of “put” and “get”?

All the source code for the exercises, including implementations of library functions required, can be found here.

Why isn’t “nil” working?

The quick answer is: nil is no longer part of Scheme, use ‘() instead. The long answer follows…

Early examples in Chapter 2 use nil as a list terminator, but when these examples are run using (e.g.) MIT Scheme, you get:

;Unbound variable: nil

Similarly, using () or null in place of nil may work on some implementations, but neither is portable. The Wizard Book addresses the issue in this footnote

It’s remarkable how much energy in the standardization of Lisp dialects has been dissipated in arguments that are literally over nothing: Should nil be an ordinary name? Should the value of nil be a symbol? Should it be a list? Should it be a pair? In Scheme, nil is an ordinary name, which we use in this section as a variable whose value is the end-of-list marker (just as true is an ordinary variable that has a true value). Other dialects of Lisp, including Common Lisp, treat nil as a special symbol. The authors of this book, who have endured too many language standardization brawls, would like to avoid the entire issue. Once we have introduced quotation in section 2.3, we will denote the empty list as ‘() and dispense with the variable nil entirely.

Since this was written, nil has been excised from the Scheme standard—but the bottom line holds: use ‘(), not nil. In an email to the accu-sicp list, Mike notes:

It’s a troublesome thing, this nil/null/’() business. Scheme48 and
scm don’t define null, and guile defines it but as a procedure akin to
common lisp’s null (to go with its nil which behaves like cl’s nil,
which itself is distinct from ‘()—maybe this had something to do
with fsf’s plans to re-do emacs in guile). I think the best bet is to
replace the authors’ use of nil with ‘().

What’s the difference between Lisp and Scheme?

Sorry, I don’t have a definitive answer to that. Scheme is a Lisp dialect. The best known Lisp dialect is probably Common Lisp—which is rather bigger than Scheme. Here are some relevant links:

Holger had this to say about the difference between Scheme and Common Lisp:

I think a good comparison is the difference between Modula-2 and Ada (only that with Scheme v CL it is a bit larger a difference). One language is designed of elegance of simplicity while the other is meant for industrial strength application developments (CL has the added ‘feature’ of carrying a few decades of historical cruft with it while Ada might suffer more from design by committee).

Mike? also notes:

My impression so far is that if I do much Scheme I’ll probably end up using different implementations for different things. Guile has a lot of good things for GNU/Linux environments, but is not much good if I want the program to run on windows, I think, and hasn’t the full numeric tower (this may have changed in versin 1.8 just out). I’ve started using scsh instead of bash or perl for scripts, and it runs on scheme48. And then there’s bigloo which looks like the most promising of the scheme compilers for targetting the .Net runtime.

This situation contrasts with Common Lisp where I think I can just pick one of sbcl or GNU clisp and stick with it (although sbcl seems more complete while it sounds like GNU clisp has a better windows port, but at least the code wouldn’t need to change as much between them—if at all?). And the tools seem to be more mature for CL (slime looks wonderful), the module system is standardized, and there seems to be more handy libraries, which also look more mature. Someday, assuming a Scheme community continues to work away as they are now, I think I’d rather use Scheme than CL, but right now it looks like CL is the more serious language for general use, so that’s on my list to learn when we’re finished here (or sooner).

Implementing the Fibonacci Series is nice, but can I write a GUI using Scheme?

I know what you mean. I guess Common Lisp is a better starting point. Holger has had some good results using LTK, which describes itself as “The easy way to do Lisp GUI programming”, and provides a Common Lisp binding for the Tk graphics toolkit. Apparently no knowledge of Tk is required.

Holger also notes:

I vaguely remembered that there was some gtk binging for guile. Google found me:

http://www.gnu.org/software/guile-gtk/.
There is guile Tk: http://wiki.tcl.tk/GuileTk (“A moribund binding of Guile to Tk”)
http://kaolin.essi.fr/STk/ —R4RS with Tk bindings.
http://www.scheme.com/csv6.9c/—SWL (seems to be Tk for Chez scheme)
PLT / Dr Scheme seems to have some graphics capabilities…

SICP is great. Can you recommend any other material for a programming language enthusiast?

Lambda the Ultimate calls itself a “programming languages weblog”. I found an interesting thread on reading matter here.

Progress to Date

Sun, 16 Jul 2006 18:20:58 Z

Where are we?

As I write this (April 2006), we’re well into Chapter 2 of the book, which starts to talk about layers of abstraction, data structures and so on.

Chapter One, “Building Abstractions with Procedures” went into some detail on the Lisp evaluation model, before covering:

recursive and iterative processes
the space/time complexity of a program
functional programming

<< A Few Lines of Code | ^ Progress Report | >> Recursion and Iteration

A Few Lines of Code

Sun, 16 Jul 2006 18:20:08 Z

A Few Lines of Code

As already mentioned, the book uses Scheme as a language for teaching. Yet Scheme itself is never really taught:

In teaching our material we use a dialect of the programming language Lisp. We never formally teach the language, because we don’t have to. We just use it, and students pick it up in a few days.

Amazingly, this turns out to be true. I find myself learning the language by using it. Sure, some of the exercises are there to help me on my way, but most of them are aimed at discovering more fundamental things about programming.

Scheme is also a powerful language. You don’t have to type a whole lot, and, by virtue of the interpreted environment, you can reshape and test your code as you go. There’s no need for Makefiles or compilation.

Should you require more information on the language, the Standard is available online at: http://schemers.org/Documents/Standards/R5RS. Scheme programs are concise and so too is the standard which, at just 50 pages, is more of a pamphlet than a doorstop.

<< Report Schedule | ^ Progress Report | >> Progress to Date

Report Schedule

Sun, 16 Jul 2006 18:19:48 Z

Schedule

After much discussion and a few iterations, we seem to have settled on a sustainable schedule. Each iteration starts with Mike assigning exercises, one per student per day. As an example, here’s the schedule for the last few exercises in Chapter One.

Thu 23rd March, Tim, Exercise 1.41
Fri 24th, Pal, 1.42
Mon 27th, Jan, 1.43
Tue 28th Mike, 1.44
Wed 29th Thomas, 1.45
Thu 30th Martin, 1.46

So, this particular round of exercises starts with Tim submitting his solution to Exercise 1.41 to the email list on Thursday 23rd March. Everyone then comments on this solution. On Friday, Pal’s solution to the next exercise gets posted.

This schedule might seem rather ambitious, but, since the book contains over 350 exercises, we need to keep things moving. As you can see, we get the weekends off, and, if someone can’t complete an exercise, he just says so and anyone else is free to step in. Besides, many of the exercises are trivial, and nearly all can be answered in just a few lines of code.

<< Mentored Developer Projects | ^ Progress Report | >> A Few Lines of Code

Progress Report

Wed, 21 Jun 2006 20:57:39 Z

The ACCU SICP Project—a Progress Report

Recursion and Iteration

Wed, 21 Jun 2006 20:56:41 Z

Recursion and Iteration

Scheme does not need any special looping construct¹ since recursive procedures (that is, procedures which call themselves) can be used to implement iterative processes. The classic example is the factorial function, which we might consider implementing using a recursive procedure:

    (define (factorial n)
      (if (= n 1)
          1
          (* n (factorial (- n 1)))))

This turns out to be an expensive implementation, since, to evaluate a particular factorial, the Scheme interpreter needs to build a chain of deferred multiplication operations, which can only be applied when it finally reduces the input argument to to the special case value, 1. We have here a recursive procedure which generates a recursive process.

By contrast:

    (define (factorial n)
      (define (iter product counter)
        (if (> counter n)
            product
            (iter (* counter product)
                  (+ counter 1))))
      (iter 1 1))

uses a recursive procedure iter to implement an iterative process. At any point in the calculation of a factorial, the complete state of the function is held in just three variables, product, counter, and n.

Some points for the curly-bracket language readers.

0) Notice the nested inner function, iter, which has been scoped within the factorial function since it has no real use outside this scope. Scheme also supports unnamed, or lambda functions.

1) I could have used the usual mathematical symbol, !, for factorial, if I wanted.

    (define (! n)
       ... )

    (! 9)
    ;Value: 362880

(Note that in Scheme, logical not is written “not”.)

It appears that pretty much any contiguous combination of non-whitespace symbols can be used to name a function. For example, the built-in increment function is 1+, which we could happily alias to ++ if we wanted:

    (define ++ 1+)

Predicates often end with a question mark, which reads nicely.

    (if (even? n) ...)

2) Numbers aren’t constrained to fit into a fixed number of bits, so we can calculate:

   (! 2006)
   ;Value: 2144794478704779 ... 000000

I was also pleased to find that Scheme builds in support for rational and complex numbers:

   (+ 7 (/ (sqrt -1) 3))
   ;Value: 7+1/3i

Space/Time Complexity

I don’t suppose analysis of the space and time requirements of a program will come as anything new to a seasoned programmer, though we may choose to measure rather than analyse. There really is nothing like running an interpreter and directly experiencing the difference between an O(n) and an O(log(n)) implementation of a function to bring the lesson home, though.

¹ In fact, Scheme does provide two special forms for looping: do, and the more general named let.

<< Progress to Date | ^ Progress Report | >> Functional Programming

Functional Programming

Wed, 21 Jun 2006 20:55:32 Z

Functional Programming

The functional style of programming may be a little more novel to curly-bracket programmers. By functional programming, I mean a style of programming where powerful abstractions can be built from higher-order functions—functions which apply to functions, that is—and where functions are first-class objects.

As an example, here is all we need to implement a function which will n-fold smooth another function. Note the higher-order helper functions, compose, which forms the composition of two functions, and repeated, which repeatedly applies a function. Both these helpers are completely general purpose building blocks.

    (define (compose f g)
     (lambda (x)
       (f (g x))))

    (define (repeated f n)
     (if (= n 1) f
         (compose f (repeated f (- n 1)))))

    (define dx 0.1)

    (define (average . items)
     (/ (apply + items)
        (length items)))

    (define (smooth f)
     (lambda (x)
       (average (f (- x dx))
                (f x)
                (f (+ x dx)))))

    (define (n-fold-smooth f n)
     ((repeated smooth n) f))

<< Recursion and Iteration | ^ Progress Report | >> Joining In