Pular para o conteúdo principal

5.2.2 O Montador

O montador transforma a sequência de instruções do controlador para uma máquina em uma lista correspondente de instruções de máquina, cada uma com sua função de execução. No geral, o montador é muito parecido com os avaliadores que estudamos no capítulo 4—existe uma linguagem de entrada (neste caso, a linguagem de máquina de registradores) e devemos executar uma ação apropriada para cada tipo de componente na linguagem.

A técnica de produzir uma função de execução para cada instrução é exatamente o que usamos na seção 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 JavaScript pode ser realizada sem saber os valores reais dos nomes. Aqui, analogamente, muita análise útil de expressões da linguagem de máquina de registradores pode ser realizada sem saber 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 poder gerar as funções de execução de instrução, o montador deve saber a que todos os rótulos se referem, então ele começa varrendo a sequência do controlador para separar os rótulos das instruções. À medida que varre o controlador, ele constrói tanto uma lista de instruções quanto uma tabela que associa cada rótulo com um ponteiro para essa lista. Então o montador aumenta a lista de instruções inserindo a função de execução para cada instrução.

A função assemble é o ponto de entrada principal para o montador. Ela recebe a sequência do controlador e o modelo de máquina como argumentos e retorna a sequência de instruções a ser armazenada no modelo. A função assemble chama extract_labels para construir a lista de instruções inicial e a tabela de rótulos a partir da sequência do controlador fornecida. O segundo argumento para extract_labels é uma função a ser chamada para processar esses resultados: Esta função usa update_insts para gerar as funções de execução de instrução e inseri-las na lista de instruções, e retorna a lista modificada.

Exemplo de Código

1function assemble(controller, machine) {
2  return extract_labels(controller,
3                        (insts, labels) => {
4                            update_insts(insts, labels, machine);
5                            return insts;
6                        });
7}

function assemble(controller, machine) {
  return extract_labels(controller,
                        (insts, labels) => {
                            update_insts(insts, labels, machine);
                            return insts;
                        });
}

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

A função extract_labels recebe uma lista controller e uma função receive como argumentos. A função receive será chamada com dois valores: (1) uma lista insts de estruturas de dados de instrução, cada uma contendo uma instrução de controller; e (2) uma tabela chamada labels, que associa cada rótulo de controller com a posição na lista insts que o rótulo designa.

Exemplo de Código

1function extract_labels(controller, receive) {
2  return is_null(controller)
3         ? receive(null, null)
4         : extract_labels(
5               tail(controller),
6               (insts, labels) => {
7                 const next_element = head(controller);
8                 return is_string(next_element)
9                        ? receive(insts,
10                                  pair(make_label_entry(next_element,
11                                                        insts),
12                                       labels))
13                        : receive(pair(make_inst(next_element),
14                                       insts),
15                                  labels);
16               });
17}

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);
               });
}

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

A função extract_labels funciona varrendo sequencialmente os elementos do controller e acumulando insts e labels. Se um elemento é uma string (e portanto um rótulo), uma entrada apropriada é adicionada à tabela labels. Caso contrário, o elemento é acumulado na lista insts.¹

A função update_insts modifica a lista de instruções, que inicialmente contém apenas as instruções do controlador, para incluir as funções de execução correspondentes:

Exemplo de Código

1function update_insts(insts, labels, machine) {
2  const pc = get_register(machine, "pc");
3  const flag = get_register(machine, "flag");
4  const stack = machine("stack");
5  const ops = machine("operations");
6  return for_each(inst => set_inst_execution_fun(
7                              inst,
8                              make_execution_function(
9                                  inst_controller_instruction(inst),
10                                  labels, machine, pc,
11                                  flag, stack, ops)),
12                  insts);
13}

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);
}

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

A estrutura de dados de instrução de máquina simplesmente emparelha a instrução do controlador com a função de execução correspondente. A função de execução não está ainda disponível quando extract_labels constrói a instrução, e é inserida mais tarde por update_insts.

Exemplo de Código

1function make_inst(inst_controller_instruction) {
2  return pair(inst_controller_instruction, null);
3}
4function inst_controller_instruction(inst) {
5  return head(inst);
6}
7function inst_execution_fun(inst) {
8  return tail(inst);
9}
10function set_inst_execution_fun(inst, fun) {
11  set_tail(inst, fun);
12}

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);
}

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

A instrução do controlador não é usada por nosso simulador, mas é útil manter por perto para depuração (veja o exercício 5.16).

Elementos da tabela de rótulos são pares:

Exemplo de Código

1function make_label_entry(label_name, insts) {
2  return pair(label_name, insts);
3}

function make_label_entry(label_name, insts) {
  return pair(label_name, insts);
}

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

Entradas serão procuradas na tabela com:

Exemplo de Código

1function lookup_label(labels, label_name) {
2  const val = assoc(label_name, labels);
3  return is_undefined(val)
4         ? error(label_name, "undefined label -- assemble")
5         : tail(val);
6}

function lookup_label(labels, label_name) {
  const val = assoc(label_name, labels);
  return is_undefined(val)
         ? error(label_name, "undefined label -- assemble")
         : tail(val);
}

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

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",
  go_to(label("here")),
"here",
  assign("a", constant(3)),
  go_to(label("there")),
"here",
  assign("a", constant(4)),
  go_to(label("there")),
"there",

Com o simulador como escrito, qual será o conteúdo do registrador a quando o controle chegar a there? Modifique a função extract_labels de modo que o montador sinalize um erro se o mesmo nome de rótulo for usado para indicar dois locais diferentes.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Com o montador como está, extract_labels constrói a lista de rótulos na ordem do texto e a busca encontra a primeira ocorrência — então go_to(label("here")) salta para o primeiro here, e a termina valendo 3.

Para rejeitar a ambiguidade, extract_labels verifica duplicatas ao inserir cada rótulo:

is_undefined(assoc(next_element, labels))
? pair(make_label_entry(next_element, insts), labels)
: error(next_element, "rótulo duplicado -- assemble")

O montador falha na montagem — em tempo de "compilação" da máquina, não no meio da execução, que é onde se quer pegar esse tipo de erro.

Resolvi o exercício 5.8

Usar a função receive aqui é uma maneira de fazer extract_labels efetivamente retornar dois valores—labels e insts—sem explicitamente criar uma estrutura de dados composta para mantê-los. Uma implementação alternativa, que retorna um par explícito de valores, é:

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);
    }
}

que seria chamada por assemble da seguinte forma:

function assemble(controller, machine) {
    const result = extract_labels(controller);
    const insts = head(result);
    const labels = tail(result);
    update_insts(insts, labels, machine);
    return insts;
}

Você pode considerar nosso uso de receive como demonstrando uma maneira elegante de retornar múltiplos valores, ou simplesmente uma desculpa para exibir um truque de programação. Um argumento como receive que é a próxima função a ser invocada é chamado de "continuação". Lembre-se de que também usamos continuações para implementar a estrutura de controle de retrocesso no avaliador amb na seção 4.3.3. ↩

Exercício 5.8