Page Numbers: Yes X: 306 Y: 1.0" First Page: 11
Margins: Top: 1.0" Bottom: 1.3"
Heading:
STANDARD PROCEDURE GUIDE 3-LISP REFERENCE MANUAL April 16, 1984
————————————————
2. Standard Procedure Guide
————————————————
This section describes each of the standard 3-LISP procedures. The code for the non-primitive standard procedures can be found in section 3. Some notes on the format of the descriptions used in this section:
1.Each procedure is illustrated with non-objectified arguments, but many can be used in other ways (for example: (PCONS . (REST [’A ’B ’C])) g ’(B . C)).
2.For each procedure, we give the declarative import. In many cases that is the only semantical information provided, since if the designation has a canonical normal-form designator, what is returned (i.e., the result) can be determined from this designation. For example, since (+ 2 3) designates the number 5, it will return the numeral 5; since (= ’A ’B) designatos falsity, it will return the boolean $FALSE. If, however, the normal-form designator is not canonical, or if there are side effects, the relevant parts of the procedural significance are described as well.
3.Typing information is typically given only in terms of what we call the functions "F-type". Thus for example the division function / would be said to have F-type of [ NUMBERS X NUMBERS ] ← NUMBERS.
4.On the format of the definitions: Each procedure is introduced with something like the following schema:
(IF PREMISE E1 E2)
If no more descriptive term is used (such as PREMISE in the above), the schematic variable names indicate the argument’s (F-)type — either the type name directly, or one of the following abbreviations:
E—Object of any typeS—(Internal) structure
CH—CharacterSEQ—Sequence (or rail)
ENV—EnvironmentST—String
FUN—FunctionTV—Truth value
N—Number
Italics are used for (meta-linguistic) schematic variables; underlined arguments indicate those positions that are normalised tail recursively with respect to the procedure call.
5.Several one-word attributes are associated with each procedure to provide a quick reference for determining the nature of the procedure. The following keywords are used:
ConsThis procedure may create new structures that will be accessible from the result. E.g., APPEND.
EnvSome of the arguments to this procedure may be normalised in some environment other that the current one; however, these environment manipulations are accomplished through non-destructive means. E.g., LET.
Smash-envThis procedure may destructively change the current environment. E.g., SET, REBIND.
I/OThis procedure may side effect the outside world by doing I/O. E.g., CHAR-IN.
CPSThis procedure is written in the continuation-passing style — instead of returning, the result will be explicitly passed to the continuation (usually as the last argument). E.g., NORMALISE.
AbnormalSome of the arguments may not always be normalised. E.g., IF.
6.Still other keywords are used to indicate the nature of the procedure’s status within the implementation:
PrimitiveThis procedure is one of the primitives that have only viciously circular definitions within the 3-LISP system. All non-primitives have complete and accurate descriptions in terms of the primitives.
KernelThis procedure is an essential part of 3-LISP because it is used regularly by the reflective processors at all levels.
7.The symbol ‘g’ (used in examples) means "normalises to"; ‘W>’ means approximately "expands to", and is used for macro redexes. Generally, illustrations of macro expansion are mild white lies: for example, in order to avoid unexpected environment dependencies, we would define INCREMENT as (MLAMBDA [N] ’(,↑+ 1 ,N)), rather than as (MLAMBDA [N] ’(+ 1 ,N)). Nonetheless, we would still say that (INCREMENT EXP) W> (+ 1 EXP), whereas it would be more accurate to say that (INCREMENT EXP) W> ({primitive + closure} 1 EXP). I.e., the ‘W>’ notation may be slightly inaccurate on hyperintensional properties of the expansion.
8.Some comments in regard to examples involving I/O. All output expressions are printed in italics following the level 1 processor’s ‘1=’ prompt. Input expression appear unitalicised following the ‘1>’ prompt.
1> ’HELLO
1= ’HELLO
Input destined for an explicit call to OBTAIN (or READ, CHAR-IN, etc.) are underlined.
1> (READ PRIMARY-STREAM) ’HELLO
1= ’HELLO
Output produced by an explicit call to PRINT (or OUTPUT, etc.) is italicised and underlined.
1> (PRINT PS ’HELLO PRIMARY-STREAM)
’HELLO1= ’OK
Note that in the interest of readability several liberties have been taken with the formatting of output expressions — actual results may vary.
9.To facilitate the writing of macros and other reflective procedures, the argument-to-parameter pattern matcher (BIND) will convert a rail-designating argument into a sequence of designators. For example, ’[1 2 3] will be converted to [’1 ’2 ’3] in order to fit the pattern [A B C]. This is consistent with the polymorphism of 1ST and REST, etc. — (1ST ’[1 2 3]) and (1ST [’1 ’2 ’3]) both normalise to ’1.
10.All standard procedures return a result. Those that accomplish a side-effect on environments (SET, REBIND, etc.) return the newly-bound value; others (e.g., OUTPUT) return a gratuitous ’OK.
11.Errors: If the process of normalizing a structure causes an error, then the escape continuation will be called. (The default escape continuation is a debugging package that interacts with the user, allowing him or her to abort the continuation, resume with a result, or whatever.) In this manual, errors are indicated by showing, in place of a result (g), an error message in italics and curly brackets. (e.g. x => {Error: Unbound Variable}). The standard debugging package is documented in the debugger handout.
————————————————————————————————————————————
2.a. SIMPLE DATA TYPES and OPERATIONS
————————————————————————————————————————————
2.a.1. ATOMS
————————————————————————————————————————————
(ATOM E)
True just in case E designates an atom.
F-Type: [ OBJECTS ] ← TRUTH-VALUESProperties: Primitive; kernel.
Examples:(ATOM ’Hello)g$TRUE
(ATOM ’$TRUE)g$FALSE
(ACONS)
Designates a nameless and otherwise inaccessible atom.
F-Type: [ ] ← ATOMSProperties: Primitive; cons.
Examples:(ACONS)g’{atom#...}
(= (ACONS) (ACONS))g$FALSE
(ATOM-NOTATION ATOM)
Designates the string that is the notation of the atom designated by ATOM.
F-Type: [ ATOMS ] ← STRINGSProperties: Primitive.
Examples:(ATOM-NOTATION ’Curious)g"CURIOUS"
(ATOM-NOTATION (ACONS))g"{atom#...}"
(ATOM-NOTATED STRING)
Designates the atom whose notation is the string designated by STRING.
F-Type: [ STRINGS ] ← ATOMSProperties: Primitive.
Examples:(ATOM-NOTATED "Lambda")g’LAMBDA
————————————————————————————————————————————
2.a.2. PAIRS (REDEXES)
————————————————————————————————————————————
(PAIR S)
True if S designates a pair; false otherwise.
F-Type: [ STRUCTURES ] ← TRUTH-VALUESProperties: Primitive; kernel.
Examples:(PAIR ’(A . B))g$TRUE
(PAIR ’(FACTORIAL 10))g$TRUE
(PAIR (+ 2 3))g$FALSE
(PCONS S1 S2)
Designates an otherwise inaccessible pair whose PROC part is the internal structure designated by S1 and whose ARGS part is the internal structure designated by S2.
F-Type: [ STRUCTURES X STRUCTURES ] ← PAIRSProperties: Primitive; cons.
Examples:(PCONS ’A ’B)g’(A . B)
(PCONS ’+ ’[2 3])g’(+ 2 3)
(PCONS 2 3)g{ERROR: Structure expected.}
(PPROC PAIR)
Designates the internal structure that is the PROC part of the pair designated by PAIR.
F-Type: [ PAIRS ] ← STRUCTURESProperties: Primitive; kernel.
Examples:(PPROC ’(A . B))g’A
(PPROC ’(1 . $TRUE))g’1
(PPROC ’(+ 2 3))g’+
(PPROC [A B C])g{ERROR: Pair expected.}
(PPROC ’+))g{ERROR: Pair expected.}
(PARGS PAIR)
Designates the internal structure that is the ARGS part of the pair designated by PAIR.
F-Type: [ PAIRS ] ← STRUCTURESProperties: Primitive; kernel.
Examples:(PARGS ’(A . B))g’B
(PARGS ’(1 . $TRUE))g’$TRUE
(PARGS ’(+ 2 3))g’[2 3]
(PARGS ’(ACONS))g’[]
(PARGS ’1))g{ERROR: Pair expected.}
(ARG N PAIR)
Designates the Nth element in the ARGS part of the pair designated by PAIR. Heavily used in macro and reflective procedures, to disassemble redex structure.
F-Type: [ NUMBERS X PAIRS ] ← STRUCTURESProperties: kernel.
Examples:(ARG 1 ’(+ 10 20))g’10
(ARG 2 ’(+ . (REST [10 20 30])))g{ERROR: Rail expected.}
(LET [[INCREMENT
(MLAMBA [CALL]
’(+ 1 ,(ARG 1 CALL)))]]
(INCREMENT 12))g13
————————————————————————————————————————————
2.a.3. SEQUENCES and RAILS
————————————————————————————————————————————
Whereas the following functions are primarily described (and will primary be used) over sequences, most of them are polymorphic, applying equally well to rails. Rail-specific behaviour is described if it is unusual or not entirely as would be expected.
(SEQUENCE E)
(RAIL E)
True if E or S designates a sequence or rail, respectively; false otherwise.
F-Types: [ SEQUENCES ] ← TRUTH-VALUESProperties: Primitive; kernel.
[ RAILS ] ← TRUTH-VALUES
Examples:(SEQUENCE [10 20 30])g$TRUE
(SEQUENCE 10 20 30)g{ERROR: Wrong number of arguments.}
(SEQUENCE (PARGS ’(FACTORIAL 10)))g$FALSE
(RAIL (PARGS ’(FACTORIAL 10)))g$TRUE
(FIRST SEQ)
Designates the first element of the sequence designated by SEQ. Also works on rails.
F-Types:[ {SEQUENCES U RAILS} ] ← STRUCTURESProperties: Primitive; kernel.
Examples:(FIRST [1 2 3])g1
(FIRST [])g{ERROR: Index too large.}
(FIRST ’[ALL IS WELL])g’ALL
(REST SEQ)
Designates the first tail of the sequence designated by VEC. REST plays the role in 3-LISP that CDR plays in standard LISPs when used on lists signifying enumerations. Also works on rails.
F-Types: [ RAILS ] ← RAILSProperties: Kernel.
{ SEQUENCES } ← SEQUENCES
Examples:(REST [1 2 3])g[2 3]
(REST 1)g{ERROR: Sequence or rail expected.}
(CONS E SEQ)
Designates a sequence (or rail) whose first element is the object designated by E, and whose first tail is the sequence (or rail) designated by SEQ. When SEQ designates a sequence, (CONS E SEQ) returns an otherwise inaccessible rail whose first tail is the same rail as that to which SEQ normalises (i.e., it returns an inaccessible but not completely inaccessible rail). When SEQ designates a rail, E must designate a structure, and (CONS E SEQ) returns the handle of an otherwise inaccessible rail whose first tail is the rail that SEQ designates.
F-Types:[ OBJECTS X SEQUENCES ] ← SEQUENCESProperties: Primitive; kernel; cons.
[ STRUCTURES X RAILS ] ← RAILS
Examples:(CONS 10 [20 30])g[10 20 30]
(CONS ’A ’[B C])g’[A B C]
(CONS ’A [’B ’C])g[’A ’B ’C]
(CONS [$TRUE] [$FALSE])g[[$TRUE] $FALSE]
(CONS 10 ’[20 30])g{ERROR: Structure expected.}
(CONS ’10 [20 30])g[’10 20 30]
(CONS 1 2)g{ERROR: Sequence or rail expected.}
(LENGTH SEQ)
Designates the number of elements in the sequence designated by SEQ. Also works on rails.
F-Type: [ {SEQUENCES U RAILS} ] ← NUMBERS Properties: Primitive.
Examples:(LENGTH ’[A B C])g3
(LENGTH [])g0
(LENGTH (LIST))g0
(LENGTH 3)g{ERROR: Sequence or rail expected.}
(NTH N SEQ)
When N designates the number k, (NTH N SEQ) designates the k’th element of the sequence or rail designated by SEQ. Elements are numbered starting at 1, not 0; therefore k may range from 1 to the length of the designation of SEQ.
F-Types: [ NUMBERS X SEQUENCES ] ← OBJECTSProperties: Primitive.
[ NUMBERS X RAILS ] ← STRUCTURES
Examples:(NTH 1 [(+ 5 5) 20 30])g10
(NTH 2 [’10 ’20 ’30])g’20
(NTH 3 ’[10 20 30])g’30
(NTH 2 [10])g{ERROR: Index too large.}
(NTH ’2 [10 20 30])g{ERROR: Number expected.}
(NTH 1 10)g{ERROR: Sequence or rail expected.}
(TAIL N SEQ)
Designates the N’th tail of the sequence or rail designated by SEQ (where N may range from 0 to the length of SEQ). In general, the k’th tail of a sequence of length K is that sequence consisting of the (k+1)’th through K’th element; thus the 0’th tail of A is identically A. If (TAIL N SEQ) designates a sequence (as opposed to a rail), it will return the N’th tail of the rail to which SEQ normalises.
F-Types:[ NUMBERS X SEQUENCES ] ← SEQUENCESProperties: Primitive.
[ NUMBERS X RAILS ] ← RAILS
Examples:(TAIL 2 [10 20 30 40])g[30 40]
(TAIL 1 (PARGS ’(RCONS ’A ’B ’C)))g’[’B ’C]
(LET [[X ’[A B]]] (= X (TAIL 0 X)))g$TRUE
(LETSEQ [[X [2 3]]
[Y (CONS 1 X)]]
(= ↑X ↑(TAIL 1 Y)))g$TRUE
(TAIL 1 [1])g[]
(TAIL 3 [1 2])g{ERROR: Index too large.}
(TAIL $FALSE [1 2])g{ERROR: Number expected.}
(TAIL 1 #C)g{ERROR: Sequence or rail expected.}
(NULL SEQ)
True just in case SEQ designates an empty sequence (or rail); false in case SEQ designates a non-empty sequence (or rail); error otherwise (i.e., NULL is strict). Note that (NULL SEQ) will return $FALSE even if SEQ designates an infinite sequence (in contrast with (= 0 (LENGTH SEQ))).
F-Type: [ {RAILS U SEQUENCES} ] ← TRUTH-VALUESProperties: Primitive; kernel.
Examples:(NULL [])g$TRUE
(NULL ’[])g$TRUE
(NULL ’[A B C])g$FALSE
(NULL (LIST))g$TRUE
(NULL (RCONS))g$TRUE
(NULL ’(A . B))g{ERROR: Sequence or rail expected.}
(LIST E1 ... Ek)
Designates the sequence of length k of objects (internal or external) designated by E1 through Ek (k >𔁆); returns an otherwise completely inaccessible normal-form designator (rail) of that sequence. Note that sequence identity is as in mathematics: two sequences are the same if and only if they consist of the same elements in the same order. Use of LIST is rare, since the shorter expression [E1 ... Ek] designates the same sequence.
F-Type: [ {OBJECTS}* ] ← SEQUENCES Properties: Primitive; kernel; cons.
Examples:(LIST 1 2 3)g[1 2 3]
(LIST ’1 ’2 ’3)g[’1 ’2 ’3]
(LIST ’A (+ 2 2))g[’A 4]
[’A (+ 2 2)]g[’A 4]
(LIST)g[]
(= (LIST) (LIST))g$TRUE
(= ↑(LIST) ↑(LIST))g$FALSE
(LET [[X [1 2]]] (= X (LIST . X)))g$TRUE
(LET [[X [1 2]]] (= ↑X ↑(LIST . X)))g$FALSE
(FIRST SEQ)(1ST SEQ)
(SECOND SEQ)(2ND SEQ)
(THIRD SEQ)(3RD SEQ)
(FOURTH SEQ)(4TH SEQ)
(FIFTH SEQ)(5TH SEQ)
These forms designate, respectively, the first, second, third, fourth, fifth, and sixth elements of the sequence (or rail) designated by SEQ. In case SEQ designates a sequence, each returns the Kth element of the rail to which SEQ normalises (1 < K <6). Defined to be equivalent to (NTH 1 SEQ), (NTH 2 SEQ), etc.
F-Type:[ SEQUENCES ] ← OBJECTSProperties: Kernel (1ST and 2ND only).
[ RAILS ] ← STRUCTURES
Examples:(3RD [10 20 30 40])g30
(1ST (CONS ’A ’[B C]))g’A
(2ND [1])g{ERROR: NON-NULL SEQUENCE EXPECTED}
(LAST SEQ)
Designates the last element of the sequence (or rail) designated by SEQ.
F-Types:[ RAILS ] ← STRUCTURESProperties: Kernel
[ SEQUENCES ] ← OBJECTS
Examples:(LAST [1 2 3])g3
(LAST [])g{ERROR: NON-NULL SEQUENCE EXPECTED.}
(LAST ’[ALL IS WELL])g’WELL
(ALL-BUT-LAST SEQ)
If SEQ designates a sequence of objects E1 ... Ek, (ALL-BUT-LAST SEQ) designates the sequence of objects E1 ... Ek-1. Designates the empty sequence if k is 1; errors if k is zero. Also works on rails.
F-Types:[ RAILS ] ← RAILSProperties: Kernel; cons
[ SEQUENCES ] ← SEQUENCES
Examples:(ALL-BUT-LAST [1 2 3])g[1 2]
(ALL-BUT-LAST [$TRUE])g[]
(ALL-BUT-LAST [])g{ERROR: NON-NULL SEQUENCE EXPECTED}
(ALL-BUT-LAST ’[ALL IS WELL])g’[ALL IS]
(MEMBER E SEQ)
True when the object designated by E is an element of the sequence designated by SEQ. If (MEMBER E SEQ) is true, and E is finite, it is guaranteed to return; if not, it will terminate only if the objects designated by E and SEQ are finite. Note: since MEMBER is defined in terms of =, it can’t be used over sequences of functions.
F-Type:[ OBJECTS X SEQUENCES ] ← TRUTH-VALUES
[ STRUCTURES X RAILS ] ← TRUTH-VALUES
Examples:(MEMBER 1 [2 3 4])g$FALSE
(MEMBER 3 [1 1 2 (+ 1 2)])g$TRUE
(MEMBER ’2 ’[1 2 3])g$TRUE
(MEMBER 2 [’1 ’2 ’3])g$FALSE
(MEMBER ’[] ’[[A] [] [B]])g$FALSE
(MEMBER [] [[1] [] [2]])g$TRUE
(MEMBER 1 2)g{ERROR: Sequence or rail expected.}
(MEMBER * [+ - * /])g{ERROR: = not defined over functions.}
(MEMBER ↑* ↑[+ - * /])g$TRUE
(APPEND SEQ1 SEQ2 ... SEQk)
If Li is the length of the sequence designated by each SEQi, (APPEND SEQ1 SEQ2 ... SEQk) designates the sequence of length L1+L2+ ... + Lk whose first L1 elements are the elements of the sequence designated by SEQ1, whose next L2 elements are the elements of the sequence designated by SEQ2, etc. (K >𔁇). Also works on rails, but not on mixtures of rails and sequences (i.e., all arguments must be of the same type). The sequence to which SEQK normalises is not copied (i.e., SEQK is accessible from the result).
F-Types:[ SEQUENCES X {SEQUENCES}* ] ← SEQUENCESProperties: Cons.
[ RAILS X {RAILS}* ] ← RAILS
Examples:(APPEND [1 2 3] [4 5 6])g[1 2 3 4 5 6]
(APPEND ’[] ’[A B C])g’[A B C]
(APPEND ’[A B C])g’[A B C]
(APPEND)g[]
(LET [[X ’[M N]]] (APPEND X X))g’[M N M N]
(LETSEQ [[X ’[M N]] [Y (APPEND X X)]]
(= X (TAIL 2 Y)))g$TRUE
(LET [[X [1 2]] [Y [3 4]]]
(BEGIN (APPEND X Y)
X))g[1 2]
(APPEND 1 [2 3])g{ERROR: Sequence or rail expected.}
(APPEND [1 2 3] [4 5 6] [7 8 9])g[1 2 3 4 5 6 7 8 9]
(LET [[X ’[G O]]] (APPEND X X X))g’[G O G O G O]
(REVERSE SEQ)
Designates a sequence whose elements are the same as the elements of the sequence designated by SEQ, except in reverse order. The resulting sequence is otherwise completely inaccessible. Also defined on rails.
F-Types:[ SEQUENCES ] ← SEQUENCESProperties: Cons.
[ RAILS ] ← RAILS
Examples:(REVERSE [])g[]
(REVERSE [1 2 3])g[3 2 1]
(REVERSE ’[[A B] [C D]])g’[[C D] [A B]]
(LET [[X [10]]] (= X (REVERSE X)))g$TRUE
(LET [[X [10]]]
(= ↑X ↑(REVERSE X)))g$FALSE
(LET [[Y ’[A]]] (= Y (REVERSE Y)))g$FALSE
(INDEX ELEMENT SEQ)
Searches the sequence designated by SEQ for an element equal to the object designated by ELEMENT, and yields the number indicating the first position in which it was found. Designates 0 if the object is not a member of the sequence. Also defined on rails.
F-Type:[ OBJECTS X {SEQUENCES U RAILS} ] ← NUMBERS
Examples:(INDEX 3 [2 3 6 1])g2
(INDEX ’B [’A ’B ’C])g2
(INDEX [10] [1 $TRUE [10]])g3
(INDEX ’+ [])g0
(EVERY PREDICATE SEQ)
True just in case the unary predicate designated by PREDICATE is true of all the elements in the sequence designated by SEQ. True, in particular, if SEQ designates a null sequence. Procedurally, it returns when it encounters the first false sequence element. Also defined on rails.
F-Type:[ FUNCTIONS X {SEQUENCES U RAILS} ] ← TRUTH-VALUES
Examples:(EVERY ATOM [’THIS ’IS ’A ’TEST])g$TRUE
(EVERY ZERO [])g$TRUE
(EVERY NULL [[] [1] 2])g$FALSE
(EVERY NULL [[] [] 2])g{ERROR: Sequence or rail expected.}
(EVERY ID [$TRUE (= 1 1)])g$TRUE
(EVERY (LAMBDA [X] (= X X))
[1 (= 1 1) (TYPE 1)])g$TRUE
(RCONS S1 ... Sk)
Designates an otherwise completely inaccessible rail of length k whose elements are the internal structures designated by S1 through Sk (k >𔁆).
F-Type: [ {STRUCTURES}* ] ← RAILS Properties: Primitive; kernel; cons.
Examples: (RCONS ’1 ’2 ’3)g’[1 2 3]
(RCONS ’A (PCONS ’B ’C))g’[A (B . C)]
(RCONS)g’[]
(= (RCONS) (RCONS))g$FALSE
(= ↑(RCONS) ↑(RCONS))g$TRUE
(RCONS 1 2 3)g{ERROR: Structure expected.}
(VECTOR-CONSTRUCTOR TEMPLATE)
Designates the RCONS or LIST procedure, depending on whether TEMPLATE designates an internal structure or (abstract) external object, respectively. VECTOR-CONSTRUCTOR is primarily useful in the terminating clause of a recursive defintion defined over general enumerations (see the definition of MAP, for example).
F-Type: [ OBJECTS ] ← FUNCTIONS Properties: Kernel.
Examples:(VECTOR-CONSTRUCTOR ’[])g{RCONS closure}
((VECTOR-CONSTRUCTOR ’[]))g’[]
(VECTOR-CONSTRUCTOR 100)g{LIST closure}
((VECTOR-CONSTRUCTOR 100))g[]
(VECTOR-CONSTRUCTOR ↑↑1)g{RCONS closure}
(COPY-VECTOR SEQ)
If SEQ designates a rail, (COPY-VECTOR SEQ) designates an otherwise completely inaccessible rail whose elements are the elements of the rail designated by VEC. If SEQ designates a sequence, (COPY-VECTOR SEQ) designates the same sequence as VEC, but returns an otherwise completely inaccessible designator (rail) of it. Rarely used, because when SEQ designates a sequence, the simpler (LIST . SEQ) can be used to achieve the same effect.
F-Types: [ SEQUENCES ] ← SEQUENCESProperties: Cons.
[ RAILS ] ← RAILS
Examples:(COPY-VECTOR ’[A B C])g’[A B C]
(COPY-VECTOR [])g[]
(LET [[Y [1 2 3]]]
[(= Y (COPY-VECTOR Y))
(= ↑Y ↑(COPY-VECTOR Y))])g[$TRUE $FALSE]