Sketchy LISP

An Introduction to Functional Programming in Scheme

1 Basic Scheme Programming

1.1 Notation

Scheme is a small language with simple syntax and clean semantics. It uses a uniform notation for all of its constructs. Here are some simple examples:

; Scheme notation   Math notation
(+ 5 7 9)           ; 5+7+9
(- n)               ; -n
(f x)               ; f(x)
(+ a (* b c))       ; a + b * c

Note that there are no precedence or associativity rules. All operations are explicitly grouped by parentheses:

(* (+ a b) (- c d))  ; in math: (a + b) * (c - d)

The semicolon introduces a comment. Everything between the ; and the end of the same line is ignored by Scheme systems.

In Scheme, operators like + or * are ordinary procedures. A procedure is a small program that receives some values and returns a result, just like a mathematical function. The terms procedure and function are used as synonyms in this text.

The values passed to a procedure are called arguments. Because all procedure applications are delimited using parentheses, many procedures can have any number of arguments. For example, the expression a+b+c+d would be written as

(+ a b c d)

Like math functions, Scheme procedures return a result that depends on the values passed to the procedure:

(+ 5 7) => 12
(+ 7 9) => 16

The double arrow => is not really part of Scheme, but it is frequently used to denote the value of an expression. In Scheme, everything that has a value is called an expression. (+ 5 7) is an expression, but 5 and 7 are also expressions. Scheme programs are formed by combining expressions.

The formula a => b reads a evaluates to b or a reduces to b. Above formula means the application of + to 5 and 7 evaluates to 12. All procedure applications have the same form: the first position between two parentheses is occupied by the procedure and the remaining positions contain arguments:

(procedure argument1 ... argumentn) => value

Some procedures have a fixed number of arguments, some have a minimum number of arguments, and some accept any number of arguments. For instance, the - procedure requires at least one argument:

(- 5)      => -5
(- 5 7)    => -2
(- 10 2 3) => 5
(-)        => bottom

When a single argument is passed to it, it negates it. When more than one argument is passed to it, it subtracts all but the first of its arguments from the first one. Passing no arguments at all to - is an error and the application reduces to bottom. Bottom denotes an undefined value. Of course, when actually entering an erroneous expression at a Scheme prompt, the system will not just print bottom but a more explanative message. The formula

e => bottom

merely states that something about the expression e is not correct. For instance, it could be used to state that the division by zero is not allowed:

(quotient x 0) => bottom

Note that above formula is not valid Scheme, because the variable x is not known without a corresponding declaration. It should be read as (quotient x 0) reduces to bottom for any value of x. Such formulae are frequently used to describe the behavior of procedures in a formal way.

Most Scheme procedures are strict. This means that a procedure that has at least one argument of bottom also reduces to bottom:

(eq? (quotient 0 0) 0) => bottom

Although the eq? procedure (which compares its two arguments) theoretically could find out that 0/0 is not equal to 0 and reduce to falsity, it does not. Because eq? is strict, it must evaluate to bottom as soon as at least one of its arguments evaluates to bottom. From a more practical point of view, this means that the evaluation of above expression would abort with an error message explaining that a division by zero was attempted. All Scheme programs abort as soon as a reduction to bottom occurs.