5.5.5 Um Exemplo de Código Compilado
Agora que vimos todos os elementos do compilador, vamos examinar um exemplo de código compilado para ver como as coisas se encaixam. Vamos compilar a declaração de uma função factorial recursiva passando como primeiro argumento para compile o resultado da aplicação de parse a uma representação em string do programa (aqui usando crases `, que funcionam como aspas simples e duplas mas permitem que a string abranja múltiplas linhas):
compile(parse(`
function factorial(n) {
return n === 1
? 1
: factorial(n - 1) * n;
}
`),
"val",
"next");
Especificamos que o valor da declaração deve ser colocado no registrador val. Não nos importamos com o que o código compilado faz após executar a declaração, então nossa escolha de "next" como descritor de ligação é arbitrária.
A função compile determina que recebeu uma declaração de função, então ela a transforma em uma declaração constante e então chama compile_declaration. Isso compila código para calcular o valor a ser atribuído (direcionado a val), seguido de código para instalar a declaração, seguido de código para colocar o valor da declaração (que é o valor undefined) no registrador alvo, seguido finalmente do código de ligação. O registrador env é preservado em torno do cálculo do valor, porque ele é necessário para instalar a declaração. Como a ligação é "next", não há código de ligação neste caso. O esqueleto do código compilado é assim:
⟨salvar env se modificado pelo código para calcular valor⟩
⟨compilação do valor da declaração, alvo val, ligação "next"⟩
⟨restaurar env se salvo acima⟩
perform(list(op("assign_symbol_value"),
constant("factorial"),
reg("val"),
reg("env"))),
assign("val", constant(undefined))
A expressão que é compilada para produzir o valor para o nome factorial é uma expressão lambda cujo valor é a função que calcula fatoriais. A função compile trata isso chamando compile_lambda_expression, que compila o corpo da função, rotula-o como um novo ponto de entrada e gera a instrução que combinará o corpo da função no novo ponto de entrada com o ambiente de tempo de execução e atribuirá o resultado a val. A sequência então pula ao redor do código da função compilada, que é inserido neste ponto. O código da função em si começa estendendo o ambiente de declaração da função por um quadro que liga o parâmetro n ao argumento da função. Então vem o corpo real da função. Como este código para o valor da variável não modifica o registrador env, o save e restore opcionais mostrados acima não são gerados. (O código da função em entry1 não é executado neste ponto, então seu uso de env é irrelevante.) Portanto, o esqueleto para o código compilado torna-se:
assign("val", list(op("make_compiled_function"),
label("entry1"),
reg("env"))),
go_to(label("after_lambda2")),
"entry1",
assign("env", list(op("compiled_function_env"), reg("fun"))),
assign("env", list(op("extend_environment"),
constant(list("n")),
reg("argl"),
reg("env"))),
⟨compilação do corpo da função⟩
"after_lambda2",
perform(list(op("assign_symbol_value"),
constant("factorial"),
reg("val"),
reg("env"))),
assign("val", constant(undefined))
O corpo de uma função é sempre compilado (por compile_lambda_body) com alvo val e ligação "next". O corpo neste caso consiste de uma única instrução return:1
return n === 1
? 1
: factorial(n - 1) * n;
A função compile_return_statement gera código para reverter a pilha usando o marcador e para restaurar o registrador continue, e então compila a expressão return com alvo val e ligação "return", porque seu valor deve ser retornado da função. A expressão return é uma expressão condicional, para a qual compile_conditional gera código que primeiro calcula o predicado (direcionado a val), então verifica o resultado e ramifica ao redor do ramo verdadeiro se o predicado for falso. Os registradores env e continue são preservados em torno do código do predicado, já que eles podem ser necessários para o resto da expressão condicional. Os ramos verdadeiro e falso são ambos compilados com alvo val e ligação "return". (Ou seja, o valor do condicional, que é o valor calculado por qualquer um de seus ramos, é o valor da função.)
revert_stack_to_marker(),
restore("continue"),
⟨salvar continue, env se modificado pelo predicado e necessário pelos ramos⟩
⟨compilação do predicado, alvo val, ligação "next"⟩
⟨restaurar continue, env se salvos acima⟩
test(list(op("is_falsy"), reg("val"))),
branch(label("false_branch4")),
"true_branch3",
⟨compilação do ramo verdadeiro, alvo val, ligação "return"⟩
"false_branch4",
⟨compilação do ramo falso, alvo val, ligação "return"⟩
"after_cond5",
O predicado n === 1 é uma aplicação de função (após transformação da combinação de operadores). Isso procura a expressão da função (o símbolo "===") e coloca este valor em fun. Ele então monta os argumentos 1 e o valor de n em argl. Então ele testa se fun contém uma função primitiva ou composta, e despacha para um ramo primitivo ou um ramo composto de acordo. Ambos os ramos retomam no rótulo after_call. O ramo composto deve configurar continue para pular após o ramo primitivo e empurrar um marcador para a pilha para corresponder à operação de reversão na instrução return compilada da função.
assign("fun", list(op("lookup_symbol_value"),
constant("==="), reg("env"))),
assign("val", constant(1)),
assign("argl", list(op("list"), reg("val"))),
assign("val", list(op("lookup_symbol_value"),
constant("n"), reg("env"))),
assign("argl", list(op("pair"), reg("val"), reg("argl"))),
test(list(op("is_primitive_function"), reg("fun"))),
branch(label("primitive_branch6")),
"compiled_branch7",
assign("continue", label("after_call8")),
save("continue"),
push_marker_to_stack(),
assign("val", list(op("compiled_function_entry"), reg("fun"))),
go_to(reg("val")),
"primitive_branch6",
assign("val", list(op("apply_primitive_function"),
reg("fun"),
reg("argl"))),
"after_call8",
Os requisitos para preservar registradores em torno da avaliação das expressões de função e argumento não resultam em nenhum salvamento de registradores, porque neste caso essas avaliações não modificam os registradores em questão.
O ramo verdadeiro, que é a constante 1, compila (com alvo val e ligação "return") para:
assign("val", constant(1)),
go_to(reg("continue")),
O código para o ramo falso é outra chamada de função, onde a função é o valor do símbolo "*", e os argumentos são n e o resultado de outra chamada de função (uma chamada a factorial). Cada uma dessas chamadas configura fun e argl e seus próprios ramos primitivo e composto. A Figura 5.17 mostra a compilação completa da declaração da função factorial. Note que os possíveis save e restore de continue e env em torno do predicado, mostrados acima, são de fato gerados, porque esses registradores são modificados pela chamada de função no predicado e necessários para a chamada de função e a ligação "return" nos ramos.
Figura 5.17: Compilação da declaração da função factorial (continua na próxima página).
// construir a função e pular o código para o corpo da função
assign("val", list(op("make_compiled_function"),
label("entry1"), reg("env"))),
go_to(label("after_lambda2")),
"entry1", // chamadas a factorial entrarão aqui
assign("env", list(op("compiled_function_env"), reg("fun"))),
assign("env", list(op("extend_environment"), constant(list("n")),
reg("argl"), reg("env"))),
// começar corpo real da função
revert_stack_to_marker(), // começa com uma instrução return
restore("continue"),
save("continue"), // preservar registradores através do predicado
save("env"),
// calcular n === 1
assign("fun", list(op("lookup_symbol_value"), constant("==="), reg("env"))),
assign("val", constant(1)),
assign("argl", list(op("list"), reg("val"))),
assign("val", list(op("lookup_symbol_value"), constant("n"), reg("env"))),
assign("argl", list(op("pair"), reg("val"), reg("argl"))),
test(list(op("is_primitive_function"), reg("fun"))),
branch(label("primitive_branch6")),
"compiled_branch7",
assign("continue", label("after_call8")),
save("continue"),
push_marker_to_stack(),
assign("val", list(op("compiled_function_entry"), reg("fun"))),
go_to(reg("val")),
"primitive_branch6",
assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))),
"after_call8", // val agora contém resultado de n === 1
restore("env"),
restore("continue"),
test(list(op("is_falsy"), reg("val"))),
branch(label("false_branch4")),
"true_branch3", // retornar 1
assign("val", constant(1)),
go_to(reg("continue")),
"false_branch4",
// calcular e retornar factorial(n - 1) * n
assign("fun", list(op("lookup_symbol_value"), constant("*"), reg("env"))),
save("continue"),
save("fun"), // salvar função *
assign("val", list(op("lookup_symbol_value"), constant("n"), reg("env"))),
assign("argl", list(op("list"), reg("val"))),
save("argl"), // salvar lista parcial de argumentos para *
// calcular factorial(n - 1) que é o outro argumento para *
assign("fun", list(op("lookup_symbol_value"),
constant("factorial"), reg("env"))),
save("fun"), // salvar função factorial
(continuação)
// calcular n - 1 que é o argumento para factorial
assign("fun", list(op("lookup_symbol_value"), constant("-"), reg("env"))),
assign("val", constant(1)),
assign("argl", list(op("list"), reg("val"))),
assign("val", list(op("lookup_symbol_value"), constant("n"), reg("env"))),
assign("argl", list(op("pair"), reg("val"), reg("argl"))),
test(list(op("is_primitive_function"), reg("fun"))),
branch(label("primitive_branch10")),
"compiled_branch11",
assign("continue", label("after_call12")),
save("continue"),
push_marker_to_stack(),
assign("val", list(op("compiled_function_entry"), reg("fun"))),
go_to(reg("val")),
"primitive_branch10",
assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))),
"after_call12", // val agora contém resultado de n - 1
assign("argl", list(op("list"), reg("val"))),
restore("fun"), // restaurar factorial
// aplicar factorial
test(list(op("is_primitive_function"), reg("fun"))),
branch(label("primitive_branch14")),
"compiled_branch15",
assign("continue", label("after_call16")),
save("continue"), // configurar para retorno de função compilada
push_marker_to_stack(), // return na função restaurará a pilha
assign("val", list(op("compiled_function_entry"), reg("fun"))),
go_to(reg("val")),
"primitive_branch14",
assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))),
"after_call16", // val agora contém resultado de factorial(n - 1)
restore("argl"), // restaurar lista parcial de argumentos para *
assign("argl", list(op("pair"), reg("val"), reg("argl"))),
restore("fun"), // restaurar *
restore("continue"),
// aplicar * e retornar seu valor
test(list(op("is_primitive_function"), reg("fun"))),
branch(label("primitive_branch18")),
"compiled_branch19", // note que uma função composta aqui é chamada tail-recursivamente
save("continue"),
push_marker_to_stack(),
assign("val", list(op("compiled_function_entry"), reg("fun"))),
go_to(reg("val")),
"primitive_branch18",
assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))),
go_to(reg("continue")),
"after_call20",
"after_cond5",
"after_lambda2",
// atribuir a função ao nome factorial
perform(list(op("assign_symbol_value"),
constant("factorial"), reg("val"), reg("env"))),
assign("val", constant(undefined))
Exercício 5.36
Considere a seguinte declaração de uma função fatorial, que é ligeiramente diferente daquela dada acima:
function factorial_alt(n) {
return n === 1
? 1
: n * factorial_alt(n - 1);
}
Compile esta função e compare o código resultante com aquele produzido para factorial. Explique quaisquer diferenças que você encontrar. Algum programa executa mais eficientemente que o outro?
💡 Mostrar solução — tente primeiro!💡 Esconder solução
A diferença da versão do texto: o condicional testa n === 1 como expressão de retorno de outra forma (ou a base retorna direto), mudando onde o compilador emite os desvios. Comparando as saídas compiladas, as instruções são essencialmente as mesmas — mudam os pontos onde o teste acontece e qual ramo cai no goto — e a moral é que variações superficiais do fonte produzem variações igualmente superficiais do objeto: o esqueleto (teste, chamada recursiva com save/restore mínimos via preserving, multiplicação na volta) é idêntico, porque é a estrutura recursiva, não a sintaxe, que dita o código.
Exercício 5.37
Compile a função fatorial iterativa:
function factorial(n) {
function iter(product, counter) {
return counter > n
? product
: iter(product * counter, counter + 1);
}
return iter(1, 1);
}
Anote o código resultante, mostrando a diferença essencial entre o código para as versões iterativa e recursiva de factorial que faz um processo construir espaço na pilha e o outro executar em espaço constante na pilha.
💡 Mostrar solução — tente primeiro!💡 Esconder solução
O ponto a observar na saída da compilação da fatorial iterativa: o laço iter vira uma chamada em posição de cauda — o compilador emite, na chamada recursiva de iter, um salto direto (compile com ligação "return") sem nenhum save pendente: a pilha não cresce entre iterações. Compare com a fatorial recursiva do texto, cujo código objeto salva continue/env antes da chamada e multiplica na volta.
O código compilado da iterativa é, na prática, o laço da máquina de registradores do exercício 5.1 — teste, duas atualizações, salto — redescoberto mecanicamente pelo compilador a partir do fonte funcional. Processos iterativos compilam para iteração de verdade; é a recursão de cauda fechando o ciclo do livro.
Exercício 5.38
Que programa foi compilado para produzir o código mostrado na Figura 5.18?
Figura 5.18: Um exemplo de saída do compilador (continua na próxima página). Veja o exercício 5.38.
assign("val", list(op("make_compiled_function"),
label("entry1"), reg("env"))),
"entry1"
assign("env", list(op("compiled_function_env"), reg("fun"))),
assign("env", list(op("extend_environment"),
constant(list("x")), reg("argl"), reg("env"))),
revert_stack_to_marker(),
restore("continue"),
assign("fun", list(op("lookup_symbol_value"), constant("+"), reg("env"))),
save("continue"),
save("fun"),
save("env"),
assign("fun", list(op("lookup_symbol_value"), constant("g"), reg("env"))),
save("fun"),
assign("fun", list(op("lookup_symbol_value"), constant("+"), reg("env"))),
assign("val", constant(2)),
assign("argl", list(op("list"), reg("val"))),
assign("val", list(op("lookup_symbol_value"), constant("x"), reg("env"))),
assign("argl", list(op("pair"), reg("val"), reg("argl"))),
test(list(op("is_primitive_function"), reg("fun"))),
branch(label("primitive_branch3")),
"compiled_branch4"
assign("continue", label("after_call5")),
save("continue"),
push_marker_to_stack(),
assign("val", list(op("compiled_function_entry"), reg("fun"))),
go_to(reg("val")),
"primitive_branch3",
assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))),
"after_call5",
assign("argl", list(op("list"), reg("val"))),
restore("fun"),
test(list(op("is_primitive_function"), reg("fun"))),
branch(label("primitive_branch7")),
"compiled_branch8",
assign("continue", label("after_call9")),
save("continue"),
push_marker_to_stack(),
assign("val", list(op("compiled_function_entry"), reg("fun"))),
go_to(reg("val")),
"primitive_branch7",
assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))),
"after_call9",
assign("argl", list(op("list"), reg("val"))),
restore("env"),
assign("val", list(op("lookup_symbol_value"), constant("x"), reg("env"))),
assign("argl", list(op("pair"), reg("val"), reg("argl"))),
restore("fun"),
restore("continue"),
test(list(op("is_primitive_function"), reg("fun"))),
branch(label("primitive_branch11")),
(continuação)
"compiled_branch12",
save("continue"),
push_marker_to_stack(),
assign("val", list(op("compiled_function_entry"), reg("fun"))),
go_to(reg("val")),
"primitive_branch11",
assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))),
go_to(reg("continue")),
"after_call13",
"after_lambda2",
perform(list(op("assign_symbol_value"),
constant("f"), reg("val"), reg("env"))),
assign("val", constant(undefined))
💡 Mostrar solução — tente primeiro!💡 Esconder solução
Lendo a figura de trás para diante: o código monta uma função com dois parâmetros que, no corpo, testa x === 0? não — os acessos são lookup "x" e lookup "n"?… O método é o que importa: (1) identifique os lookup_symbol_value para descobrir os nomes envolvidos; (2) ache os testes (is_falsy) e o que cada ramo devolve; (3) reconstrua o condicional e as chamadas pelos save/restore e ligações de continue. O programa da figura 5.18 é a declaração recursiva
function f(x) {
return x === 0 ? 1 : x * f(x - 1);
}
— a fatorial com o nome trocado (f), reconhecível pelo literal 1 no ramo de base, pela multiplicação pendente após a chamada recursiva e pelo decremento do argumento na montagem de argl.
Exercício 5.39
Que ordem de avaliação nosso compilador produz para argumentos de uma aplicação? É da esquerda para a direita (como mandatado pela especificação ECMAScript), da direita para a esquerda, ou alguma outra ordem? Onde no compilador esta ordem é determinada? Modifique o compilador de modo que ele produza alguma outra ordem de avaliação. (Veja a discussão da ordem de avaliação para o avaliador de controle explícito na seção 5.4.) Como a mudança da ordem de avaliação de argumentos afeta a eficiência do código que constrói a lista de argumentos?
💡 Mostrar solução — tente primeiro!💡 Esconder solução
O compilador do texto gera a avaliação dos argumentos da direita para a esquerda: construct_arglist inverte a lista de códigos de operandos e vai fazendo pair do valor corrente com argl — o último operando é avaliado primeiro (assim argl é construída por pair sem inversão final).
Onde: em construct_arglist, na linha que faz reverse(operand_codes).
Para mudar para esquerda→direita: processe os códigos na ordem original acumulando em argl com um append no fim (argl ← append(argl, list(val))), ou construa como agora e acrescente uma inversão final de argl. O custo: ou um append linear por argumento (quadrático no total), ou uma reverse extra em tempo de execução por aplicação — a ordem direita→esquerda existe justamente porque pair constrói listas de trás para frente de graça. (O avaliador de controle explícito da seção 5.4 pagou o mesmo preço na outra moeda.) Para aderir à especificação ECMAScript, o preço da inversão final é o mais honesto.
Exercício 5.40
Uma forma de entender o mecanismo preserving do compilador para otimizar o uso da pilha é ver que operações extras seriam geradas se não usássemos essa ideia. Modifique preserving de modo que ele sempre gere as operações save e restore. Compile algumas expressões simples e identifique as operações de pilha desnecessárias que são geradas. Compare o código àquele gerado com o mecanismo preserving intacto.
💡 Mostrar solução — tente primeiro!💡 Esconder solução
Trocando preserving por uma versão que sempre embrulha:
function preserving(regs, seq1, seq2) {
return is_null(regs)
? append_instruction_sequences(seq1, seq2)
: preserving(tail(regs),
make_instruction_sequence(…,
append(list(save(head(regs))),
append(statements(seq1),
list(restore(head(regs)))))),
seq2);
}
Compilando f("x", "y") com isso: aparecem save("env")/restore("env") em volta da avaliação do nome f (que não toca env), save("argl") em volta de literais (que não tocam argl), save("fun")/restore("fun") em volta da montagem de argumentos constantes — meia dúzia de pares de operações de pilha para uma aplicação que, com o preserving inteligente, compila sem nenhuma. A comparação mostra o mecanismo pelo avesso: preserving não é uma otimização exótica, é só não pagar por proteção que ninguém pediu — as anotações de "registradores que modifica/precisa" de cada sequência são o que torna a decisão local e segura.
Exercício 5.41
Nosso compilador é inteligente sobre evitar operações de pilha desnecessárias, mas não é nada inteligente quando se trata de compilar chamadas às funções primitivas da linguagem em termos das operações primitivas fornecidas pela máquina. Por exemplo, considere quanto código é compilado para calcular a + 1: O código configura uma lista de argumentos em argl, coloca a função de adição primitiva (que encontra procurando o símbolo "+" no ambiente) em fun, e testa se a função é primitiva ou composta. O compilador sempre gera código para realizar o teste, assim como código para ramos primitivo e composto (apenas um dos quais será executado). Não mostramos a parte do controlador que implementa primitivas, mas presumimos que essas instruções fazem uso de operações aritméticas primitivas nos caminhos de dados da máquina. Considere quanto menos código seria gerado se o compilador pudesse fazer codificação aberta (open-code) de primitivas—isto é, se ele pudesse gerar código para usar diretamente essas operações primitivas da máquina. A expressão a + 1 poderia ser compilada em algo tão simples quanto:2
assign("val", list(op("lookup_symbol_value"), constant("a"), reg("env"))),
assign("val", list(op("+"), reg("val"), constant(1)))
Neste exercício estenderemos nosso compilador para suportar codificação aberta de primitivas selecionadas. Código de propósito especial será gerado para chamadas a essas funções primitivas ao invés do código geral de aplicação de função. Para suportar isso, aumentaremos nossa máquina com registradores de argumentos especiais arg1 e arg2. As operações aritméticas primitivas da máquina tomarão suas entradas de arg1 e arg2. Os resultados podem ser colocados em val, arg1 ou arg2.
O compilador deve ser capaz de reconhecer a aplicação de uma primitiva de código aberto no programa fonte. Aumentaremos o despacho no procedimento compile para reconhecer os nomes dessas primitivas além das formas sintáticas que ele atualmente reconhece. Para cada forma sintática nosso compilador tem um gerador de código. Neste exercício construiremos uma família de geradores de código para as primitivas de código aberto.
a. As primitivas de código aberto, ao contrário das formas sintáticas, todas precisam que suas expressões de argumento sejam avaliadas. Escreva um gerador de código spread_arguments para uso por todos os geradores de código de código aberto. A função spread_arguments deve tomar uma lista de expressões de argumento e compilar as expressões de argumento dadas direcionadas a registradores de argumentos sucessivos. Note que uma expressão de argumento pode conter uma chamada a uma primitiva de código aberto, então registradores de argumentos terão que ser preservados durante a avaliação da expressão de argumento.
b. Os operadores JavaScript ===, *, - e +, entre outros, são implementados na máquina de registradores como funções primitivas e são referidos no ambiente global com os símbolos "===", "*", "-" e "+". Em JavaScript, não é possível redeclarar esses nomes, porque eles não atendem às restrições sintáticas para nomes. Isso significa que é seguro fazer código aberto deles. Para cada uma das funções primitivas ===, *, - e +, escreva um gerador de código que tome uma aplicação com uma expressão de função que nomeia essa função, junto com um alvo e um descritor de ligação, e produza código para espalhar os argumentos nos registradores e então realizar a operação direcionada ao alvo dado com a ligação dada. Faça compile despachar para esses geradores de código.
c. Experimente seu novo compilador no exemplo de factorial. Compare o código resultante com o resultado produzido sem código aberto.
💡 Mostrar solução — tente primeiro!💡 Esconder solução
Codificação aberta das primitivas: um caso novo no compilador reconhece aplicações cujo operador é um dos operadores conhecidos (+, -, *, /, ===, …) e emite a operação de máquina diretamente:
// em compile, antes do caso geral de aplicação:
: is_operator_combination_open_codable(comp)
? compile_open_code(comp, target, linkage, env)
: …
function compile_open_code(comp, target, linkage) {
const a = compile(first_operand(comp), "arg1", "next");
const b = compile(second_operand(comp), "arg2", "next");
return end_with_linkage(linkage,
preserving(list("env"),
a,
preserving(list("arg1"),
b,
make_instruction_sequence(list("arg1", "arg2"), list(target),
list(assign(target,
list(op(operator_of(comp)),
reg("arg1"), reg("arg2"))))))));
}
a + 1 compila para dois assign e uma soma — sem argl, sem lookup de "+", sem teste primitiva/composta, sem desvios. A ressalva clássica: isso assume que + é a primitiva — se o programa do usuário redefinir + (possível com a variante do exercício 4.5), a codificação aberta fica incorreta; compiladores reais guardam essa otimização atrás da suposição (ou verificação) de que as primitivas não foram sombreadas.
[1] Porque o append_return_undefined em compile_lambda_body, o corpo na verdade consiste de uma sequência com duas instruções return. No entanto, a verificação de código morto em compile_@sequence parará após a compilação da primeira instrução return, então o corpo efetivamente consiste de apenas uma única instrução return.
[2] Usamos o mesmo símbolo + aqui para denotar tanto a função da linguagem fonte quanto a operação da máquina. Em geral não haverá uma correspondência um-para-um entre primitivas da linguagem fonte e primitivas da máquina.