5.5.6 Análise Léxica
Uma das otimizações mais comuns realizadas por compiladores é a otimização de busca de nomes. Nosso compilador, como o implementamos até agora, gera código que usa a operação lookup_symbol_value da máquina avaliadora. Isso busca um nome comparando-o com cada nome que está atualmente ligado, trabalhando quadro por quadro para fora através do ambiente de tempo de execução. Esta busca pode ser cara se os quadros estiverem profundamente aninhados ou se houver muitos nomes. Por exemplo, considere o problema de procurar o valor de x ao avaliar a expressão x * y * z em uma aplicação da função de cinco argumentos que é retornada por:
((x, y) =>
(a, b, c, d, e) =>
((y, z) => x * y * z)(a * b * x, c + d + x))(3, 4)
Cada vez que lookup_symbol_value busca x, ela deve determinar que o símbolo "x" não é igual a "y" ou "z" (no primeiro quadro), nem a "a", "b", "c", "d", ou "e" (no segundo quadro). Porque nossa linguagem é lexicamente escopo, o ambiente de tempo de execução para qualquer componente terá uma estrutura que é paralela à estrutura léxica do programa no qual o componente aparece. Assim, o compilador pode saber, quando ele analisa a expressão acima, que cada vez que a função é aplicada a ligação para x em x * y * z será encontrada dois quadros para fora do quadro atual e será a primeira ligação naquele quadro.
Podemos explorar este fato inventando um novo tipo de operação de busca de nome, lexical_address_lookup, que toma como argumentos um ambiente e um endereço léxico que consiste de dois números: um número de quadro, que especifica quantos quadros passar, e um número de deslocamento, que especifica quantas ligações passar naquele quadro. A operação lexical_address_lookup produzirá o valor do nome armazenado naquele endereço léxico em relação ao ambiente atual. Se adicionarmos a operação lexical_address_lookup à nossa máquina, podemos fazer o compilador gerar código que referencia nomes usando esta operação, ao invés de lookup_symbol_value. Da mesma forma, nosso código compilado pode usar uma nova operação lexical_address_assign ao invés de assign_symbol_value. Com endereçamento léxico, não há necessidade de incluir quaisquer referências simbólicas a nomes no código objeto, e quadros não precisam incluir símbolos em tempo de execução.
Para gerar tal código, o compilador deve ser capaz de determinar o endereço léxico de um nome sobre o qual ele está prestes a compilar uma referência. O endereço léxico de um nome em um programa depende de onde se está no código. Por exemplo, no programa seguinte, o endereço de x na expressão e₁ é (2,0)—dois quadros atrás e a primeira variável no quadro. Naquele ponto y está no endereço (0,0) e c está no endereço (1,2). Na expressão e₂, x está em (1,0), y está em (1,1), e c está em (0,2).
((x, y) =>
(a, b, c, d, e) =>
((y, z) => e₁)(e₂, c + d + x))(3, 4);
Uma forma do compilador produzir código que usa endereçamento léxico é manter uma estrutura de dados chamada ambiente de tempo de compilação. Isso mantém o controle de quais ligações estarão em quais posições em quais quadros no ambiente de tempo de execução quando uma particular operação de acesso ao nome for executada. O ambiente de tempo de compilação é uma lista de quadros, cada um contendo uma lista de símbolos. Não haverá valores associados aos símbolos, já que valores não são computados em tempo de compilação. (O exercício 5.47 mudará isso, como uma otimização para constantes.) O ambiente de tempo de compilação torna-se um argumento adicional para compile e é passado adiante para cada gerador de código. A chamada de nível superior a compile usa um ambiente de tempo de compilação que inclui os nomes de todas as funções e valores primitivos. Quando o corpo de uma expressão lambda é compilado, compile_lambda_body estende o ambiente de tempo de compilação por um quadro contendo os parâmetros da função, de modo que o corpo seja compilado com aquele ambiente estendido. Similarmente, quando o corpo de um bloco é compilado, compile_block estende o ambiente de tempo de compilação por um quadro contendo os nomes locais escaneados do corpo. Em cada ponto na compilação, compile_name e compile_assignment_declaration usam o ambiente de tempo de compilação para gerar os endereços léxicos apropriados.
Os exercícios 5.45 a 5.45 descrevem como completar este esboço da estratégia de endereçamento léxico para incorporar busca léxica no compilador. Os exercícios 5.47 e 5.46 descrevem outros usos para o ambiente de tempo de compilação.
Exercício 5.42
Escreva uma função lexical_address_lookup que implementa a nova operação de busca. Ela deve tomar dois argumentos—um endereço léxico e um ambiente de tempo de execução—e retornar o valor do nome armazenado no endereço léxico especificado. A função lexical_address_lookup deve sinalizar um erro se o valor do nome for a string "*unassigned*". Também escreva uma função lexical_address_assign que implementa a operação que muda o valor do nome em um endereço léxico especificado.
💡 Mostrar solução — tente primeiro!💡 Esconder solução
function lexical_address_lookup(address, env) {
const frame = list_ref(env, frame_index(address));
const value = list_ref(frame_values(frame),
displacement_index(address));
return value === "*unassigned*"
? error(address, "nome não atribuído -- lexical_address_lookup")
: value;
}
function lexical_address_assign(address, value, env) {
const frame = list_ref(env, frame_index(address));
set_element(frame_values(frame),
displacement_index(address),
value);
}
O endereço léxico (f, d) dispensa qualquer busca por nome: f saltos de frame, d posições dentro dele — dois list_refs cegos, exatamente o que torna a operação compilável em aritmética de ponteiros numa máquina real. O teste de "*unassigned*" preserva a detecção da zona morta temporal do exercício 4.16, agora no acesso posicional.
Exercício 5.43
Modifique o compilador para manter o ambiente de tempo de compilação como descrito acima. Ou seja, adicione um argumento de ambiente de tempo de compilação a compile e aos vários geradores de código, e estenda-o em compile_lambda_body e compile_block.
💡 Mostrar solução — tente primeiro!💡 Esconder solução
Mudança mecânica e disciplinada: compile(component, target, linkage) vira compile(component, target, linkage, comp_env), e cada gerador repassa o ambiente adiante. Os dois pontos que estendem:
// compile_lambda_body: parâmetros + locais varridos entram como frame novo
const extended = pair(append(parameters(exp),
scan_out_declarations(body)),
comp_env);
… compile(body, "val", "return", extended) …
// compile_block: os declarados do bloco formam o frame
const extended = pair(scan_out_declarations(block_body(stmt)), comp_env);
Todos os demais geradores apenas conduzem comp_env intacto. O ambiente de tempo de compilação é a sombra estática do ambiente de execução: cresce nos mesmos pontos, mas carrega só os nomes — o suficiente para o exercício 5.44 calcular endereços.
Exercício 5.44
Escreva uma função find_symbol que toma como argumentos um símbolo e um ambiente de tempo de compilação e retorna o endereço léxico do símbolo com respeito àquele ambiente. Por exemplo, no fragmento de programa mostrado acima, o ambiente de tempo de compilação durante a compilação da expressão e₁ é:
list(list("y", "z"),
list("a", "b", "c", "d", "e"),
list("x", "y"))
A função find_symbol deve produzir:
find_symbol("c", list(list("y", "z"),
list("a", "b", "c", "d", "e"),
list("x", "y")));
Resultado:
list(1, 2)
find_symbol("x", list(list("y", "z"),
list("a", "b", "c", "d", "e"),
list("x", "y")));
Resultado:
list(2, 0)
find_symbol("w", list(list("y", "z"),
list("a", "b", "c", "d", "e"),
list("x", "y")));
Resultado:
"not found"
💡 Mostrar solução — tente primeiro!💡 Esconder solução
function find_symbol(symbol, comp_env) {
function scan_frame(symbols, displacement) {
return is_null(symbols)
? "not found in frame"
: head(symbols) === symbol
? displacement
: scan_frame(tail(symbols), displacement + 1);
}
function scan_env(env, frame_no) {
if (is_null(env)) {
return "not found";
}
const d = scan_frame(head(env), 0);
return d === "not found in frame"
? scan_env(tail(env), frame_no + 1)
: make_lexical_address(frame_no, d);
}
return scan_env(comp_env, 0);
}
A busca é a mesma que lookup_symbol_value faria em execução — só que sobre a sombra estática, uma vez, em tempo de compilação. No exemplo do texto, find_symbol("y", env) devolve o endereço (frame 1, posição 0): y está um contorno acima, primeira posição.
Exercício 5.45
Usando find_symbol do exercício 5.44, reescreva compile_assignment_declaration e compile_name para produzir instruções de endereço léxico. Em casos onde find_symbol retorna "not found" (ou seja, onde o nome não está no ambiente de tempo de compilação), você deve reportar um erro de tempo de compilação. Teste o compilador modificado em alguns casos simples, como a combinação lambda aninhada no início desta seção.
💡 Mostrar solução — tente primeiro!💡 Esconder solução
compile_name troca a busca por símbolo pelo acesso posicional:
function compile_name(exp, target, linkage, comp_env) {
const address = find_symbol(symbol_of_name(exp), comp_env);
return address === "not found"
? error(exp, "nome não declarado -- compile") // erro de COMPILAÇÃO
: end_with_linkage(linkage,
make_instruction_sequence(list("env"), list(target),
list(assign(target,
list(op("lexical_address_lookup"),
constant(address), reg("env"))))));
}
e compile_assignment_declaration faz o simétrico com lexical_address_assign. Duas consequências dignas de nota: (1) nomes inexistentes deixam de ser um erro de execução e viram erro de compilação — a classe inteira de ReferenceError morre antes de o programa rodar; (2) o registrador de ambiente continua necessário, mas os símbolos desaparecem do código objeto — no lambda aninhado do início da seção, cada acesso vira um par de inteiros.
Exercício 5.46
Em JavaScript, uma tentativa de atribuir um novo valor a um nome que é declarado como uma constante leva a um erro. O exercício 4.16 mostra como detectar tais erros em tempo de execução. Com as técnicas apresentadas nesta seção, podemos detectar tentativas de atribuir um novo valor a uma constante em tempo de compilação. Para este propósito, estenda as funções compile_lambda_body e compile_block para registrar no ambiente de tempo de compilação se um nome é declarado como uma variável (usando let ou como um parâmetro), ou como uma constante (usando const ou function). Modifique compile_assignment para reportar um erro apropriado quando detectar uma atribuição a uma constante.
💡 Mostrar solução — tente primeiro!💡 Esconder solução
O ambiente de tempo de compilação passa a guardar pares (nome, tipo-de-declaração):
// compile_lambda_body / compile_block:
// parâmetros → "variable"
// declarações let → "variable"
// declarações const → "constant"
// declarações function → "constant"
find_symbol devolve, junto com o endereço, o tipo registrado; compile_assignment consulta:
const kind = declaration_kind(symbol, comp_env);
return kind === "constant"
? error(symbol, "atribuição a constante -- compile")
: … código normal de lexical_address_assign …;
O erro que o exercício 4.16 pegava com "*unassigned*"-e-teste em execução agora nem chega a gerar código: é rejeitado na compilação, com a linha exata. É o mesmo movimento do 5.48 — transformar disciplina dinâmica em fato estático — aplicado à imutabilidade.
Exercício 5.47
O conhecimento sobre constantes em tempo de compilação abre a porta para muitas otimizações que nos permitem gerar código objeto mais eficiente. Além da extensão do ambiente de tempo de compilação no exercício 5.46 para indicar nomes declarados como constantes, podemos armazenar o valor de uma constante se ele for conhecido em tempo de compilação, ou outras informações que podem nos ajudar a otimizar o código.
a. Uma declaração constante como const nome = literal; nos permite substituir todas as ocorrências de nome dentro do escopo da declaração por literal de modo que nome não tenha que ser procurado no ambiente de tempo de execução. Esta otimização é chamada propagação de constantes. Use um ambiente de tempo de compilação estendido para armazenar constantes literais, e modifique compile_name para usar a constante armazenada na instrução assign gerada ao invés da operação lookup_symbol_value.
b. Declaração de função é um componente derivado que se expande para declaração constante. Vamos assumir que os nomes de funções primitivas no ambiente global também são considerados constantes. Se estendermos ainda mais nosso ambiente de tempo de compilação para manter o controle de quais nomes se referem a funções compiladas e quais a funções primitivas, podemos mover o teste que verifica se uma função é compilada ou primitiva do tempo de execução para o tempo de compilação. Isso torna o código objeto mais eficiente porque ele substitui um teste que deve ser realizado uma vez por aplicação de função no código gerado por um que é realizado pelo compilador. Usando tal ambiente de tempo de compilação estendido, modifique compile_function_call de modo que se puder ser determinado em tempo de compilação se a função chamada é compilada ou primitiva, somente as instruções em compiled_branch ou primitive_branch sejam geradas.
c. Substituir nomes constantes por seus valores literais como na parte (a) abre caminho para outra otimização, a saber, substituir aplicações de funções primitivas a valores literais com o resultado computado em tempo de compilação. Esta otimização, chamada dobramento de constantes (constant folding), substitui expressões como 40 + 2 por 42 realizando a adição no compilador. Estenda o compilador para realizar dobramento de constantes para operações aritméticas em números e para concatenação de strings.
💡 Mostrar solução — tente primeiro!💡 Esconder solução
a. Propagação de constantes: quando compile_block/compile_lambda_body registram const nome = literal;, guardam também o literal; compile_name verifica:
const info = find_symbol_info(symbol, comp_env);
return has_known_value(info)
? end_with_linkage(linkage,
make_instruction_sequence(null, list(target),
list(assign(target, constant(known_value(info))))))
: … lexical_address_lookup como antes …;
O acesso vira uma carga imediata — nem ambiente é preciso.
b. Dobra de constantes (constant folding): com a propagação instalada, operações abertas (exercício 5.41) cujos operandos são constantes conhecidas podem ser avaliadas pelo compilador: compile_open_code testa se ambos os lados têm valor conhecido e, em caso positivo, emite assign(target, constant(resultado)) — 2 * 3 no fonte não gera multiplicação nenhuma no objeto.
A cadeia completa 5.44 → 5.49 → 5.50 é o embrião de um otimizador de verdade: conhecer o que não muda em tempo de compilação converte trabalho de execução em trabalho feito uma única vez — o tema do capítulo, levado à conclusão.