t3x.org / sketchy / sk03.html
SketchyLISP
Reference
  Copyright (C) 2007
Nils M Holm

3 Syntax

3.1 Summary

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.

3.2 Quotation

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)

3.2.1 quote

(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.

3.3 Procedures

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

3.3.1 Variadic Procedures

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)

3.3.2 Primitive Procedures

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.

3.4 Binding Constructs

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

3.4.1 define

(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:

3.4.2 let

(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.

3.4.3 let*

(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.

3.4.4 letrec

(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.

3.5 Lexical and Dynamic Scoping

3.5.1 Bound and Free Variables

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.

3.5.2 Dynamic Scoping

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.

3.5.3 Lexical Scoping

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

3.6 Conditional Evaluation

3.6.1 and

(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.

3.6.2 begin

(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.

3.6.3 case

(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:

3.6.4 cond

(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:

3.6.5 if

(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:

3.6.6 or

(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.