[phylum]<3-LISP>documentation>old-3-manual-01.bravo!1

𔁇.Overview 𔁈
𔁈.Model of Computation 𔁉
𔁉.Semantics 𔁊
𔁊.Notation 𔁌
𔁋.Standard Procedures 󈋆
𔁌.Reflective Programming 󈋈
𔁍.Implementation 󈋒
𔁎.Standard Procedure Definitions 󈋘
𔁏.Standard Procedure Guide 󈋘
10.Standard Procedure Index 󈋘
11.Glossary 󈋤

The 3-LISP programming language is designed to illustrate both the integration of declarative and procedural semantics in a unified calculus, and the provision of reflective capabilities. It is a direct descendent of McCarthy’s LISP 1.5 and of Sussman and Steele’s SCHEME; many features of those formalisms are embodied in 3-LISP without comment. There are, however, some major differences between 3-LISP and prior LISP dialects. More specifically:

1.Statically Scoped and Higher Order: Like SCHEME and the untyped l-calculus, but unlike LISP 1.5, functions of any degree may be used in 3-LISP as arbitrary arguments. Free variables are statically (lexically) scoped. Consequently, flat (non meta-structural) 3-LISP is on its own a higher-order functional calculus.

2.Untyped and Unsorted: Though the semantic domain and primitive functions are strongly typed (in the computer scientist’s sense — what logicians call sorted), user-defined procedures need not be typed, and no typing information is explicitly stated. In addition, there are no type restrictions (in the logician’s sense).

3.Meta-Structural: As in all LISPs, quotation is provided primitively, enabling the explicit mention of program structures. Because naming and normalisation are orthogonal, quotation is a structural primitive, not a functional primitive (i.e. there is no primitive QUOTE procedure). Handles (normal-form designators of internal structures) are unique and canonical normal-form structure designators.

4.Semantically Rationalised: Traditional evaluation is rejected in favour of independent notions of simplification and designation. The 3-LISP processor is based on a form of simplification called normalisation that takes each structure into a co-designating structure in normal form. As a consequence, processing is semantically flat: programs may cross the meta-structural hierarchy only with the explicit use of the two level-crossing primitives (↑ and ↑, q.v.); note that reflective procedures are not level-crossing. In addition, the processor is idempotent (all normal-form structures normalise to themselves). With the exception of the one side-effect primitive (REPLACE), the declarative (F) and procedural (Y) semantics can be specified independently.

5.Category Aligned: There is a one-to-one correspondence across primitive structural categories, declarative semantic categories, and categories of procedural treatment. In addition, there are corresponding notational categories, although the standard notation (see section 4) has some additional complexity for user convenience.

6.Procedures and Functions: The standard (but user-defined) procedure LAMBDA is used purely as a naming operator; recursion is treated with the explicit use of circular-structure generating Y-operators. Closures are a distinguished structural type, and are normal-form function designators.

7.Procedurally Reflective: 3-LISP supports two kinds of procedure: simple and reflective. Reflective procedures are run not in the object level of a program, but integrated into an explicit version of the processor that was running that program. Thus, the 3-LISP virtual machine consists of an infinite tower of type-equivalent processors. This architecture unifies the traditional notions of an explicitly available EVAL and APPLY, meta-circular interpreters, and idiosyncratic extensions to facilitate debugging.

In spite of these powers, 3-LISP has various limitations arising from the fact that it is purely procedural language (it should be kept in mind that 3-LISP, in the final analysis, is a dialect of LISP). These limitations are worth noting at the outset, so that potential programmers can avoid searching in the manual for features and provisions that are simply not to be found. Specifically:

1.Too fine-grained: The reflective (and meta-structural) facilities of 3-LISP provide an extremely fine-grained access to program and processor state (3-LISP reflection is what in philosophy is called hyper-intensional). A 3-LISP reflective procedure, in particular, can reason about what general methods are being employed in a program only by sifting through a myriad inconsequential matters of spelling and syntactic form. The 3-LISP processor state, in addition, is encoded (in the environment and continuation structures) in what may seem to be overly precise detail. There is no doubt that a reflective dialect based on a more coarsed-grained model of procedural intension would be nice; providing an adequate theory of procedural intension, however, is one of the most major and difficult outstanding problems in computer science and AI. As soon as someone can provide an adequate account of procedural intension, a reflective dialect based on it could be constructed, with very much the same general architecture as has been employed in 3-LISP.

2.No descriptions: Although given a declarative semantics, 3-LISP is still fundamentally a procedural language: you cannot say anything in it (3-LISP structures lack assertional force). As a formal model of reflective thinking or reasoning, therefore, 3-LISP is utterly inadequate; some sort of descriptive or assertional language is clearly required. Again, given a computationally adequate descriptive language, a reflective dialect could be constructed based on 3-LISP’s underlying architecture.

3.No intentional accounts: Related to both of the foregoing points is the fact that a 3-LISP program, upon reflecting, is not given any sort of intentional description — say, of what the object level program was trying to do when it reflected. Any user of 3-LISP will realise that a model of reflection that provided intentional description along with causally connected access to the process state would be nice. We would like this too.

4.Not mathematically "pure": 2-LISP, the non-reflective dialect on which 3-LISP is approximately based, contains a variety of features (side-effects of various sorts, sequential processing of vector elements, etc.) that are classically considered inelegant. We have included such facilities in 3-LISP for two reasons: a) because we believe that in constructing rough-and-tumble systems able to reason about our complex embedding world, one needs mechanisms to deal with state, failure, program change, and so forth, and b) because we aim in part to show how rationalised semantics and procedural reflection are powerful not only in mathematically pure calculi, but also in real computational settings. It is easy to imagine, however, a reflective dialect without any replacing operations, for example; such a subset might in fact be preferable to full 3-LISP in certain circumstances. Merely by providing a facility, in other words, we do not mean to imply that we consider using it to be good programming practice.

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 (what is typically called an ‘interpreter’, although we use the term ‘interpretation’ in its original semantic sense: as between sign and signified).

Objects in the structural field are called internal structures or, when it is not confusing, just structures; mathematical entities like numbers and sets are called external structures or abstractions (but never just structures). The world consists of entities of all sorts, including both internal and external structures, and undoubtedly many other things as well. There are 9 internal structure types, over which 8 asymmetric first-order locality relationships are defined. (The notational information here is informal; for more detail see section 4.) Note that six and a half of the categories are normal-form structures, of which five are canonical.

1.NumeralsNumbersYesYesa sequence of digits
2.BooleansTruth-ValuesYesYes$T or $F
3.HandlesInternal StructuresYesYes’EXP
4.CharatsCharactersYesYes#CHAR
5.StreamersStreamsYesYes{STREAMER: ... }
6.ClosuresFunctionsYesNo{CLOSURE: TYPE ENV PAT BODY}
7.RailsSequencesSomeNo[EXP EXP ... EXP]
8.Pairs(Value of Application)No—(EXP . EXP)
9.Atoms(Designation of Binding)No—a sequence of alphanumerics

1.CARPairs ← StructuresYesYesYesNo
2.CDRPairs ← StructuresYesYesYesNo
3.FIRSTRails ← Structures U {T}NoYesYesNo
4.RESTRails ← Rails U {T}NoYesYesNo
5.ENVClosures ← RailsYesYesYesNo
6.PATTERNClosures ← StructuresYesYesYesNo
7.BODYClosures ← StructuresYesYesYesNo
8.REFHandles ← StructuresYesNoYesYes

1.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). Note that these numerals, being in some sense rather abstract elements of a field, have no radix (radix in 3-LISP is a property of numerical notations).

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

3.Handles: Handles are unique normal-form designators of other internals structures — they are the 3-LISP field’s form of canonical quotation. Thus for the atom X there is a single handle, written ’X. All 3-LISP structures have handles (including handles themselves; thus the handle of the handle of the atom X is ’’X); this is one of several ways in which the field is taken to be infinite.

4.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); there is only one charat for the character ‘+’, although there of course may be an arbitrary number of tokens (occurences) of that character.

5.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 INPUT and OUTPUT. Streamers are their normal-form designators. Note that no field relationships are defined over streamers. Streamers will probably play a role in implementations and embeddings of 3-LISP, but at present the language puts no specific constraints on the way in which this role is played.

6.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 (expression and enclosing environment). Although closures, being first-class structures, can be inspected and compared, closure identity is far more fine grained than function identity.

7.Rails: Rails, derivative from standard LISP’s lists, are used to encode enumerations (i.e., to designate abstract sequences). Like the lists of LISP 1.5, isomorphic rails may be distinct. Those rails whose elements are 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.

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

The 3-LISP processor (ignoring for the moment its reflective capabilities) is a serial, sequential, behaving agent with state, that takes structures onto other structures. It may be represented in terms of a function from structures (programs) and processor states onto other structures (and other processor states), as the discussion of semantics in the next section shows in detail. Very simply, the processor is designed to satisfy a number of criteria:

1.It is a normaliser, in that it takes structures onto normal-form codesignators. In contrast with the l-calculus, where the notion of normal-form is defined in terms of the assumed l-calculus processor (some combination of a- and b-reduction), we define a structure to be in normal-form iff it satisfies three criteria (each of these concepts is defined formally in section 3):

It then requires a proof to show that the processor satisfies this mandate; this can be done, except of course that a user may, using reflection, cause the processor to violate this (or indeed any other possible) specification.

The state of the processor is represented in two theoretical entities: an environment (an ordered sequence of pairings of atoms and bindings) and a continuation (a function from partial results to results). Upon reflection, normal-form designators of these two state variables are provided, as well as a designator of the program structure, as arguments to reflective procedures.

1.Field side effects: Alterations to the mutable first-order relationships on the field. Thus for example the standard procedure RPLACA, when reduced with an argument, engenders a change in the CAR function from pairs to other internal structures.

3.Continuation side effects: Alterations to the normal flow of processor control. A procedure is said to engender a continuation side effect if it does not call its continuation with the result of processing its body (the redex ‘(QUIT)’, for example, discards its continuation completely).

The full semantical significance of a 3-LISP internal structure consists of two parts: its declarative import and its procedural consequence. Very roughly, the declarative import is what a structure stands for or designates (usually, but not always, independent of any active processing on the part of the machine); its procedural consequence is what behaviour it engenders upon being processed (what it returns, how it affects the processor and field state, etc.). For example, declaratively, the boolean constant $T designates Truth, whereas its procedural consequence is that it is returned unchanged, causing no side-effects.

The nine internal structure types divide into two natural classes: the normal-form types and the general-purpose types. In the first class are seven types: six (booleans, numerals, rails, closures, streamers, and charats) that are normal-form designators of the five external types, plus the handles, which are normal-form designators for all internal structures. In the second (general purpose) class are the atoms and pairs (used for general context-relative expressions as, respectively, names and redexes), which can designate entities of any type. These semantical relationships are pictured in the following table:

More formally, we associate with each expression its full significance, using the meta-theoretic function S. The procedural consequence is broken into three parts: what is returned (Y), the resulting environment, and the resulting structural field. Thus S is typed as follows:

NOTE: ... There is lots and lots and lots of work to be done here: note that all of this mathematics is 2-LISP; admit that we don’t have an appropriate 3-LISP semantics yet; define SIDE-EFFECT-FREE and NORMAL-FORM etc.; Put in the general F − Y − Q diagram; show the 3-LISP processor regimen, etc.; Should take about a week. ...