T3X.ORG : Sketchy LISP

An Introduction to Functional Programming in Scheme

By Nils M Holm, 2006,2007,2008,2009 (contact)

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 by 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 them:

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

The double arrow ==> is not really part of Scheme, but 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 notation a ==> b reads "a evaluates to b" or "a reduces to b", so (+ 5 7) ==> 12 means "the application of + to 5 and 7 evaluates to 12". All procedure applications share 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
(-)         ==>  undefined

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 an undefined value. Of course, when actually entering an erroneous expression at a Scheme prompt, the system will not just print "undefined" but a more explanative message. The notation

e  ==>  undefined

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)  ==>  undefined

Note that above form is not valid Scheme, because the variable x is not known without a corresponding definition. It should be read as "(quotient x 0) reduces to an undefined value for any argument x". Such forms are frequently used to describe the behavior of procedures in a formal way.

Scheme procedures are strict. This means that a procedure that has at least one argument with an undefined value also reduces to an undefined value:

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

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, its value is undefined as soon as at least one of its arguments evaluates to an undefined value. 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 an undefined value occurs.