Lambda implementation.


In mathematics lambda means a function that is not given a name. In Forth and other computer languages they are sometimes called quotations. Quotation refers to the body of a function that calls other functions that are given a name, and hence can be called by an interpreter.
Let's assume our Forth has the following mechanism available:
({) (}) brackets a piece of code and leaves an execution token, not dea. 1] Can be used outside a definition instead of :NONAME As lightweight as possible. Inside: compilation mode.
(( )) make sure dictionary space can be used between them by compiling an AHEAD, or equivalent.
([) (]) New context for definitions, maybe in the middle of a word. - tucks away onto the return stack, any data that could be spoiled by compiling something, then recovers it again In particular w.r.t. current wordlist, remove the information what word is being compiled, then restore it again. Inside: interpretation mode.
(s s) save and restore STATE.
This will allow us to add lambda's to a system, which in Forth terms are execution tokens, that can be passed to EXECUTE .
The word ,, ("multicomma") is long overdue : : ,, HERE SWAP DUP ALLOT MOVE ; We'll use it here.
First example: Let's have a smart C" , i.e. one that works in both interpret and compilation mode, then we'll unsmart it.
Remember C" AAP" leaves the address where "AAP" is stored as a brain-damaged string, one that cannot have more than 255 char's. COUNT will turn that into a regular forth constant string. (adr len), We need (( because space is allocated, but not (s because state is not changed: 
: C"
    STATE @ IF (( THEN
    &" PARSE  HERE DUP C, ,,
    STATE @ IF )) THEN
    STATE @ IF POSTPONE LITERAL THEN
; IMMEDIATE

It doesn't harm to compile a jump over the string in interpret state, and LITERAL is state smart anyway so we get. 
: C" ((  &" PARSE HERE DUP , ,, )) POSTPONE LITERAL ; IMMEDIATE
Note that any reference to state has disappeared, except for LITERAL which is generally accepted practice for a literal. 1]
Similarly we can have a lambda, that works in interpret state and compilation state:
Lambda has its own way with STATE so we must use (s s). We need (( too because space is allocated. Furthermore it leaves an execution token that is a literal. And of course it must compile a sequence that can be executed as code. The result is as follows. 
: {
     (s
        STATE @ IF (( THEN
            ({)
; IMMEDIATE

: }
            )})
        STATE @ IF )) THEN
    s)
    STATE @ IF POSTPONE LITERAL THEN
; IMMEDIATE
Cutting the same corners this becomes 
: {   (s (( ({)   ;    IMMEDIATE
: }   (}) )) s)   POSTPONE LITERAL ;    IMMEDIATE
A separate compilation stack would be ideal, otherwise care must be taken that the light weight xt left by (}) remains intact through )). Where { } leaves a constant, that can be used as a literal inside or outside of a definition, it is usefull outside of a definition. On the other hand [ ] is only useful inside a definition, but it can be used in interpret state too. This may be useful if ;) (: implements the hiding of local names of some sort.
Implementation examples (for ciforth) 
\ 'TASK @ CONSTANT docol
: ({)   HERE docol , HERE CELL+ , 1 STATE ! ;
: (})   '(;) , ;      \ (;) is an alias for EXIT
For (s we need :I inlining, (Other forths can use [[ ]] if available.) 
:I (s STATE @ >R ;
:I s) R> STATE ! ;

:I ((  AHEAD >R ;
:I ))  R> THEN ;
Conflating everything and saving state inside ({) which avoids inlining or the use of the return stack, we get 
: {  POSTPONE AHEAD HERE docol , HERE CELL+ ,    STATE @ 1 STATE ! ;
IMMEDIATE
: }  STATE ! '(;) , POSTPONE THEN POSTPONE LITERAL ; IMMEDIATE
The consequences of having a neat { } are important. A demonstration is given in the lesson "decent looping".

Nested compilation.

Nested usage of the dictionary mechanism did not enter the picture at this stage. Up till now we didn't use [ ] , and for a good reason. If these words are to be generally useful as bracketing mechanism they must save and restore rather then setting state to a fixed value. The build up of the current definition is interrupted which need handling too.
The four brackets now allows us more powerful [ ] mechanism than is standard. By using ;) (: we create a new context for definitions, maybe in the middle of a word. Instead of the local values that are customary, we can add any type of word to the dictionary such as local tables, variables and colon definitions. We need words to isolate the latest word from the dictionary and leave its DEA, then to link that DEA again into the dictionary, as the latest. These words are as system-dependant as anything shown here. An implementation in ciforth follows. 
: UNLINK-LATEST LATEST CURRENT @ >LFA DUP @ >LFA @ SWAP ! ;
: LINK-LATEST LATEST OVER >LFA ! CURRENT @ >LFA ! ;
: ;) CSP @   UNLINK-LATEST   0 STATE ! ;
: (: LINK-LATEST CSP ! ;
Now alternative square brackets can be defined. Contrary to the classical brackets they do not allow to generate a stack item, then pass it to the definition being compiled to be consumed by LITERAL. 3] 
: [  (( (s ;) ;   IMMEDIATE
: ]  (: s) )) ;   IMMEDIATE

Conclusion

So we have proven the following lemma:
Adding 4 simple bracketing mechanism allows us to have all sorts of nesting imaginable. In particular using 3 of them we can have a lambda syntax that is a true literal, i.e. it is the same for interpret and compilation state and not more state-smart then a number is.

Notes


1] Sometimes called name token, to indicate that more data is available from this token than just an execution token. An objectionable name because it suggest that the only extra data is the name which is plain wrong. Think e.g. of an immediacy flag or information to find out to which wordlist the word belongs.
2] I've explained that in a system with a separate compilation stack INTERPRET can inspect whether a word leaves a literal. Then interpret can do 
   ' LIT COMPILE,  COMPILE,
as needed in compilation mode.
3] This is not really a limitation. Replace 
[ 122 B/BUF * ] LITERAL
by 
[ 122 B/BUF * CONSTANT BUFSIZE ] BUFSIZE

  • Other Forth lectures
    • Go to the home page of Albert van der Horst