COMMENT ⊗   VALID 00007 PAGES 
RECORD PAGE   DESCRIPTION
 00001 00001
 00002 00002	.TURN ON "∪", "β" FOR "α"
 00003 00003	.P
 00007 00004	.P
 00010 00005	.P
 00011 00006	.P
 00013 00007	.P
 00015 ENDMK
⊗;
.TURN ON "∪", "β" FOR "α"
.MACRO B ⊂SKIP BEGIN NOFILL INDENT 20⊃
.MACRO BL ⊂BEGIN NOFILL⊃
.MACRO E ⊂ END ⊃
.MACRO P ⊂ NEXT PAGE ⊃
.EVERY HEADING({DATE},,LISP CALL-BY-EXPRESSION)
.EVERY FOOTING(,Page {PAGE})
.P
Three versions of "eval" are presented.  The first utilizes traditional
"call-by-value" arguments.  The second utilizes Algol-style call-by-name
arguments, herein called "call-by-expression".  The third utilizes
Vuillemin/Manna's "normal rule", in which arguments are passed by
expression but evaluated only the first time they are fetched.

The second and third versions utilize a different ALIST format than the
traditional.  When λx,y.foo[x,y] is applied to [e+1,∪aβp], the first
version's "pair" adds to the ALIST `a' the following two pairs:
.B
X . eval((PLUS E 1), a)
Y . eval((CAR P), a)
.E
That is, it evaluates the arguments with respect to the ALIST `a' and records
the results of evaluation on the ALIST.  However, the new "pair" adds to
the ALIST `a' the following two triples:
.B
X . a . (PLUS E 1)
Y . a . (CAR P)
.E
That is, it does not evaluate the arguments, but instead records the ALIST with
respect to which they ought to be evaluated.

The difference beteen the second and third versions is that the third uses
∪rplacd to substitute the value of a bound expression for the expression when
it is first fetched.

Functional arguments and functional results
are handled by all three versions.  A λ-expression bound when the ALIST `a'
was extant is automatically expanded to:
.B
(FUNARG (LAMBDA (...) ...) a)
.E
In the first version of "eval",
"pair" expands the λ-expression at binding time
while in the new versions expansion is deferred until it is fetched.

Note that "pair" has four arguments.  The last two are both ALISTs.  The
first ALIST is the one with which arguments are evaluated; the second ALIST
is the one on which the bindings are recorded.

To simplify the presentation, "eval", "evcon", and  "pair"
are identical for all three
versions; the differences are isolated to the auxiliary functions "fetch" and
"pair1".
.P
.BL
eval[e, a] ←
∪if ∪at e ∪then
    [	∪if e = T ∪then T
	∪else ∪if e = NIL ∪then NIL
	∪else ∪if ∪numberp e ∪then e
	∪else {assoc[e, a]}
	      [λw. ∪if ∪n w ∪then error[] ∪else fetch[w]]
    ]
∪else ∪if ∪at ∪aβe ∪then
    [	∪if ∪aβe = CAR ∪then ∪a eval[∪adβe, a]
	∪else ∪if ∪aβe = CDR ∪then ∪d eval[∪adβe, a]
	∪else ∪if ∪aβe = CONS ∪then eval[∪adβe, a] . eval[∪addβe, a]
	∪else ∪if ∪aβe = EQ ∪then eval[∪adβe, a] = eval[∪addβe, a]
	∪else ∪if ∪aβe = ATOM ∪then ∪at eval[∪adβe, a]
	∪else ∪if ∪aβe = NULL ∪then ∪n eval[∪adβe, a]
	∪else ∪if ∪aβe = QUOTE ∪then ∪ad e
	∪else ∪if ∪aβe = COND ∪then evcon[∪dβe, a]
	∪else ∪if ∪aβe = LAMBDA ∪then list[FUNARG, e, a]
	∪else ∪if ∪aβe = LABEL ∪then
	    [	∪if ∪addβe = FUNARG ∪then e
		∪else list[LABEL, ∪adβe, list[FUNARG, ∪addβe, a]]   ]
	∪else ∪if ∪aβe = FUNARG ∪then e
	∪else {assoc[∪aβe, a]}
	      [λw. ∪if ∪nβw ∪then
		{ass1[EXPR, ∪ae]}
		[λz. ∪if ∪nβz ∪then error[] ∪else eval[∪dβz.∪dβe, a]]
	       ∪else eval[fetch[w].∪dβe, a]
	      ]
    ]
∪else ∪if ∪aaβe = LAMBDA ∪then eval[∪addaβe, pair[∪adaβe, ∪dβe, a, a]]
∪else ∪if ∪aaβe = LABEL ∪then
		eval[∪adaβe.∪dβe, pair[∪adaβe.NIL, ∪addaβe.NIL, a, a]]
∪else ∪if ∪aaβe = FUNARG ∪then
			eval[∪addadaβe, pair[∪adadaβe, ∪dβe, a, ∪addaβe]]
∪else eval[eval[∪aβe, a].∪de, a]


evcon[u, a] ←
∪if ∪nu ∪then error[]
∪else ∪if eval[∪aaβu, a] ∪then eval[∪adaβu, a]
∪else evcon[∪dβu, a]


pair[u, v, w, x] ←
∪if ∪nβu ∪then
    [	∪if ∪nβv ∪then x ∪else error[]	]
∪else ∪if ∪nβv ∪then error[]
∪else [∪aβu . pair1[∪aβv, w]] . pair[∪dβu, ∪dβv, w, x]
.E
.P
CALL-BY-VALUE RULE:
.SKIP 2
.BL
pair1[e, a] ← eval[e, a]


fetch[w] ← ∪ad w
.E
.SKIP 5
CALL-BY-EXPRESSION RULE:
.SKIP 2
.BL
pair1[e, a] ← a . e


fetch[w] ← eval[∪ddβw, ∪adβw]
.E
.SKIP 5
NORMAL RULE:
.SKIP 2
.BL
pair1[e, a] ← a . e


fetch[w] ← {eval[∪ddβw, ∪adβw]}
	   [λe. prog2[ ∪rplacd[∪dβw,list[QUOTE, e]], e ]]
.E
.P
Call-by-value is the most efficient rule to use in compiled code,
and is adequate for most purposes; in fact, with the addition of
SETQ, call-by-value is often necessary to force earliest evaluation
of an argument.  It is recommended that, as in Algol-60, the rule
to be used for evaluating each argument be declared individually.
.skip BL
function f(value x, y) =
	if x = 0 then 0 else f(x-1, f(x,y-1))

function f(expression x, y) =
	if x=0 then 0 else f(x-1, f(x, y-1))

function f(normal x, y) =
	if x=0 then 0 else f(x-1, f(x,y-1))

function f(value x; normal y) =
	if x=0 then 0 else f(x-1, f(x, y-1))
.E
The first version of the "minimal fixed point" function does not
terminate for x≠0.  The rest do terminate, but the second version
involves redundant evaluations.  The third and fourth versions avoid
the redundant evaluations, but the fourth is faster than the third
because x is evaluated at binding time instead of at its first fetch.
.P
The syntax of m-expressions employed in the definition of "eval" is as
follows.  These are the actual LISP70 declarations which would generate
a fast translator from m-expressions to S-expressions.
.SKIP 2 BL
<mexpr> 	= ∪if <mexpr>:a ∪then <mexpr>:b ∪else <mexpr>:c
			→→ (COND (:a :b) (T :c))
		= <mterm>:a  !=  <mterm>:b  →→  (EQ :a :b)
		= <mterm>:a  !.  <mterm>:b  →→  (CONS :a :b)
		= !λ  <idlist>:v  !.  <mexpr>:m  →→  (LAMBDA :v :m)
		= <mterm>

<mterm>		= ∪a <mterm>:m  →→  (CAR :m)
		= ∪d <mterm>:m  →→  (CDR :m)
		= ∪n <mterm>:m  →→  (NULL :m)
		= ∪at <mterm>:m  →→  (ATOM :m)
		= ∪numberp <mterm>:m  →→  (NUMBERP :m)
		= !{  <arglist>:a  !}  <mprimary>:p  →→  (:p  ::a)
		= <mprimary>

<mprimary>	= <identifier>
		= <number>
		= <sexpression>:s →→ (QUOTE :s)
		= ![  <mexpr>:m  !]  →→  :m
		= <mprimary>:p  ![  <arglist>:a  !]  →→  (:p ::a)

<arglist>	= ⊂REP !,  <mexpr>:m⊃  →→  :m

<idlist>	= ⊂REP !,  <identifier>:v⊃  →→  :v

<definition>	= <identifier>:p  ![  <idlist>:v  !]  !←  <mexpr>:m
			→→ (DEFPROP :p (LAMBDA :v :m))
.E