Scheme and its Ideologies

Michael Falk

The University of Melbourne

A famous quotation

Alan Kay: Yes, that was the big revelation to me when I was in graduate school—when I finally understood that the half page of code on the bottom of page 13 of the Lisp 1.5 manual was Lisp in itself. These were “Maxwell’s Equations of Software!” This is the whole world of programming in a few lines that I can put my hand over. (Feldman 2004, 26)

The Man Himself, holding a prototype Dynabook. Source: Wikipedia

Maxwell’s Equations

\[ \nabla \cdot \mathbf{E} = \frac{\rho}{\varepsilon_0} \tag{1}\] \[ \nabla \cdot \mathbf{B} = 0 \tag{2}\] \[ \nabla \times \mathbf{E} = -\frac{\partial \mathbf{B}}{\partial t} \tag{3}\] \[ \nabla \times \mathbf{B} = \mu_0 \left(\mathbf{J} + \varepsilon_0 \frac{\partial \mathbf{E}}{\partial t} \right) \tag{4}\]

Four interlinked equations, showing that the electric field \(\mathbf{E}\) and magnetic field \(\mathbf{B}\) form a single electromagentic field. The four equations expression Gauss’s law (Equation 1), Gauss’s law of magnetism (Equation 2), Faraday’s law (Equation 3) and the Ampère-Maxwell law (Equation 4).

Page 13 of the LISP 1.5 Manual

apply[fn x a] =
  [atom[fn] → [eq[fn CAR] → caar[x];
              eq{fn CDR] → cdar[x];
              eq[fn CONS] → cons{car[x] cadr[x]];
              eq[fn ATOM] → atom{car[x]];
              eq[fn EQ] → eq[car[x] cadr[x]];
  T apply[eval[fn a] x a]];
  eq[car[fn] LAMBDA] → eval[caddr[fn] pairlis[cadr[fn] x a]];
  eq[car[fn] LABEL] → apply[caddr[fn] X cons[cons[cadr[fn];
                                        caddr[fnj]  a]]]

eval[e a] = [atom[e] → cdr[assoc[e a]];
  atom[car[e]] →
          [eq[car[e]QUOTE] → cadr[e];
          eq[car{e] COND] → evcon[cdr[e] a];
          T → apply[car[e] evlis[cdr[e] a] a]];
  T → apply[car[e] evlis[cdr[e] a] a]]

(McCarthy et al. 1962, 13)

The Magic of LISP

The metacircular wizard from the cover of Structure and Interpretation of Comptuer Programs by Abelson, Sussman, and Sussman (1996)

\(\lambda\) the Ultimate

Lambda was conferred its ultimacy by Sussman and Steele Jr. (1975), Steele Jr. and Sussman (1976), Steele Jr. (1976), Steele Jr. (1977), Steele Jr. and Sussman (1979).

Strange Loops in LISP

An analogous double-entendre can happen with LISP programs that are designed to reach in and change their own structure. If you look at them on the LISP level, you will say that they change themselves; but if you shift levels, and think of LISP programs as data to the LISP interpreter […], then in fact the sole program that is running is the interpreter, and the changes being made are merely changes in the data. (Hofstadter 1999, 692)

In this analogy, S-expressions in LISP are like thoughts in the mind, and the LISP interpreter is like the neurons of the brain. The software can inspect itself but not the machine.

JavaScript: The Ultimate \(\lambda\)

JavaScript is the first lambda language to go mainstream. Deep down, JavaScript has more in common with Lisp and Scheme than with Java. It is Lisp in C’s clothing. This makes JavaScript a remarkably powerful language. (Crockford 2008)

References

Abelson, Harold, Gerald Jay Sussman, and Julie Sussman. 1996. Structure and Interpretation of Computer Programs. Second. Cambridge: MIT Press.

Crockford, Douglas. 2008. JavaScript: The Good Parts. Sebastopol, Calif: O’Reilly. https://learning.oreilly.com/library/view/javascript-the-good/9780596517748/.

Feldman, Stuart. 2004. “A Conversation with Alan Kay: Big Talk with the Creator of Smalltalk - and Much More.” Queue 2 (9): 20–30. https://doi.org/10.1145/1039511.1039523.

Hofstadter, Douglas R. 1999. Gödel, Escher, Bach: An Eternal Golden Braid. New York: Basic Books.

McCarthy, John, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart, and Michael I. Levin. 1962. LISP 1.5 Programmer’s Manual. Cambridge: The MIT Press. https://doi.org/10.7551/mitpress/5619.001.0001.

Steele Jr., Guy Lewis. 1976. “LAMBDA: The Ultimate Declarative.” 379. Cambridge, Mass: Massachusetts Institute of Technology. https://dspace.mit.edu/handle/1721.1/6091.

———. 1977. “Debunking the "Expensive Procedure Call" Myth; or, Procedure Call Implementations Considered Harmful; or, Lambda: The Ultimate Goto.” 443. Cambridge, Mass: Massachusetts Institute of Technology. https://apps.dtic.mil/sti/pdfs/ADA062381.pdf.

Steele Jr., Guy Lewis, and Gerald Jay Sussman. 1976. “LAMBDA: The Ultimate Imperative.” 353. Cambridge, Mass: Massachusetts Institute of Technology.

———. 1979. “Design of LISP-Based Processors; or, Scheme: A Dielectric LISP; or, Finite Memories Considered Harmful; or, LAMBDA: The Ultimate Opcode.” 514. Cambridge, Mass: Massachusetts Institute of Technology. https://dspace.mit.edu/bitstream/handle/1721.1/5731/AIM-514.pdf.

Sussman, Gerald Jay, and Guy Lewis Steele Jr. 1975. “Scheme: An Interpreter for Extended Lambda Calculus.” 349. Cambridge, Mass: Massachusetts Institute of Technology. https://dspace.mit.edu/bitstream/handle/1721.1/5794/AIM-349.pdf.