Bonjour Je vous présente la deuxième partie de ma traduction du guide d'implémentation de votre langage de programmation JavaScript - PL Tutorial .
Du traducteur
Nous allons créer notre propre langage de programmation - langage λ (dans l'original - λanguage). Dans le processus de création, nous utiliserons de nombreuses techniques intéressantes, telles que la descente récursive, le style de transfert de contrôle et les techniques d'optimisation de base. Deux versions de l'interpréteur seront créées - les interprètes standard et CPS, le trans-compilateur en JavaScript.
L'auteur de l'original est Mihai Bazon , l'auteur de la célèbre bibliothèque UglifyJS (un outil pour minimiser et formater le code JS).
PS Il y a un bug dans l'interpréteur et le compilateur: dans des expressions comme a() && b() ou a() || b() a() || b() deux parties sont toujours exécutées. Bien sûr, cela est faux car a() faux pour l'opérateur && , ou pas faux pour le || , alors la valeur de b() ne joue aucun rôle. Ce n'est pas difficile à résoudre.
Interprète simple
Dans la partie précédente, nous avons écrit 3 fonctions: InputStream , TokenStream et parse . Pour obtenir l'AST du code, nous utilisons le code suivant:
var ast = parse(TokenStream(InputStream(code)));
Écrire un interpréteur est plus facile qu'un analyseur: nous parcourons simplement récursivement l'arborescence et exécutons les expressions dans leur ordre normal.
Contexte ( Environment )
Pour une exécution correcte du code, nous avons besoin d'un contexte - un objet contenant toutes les variables dans un emplacement donné. Il sera transmis en tant qu'argument à la fonction d' evaluate .
Chaque fois que nous entrons dans le nœud lambda , nous devons ajouter de nouvelles variables aux arguments de la fonction de contexte. Si l'argument chevauche la variable du bloc externe, nous devons restaurer l'ancienne valeur de la variable après avoir quitté la fonction.
La façon la plus simple de procéder consiste à utiliser l'héritage JavaScript prototype. Lorsque nous entrons dans une nouvelle fonction, nous créons un nouveau contexte, définissons le contexte externe comme son prototype et appelons la fonction dans le nouveau contexte. Grâce à cela, nous n'avons rien - dans le contexte externe, toutes ses variables resteront.
Voici l'implémentation de l'objet 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);
L'objet Environment a un champ parent qui pointe vers le contexte externe. Il sera null pour le contexte global. Il a un champ vars dans lequel toutes les variables appartiennent à ce contexte. Pour un contexte global, il est immédiatement égal à un objet vide ( Object.create(null) ) et une copie des variables du contexte parent ( Object.create(parent.vars) ) pour un non global.
Il a plusieurs méthodes:
extend() - copie le contexte actuel.lookup(name) - recherchez le contexte dans lequel la variable nommée name définie.get(name) - récupère la valeur d'une variable nommée name . Lève une exception si la variable n'a pas été définie.set(name, value) - définit la valeur d'une variable. Cette méthode recherche le contexte dans lequel la variable est définie. S'il n'est pas défini et que nous ne sommes pas dans un contexte global, une exception sera levée.def(name, value) - crée (ou chevauche ou remplace) une variable dans le contexte actuel.
evaluate fonction
Maintenant que nous avons l'objet Environment , nous pouvons passer à la résolution du problème principal. Cette fonction sera un grand bloc de switch , qui effectuera une action en fonction du type du nœud transmis:
function evaluate(exp, env) { switch (exp.type) {
Pour les littéraux, nous renvoyons simplement sa valeur:
case "num": case "str": case "bool": return exp.value;
Les variables sont extraites du contexte (le nom de la variable est contenu dans le champ de value ):
case "var": return env.get(exp.value);
Pour attribuer, nous devons nous assurer que sur le côté gauche, nous avons le nom de la variable (nœud var ). Sinon, nous lançons simplement une exception (nous ne prenons pas en charge l'affectation à autre chose que des variables). Ensuite, nous définissons la valeur de la variable en utilisant env.set . Notez que le côté droit de l'expression doit être calculé à l'aide de l'appel récursif pour 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));
Pour un nœud de type binary nous devons appliquer l'opérateur pour les deux opérandes. Nous écrirons la fonction apply_op plus tard. Aussi, nous appelons evaluate pour les deux parties de l'expression:
case "binary": return apply_op(exp.operator, evaluate(exp.left, env), evaluate(exp.right, env));
Un nœud de type lambda renverra une fermeture JavaScript normale, il peut donc être appelé comme une fonction régulière même à partir de JavaScript. J'ai ajouté la fonction make_lambda , que je montrerai plus tard:
case "lambda": return make_lambda(env, exp);
L'exécution du nœud if assez simple: on trouve d'abord la valeur de la condition. Si ce n'est pas faux, retournez la valeur de la branche then . Sinon, s'il y a une branche else , alors sa valeur, 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;
Le nœud prog est une séquence d'expressions. Nous exécutons simplement toutes les expressions dans l'ordre et prenons la valeur de cette dernière (la valeur de la séquence vide est false ):
case "prog": var val = false; exp.prog.forEach(function(exp){ val = evaluate(exp, env) }); return val;
Pour un nœud de type call nous devons appeler une fonction. Avant cela, nous allons trouver la valeur de la fonction elle-même, trouver les valeurs de tous les arguments et appeler la fonction en utilisant apply :
case "call": var func = evaluate(exp.func, env); return func.apply(null, exp.args.map(function(arg){ return evaluate(arg, env); }));
Nous n'arriverons jamais ici, mais au cas où nous ajouterions un nouveau type de nœud à l'analyseur et oublierions de l'ajouter à l'interpréteur:
default: throw new Error("I don't know how to evaluate " + exp.type); } }
C'était la partie principale de l'interprète. Ci-dessus, nous avons utilisé deux fonctions que nous n'avons pas encore implémentées, alors commençons:
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); }
Il reçoit le type d'opérateur et les arguments. switch simple et intuitif. Contrairement à JavaScript, qui peut prendre n'importe quelle valeur, comme les variables, même celles qui n'ont aucun sens. Nous exigeons que les opérandes des opérateurs arithmétiques soient des nombres et ne permettent pas la division par zéro. Pour les cordes, nous trouverons quelque chose plus tard.
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; }
Comme vous pouvez le voir ci-dessus, il renvoie une fonction JavaScript standard qui utilise le contexte passé et les fonctions AST. Tout le travail n'est effectué que lorsque la fonction elle-même est appelée: un contexte est créé, des arguments sont définis (s'ils ne suffisent pas, ils deviennent false ). Ensuite, le corps de la fonction est simplement exécuté dans un nouveau contexte.
Fonctions natives
Comme vous pouvez le voir, nous n'avions aucun moyen d'interagir avec JavaScript à partir de notre langue. J'avais l'habitude d'utiliser les fonctions print et println , mais je ne les ai définies nulle part. Nous devons les écrire en JavaScript et les ajouter simplement au contexte global.
Voici un exemple d'un tel code:
Code entier
Vous pouvez télécharger tout le code que nous avons écrit tout ce temps. Il peut être lancé à l'aide de NodeJS. Passez simplement le code au flux standard:
echo 'sum = lambda(x, y) x + y; println(sum(2, 3));' | node lambda-eval1.js
Exemples de code
Notre langage de programmation, bien que simple, peut (théoriquement) résoudre tout problème qui peut être résolu par un ordinateur. En effet, certains mecs plus intelligents que moi ne le seront jamais - Alonzo Church et Alan Turing - ont déjà prouvé que le λ-calcul (lambda calcul) est équivalent à une machine de Turing, et notre langage λ implémente le λ-calcul.
Cela signifie que même si notre langue n'a pas d'opportunités, nous pouvons tout de même pouvoir les réaliser en utilisant ce que nous avons déjà. Ou, si cela est difficile à faire, nous pouvons écrire un interprète pour une autre langue.
Cycles
Les boucles ne sont pas un problème si nous avons une récursivité. J'ai déjà montré un exemple de boucle implémentée au-dessus de la récursivité. Essayons encore.
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);
Mais ici, nous avons un problème: si nous augmentons le nombre d'itérations, disons, à 1000. Par exemple, j'obtiens l'erreur «Taille maximale de la pile d'appels dépassée» après 600. Cela se produit car l'interpréteur est récursif et la récursivité atteint la profondeur maximale.
Il s'agit d'un problème grave, mais il existe une solution. Je voudrais ajouter de nouvelles constructions pour l'itération ( for ou while ), mais essayons de nous en passer. La récursivité est magnifique, alors laissons-la. Nous verrons plus loin comment contourner cette limitation.
Structures de données (leur absence)
Il existe trois types de données dans notre langage λ: les nombres, les chaînes et les types booléens. Il peut sembler que vous ne pouvez pas créer de types complexes, tels que des tableaux ou des objets. Mais ce n'est pas un tat, nous avons un autre type: fonction. Il s'avère que si nous suivons le λ-calcul, nous pouvons créer toutes les structures de données, y compris les objets, même avec héritage.
Je vais le montrer sur l'exemple des listes. Imaginons que nous ayons une fonction cons qui crée un objet contenant deux valeurs. Appelons cet objet "cellule" ou "paire". Nous nommerons l'une des valeurs «voiture» et l'autre «cdr». Tout simplement parce qu'ils sont appelés ainsi en Lisp. Maintenant, si nous avons un objet "cellule", alors nous pouvons obtenir ses valeurs en utilisant les fonctions car et cdr :
x = cons(10, 20); print(car(x));
Maintenant, nous pouvons facilement définir une liste:
Une liste est une paire contenant le premier élément dans `car` et les autres éléments dans` cdr`. Mais `cdr` ne peut contenir qu'une seule valeur! Cette valeur sera une liste. Une liste est une paire contenant le premier élément dans `car` et les autres éléments dans` cdr`. Mais `cdr` ne peut contenir qu'une seule valeur! Cette valeur sera une liste. [...]
Il s'agit d'un type de données récursif. Mais un problème demeure: quand devez-vous arrêter? Logiquement, nous devrions arrêter lorsque cdr est une liste vide. Mais qu'est-ce qu'une liste vide? Pour ce faire, ajoutons un nouvel objet appelé "NIL". Il peut être utilisé en couple (nous pouvons utiliser car et cdr dessus, mais leur résultat sera NIL lui-même). Créons maintenant une liste des éléments 1, 2, 3, 4, 5:
x = cons(1, cons(2, cons(3, cons(4, cons(5, NIL))))); print(car(x));
Cela a l'air horrible quand il n'y a pas de syntaxe spéciale pour cela. Mais je voulais juste montrer que cela peut être fait en utilisant les fonctionnalités existantes du langage λ. Voici l'implémentation:
cons = λ(a, b) λ(f) f(a, b); car = λ(cell) cell(λ(a, b) a); cdr = λ(cell) cell(λ(a, b) b); NIL = λ(f) f(NIL, NIL);
Quand j'ai vu pour la première fois cons / car / cdr fait de cette façon, j'ai été surpris qu'ils n'aient pas besoin d'un seul if (mais c'est étrange étant donné qu'il n'est pas dans le λ-calcul d'origine). Bien sûr, aucun langage de programmation ne procède de cette façon, car il est extrêmement inefficace, mais cela ne rend pas les λ-calculs moins beaux. Dans un langage clair, ce code effectue les opérations suivantes:
- la fonction
cons prend deux valeurs ( a et b ) et retourne la fonction qui les contient. Cette fonction est l'objet même de la paire. Elle prend un argument et l'appelle pour les deux valeurs de la paire. - La fonction
car appelle l'argument passé, en passant une fonction qui renvoie le premier argument. - la fonction
cdr fait la même chose que la fonction car , mais avec la seule différence étant que la fonction passée renvoie le deuxième argument. - la fonction
NIL fonctionne de la même manière que cons , mais renvoie une paire avec deux valeurs égales à 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));
Il existe de nombreux algorithmes sur les listes qui peuvent être implémentés de manière récursive et semblent logiques. Par exemple, voici une fonction qui appelle la fonction transmise pour chaque élément de liste:
foreach = λ(list, f) if list != NIL { f(car(list)); foreach(cdr(list), f); }; foreach(x, println);
Et voici un autre qui crée une liste pour une plage de nombres:
range = λ(a, b) if a <= b then cons(a, range(a + 1, b)) else NIL;
Les listes que nous avons implémentées ci-dessus sont immuables (nous ne pouvons pas changer de car ou de cdr fois la liste créée). La plupart des lisp ont des fonctions pour changer une paire. Dans Scheme, ils sont appelés set-car! / set-cdr! . En Common Lisp, rplaca / rplacd . Cette fois, nous utilisons les noms de Scheme:
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);
Cela montre que nous pouvons implémenter des structures de données mutables. Je n'entrerai pas dans les détails de son fonctionnement, cela ressort clairement du code.
Nous pouvons aller plus loin et implémenter les objets, mais sans changement de syntaxe ce sera difficile à faire. Une autre façon est d'implémenter une nouvelle syntaxe dans le tokenizer / parser et d'ajouter leur traitement dans l'interpréteur. Tous les principaux langages de programmation font cela, et il est nécessaire d'atteindre des performances normales. Nous ajouterons une nouvelle syntaxe dans la prochaine partie de l'article.
[Du traducteur: si vous êtes intéressé par le calcul lambda, il y a un article sympa sur Habré dédié à ce sujet: le calcul lambda en JavaScript .]
Nouvelles constructions syntaxiques
Notre langage λ a pas mal de constructions syntaxiques. Par exemple, il n'existe aucun moyen direct d'ajouter de nouvelles variables. Comme je l'ai déjà dit, nous devons utiliser IIFE, donc cela ressemble à ceci:
(λ(x, y){ (λ(z){
Nous ajouterons le mot clé let . Cela nous permettra d'écrire quelque chose comme ceci:
let (x = 2, y = 3, z = x + y) print(x + y + z);
Pour chaque variable du bloc let , les variables précédentes doivent être disponibles même à partir du même bloc. Par conséquent, le code ci-dessus sera équivalent à ce qui suit:
(λ(x){ (λ(y){ (λ(z){ print(x + y + z); })(x + y); })(3); })(2);
Ces modifications peuvent être effectuées directement dans l'analyseur et ne nécessiteront alors pas de modifications dans l'interpréteur. Au lieu d'ajouter un nouveau nœud let , nous pouvons le transformer en nœuds d' call et lambda . Cela signifie que nous n'avons effectué aucun changement sémantique dans notre langage - c'est ce qu'on appelle le «sucre syntaxique», et l'opération de conversion en nœuds AST qui existait auparavant est appelée «sans sucre» (original: «desugaring»).
Cependant, nous devons quand même changer l'analyseur. Ajoutons un nouveau nœud «let» car il peut être interprété plus efficacement (pas besoin de créer de fermetures et de les appeler tout de suite, il suffit de copier et changer le contexte).
En outre, nous ajouterons la prise en charge de "let named", qui était dans Scheme. Cela facilite la création de boucles:
print(let loop (n = 10) if n > 0 then n + loop(n - 1) else 0);
Il s'agit d'une boucle "récursive" qui compte la somme de 10 + 9 + ... + 0. Auparavant, nous devions le faire comme ceci:
print((λ(loop){ loop = λ(n) if n > 0 then n + loop(n - 1) else 0; loop(10); })());
De plus, pour faciliter cela, nous ajouterons la syntaxe des "fonctions avec un nom". Cela ressemblera à ceci:
print((λ loop (n) if n > 0 then n + loop(n - 1) else 0) (10));
Modifications à effectuer pour cela:
- Prise en charge du nom facultatif après
lambda mot clé lambda . S'il est présent, alors nous devons ajouter une variable au contexte actuel qui pointera vers la fonction elle-même. C'est exactement la même chose que les fonctions avec un nom en JavaScript. - Prise en charge du nouveau mot clé
let . Vient ensuite un nom facultatif et une liste (éventuellement vide) de définitions de variables sous cette forme: foo = EXPRESSION , séparés par des virgules. Le corps de l'expression let est une expression unique (qui, bien sûr, peut être une séquence d'expressions).
Modifications de l'analyseur
Tout d'abord, un petit changement dans le tokenizer, ajoutez le mot clé let à la liste des mots clés:
var keywords = " let if then else lambda λ true false ";
Modifiez la fonction parse_lambda qu'elle lit un nom facultatif:
function parse_lambda() { return { type: "lambda", name: input.peek().type == "var" ? input.next().value : null,
Ajoutez maintenant une fonction qui analyse l'expression 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(), }; }
Cela gère deux cas. Si après let il y a un jeton de type var , alors il est let avec un nom. De plus, nous lisons la liste des définitions en utilisant la fonction delimited , car elles sont entre crochets et séparées par des virgules, et nous utilisons la fonction parse_vardef , qui est montrée ci-dessous. Ensuite, nous retournons un nœud de type call , qui appelle immédiatement une fonction nommée (IIFE). Les arguments de la fonction sont les variables définies par let , et le nœud d' call passera les valeurs comme arguments. Et, bien sûr, le corps de la fonction est lu à l'aide de parse_expression() .
S'il s'agit d'un let simple, alors nous retournons un noeud de type let avec les champs vars et body . Le champ vars contient un tableau de variables au format suivant: { name: VARIABLE, def: AST } , qui sont analysées par la fonction suivante:
function parse_vardef() { var name = parse_varname(), def; if (is_op("=")) { input.next(); def = parse_expression(); } return { name: name, def: def }; }
De plus, vous devez ajouter une vérification pour un nouveau type d'expression dans la fonction parse_atom :
Changements d'interprète
Puisque nous avons décidé de changer la structure de l'AST au lieu de la «casser» dans les anciens types de nœuds, nous devons ajouter le traitement de la nouvelle logique à l'interpréteur.
Afin d'ajouter la prise en charge du nom de fonction facultatif, nous modifions la fonction make_lambda :
function make_lambda(env, exp) { if (exp.name) {
Si la fonction a un nom, alors lorsque nous créons la fermeture, nous faisons une copie du contexte et ajoutons la fonction au contexte. Le reste reste le même.
Et enfin, pour traiter un nœud de type let , nous ajoutons le cas suivant à l'interpréteur:
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);
Notez que pour chaque variable, un nouveau contexte est créé dans lequel une nouvelle variable est ajoutée. Après cela, nous exécutons simplement le corps dans le dernier contexte.
Des exemples
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.
, , . , .
Conclusion
, . , - ; , , ? — JavaScript. , JavaScript — ? , , JavaScript, , , . JavaScript ( , ).
, , Lisp — : //. , , .. Lisp . Lisp let , , Lisp.
: JavaScript. Partie 3: interprète CPS