Structure and Interpretation of Computer Programs

35

 Notice, however, that our compiler is a Scheme program, and the syntax procedures that it uses to

manipulate expressions are the actual Scheme procedures used with the metacircular evaluator. For the

explicit-control evaluator, in contrast, we assumed that equivalent syntax operations were available as

operations for the register machine. (Of course, when we simulated the register machine in Scheme,

we used the actual Scheme procedures in our register machine simulation.) 

36

 This procedure uses a feature of Lisp called backquote (or quasiquote) that is handy for

constructing lists. Preceding a list with a backquote symbol is much like quoting it, except that

anything in the list that is flagged with a comma is evaluated.

For example, if the value of 

linkage

 is the symbol 

branch25

, then the expression 

‘((goto

(label ,linkage)))

 evaluates to the list 

((goto (label branch25)))

. Similarly, if the

value of 

x

 is the list 

(a b c)

, then 

‘(1 2 ,(car x))

 evaluates to the list 

(1 2 a)

. 

37

 We can’t just use the labels 

true-branch

, 

false-branch

, and 

after-if

 as shown above,

because there might be more than one 

if

 in the program. The compiler uses the procedure 

make-label

 to generate labels. 

Make-label

 takes a symbol as argument and returns a new

symbol that begins with the given symbol. For example, successive calls to 

(make-label ’a)

would return 

a1

, 

a2

, and so on. 

Make-label

 can be implemented similarly to the generation of

unique variable names in the query language, as follows: 

(define label-counter 0)

(define (new-label-number)

  (set! label-counter (+ 1 label-counter))

  label-counter)

(define (make-label name)

  (string->symbol

    (string-append (symbol->string name)

                   (number->string (new-label-number)))))

38

 We need machine operations to implement a data structure for representing compiled procedures,

analogous to the structure for compound procedures described in section 4.1.3: 

(define (make-compiled-procedure entry env)

  (list ’compiled-procedure entry env))

(define (compiled-procedure? proc)

  (tagged-list? proc ’compiled-procedure))

(define (compiled-procedure-entry c-proc) (cadr c-proc))

(define (compiled-procedure-env c-proc) (caddr c-proc))

39

 Actually, we signal an error when the target is not 

val

 and the linkage is 

return

, since the only

place we request 

return

 linkages is in compiling procedures, and our convention is that procedures

return their values in 

val

. 

40

 Making a compiler generate tail-recursive code might seem like a straightforward idea. But most

compilers for common languages, including C and Pascal, do not do this, and therefore these

languages cannot represent iterative processes in terms of procedure call alone. The difficulty with tail

recursion in these languages is that their implementations use the stack to store procedure arguments

and local variables as well as return addresses. The Scheme implementations described in this book

store arguments and variables in memory to be garbage-collected. The reason for using the stack for

variables and arguments is that it avoids the need for garbage collection in languages that would not

otherwise require it, and is generally believed to be more efficient. Sophisticated Lisp compilers can,

---

in fact, use the stack for arguments without destroying tail recursion. (See Hanson 1990 for a

description.) There is also some debate about whether stack allocation is actually more efficient than

garbage collection in the first place, but the details seem to hinge on fine points of computer

architecture. (See Appel 1987 and Miller and Rozas 1994 for opposing views on this issue.) 

41

 The variable 

all-regs

 is bound to the list of names of all the registers: 

(define all-regs ’(env proc val argl continue))

42

 Note that 

preserving

 calls 

append

 with three arguments. Though the definition of 

append

shown in this book accepts only two arguments, Scheme standardly provides an 

append

 procedure

that takes an arbitrary number of arguments. 

43

 We have used the same symbol 

+

 here to denote both the source-language procedure and the

machine operation. In general there will not be a one-to-one correspondence between primitives of the

source language and primitives of the machine. 

44

 Making the primitives into reserved words is in general a bad idea, since a user cannot then rebind

these names to different procedures. Moreover, if we add reserved words to a compiler that is in use,

existing programs that define procedures with these names will stop working. See exercise 5.44 for

ideas on how to avoid this problem. 

45

 This is not true if we allow internal definitions, unless we scan them out. See exercise 5.43. 

46

 This is the modification to variable lookup required if we implement the scanning method to

eliminate internal definitions (exercise 5.43). We will need to eliminate these definitions in order for

lexical addressing to work. 

47

 Lexical addresses cannot be used to access variables in the global environment, because these

names can be defined and redefined interactively at any time. With internal definitions scanned out, as

in exercise 5.43, the only definitions the compiler sees are those at top level, which act on the global

environment. Compilation of a definition does not cause the defined name to be entered in the

compile-time environment. 

48

 Of course, compiled procedures as well as interpreted procedures are compound (nonprimitive).

For compatibility with the terminology used in the explicit-control evaluator, in this section we will

use ‘‘compound’’ to mean interpreted (as opposed to compiled). 

49

 Now that the evaluator machine starts with a 

branch

, we must always initialize the 

flag

 register

before starting the evaluator machine. To start the machine at its ordinary read-eval-print loop, we

could use 

(define (start-eceval)

  (set! the-global-environment (setup-environment))

  (set-register-contents! eceval ’flag false)

  (start eceval))

50

 Since a compiled procedure is an object that the system may try to print, we also modify the system

print operation 

user-print

 (from section 4.1.4) so that it will not attempt to print the components

of a compiled procedure: 

---