[phylum]<3-LISP>documentation>issues>issue-15.bravo!2

———————————————————————————————————————————

Description:Although traditional LISPs provide no indication of the semantics of (object-level) data structures, the declarative orientation of our semantics suggests that 3-LISP should do so. In addition, vanilla 3-LISP supports no concept of data abstraction or modelling — clearly a pre-requisite to the proper semantical treatment of general data structures. We propose a variant of 3-LISP, called 3d-LISP, with methods for more abstract data designation, for which the normalisation theorem holds.

———————————————————————————————————————————

Since in general (F . A) designates the value of the function designated by F applied to the arguments designated by A, we extend 3-LISP to include non-reducible pairs for modelling objects outside the standard semantical domain. Specifically, suppose you want to model the complex number C1 with the two reals X1 and Y1, such that C1 = X1 + Y1i. Then, if F is the function lX,Y . X + Yi, then C1 = F(X1,Y1). Using 2/3-LISP notation, C1 is (F X1 Y1). As it happens, in this case we could define F as follows:

Thus (F X1 Y1) would designate C1 all right, but would never terminate if it were reduced. However in general the function mapping the arguments to the desired object — which we will call the modelling function — could not be defined in 2/3-LISP. Suppose, for example, we model people with their names: Church could be modelled by (G "Alonzo Curch"), for some G. But in this case G cannot be defined, since people are not part of the semantical domain, or of any set-theoretic or mathematical of it.

Essentially the idea is to add constants, used for arbitrary purposes by the user, but also for designating modelling functions.

1.NumeralsNumbersYesYesa sequence of digits
2.BooleansTruth-ValuesYesYes$T or $F
3.HandlesInternal StructuresYesYes’EXP
4.Constants(Anything)YesNo@EXP
5.RailsSequencesSomeNo[EXP EXP ... EXP]
6.Pairs(Value of Application)SomeNo(EXP . EXP)
7.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.REFHandles ← StructuresYesNoYesYes

Constants are typically used for two purposes: as rigid designators (proper names) for anything the user wishes, and for modelling functions for data abstraction.

Typing:TYPEdefined on 11+ types (7 internal, 4+ external)
Identity:=defined on 9 types (everything except modelled entities)
Structural:PCONS, CAR, CDRto construct and examine pairs
ACONS, CCONSto construct atoms and constants
RCONS, SCONS, PREPto construct rails and sequences
LENGTH, NTH, TAIL, EMPTYto examine " " "
Modifier:REPLACEto modify mutable structures
Control:EFan extensional if-then-else conditional
Semantics:UP, DOWNto mediate between sign & signified
Arithmetic:+, -, *, /, <, >as usual
I/O:INPUT, OUTPUTprimitive operations on streams

————————————————————————————————————————————

(define READ-NORMALISE-PRINT
(l [level env]
(block (prompt level)
(normalise (read stream) env reply))
(read-normalise-print level env))))

(define NORMALISE
(l [exp env cont]
(cond [(normal exp) (cont exp)]
[(atom exp) (cont (binding exp env))]
[(rail exp) (normalise-rail exp env cont)]
[(pair exp) (reduce (car exp) (cdr exp) env cont)])))

(define REDUCE
(l [proc args env cont]
(normalise proc env
(l [proc!]; C-PROC!
(if (reflective proc!)
(↑(de-reflect proc!) args env cont)
(normalise args env
(l [args!]; C-ARGS!
(cond [(primitive proc!) (cont ↑(↑proc! . ↑args!))]
[(constant proc!) (cont (pcons proc! args!))]
[$T (normalise (body proc!)
(bind (pattern proc!) args! (environment proc!))
cont)]))))))))

(define NORMALISE-RAIL
(l [rail env cont]
(if (empty rail)
(cont (rcons))
(normalise (1st rail) env
(l [first!]; C-FRST!
(normalise-rail (rest rail) env
(l [rest!] (cont (prep first! rest!))))))))); C-REST!

————————————————————————————————————————————

(define NORMAL
(l [x]
(select (type x)
[@atom $F]
[[@numeral @boolean @handle @constant] $T]
[@rail (normal-rail x)]
[@pair (and (constant (car x)) (normal (cdr x)))])))

(define PRIMITIVE
(let [[primitives [↑type ↑= ↑pcons ↑rcons ↑scons ↑acons ↑ccons ↑car ↑cdr ↑prep
↑length ↑nth ↑tail ↑empty ↑replace ↑ef ↑up ↑down ↑+ ↑* ↑- ↑/
↑< ↑> ↑input ↑output]]]
(l [proc] (member proc primitives))))

(define BIND
(l [pattern args bindings]
(cond [(atom pattern) (prep (scons pattern args) bindings)]
[(handle args) (bind pattern (map up ↑args) bindings)]
[(and (empty pattern) (empty args)) bindings]
[$T (bind (1st pattern)
(1st args)
(bind (rest pattern) (rest args) bindings))])))

————————————————————————————————————————————

(define LAMBDA
(lambda reflect [[kind pattern body] env cont]
(reduce kind ↑(scons ↑env pattern body) env cont))))))

(define SIMPLE (l [env pattern body] (@function env pattern body)))
(define REFLECT (l [env pattern body] (@reflector (simple env pattern body))))

(define MACRO
(l [def-env pattern body]
(reflect def-env
̀ [,pattern env cont]
̀ (normalise ,body env cont))))

(define MULTI-Y-OPERATOR
(l funs
(let [[temps (map (l [fun] (l ? ?))
funs)]]
(map (l [temp fun] (replace ↑temp ↑(fun . temps)))
temps
funs))))

(define SET
(lambda reflect [[var binding] env cont]
(normalise binding env
(l [binding!]
(block (rebind var binding! env)
(cont))))))

(define REBIND
(l [var binding env]
(cond [(empty env) (replace ↑env ↑[[var binding]])]
[(= var (1st (1st env))) (rplacn 2 ↑(1st env) ↑binding)]
[$T (rebind var binding (rest env))])))

(define LETSEQ
(lambda macro [list body]
(if (empty list)
body
̀ (let [,(1st list)]
(letseq ,(rest list) ,body))))))

(define LETREC
(lambda macro [list body]
(let [[pattern (rcons . (map 1st list))]]
̀ (let [[,pattern
(multi-y-operator .
,(rcons . (map (l [pair] ̀ (l ,pattern ,(2nd pair)))
list)))]]
,body))))

————————————————————————————————————————————

(define IF
(lambda reflect [[premise then else] env cont]
(normalise premise env
(l [premise!]
(normalise (ef ↑premise! then else) env cont)))))

(define COND
(lambda macro clauses
̀ (if ,(1st (1st clauses))
,(2nd (1st clauses))
(cond . ,(rest clauses)))))

(define BLOCK-HELPER
(l [clauses env cont]
(cond [(empty clauses) (cont)]
[(unit clauses) (normalise (1st clauses) env cont)]
[$T (normalise (1st clauses) env
(l ? (block-helper (rest clauses) env cont))])))

;;; SELECT and SELECTQ need to be re-thought. The current structural form is inelegant (you can’t select
;;; on a boolean), and the use of (ACONS), while it avoids intruding into the user’s name-space, is less
;;; than elegant.

(define SELECTQ
(labels [[SELECTQ-HELPER
(l [cases select-key]
(if (= (1st (1st cases)) ’$T)
(2nd (1st cases))
̀ (if (,(if (atom (1st (1st cases))) ’= ’member)
,select-key
,↑(1st (1st cases)))
,(2nd (1st cases))
,(select-helper (rest cases) select-key))))]]
(lambda macro [list body]
(let [[select-key (acons)]]
̀ (let [[,select-key ,(1st args)]]
,(select-helper (rest args) select-key))))))

————————————————————————————————————————————

(define ATOM (l [x] (= (type x) @atom)))
(define RAIL (l [x] (= (type x) @rail)))
(define PAIR (l [x] (= (type x) @pair)))
(define NUMERAL (l [x] (= (type x) @numeral)))
(define HANDLE (l [x] (= (type x) @handle)))
(define BOOLEAN (l [x] (= (type x) @boolean)))
(define CONSTANT (l [x] (= (type x) @constant)))

(define NUMBER (l [x] (= (type x) @number)))
(define SEQUENCE (l [x] (= (type x) @sequence)))
(define TRUTH-VALUE (l [x] (= (type x) @truth-value)))
(define FUNCTION (l [x] (= (type x) @function)))
(define REFLECTOR (l [x] (= (type x) @reflector)))

————————————————————————————————————————————

(define TYPE (l [e] (type e)))
(define = (l [e1 e2] (= e1 e2)))
(define EF (l [prem c1 c2] (ef prem c1 c2)))
(define UP (l [e] (up e)))
(define DOWN (l [s!] (down s!)))
(define REPLACE (l [s1 s2] (replace s1 s2)))

(define PCONS (l [s1 s2] (pcons s1 s2)))
(define CAR (l [pair] (car pair)))
(define CDR (l [pair] (cdr pair)))

(define RCONS (l structures (rcons . structures)))
(define SCONS (l entities (scons . entities)))
(define PREP (l [e vector] (prep e vector)))
(define LENGTH (l [vector] (length vector)))
(define NTH (l [n vector] (nth n vector)))
(define TAIL (l [n vector] (tail n vector)))
(define EMPTY (l [vector] (empty vector)))

(define + (l numbers (+ . numbers)))
(define - (l numbers (- . numbers)))
(define / (l numbers (/ . numbers)))
(define * (l numbers (* . numbers)))
(define < (l numbers (< . numbers)))
(define > (l numbers (> . numbers)))

Proper Names: 3-LISP, INTERLISP, FORTRAN, etc. (i.e., font 7 in regular text). Generally, use 1 pt size smaller than running text. (Fonts 1, 7, 0, 9, and 5 are, respectively, TimesRoman 8, 9, 10, 11, and 12). Also XEROX PARC.

Category Names: STRUCTURES, RAILS, SEQUENCES, etc. — bold italic gacha 10 (font 3) for meta-theoretical names of the domain categories.

Code: Gacha for now (font 3). Meta-theoretic variables in code are sometimes simply italic (i.e. (RCONS X Y)). Elipsis is font 0 (i.e. (+ A1 A2 ... Ak), not (+ A1 A2 ... Ak)).

Subscripts and Superscripts: Font 6 (gacha 8), with an up of 4 pts and a down of 2 pts for super and subscripts, respectively (default is 2; therefore superscripts have to be set explicitly). I.e., A1, A2, ... Ak, or F1(A).