SICP - Compilation

Shorter lecture on the way a compiler for LISP might function.


Note Dump:

Compilation

Lol apparently it is hawaiian shirt day... must be Friday.

The explicit control evaluator bridges the gap between a high level language like LISP and a low level register machine.

A LISP interpretter is built on a register machine interpreter.  We write an interpreter to raise the machine to the level of the language that we want to write.

With compilation, we feed the source code into a compiler that translates the LISP program into register language. The linker/loader connects the register language to a library.  Basically brings the high level program down to the level of the machine.

An interpreter is a general purpose simulator, whereas the compiler produces the specific machine to run the program we fed it, so compiled code can be faster.

Interpreting is easier for debugging.

Interpreted code and compiled code can call each other.

For a zeroith (0th) level compiler, we walk over the code, and instead of executing the procedures we save them away...

Register Operations in interperting (F X)
(assign unev (operands (fetch exp)))
(assign exp (operator (fetch exp)))
(save...)
(restore...)
etc... total of 19 register operations.

When you reach a branch, compile both branches.
(IF P A B)
<CODE FOR P - RESULT IN VAL>
BRANCH IF VAL IS TRUE TO LABEL1
<CODE FOR B>
GOTO NEXT THING
LABEL1 <CODE FOR A>
GOTO NEXT THING

This compiler just stashes away the register operations instead of running them, other than that it is just like the evaluator.

This compiler isn't very smart...
We can get rid of some general purpose stuff.  EXP and UNEV are not necessary because in compiled code these things are constants anyway.
We can also handle program flow much better. A lot of what goes into CONTINUE has to do with evaluator analysis, which the compiler doesn't care about.

Optimized compiled code reduces 19 register operations down to these:

(save env)
(assign val (lookup-var-val 'f (fetch env)))
(restore env)
(assign fun (fetch val))
(save fun)
(assign argl '())
(save argl)
(assign val (lookup-var-val 'x (fetch env)))
(restore argl)
(assign argl (cons (fetch val) (fetch argl)))
(restore fun)

This compiler is better but its still pretty dumb.
The save and restore procedures are done because the interpreter is recursive.  In this case we know the assignment has no effect so there is no reason to do this save/restore.

The evaluator has to be pessimistic, meaning it needs to save everything. The compiler knows what it needs to save.

Eliminating unnecessary stack operations results in this (down from 19):
(assign fun (lookup-var-val 'f (fetch env)))
(assign val (lookup-var-val 'x (fetch env)))
(assign argl (cons (fetch val) '()))

computation procedes to apply-dispatch

(OP A1 A2)
{COMPILE OP; RESULT IN FUN} <- this part must preserve ENV
{COMPILE A1; RESULT IN VAL} <- it will need the environment, must preserve ENV \
(ASSIGN ARGL (CONS (FETCH VAL) '()))                                            \__ this must
{COMPILE A2; RESULT IN VAL} <- this must preserve ARGL                          /   preserve FUN
(ASSIGN ARGL (CONS (FETCH VAL) (FETCH ARGL)))                                  /
(GOTO APPLY-DISPATCH)

Compiler starts making little code sequenses and appending them together. These appends must preserve the necessary registers.

APPEND SEQ1 AND SEQ2 PRESERVING REG
IF SEQ2 NEEDS REG AND SEQ1 MODIFIES REG
(SAVE REG)
<SEQ1>
(RESTORE REG)
<SEQ2>
OTHERWISE
<SEQ1>
<SEQ2>

A sequence of instructions includes information regarding what registers are modified and what registers are needed.
<sequence of instruction; set of registers modified; set of registers needed>
<(ASSIGN R1 (FETCH R2)); {R1}; {R2}> <-- we need R2, we modify R1

<S1; M1; N1> AND <S2; M2; N2>
results in
<S1, S2; M1 UNION M2; N1 UNION [N2 - M1]>

A compiler can be smarter about saving argument lists and using

Talk about the implementation of primatives in Scheme.

Breaktime... almost done.