Scheme

Reading: The Scheme Programming Language, 2.1–8, 3.2

Scheme is part of the Lisp family of languages, which also includes Common Lisp, a standardization of Lisp (partially influenced by Scheme); Emacs Lisp, the extension language used by Emacs; and Clojure, which many of you learned in Programming Paradigms.

Running Scheme

Scheme has a large number of not-completely-compatible implementations. We are using Chez Scheme, which is reputed to be very fast, and goes with the book we are using.

It is installed on studentnn.cse.nd.edu, where nn ∈ {04,05,06,10,11,12,13}, at ~dchiang/Public/pl/bin/scheme. To install it on your own computer, you can probably use one of these commands:

sudo apt-get install chezscheme
brew install chezscheme
sudo port install chez-scheme

Now create a file called hello.scm:

#!/usr/bin/env scheme --script
(display "Hello, world.\n")

To run it, make sure that scheme is in your PATH, and type

scheme --script hello.scm

or make it executable and run it directly:

chmod +x hello.scm
./hello.scm

The Scheme language

I’d like you to take away three main ideas from this reading:

Lists

Scheme is a dialect of Lisp, which originally stood for List Processor. Lists are the workhorse data structure in Scheme (more so than in Clojure, which you may be more familiar with), so please get familiar with them and their associated functions with their weird names (cons, car, cdr, etc).

Scheme expressions are also lists (which is what gives Scheme syntax its characteristic appearance with lots of parentheses). This has interesting implications for things like macros, which we won’t delve into. But please be sure you understand the difference between (+ 1 1) and '(+ 1 1).

Functions

lambda expressions are known as “anonymous functions” in some other languages, and we also sometimes call them abstractions. We’ll be using them all semester long, so be sure you understand them well.

An important issue is that of lexical (or static) scoping. The Scheme book explains this in the paragraph starting “What happens when the procedure….” It goes by very quickly, so please pay very careful attention to it.

Recursion

Recursion plays a much more prominent role in Scheme and other functional programming languages than it does in imperative languages. The book gives three ways of defining recursive functions:

define is for top-level (global) definitions of functions, which can be recursive;
letrec is for local definitions of functions that can be recursive; and
named let, which is similar to letrec, but is sometimes more convenient in situations where you might use a loop in an imperative language.

The book spends a while talking about tail recursion, which is important to know about for practical Scheme programming. (If you’re coming from Clojure, this is a major difference: since the JVM does not allow tail recursion, neither does Clojure; instead, the only way to write efficient loops is using loop/recur, which is similar to named let.)