Page Numbers: Yes X: 306 Y: 1.0" First Page: 33
Margins: Top: 1.0" Bottom: 1.3"
Heading:

STANDARD PROCEDURES3-LISP REFERENCE MANUAL March 11, 1984

—————————————–

4. Standard Procedures

—————————————–

There are about 150 standard procedures in 3-LISP: procedures that are described in this manual, used without comment in utility packages, and so forth (we also expect to ‘compile’ these procedures into the standard implementation). A 3-LISP programmer should consider these to be the base set, on top of which to define other functionality as desired. Within the set of standard procedures, however, are two important sub-classes: primitive procedures that provide access to the structural field and to the external world (e.g., I/O); and kernel procedures that are essential to the workings of the system. These two sets are neither mutually exclusive nor exhaustive: many of the primitives are kernel procedures as well (NULL, for example), but there are some non-kernel primitives (LENGTH, +, ACONS, etc.). In addition, it is clear that many kernel procedures are not primitive (LAMBDA, BINDING, NORMALISE, and NORMAL, to name a few). Finally, there are about 90 other standard procedures (MAX, LETSEQ, DO, etc.) that are neither primitive nor kernel.

4.a. Primitive Procedures

There are a number of primitive procedures (listed below) that have no definition within 3-LISP, and that are reduced with arguments in "unit time", in the sense that from no level of reflective access is there any visible grain to their operation. All the 3-LISP primitives are simple: there are no primitive reflectives. To a certain extent the particular set is arbitrary, and it is certainly not minimal: LIST, for example, could be defined in terms of RCONS, UP, and DOWN; LENGTH could be defined in terms of NULL and +; etc..

CategoryStandard NameFunctionality

Identity:=defined all types except functions
Structural:LIST, CONS, RCONSto construct and examine
LENGTH, NTH, TAIL, NULL sequences and rails
CCONS, PATTERN, BODY to construct and
ENVIRONMENT-DESIGNATOR examine closures
ACONSto construct atoms
PCONS, PPROC, PARGSto construct and examine pairs
Control:EFan "extensional" if-then-else conditional
Semantics:UP (↑), DOWN (↑)to mediate between designator & designation
Arithmetic:+, -, *, /, <, >,<=,>=, <>as you would expect
I/O:CHAR-IN, CHAR-OUTprimitive operations on streams
READ, PRINTto read or print structures
INTERNALISE, EXTERNALISEto mediate between notation and structure
PRESENT, OBTAINto communicate about arbitary objects
[[[[System:LOADFILE, EDITDEFsystem support]]]]
Typing:TYPEdefined on 18 types (10 internal, 8 external)
SIMPLE, REFLECTIVE, to distinguish different types of closures
MACRO, PRIMITIVE
SEQUENCE, NUMBER, STRING,characteristic functions on all types
FUNCTION, CHARACTER, TRUTH-VALUE, STREAM, ATOM, PAIR,
RAIL, BOOLEAN, CLOSURE, HANDLE, NUMERAL, ...

4.b. Kernel Procedures

The kernel procedures are those that are used crucially in the 3-LISP reflective processor (i.e., they are used by the reflective processor to process the reflective processor). As a consequence, rebinding the standard name of one of these closures in the global environment (more accurately: in any environment captured inside any of the kernel closures) would cause the reflective tower to fall. Thus for all practical purposes the kernel procedures are as ‘wired-in’ to 3-LISP as are the primitives, even though in a strict sense they have visible definitions, and are compositionally executed by the processor (by expanding closures). Note that there are reflective kernel procedures as well as simple ones. It turns out that the kernel procedures are exactly the acquaintances of NORMALISE, although this needn’t have been so (they could have been a subset, since there might have been code in the reflective processor that, although used when processing some forms of user code, didn’t happen to be used to process the processor itself).

Kernel Primitives

PPROC, PARGS, RCONS, LIST, PREP, NTH, TAIL, NULL, CCONS, REFLECTIVE, MACRO, ENVIRONMENT-DESIGNATOR, PATTERN, BODY, TYPE, =, EF, UP, DOWN

Kernel Non-primitives

UNIT, DOUBLE, REST, 1ST, 2ND, MEMBER, VECTOR-CONSTRUCTOR, MAP, ENVIRONMENT, REFLECTIVE,
DE-REFLECT, ATOM, PAIR, RAIL, HANDLE, EXTERNAL, LAMBDA, SIMPLE, BINDING, BIND, LET, IF, COND, COND-HELPER, AND, AND-HELPER, NORMALISE, REDUCE, NORMALISE-RAIL, NORMAL, NORMAL-RAIL, PRIMITIVE

4.c. Standard Procedure Guide

The remainder of this section is taken up with descriptions of each of the standard procedures. The 3-LISP code for the standard procedures can be found in Appendix A. Notes on the format of these descriptions:

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. In some cases, the typing restrictions specified in this section are stricter than one would expect given the appendix A definitions.

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. Intensional positions (positions that are or may not necessarily be normalised) are indicated with <<<???>>>>.

5.Several one-word attributes are associated with each procedure that can 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 ’HELLO PRIMARY-STREAM) HELLO
1= ’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: <<< ??? >>>