Para obter uma boa compreensão do projeto de máquinas de registradores, devemos testar as máquinas que projetamos para ver se elas funcionam conforme o esperado. Uma maneira de testar um projeto é simular manualmente a operação do controlador, como em Exercício 5.5. No entanto, isso é extremamente tedioso para todas, exceto as máquinas mais simples. Nesta seção, construiremos um simulador para máquinas descritas na linguagem de máquina de registradores. O simulador é um programa em Scheme com quatro procedimentos de interface. O primeiro usa uma descrição de uma máquina de registradores para construir um modelo da máquina (uma estrutura de dados cujas partes correspondem às partes da máquina a ser simulada), e os outros três nos permitem simular a máquina manipulando o modelo:
(make-machine ⟨register-names⟩ ⟨operations⟩ ⟨controller⟩)constrói e retorna um modelo da máquina com os registradores, operações e controlador fornecidos.
(set-register-contents! ⟨machine-model⟩ ⟨register-name⟩ ⟨value⟩)armazena um valor em um registrador simulado na máquina fornecida.
(get-register-contents ⟨machine-model⟩ ⟨register-name⟩)retorna o conteúdo de um registrador simulado na máquina fornecida.
(start ⟨machine-model⟩)simula a execução da máquina fornecida, começando do início da sequência do controlador e parando quando chega ao final da sequência.
Como exemplo de como esses procedimentos são usados, podemos definir
gcd-machine como um modelo da máquina GCD de
5.1.1 da seguinte forma:
(define gcd-machine
(make-machine
'(a b t)
(list (list 'rem remainder) (list '= =))
'(test-b
(test (op =) (reg b) (const 0))
(branch (label gcd-done))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label test-b))
gcd-done)))
O primeiro argumento para make-machine é uma lista de nomes
de registradores. O próximo argumento é uma tabela (uma lista de listas
de dois elementos) que associa cada nome de operação a um procedimento
Scheme que implementa a operação (ou seja, produz o mesmo valor de saída
dados os mesmos valores de entrada). O último argumento especifica o
controlador como uma lista de rótulos e instruções da máquina, como em
5.1.
Para calcular MDCs com esta máquina, definimos os registradores de entrada, iniciamos a máquina e examinamos o resultado quando a simulação termina:
(set-register-contents! gcd-machine 'a 206)
done
(set-register-contents! gcd-machine 'b 40)
done
(start gcd-machine)
done
(get-register-contents gcd-machine 'a)
2
Este cálculo será executado muito mais lentamente do que um procedimento
gcd escrito em Scheme, porque simularemos instruções de
máquina de baixo nível, como assign, por operações muito
mais complexas.
Exercício 5.7: Use o simulador para testar as máquinas que você projetou no Exercício 5.4.
O modelo de máquina gerado por make-machine é representado
como um procedimento com estado local usando as técnicas de passagem de
mensagens desenvolvidas no
Capítulo 3. Para construir este
modelo, make-machine começa chamando o procedimento
make-new-machine para construir as partes do modelo de
máquina que são comuns a todas as máquinas de registradores. Este modelo
básico de máquina construído por make-new-machine é
essencialmente um contêiner para alguns registradores e uma pilha, junto
com um mecanismo de execução que processa as instruções do controlador
uma por uma.
Make-machine então estende este modelo básico (enviando
mensagens) para incluir os registradores, operações e controlador da
máquina específica que está sendo definida. Primeiro, ele aloca um
registrador na nova máquina para cada um dos nomes de registradores
fornecidos e instala as operações designadas na máquina. Em seguida, ele
usa um montador (descrito abaixo em
5.2.2) para transformar a lista do
controlador em instruções para a nova máquina e instala essas instruções
como a sequência de instruções da máquina.
Make-machine retorna como seu valor o modelo de máquina
modificado.
(define (make-machine register-names
ops
controller-text)
(let ((machine (make-new-machine)))
(for-each (lambda (register-name)
((machine 'allocate-register)
register-name))
register-names)
((machine 'install-operations) ops)
((machine 'install-instruction-sequence)
(assemble controller-text machine))
machine))
Representaremos um registrador como um procedimento com estado local,
como no Capítulo 3. O
procedimento make-register cria um registrador que mantém
um valor que pode ser acessado ou alterado:
(define (make-register name)
(let ((contents '*unassigned*))
(define (dispatch message)
(cond ((eq? message 'get) contents)
((eq? message 'set)
(lambda (value)
(set! contents value)))
(else
(error "Unknown request:
REGISTER"
message))))
dispatch))Os seguintes procedimentos são usados para acessar registradores:
(define (get-contents register)
(register 'get))
(define (set-contents! register value)
((register 'set) value))
Também podemos representar uma pilha como um procedimento com estado
local. O procedimento make-stack cria uma pilha cujo estado
local consiste em uma lista dos itens na pilha. Uma pilha aceita
solicitações para push (empilhar) um item na pilha, para
pop (desempilhar) o item superior da pilha e retorná-lo, e
para initialize (inicializar) a pilha como vazia.
(define (make-stack)
(let ((s '()))
(define (push x)
(set! s (cons x s)))
(define (pop)
(if (null? s)
(error "Empty stack: POP")
(let ((top (car s)))
(set! s (cdr s))
top)))
(define (initialize)
(set! s '())
'done)
(define (dispatch message)
(cond ((eq? message 'push) push)
((eq? message 'pop) (pop))
((eq? message 'initialize)
(initialize))
(else
(error "Unknown request: STACK"
message))))
dispatch))Os seguintes procedimentos são usados para acessar pilhas:
(define (pop stack) (stack 'pop))
(define (push stack value)
((stack 'push) value))
O procedimento make-new-machine, mostrado na
Figura 5.13, constrói um objeto cujo
estado local consiste em uma pilha, uma sequência de instruções
inicialmente vazia, uma lista de operações que inicialmente contém uma
operação para inicializar a pilha, e uma
tabela de registradores que
inicialmente contém dois registradores, chamados flag e
pc (para "contador de programa"). O procedimento interno
allocate-register adiciona novas entradas à tabela de
registradores, e o procedimento interno
lookup-register procura registradores na tabela.
Figura 5.13:
O procedimento make-new-machine, que implementa o modelo
básico de máquina.
(define (make-new-machine)
(let ((pc (make-register 'pc))
(flag (make-register 'flag))
(stack (make-stack))
(the-instruction-sequence '()))
(let ((the-ops
(list
(list 'initialize-stack
(lambda ()
(stack 'initialize)))))
(register-table
(list (list 'pc pc)
(list 'flag flag))))
(define (allocate-register name)
(if (assoc name register-table)
(error
"Multiply defined register: "
name)
(set! register-table
(cons
(list name
(make-register name))
register-table)))
'register-allocated)
(define (lookup-register name)
(let ((val
(assoc name register-table)))
(if val
(cadr val)
(error "Unknown register:"
name))))
(define (execute)
(let ((insts (get-contents pc)))
(if (null? insts)
'done
(begin
((instruction-execution-proc
(car insts)))
(execute)))))
(define (dispatch message)
(cond ((eq? message 'start)
(set-contents!
pc
the-instruction-sequence)
(execute))
((eq?
message
'install-instruction-sequence)
(lambda (seq)
(set!
the-instruction-sequence
seq)))
((eq? message
'allocate-register)
allocate-register)
((eq? message 'get-register)
lookup-register)
((eq? message
'install-operations)
(lambda (ops)
(set! the-ops
(append the-ops ops))))
((eq? message 'stack) stack)
((eq? message 'operations)
the-ops)
(else
(error "Unknown request:
MACHINE"
message))))
dispatch)))
O registrador flag é usado para controlar o desvio na
máquina simulada. Instruções test definem o conteúdo de
flag como o resultado do teste (verdadeiro ou falso).
Instruções branch decidem se devem ou não desviar
examinando o conteúdo de flag.
O registrador pc determina a sequência de instruções à
medida que a máquina é executada. Essa sequência é implementada pelo
procedimento interno execute. No modelo de simulação, cada
instrução da máquina é uma estrutura de dados que inclui um procedimento
sem argumentos, chamado de
procedimento de execução de instrução, de modo que chamar esse
procedimento simula a execução da instrução. À medida que a simulação é
executada, pc aponta para o lugar na sequência de
instruções que começa com a próxima instrução a ser executada.
Execute obtém essa instrução, executa-a chamando o
procedimento de execução de instrução e repete esse ciclo até que não
haja mais instruções para executar (ou seja, até que
pc aponte para o final da sequência de instruções).
Como parte de sua operação, cada procedimento de execução de instrução
modifica pc para indicar a próxima instrução a ser
executada. Instruções branch e goto alteram
pc para apontar para o novo destino. Todas as outras
instruções simplesmente avançam pc, fazendo-o apontar para
a próxima instrução na sequência. Observe que cada chamada para
execute chama execute novamente, mas isso não
produz um loop infinito porque a execução do procedimento de execução de
instrução altera o conteúdo de pc.
Make-new-machine retorna um procedimento
dispatch que implementa o acesso por passagem de mensagens
ao estado interno. Observe que iniciar a máquina é realizado definindo
pc para o início da sequência de instruções e chamando
execute.
Para conveniência, fornecemos uma interface procedural alternativa para
a operação start de uma máquina, bem como procedimentos
para definir e examinar o conteúdo dos registradores, conforme
especificado no início de 5.2:
(define (start machine)
(machine 'start))
(define (get-register-contents
machine register-name)
(get-contents
(get-register machine register-name)))
(define (set-register-contents!
machine register-name value)
(set-contents!
(get-register machine register-name)
value)
'done)Esses procedimentos (e muitos procedimentos em 5.2.2 e 5.2.3) usam o seguinte para procurar o registrador com um determinado nome em uma determinada máquina:
(define (get-register machine reg-name)
((machine 'get-register) reg-name))O montador transforma a sequência de expressões do controlador de uma máquina em uma lista correspondente de instruções da máquina, cada uma com seu procedimento de execução. No geral, o montador é muito parecido com os avaliadores que estudamos no Capítulo 4—há uma linguagem de entrada (neste caso, a linguagem de máquina de registradores) e devemos realizar uma ação apropriada para cada tipo de expressão na linguagem.
A técnica de produzir um procedimento de execução para cada instrução é exatamente o que usamos em 4.1.7 para acelerar o avaliador separando a análise da execução em tempo de execução. Como vimos no Capítulo 4, muita análise útil de expressões Scheme poderia ser realizada sem conhecer os valores reais das variáveis. Aqui, analogamente, muita análise útil de expressões da linguagem de máquina de registradores pode ser realizada sem conhecer o conteúdo real dos registradores da máquina. Por exemplo, podemos substituir referências a registradores por ponteiros para os objetos de registrador, e podemos substituir referências a rótulos por ponteiros para o lugar na sequência de instruções que o rótulo designa.
Antes de gerar os procedimentos de execução de instruções, o montador deve saber a que todos os rótulos se referem, então ele começa escaneando o texto do controlador para separar os rótulos das instruções. À medida que escaneia o texto, ele constrói tanto uma lista de instruções quanto uma tabela que associa cada rótulo a um ponteiro para essa lista. Em seguida, o montador aumenta a lista de instruções inserindo o procedimento de execução para cada instrução.
O procedimento assemble é a entrada principal para o
montador. Ele recebe o texto do controlador e o modelo da máquina como
argumentos e retorna a sequência de instruções a ser armazenada no
modelo. Assemble chama extract-labels para
construir a lista inicial de instruções e a tabela de rótulos a partir
do texto do controlador fornecido. O segundo argumento para
extract-labels é um procedimento a ser chamado para
processar esses resultados: Este procedimento usa
update-insts! para gerar os procedimentos de execução de
instruções e inseri-los na lista de instruções, e retorna a lista
modificada.
(define (assemble controller-text machine)
(extract-labels controller-text
(lambda (insts labels)
(update-insts! insts labels machine)
insts)))
Extract-labels recebe como argumentos uma lista
text (a sequência de expressões de instrução do
controlador) e um procedimento receive.
Receive será chamado com dois valores: (1) uma lista
insts de estruturas de dados de instrução, cada uma
contendo uma instrução de text; e (2) uma tabela chamada
labels, que associa cada rótulo de text à
posição na lista insts que o rótulo designa.
(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))))))
Extract-labels funciona escaneando sequencialmente os
elementos de text e acumulando insts e
labels. Se um elemento é um símbolo (e, portanto, um
rótulo), uma entrada apropriada é adicionada à tabela
labels. Caso contrário, o elemento é acumulado na lista
insts.289
Update-insts! modifica a lista de instruções, que
inicialmente contém apenas o texto das instruções, para incluir os
procedimentos de execução correspondentes:
(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)))
A estrutura de dados de instrução da máquina simplesmente emparelha o
texto da instrução com o procedimento de execução correspondente. O
procedimento de execução ainda não está disponível quando
extract-labels constrói a instrução, e é inserido
posteriormente por update-insts!.
(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))O texto da instrução não é usado pelo nosso simulador, mas é útil mantê-lo por perto para depuração (veja Exercício 5.16).
Elementos da tabela de rótulos são pares:
(define (make-label-entry label-name insts)
(cons label-name insts))As entradas serão procuradas na tabela com
(define (lookup-label labels label-name)
(let ((val (assoc label-name labels)))
(if val
(cdr val)
(error "Undefined label: ASSEMBLE"
label-name))))Exercício 5.8: O seguinte código de máquina de registradores é ambíguo, porque o rótulo
hereé definido mais de uma vez:start (goto (label here)) here (assign a (const 3)) (goto (label there)) here (assign a (const 4)) (goto (label there)) thereCom o simulador como está escrito, qual será o conteúdo do registrador
aquando o controle chegar athere? Modifique o procedimentoextract-labelspara que o montador sinalize um erro se o mesmo nome de rótulo for usado para indicar dois locais diferentes.
O montador chama make-execution-procedure para gerar o
procedimento de execução para uma instrução. Como o procedimento
analyze no avaliador de
4.1.7, ele despacha no tipo
de instrução para gerar o procedimento de execução apropriado.
(define (make-execution-procedure
inst labels machine pc flag stack ops)
(cond ((eq? (car inst) 'assign)
(make-assign
inst machine labels ops pc))
((eq? (car inst) 'test)
(make-test
inst machine labels ops flag pc))
((eq? (car inst) 'branch)
(make-branch
inst machine labels flag pc))
((eq? (car inst) 'goto)
(make-goto inst machine labels pc))
((eq? (car inst) 'save)
(make-save inst machine stack pc))
((eq? (car inst) 'restore)
(make-restore inst machine stack pc))
((eq? (car inst) 'perform)
(make-perform
inst machine labels ops pc))
(else (error "Unknown instruction
type: ASSEMBLE"
inst))))Para cada tipo de instrução na linguagem de máquina de registradores, há um gerador que constrói um procedimento de execução apropriado. Os detalhes desses procedimentos determinam tanto a sintaxe quanto o significado das instruções individuais na linguagem de máquina de registradores. Usamos abstração de dados para isolar a sintaxe detalhada das expressões de máquina de registradores do mecanismo geral de execução, como fizemos para avaliadores em 4.1.2, usando procedimentos de sintaxe para extrair e classificar as partes de uma instrução.
Assign Instruções
O procedimento make-assign lida com instruções
assign:
(define (make-assign
inst machine labels operations pc)
(let ((target
(get-register
machine
(assign-reg-name inst)))
(value-exp (assign-value-exp inst)))
(let ((value-proc
(if (operation-exp? value-exp)
(make-operation-exp
value-exp
machine
labels
operations)
(make-primitive-exp
(car value-exp)
machine
labels))))
(lambda () ; procedimento de execução
; para assign
(set-contents! target (value-proc))
(advance-pc pc)))))
Make-assign extrai o nome do registrador de destino (o
segundo elemento da instrução) e a expressão de valor (o resto da lista
que forma a instrução) da instrução assign usando os
seletores
(define (assign-reg-name assign-instruction)
(cadr assign-instruction))
(define (assign-value-exp assign-instruction)
(cddr assign-instruction))
O nome do registrador é procurado com get-register para
produzir o objeto de registrador de destino. A expressão de valor é
passada para make-operation-exp se o valor for o resultado
de uma operação, e para make-primitive-exp caso contrário.
Esses procedimentos (mostrados abaixo) analisam a expressão de valor e
produzem um procedimento de execução para o valor. Este é um
procedimento sem argumentos, chamado value-proc, que será
avaliado durante a simulação para produzir o valor real a ser atribuído
ao registrador. Observe que o trabalho de procurar o nome do registrador
e analisar a expressão de valor é realizado apenas uma vez, no momento
da montagem, não toda vez que a instrução é simulada. Essa economia de
trabalho é a razão pela qual usamos procedimentos de execução e
corresponde diretamente à economia de trabalho que obtivemos separando a
análise do programa da execução no avaliador de
4.1.7.
O resultado retornado por make-assign é o procedimento de
execução para a instrução assign. Quando este procedimento
é chamado (pelo procedimento execute do modelo da máquina),
ele define o conteúdo do registrador de destino como o resultado obtido
pela execução de value-proc. Em seguida, ele avança o
pc para a próxima instrução executando o procedimento
(define (advance-pc pc)
(set-contents! pc (cdr (get-contents pc))))
Advance-pc é a terminação normal para todas as instruções,
exceto branch e goto.
Test, branch, e goto Instruções
Make-test lida com instruções test de maneira
semelhante. Ele extrai a expressão que especifica a condição a ser
testada e gera um procedimento de execução para ela. No momento da
simulação, o procedimento para a condição é chamado, o resultado é
atribuído ao registrador flag, e o pc é
avançado:
(define
(make-test
inst machine labels operations flag pc)
(let ((condition (test-condition inst)))
(if (operation-exp? condition)
(let ((condition-proc
(make-operation-exp
condition
machine
labels
operations)))
(lambda ()
(set-contents!
flag (condition-proc))
(advance-pc pc)))
(error "Bad TEST instruction:
ASSEMBLE" inst))))
(define (test-condition test-instruction)
(cdr test-instruction))
O procedimento de execução para uma instrução
branch verifica o conteúdo do registrador
flag e define o conteúdo do pc para o destino
do desvio (se o desvio for tomado) ou simplesmente avança o
pc (se o desvio não for tomado). Observe que o destino
indicado em uma instrução branch deve ser um rótulo, e o
procedimento make-branch impõe isso. Observe também que o
rótulo é procurado no momento da montagem, não cada vez que a instrução
branch é simulada.
(define
(make-branch
inst machine labels flag pc)
(let ((dest (branch-dest inst)))
(if (label-exp? dest)
(let ((insts
(lookup-label
labels
(label-exp-label dest))))
(lambda ()
(if (get-contents flag)
(set-contents! pc insts)
(advance-pc pc))))
(error "Bad BRANCH instruction:
ASSEMBLE"
inst))))
(define (branch-dest branch-instruction)
(cadr branch-instruction))
Uma instrução goto é semelhante a um desvio, exceto que o
destino pode ser especificado como um rótulo ou como um registrador, e
não há condição para verificar—o pc é sempre definido para
o novo destino.
(define (make-goto inst machine labels pc)
(let ((dest (goto-dest inst)))
(cond ((label-exp? dest)
(let ((insts
(lookup-label
labels
(label-exp-label dest))))
(lambda ()
(set-contents! pc insts))))
((register-exp? dest)
(let ((reg
(get-register
machine
(register-exp-reg dest))))
(lambda ()
(set-contents!
pc
(get-contents reg)))))
(else (error "Bad GOTO instruction:
ASSEMBLE"
inst)))))
(define (goto-dest goto-instruction)
(cadr goto-instruction))
As instruções de pilha save e
restore simplesmente usam a pilha com o registrador
designado e avançam o pc:
(define (make-save inst machine stack pc)
(let ((reg (get-register
machine
(stack-inst-reg-name inst))))
(lambda ()
(push stack (get-contents reg))
(advance-pc pc))))
(define (make-restore inst machine stack pc)
(let ((reg (get-register
machine
(stack-inst-reg-name inst))))
(lambda ()
(set-contents! reg (pop stack))
(advance-pc pc))))
(define (stack-inst-reg-name
stack-instruction)
(cadr stack-instruction))
O tipo final de instrução, tratado por make-perform, gera
um procedimento de execução para a ação a ser realizada. No momento da
simulação, o procedimento de ação é executado e o pc é
avançado.
(define (make-perform
inst machine labels operations pc)
(let ((action (perform-action inst)))
(if (operation-exp? action)
(let ((action-proc
(make-operation-exp
action
machine
labels
operations)))
(lambda ()
(action-proc)
(advance-pc pc)))
(error "Bad PERFORM instruction:
ASSEMBLE"
inst))))
(define (perform-action inst) (cdr inst))
O valor de uma expressão reg, label ou
const pode ser necessário para atribuição a um registrador
(make-assign) ou para entrada em uma operação
(make-operation-exp, abaixo). O seguinte procedimento gera
procedimentos de execução para produzir valores para essas expressões
durante a simulação:
(define (make-primitive-exp exp machine labels)
(cond ((constant-exp? exp)
(let ((c (constant-exp-value exp)))
(lambda () c)))
((label-exp? exp)
(let ((insts
(lookup-label
labels
(label-exp-label exp))))
(lambda () insts)))
((register-exp? exp)
(let ((r (get-register
machine
(register-exp-reg exp))))
(lambda () (get-contents r))))
(else (error "Unknown expression type:
ASSEMBLE"
exp))))
A sintaxe das expressões reg, label e
const é determinada por
(define (register-exp? exp)
(tagged-list? exp 'reg))
(define (register-exp-reg exp)
(cadr exp))
(define (constant-exp? exp)
(tagged-list? exp 'const))
(define (constant-exp-value exp)
(cadr exp))
(define (label-exp? exp)
(tagged-list? exp 'label))
(define (label-exp-label exp)
(cadr exp))
Instruções assign, perform e
test podem incluir a aplicação de uma operação de máquina
(especificada por uma expressão op) a alguns operandos
(especificados por expressões reg e const). O
seguinte procedimento produz um procedimento de execução para uma
"expressão de operação"—uma lista contendo a operação e as expressões de
operando da instrução:
(define (make-operation-exp
exp machine labels operations)
(let ((op (lookup-prim
(operation-exp-op exp)
operations))
(aprocs
(map (lambda (e)
(make-primitive-exp
e machine labels))
(operation-exp-operands exp))))
(lambda () (apply op (map (lambda (p) (p))
aprocs)))))A sintaxe das expressões de operação é determinada por
(define (operation-exp? exp)
(and (pair? exp)
(tagged-list? (car exp) 'op)))
(define (operation-exp-op operation-exp)
(cadr (car operation-exp)))
(define (operation-exp-operands operation-exp)
(cdr operation-exp))
Observe que o tratamento das expressões de operação é muito semelhante
ao tratamento das aplicações de procedimentos pelo procedimento
analyze-application no avaliador de
4.1.7 em que geramos um
procedimento de execução para cada operando. No momento da simulação,
chamamos os procedimentos de operando e aplicamos o procedimento Scheme
que simula a operação aos valores resultantes. O procedimento de
simulação é encontrado procurando o nome da operação na tabela de
operações da máquina:
(define (lookup-prim symbol operations)
(let ((val (assoc symbol operations)))
(if val
(cadr val)
(error "Unknown operation: ASSEMBLE"
symbol))))Exercício 5.9: O tratamento das operações de máquina acima permite que elas operem em rótulos, bem como em constantes e no conteúdo de registradores. Modifique os procedimentos de processamento de expressões para impor a condição de que as operações só podem ser usadas com registradores e constantes.
Exercício 5.10: Projete uma nova sintaxe para instruções de máquina de registradores e modifique o simulador para usar sua nova sintaxe. Você pode implementar sua nova sintaxe sem alterar nenhuma parte do simulador, exceto os procedimentos de sintaxe nesta seção?
Exercício 5.11: Quando introduzimos
saveerestoreem 5.1.4, não especificamos o que aconteceria se você tentasse restaurar um registrador que não foi o último salvo, como na sequência(save y) (save x) (restore y)Há várias possibilidades razoáveis para o significado de
restore:
(restore y)coloca emyo último valor salvo na pilha, independentemente de qual registrador esse valor veio. Esta é a maneira como nosso simulador se comporta. Mostre como tirar vantagem desse comportamento para eliminar uma instrução da máquina de Fibonacci de 5.1.4 (Figura 5.12).(restore y)coloca emyo último valor salvo na pilha, mas apenas se esse valor foi salvo dey; caso contrário, ele sinaliza um erro. Modifique o simulador para se comportar dessa maneira. Você terá que alterarsavepara colocar o nome do registrador na pilha junto com o valor.(restore y)coloca emyo último valor salvo dey, independentemente de quais outros registradores foram salvos apósye não restaurados. Modifique o simulador para se comportar dessa maneira. Você terá que associar uma pilha separada a cada registrador. Você deve fazer a operaçãoinitialize-stackinicializar todas as pilhas de registradores.
Exercício 5.12: O simulador pode ser usado para ajudar a determinar os caminhos de dados necessários para implementar uma máquina com um determinado controlador. Estenda o montador para armazenar as seguintes informações no modelo da máquina:
- uma lista de todas as instruções, com duplicatas removidas, ordenadas por tipo de instrução (
assign,goto, e assim por diante);- uma lista (sem duplicatas) dos registradores usados para manter pontos de entrada (esses são os registradores referenciados por instruções
goto);- uma lista (sem duplicatas) dos registradores que são
saved ourestored;- para cada registrador, uma lista (sem duplicatas) das fontes das quais ele é atribuído (por exemplo, as fontes para o registrador
valna máquina fatorial de Figura 5.11 são(const 1)e((op *) (reg n) (reg val))).Estenda a interface de passagem de mensagens para a máquina para fornecer acesso a essas novas informações. Para testar seu analisador, defina a máquina de Fibonacci de Figura 5.12 e examine as listas que você construiu.
Exercício 5.13: Modifique o simulador para que ele use a sequência do controlador para determinar quais registradores a máquina tem, em vez de exigir uma lista de registradores como argumento para
make-machine. Em vez de pré-alocar os registradores emmake-machine, você pode alocá-los um por um quando eles forem vistos pela primeira vez durante a montagem das instruções.
A simulação é útil não apenas para verificar a correção de um projeto de
máquina proposto, mas também para medir o desempenho da máquina. Por
exemplo, podemos instalar em nosso programa de simulação um "medidor"
que mede o número de operações de pilha usadas em um cálculo. Para fazer
isso, modificamos nossa pilha simulada para acompanhar o número de vezes
que os registradores são salvos na pilha e a profundidade máxima
atingida pela pilha, e adicionamos uma mensagem à interface da pilha que
imprime as estatísticas, como mostrado abaixo. Também adicionamos uma
operação ao modelo básico de máquina para imprimir as estatísticas da
pilha, inicializando the-ops em
make-new-machine para
(list (list 'initialize-stack
(lambda ()
(stack 'initialize)))
(list 'print-stack-statistics
(lambda ()
(stack 'print-statistics))))Aqui está a nova versão de make-stack:
(define (make-stack)
(let ((s '())
(number-pushes 0)
(max-depth 0)
(current-depth 0))
(define (push x)
(set! s (cons x s))
(set! number-pushes (+ 1 number-pushes))
(set! current-depth (+ 1 current-depth))
(set! max-depth
(max current-depth max-depth)))
(define (pop)
(if (null? s)
(error "Empty stack: POP")
(let ((top (car s)))
(set! s (cdr s))
(set! current-depth
(- current-depth 1))
top)))
(define (initialize)
(set! s '())
(set! number-pushes 0)
(set! max-depth 0)
(set! current-depth 0)
'done)
(define (print-statistics)
(newline)
(display (list 'total-pushes
'=
number-pushes
'maximum-depth
'=
max-depth)))
(define (dispatch message)
(cond ((eq? message 'push) push)
((eq? message 'pop) (pop))
((eq? message 'initialize)
(initialize))
((eq? message 'print-statistics)
(print-statistics))
(else
(error "Unknown request: STACK"
message))))
dispatch))Exercício 5.15 a Exercício 5.19 descrevem outros recursos úteis de monitoramento e depuração que podem ser adicionados ao simulador de máquina de registradores.
Exercício 5.14: Meça o número de empilhamentos e a profundidade máxima da pilha necessária para calcular para vários pequenos valores de usando a máquina fatorial mostrada na Figura 5.11. A partir de seus dados, determine fórmulas em termos de para o número total de operações de empilhamento e a profundidade máxima da pilha usada no cálculo de para qualquer . Observe que cada uma dessas é uma função linear de e, portanto, é determinada por duas constantes. Para obter as estatísticas impressas, você terá que aumentar a máquina fatorial com instruções para inicializar a pilha e imprimir as estatísticas. Você pode querer também modificar a máquina para que ela leia repetidamente um valor para , calcule o fatorial e imprima o resultado (como fizemos para a máquina MDC na Figura 5.4), para que você não precise invocar repetidamente
get-register-contents,set-register-contents!estart.
Exercício 5.15: Adicione contagem de instruções à simulação de máquina de registradores. Ou seja, faça o modelo da máquina acompanhar o número de instruções executadas. Estenda a interface do modelo da máquina para aceitar uma nova mensagem que imprime o valor da contagem de instruções e redefine a contagem para zero.
Exercício 5.16: Aumente o simulador para fornecer rastreamento de instruções. Ou seja, antes de cada instrução ser executada, o simulador deve imprimir o texto da instrução. Faça o modelo da máquina aceitar mensagens
trace-onetrace-offpara ligar e desligar o rastreamento.
Exercício 5.17: Estenda o rastreamento de instruções de Exercício 5.16 para que, antes de imprimir uma instrução, o simulador imprima quaisquer rótulos que precedam imediatamente essa instrução na sequência do controlador. Tenha cuidado para fazer isso de uma maneira que não interfira na contagem de instruções (Exercício 5.15). Você terá que fazer o simulador reter as informações de rótulo necessárias.
Exercício 5.18: Modifique o procedimento
make-registerde 5.2.1 para que os registradores possam ser rastreados. Registradores devem aceitar mensagens que ligam e desligam o rastreamento. Quando um registrador é rastreado, atribuir um valor ao registrador deve imprimir o nome do registrador, o conteúdo antigo do registrador e o novo conteúdo sendo atribuído. Estenda a interface para o modelo da máquina para permitir que você ligue e desligue o rastreamento para registradores designados da máquina.
Exercício 5.19: Alyssa P. Hacker quer um recurso de ponto de interrupção no simulador para ajudá-la a depurar seus projetos de máquinas. Você foi contratado para instalar esse recurso para ela. Ela quer ser capaz de especificar um lugar na sequência do controlador onde o simulador parará e permitirá que ela examine o estado da máquina. Você deve implementar um procedimento
(set-breakpoint ⟨machine⟩ ⟨label⟩ ⟨n⟩)que define um ponto de interrupção logo antes da instrução após o rótulo fornecido. Por exemplo,
(set-breakpoint gcd-machine 'test-b 4)instala um ponto de interrupção em
gcd-machinelogo antes da atribuição ao registradora. Quando o simulador atinge o ponto de interrupção, ele deve imprimir o rótulo e o deslocamento do ponto de interrupção e parar de executar instruções. Alyssa pode então usarget-register-contentseset-register-contents!para manipular o estado da máquina simulada. Ela deve então ser capaz de continuar a execução dizendo(proceed-machine ⟨machine⟩)Ela também deve ser capaz de remover um ponto de interrupção específico por meio de
(cancel-breakpoint ⟨machine⟩ ⟨label⟩ ⟨n⟩)ou remover todos os pontos de interrupção por meio de
(cancel-all-breakpoints ⟨machine⟩)
289 Usar
o procedimento receive aqui é uma maneira de fazer com
que extract-labels retorne efetivamente dois
valores—labels e insts—sem explicitamente
criar uma estrutura de dados composta para armazená-los. Uma
implementação alternativa, que retorna um par explícito de valores,
é
(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)))))))que seria chamado por assemble da seguinte forma:
(define (assemble controller-text machine)
(let ((result
(extract-labels controller-text)))
(let ((insts (car result))
(labels (cdr result)))
(update-insts! insts labels machine)
insts)))
Você pode considerar nosso uso de receive como uma
demonstração de uma maneira elegante de retornar múltiplos valores,
ou simplesmente uma desculpa para mostrar um truque de programação.
Um argumento como receive que é o próximo procedimento
a ser invocado é chamado de “continuação”. Lembre-se de que também
usamos continuações para implementar a estrutura de controle de
backtracking no avaliador amb em
4.3.3.