Page Numbers: Yes X: 310 Y: 10.44" First Page: 11
Margins: Top: 1.0" Bottom: 1.3"
Heading:
CS-370 (FALL 1982)2-LISP REFERENCE GUIDE
————————————————————————————————————————————
EVERYTHING FROM THIS POINT ON IS STILL 3-LISP
————————————————————————————————————————————
6. Primitive Procedures
6.1. Summary (fuller definitions are given below):
CategoryStandard NameFunctionality
Typing:TYPEdefined on 13 types (8 internal, 5 external)
PROCEDURE-TYPEto distinguish simple and reflective closures
Identity:=defined on 12 types (all except functions)
Structural:PCONS, CAR, CDRto construct and examine pairs
CCONS, ENV, PATTERN, BODYto construct and examine closures
ACONSto construct atoms
RCONS, SCONS, PREPto construct rails and sequences
LENGTH, NTH, TAIL to examine " " "
Modifier:REPLACEto modify mutable structures
Control:IFan extensional if-then-else conditional
Semantics:UP, DOWNto mediate between sign & signified
Arithmetic:+, -, *, /as usual
I/O:INPUT, OUTPUTprimitive operations on streams
Reflection:LEVELthe current reflective level
The following kernel functions need not be primitive; they are defined in the reflective model in terms of the above:
DEFINE, LAMBDA, NORMALISE, REDUCE, SET, BINDING, MACRO, READ, PRINT, SIMPLE, REFLECT
6.2. Procedure Definitions:
Note: Each procedure is illustrated with non-objectified arguments, but can be used in other ways (for example: (PCONS . (REST ’[A B C])) g ’(B . C)). Listed in alphabetical order:
———————————————————
↑A— see UP
↑A— see DOWN
———————————————————
(= A1 A2)True if A1 and A2 designate the same entity; false otherwise. Returns $T or $F as appropriate, unless either argument designates a function (or a sequence constaining a function, or a sequence containing a sequence containing a function, etc.), in which case it errors, or an infinite sequence, in which case it doesn’t terminate. Note that although equality is defined over closures, it is too fine grained to be used for function identity.
F-Type:[ OBJECTS - FUNCTIONS ] ← TRUTH-VALUES
Examples:(= 3 (+ 1 2))g$T
(= 5 ’5)g$F
(= [10 20] [10 20])g$T
(= ’[10 20] ’[10 20])g$F
(= CAR CDR)g<ERROR: = CALLED ON A FUNCTION>
(= ↑CAR ↑CDR)g$F
(= ↑CAR ↑CAR)g$T
(= ↑(LAMBDA SIMPLE [X] X)
↑(LAMBDA SIMPLE [X] X))g$F
Semantics:S(E0("=)) = l ...
———————————————————
(+ A B)These forms designate, respectively, the sum, product, difference, and quotient
(* A B)of the numbers designated by A and B. Each returns the numeral that is the
(- A B)canonical designator of that number, except that (/ A B) will produce an error if
(/ A B)B designates zero. At the moment, arithmetic is defined only on integers (we
intend to define full rational arithmetic (with no upper limit on numeral size,
and therefore no limit on precision) in due course.
F-Type:[ NUMBERS X NUMBERS ] ← NUMBERS
Examples:(* 2 3)g6
(/ 3 2)g1
(/ -3 2)g-1
Semantics:S(E0("+)) = l ...
S(E0("*)) = l ...
S(E0("-)) = l ...
S(E0("/)) = l ...
———————————————————
(ACONS)Designates an otherwise inaccesible atom.
F-Type:[ ] ← ATOMS
Examples:(ACONS)g<ATOM without a label>
(= (ACONS) (ACONS))g$F
Semantics:S(E0("ACONS)) = l ...
———————————————————
(BODY C)Designates the body designator in the closure designated by C; returns its handle.
F-Type:[ CLOSURES ] ← S-EXPRESSIONS
Examples:(BODY ↑(LAMBDA SIMPLE [A B] (PCONS B A)))g’(PCONS B A)
Semantics:S(E0("BODY)) = l ...
———————————————————
(CAR A)Designates the expression that is the CAR of the pair designated by A; returns its handle.
F-Type:[ PAIRS ] ← S-EXPRESSIONS
Examples:(CAR ’(+ 2 3))g’+
Semantics:S(E0("CAR)) = l ...
———————————————————
(CCONS T E P B)Designates an otherwise inaccessible closure of the type designated by T (either SIMPLE or REFLECT) containing designators of the environment designated by E, the pattern designated by P, and the body designated by B; returns the handle of that closure. Note how a level-crossing operation (↑) will typically be used to construct closures; this is because closures are a failure. (CCONS will rarely be used explicitly by a user program.)
F-Type:[ ATOMS X RAILS X S-EXPRESSIONS X S-EXPRESSIONS ] ← CLOSURES
Examples:(CCONS ’SIMPLE ↑GLOBAL ’[X] ’X)g’<SIMPLE <GLOBAL ENV> [X] X>
Semantics:S(E0("CCONS)) = l ...
———————————————————
(CDR A)Designates the structure that is the CDR of the pair designated by A; returns its handle.
F-Type:[ PAIRS ] ← S-EXPRESSIONS
Examples:(CDR ’(A . B))g’B
(CDR ’(+ 2 3))g’[2 3]
Semantics:S(E0("CDR)) = l ...
———————————————————
(DOWN A)If R is the referent of A, then (DOWN A) designates the referent of R,
↑Aproviding that R is a normal-form designator, and returns R. "↑EXP"
expands to "(DOWN EXP)" in standard notation.
F-Type:[ S-EXPRESSIONS ] ← OBJECTS
Examples:↑’4g4
↑(NTH 2 ’[10 20 30])g20
↑3g<ERROR: 3 is not a designator>
↑↑$Tg$T
Semantics:S(E0("DOWN)) = l ...
———————————————————
(EF PREM C1 C2)Designates the referent of C1 or C2 depending on whether PREM is true or false, respectively; returns the result of normalising C1 or C2. Note that, unlike the non-primitive IF, EF is fully extensional.
F-Type:[ TRUTH-VALUES X OBJECTS X OBJECTS ] ← OBJECTS
Examples:(EF (= 1 2) ’A ’B)g’B
1> (EF (= 1 2)
(PRINT "Hello")
(PRINT "Good-bye")) Hello Good-bye
1>
Semantics:S(E0("EF)) = l ...
———————————————————
(ENV C)Designates the environment designator in the closure designated by C; returns its handle.
F-Type:[ CLOSURES ] ← RAILS
Examples:(ENV ↑RCONS)g’<GLOBAL ENV>
Semantics:S(E0("ENV)) = l ...
———————————————————
(INPUT S)Designates the next item in the stream designated by S; returns its normal-form designator. It may be assumed that S is side-effected by this operation.
F-Type:[ STREAMS ] ← OBJECTS
Semantics:S(E0("INPUT)) = l ...
———————————————————
(LENGTH A)Designates the length of the rail or sequence designated by A; returns the numeral for that number, if it is finite.
F-Type:[ RAILS U SEQUENCES ] ← NUMBERS
Examples:(LENGTH ’[A B C])g3
(LENGTH (SCONS))g0
Semantics:S(E0("LENGTH)) = l ...
———————————————————
(LEVEL)Designates the number associated with the current reflective level of the processor (initially 1, and incremented by 1 upon reflection); returns the corresponding numeral.
F-Type:[ ] ← NUMBERS
Semantics:S(E0("LEVEL)) = l ...
———————————————————
(NTH I A)Designates the I’th element of the rail or sequence designated by A; returns a normal-form designator of that element (note that vector elements are numbered starting at 1, not zero).
F-Types:[ NUMBERS X RAILS ] ← S-EXPRESSIONS
[ NUMBERS X SEQUENCES ] ← OBJECTS
Examples:(NTH 2 [10 20 30])g20
(NTH 2 [’10 ’20 ’30])g’20
(NTH 2 ’[10 20 30])g’20
Semantics:S(E0("NTH)) = l ...
———————————————————
(OUTPUT A S)Puts the entity designated by A into the stream designated by S. Designates T and returns nothing.
F-Type:[ S-EXPRESSIONS X STREAMS ] ← T
Semantics:S(E0("OUTPUT)) = l ...
———————————————————
(PATTERN C)Designates the pattern designator in the closure designated by C; returns its handle.
F-Type:[ CLOSURES ] ← S-EXPRESSIONS
Examples:(PATTERN ↑(LAMBDA SIMPLE [A B] (PCONS B A)))g’[A B]
(DEFINE ARITY
(LAMBDA SIMPLE [FUN]
(LENGTH (PATTERN ↑FUN))))
Semantics:S(E0("PATTERN)) = l ...
———————————————————
(PCONS A1 A2)Designates an otherwise inaccessible pair whose CAR is the structure designated by A1 and whose CDR is the structure designated by A2. Returns the handle of that pair.
F-Type:[ S-EXPRESSIONS X S-EXPRESSIONS ] ← PAIRS
Examples:(PCONS ’A ’B)g’(A . B)
(PCONS ’+ ’[2 3])g’(+ 2 3)
(PCONS 2 3)g<ERROR: expecting a structure, found a number>
Semantics:S(E0("PCONS)) = l ...
———————————————————
(PREP EL VEC)Designates a vector whose first element is the entity designated by EL, and whose first tail is the vector designated by VEC. The type of the vector (i.e., rail or sequence) is the same as the type of VEC.
F-Types:[ OBJECTS X SEQUENCES ] ← SEQUENCES
[ S-EXPRESSIONS X RAILS ] ← RAILS
Examples:(PREP 10 [20 30])g[10 20 30]
(PREP ’A ’[B C])g’[A B C]
Semantics:S(E0("PREP)) = l ...
———————————————————
(PROCEDURE-TYPE C)Designates one of the atoms SIMPLE or REFLECT, depending on whether the closure designated by C is simple or reflective; returns the corresponding handle.
F-Type:[ CLOSURES ] ← ATOMS
Examples:(PROCEDURE-TYPE ↑CAR)g’SIMPLE
(PROCEDURE-TYPE ↑LAMBDA)g’REFLECT
Semantics:S(E0("PROCEDURE-TYPE)) = l ...
———————————————————
(RCONS A1 ... Ak)Designates an otherwise inaccessible rail of length k whose i’th element is (the structure designated by) Ai. Returns the handle of the new rail.
F-Type:[ S-EXPRESSIONS ]* ← RAILS
Examples:(RCONS ’A ’B ’C)g’[A B C]
(RCONS)g’[]
(= (RCONS) (RCONS))g$F
(RCONS 1 2 3)g<ERROR: expecting a structure, found a number>
Semantics:S(E0("RCONS)) = l ...
———————————————————
(REPLACE A B)Replaces the structure (pair, rail, or closure) designated by A with the structure of similar type designated by B. Designates T and returns nothing; however, subsequent to its execution the field will be altered in such a way that every relationship in which A participated will be changed to have B as its participant (with the consequence that A becomes inaccessible).
F-Types:[ PAIRS X PAIRS ] ← T
[ RAILS X RAILS ] ← T
[ CLOSURES X CLOSURES ] ← T
Examples:(LET [[X ’(+ 2 3)]]
(BLOCK (REPLACE (CDR X) ’[20 30])
X))g’(+ 20 30)
(DEFINE RPLACA
(LAMBDA SIMPLE [PAIR A]
(REPLACE PAIR (PCONS A (CDR PAIR))))
Semantics:S(E0("REPLACE)) = l ...
———————————————————
(SCONS A1 ... Ak)Designates the sequence of entities designated by A1 through Ak; returns an otherwise inaccessible normal-form designator of that sequence.
F-Type:[ OBJECTS ]* ← SEQUENCES
Examples:(SCONS 1 2 3)g[1 2 3]
(SCONS)g[]
(LET [[X [’A ’B]]] (= X (SCONS . X)))g$T
(LET [[X [’A ’B]]] (= ↑X ↑(SCONS . X)))g$F
Semantics:S(E0("SCONS)) = l ...
———————————————————
(TAIL I A)Designates the I’th tail of the rail or sequence designated by A (where I may range from 0 to the length of A); returns a normal-form designator of that vector. In general, the I’th tail of a vector of length K is that vector consisting of the (I+1)th through Kth element (thus the zero-th tail of A is A).
F-Types:[ NUMBERS X RAILS ] ← RAILS
[ NUMBERS X SEQUENCES ] ← SEQUENCES
Examples:(TAIL 2 [10 20 30 40])g[30 40]
(TAIL 1 (CDR ’(RCONS ’A ’B ’C)))g’[’B ’C]
(LET [[X [$T $F]]] (= X (TAIL 0 X)))g$T
Semantics:S(E0("TAIL)) = l ...
———————————————————
(TYPE A)Designates the atom associated with the type of the object designated by A (chosen from the standard 12); returns the handle of that atom.
F-Type:[ OBJECTS ] ← ATOMS
Examples:(TYPE 3)g’NUMBER
(TYPE ’3)g’NUMERAL
(TYPE (= 2 3))g’TRUTH-VALUE
(TYPE ’(= 2 3))g’PAIR
(TYPE ↑(= 2 3))g’BOOLEAN
Semantics:S(E0("TYPE)) = l ...
———————————————————
(UP A)Designates the form to which A normalises (i.e., it "double-designates"
↑Awhat A designates singly), returning the handle of that form. "↑EXP"
expands to "(UP EXP)" in standard notation.
F-Type:[ OBJECTS ] ← S-EXPRESSIONS
Examples:↑(+ 2 3)g’5
↑(LAMBDA SIMPLE [X] X)g’<CLOSURE: ... >
[’(= 2 3) ↑(= 2 3)]g[’(= 2 3) ’$F]
Semantics:S(E0("UP)) = l ...
———————————————————
6. Processor Top Level
Each reflective level of the processor is assumed to start off running the following procedure:
(DEFINE READ-NORMALISE-PRINT
(LAMBDA SIMPLE [ENV STREAM]
(BLOCK (PROMPT (LEVEL) STREAM)
(MAPLET [[FORM (NORMALISE (READ STREAM) ENV ID*)]]
(PROMPT #=)
(PRINT FORM STREAM))
(READ-NORMALISE-PRINT ENV STREAM))))
The way this is imagined to work is as follows: the very top processor level (infinitely high up) is invoked by someone (say, God, or some functional equivalent) normalising the expression ‘(READ-NORMALISE-PRINT GLOBAL INPUT-STREAM)’, where INPUT-STREAM designates the primary input channel. When it reads an expression, it is given the input string ‘(READ-NORMALISE-PRINT GLOBAL STREAM)’, which causes the level below it to read an expression, which is in turn given ‘(READ-NORMALISE-PRINT GLOBAL STREAM)’, and so forth, until finally the second reflective level is given ‘(READ-NORMALISE-PRINT GLOBAL STREAM)’. This types out ‘1>’ on the console, and awaits your input.
7. Environments
Environments are sequences of two-element sequences, with each sub-sequence consisting of a variable and a binding (both of which are of course expressions). A normal-form environment designator, therefore, is a rail of rails, with each rail consisting of two handles. Variables are looked up starting at the front (i.e. the second element of the first subrail whose first element is the variable is the binding of that variable in that environment). Environments can also share tails: this is implemented by normal-form environment designators sharing tails (this is used heavily in the GLOBAL/ROOT/LOCAL protocols, and so forth). Effecting a side-effect on the standard normal-form environment designator changes what the environment is, which is as it should be. Each level is initialised with the same global environment.
The four standard continuations:
C0: Accept the normalised function designator in an application.
C1: Accept the normalised arguments for a SIMPLE application.
C2: Accept the normalised first element in a rail fragment.
C3: Accept the normalised tail of a rail fragment.
(C4: Identifies top level call of READ-NORMALISE-PRINT.)
(C5: Used in order to read in 2-LISP structures by IN-2-LISP.)
X. A 2-LISP Glossary
...