Use the simulator to test the machines you designed in Exercise 5.4.
The following register-machine code
is ambiguous, because the label here is defined more than once:
start
(goto (label here))
here
(assign a (const 3))
(goto (label there))
here
(assign a (const 4))
(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 treatment of machine operations above permits them to operate on labels as well as on constants and the contents of registers. Modify the expression-processing procedures to enforce the condition that operations can be used only with registers and constants.
Design a new syntax for register-machine instructions and modify the simulator to use your new syntax. Can you implement your new syntax without changing any part of the simulator except the syntax procedures in this section?
When we introduced save
and restore in 5.1.4, we didn't specify what would happen
if you tried to restore a register that was not the last one saved, as in the
sequence
(save y)
(save x)
(restore y)
There are several reasonable possibilities for the meaning of restore:
1. (restore y) puts into y the last value saved on the stack,
regardless of what register that value came from. This is the way our
simulator behaves. Show how to take advantage of this behavior to eliminate
one instruction from the Fibonacci machine of 5.1.4 (Figure 5.12).
2. (restore y) puts into y the last value saved on the stack, but
only if that value was saved from y; otherwise, it signals an error.
Modify the simulator to behave this way. You will have to change save
to put the register name on the stack along with the value.
3. (restore y) puts into y the last value saved from y
regardless of what other registers were saved after y and not restored.
Modify the simulator to behave this way. You will have to associate a separate
stack with each register. You should make the initialize-stack
operation initialize all the register stacks.
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:
@itemize
@item
a list of all instructions, with duplicates removed, sorted by instruction type
(assign, goto, and so on);
@item
a list (without duplicates) of the registers used to hold entry points (these
are the registers referenced by goto instructions);
@item
a list (without duplicates) of the registers that are saved
or restored;
@item
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.
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.
Measure the number of pushes and
the maximum stack depth required to compute ${n!$} for various small values of
$n$ using the factorial machine shown in Figure 5.11. From your data
determine formulas in terms of $n$ for the total number of push operations
and the maximum stack depth used in computing ${n!$} for any ${n \gt 1$}. Note
that each of these is a linear function of $n$ and is thus determined by two
constants. In order to get the statistics printed, you will have to augment
the factorial machine with instructions to initialize the stack and print the
statistics. You may want to also modify the machine so that it repeatedly
reads a value for $n$, computes the factorial, and prints the result (as we
did for the @abbr{GCD} machine in Figure 5.4), so that you will not
have to repeatedly invoke get-register-contents,
set-register-contents!, and start.
Add instruction counting to the register machine simulation. That is, have the machine model keep track of the number of instructions executed. Extend the machine model's interface to accept a new message that prints the value of the instruction count and resets the count to zero.
Augment the simulator to provide
for instruction tracing. That is, before each instruction is
executed, the simulator should print the text of the instruction. Make the
machine model accept trace-on and trace-off messages to turn
tracing on and off.
Extend the instruction tracing of Exercise 5.16 so that before printing an instruction, the simulator prints any labels that immediately precede that instruction in the controller sequence. Be careful to do this in a way that does not interfere with instruction counting (Exercise 5.15). You will have to make the simulator retain the necessary label information.
Modify the make-register
procedure of 5.2.1 so that registers can be traced. Registers
should accept messages that turn tracing on and off. When a register is
traced, assigning a value to the register should print the name of the
register, the old contents of the register, and the new contents being
assigned. Extend the interface to the machine model to permit you to turn
tracing on and off for designated machine registers.
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 ⟨@var{machine}⟩ ⟨@var{label}⟩ ⟨@var{n}⟩)
that sets a breakpoint just before the $n^{\text{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 ⟨@var{machine}⟩)
She should also be able to remove a specific breakpoint by means of
(cancel-breakpoint ⟨@var{machine}⟩ ⟨@var{label}⟩ ⟨@var{n}⟩)
or to remove all breakpoints by means of
(cancel-all-breakpoints ⟨@var{machine}⟩)