SketchyLISP Reference Manual - Copyright (C) 2005 Nils M Holm

3 Reduction Rules

3.1 Introduction

Each SketchyLISP expression may be reduced using the following rules. If more than one reduction is possible, the order of application is call-by-value, ie inner expressions are evaluated first. The terms reduction and evaluation are synonyms in this manual. When no rules can be applied to an expression, that expression is said to be in its normal form.

The arrow operator

x => y

means x reduces to y. The notation

eval[x]

is used to denote the normal form of x. The operator

s[x/y]

denotes the substitution of each symbol x in s by y.

In each step, the resulting expression is different from the original one. Expressions never get changed in SketchyLISP, but only rewritten. This process is similar to rewriting a term by hand: adding a new line to the bottom of a number of rewritten terms does not change any of the above lines.

3.2 Atoms

Symbols reduce to the expressions they are bound to. Bindings of symbols to expressions are created by the define, lambda, and letrec pseudo functions, which will be explained later. It is an error to refer to symbols that are not (or not yet) bound to a value, ie

unbound-symbol => undefined

Booleans, numbers, chars, and strings are always in their normal forms:

   #t => #t
  123 => 123
  #\y => #\y
"Hi!" => "Hi!"

Procedures are either closures or continuations. They are created by the primitive functions lambda and call/cc.

(lambda (x) x) => #<closure (x)>
(call/cc (lambda (k) k)) => #<continuation>

Both closures and continuations will be explained in the sections on lambda and call/cc of the following chapter.

3.3 Lists

The first member of each list is reduced to its normal form. If the normal form of the first member is not one of these symbols

cond, define, lambda, letrec, quote

then the remaining members are also reduced to their normal forms.

Formally: if eval[a1] is not in {cond, define, lambda, letrec, quote}, then

(a1 a2 ... aN) => (eval[a1] eval[a2] ... eval[aN])

and otherwise

(a1 a2 ... aN) => (eval[a1] a2 ... aN)

In other words, arguments of the above pseudo functions are passed by name, while all other arguments are passed by value.

Subsequent steps will be performed with the above reductions in effect.

3.4 Primitive Functions

If the first member of a list is a symbol which denotes a primitive operation of SketchyLISP, this operation is applied to the remaining members of the list:

(primitive a2 ... aN) => primitive(a2, ..., aN)

where primitive(...) denotes the application of a built-in function of the interpreter. (For a summary of primitive functions see the following chapter.)

3.5 Lambda Functions

A lambda function is an expression of the form

(lambda (x) t)

(X) is called the argument list of the lambda function, x is a formal argument (or a variable) of the function, and t is the term (or body) of the function.

If the first member of a list is a lambda function, then the list denotes the application of that lambda function to some arguments:

((lambda (x) t) y)

An expression that a function is being applied to is called an actual argument or just an argument. In the above application, y is the only actual argument.

Applications of lambda functions are reduced in two steps. The first step is called beta reduction. In this step, the expression is reduced by substituting each free symbol x that occurs in t by y, resulting in t':

((lambda (x) t) y) => t[x/y] = t'

A symbol x is free in a term t, if

For example, x is free in

(lambda (y) x)

but it is not free in

(lambda (x) x)

A variable that is not free in an expression is said to be bound in that expression. Note especially that x is bound in (lambda (x) t) but free in the t of (lambda (x) t).

A variable is said to be bound in a lambda expression, because applying the lambda function to a value binds the variable to an argument. Referring to a variable x that is bound to a value y yields y. In the following example, the variable x is bound to the argument y.

((lambda (x) t) y) ; x is bound to y

Because a lambda function may have more than one single argument, the more general form of the reduction of its application is

((lambda (x1 ... xN) t) y1 ... yM) => t[x1/y1] ... [xN/yM] = t'

The number of the formal arguments of lambda (n) must exactly match the number of actual arguments (m) in function applications. If the numbers do not match, the normal form of the expression is undefined.

When binding multiple arguments during a function application, variables are bound to arguments by position (the = sign denotes a binding):

((lambda (a b c) t) x y z) ; a=x, b=y, c=z

In the second step during the evaluation of a list, the resulting expression t' is reduced to its normal form using any reduction rule described in this chapter:

t' => eval[t']

The result of this step is the result of the entire reduction. The entire reduction may be written as:

((lambda (x1 ... xN) t) y1 ... yN) => eval[ t[x1/y1] ... [xN/yN] ]

3.6 Variadic Lambda Functions

A lambda function whose argument list is an improper list (or even a single symbol) is called a variadic function. Such a function expects at least one actual argument for each formal argument preceding the dot of its improper argument list. For example, the following lambda function accepts one or more (actual) arguments:

(lambda (a . b) x)

This function expects at least three arguments:

(lambda (a b c . d) x)

The symbols preceding the dot are bound to arguments as described in the previous section. The variable following the dot is bound to the rest of the list of actual arguments. The rest of this list is the list of actual arguments after removing each member that already has been bound to a symbol:

((lambda (a . b) b) 'foo 'bar)      => '(bar)
((lambda (a . b) b) 'foo 'bar 'baz) => '(bar baz)

If the rest of the argument list is empty, the symbol after the dot is bound to ().

((lambda (a . b) b) 'foo) => '()

The argument list of a lambda function may consist of one single symbol (so in fact it is not a list at all). In this case, the complete list of actual arguments is bound to that symbol:

((lambda a a) 'foo)      => '(foo)
((lambda a a) 'foo 'bar) => '(foo bar)

If no arguments are passed to a function with an atomic argument list, () is bound to the argument symbol:

((lambda a a)) => '()

3.7 Empty Lists

The empty list () is always in its normal form:

() => ()

Note: R5RS Scheme requires empty lists to be quoted. In SketchyLISP quotation of empty lists is optional.

3.8 Other Lists

If the first member of a list is not a procedure, the normal form of the list is undefined.

(() a2 ... aN) => undefined
(undefined a2 ... aN) => undefined