5.2.2 The Assembler - SICP Comparison Edition

Permalink copied!

The assembler transforms the sequence of controller expressions instructions for a machine into a corresponding list of machine instructions, each with its execution procedure. function. Overall, the assembler is much like the evaluators we studied in chapter 4—there is an input language (in this case, the register-machine language) and we must perform an appropriate action for each type of component in the language.

The technique of producing an execution procedure function for each instruction is just what we used in section 4.1.7 to speed up the evaluator by separating analysis from runtime execution. As we saw in chapter 4, much useful analysis of Scheme JavaScript expressions could be performed without knowing the actual values of variables. names. Here, analogously, much useful analysis of register-machine-language expressions can be performed without knowing the actual contents of machine registers. For example, we can replace references to registers by pointers to the register objects, and we can replace references to labels by pointers to the place in the instruction sequence that the label designates.

Before it can generate the instruction execution procedures, functions, the assembler must know what all the labels refer to, so it begins by scanning the controller textsequence to separate the labels from the instructions. As it scans the textcontroller, it constructs both a list of instructions and a table that associates each label with a pointer into that list. Then the assembler augments the instruction list by inserting the execution procedure function for each instruction.

The assemble procedure function is the main entry to the assembler. It takes the controller textsequence and the machine model as arguments and returns the instruction sequence to be stored in the model. Assemble The function assemble calls extract-labels extract_labels to build the initial instruction list and label table from the supplied controller text. The second argument to extract-labels extract_labels is a procedure function to be called to process these results: This procedure function uses update-insts! update_insts to generate the instruction execution procedures functions and insert them into the instruction list, and returns the modified list.

Original	JavaScript
`(define (assemble controller-text machine) (extract-labels controller-text (lambda (insts labels) (update-insts! insts labels machine) insts)))`	`function assemble(controller, machine) { return extract_labels(controller, (insts, labels) => { update_insts(insts, labels, machine); return insts; }); }`

Original		JavaScript
`Extract-labels` takes as arguments a list `text` (the sequence of controller instruction expressions) and a `receive` procedure. `Receive` will be called with two values: (1) a list `insts` of instruction data structures, each containing an instruction from `text`; and (2) a table called `labels`, which associates each label from `text` with the position in the list `insts` that the label designates.		The function `extract_labels` takes a list `controller` and a function `receive` as arguments. The function `receive` will be called with two values: (1) a list `insts` of instruction data structures, each containing an instruction from `controller`; and (2) a table called `labels`, which associates each label from `controller` with the position in the list `insts` that the label designates.

Original	JavaScript
`(define (extract-labels text receive) (if (null? text) (receive '() '()) (extract-labels (cdr text) (lambda (insts labels) (let ((next-inst (car text))) (if (symbol? next-inst) (receive insts (cons (make-label-entry next-inst insts) labels)) (receive (cons (make-instruction next-inst) insts) labels)))))))`	`function extract_labels(controller, receive) { return is_null(controller) ? receive(null, null) : extract_labels( tail(controller), (insts, labels) => { const next_element = head(controller); return is_string(next_element) ? receive(insts, pair(make_label_entry(next_element, insts), labels)) : receive(pair(make_inst(next_element), insts), labels); }); }`

Extract-labels The function extract_labels works by sequentially scanning the elements of the textcontroller and accumulating the insts and the labels. If an element is a symbol string (and thus a label) an appropriate entry is added to the labels table. Otherwise the element is accumulated onto the insts list.[1]

Update-insts! The function update_insts modifies the instruction list, which initially contains only the text of the instructions, the controller instructions, to include the corresponding execution procedures: functions:

Original	JavaScript
`(define (update-insts! insts labels machine) (let ((pc (get-register machine 'pc)) (flag (get-register machine 'flag)) (stack (machine 'stack)) (ops (machine 'operations))) (for-each (lambda (inst) (set-instruction-execution-proc! inst (make-execution-procedure (instruction-text inst) labels machine pc flag stack ops))) insts)))`	`function update_insts(insts, labels, machine) { const pc = get_register(machine, "pc"); const flag = get_register(machine, "flag"); const stack = machine("stack"); const ops = machine("operations"); return for_each(inst => set_inst_execution_fun( inst, make_execution_function( inst_controller_instruction(inst), labels, machine, pc, flag, stack, ops)), insts); }`

The machine instruction data structure simply pairs the controller instruction text with the corresponding execution procedure. function. The execution procedure function is not yet available when extract-labels extract_labels constructs the instruction, and is inserted later by update-insts!. update_insts.

Original	JavaScript
`(define (make-instruction text) (cons text '())) (define (instruction-text inst) (car inst)) (define (instruction-execution-proc inst) (cdr inst)) (define (set-instruction-execution-proc! inst proc) (set-cdr! inst proc))`	`function make_inst(inst_controller_instruction) { return pair(inst_controller_instruction, null); } function inst_controller_instruction(inst) { return head(inst); } function inst_execution_fun(inst) { return tail(inst); } function set_inst_execution_fun(inst, fun) { set_tail(inst, fun); }`

The instruction text controller instruction is not used by our simulator, but is handy to keep around for debugging (see exercise 5.16).

Elements of the label table are pairs:

Original	JavaScript
`(define (make-label-entry label-name insts) (cons label-name insts))`	`function make_label_entry(label_name, insts) { return pair(label_name, insts); }`

Entries will be looked up in the table with

Original	JavaScript
`(define (lookup-label labels label-name) (let ((val (assoc label-name labels))) (if val (cdr val) (error "Undefined label - - ASSEMBLE" label-name))))`	`function lookup_label(labels, label_name) { const val = assoc(label_name, labels); return is_undefined(val) ? error(label_name, "undefined label -- assemble") : tail(val); }`

Exercise 5.8 The following register-machine code is ambiguous, because the label here is defined more than once:

Original	JavaScript
`start (goto (label here)) here (assign a (const 3)) (goto (label there)) here (assign a (const 4)) (goto (label there)) there`	`"start", go_to(label("here")), "here", assign("a", constant(3)), go_to(label("there")), "here", assign("a", constant(4)), go_to(label("there")), "there",`

With the simulator as written, what will the contents of register a be when control reaches there? Modify the extract-labels extract_labels procedure function so that the assembler will signal an error if the same label name is used to indicate two different locations.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

[1] Using the receive procedure function here is a way to get extract-labels extract_labels to effectively return two values—labels and insts—without explicitly making a compound data structure to hold them. An alternative implementation, which returns an explicit pair of values, is

Original

JavaScript

(define (extract-labels text) (if (null? text) (cons '() '()) (let ((result (extract-labels (cdr text)))) (let ((insts (car result)) (labels (cdr result))) (let ((next-inst (car text))) (if (symbol? next-inst) (cons insts (cons (make-label-entry next-inst insts) labels)) (cons (cons (make-instruction next-inst) insts) labels)))))))

function extract_labels(controller) { if (is_null(controller)) { return pair(null, null); } else { const result = extract_labels(tail(controller)); const insts = head(result); const labels = tail(result); const next_element = head(controller); return is_string(next_element) ? pair(insts, pair(make_label_entry(next_element, insts), labels)) : pair(pair(make_inst(next_element), insts), labels); } }

which would be called by assemble as follows:

Original	JavaScript
`(define (assemble controller-text machine) (let ((result (extract-labels controller-text))) (let ((insts (car result)) (labels (cdr result))) (update-insts! insts labels machine) insts)))`	`function assemble(controller, machine) { const result = extract_labels(controller); const insts = head(result); const labels = tail(result); update_insts(insts, labels, machine); return insts; }`

You can consider our use of receive as demonstrating an elegant way to return multiple values, or simply an excuse to show off a programming trick. An argument like receive that is the next procedure function to be invoked is called a continuation. Recall that we also used continuations to implement the backtracking control structure in the amb evaluator in section 4.3.3.

< Previous

Next >

5.2.2 The Assembler