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

4 Primitive Functions

4.1 Introduction

Primitive functions are those functions that cannot be expressed in terms of SketchyLISP in a practical way. These functions form the core of the language. Some of the primitives listed in this chapter are in fact pseudo functions. Their applications look like function applications, but their semantics differ from regular function applications in one detail: all pseudo functions are called by name.

In this section a symbol is called a symbol only if it is quoted. Otherwise it is called a variable. Eg, 'x denotes a symbol and x denotes a variable.

At the beginning of each function description, a generalized sample application is given. This application lists the types that the function expects by giving examples:

(car '(x.y)) => 'x

Unless such an example uses a variable as argument, it is an error to apply the function to a type other than that specified in the example:

(car 'non-pair) => bottom

When a variable is used as an argument, the function accepts any type:

(pair? x) => {#t,#f}

The symbol bottom is used to denote an undefined value. A value is undefined, if it does not have a unique normal form. This does not imply that a reduction that results in bottom terminates with an error. It rather says that the result of the reduction should be considered invalid.

As an example, assume that both the symbols x and y are bound to the numeric value 457. Given these bindings, the expression

(eq? x y)

may reduce to #t or #f, since the identity of instances of numbers is arguable. Because the result is not predictable, it must be considered undefined.

4.2 Bindings and Definitions

4.2.1 bottom

(bottom ...) => bottom

(Bottom) evaluates to an undefined result. Any expression that contains a subexpression evaluating to (bottom) evaluates itself to (bottom). The bottom function may have any number of arguments.

(bottom)           => bottom
(bottom 'x 'y 'z)  => bottom
(eq? (bottom) ())  => bottom

The bottom function is specific to SketchyLISP.

4.2.2 define

(define x y) => 'x

Define binds the normal form of y to the symbol x:

(define x y) => 'x ; x := eval[y]

The notation x := y denotes that the value of y is bound to x globally. A binding is global, if it is visible in an entire program.

Since its arguments are passed to define call-by-name, it does not matter what x is bound to when define is applied. The previous binding of x is lost.

Define is used in association with lambda to create new functions:

(define f (lambda (x) t))

Functions created using define may be mutually recursive.

Applications of define may not occur inside of other expressions.

The define pseudo function conforms mostly to R5RS. It differs from R5RS in this points:

4.2.3 lambda

(lambda (x1 ... xN) t) => #<closure (x1 ... xN)>

Applications of lambda reduce to lexical closures. If the term t of a lambda expression

(lambda (x) t)

contains any free variables, an association list (a list of key/value pairs) is added to the resulting closure. For example,

(letrec ((y 'foo))
   (lambda (x) (cons y x)))
=> #<closure (x) (cons y x) ((y.foo))>

(The function term and the environment normally do not print in closures, but the :k 2 meta command can be used to make them visible.)

The association list '((y.foo)) is called the lexical environment of the closure. When a closure is applied to a value, its free variables get bound to the values stored in the environment:

((lambda (x) (cons y x) ((y.foo))) 'bar)  =>  '(foo.bar)

The lambda pseudo function mostly conforms to R5RS. It differs from R5RS in the following point:

4.2.4 letrec

(letrec ((x1 y1) ... (xN yN)) z) => eval[z]

Letrec binds each symbol Xi to eval[Yi], thereby forming a local environment. The expression z is evaluated inside of that local environment. The normal form of z is the normal form of the entire letrec expression.

Letrec may be used to create mutually recursive functions:

(letrec ((even-p (lambda (x)
        (cond ((null? x) #t)
            (#t (odd-p (cdr x))))))
    (odd-p (lambda (x)
        (cond ((null? x) #f)
            (#t (even-p (cdr x)))))))
    (list (odd-p '(i i i))
        (even-p '(i i i))))
=> '(#t #f)

It is an error for a binding of letrec to refer to the value of another binding of the same letrec:

(letrec ((foo 'outer-value))
    (letrec ((foo 'inner-value)
        (bar foo))
            bar))
=> bottom

The letrec pseudo function conforms to R5RS.

4.2.5 quote

(quote x) => 'x

Quote evaluates to its single argument. Because arguments to quote are passed to it call-by-name, (quote x) always results in 'x while x itself would reduce to eval[x]. Quote is used to quote expressions which are not to be evaluated:

(())                 => bottom
(quote (()))         => '(())
(car '(x.y))         => 'x
(quote (car '(x.y))) => '(car '(x.y))

The notation 'x is equal to (quote x):

'(x y) = (quote (x y)) => '(x y)

The quote pseudo function conforms to R5RS.

4.3 Control

4.3.1 apply

(apply fun list) => eval[(fun.list)]

Apply applies the given function (fun) to the arguments contained in the given list. Both fun and list are passed to apply call-by-value, but fun is applied to the arguments in list call-by-name. The number of arguments of fun must match the number of members of list. For example,

(apply cons '(a b))           => '(a.b)
(apply (lambda () 'foo) '())  => 'foo
(apply cons '(a))             => bottom

The apply function conforms to R5RS.

4.3.2 call/cc

(call/cc f) => expression

(Call/cc f) captures the current continuation and passes it to f. F must be a function of one argument. The following conversion takes place:

(call/cc f) => (f #<continuation>)

The current continuation (represented by #<continuation>) is the part of an expression that will be evaluated next. For example, in

(cons 'foo (call/cc (lambda (k) 'bar)))

the (current) continuation of

(call/cc (lambda (k) 'bar))

is

(cons 'foo _)

where _ denotes the not-yet-evaluated application of call/cc.

Applications of call/cc reduce to the result of the function passed to call/cc unless this function applies its argument. For instance:

(call/cc (lambda (ignored) 'foo)) => 'foo

If the function passed to call/cc applies the captured continuation passed to it, though, the current context of the formula is discarded and replaced with the captured continuation. The application of call/cc in the restored context reduces to the argument of the continuation:

(cons 'foo (call/cc (lambda (k) (k 'bar))))
=> (cons 'foo ((lambda (k) (k 'bar)) #<continuation>))
=> (cons 'foo (#<continuation> 'bar))
=> (cons 'foo 'bar)

The current continuation of the application of a captured continuation is discarded, so:

(cons 'foo (call/cc (lambda (k) (cons 'zzz (k 'bar)))))
=> (cons 'foo ((lambda (k) (cons 'zzz (k 'bar))) #<continuation>))
=> (cons 'foo (cons 'zzz (#<continuation> 'bar)))
=> (cons 'foo 'bar)

Because activating the continuation k replaces the current context with the one previously captured by call/cc, the

(cons 'foo (cons 'zzz _))

part is thrown away and replaced with

(cons 'foo _) 

Finally, the application of call/cc is replaced with the value passed to k.

Because call/cc can be used to expose the order of evaluation of function arguments, the reduction of lists - as explained in the previous chapter - is extended as follows:

Members of lists are evaluated from the left to the right, so each Ai is guaranteed to be evaluated before Aj, if i<j in

(a1 ... aN)

Consequently,

(call/cc (lambda (k) (#f (k 'foo) (k 'bar)))) => 'foo

Note that this extension applies to SketchyLISP, but not to Scheme.

Once captured, continuations have indefinite extent. As long as they can be referred to using a symbol, they remain valid. Therefore they can be applied any number of times and even after returning from call/cc.

The call/cc function conforms to R5RS.

4.3.3 cond

(cond (p1 e1) ... (pN eN)) => e#T

The arguments of cond are passed to it call-by-name. Each argument of cond must be a clause of the form

(Pj Ej)

where Pj must evaluate to a boolean. Ej may be of any type.

Cond first evaluates P1. If it reduces to #t, cond evaluates E1. In this case, E1 is the normal form of the entire cond expression. Otherwise cond does not evaluate E1 and proceeds with the following arguments until a clause with Pj=#t is found. The following rules apply.

(cond (x y) (x2 y2)) => eval[y], if eval[x]=#t
(cond (x y) (x2 y2)) => (cond (x2 y2)), if eval[x]=#f
(cond (x y) (x2 y2)) => bottom, if eval[x] not in {#t,#f}
(cond (x y))         => bottom, if eval[x]=#f

The cond pseudo function mostly conforms to R5RS. It differs from the R5RS version in these point:

4.4 Composition and Decomposition

4.4.1 car

(car '(x.y)) => 'x

(Car x) evaluates to the car part of x. X must be a pair. The following rules apply:

(car '(x.y))    => 'x
(car '(x y))    => 'x
(car '(x))      => 'x
(car ())        => bottom
(car 'non-pair) => bottom

The car function conforms to R5RS.

4.4.2 cdr

(cdr '(x.y)) => 'y

(Cdr x) evaluates to the cdr part of x. X must be a pair. The following rules apply:

(cdr '(x.y))    => 'y
(cdr '(x y))    => '(y)
(cdr '(x))      => '()
(cdr ())        => bottom
(cdr 'non-pair) => bottom

The cdr function conforms to R5RS.

4.4.3 cons

(cons x y) => '(x.y)

Cons creates a new pair from two given expressions. Its first argument x forms the car part of the new pair and its second argument y forms the cdr part. The following rules apply:

(cons 'x 'y)      => '(x.y)
(cons 'x ())      => '(x)
(cons 'x '(y.())) => '(x y)
(cons 'x '(y))    => '(x y)
(cons 'x '(y.z))  => '(x y.z)

Note: '(x y.z) is a called an improper list or a dotted list, because its last element is not equal to ():

(cdr (cdr '(x y.z))) =/= '()

The cons function conforms to R5RS.

4.5 Predicates

4.5.1 char?

(char? x) => {#t,#f}

(Char? x) evaluates to #t if x is a char literal and otherwise to #f. The following rules apply:

(char? #\x)       => #t
(char? #\space)   => #t
(char? #\\)       => #t
(char? 'non-char) => #f

The char? function conforms to R5RS.

4.5.2 eq?

(eq? x y) => {#t,#f}

(Eq x y) evaluates to #t if x and y are identical and otherwise to #f. Two expressions are identical, if, and only if they are the same symbol or they are both the same boolean literal or they are both empty lists. All other atoms as well as pairs may be different, even if they look equal. Objects bound to the same symbol are always identical, so

(eq a a) => #t

even if a is a variable. The following rules apply:

(eq? x x)           => #t
(eq? 'x 'x)         => #t
(eq? 'x 'y)         => #f
(eq? () ())         => #t
(eq? 'x '(x.y))     => #f
(eq? #f #f)         => #t
(eq? '(x.y) '(x.y)) => bottom
(eq? '(x y) '(x y)) => bottom
(eq? 123 123)       => bottom
(eq? #\x #\x)       => bottom
(eq? "foo" "foo")   => bottom

The eq? function conforms to R5RS.

4.5.3 null?

(null? x) => {#t,#f}

(Null? x) evaluates to #t if x is equal to () and otherwise to #f. It easily may be defined using the SketchyLISP function

(define null? (lambda (x) (eq? x ())))

but for reasons of efficiency, it has been implemented as a primitive function.

The null? function conforms to R5RS.

4.5.4 number?

(number? x) => {#t,#f}

(Number? x) evaluates to #t if x is a numeric literal and otherwise to #f. The following rules apply:

(number? 123)          => #t
(number? -123)         => #t
(number? +123)         => #t
(number? 'non-integer) => #f

The number? function conforms to R5RS.

4.5.5 pair?

(pair? x) => {#t,#f}

Applications of pair? evaluate to #t if x is a pair and otherwise to #f. The following rules apply:

(pair? '(x.y))    => #t
(pair? '(x y))    => #t
(pair? ())        => #f
(pair? 'non-pair) => #f

The pair? function conforms to R5RS.

4.5.6 procedure?

(procedure? x) => {#t,#f}

(Procedure? x) evaluates to #t if x is a procedure and otherwise to #f. The following objects are procedures:

The following rules apply:

(procedure? cons)       => #t
(procedure? procedure?) => #t
(procedure? (lambda (x) x))           => #t
(procedure? (call/cc (lambda (k) k))) => #t
(procedure? 'non-procedure)           => #f

The procedure? function conforms to R5RS.

4.5.7 string?

(string? x) => {#t,#f}

(String? x) evaluates to #t if x is a string literal and otherwise to #f. The following rules apply:

(string? "some text") => #t
(string? "")          => #t
(string? 'non-string) => #f

The string? function conforms to R5RS.

4.5.8 symbol?

(symbol? x) => {#t,#f}

(Symbol? x) evaluates to #t if x is a literal symbol and otherwise to #f. The following rules apply:

(symbol? 'foo)         => #t
(symbol? 'symbol?)     => #t
(symbol? symbol?)      => #f
(symbol? "non-symbol") => #f

The symbol? function conforms to R5RS.

4.6 Type Conversion

4.6.1 char->integer

(char->integer #\c) => integer

The char->integer function evaluates to an integer whose value is equal to the ASCII code of its argument. The following rules apply:

(char->integer #\a)       => 97
(char->integer #\A)       => 65
(char->integer #\space)   => 32
(char->integer #\\)       => 92
(char->integer 'non-char) => bottom

The char->integer function conforms to R5RS.

4.6.2 integer->char

(integer->char 123) => char

The integer->char function evaluates to a char literal whose ASCII code is equal to its argument. The argument must be in the range 0..127. The following rules apply:

(integer->char 97)           => #\a
(integer->char 65)           => #\A
(integer->char 32)           => #\space
(integer->char 92)           => #\\
(integer->char 'non-integer) => bottom
(integer->char -1)           => bottom
(integer->char 128)          => bottom

The integer->char function conforms to R5RS.

4.6.3 integer->list

(integer->list 123) => list

The integer->list function evaluates to a list containing the digits and, if one exists, the prefix of the given integer. Digits are represented by the symbols 0-digit through 9-digit. The following rules apply:

(integer->list 0)            => '(0-digit)
(integer->list 123)          => '(1-digit 2-digit 3-digit)
(integer->list -5)           => '(- 5-digit)
(integer->list +7)           => '(+ 7-digit)
(integer->list 'non-integer) => bottom

The integer->list function is specific to SketchyLISP.

4.6.4 list->integer

(list->integer list) => integer

The list->integer function evaluates to an integer composed of the digits and the prefix (if any) contained in the given list. The list must contain a positive number of digits, and it may contain a sign of the form + or - at its first position. Digits are represented by the symbols 0-digit through 9-digit. The following rules apply:

(list->integer '(0-digit))     => 0
(list->integer '(1-digit 2-digit 3-digit)) => 123
(list->integer '(- 7-digit))   => -7
(list->integer '(+ 5-digit))   => +5
(list->integer '(non-digit))   => bottom
(list->integer '())            => bottom
(list->integer '(-))           => bottom
(list->integer '(+ + 1-digit)) => bottom
(list->integer 'non-list)      => bottom

The list->integer function is specific to SketchyLISP.

4.6.5 list->string

(list->string list) => string

The list->string function evaluates to a string literal that is composed of the characters contained in the list passed to it. The list must contain objects of the type char exclusively. The following rules apply:

(list->string '(#\X))             => "X"
(list->string '(#\t #\e #\x #\t)) => "text"
(list->string '())                => ""
(list->string '(#\"))             => "\""
(list->string '(non-char))        => bottom
(list->string 'non-list)          => bottom

The list->string function conforms to R5RS.

4.6.6 string->list

(string->list "xyz") => list

The string->list function evaluates to a list containing the same characters as the string passed to it. Each character of the string will be represented by an individual char literal in the resulting list. The following rules apply:

(string->list "X")         => '(#\X)
(string->list "text")      => '(#\t #\e #\x #\t)
(string->list "")          => '()
(string->list "\"")        => '(#\")
(string->list 'non-string) => bottom

The string->list function conforms to R5RS.

4.6.7 string->symbol

(string->symbol "xyz") => 'xyz

The string->symbol function evaluates to a symbol that is composed of the characters of the given string argument. The following rules apply:

(string->symbol "foo")       => 'foo
(string->symbol "FOO")       => 'FOO
(string->symbol " ")         => '
(string->symbol "")          => bottom
(string->symbol 'non-string) => bottom

Notes

(1) String->symbol may be used to create symbols that cannot be accessed by programs, such as symbols containing white space, symbols containing upper case letters, and symbols containing special characters like parentheses, dots, semicolons, etc.

(2) Symbols containing spaces lead to an ambiguity, as demonstrated below. Therefore future implementation of SketchyLISP may refuse to create such symbols.

(string->symbol "ga ga")                  => 'ga ga
(symbol->string (string->symbol "ga ga")) => "ga ga"
(symbol->string 'ga ga)                   => bottom

The string->symbol function mostly conforms to R5RS.
The R5RS variant allows the creation of empty symbols.

4.6.8 symbol->string

(symbol->string 'xyz) => "xyz"

The symbol->string function evaluates to a string that is composed of the characters of the literal symbol passed to it. The following rules apply:

(symbol->string 'foo)         => "foo"
(symbol->string 'FOO)         => "foo"
(symbol->string "non-symbol") => bottom

The symbol->string function conforms to R5RS.