| Guy L. Steele Jr. | 10 | LAMBDA: The Ultimate Declarative |
FACT: <set up arguments for FACT1>
GOTO FACT1 ;call FACT1
FACT1: <if quantity names M is non-zero go to FACT1A>
<return quantity named A in register RESULT>
POPJ
FACT1A: <do subtraction and multiplication>
GOTO FACT1 ;FACT1 calling itself
Filling in the arithmetic operations and register assignments gives:
- On arrival here, quantity named N is in register ARG.
FACT: MOVEI RESULT,1 ;N already in ARG; set up 1
GOTO FACT1 ;call FACT1
- On arrival here, quantity named M is in ARG,
- and quantity named A is in RESULT.
FACT1: JUMPN ARG,FACT1A
POPJ ;A is already in RESULT!
FACT1A: MOVE R1,ARG ;must do subtraction in R1
SUBI R1,1
IMUL RESULT,ARG ;do multiplication
MOVE ARG,R1 ;now put result of subtraction in ARG
GOTO FACT1 ;FACT1 calling itself
This code, while not perfect, is not bad.
The major deficiency, which is the use of R1, is easily cured if the compiler could know at some level that the subtraction and multiplication can be interchanged (for neither has side effects which would affect the other), producing:
FACT1A: IMUL RESULT,ARG
SUBI ARG,1
GOTO FACT1
Similarly, the sequence:
FACT1:
GOTO FACT1
could be optimized by removing the GOTO.
These tricks, however, are know by any current reasonably sophisticated optimizing compiler.
What is more important is the philosophy taken in interpreting the meaning of the program during the compilation process.
The structure of this compiled code is a loop, not a nested sequence of stack-pushing function calls.
Like the SCHEME interpreter or the various PLASMA implementations, a compiler based on these ideas would correctly reflect the semantics of lambda-calculus-based models of high-level constructs.
