4.1.3 Estruturas de Dados do Avaliador
Além de definir a representação de componentes, a implementação do avaliador também deve definir as estruturas de dados que o avaliador manipula internamente, como parte da execução de um programa, como a representação de funções e ambientes e a representa ção de verdadeiro e falso.
Teste de predicados
Para limitar as expressões de predicado de condicionais a predicados adequados (expressões que avaliam para um valor booleano) como fazemos ao longo deste livro, insistimos aqui que a função is_truthy seja aplicada apenas a valores booleanos, e aceitamos apenas o valor booleano true como verdadeiro. O oposto de is_truthy é chamado is_falsy.1
function is_truthy(x) {
return is_boolean(x)
? x
: error(x, "boolean expected, received");
}
function is_falsy(x) { return ! is_truthy(x); }
Representando funções
Para lidar com primitivos, assumimos que temos disponíveis as seguintes funções:
apply_primitive_function(fun,args)aplica a função primitiva dada aos valores de argumento na lista args e retorna o resultado da aplicação.is_primitive_function(fun)testa se fun é uma função primitiva.
Esses mecanismos para lidar com primitivos são descritos mais adiante na seção 4.1.4.
Funções compostas são construídas a partir de parâmetros, corpos de função e ambientes usando o construtor make_function:
function make_function(parameters, body, env) {
return list("compound_function", parameters, body, env);
}
function is_compound_function(f) {
return is_tagged_list(f, "compound_function");
}
function function_parameters(f) { return list_ref(f, 1); }
function function_body(f) { return list_ref(f, 2); }
function function_environment(f) { return list_ref(f, 3); }
Representando valores de retorno
Vimos na seção 4.1.1 que a avaliação de uma sequência termina quando uma declaração de retorno é encontrada, e que a avaliação de uma aplicação de função precisa retornar o valor undefined se a avaliação do corpo da função não encontrar uma declaração de retorno. Para reconhecer que um valor resultou de uma declaração de retorno, introduzimos valores de retorno como estruturas de dados do avaliador.
function make_return_value(content) {
return list("return_value", content);
}
function is_return_value(value) {
return is_tagged_list(value, "return_value");
}
function return_value_content(value) {
return head(tail(value));
}
Operações sobre ambientes
O avaliador precisa de operações para manipular ambientes. Como explicado na seção 3.2, um ambiente é uma sequência de frames, onde cada frame é uma tabela de vinculações que associam símbolos com seus valores correspondentes. Usamos as seguintes operações para manipular ambientes:
lookup_symbol_value(symbol,env)retorna o valor que está vinculado a symbol no ambiente env, ou sinaliza um erro se symbol estiver não vinculado.extend_environment(symbols,values,base-env)retorna um novo ambiente, consistindo de um novo frame no qual os símbolos na lista symbols estão vinculados aos elementos correspondentes na lista values, onde o ambiente envolvente é o ambiente base-env.assign_symbol_value(symbol,value,env)encontra o frame mais interno de env no qual symbol está vinculado, e muda esse frame de modo que symbol agora esteja vinculado a value, ou sinaliza um erro se symbol estiver não vinculado.
Para implementar essas operações, representamos um ambiente como uma lista de frames. O ambiente envolvente de um ambiente é o tail da lista. O ambiente vazio é simplesmente a lista vazia.
function enclosing_environment(env) { return tail(env); }
function first_frame(env) { return head(env); }
const the_empty_environment = null;
Cada frame de um ambiente é representado como um par de listas: uma lista dos nomes vinculados naquele frame e uma lista dos valores associados.2
function make_frame(symbols, values) { return pair(symbols, values); }
function frame_symbols(frame) { return head(frame); }
function frame_values(frame) { return tail(frame); }
Para estender um ambiente por um novo frame que associa símbolos com valores, fazemos um frame consistindo da lista de símbolos e da lista de valores, e juntamos isso ao ambiente. Sinalizamos um erro se o número de símbolos não corresponder ao número de valores.
function extend_environment(symbols, vals, base_env) {
return length(symbols) === length(vals)
? pair(make_frame(symbols, vals), base_env)
: error(pair(symbols, vals),
length(symbols) < length(vals)
? "too many arguments supplied"
: "too few arguments supplied");
}
Isso é usado por apply na seção 4.1.1 para vincular os parâmetros de uma função aos seus argumentos.
Para procurar um símbolo em um ambiente, varremos a lista de símbolos no primeiro frame. Se encontrarmos o símbolo desejado, retornamos o elemento correspondente na lista de valores. Se não encontrarmos o símbolo no frame atual, pesquisamos o ambiente envolvente, e assim por diante. Se alcançarmos o ambiente vazio, sinalizamos um erro de "unbound name".
function lookup_symbol_value(symbol, env) {
function env_loop(env) {
function scan(symbols, vals) {
return is_null(symbols)
? env_loop(enclosing_environment(env))
: symbol === head(symbols)
? head(vals)
: scan(tail(symbols), tail(vals));
}
if (env === the_empty_environment) {
error(symbol, "unbound name");
} else {
const frame = first_frame(env);
return scan(frame_symbols(frame), frame_values(frame));
}
}
return env_loop(env);
}
Para atribuir um novo valor a um símbolo em um ambiente especificado, varremos o símbolo, assim como em lookup_symbol_value, e mudamos o valor correspondente quando o encontramos.
function assign_symbol_value(symbol, val, env) {
function env_loop(env) {
function scan(symbols, vals) {
return is_null(symbols)
? env_loop(enclosing_environment(env))
: symbol === head(symbols)
? set_head(vals, val)
: scan(tail(symbols), tail(vals));
}
if (env === the_empty_environment) {
error(symbol, "unbound name -- assignment");
} else {
const frame = first_frame(env);
return scan(frame_symbols(frame), frame_values(frame));
}
}
return env_loop(env);
}
O método descrito aqui é apenas uma das muitas maneiras plausíveis de representar ambientes. Como usamos abstração de dados para isolar o resto do avaliador da escolha detalhada de representação, poderíamos mudar a representação de ambiente se quiséssemos. (Veja o exercício 4.9.) Em um sistema JavaScript de qualidade de produção, a velocidade das operações de ambiente do avaliador — especialmente a de busca de símbolos — tem um grande impacto no desempenho do sistema. A representação descrita aqui, embora conceitualmente simples, não é eficiente e não seria ordinariamente usada em um sistema de produção.3
Exercício 4.9
Em vez de representar um frame como um par de listas, podemos representar um frame como uma lista de vinculações, onde cada vinculação é um par símbolo-valor. Reescreva as operações de ambiente para usar esta representação alternativa.
💡 Mostrar solução — tente primeiro!💡 Esconder solução
Um frame vira uma lista de pares símbolo-valor, e as quatro operações mudam juntas — o resto do avaliador nem percebe:
function make_frame(symbols, values) {
return is_null(symbols)
? null
: pair(pair(head(symbols), head(values)),
make_frame(tail(symbols), tail(values)));
}
function add_binding_to_frame(symbol, value, frame) {
// um frame agora é uma lista mutável de vinculações
set_tail(frame, pair(head(frame), tail(frame)));
set_head(frame, pair(symbol, value));
}
function frame_lookup(symbol, frame) {
return is_null(frame)
? null
: head(head(frame)) === symbol
? head(frame) // devolve a vinculação (par)
: frame_lookup(symbol, tail(frame));
}
lookup_symbol_value e assign_symbol_value percorrem os frames chamando frame_lookup; ao encontrar a vinculação, leem (tail(binding)) ou escrevem (set_tail(binding, val)) nela.
Por que funciona: a representação original mantém duas listas paralelas (símbolos e valores) que precisam ser percorridas em sincronia; a lista de vinculações guarda cada par junto, então achar o símbolo é achar o valor. A abstração de dados fez seu trabalho: só make_frame, add_binding_to_frame e as buscas conhecem o formato.
Armadilha: add_binding_to_frame num frame vazio (null) não tem par para mutar — trate o frame vazio como caso especial em extend_environment (crie a lista diretamente) ou represente todo frame com uma cabeça sentinela.
Exercício 4.10
As funções lookup_symbol_value e assign_symbol_value podem ser expressas em termos de uma função mais abstrata para percorrer a estrutura de ambiente. Defina uma abstração que capture o padrão comum e redefina as duas funções em termos desta abstração.
💡 Mostrar solução — tente primeiro!💡 Esconder solução
O padrão comum: descer os frames do ambiente, procurar o símbolo no frame, agir sobre a vinculação se achar, subir para o ambiente envolvente se não. A abstração recebe o que fazer em cada desfecho:
function traverse_environment(symbol, env, found, not_found_in_env) {
function env_loop(env) {
function scan(symbols, vals) {
return is_null(symbols)
? env_loop(enclosing_environment(env))
: symbol === head(symbols)
? found(vals)
: scan(tail(symbols), tail(vals));
}
if (env === the_empty_environment) {
return not_found_in_env();
} else {
const frame = first_frame(env);
return scan(frame_symbols(frame), frame_values(frame));
}
}
return env_loop(env);
}
function lookup_symbol_value(symbol, env) {
return traverse_environment(symbol, env,
vals => head(vals),
() => error(symbol, "unbound name"));
}
function assign_symbol_value(symbol, val, env) {
return traverse_environment(symbol, env,
vals => { set_head(vals, val); },
() => error(symbol, "unbound name -- assignment"));
}
Por que funciona: as duas funções diferiam apenas no que fazem na célula encontrada (ler vs. mutar) e na mensagem de erro. Passar essas duas decisões como funções (found, not_found_in_env) fatora o percurso — o mesmo movimento de accumulate no capítulo 2, aplicado à estrutura de ambientes.
Exercício 4.11
Nossa linguagem distingue constantes de variáveis usando diferentes palavras-chave — const e let — e previne atribuição a constantes. No entanto, nosso interpretador não faz uso desta distinção; a função assign_symbol_value alegremente atribuirá um novo valor a um dado símbolo, independentemente de ter sido declarado como uma constante ou uma variável. Corrija essa falha chamando a função error sempre que uma tentativa for feita de usar uma constante no lado esquerdo de uma atribuição. Você pode proceder da seguinte forma:
- Introduza predicados
is_constant_declarationeis_variable_declarationque permitam distinguir os dois tipos. Como mostrado na seção 4.1.2,parseos distingue usando as tags"constant_declaration"e"variable_declaration". - Mude
scan_out_declarationse (se necessário)extend_environmentde modo que constantes sejam distinguíveis de variáveis nos frames nos quais elas são vinculadas. - Mude
assign_symbol_valuede modo que ela verifique se o dado símbolo foi declarado como uma variável ou como uma constante, e no último caso sinalize um erro de que operações de atribuição não são permitidas em constantes. - Mude
eval_declarationde modo que quando ela encontrar uma declaração de constante, ela chame uma nova função,assign_constant_value, que não realiza a verificação que você introduziu emassign_symbol_value. - Se necessário, mude
applypara garantir que atribuição a parâmetros de função permaneça possível.
💡 Mostrar solução — tente primeiro!💡 Esconder solução
A ideia central: guardar, junto de cada valor, como o nome foi declarado — e consultar essa marca na atribuição.
function is_constant_declaration(component) {
return is_tagged_list(component, "constant_declaration");
}
function is_variable_declaration(component) {
return is_tagged_list(component, "variable_declaration");
}
Em scan_out_declarations, em vez de devolver só os símbolos, devolva pares (símbolo, é-constante?); extend_environment guarda o valor embrulhado: pair(valor, é_constante). Então:
function assign_symbol_value(symbol, val, env) {
// ... encontra a célula c ...
if (tail(head(vals))) { // marcada como constante
error(symbol, "assignment to constant not allowed");
} else {
set_head(head(vals), val);
}
}
function assign_constant_value(symbol, val, env) {
set_head(head(vals), val); // sem verificação
}
eval_declaration despacha: declarações de constante inicializam via assign_constant_value (afinal, a primeira escrita numa constante é legítima — é a inicialização que substitui o "*unassigned*"); as demais atribuições passam pela verificação.
Por que apply precisa de atenção: parâmetros de função são variáveis (atribuíveis). Ao construir o frame dos parâmetros em apply, marque-os como variáveis — senão a mudança quebraria todo programa que atribui a um parâmetro.
Exercício 4.12
- A especificação do JavaScript requer que uma implementação sinalize um erro de tempo de execução ao tentar acessar o valor de um nome antes que sua declaração seja avaliada (veja o final da seção 3.2.4). Para alcançar este comportamento no avaliador, mude
lookup_symbol_valuepara sinalizar um erro se o valor que ela encontrar for"*unassigned*". - Similarmente, não devemos atribuir um novo valor a uma variável se ainda não avaliamos sua declaração
let. Mude a avaliação de atribuição de modo que atribuição a uma variável declarada comletsinalize um erro neste caso.
💡 Mostrar solução — tente primeiro!💡 Esconder solução
As duas partes são o mesmo teste em dois lugares:
// 1. acesso antes da declaração
function lookup_symbol_value(symbol, env) {
// ... encontra o valor val ...
return val === "*unassigned*"
? error(symbol, "name used before declaration")
: val;
}
// 2. atribuição antes da declaração let
function assign_symbol_value(symbol, val, env) {
// ... encontra a célula ...
if (head(vals) === "*unassigned*") {
error(symbol, "assignment to name before declaration");
} else {
set_head(vals, val);
}
}
Por que funciona: o placeholder "*unassigned*" que eval_block instala ao "içar" as declarações é exatamente a evidência de que a declaração ainda não foi avaliada — a temporal dead zone do JavaScript real, reconstruída no interpretador. O erro na leitura implementa o que a seção 3.2.4 prometeu; o erro na escrita fecha a outra metade da janela.
Armadilha: a verificação da parte 2 não pode valer para eval_declaration em si — a inicialização da declaração é justamente a escrita que substitui o placeholder (use um caminho sem verificação, como o assign_constant_value do exercício 4.11).
Exercício 4.13
Antes do modo estrito do ECMAScript 2015 que estamos usando neste livro, as variáveis JavaScript funcionavam de forma bastante diferente das variáveis Scheme, o que teria tornado esta adaptação para JavaScript consideravelmente menos convincente.
- Antes do ECMAScript 2015, a única maneira de declarar uma variável local em JavaScript era usando a palavra-chave
varem vez da palavra-chavelet. O escopo de variáveis declaradas comvaré o corpo inteiro da declaração de função ou expressão lambda imediatamente envolvente, em vez de apenas o bloco imediatamente envolvente. Modifiquescan_out_declarationseeval_blockde modo que nomes declarados comconsteletsigam as regras de escopo devar. - Quando não em modo estrito, JavaScript permite que nomes não declarados apareçam à esquerda do
=em atribuições. Tal atribuição adiciona a nova vinculação ao ambiente global. Modifique a funçãoassign_symbol_valuepara fazer a atribuição se comportar desta maneira. O modo estrito, que proíbe tais atribuições, foi introduzido em JavaScript para tornar programas mais seguros. Que questão de segurança é abordada ao prevenir que atribuição adicione vinculações ao ambiente global?
💡 Mostrar solução — tente primeiro!💡 Esconder solução
Parte 1 — escopo de função (var): hoje, eval_block chama scan_out_declarations no bloco e estende o ambiente com um frame por bloco. Para simular var, blocos comuns deixam de criar frame: quem varre é a aplicação de função — apply percorre o corpo inteiro (recursivamente, entrando em blocos aninhados, mas sem entrar em lambdas e declarações de função internas) e cria um único frame com todos os nomes, junto dos parâmetros. eval_block passa a avaliar o corpo no ambiente corrente, sem estender.
Parte 2 — atribuição cria vinculação global:
function assign_symbol_value(symbol, val, env) {
function env_loop(env) {
// ... busca normal ...
if (env === the_empty_environment) {
// em vez de error(symbol, "unbound name"):
add_binding_to_frame(symbol, val,
first_frame(the_global_environment));
}
// ...
}
return env_loop(env);
}
A questão de segurança: sem a proibição, um erro de digitação vira uma variável global silenciosa. totl = totl + x; dentro de uma função não falha — cria e polui um nome global, que outra parte do programa (ou outro script na mesma página!) pode ler e escrever. Pior: código malicioso ou descuidado pode sobrescrever nomes globais dos quais o resto do programa depende. O modo estrito transforma esse acidente em erro imediato e localizado — falhar cedo e perto da causa em vez de corromper estado longe dela.
📝 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! ✨