Que tal escrever um interpretador em cem linhas de código? Let's ride!
Um interpretador é um programa que lê um programa em uma dada linguagem e executa as ações descritas por esse programa. (Um compilador, por outro lado, lê um programa em uma linguagem e o traduz para outra linguagem, freqüentemente a linguagem de máquina de um processador. O processador, por sua vez, é um interpretador de linguagem de máquina implementado em hardware. But I digress.) Há duas linguagens envolvidas em um interpretador: a linguagem de implementação (em que o interpretador é escrito) e a linguagem implementada (que o interpretador interpreta). (Em um compilador há três linguagens envolvidas: a linguagem de implementação, a linguagem fonte e a linguagem alvo.) Essas linguagens podem coincidir (e.g., podemos escrever um interpretador de JavaScript em JavaScript), mas mesmo assim as entidades das duas linguagens freqüentemente são distintas (e.g., funções da linguagem implementada podem ser representadas por uma outra estrutura de dados da linguagem de implementação).
Neste post, implementaremos um interpretador para uma linguagem Lisp-like em JavaScript. O objetivo primário é demonstrar o funcionamento geral de um interpretador. Assim, implementaremos apenas um "Lisp" bem básico, que em certos aspectos diverge dos Lisps típicos. Usaremos JavaScript para a implementação, em parte por ser uma linguagem bem conhecida, e em parte para podermos testar o interpretador no browser. O código desenvolvido neste post, prontamente modificável e experimentável, pode ser encontrado aqui.
O primeiro passo na interpretação de um programa é a análise sintática, ou parsing. O parser lê o texto de um programa e produz uma estrutura de dados que reflete a estrutura sintática do programa. Por exemplo, ao se deparar com uma expressão do tipo 2*3+4*5 em uma linguagem de programação típica, o parser produzirá uma árvore do tipo:
+
/ \
/ \
* *
/ \ / \
2 3 4 5
Essa árvore reflete o agrupamento hierárquico dos elementos da expressão, segundo a sintaxe da linguagem em questão.
Uma vantagem de se implementar um Lisp é que o texto de um programa em Lisp é uma representação direta e uniforme da árvore sintática do programa. A expressão acima, por exemplo, seria representada por (+ (* 2 3) (* 4 5)) em Lisp. Isso torna o parser bastante simples.
De fato, ao contrário do que acontece com a maior parte das linguagens de programação, o significado de um programa em um Lisp tradicional não é definido em termos da sintaxe textual do programa. Ao invés disso, é definido um mapeamento da sintaxe textual para as estruturas em memória, e é a partir das estruturas que se define a semântica da linguagem. (+ 2 3) não "é" uma soma; (+ 2 3) é uma lista, que quando avaliada realizará uma soma. O resultado prático disso para nós neste momento é que é fácil de separar o parsing do resto do processo de interpretação em um Lisp; primeiro definimos os tipos de dados que podem ser encontrados no texto de um programa, e depois nos preocupamos com o que eles significam.
Nossa linguagem terá os seguintes tipos de dados:
Um programa conterá uma seqüência de expressões (formas, em Lispês) independentes. Escreveremos nosso parser como uma função que recebe o texto do programa, faz o parsing de uma forma, e retorna a estrutura correspondente e o que sobrou do texto. Posteriormente, chamaremos o parser repetidamente com o que sobrou de cada passo de parsing, até consumir todo o programa. O parser procurará o primeiro caractere não-em-branco da entrada, e tomará ações distintas dependendo do que ele for. Se for um (, lemos itens até encontrarmos o ) correspondente, e os acumulamos em uma lista. Se for outro caractere, lemos a entrada até o próximo parêntese ou espaço; se o que encontramos consistir apenas de dígitos (possivelmente precedidos por um -), estamos diante de um número; caso contrário, encontramos um símbolo.
function read(text) {
text = text.trimLeft(); // Pula espaços iniciais.
if (text == "")
throw "EOF";
else if (text[0] == "(") {
var list = [];
text = text.substring(1); // Pula o '('.
while ([item, text] = read(text), item!=")")
text.push(item);
return [list, text];
}
else if (text[0] == ")")
return [")", text.substring(1)];
else {
match = text.match(/^[^\s()]+/); // Lê tudo até o primeiro parêntese ou espaço.
if (match[0].match(/^-?\d+$/))
return [Number(match[0]), text.substring(match[0].length)];
else
return [match[0], text.substring(match[0].length)];
}
}
Agora, se chamarmos read("1 2 3"), teremos como resultado [1, " 2 3"], e se chamarmos read("(+ 2 3)"), teremos [["+",2,3], ""]. Podemos nos dar por satisfeitos com o parser por ora.
Feito o parsing, podemos fazer a interpretação propriamente dita, isto é, executar as operações indicadas pelo programa. Nossa linguagem é baseada em expressões; o significado de um programa é especificado em termos de como é avaliada (evaluated) cada expressão do programa, i.e., qual é o valor de cada expressão, e possíveis efeitos colaterais de avaliar uma expressão. (Outras linguagens possuem tanto expressões quanto statements, comandos que não possuem valor, mas apenas efeito colateral.)
Números são avaliados para si mesmos; o valor da expressão 2 é o próprio 2.
Símbolos são interpretados como referências a variáveis. Em qualquer ponto da avaliação, há um ambiente (environment), um conjunto de associações de nomes de variáveis aos seus respectivos valores. O valor de um símbolo é o valor da variável nomeada pelo símbolo no ambiente em que ele é avaliado. Se a variável não existir, um erro de execução ocorre.
É importante notar que trechos de programa diferentes podem ser avaliados em ambientes diferentes. É possível criar variáveis locais, visíveis em apenas um trecho do programa. Por exemplo, os parâmetros de uma função são visíveis apenas pelas expressões contidas na função. Cada chamada à função cria um novo ambiente, associando os parâmetros da função aos valores usados naquela chamada. Além dos parâmetros, as expressões da função também verão as variáveis definidas fora da função (desde que elas não tenham os mesmos nomes dos parâmetros). Como se pode ver, ambientes são hierárquicos: o valor de uma expressão é procurado primeiro no ambiente mais recentemente criado (e.g., os parâmetros da função); se a variável não for encontrada aí, ela será procurada em ambientes mais externos, até chegar no ambiente global. Representaremos ambientes no nosso interpretador por objetos simples (associações nome/valor) em JavaScript; ligaremos um ambiente ao ambiente imediatamente mais externo a ele através de um campo _parent no objeto. E.g., {x:1, y:2, _parent: {a:3, b:4}} representa um ambiente com as variáveis x e y, subordinado a um ambiente com as variáveis a e b. Para encontrar uma variável em um ambiente, usaremos a função lookup:
function lookup(name, env) {
if (env) {
if (env[name] !== undefined)
// Se o nome está presente no ambiente atual, retornamo-lo.
return env[name];
else
// Caso contrário, procuramos no ambiente pai.
return lookup(name, env._parent);
}
else {
// Se mandamos procurar no ambiente pai, e o ambiente pai não existe, paramos aqui.
throw "Unbound variable " + name;
}
}
Com isso, podemos começar a escrever o nosso avaliador de expressões. Ele recebe uma expressão para avaliar e o ambiente onde a expressão será avaliada:
function eval(code, env) {
if (typeof(code) == "number")
return code;
else if (typeof(code) == "string")
return lookup(code, env);
...
Falta definirmos como avaliaremos listas. Uma lista é avaliada da seguinte maneira: se o primeiro elemento da lista for o nome de um operador especial (como if), a avaliação segue segundo as regras do operador; caso contrário, o primeiro elemento é tomado como uma função a ser chamada usando os outros elementos como argumentos. Assim, (f x y) é interpretado como a chamada da função f com os argumentos x e y. Finalmente, se a lista for vazia, o resultado é a própria lista vazia.
Nossa linguagem tem quatro operadores especiais. Um deles, lambda, é usado para criar funções. (lambda (x y) (+ x y)) cria uma função que recebe dois argumentos, nomeados x e y, e retorna a soma dos dois. Representaremos as funções do nosso Lisp por um objeto em JavaScript contendo a lista de parâmetros, o corpo da função, e o ambiente em que a função foi criada. (A chamada da função pode ocorrer posteriormente em um ambiente completamente diferente do ambiente em que ela foi criada; queremos, entretanto, que o corpo da função seja avaliado no ambiente original da definição. Caso contrário, se alguém criar uma variável chamada + e chamar a função que acabamos de definir, ela não mais necessariamente somará dois números.)
else if (code.length == 0)
return []; // Se for a lista vazia, retorna vazio.
else {
switch (code[0]) {
case "lambda":
return { type: "lambda", args: code[1], body: code[2], env: env };
lambda cria uma função, mas não lhe dá um nome. O segundo operador especial da nossa linguagem é o define: (define nome valor) cria uma variável chamada nome no ambiente atual, com o valor especificado. Para avaliar essa expressão, avaliamos o valor, e acrescentamos a variável ao ambiente:
case "define":
return env[code[1]] = eval(code[2], env);
O terceiro operador é o if: (if test then else) avalia test; se test for diferente da lista vazia, avalia-se then; senão, avalia-se else. O resultado da expressão inteira é o valor da expressão escolhida segundo o teste.
case "if":
if (eval(code[1], env).length !== 0)
return eval(code[2], env);
else
return eval(code[3], env);
O último operador é o quote: (quote x) retorna x intacto, sem avaliar. O quote serve para quando queremos tratar um símbolo ou lista como um dado, não como um trecho de código a ser avaliado; (quote (+ 2 3)) simplesmente retorna a lista (+ 2 3) intacta.
case "quote":
return code[1];
Por último, o caso em que o primeiro elemento da lista não é um operador especial: devemos avaliar todos os elementos da lista, e chamar a função resultante da avaliação do primeiro:
default:
var evals = code.map(function(x) eval(x, env));
var fun = evals[0];
var args = evals.slice(1);
Na verdade teremos dois tipos de função no nosso interpretador: funções definidas pelo usuário, que possuem um corpo escrito em Lisp e que deveremos avaliar, e funções embutidas no interpretador (como +), que serão definidas diretamente em JavaScript. Representaremos as funções embutidas por funções do JavaScript; para avaliar uma chamada a uma função embutida, basta chamar a função com o resultado da avaliação dos argumentos:
if (typeof(fun) == "function")
return fun.apply(null, args);
Se se trata de uma função definida pelo usuário, devemos avaliar o corpo da função em um ambiente associando os parâmetros da função com os argumentos com que foi chamada. Além disso, a função deve enxergar as variáveis que existiam quando ela foi definida; logo, o ambiente de definição deve ser linkado como ambiente pai.
else if (typeof(fun) == "object" && fun.type == "lambda") {
var newenv = { _parent: fun.env };
for (var i in fun.args)
newenv[fun.args[i]] = args[i];
return eval(fun.body, newenv);
}
Por último, se o primeiro item não for uma função, reportamos um erro:
else
throw "Not a function: " + fun;
}
}
}
A parte importante do interpretador está pronta. Falta é definir um ambiente padrão, com algumas funções básicas. Eis algumas funções aritméticas:
var stdenv = {
"+": function(x,y) x+y,
"-": function(x,y) x-y,
"*": function(x,y) x*y,
"/": function(x,y) x/y,
Aqui as definições são bastante simples, pois os números do nosso Lisp são representados por números do JavaScript. Se não fosse esse o caso, teríamos um passo de conversão dos argumentos para números do JavaScript, e do resultado de volta para números do Lisp. As funções de comparação são menos diretas: devemos converter os booleanos do JavaScript (true e false) para os do Lisp (whatever e ()). (Qualquer coisa diferente de () é verdadeira, segundo o if; convencionalmente, se usa o símbolo t para representar "verdadeiro".)
"=": function(x,y) x==y? "t" : [],
"<": function(x,y) x<y? "t" : [],
...
Outras funções importantes em um Lisp são as funções de manipulação de listas: (first ls) retorna o primeiro elemento de uma lista, (rest ls) retorna a lista sem o primeiro elemento, e (cons x ls) cria uma lista nova adicionando x à lista original.
"first": function(ls): return ls[0],
"rest" : function(ls): return ls.slice(1),
"cons" : function(x,ls) : return [x].concat(ls),
Além disso, temos os testes null?, que testa se um objeto é a lista vazia, e cons?, que testa se um objeto é uma lista não-vazia.
"null?": function(x) typeof(x)=="object" && x.length==0? "t" : [],
"cons?": function(x) typeof(x)=="object" && x.length>0? "t" : [],
}
E está pronto! Já podemos chamar nosso interpretador:
eval(read("(define fac (lambda (n) (if (= n 0) 1 (* n (fac (- n 1))))))")[0], stdenv);
alert(eval(read("(fac 5)")[0], stdenv));
Não criamos uma função para ler todas as expressões de um programa e chamar eval com cada uma, nem criamos meios de chamar o interpretador sem escrevermos a chamada no fonte do interpretador ou em um prompt, mas esses são detalhes menores. Você pode usar a interface mencionada no começo do post para experimentar o interpretador.
** O nome do post foi inspirado no Write Yourself a Scheme in 48 Hours, um tutorial de Haskell.
Copyright © 2010-2024 Vítor De Araújo
O conteúdo deste blog, a menos que de outra forma especificado, pode ser utilizado segundo os termos da licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International.
Powered by Blognir.