4.1.7 Separando Análise Sintática da Execução
O avaliador implementado acima é simples, mas é muito ineficiente, porque a análise sintática de componentes é intercalada com sua execução. Assim, se um programa é executado muitas vezes, sua sintaxe é analisada muitas vezes. Considere, por exemplo, avaliar factorial(4) usando a seguinte definição de factorial:
function factorial(n) {
return n === 1
? 1
: factorial(n - 1) * n;
}
Cada vez que factorial é chamado, o avaliador deve determinar que o corpo é uma expressão condicional e extrair o predicado. Somente então ele pode avaliar o predicado e despachar com base em seu valor. Cada vez que avalia a expressão factorial(n - 1) * n, ou as subexpressões factorial(n - 1) e n - 1, o avaliador deve realizar a análise de caso em evaluate para determinar que a expressão é uma aplicação, e deve extrair sua expressão de função e expressões de argumento. Esta análise é cara. Realizá-la repetidamente é desperdiçador.
Podemos transformar o avaliador para ser significativamente mais eficiente organizando as coisas de modo que a análise sintática seja realizada apenas uma vez.1 Dividimos evaluate, que recebe um componente e um ambiente, em duas partes. A função analyze recebe apenas o componente. Ela realiza a análise sintática e retorna uma nova função, a função de execução, que encapsula o trabalho a ser feito na execução do componente analisado. A função de execução recebe um ambiente como seu argumento e completa a avaliação. Isso economiza trabalho porque analyze será chamado apenas uma vez em um componente, enquanto a função de execução pode ser chamada muitas vezes.
Com a separação em análise e execução, evaluate agora se torna:
function evaluate(component, env) {
return analyze(component)(env);
}
O resultado de chamar analyze é a função de execução a ser aplicada ao ambiente. A função analyze é a mesma análise de caso realizada pelo evaluate original da seção 4.1.1, exceto que as funções para as quais despachamos realizam apenas análise, não avaliação completa:
function analyze(component) {
return is_literal(component)
? analyze_literal(component)
: is_name(component)
? analyze_name(component)
: is_application(component)
? analyze_application(component)
: is_operator_combination(component)
? analyze(operator_combination_to_application(component))
: is_conditional(component)
? analyze_conditional(component)
: is_lambda_expression(component)
? analyze_lambda_expression(component)
: is_sequence(component)
? analyze_sequence(sequence_statements(component))
: is_block(component)
? analyze_block(component)
: is_return_statement(component)
? analyze_return_statement(component)
: is_function_declaration(component)
? analyze(function_decl_to_constant_decl(component))
: is_declaration(component)
? analyze_declaration(component)
: is_assignment(component)
? analyze_assignment(component)
: error(component, "unknown syntax -- analyze");
}
Aqui está a função de análise sintática mais simples, que trata expressões literais. Ela retorna uma função de execução que ignora seu argumento de ambiente e apenas retorna o valor do literal:
function analyze_literal(component) {
return env => literal_value(component);
}
Procurar o valor de um nome ainda deve ser feito na fase de execução, já que isso depende de conhecer o ambiente.2
function analyze_name(component) {
return env => lookup_symbol_value(symbol_of_name(component), env);
}
A função analyze_assignment também deve adiar a avaliação real da expressão de valor até a fase de execução:
function analyze_assignment(component) {
const symbol = assignment_symbol(component);
const value_function = analyze(assignment_value_expression(component));
return env => {
const value = value_function(env);
assign_symbol_value(symbol, value, env);
return value;
};
}
A função analyze_declaration é semelhante. Observe que procurar o valor do nome também deve ser adiado para a fase de execução, para tratamento de definições de funções recursivas e mutuamente recursivas:
function analyze_declaration(component) {
const symbol = declaration_symbol(component);
const value_function = analyze(declaration_value_expression(component));
return env => {
const value = value_function(env);
assign_symbol_value(symbol, value, env);
return undefined;
};
}
Para expressões condicionais, começamos analisando o predicado, consequente e alternativa. Podemos decidir qual avaliar na fase de execução:
function analyze_conditional(component) {
const pfun = analyze(conditional_predicate(component));
const cfun = analyze(conditional_consequent(component));
const afun = analyze(conditional_alternative(component));
return env => is_truthy(pfun(env)) ? cfun(env) : afun(env);
}
Analisar uma expressão lambda também alcança um ganho importante de eficiência: Analisamos o corpo da lambda apenas uma vez, mesmo que a função resultante seja aplicada muitas vezes.
function analyze_lambda_expression(component) {
const parameters = lambda_parameter_symbols(component);
const bfun = analyze(lambda_body(component));
return env => make_function(parameters, bfun, env);
}
A análise de uma sequência de declarações é mais envolvida.3 Cada declaração na sequência é analisada, produzindo uma função de execução. Essas funções de execução são combinadas para produzir uma função de execução que recebe um ambiente como argumento e executa sequencialmente as funções de execução individuais.
function analyze_sequence(stmts) {
function sequentially(fun1, fun2) {
return env => {
const fun1_val = fun1(env);
return is_return_value(fun1_val)
? fun1_val
: fun2(env);
};
}
function loop(first_fun, rest_funs) {
return is_null(rest_funs)
? first_fun
: loop(sequentially(first_fun, head(rest_funs)),
tail(rest_funs));
}
const funs = map(analyze, stmts);
return is_null(funs)
? env => undefined
: loop(head(funs), tail(funs));
}
Para analisar uma aplicação, analisamos a expressão de função e as expressões de argumento e construímos uma função de execução que chama a função de execução da expressão de função (para obter a função real a ser aplicada) e as funções de execução das expressões de argumento (para obter a lista de argumentos real). Passamos estes para execute_application, que é o análogo de apply na seção 4.1.1. A função execute_application difere de apply por chamar as funções de execução das partes da função (o corpo das funções compostas), em vez de chamar evaluate.
function analyze_application(component) {
const ffun = analyze(function_expression(component));
const afuns = map(analyze, arg_expressions(component));
return env => execute_application(ffun(env),
map(afun => afun(env), afuns));
}
function execute_application(fun, args) {
if (is_primitive_function(fun)) {
return apply_primitive_function(fun, args);
} else if (is_compound_function(fun)) {
const result = function_body(fun)(
extend_environment(
function_parameters(fun),
args,
function_environment(fun)));
return is_return_value(result)
? return_value_content(result)
: undefined;
} else {
error(fun, "unknown function type -- execute_application");
}
}
Para blocos, analisamos o corpo e criamos uma função que estende o ambiente apropriadamente quando executada:
function analyze_block(component) {
const body = block_body(component);
const bfun = analyze(body);
const locals = scan_out_declarations(body);
const unassigneds = list_of_unassigned(locals);
return env => bfun(extend_environment(locals, unassigneds, env));
}
Para declarações de retorno, analisamos a expressão de retorno e aplicamos make_return_value ao resultado na fase de execução:
function analyze_return_statement(component) {
const rfun = analyze(return_expression(component));
return env => make_return_value(rfun(env));
}
Nosso novo avaliador usa as mesmas estruturas de dados, funções de sintaxe e operações de execução da seção 4.1.2, 4.1.3 e 4.1.4.
Exercício 4.20
Estenda o avaliador de análise sintática nesta seção para suportar a forma sintática especial derivada let (do exercício 4.6).
💡 Mostrar solução — tente primeiro!💡 Esconder solução
Como let é uma forma derivada, o avaliador de análise só precisa transformar antes de analisar — o caso novo em analyze delega para a análise da tradução:
function analyze(component) {
return …
: is_let(component)
? analyze(let_to_application(component))
: …;
}
onde let_to_application é a mesma transformação do avaliador original (o let vira a aplicação imediata de uma lambda aos inicializadores). O trabalho de tradução acontece uma única vez, na análise — nas execuções seguintes roda direto a função de execução da aplicação, que é o ponto da seção.
Exercício 4.21
Alyssa P. Hacker não entende por que analyze_sequence precisa ser tão complicada. Tudo o que outras funções de análise fazem é analisar seus componentes e retornar uma função de execução. Ela o reescreve como:
function analyze_sequence(stmts) {
function execute_sequence(funs, env) {
if (is_null(funs)) {
return undefined;
} else if (is_null(tail(funs))) {
return head(funs)(env);
} else {
const head_val = head(funs)(env);
return is_return_value(head_val)
? head_val
: execute_sequence(tail(funs), env);
}
}
const funs = map(analyze, stmts);
return env => execute_sequence(funs, env);
}
Eva Lu Ator explica a Alyssa que a versão no texto faz mais da análise na fase de análise. O programa de Alyssa faz trabalho extra na fase de execução, todo ele sem qualquer ganho em eficiência.
Compare as duas versões de analyze_sequence. Por exemplo, considere o caso comum (típico de corpos de função) onde a sequência tem apenas uma declaração. Que trabalho a função de execução produzida pelo programa de Alyssa fará? E quanto à função de execução produzida pelo programa no texto acima? Como as duas versões se comparam para uma sequência com duas expressões?
💡 Mostrar solução — tente primeiro!💡 Esconder solução
As duas versões produzem os mesmos resultados; a diferença é quanto trabalho sobra para a execução.
Na versão do texto, analyze_sequence combina as funções de execução durante a análise: uma sequência de duas declarações vira uma única função env => { f1(env); return f2(env); }, construída uma vez. Executá-la é só chamar funções já costuradas.
Na versão de Alyssa, a análise devolve uma função que, a cada execução, percorre a lista das funções analisadas (execute_sequence itera sobre funs com testes de is_null, head, tail). A análise ficou mais simples exatamente porque parte do trabalho — o percurso e o encadeamento da sequência — foi adiada para o tempo de execução, e é paga de novo em toda chamada.
Para uma sequência dentro de uma função chamada em um laço, a versão do texto percorre a lista uma vez (na análise); a de Alyssa a percorre uma vez por chamada. É a distinção do capítulo inteiro em miniatura: análise é o que você paga uma vez; execução é o que você paga sempre.
Exercício 4.22
Projete e realize alguns experimentos para comparar a velocidade do avaliador metacircular original com a versão nesta seção. Use seus resultados para estimar a fração de tempo que é gasto em análise versus execução para várias funções.
💡 Mostrar solução — tente primeiro!💡 Esconder solução
Um experimento honesto compara os dois avaliadores sobre o mesmo programa, variando a razão análise/execução:
- Programas ricos em reexecução —
fib(20)recursivo, um laço executado milhares de vezes: o corpo é analisado uma vez e executado milhões; o avaliador com análise costuma ficar várias vezes mais rápido (fatores de 2× a 10× são típicos), porque o original re-desmonta a sintaxe do corpo a cada chamada. - Programas de execução única — uma sequência longa de declarações simples rodada uma vez: os dois empatam, ou o de análise perde por uma margem pequena (paga a construção das funções de execução sem amortizá-la).
Estimando a fração análise/execução: meça (original) e (com análise) para um programa com grande de reexecuções. No original, cada execução carrega o custo de análise embutido; com análise, ele quase some. A fração do tempo original gasta em análise é aproximadamente — para funções recursivas pequenas como fib, tipicamente na casa de metade ou mais do tempo total, o que explica por que a separação análise/execução foi um passo tão importante rumo à compilação (capítulo 5).
📝 Encontrou algo errado nesta página?
Sua ajuda é muito importante para melhorar a qualidade da tradução!
🐛 Encontrou um erro?
Se você encontrou:
- Erro de tradução (palavra incorreta, termo técnico errado)
- Erro de ortografia ou gramática
- Link quebrado
- Código de exemplo que não funciona
- Problema de formatação
❓ Tem uma dúvida?
Se você tem:
- Dúvida sobre o conteúdo desta seção
- Pergunta sobre um conceito do SICP
- Dificuldade em entender algum exemplo
- Questão sobre a tradução de algum termo
💡 Tem uma sugestão de melhoria?
Se você quer sugerir:
- Melhoria na explicação
- Exemplo adicional
- Recurso visual (diagrama, ilustração)
- Qualquer outra ideia
🌍 Quer discutir a tradução?
Se você quer debater:
- Escolha de tradução de algum termo
- Consistência de terminologia
- Nuances do português
Obrigado por ajudar a melhorar o SICP.js PT-BR! ✨