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

GLOSSARY3-LISP REFERENCE MANUALMarch 12, 1984

———————————

9. A 3-LISP Glossary

———————————

Accessible — An internal structure is accessible if it is the value of one of the 9 binary functions defined over the structural field (CAR, CDR, FIRST, REST, ENV, PATTERN, BODY, PROCEDURE-TYPE, or REF) on some argument that in turn is accessible. In addition, the handles of all structures are accessible from their referents. Finally, the booleans, numerals, and charats are always accessible. The lexical internalisation function also makes a considerable number of atoms accessible (all those that have established names) by keeping an explicit representation of the name–atom pairings. When a so-called ‘new’ structure is generated (by RCONS, SCONS, ACONS, PCONS, or CCONS) it is guaranteed to be otherwise inaccessible, meaning that it cannot be accessed from any other accessible structure. Finally, a rail is considered to be completely inaccessible if it and all of its tails are inaccessible. Thus (RCONS ’A ’B ’C) returns as otherwise completely inaccessible rail, whereas if X is bound to ’[B C], then (PREP ’A X) returns an inaccessible (but not completely inaccessible) rail.

Apply — The relationship between an abstract (external) mathematical function and arguments to values (the application of the addition function to the platonic numbers 1 and 2 is the number 3).

Atom — A non-composite internal structure used as a environment-relative name.

Back-quote — A lexical notation operator (borrowed from MACLISP), designed to facilitate the construction of quoted structures with context-dependent insertions, as in the construction of macros. 3-LISP back-quotes are very much like Quine’s corner quotes <ref>. For example, ̀ (+ ,A ,B) abbreviates (PCONS ’+ (RCONS A B)), and will normalise to ’(+ 1 2) in an environment in which A is bound to ’1 and B to ’2. See section 4.c. [[ Put in the backquote principle ]]

Binding — xxx

Boolean — One of two non-composite internal structures — canonical normal-form designators of Truth and Falsity, respectively. In the standard notation the two booleans are spelled ‘$T’ and ‘$F’.

C-PROC!, C-ARGS!, C-FIRST!, C-REST! — The four standard continuations engendered at each reflective level by the reflective processor. See sections 111.

Canonical — xxx

Character — xxx

Charat — A non-composite internal structure that is a normal-form canonical designator of a character. In the standard notation charats are notated with two characters: a sharp sign (‘#’) followed by the character designated; thus ‘#4’ notates the charat that designates the character ‘4’.

Closure — A primitive internal structure type: a composite, normal-form but not canonical designator of a function. Closures are constructed with CCONS (q.v. section 111). Closures, being internal structures, contain environments designators, patterns, and bodies, which may be accessed with the selector functions CENV, PATTERN, and BODY, respectively.

Co-Designate — xxx

Completely Inaccessible — See ‘Accessible’.

Context Independent — xxx.

Continuation — xxx

Continuation Passing Style (CPS) — xxx

Declarative Import — The first coordinate of the full significance of a 3-LISP structure. The declarative import is our reconstruction of what a structure designates or refers to. For example, we take the numeral ‘144’ to designate the number that is the square of 12; thus we would say that 144 is the declarative import of that numeral.

Designate — The relationship between a symbol X and the object that is F(X). For example, the numeral 1 (i.e., the numeral notated with the character ‘1’) designates the number 1; the handle ’X designates the atom X; and the expression (LAMBDA SIMPLE [X] X) designates the identity function. designation, designator

Designator — xxx

Designation — xxx

Digit — xxx

Dynamic Scoping — xxx

Environment — A theoretical entity the captures part of the processor state (the other is the continuation). Specifically, an environment is an external sequence of two-tuples of atoms and bindings; thus the environment designated by the 3-LISP structure [[’A ’3] [’ID ’{CLOSURE [] ’[X] X}] [’HANDLE ’’A]] contains bindings for three structures (A, ID, and HANDLE, bound respectively to the numeral 3, a closure designating the identity function, and the handle ’A). Note that all well-formed 3-LISP environments contain bindings for only atoms, and all bindings are normal-form structures.

Evaluate — We do not use the term ‘evaluate’, since it is ambiguously used as a function from expressions either onto their designations or onto co-designative simpler expressions.

Expression — xxx

Extension — xxx

Extensional — xxx

External — xxx

Externalise — xxx Externalisation

First-order — xxx

Function — An external (abstract) mathematical object, that can be applied to arguments so as to yield values. Mathematicians typically treat functions as sets of ordered pairs; we don’t really care one way or another.

Functional — xxx

Handle — A non-composite internal structure that is a normal-form and canonical designator of another internal structure. Handles are notated with a single prefixed single-quote mark: thus the lexical expression ‘ ’A ’ notates the handle of the atom A.

Higher-order — xxx

Hyper-intensional — xxx

Inaccessible — See ‘Accessible’.

Internal — xxx

Internalise — xxx Internalisation

Intension — xxx

Intensional — xxx

Internal Structures — Any of the ingredients in the 3-LISP structural field.

Kernel — xxx

Lexical — xxx

Lexical Scoping — See ‘Static Scoping’.

Macro — xxx

Mention — (As opposed to ‘Use’.)

Meta-structural — xxx

Normal-form — Structures are defined to be in normal-form if they are stable (q.v. — self-normalising), side-effect free (q.v. — processing them engenders no side-effects), and context-independent (q.v. — neither Y nor F depends on the environment or continuation). Of the eleven 3-LISP structure types, eight and a half are in normal-form: the handles, charats, numerals, booleans, closures, stringers, environment designators, streamers, and some of the rails (those whose constituents are in normal form). See the table in section 111.

Normalise — A form of simplification in which structures are converted into a normal-form (q.v.) codesignating (q.v.) structure.

Notation — xxx

Number — The standard mathematical notion (external, abstract, Platonic, whatever). 3-LISP deals only with integer numbers.

Numeral — A non-composite internal structure that is a normal-form and canonical designator of a number. The 3-LISP field is presumed to have an infinite number of numerals, one per number.

Order — xxx

Pair — A "composite" internal structure, used to encode redexes (reducible expressions). Each pair has a CAR and a CDR; the pair designates the value of the function designated by the CAR applied to the arguments designated by the CDR (if the function is extensional).

Phi (F) — xxx

Psi (Y) — xxx

Primitive — xxx

Procedural Consequence — xxx

Processor — xxx

Procedure — xxx

Quotation — xxx

Rail — xxx

Redex — (Short for reducible expression) An internal structure that encodes designators of functions and arguments, capable of being reduced into normal-form.

Reduce — xxx Reduction

Referent — xxx

Referential Transparency — xxx

Reflect — xxx

Reflection — xxx

Reflective — xxx

Reflective Processor — xxx

Reflective Procedure — xxx

Result — xxx

Returns — xxx

Semantics — xxx

Semantically Rationalised — xxx

Semantically Flat — xxx

Sequence — The standard mathematical notion of an ordered set of objects. The same element may occur at different positions in the sequence (thus the sequence designated by [1 2 1] is of length 3 and contains two occurences of the number 1), but there is only one sequence with the same elements at each position. Sequences may be of null, finite, or infinite length.

Side Effect — xxx

Significance — xxx

Simple — xxx

Simplification — xxx

Stable — xxx

Standard — xxx

Standard Notation — The internalisation function Q that maps from external lexical notation into internal structures can be changed by the user; it is not considered a primitive part of the language. Nonetheless there is a standard notation, which is used throughout this manual, and is translated by the version of Q that is provided with 3-LISP. It is documented in section 4.

Static Scoping — xxx

Stream — xxx

Streamer — xxx

String — xxx

Stringer — xxx

Structural Field — The full collection of internal structures, relationships defined over them, and accessbility relationships that, together with the 3-LISP processor, constitute the 3-LISP machine.

Structure — xxx

Syntax — xxx

Tail-Recursive — A position within a composite structure is tail-recursive with respect to the overall structure if the processing of any structure in that position can be done with the same continuation as is used for the encompassing structure. Thus for example ... Also, a processor runs programs tail-recursively if it in fact processes program fragments that are in tail-recursive positions ...

Theta (Q) — xxx

Token — xxx

Truth-Values — xxx

Type1 — (as opposed to token)

Type2 — (of the "sort" variety)

Type Alignment — A correspondence between the types of internal structure, procedural consequence, and declarative import.

Use — (As opposed to ‘Mention’.)

Unsorted — xxx

Untyped — xxx

Value — The result of applying a mathematical function to its arguments. Thus the value of the addition function applied to the numbers 1 and 2 is the number 3. As opposed to normal-forms, values need not be internal structures.

Variable — xxx

Vector — xxx

Y-Operator — xxx