Page:AIM-379.djvu/12

From Wikisource
Jump to navigation Jump to search
This page needs to be proofread.
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.