Olá Apresento a você a segunda parte da minha tradução do guia para implementar sua linguagem de programação JavaScript - PL Tutorial .
Do tradutor
Criaremos nossa própria linguagem de programação - linguagem λ (no original - linguagem λ ). No processo de criação, usaremos muitas técnicas interessantes, como descida recursiva, estilo de transferência de controle e técnicas básicas de otimização. Serão criadas duas versões do intérprete - o regular e o CPS, o transcompilador em JavaScript.
O autor do original é Mihai Bazon , o autor da famosa biblioteca UglifyJS (uma ferramenta para minimizar e formatar o código JS).
PS Existe um erro no interpretador e compilador: em expressões como a() && b() ou a() || b() a() || b() ambas as partes são sempre executadas. Obviamente, isso está errado porque a() falso para o operador && ou falso para o || , o valor de b() não desempenha nenhum papel. Isso não é difícil de corrigir.
Intérprete simples
Na parte anterior, escrevemos 3 funções: InputStream , TokenStream e parse . Para obter o AST do código, usamos o seguinte código:
var ast = parse(TokenStream(InputStream(code)));
Escrever um intérprete é mais fácil do que um analisador: apenas percorremos recursivamente a árvore e executamos as expressões em sua ordem normal.
Contexto ( Environment )
Para a execução correta do código, precisamos de um contexto - um objeto contendo todas as variáveis em um determinado local. Será passado como argumento para a função de evaluate .
Cada vez que entramos no nó lambda , devemos adicionar novas variáveis aos argumentos da função de contexto. Se o argumento sobrepuser a variável do bloco externo, devemos restaurar o valor antigo da variável após sair da função.
A maneira mais fácil de fazer isso é usar a herança de protótipo do JavaScript. Quando inserimos uma nova função, criamos um novo contexto, definimos o contexto externo como seu protótipo e chamamos a função no novo contexto. Graças a isso, não temos nada - no contexto externo todas as suas variáveis permanecerão.
Aqui está a implementação do objeto Environment :
function Environment(parent) { this.vars = Object.create(parent ? parent.vars : null); this.parent = parent; } Environment.prototype = { extend: function() { return new Environment(this); }, lookup: function(name) { var scope = this; while (scope) { if (Object.prototype.hasOwnProperty.call(scope.vars, name)) return scope; scope = scope.parent; } }, get: function(name) { if (name in this.vars) return this.vars[name]; throw new Error("Undefined variable " + name); }, set: function(name, value) { var scope = this.lookup(name);
O objeto Environment possui um campo parent que aponta para o contexto externo. Será null para o contexto global. Possui um campo vars no qual existem todas as variáveis que pertencem a esse contexto. Para um contexto global, é imediatamente igual a um objeto vazio ( Object.create(null) ) e uma cópia das variáveis do contexto pai Object.create(parent.vars) ) para um não global.
Tem vários métodos:
extend() - copia o contexto atual.lookup(name) - encontre o contexto em que a variável denominada name definida.get(name) - obtém o valor de uma variável chamada name . Lança uma exceção se a variável não tiver sido definida.set(name, value) - define o valor de uma variável. Este método procura o contexto em que a variável está definida. Se não estiver definido e não estivermos em um contexto global, uma exceção será lançada.def(name, value) - cria (ou sobrepõe ou substitui) uma variável no contexto atual.
evaluate função
Agora que temos o objeto Environment , podemos prosseguir para solucionar o problema principal. Esta função será um bloco de switch grande, que executará alguma ação dependendo do tipo do nó transmitido:
function evaluate(exp, env) { switch (exp.type) {
Para literais, simplesmente retornamos seu valor:
case "num": case "str": case "bool": return exp.value;
As variáveis são obtidas do contexto (o nome da variável está contido no campo de value ):
case "var": return env.get(exp.value);
Para atribuir, devemos garantir que, no lado esquerdo, tenhamos o nome da variável (nó var ). Caso contrário, simplesmente lançamos uma exceção (não apoiamos a atribuição a nada além de variáveis). Em seguida, definimos o valor da variável usando env.set . Observe que o lado direito da expressão deve ser calculado usando a chamada recursiva para evaluate :
case "assign": if (exp.left.type != "var") throw new Error("Cannot assign to " + JSON.stringify(exp.left)); return env.set(exp.left.value, evaluate(exp.right, env));
Para um nó do tipo binary devemos aplicar o operador para ambos os operandos. Escreveremos a função apply_op mais tarde. Além disso, chamamos evaluate para ambas as partes da expressão:
case "binary": return apply_op(exp.operator, evaluate(exp.left, env), evaluate(exp.right, env));
Um nó do tipo lambda retornará um fechamento normal do JavaScript, para que possa ser chamado como uma função regular, mesmo a partir do JavaScript. Eu adicionei a função make_lambda , que mostrarei mais tarde:
case "lambda": return make_lambda(env, exp);
A execução do nó if bastante simples: primeiro encontramos o valor da condição. Se não for falso, retorne o valor da ramificação then . Caso contrário, se houver um ramo else , seu valor ou false :
case "if": var cond = evaluate(exp.cond, env); if (cond !== false) return evaluate(exp.then, env); return exp.else ? evaluate(exp.else, env) : false;
O nó prog é uma sequência de expressões. Simplesmente executamos todas as expressões em ordem e pegamos o valor desta última (o valor da sequência vazia é false ):
case "prog": var val = false; exp.prog.forEach(function(exp){ val = evaluate(exp, env) }); return val;
Para um nó do tipo call precisamos chamar uma função. Antes disso, encontraremos o valor da própria função, encontraremos os valores de todos os argumentos e chamaremos a função usando apply :
case "call": var func = evaluate(exp.func, env); return func.apply(null, exp.args.map(function(arg){ return evaluate(arg, env); }));
Nós nunca chegaremos aqui, mas no caso de adicionarmos um novo tipo de nó ao analisador e esquecermos de adicioná-lo ao intérprete:
default: throw new Error("I don't know how to evaluate " + exp.type); } }
Esta foi a parte principal do intérprete. Acima, usamos duas funções que ainda não implementamos, então vamos começar:
apply_op :
function apply_op(op, a, b) { function num(x) { if (typeof x != "number") throw new Error("Expected number but got " + x); return x; } function div(x) { if (num(x) == 0) throw new Error("Divide by zero"); return x; } switch (op) { case "+" : return num(a) + num(b); case "-" : return num(a) - num(b); case "*" : return num(a) * num(b); case "/" : return num(a) / div(b); case "%" : return num(a) % div(b); case "&&" : return a !== false && b; case "||" : return a !== false ? a : b; case "<" : return num(a) < num(b); case ">" : return num(a) > num(b); case "<=" : return num(a) <= num(b); case ">=" : return num(a) >= num(b); case "==" : return a === b; case "!=" : return a !== b; } throw new Error("Can't apply operator " + op); }
Ele recebe o tipo e os argumentos do operador. switch simples e intuitivo. Ao contrário do JavaScript, que pode assumir qualquer valor, como variáveis, mesmo aquelas que não fazem sentido. Exigimos que os operandos dos operadores aritméticos sejam números e não permitam a divisão por zero. Para strings, apresentaremos algo mais tarde.
make_lambda :
function make_lambda(env, exp) { function lambda() { var names = exp.vars; var scope = env.extend(); for (var i = 0; i < names.length; ++i) scope.def(names[i], i < arguments.length ? arguments[i] : false); return evaluate(exp.body, scope); } return lambda; }
Como você pode ver acima, ele retorna uma função JavaScript regular que usa o contexto passado e as funções AST. Todo o trabalho é realizado apenas quando a própria função é chamada: um contexto é criado, argumentos são definidos (se não forem suficientes, tornam-se false ). Em seguida, o corpo da função é simplesmente executado em um novo contexto.
Funções nativas
Como você pode ver, não tivemos como interagir com o JavaScript em nosso idioma. Eu costumava usar as funções print e println , mas não as defini em lugar nenhum. Precisamos escrevê-los em JavaScript e apenas adicioná-los ao contexto global.
Aqui está um exemplo desse código:
Código inteiro
Você pode baixar todo o código que escrevemos esse tempo todo. Pode ser iniciado usando o NodeJS. Basta passar o código para o fluxo padrão:
echo 'sum = lambda(x, y) x + y; println(sum(2, 3));' | node lambda-eval1.js
Exemplos de código
Nossa linguagem de programação, embora simples, pode (teoricamente) resolver qualquer problema que possa ser resolvido por um computador. Isso ocorre porque alguns caras mais espertos do que eu jamais serei - Alonzo Church e Alan Turing - uma vez provaram que o λ-cálculo (lambda calculus) é equivalente a uma máquina de Turing, e nossa linguagem λ implementa λ-cálculo.
Isso significa que, mesmo que nosso idioma não tenha nenhuma oportunidade, todos nós podemos realizá-los usando o que já temos. Ou, se isso for difícil, podemos escrever um intérprete para outro idioma.
Ciclos
Loops não são um problema se tivermos recursão. Eu já mostrei um exemplo de loop implementado em cima da recursão. Vamos tentar novamente.
print_range = λ(a, b) if a <= b { print(a); if a + 1 <= b { print(", "); print_range(a + 1, b); } else println(""); }; print_range(1, 10);
Mas aqui temos um problema: se aumentarmos o número de iterações, digamos, para 1000. Por exemplo, recebo o erro “Tamanho máximo da pilha de chamadas excedido” após 600. Isso acontece porque o intérprete é recursivo e a recursão atinge a profundidade máxima.
Este é um problema sério, mas há uma solução. Eu gostaria de adicionar novas construções para iteração ( for ou while ), mas vamos tentar ficar sem elas. A recursão está linda, então vamos deixar. Veremos mais adiante como contornar essa limitação.
Estruturas de dados (falta dela)
Existem três tipos de dados em nosso idioma λ: números, seqüências de caracteres e tipos booleanos. Pode parecer que você não pode criar tipos complexos, como matrizes ou objetos. Mas isso não é um problema, temos mais um tipo: function. Acontece que, se seguirmos o cálculo λ, podemos criar qualquer estrutura de dados, incluindo objetos, mesmo com herança.
Vou mostrá-lo no exemplo de listas. Vamos imaginar que temos uma função cons que cria um objeto contendo dois valores. Vamos chamar esse objeto de "célula" ou "par". Vamos nomear um dos valores "carro" e o outro "cdr". Só porque eles são chamados no Lisp. Agora, se tivermos um objeto "cell", podemos obter seus valores usando as funções car e cdr :
x = cons(10, 20); print(car(x));
Agora podemos definir facilmente uma lista:
Uma lista é um par que contém o primeiro elemento em `car` e os demais elementos em` cdr`. Mas `cdr` pode conter apenas um valor! Este valor será uma lista. Uma lista é um par que contém o primeiro elemento em `car` e os demais elementos em` cdr`. Mas `cdr` pode conter apenas um valor! Este valor será uma lista. [...]
Este é um tipo de dados recursivo. Mas um problema permanece: quando você precisa parar? Logicamente, devemos parar quando cdr é uma lista vazia. Mas o que é uma lista vazia? Para fazer isso, vamos adicionar um novo objeto chamado "NIL". Pode ser usado em casal (podemos usar o car e os cdr , mas o resultado será o próprio NIL ). Agora vamos criar uma lista dos itens 1, 2, 3, 4, 5:
x = cons(1, cons(2, cons(3, cons(4, cons(5, NIL))))); print(car(x));
Parece horrível quando não há sintaxe especial para isso. Mas eu só queria mostrar que isso pode ser feito usando os recursos existentes da linguagem λ. Aqui está a implementação:
cons = λ(a, b) λ(f) f(a, b); car = λ(cell) cell(λ(a, b) a); cdr = λ(cell) cell(λ(a, b) b); NIL = λ(f) f(NIL, NIL);
Quando vi pela primeira vez cons / car / cdr feitos dessa maneira, fiquei surpreso que eles não precisassem de um único if (mas isso é estranho, considerando o fato de que ele não está no λ-cálculo original). Obviamente, nenhuma linguagem de programação faz isso desta maneira, porque é extremamente ineficiente, mas não torna os cálculos λ menos bonitos. Em uma linguagem clara, esse código faz o seguinte:
- a função
cons usa dois valores ( b ) e retorna a função que os mantém. Essa função é o próprio objeto do par. Ela pega uma discussão e a chama pelos dois valores do par. - A função
car chama o argumento passado, passando uma função que retorna o primeiro argumento. - a função
cdr faz o mesmo que a função car , mas com a única diferença é que a função passada retorna o segundo argumento. - a função
NIL funciona da mesma forma que cons , mas retorna um par com dois valores iguais a NIL.
cons = λ(a, b) λ(f) f(a, b); car = λ(cell) cell(λ(a, b) a); cdr = λ(cell) cell(λ(a, b) b); NIL = λ(f) f(NIL, NIL); x = cons(1, cons(2, cons(3, cons(4, cons(5, NIL))))); println(car(x));
Existem muitos algoritmos nas listas que podem ser implementados recursivamente e parecem lógicos. Por exemplo, aqui está uma função que chama a função passada para cada item da lista:
foreach = λ(list, f) if list != NIL { f(car(list)); foreach(cdr(list), f); }; foreach(x, println);
E aqui está outra que cria uma lista para um intervalo de números:
range = λ(a, b) if a <= b then cons(a, range(a + 1, b)) else NIL;
As listas que implementamos acima são imutáveis (não podemos mudar de car ou cdr após a criação da lista). A maioria dos Lisp tem funções para alterar um par. No esquema, eles são chamados de set-car! / set-cdr! . No Common Lisp, rplaca / rplacd . Desta vez, usamos os nomes do esquema:
cons = λ(x, y) λ(a, i, v) if a == "get" then if i == 0 then x else y else if i == 0 then x = v else y = v; car = λ(cell) cell("get", 0); cdr = λ(cell) cell("get", 1); set-car! = λ(cell, val) cell("set", 0, val); set-cdr! = λ(cell, val) cell("set", 1, val);
Isso mostra que podemos implementar estruturas de dados mutáveis. Não vou me aprofundar em como isso funciona, está claro no código.
Podemos ir além e implementar os objetos, mas sem alterações na sintaxe, será difícil fazer isso. Outra maneira é implementar uma nova sintaxe no tokenizer / analisador e adicionar seu processamento no intérprete. Todas as principais linguagens de programação fazem isso e é necessário obter desempenho normal. Adicionaremos nova sintaxe na próxima parte do artigo.
[Do tradutor: se você estiver interessado em cálculo lambda, há um artigo interessante sobre Habré dedicado a este tópico: cálculo lambda em JavaScript .]
Novas construções de sintaxe
Nossa linguagem λ possui algumas construções sintáticas. Por exemplo, não há maneira direta de adicionar novas variáveis. Como eu disse antes, devemos usar o IIFE, então fica algo assim:
(λ(x, y){ (λ(z){
Adicionaremos a palavra-chave let . Isso nos permitirá escrever algo como isto:
let (x = 2, y = 3, z = x + y) print(x + y + z);
Para cada variável no bloco let , as variáveis anteriores devem estar disponíveis mesmo no mesmo bloco. Portanto, o código acima será equivalente ao seguinte:
(λ(x){ (λ(y){ (λ(z){ print(x + y + z); })(x + y); })(3); })(2);
Essas alterações podem ser feitas diretamente no analisador e, em seguida, não exigirão alterações no intérprete. Em vez de adicionar um novo nó let , podemos transformá-lo em nós de call e lambda . Isso significa que não fizemos alterações semânticas em nossa linguagem - isso é chamado de "açúcar sintático", e a operação de converter isso em nós AST que existia antes é chamada de "sem açúcar" (original: "desugaring").
No entanto, devemos alterar o analisador de qualquer maneira. Vamos adicionar um novo nó "let", porque ele pode ser interpretado com mais eficiência (não há necessidade de criar fechamentos e chamá-los imediatamente, basta copiar e alterar o contexto).
Além disso, adicionaremos suporte para "let named", que estava no esquema. Isso facilita a criação de loops:
print(let loop (n = 10) if n > 0 then n + loop(n - 1) else 0);
Este é um loop "recursivo" que conta a soma de 10 + 9 + ... + 0. Anteriormente, teríamos que fazer o seguinte:
print((λ(loop){ loop = λ(n) if n > 0 then n + loop(n - 1) else 0; loop(10); })());
Além disso, para facilitar isso, adicionaremos a sintaxe de "funções com um nome". Ficará assim:
print((λ loop (n) if n > 0 then n + loop(n - 1) else 0) (10));
Modificações que precisam ser feitas para isso:
- Suporte para o nome opcional após a palavra-chave
lambda . Se estiver presente, devemos adicionar uma variável ao contexto atual que apontará para a própria função. É exatamente o mesmo que funções com um nome em JavaScript. - Suporte para a nova palavra-chave
let . A seguir, vem um nome opcional e uma lista (possivelmente vazia) de definições de variáveis neste formato: foo = EXPRESSION , separadas por vírgulas. O corpo de uma expressão let é uma expressão (que, é claro, pode ser uma sequência de expressões).
Alterações do analisador
Primeiro, uma pequena alteração no tokenizer, adicione a palavra-chave let à lista de palavras-chave:
var keywords = " let if then else lambda λ true false ";
Altere a função parse_lambda que leia um nome opcional:
function parse_lambda() { return { type: "lambda", name: input.peek().type == "var" ? input.next().value : null,
Agora adicione uma função que analise a expressão let :
function parse_let() { skip_kw("let"); if (input.peek().type == "var") { var name = input.next().value; var defs = delimited("(", ")", ",", parse_vardef); return { type: "call", func: { type: "lambda", name: name, vars: defs.map(function(def){ return def.name }), body: parse_expression(), }, args: defs.map(function(def){ return def.def || FALSE }) }; } return { type: "let", vars: delimited("(", ")", ",", parse_vardef), body: parse_expression(), }; }
Isso lida com dois casos. Se depois de let existir um token do tipo var , isso será let com um nome. Além disso, lemos a lista de definições usando a função delimited , pois estão entre colchetes e separadas por vírgulas, e usamos a função parse_vardef , mostrada abaixo. Em seguida, retornamos um nó do tipo call , que chama imediatamente uma função denominada (IIFE). Os argumentos para a função são as variáveis definidas por let e o nó de call passará os valores como argumentos. E, é claro, o corpo da função é lido usando parse_expression() .
Se for um simples let , retornamos um nó do tipo let com os campos vars e body . O campo vars contém uma matriz de variáveis no seguinte formato: { name: VARIABLE, def: AST } , que são analisados pela seguinte função:
function parse_vardef() { var name = parse_varname(), def; if (is_op("=")) { input.next(); def = parse_expression(); } return { name: name, def: def }; }
Além disso, você precisa adicionar uma verificação para um novo tipo de expressão na função parse_atom :
Alterações de intérpretes
Como decidimos alterar a estrutura do AST em vez de "quebrá-lo" nos tipos antigos de nós, devemos adicionar o processamento da nova lógica ao intérprete.
Para adicionar suporte ao nome da função opcional, modificamos a função make_lambda :
function make_lambda(env, exp) { if (exp.name) {
Se a função tiver um nome, quando criamos o fechamento, fazemos uma cópia do contexto e adicionamos a função ao contexto. O resto permanece o mesmo.
E, finalmente, para processar um nó do tipo let , adicionamos o seguinte caso ao intérprete:
case "let": exp.vars.forEach(function(v){ var scope = env.extend(); scope.def(v.name, v.def ? evaluate(v.def, env) : false); env = scope; }); return evaluate(exp.body, env);
Observe que para cada variável é criado um novo contexto no qual uma nova variável é adicionada. Depois disso, simplesmente executamos o corpo no último contexto.
Exemplos
println(let loop (n = 100) if n > 0 then n + loop(n - 1) else 0); let (x = 2, y = x + 1, z = x + y) println(x + y + z);
— .
. , , , . JavaScript λ.
:
globalEnv.def("fibJS", function fibJS(n){ if (n < 2) return n; return fibJS(n - 1) + fibJS(n - 2); }); globalEnv.def("time", function(fn){ var t1 = Date.now(); var ret = fn(); var t2 = Date.now(); println("Time: " + (t2 - t1) + "ms"); return ret; });
time , , , .
fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); print("fib(10): "); time( λ() println(fib(10)) ); print("fibJS(10): "); time( λ() println(fibJS(10)) ); println("---");
, Google Chrome, n (27), λ , , JS 4 . , , .
λ JavaScript. , for / while ; JS. ? JS , .
, , JavaScript, , JavaScript.
, , . , .
Conclusão
, . , - ; , , ? — JavaScript. , JavaScript — ? , , JavaScript, , , . JavaScript ( , ).
, , Lisp — : //. , , .. Lisp . Lisp let , , Lisp.
: JavaScript. Parte 3: Intérprete de CPS