[phylum]<3-LISP>course>manual>manual-1.bravo!6

3-LISP is based on a serial model of computation, consisting of a topology or graph of structures collectively called a structural field, examined and manipulated by a single active processor, which executes simple or complex procedures. This first section describes the elements of the structural field, the notation used to present them, and the types of procedure defined over them.

Objects in the structural field are called internal structures (or, when it is not confusing, just structures), since the structural field lies entirely within the computational process. Mathematical entities like numbers and sequences, on the other hand, are called external structures or abstractions (but never just structures). It is probably misleading to think of internal structures either as syntactic expressions or as platonic mathematical abstractions; they fall somewhere between those two in terms both of concreteness and of intensionality. The world consists of objects of all sorts, including both internal and external structures, and undoubtedly many other things as well.

Internal structures, although causal ingredients in a process, and capable of engendering behaviour, are nonetheless rather abstract sorts of objects; they aren’t really the sort of thing you can see or touch, or would find inside the computer if you were to take it apart. Rather, they are functionally defined abstractions, playing a crucial role in the explanatory theory of any 3-LISP process. Two properties are of particular interest. First, they should to be distinguished from the notations that are used to represent them outside of the machine (see section 1.b). Second, all structures are taken to be semantic objects — to signify or stand for something above and beyond what they themselves are. In particular, all structures are taken to designate something.

There are at least eleven types (kinds, categories) of internal structures that populate the structural field. The type of each structure is immutable; it may be interrogated with the standard procedure TYPE. Since they are internal, and can therefore be directly compared, identity conditions on structures are directly computable. Therefore the standard procedure ‘=’ can be used to test whether any two structures are one and the same.

NumeralsNumbersYes —a sequence of digits
BooleansTruth-ValuesYes —$TRUE or $FALSE
CharatsCharactersYes —#character
StringersStringsYes —"sequence of characters"
StreamersStreamsYes —{stream ... }
HandlesInternal StructuresYes —’EXP
Environment-designatorsEnvironmentsYesECONS{environment ... }
ClosuresFunctionsYesCCONS{closure ... }
RailsSequencesSomeRCONS[EXP EXP ... EXP]
Atoms(Designation of Binding)NoACONS sequence of alphanumerics
Pairs(Value of Application)NoPCONS(EXP . EXP)

A structure is said to be in normal form if it has three properties: it is stable (meaning that it normalizes to itself in all contexts), it is side-effect free (meaning that normalizing it will produce no processor, field, or external side effects), and context-independent (meaning that its semantics, procedural and declarative, are independent of context). A normal-form structure S1 is canonical if it is the unique normal-form designator of its designation. The claim on the 3-LISP processor is that, given a structure S1, it will yield a normal-form co-designating structure S2. Because of the stability of normal-form structures, it follows that the processor is idempotent.

Numerals: There are an infinite number of 3-LISP integer numerals, set in one-to-one correspondence to the abstract external numbers (ultimately we intend to support full rational or repeating fraction arithmetic, but at the moment only integers are defined). All numerals are canonical normal-form designators of numbers.

Booleans: There are just two boolean structures, notated as ‘$TRUE’ and ‘$FALSE’, that are constants (rigid designators) of Truth and Falsity, respectively. These normal-form structures may be viewed as the canonical true and false statements.

Charats: We do not claim to know what characters are, but charats are their normal-form designators. More precisely, a charat is an atomic structure associated one-to-one with character types (in the linguists’ sense) — i.e., there is only one charat for the character ‘+’, although there of course may be an arbitrary number of tokens (occurences) of that character.

Stringers: Stringers, often used but rarely mentioned as such, are canonical, normal-form designators of strings, associated with the string type (in the linguists’ sense) — e.g., there is only one stringer designating the string tokens of which would be printed ‘This is a 29 character string’.

Streamers: Streams are intended to serve as the interface with the outside world (i.e., to function essentially as communication channels); as a consequence we say virtually nothing about them, other than that they are legimitate arguments for reading and printing (i.e., by such procedures as CHAR-IN, READ, PRINT, etc.). Streamers are their normal-form designators. Note that no field relationships are defined over streamers.

Handles: Handles are unique normal-form designators of other internal structures — they are the 3-LISP field’s canonical form of structural quotation (not of lexical quotation — see section 3.b). Thus for the atom X there is a single handle, notated ’X. All 3-LISP structures have handles (including handles themselves; the handle of the handle of the atom X is notated ’’X).

Closures: Closures are normal-form function designators; because we have no adequate theory of procedural intension, they retain all the relevant contextual information from the point of function definition (structure and enclosing environment). Although closures, being first-class structures, can be inspected and compared, closure identity is far more fine grained than function identity.

Atoms: As in standard LISPs, atoms are atomic structures used as variables (schematic names). Atoms are associated with identifiers (lexical spellings) by the INTERNALIZE and EXTERNALIZE procedures — see ATOM-NOTATION and ATOM-NOTATED.

Pairs: Pairs (as in LISP 1.5) are ordered pairs, consisting of a first and second element (which may in turn be any structure in the field). Unlike standard LISPs, however, 3-LISP pairs are used for only one purpose: to encode function applications (a pair is therefore sometimes called a redex, for ‘reducible expression’).

Rails: Rails, derivative from standard LISP’s lists, are used to designate abstract sequences. Like the lists of LISP 1.5, isomorphic rails may be distinct. Those rails all of whose elements are in normal-form are by definition themselves in normal-form; thus the rail [1 2] is in normal-form, whereas the rail [1 (+ 1 1)] is not.

PPROCPairs ← StructuresYesYesNoPPROC
PARGSPairs ← StructuresYesYesNoPARGS
FIRSTRails ← StructuresNoYesNoFIRST
RESTRails ← RailsNoYesNoREST
ENVIRONMENTClosures ← EnvironmentsYesYesNoCLOSURE-ENVIRONMENT
PATTERNClosures ← StructuresYesYesNoPATTERN
BODYClosures ← StructuresYesYesNoBODY
COMMENTClosures ← StringsYesYesNoCOMMENT
DESIGNATIONHandles ← StructuresYesYesYesDOWN (↑)

All of these relations are total functions, with the exception of FIRST and REST, which are partial, both of them being undefined on so-called empty rails. The DESIGNATION function is one-to-one and onto; its inverse, therefore (DESIGNATION-1), is also a total function on structures, called HANDLE. It is a subset of the function designated by the standard procedure UP (↑).

Some structures — all numerals, charats, booleans, streamers, and their handles — are permanent members of any structural field configuration. Others — pairs, rails, atoms, and closures — can be brought into existence and connected to existing structures through the use of one of the primitive constructors. For example, the standard procedure called PCONS creates a new pair and establishes a PPROC and PARGS relationship between this pair and the two structures given to PCONS as arguments.

A structure X is accessible from structure Y if X can be reached from Y through a series of FIRST, REST, PPROC, etc. connections. In addition, the handles of all structures are accessible from those structures. When a so-called ‘new’ structure is generated (by CONS, RCONS, ACONS, CCONS, or PCONS) it is guaranteed to be otherwise inaccessible, meaning that it cannot be accessed from any other accessible structure. A rail is considered to be completely inaccessible if it and all of its tails (i.e., rails reachable via one or more applications of REST) are inaccessible. Thus RCONS returns an otherwise completely inaccessible rail, whereas CONS returns an inaccessible, but not completly inaccessible, rail.

The 3-LISP internalization function (the notational interpretation function Q that maps notations into internal structures) is not, strictly speaking, a primitive part of the language definition, since it is not used in internal processing. There is, however, a standard notation that is used in all documentation (including this reference guide) and provided with 3-LISP upon initialization. (A user may, however, completely replace it with his/her own version, if desired). This section explains that standard notation.

The goal of category alignment is met by having the standard notation for each type be identifiable in the first character (except for "notational escapes", described below), as indicated in the following chart:

Numeraldigit0, 1, -24, +100, 007
AtomletterA, +, CAR, ATOM
Boolean$$T, $F
Pair((A . B), (+ 2 3)
Rail[[1 2 3], []
Handle’’A, ’(+ 2 3), ’’[]
Charat##A, #/
Stringer""This is a string"
Other{{closure}, {streamer}

Examples: ‘(A . 1)’ notates a pair whose PPROC is the atom notated ‘A’ and whose PARGS is the numeral notated ‘1’; ‘[]’ notates an empty rail; ‘[1 2 3 4 5 6]’ notates a rail whose FIRST and REST would be notated ‘1’ and ‘[2 3 4 5 6]’, respectively; ‘’100’ notates the handle for the numeral that would be notated ‘100’.

2.An atom label may begin with a digit (or sign) providing it contains at least one non-digit (i.e., ‘6N237E’, ‘-X’ and ‘1+’ are valid atom labels). Any atom notation that also satisfies the rules for numeral tokens will be taken to be the latter. For example, ‘1-’ and ‘+’ notate atoms, whereas ‘+1’ and ‘-1’ notate numerals.

3.Left brace (‘{’) is used as a general notational escape, not only for closures and streamers, but also for un-labelled atoms, errors, and other notational commentary. This notation is employed only on output.

5.Sign-character::=‘+’ | ‘-’
Digit-character::=‘0’ | ‘1’ | ‘2’ | ‘3’ | ‘4’ | ‘5’ | ‘6’ | ‘7’ | ‘8’ | ‘9’
Any-character::=Any character in the character set: i.e., carriage-return, space, or
any of:ABCDEFGHIJKLMNOPQRSTUVWXYZ
abcdefghijklmnopqrstuvwxyz
1234567890!@#$%~&*-=+\|<>()[]{}←↑;:’",./?
Atom-character::=Any character except Space, carriage-return, ‘$’, ‘#’, ‘"’, ‘;’, or Special
String-character::=Any character except ‘"’ and ‘%’ (see note)
Normal-character::=Any character except ‘%’ and carriage-return (see note)
Special::=‘(’ | ‘)’ | ‘[’ | ‘]’ | ‘↑’ | ‘↑’ | ‘.’ | ‘,’ | ‘{’ | ‘}’ | ‘’’ | ‘%’

Note: A percent sign (‘%’) may be used as a character-level quote to insert double quotes and percent signs into strings; thus the notation for the stringer designating the string ‘Is "The 7% Solution" playing?’ would be ‘"Is %"The 7%% Solution%" playing?"’. Similarly, ‘%%’ may be used to insert percent signs into atom names or comments.

In the standard notation, structures are notated with sequences of lexical tokens, each of which is composed of a sequence of one or more characters chosen from a collection of characters called the character set, listed above.

Sequences of characters are broken down into tokens in the conventional way, with the rule that there must always be at least one token separator between adjacent non-special tokens. For example, the character stream ‘(foo [1 $T ↑#x ’’100])’ consists of the ten tokens: ‘(’, ‘foo’, ‘[’, ‘1’, ‘$T’, ‘↑’, ‘#x’, ‘’’100’ ‘]’, and ‘)’.

For convenience, the following table lists all "special" (i.e., non alpha-numeric) characters that are used for some special purpose. Note that the standard notation uses one character (down-arrow: ‘↑’) that is not part of the standard ASCII character set, but we reserve ASCII backslash (‘\’) so that it can be used in its stead. We assume, in other words, that the 3-LISP standard notation is indeed based on the standard ASCII sequence, but simply choose to print backslash as a down-arrow.

(—starts pairs↑—abbreviation for UP
)—ends pairs↑—abbreviation for DOWN (same as ‘\’)
.—separates PPROC and PARGS%—character quotation operator
[—starts rails,—normalized expression within a quote
]—ends rails;—starts comments (to CRLF)
’—quotations (including handles)-—starts negative numerals
#—charats+—starts some positive numerals
$—booleans ($T and $F){—starts notational escapes
"—starts and ends strings}—ends notational escapes

A general comment: The internalization function described above is not "onto"; there are structures that are not the result of internalising any lexical expression, for two reasons. First, upon internalisation, all pairs and rails notated are created from previously-inaccessible structures. Hence, any structure with a shared sub-structure will have no lexical counterpart. Second, closures and un-named atoms (those created by ACONS) have no standard lexical counterparts. The standard version of EXTERNALISE, approximately the inverse of INTERNALISE, makes no attempt to deal in a sophisticated way with either of these problems. In particular, no attempt is made to show shared substructure, and un-notatable structures — closures, nameless atoms, and circular structures — are marked with a standard lexical escape: a note enclosed in braces (e.g., ‘{closure}’, ‘{streamer}’, etc.).

On quotation: Simple quoted expressions (specifically, those not containing commas) notate handles: ‘’’ expression, if expression contains no commas, notates the handle for the structure notated by expression. Comma’ed expressions may be used within the scope of the quote, however, allowing one to conveniently notate expressions for constructing structures that resemble the structure that would be notated by the given lexical expression, except that certain parts are substituted in. I.e., the comma notation gives you a "fill-in-the-blanks" capability within quotations. These so-called complex quotations are particularly useful when defining macros. (The idea is based on the back-quote feature, borrowed from MACLISP [Moon 74], and is reminiscent of Quine’s "corner quotes" [Quine ??].)

In order to understand the comma notation precisely, note that ‘’(A . B)’ is in some ways equivalent to ‘(PCONS ’A ’B)’; the latter notates a structure that normalizes to the structure that would be notated by the first. Trading on this correspondence, the notation ‘’(A . ,X)’ is lexical shorthand for ‘(PCONS ’A X)’, which notates a structure that would normalize to a structure that would be notated ‘(A . HELLO)’ in an environment where X was bound to ’HELLO.

’1’1’1
’(A . ,B)(PCONS ’A B)’(A . 2)
’[A ,B C](RCONS ’A B ’C)’[A 2 C]
’[[A B][,C D]](RCONS ’[A B] (RCONS C ’D))’[[A B][’3 D]]
’’[A ,B ,,C](PCONS (’RCONS’ [’A B ,C]))’(RCONS [’A B ’3]) (i.e., ’[A ,B 3])

Lexical Quotation Principle: A lexical expression E1 preceded by a quote will notate a structure S1 that designates a structure S2 that would be notated by E1, with the exception that those fragments of S2 that would be notated by portions of E1 that are preceded by a comma will in fact be designated by the structures that those portions notate, rather than notated by them directly.

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.

The primitive procedures (listed below) are those 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..

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
CLOSURE-ENVIRONMENT 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-OUTcharacter operations on streams
STRING-IN, STRING-OUTstring operations on streams
READ, PRINTto read or print structures
INTERNALIZE, EXTERNALIZEto mediate between notation and structure
System:LOADloads files into 3-lisp processor
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, ...

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).