SketchyLISP Reference |
Copyright (C) 2007 Nils M Holm |
[<<Programs] | [Contents] [Index] | [Primitive Functions>>] |
3.1 Summary
3.2 Quotation
3.3 Procedures
3.4 Binding Constructs
3.5 Lexical Closures
3.6 Conditional Evaluation
The syntax of SketchyLISP is divided into categories:
Except for syntax transformers, these constructs will be explained in this chapter. Syntax transformers, which are used to form new syntaxes on top of existing ones, are later described in an individual chapter.
All SketchyLISP syntaxes look like a procedure application
with a keyword (like quote
) in the place of the
procedure:
(quote (+ 1 2))
Unlike procedures, syntax objects are called by name. That is, arguments are not evaluated before passing them to syntax objects. Therefore
(quote (+ 1 2)) => (+ 1 2)
Some syntax objects will evaluate arguments at a later time.
The normal form of a form x that is passed to a syntax
object is denoted by eval[x]
,
e.g.:
(if #t x y) => eval[x]
Values without an unambiguous normal form cannot occur in programs, but they can be returned by functions. Such values include, for example:
#<procedure ...> #<eof> #<void>
The
#<void>
value is used to
denote that the value returned by a function is unspecific, i.e.
uninteresting.
Syntactically, all values starting with the prefix
#<
are unreadable. They can print, but they cannot be
read by the SketchyLISP parser.
Booleans, numbers, chars, strings, and vectors are auto-quoting data. They are always in their normal forms:
#t => #t 123 => 123 #\y => #\y "\"Hi!\"" => "\"Hi!\"" #(x y z) => #(x y z)
(quote x) => x
Quote
turns the form passed to it into a datum:
symbol => value of symbol (quote symbol) => symbol (#f) => bottom (quote (#f)) => (#f) (+ 1 2) => 3 (quote (+ 1 2)) => (+ 1 2)
The notation 'x
is equal to
(quote x)
:
'(x y) => (x y) (quote (x y)) => (x y)
The quote
syntax conforms to R5RS.
Each lambda expression evaluates to a procedure:
(lambda (x y) (+ x y)) => #<procedure (x y)>
The (x y)
after the lambda
keyword is
called the argument list
of the procedure, x and y are the
formal arguments or
variables, and
(+ x y)
is the body
of the procedure.
A procedure is applied to some
actual arguments
(or just arguments
)
using parentheses:
((lambda (x y) (+ x y)) 5 7) => 12
This expression applies the procedure created by lambda
to the arguments 5 and 7, giving 12.
When a procedure is applied to some arguments, it binds each actual argument to a variable. Bindings are established by position, so
((lambda (x y) (+ x y)) 5 7)
binds x to 5 and y to 7.
A set of bindings is called an environment. The body of a procedure is evaluated inside of the environment created by binding variables to arguments, so when
(lambda (x y) (+ x y))
is applied to 5 and 7,
(+ x y)
is evaluated inside of an environment that binds x
to 5 and y to 7. The +
function computes
the sum of some numbers, so the body of the function evaluates to
12.
The result of the function is the value of its body.
As soon as a function returns its result, its environment ceases to exist.
SketchyLISP procedures are called by value. This means that inner applications are always evaluated first, and the normal forms of inner expressions are passed to outer procedures:
(+ (* 2 3) (* 3 4))
is evaluated by first reducing (* 2 3)
and (* 3 4)
to their normal forms in no
specific order and then evaluating:
(+ 6 12)
Procedures may have any number of variables:
((lambda () 'foo)) => foo ((lambda (x) (- x)) 1) => -1 ((lambda (x y) (* x y)) 4 5) => 20 ((lambda (x y z) (* x (+ y z))) 3 2 1) => 9
Some procedures (like +
) accept a variable
number of arguments:
(+) => 0 (+ 2) => 2 (+ 2 3) => 5 (+ 2 3 7) => 12
Such procedures are called variadic procedures. A variadic procedure is created by a lambda expression with an improper argument list. For instance, the function
(lambda (a b . c) c)
accepts two or more arguments. The first two arguments are bound to a and b and the rest of the list of formal arguments is bound to c:
((lambda (a b . c) c) 1 2) => () ((lambda (a b . c) c) 1 2 3) => (3) ((lambda (a b . c) c) 1 2 3 4) => (3 4)
The variables before the dot bind to mandatory arguments and the dotted variable binds to the list of optional arguments, which may be empty.
There may by any positive number of variables before the dot:
(lambda (a . b) b) (lambda (a b . c) c) (lambda (a b c . d) d)
To create a function that has only optional arguments,
the argument list of lambda
is replaced with a single
variable:
(lambda a a)
Such a function binds a list of all arguments to its only variable:
((lambda a a)) => () ((lambda a a) 1) => (1) ((lambda a a) 1 2) => (1 2) ((lambda a a) 1 2 3) => (1 2 3)
A primitive procedure is a procedure that is not implemented in SketchyLISP for reasons of convenience, efficiency, implementation strategy, or whatever.
Technically, primitive procedures form the core of the language and the more abstract procedures are implemented on top of primitives.
To the programmer, there is no difference between a primitive
procedure and a procedure created by lambda
.
Symbols are used as variables. They reduce to their values:
symbol => value
Variables are assigned values by binding constructs, which will be explained in this section.
It is an error to refer to a variable that is not bound to any value:
unbound-symbol => bottom
(define y x) => #<void>
Define
introduces a symbol (y) and binds
it to the normal form of an expression (x).
The value of the expression is bound to the symbol in the
global environment.
This means that a binding established by define
is visible in an entire program.
Define
is used in association with
lambda
to create new functions:
(define f (lambda (x) body))
Functions may also be defined using the following, shorter notation:
(define (f x) b) = (define f (lambda (x) b)) (define (f x . y) b) = (define f (lambda (x . y) b)) (define (f . x) b) = (define f (lambda x b))
Functions created using define
may be mutually
recursive:
(define (d1 x) (and (> x 0) (d2 (- x 1)))) (define (d2 x) (and (> x 0) (d1 (- x 1))))
Applications of define
may not occur inside of other
expressions.
The define
syntax conforms to R5RS with one restriction:
define
may appear inside of local contexts.(let ((x1 v1) ... (xn vn)) body) => eval[body]
Let
binds each symbol xi to
eval[vi], thereby forming a local environment.
The expression body is evaluated inside of that local
environment. The normal form of body is the normal form
of the entire let
expression.
Let
first evaluates all values
v1..vn and then
binds their normal forms to the symbols
x1..xn. Therefore, variables
in the values v1..vn of
let
are either unbound or bound in the outer context of
that let
:
(let ((x 'outer)) (let ((x 'inner) (y x)) y)) => outer
Except for its syntax, the let
construct is perfectly
equal to the application of a lambda function:
(let ((x 3) ((lambda (x y) (y 4)) = (* x y)) (* x y)) 3 4)
The let
syntax conforms to R5RS.
(let* ((x1 v1) ... (xn vn)) body) => eval[body]
Let*
is like let
, but binds values
sequentially. It first evaluates v1 and binds
it to x1. Then it evaluates v2
in the environment that binds x1 to
v1, etc:
(let* ((a 1) (b (+ 1 a)) (c (+ 1 b))) c) => 3
In SketchyLISP, let*
is a syntax transformer that
transforms
(let* ((x1 v1) into (let ((x1 v1)) ... ... (xn vn)) (let ((xn vn)) body) body)...)
The let*
syntax conforms to R5RS.
(letrec ((x1 v1) ... (xn vn)) body) => eval[body]
Letrec
binds each symbol xi to
eval[vi], thereby forming a local environment. The
expression body is evaluated inside of that local
environment. The normal form of body is the normal form
of the entire letrec
expression.
Letrec
is basically equal to let
, but after
binding its values to its arguments, it fixes recursive bindings (using
recursive-bind
). Hence it can be used to bind recursive or
even mutually recursive functions:
(letrec ((d1 (lambda (x) (and (> x 0) (d2 (- x 1))))) (d2 (lambda (x) (and (> x 0) (d1 (- x 1)))))) (d1 10)) => #f
It is an error for a value of letrec
to refer
to a name of the same letrec
:
(let ((complement (lambda (p) (lambda (x) (not (p x)))))) (letrec ((one? (lambda (x) (= 1 x))) (not-one? (complement one?))) (not-one? 0))) => bottom
The letrec
syntax conforms to R5RS.
A variable is bound in an expression, if the expression is a binding construct and the variable is assigned a value by that construct.
For example, the variable x is bound in
(let ((x 1)) x)
and in
(lambda (x) x)
In the second example, the value of x is not known before the resulting procedure is applied to it.
A variable is free in an expression, if it is not bound in that expression. For example x is free in the following expressions:
(let ((y 1)) (+ x y)) (lambda (y z) (+ x y z))
This section discusses the values of free variables in the bodies of lambda expressions.
When a function is defined using define
, all free
variables of the resulting procedure are bound in the global
context. For instance, in
(define (d1 x) (and (> x 0) (d2 (- x 1))))
the variable d2 is not bound at all. Defining d2 at a later time changes the value of d2 in d1 dynamically:
(define (d2 x) (and (> x 0) (d1 (- x 1))))
Because this method changes the value of a variable dynamically, it is called dynamic scoping.
Here is another example:
(define v 'lexical-scoping) (define (p) v) (define v 'dynamic-scoping) (p) => dynamic-scoping
SketchyLISP uses dynamic scoping in global procedures, because it is a simple means of defining mutually recursive procedures like d1 and d2 above.
When lexical scoping is used, procedures capture the values of free variables when they are created:
(let ((v 'lexical-scoping)) (let ((p (lambda () v))) (let ((v 'dynamic-scoping)) (p)))) => lexical-scoping
The procedure p captures the value of v in
its lexical context. The lexical context of a procedure is
the context in which it is defined. When p is defined,
v is bound to 'lexical-value
, so the procedure
memorizes this value.
When p is applied at a later time, the dynamic change of v does not matter, because p carries an internal copy of the lexical binding of v.
The place where a procedure stores the bindings of free variables is called the lexical environment of that procedure.
A procedure with a lexical environment is sometimes also called a
closure. A procedure that captures
the bindings of a set of variables is said to close over
those variables.
Note
Because procedures close over free variables in local contexts,
it is impossible to create a recursive procedure using let
:
(let ((d (lambda (x) 'wrong!))) (let ((d (lambda (x) (and (> x 0) (d (- x 1)))))) (d 1))) => wrong!
In the inner let
, lambda
closes over
the outer d before binding the procedure to the
inner d.
This is exactly the problem which letrec
fixes:
(let ((d (lambda (x) 'wrong!))) (letrec ((d (lambda (x) (and (> x 0) (d (- x 1)))))) (d 1))) => #f
(and expr1 ...) => value
And
evaluates the given expressions from the left
to the right. When an expression reduces to logical falsity,
and
returns #f
immediately and does not
evaluate any further expressions. When no argument of and
evaluates to #f
, the normal form of the last expression
is returned.
And
can be defined in terms of if
as follows:
(and x) = x (and x1 x2) = (if x1 (if x2 x2 #f) #f) (and x1 x2 ...) = (if x1 (and x2 ...) #f)
The following rules apply:
(and) => #t (and 'foo) => foo (and #f) => #f (and #t 'foo) => foo (and #t #f) => #f (and #f 'foo) => #f (and #f #f) => #f (and 'foo 'bar) => bar (and 1 2 3) => 3
The and
syntax conforms to R5RS.
(begin expr1 ... exprn) => eval[exprn]
Begin
reduces each of the given expressions to their normal
form. Expressions are reduced from the left to the right. The normal form of
each but the last expression is discarded. The normal form of the last
expression is returned.
The only effect of begin
is to make sure that the given
expressions are reduced in the given order:
(begin x1 x2 x3)
is equivalent to (but obviously more readable than):
((lambda (x) x3) ((lambda (x) x2) x1))
Begin
is used to group expressions with side effects
(see input/output primitives):
(begin (write 1) (write 2))
is guaranteed to write 12
while
((lambda x x) (write 1) (write 2))
may write either 12
or 21
.
The following rules apply:
(begin) => #<void> (begin 'foo) => foo (begin 'a 'b 'c) => c
The begin
syntax conforms to R5RS.
(case key ((data1) expr1) ...) => value
Case
first evaluates the expression key. It
then checks whether (the normal form of) key is contained
in the sequence of atoms data1. If this is the
case, the normal form of expr1 is returned, and
the subsequent cases are left unchecked. If key is not in
the sequence of the current case, case
checks the next
case until it finds a matching one.
The last case may contain the keyword else
instead of
(datan)
. This keyword introduces the default
case which matches any key.
In SketchyLISP, case
is a syntax transformer that
transforms
(case key (d1 x1) ... (dn xn) (else y))
into
(if (memv key d1) x1 ... (if (memv key dn) xn y) ...)
Then following rules apply:
(case 'b ((a) 'a) ((b) 'b) ((c) 'c)) => b (case 1 ((1) 'a) ((1) 'b)) => a (case 'foo (else 'bar)) => bar (case 'b ((a b c) 'abc) (else 'bar)) => abc (case 'foo ((bar) 'bar)) => bottom
The case
syntax conforms to R5RS with one restriction:
case
is allowed to run out of cases,
returning an unspecific value.(cond (p1 e1) ...) => value
Each argument of cond
must be
a clause of the form
(pj ej)
where the normal form of pj is interpreted as a truth value.
Cond
first evaluates p1. If it
reduces to a true
value (something other than #f
),
cond
evaluates e1 and returns it.
No other clauses are evaluated in this case. If p1
reduces to falsity, cond
does not evaluate
e1 and proceeds with p2.
It iterates though the clauses until a true predicate is found.
The keyword else
may be used instead of #t
to introduce the default clause, which must be last.
The following rules apply:
(cond (#t 1) (x2 2)) => 1 (cond (#f 1) (#t 2)) => 2 (cond (else 'foo)) => foo (cond (#f x)) => bottom
The cond
syntax conforms to R5RS with one restriction:
cond
is allowed to run out of clauses,
returning an unspecific value.(if p c a) => value
If
first evaluates the predicate p.
If p evaluates to a true value, if
evaluates the consequent c and returns its value.
Otherwise the normal form of the alternative a is
returned.
If
is just a shorthand form of cond
:
(if p c a) = (cond (p c) (else a))
The following rules apply:
(if #t 'true 'false) => true (if #f 'true 'false) => false
The if
syntax conforms to R5RS with one restriction:
if
may be called without an alternative,
returning an unspecific value if the predicate evaluates to
#f
.
(or expr1 ...) => value
Or
evaluates the given expressions from the left
to the right. When an expression reduces to logical truth,
or
returns its value immediately and does not evaluate
any further expressions. When no argument of or
evaluates to truth, the normal form of the last expression is
returned.
Or
can be defined in terms of cond
as follows:
(or x) = x (or x1 ... xn) = (cond (x1 x1) ... (xn xn) (else #f))
The following rules apply:
(or) => #f (or 'foo) => foo (or #f) => #f (or #t 'foo) => #t (or #t #f) => #t (or #f 'foo) => foo (or #f #f) => #f (or 'foo 'bar) => foo (or #f #f 3) => 3
The or
syntax conforms to R5RS.
[<<Programs] | [Contents] [Index] | [Primitive Functions>>] |