SketchyLISP Reference Manual - Copyright (C) 2005 Nils M Holm
Previous: Programs | - Contents - Index - | Next: Primitive Functions |
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.
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.
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.
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.)
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] ]
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)) => '()
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.
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
Previous: Programs | - Contents - Index - | Next: Primitive Functions |