5.8 Exercise 5.8

Consider the following program with an ambiguous label:

start

(goto (label here))

here

(assign a (const 3))

(goto (label there))

here

(assign a (const 4))

(goto (label there))

there

We can see in extract-labels that new labels are prepended to the list of existing labels. However, the instructions are iterated through in reverse order – the fact that extract-labels calls (extract-labels (cdr text) ...) is a tell-tale clue of this. This means that the first declaration of the here label will be first in the list. Since lookup-label uses assoc, it will therefore return the first instance of the here label in code.

We can verify this by simulation:

(define broken-machine

(make-machine

'(a)

'()

'(start

(goto (label here))

here

(assign a (const 3))

(goto (label there))

here

(assign a (const 4))

(goto (label there))

there)))

We can fix this by forcing extract-labels to verify that a label with a given name doesn’t already exist in the list of labels. It’s not very efficient, but assoc will do the job here with minimal changes:

(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)

(if (assoc next-inst labels)

(error "Duplicate label -- ASSEMBLE" next-inst)

(receive insts

(cons (make-label-entry next-inst insts)

labels)))

(receive (cons (make-instruction next-inst)

insts)

labels)))))))