5.2.3 Instruções e Suas Funções de Execução
O montador chama make_execution_function para gerar a função de execução para uma instrução do controlador. Como a função analyze no avaliador da seção 4.1.7, esta despacha no tipo da instrução para gerar a função de execução apropriada. Os detalhes dessas funções de execução determinam o significado das instruções individuais na linguagem de máquina de registradores.
Os elementos da sequência controller recebida por make_machine e passada para assemble são strings (para rótulos) e listas marcadas (para instruções). A marca em uma instrução é uma string que identifica o tipo de instrução, como "go_to", e os elementos restantes da lista contêm os argumentos, como o destino do go_to. O despacho em make_execution_function usa:
As listas marcadas são construídas quando a expressão list que é o terceiro argumento para make_machine é avaliada. Cada argumento para essa list é ou uma string (que avalia para si mesma) ou uma chamada para um construtor para uma lista marcada de instrução. Por exemplo, assign("b", reg("t")) chama o construtor assign com argumentos "b" e o resultado de chamar o construtor reg com o argumento "t". Os construtores e seus argumentos determinam a sintaxe das instruções individuais na linguagem de máquina de registradores. Os construtores de instrução e seletores são mostrados abaixo, juntamente com os geradores de função de execução que usam os seletores.
A instrução assign
A função make_assign_ef cria funções de execução para instruções assign:
A função assign constrói instruções assign. Os seletores assign_reg_name e assign_value_exp extraem o nome do registrador e a expressão de valor de uma instrução assign.
A função make_assign_ef procura o nome do registrador com get_register para produzir o objeto de registrador alvo. A expressão de valor é passada para make_operation_exp_ef se o valor é o resultado de uma operação, e é passada para make_primitive_exp_ef caso contrário. Essas funções (mostradas abaixo) analisam a expressão de valor e produzem uma função de execução para o valor. Esta é uma função sem argumentos, chamada value_fun, que será avaliada 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. Esta economia de trabalho é a razão pela qual usamos funções de execução, e corresponde diretamente à economia de trabalho que obtivemos separando a análise do programa da execução no avaliador da seção 4.1.7.
O resultado retornado por make_assign_ef é a função de execução para a instrução assign. Quando esta função é chamada (pela função execute do modelo de máquina), ela define o conteúdo do registrador alvo para o resultado obtido executando value_fun. Então ela avança o pc para a próxima instrução executando a função:
A função advance_pc é a terminação normal para todas as instruções exceto branch e go_to.
As instruções test, branch e go_to
A função make_test_ef trata instruções test de maneira semelhante. Ela extrai a expressão que especifica a condição a ser testada e gera uma função de execução para ela. No tempo de simulação, a função para a condição é chamada, o resultado é atribuído ao registrador flag, e o pc é avançado:
A função test constrói instruções test. O seletor test_condition extrai a condição de um teste.
A função de execução para uma instrução branch verifica o conteúdo do registrador flag e ou define o conteúdo do pc para o destino do ramo (se o ramo for tomado) ou apenas avança o pc (se o ramo não for tomado). Observe que o destino indicado em uma instrução branch deve ser um rótulo, e a função make_branch_ef 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.
A função branch constrói instruções branch. O seletor branch_dest extrai o destino de um ramo.
Uma instrução go_to é semelhante a um ramo, exceto que o destino pode ser especificado como um rótulo ou como um registrador, e não há condição a verificar—o pc é sempre definido para o novo destino.
A função go_to constrói instruções go_to. O seletor go_to_dest extrai o destino de um go_to.
Outras instruções
As instruções de pilha save e restore simplesmente usam a pilha com o registrador designado e avançam o pc:
As funções save e restore constroem instruções save e restore. O seletor stack_inst_reg_name extrai o nome do registrador de tais instruções.
O tipo de instrução final, tratado por make_perform_ef, gera uma função de execução para a ação a ser realizada. No tempo de simulação, a função de ação é executada e o pc é avançado.
A função perform constrói instruções perform. O seletor perform_action extrai a ação de um perform.
Funções de execução para subexpressões
O valor de uma expressão reg, label ou constant pode ser necessário para atribuição a um registrador (make_assign_ef, acima) ou para entrada em uma operação (make_operation_exp_ef, abaixo). A função seguinte gera funções de execução para produzir valores para essas expressões durante a simulação:
A sintaxe de expressões reg, label e constant é determinada pelas seguintes funções construtoras, juntamente com predicados e seletores correspondentes.
As 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 constant). A função seguinte produz uma função 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:
A sintaxe de expressões de operação é determinada por:
Observe que o tratamento de expressões de operação é muito parecido com o tratamento de aplicações de função pela função analyze_application no avaliador da seção 4.1.7 em que geramos uma função de execução para cada operando. No tempo de simulação, chamamos as funções de operando e aplicamos a função JavaScript que simula a operação aos valores resultantes. Fazemos uso da função apply_in_underlying_javascript, como fizemos em apply_primitive_function na seção 4.1.4. Isso é necessário para aplicar op a todos os elementos da lista de argumentos afuns produzida pelo primeiro map, como se fossem argumentos separados para op. Sem isso, op teria sido restrito a ser uma função unária.
A função de simulação é encontrada procurando o nome da operação na tabela de operações para a máquina:
Exercício 5.9
O tratamento de operações de máquina acima permite que elas operem em rótulos bem como em constantes e conteúdo de registradores. Modifique as funções de processamento de expressão para impor a condição de que operações só podem ser usadas com registradores e constantes.
💡 Mostrar solução — tente primeiro!💡 Esconder solução
Em make_operation_exp, os operandos hoje passam por make_primitive_exp, que aceita constantes, registradores e rótulos. Restrinja no ponto de construção:
function make_operation_exp(exp, machine, labels, operations) {
const op = lookup_prim(operation_exp_op(exp), operations);
const afuns = map(e => is_label_exp(e)
? error(e, "operação sobre rótulo não permitida -- assemble")
: make_primitive_exp(e, machine, labels),
operation_exp_operands(exp));
return () => apply_in_underlying_javascript(op, map(f => f(), afuns));
}
Rótulos continuam válidos onde fazem sentido (go_to, destinos de salto em assign) — só deixam de ser operandos de operações, onde seriam um vazamento da representação interna para a aritmética da máquina.
Exercício 5.10
Quando introduzimos save e restore na seção 5.1.4, não especificamos o que aconteceria se você tentasse restaurar um registrador que não era 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 deste comportamento para eliminar uma instrução da máquina de Fibonacci da seção 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 desta maneira. Você terá que mudarsavepara colocar o nome do registrador na pilha junto com o valor. -
restore(y)coloca emyo último valor salvo deyindependentemente de quais outros registradores foram salvos depois deye não restaurados. Modifique o simulador para se comportar desta maneira. Você terá que associar uma pilha separada com cada registrador. Você deve fazer a operaçãoinitialize_stackinicializar todas as pilhas de registradores.
💡 Mostrar solução — tente primeiro!💡 Esconder solução
Três semânticas possíveis, em ordem de rigor:
- Como está (pilha única):
restore("y")entrega o último valor salvo, seja de quem for — no exemplo,yrecebe o valor salvo dex. Nenhum erro; resultados silenciosamente estranhos. - Pilha única com verificação:
saveempilha o par (nome, valor) erestoreconfere o nome:
// save: push(stack, pair(reg_name, get_contents(reg)))
// restore:
const top = pop(stack);
head(top) === reg_name
? set_contents(reg, tail(top))
: error(reg_name, "restore de registrador que não é o último salvo");
- Uma pilha por registrador: a máquina mantém uma tabela nome → pilha;
save/restoreusam a pilha do próprio registrador.restore("y")só devolve valores dey, em qualquer ordem relativa aos outros — uma disciplina diferente, que a máquina de Fibonacci aceitaria sem mudanças, mas que deixa de detectar certos erros de emparelhamento.
O exercício quer que se perceba que isso é uma escolha de projeto da máquina, não uma fatalidade.
Exercício 5.11
O simulador pode ser usado para ajudar a determinar os caminhos de dados necessários para implementar uma máquina com um dado controlador. Estenda o montador para armazenar a seguinte informação no modelo de máquina:
- uma lista de todas as instruções, com duplicatas removidas, ordenada por tipo de instrução (
assign,go_to, e assim por diante); - uma lista (sem duplicatas) dos registradores usados para manter pontos de entrada (estes são os registradores referenciados por instruções
go_to); - uma lista (sem duplicatas) dos registradores que são salvos (
save) ou restaurados (restore); - 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 da figura 5.11 sãoconstant(1)elist(op("*"), reg("n"), reg("val"))).
Estenda a interface de passagem de mensagens para a máquina para fornecer acesso a esta nova informação. Para testar seu analisador, defina a máquina de Fibonacci da figura 5.12 e examine as listas que você construiu.
💡 Mostrar solução — tente primeiro!💡 Esconder solução
Na montagem, além das funções de execução, o montador acumula quatro tabelas no modelo (expostas por novas mensagens do dispatch):
sorted_instructions // instruções únicas, agrupadas por tipo
entry_points // registradores usados em go_to(reg(...))
stack_registers // registradores que aparecem em save/restore
register_sources // nome → lista de fontes de assign
A coleta é um percurso pelas instruções: classifique cada uma pelo tipo (assign, test, branch, go_to, save, restore, perform), registre o que interessa e elimine duplicatas com member antes de inserir.
O uso prometido: essas listas são a especificação dos caminhos de dados — quais botões existem (fontes de cada registrador), onde a pilha se conecta, quais registradores alimentam saltos. O simulador vira ferramenta de projeto de hardware.
Exercício 5.12
Modifique o simulador de modo 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 em make_machine, você pode alocá-los um de cada vez quando eles são vistos pela primeira vez durante a montagem das instruções.
💡 Mostrar solução — tente primeiro!💡 Esconder solução
Troque a pré-alocação por alocação preguiçosa — get_register vira o criador:
function lookup_register(name) {
const val = assoc(name, register_table);
if (is_undefined(val)) {
allocate_register(name); // primeiro uso: cria
return lookup_register(name);
}
return tail(val);
}
Como toda referência a registrador passa por get_register durante a montagem (em make_primitive_exp, make_save, make_restore, advance_pc…), cada registrador nasce no primeiro momento em que o controlador o menciona. make_machine fica com dois argumentos (operações e controlador) — e o simulador perde uma fonte de dessincronia entre a lista declarada e a máquina real.