Chapter 5

The following register-machine code is ambiguous, because the label here is defined more than once: start \(\quad(\) goto (label here)) here \(\quad\) (assign a (const 3)) \(\quad(\) goto (label there)) here \(\quad(\) assign a (const 4)) \(\quad(\) goto (label there)) there With the simulator as written, what will the contents of register a be when control reaches there? Modify the extract-labels procedure so that the assembler will signal an error if the same label name is used to indicate two different locations.

The simulator can be used to help determine the data paths required for implementing a machine with a given controller. Extend the assembler to store the following information in the machine model: \- a list of all instructions, with duplicates removed, sorted by instruction type (assign, goto, and so on); \- a list (without duplicates) of the registers used to hold entry points (these are the registers referenced by goto instructions); \- a list (without duplicates) of the registers that are saved or restored; \- for each register, a list (without duplicates) of the sources from which it is assigned (for example, the sources for register val in the factorial machine of figure \(5.11\) are (const 1) and ( (op *) (reg n) (reg val))). Extend the message-passing interface to the machine to provide access to this new information. To test your analyzer, define the Fibonacci machine from figure \(5.12\) and examine the lists you constructed. Exercise \(5.13\) Modify the simulator so that it uses the controller sequence to determine what registers the machine has rather than requiring a list of registers as an argument to make-machine. Instead of pre-allocating the registers in make- machine, you can allocate them one at a time when they are first seen during assembly of the instructions.

Alyssa P. Hacker wants a breakpoint feature in the simulator to help her debug her machine designs. You have been hired to install this feature for her. She wants to be able to specify a place in the controller sequence where the simulator will stop and allow her to examine the state of the machine. You are to implement a procedure (set-breakpoint ?machine \(\rangle\langle\) label \(\rangle\langle n\rangle\) ) that sets a breakpoint just before the \(n\)th instruction after the given label. For example, (set-breakpoint gcd-machine 'test-b 4) installs a breakpoint in gcd-machine just before the assignment to register a. When the simulator reaches the breakpoint it should print the label and the offset of the breakpoint and stop executing instructions. Alyssa can then use get-register-contents and set-register-contents! to manipulate the state of the simulated machine. She should then be able to continue execution by saying (proceed-machine \(\langle\) machine \(\rangle\) ) She should also be able to remove a specific breakpoint by means of (cancel-breakpoint ?machine \(\rangle\langle\) label \(\rangle\langle n\rangle\) ) or to remove all breakpoints by means of (cancel-all-breakpoints \(\langle\) machine \(\rangle\) )

Monitor the stack operations in the tree-recursive Fibonacci computation: (define (fib \(\mathrm{n}\) ) \((\) if \((<\mathrm{n} 2)\) \(\operatorname{n}(+(\mathrm{fib}(-\mathrm{n} 1))(\mathrm{fib}(-\mathrm{n} 2))))\) a. Give a formula in terms of \(n\) for the maximum depth of the stack required to compute \(\operatorname{Fib}(n)\) for \(n \geq 2\). Hint: In section \(1.2 .2\) we argued that the space used by this process grows linearly with \(n\). b. Give a formula for the total number of pushes used to compute \(\operatorname{Fib}(n)\) for \(n \geq 2\). You should find that the number of pushes (which correlates well with the time used) grows exponentially with \(n\). Hint: Let \(S(n)\) be the number of pushes used in computing \(\operatorname{Fib}(n)\). You should be able to argue that there is a formula that expresses \(S(n)\) in terms of \(S(n-1), S(n-2)\), and some fixed "overhead" constant \(k\) that is independent of \(n\). Give the formula, and say what \(k\) is. Then show that \(S(n)\) can be expressed as \(a \mathrm{Fib}(n+1)+b\) and give the values of \(a\) and \(b\).

Compile the iterative factorial procedure (define (factorial n) (define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter 1)))) (iter 1 1)) Annotate the resulting code, showing the essential difference between the code for iterative and recursive versions of factorial that makes one process build up stack space and the other run in constant stack space.

Our compiler is clever about avoiding unnecessary stack operations, but it is not clever at all when it comes to compiling calls to the primitive procedures of the language in terms of the primitive operations supplied by the machine. For example, consider how much code is compiled to compute \((+a 1):\) The code sets up an argument list in argl, puts the primitive addition procedure (which it finds by looking up the symbol + in the environment) into proc, and tests whether the procedure is primitive or compound. The compiler always generates code to perform the test, as well as code for primitive and compound branches (only one of which will be executed). We have not shown the part of the controller that implements primitives, but we presume that these instructions make use of primitive arithmetic operations in the machine's data paths. Consider how much less code would be generated if the compiler could open-code primitives-that is, if it could generate code to directly use these primitive machine operations. The expression (+ a 1) might be compiled into something as simple as \({ }^{43}\) (assign val (op lookup-variable-value) (const a) (reg env)) (assign val (op +) (reg val) (const 1)) In this exercise we will extend our compiler to support open coding of selected primitives. Special-purpose code will be generated for calls to these primitive ;; construct the procedure and skip over code for the procedure body (assign val (op make-compiled-procedure) (label entry2) (reg env)) (goto (label after-lambda1)) entry2 ;calls to factorial will enter here (assign env (op compiled-procedure-env) (reg proc)) (assign env (op extend-environment) (const (n)) (reg argl) (reg env)) begin actual procedure body (save continue) (save env) ;; compute (=n 1) (assign proc (op lookup-variable-value) (const =) (reg env)) (assign val (const 1)) (assign argl (op list) (reg val)) (assign val (op lookup-variable-value) (const n) (reg env)) (assign argl (op cons) (reg val) (reg argl)) (test (op primitive-procedure?) (reg proc)) (branch (label primitive-branch17)) compiled-branch16 (assign continue (label after-calli5)) (assign val (op compiled-procedure-entry) (reg proc)) (goto (reg val)) primitive-branch17 (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) after-callis ; val now contains result of \((=\mathrm{n} 1)\) (restore env) (restore continue) (test (op false?) (reg val)) (branch (label false-branch4)) true-branch5 ; return 1 (assign val (const 1)) (goto (reg continue)) false-branch4 ;; compute and return (* (factorial (- n 1)) n) (assign proc (op lookup-variable-value) (const *) (reg env)) (save continue) (save proc) ; save* procedure (assign val (op lookup-variable-value) (const n) (reg env)) (assign argl (op list) (reg val)) (save argl) ; save partial argument list for * ;; compute (factorial (- n 1)), which is the other argument for* (assign proc (op lookup-variable-value) (const factorial) (reg env)) (save proc) ; save factorial procedure