こんにちは JavaScriptプログラミング言語を実装するためのガイド、 PLチュートリアルの翻訳の第2部を紹介します。

翻訳者から

独自のプログラミング言語-λ言語 （元の言語 -λanguage）を作成します。 作成のプロセスでは、再帰降下、コントロール転送スタイル、基本的な最適化手法など、多くの興味深い手法を使用します。 インタプリタの2つのバージョンが作成されます-通常のインタプリタとCPSインタプリタ、JavaScriptのトランスコンパイラ。

オリジナルの作者は、有名なUglifyJSライブラリ（JSコードを最小化およびフォーマットするためのツール）の作者であるMihai Bazonです。

PSインタプリタとコンパイラにバグがあります： a() && b()またはa() || b()ような式で a() || b()両方の部分が常に実行されます。 もちろん、これは間違ってa() &&演算子に対してa()偽であるか、 ||に対して偽ではないためです。 、 b()値は何の役割も果たしません。 これを修正するのは難しくありません。

シンプルな通訳

前のパートでは、 InputStream 、 TokenStreamおよびparse 3つの関数をTokenStreamしました。 コードからASTを取得するには、次のコードを使用します。

 var ast = parse(TokenStream(InputStream(code))); 

インタプリタの記述は、パーサーよりも簡単です。ツリーを再帰的に走査し、通常の順序で式を実行するだけです。

コンテキスト（ Environment ）

適切なコードを実行するには、コンテキストが必要です。これは、特定の場所にあるすべての変数を含むオブジェクトです。 evaluate関数の引数として渡されます。

ラムダノードに入るたびに、コンテキストに新しい変数を追加する必要があります-関数の引数。 引数が外部ブロックからの変数と重複する場合、関数を終了した後に変数の古い値を復元する必要があります。

これを行う最も簡単な方法は、JavaScriptプロトタイプ継承を使用することです。 新しい関数を入力すると、新しいコンテキストを作成し、外部コンテキストをそのプロトタイプとして設定し、新しいコンテキストで関数を呼び出します。 このおかげで、私たちには何もありません-外部のコンテキストでは、その変数はすべて残ります。

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); //          if (!scope && this.parent) throw new Error("Undefined variable " + name); return (scope || this).vars[name] = value; }, def: function(name, value) { return this.vars[name] = value; } }; 

Environmentオブジェクトには、外部コンテキストを指すparentフィールドがあります。 グローバルコンテキストの場合はnullになります。 varsフィールドがあり、このコンテキストに属するすべての変数があります。 グローバルコンテキストの場合、空のオブジェクト（ Object.create(null) ）および非グローバルコンテキストの親コンテキストの変数のコピー（ Object.create(parent.vars) ）にすぐに等しくなります。

いくつかの方法があります：

• extend() -現在のコンテキストをコピーします。
• lookup(name)というnameの変数name定義されているコンテキストを見つけます。
• get(name) -nameというname変数の値を取得します。 変数が定義されていない場合、例外をスローします。
• set(name, value) -変数の値を設定します。 このメソッドは、変数が定義されているコンテキストを探します。 定義されておらず、グローバルコンテキストにない場合、例外がスローされます。
• def(name, value) -現在のコンテキストで変数を作成（またはオーバーラップまたはオーバーライド）します。

evaluate関数

Environmentオブジェクトができたので、次に主な問題の解決に進みます。 この関数は、送信ノードのタイプに応じていくつかのアクションを実行する大きなswitchブロックになります。

 function evaluate(exp, env) { switch (exp.type) { 

リテラルの場合、単にその値を返します。

  case "num": case "str": case "bool": return exp.value; 

変数はコンテキストから取得されます（変数の名前はvalueフィールドに含まれていvalue ）。

  case "var": return env.get(exp.value); 

割り当てるには、左側に変数の名前（ノードvar ）があることを確認する必要があります。 そうでない場合は、単に例外をスローします（変数以外への代入はサポートしていません）。 次に、 env.setを使用して変数の値を設定します。 式の右辺は、 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)); 

タイプがbinaryノードの場合、両方のオペランドに演算子を適用する必要があります。 apply_op関数は後で記述します。 また、式の両方の部分に対してevaluateを呼び出します。

  case "binary": return apply_op(exp.operator, evaluate(exp.left, env), evaluate(exp.right, env)); 

lambda型のノードは通常のJavaScriptクロージャーを返すため、JavaScriptからでも通常の関数のように呼び出すことができます。 make_lambda関数を追加しました。これについては後で説明します。

  case "lambda": return make_lambda(env, exp); 

ifノードの実行if非常に簡単です。最初に条件の値を見つけます。 falseでない場合は、 thenブランチの値を返します。 それ以外の場合、 elseブランチがある場合、その値、または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; 

progノードは一連の式です。 すべての式を順番に実行し、後者の値を取得します（空のシーケンスの値はfalse ）。

  case "prog": var val = false; exp.prog.forEach(function(exp){ val = evaluate(exp, env) }); return val; 

callタイプのノードの場合、関数を呼び出す必要があります。 その前に、関数自体の値を見つけ、すべての引数の値を見つけ、 applyを使用して関数を呼び出しapply 。

  case "call": var func = evaluate(exp.func, env); return func.apply(null, exp.args.map(function(arg){ return evaluate(arg, env); })); 

ここには到達しませんが、パーサーに新しいノードタイプを追加し、インタープリターに追加するのを忘れた場合は、次のようにします。

  default: throw new Error("I don't know how to evaluate " + exp.type); } } 

これが通訳の主要部分でした。 上記では、まだ実装していない2つの関数を使用したので、始めましょう。

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); } 

演算子のタイプと引数を受け取ります。 シンプルで直感的なswitch 。 変数のような任意の値をとることができるJavaScriptとは異なり、意味をなさないものもです。 算術演算子のオペランドは数値であり、ゼロによる除算を許可しないことが必要です。 文字列については、後で何かを考えます。

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; } 

上記のように、渡されたコンテキストとAST関数を使用する通常のJavaScript関数を返します。 すべての作業は、関数自体が呼び出されたときにのみ実行されます。コンテキストが作成され、引数が設定されます（十分でない場合はfalseになりfalse ）。 次に、関数の本体が新しいコンテキストで実行されます。

ネイティブ関数

ご覧のとおり、私たちの言語のJavaScriptとやり取りする方法はありませんでした。 以前はprintおよびprintln関数を使用していましたが、どこにも定義していませんでした。 JavaScriptで記述し、グローバルコンテキストに追加するだけです。

そのようなコードの例を次に示します。

 //  -   var code = "sum = lambda(x, y) x + y; print(sum(2, 3));"; // ,  parse  TokenStream,      InputStream var ast = parse(TokenStream(InputStream(code))); //    var globalEnv = new Environment(); //  ""  "print" globalEnv.def("print", function(txt){ console.log(txt); }); //  evaluate(ast, globalEnv); //  5 

全コード

これまでに作成したすべてのコードをダウンロードできます 。 NodeJSを使用して起動できます。 コードを標準ストリームに渡すだけです：

 echo 'sum = lambda(x, y) x + y; println(sum(2, 3));' | node lambda-eval1.js 

コード例

私たちのプログラミング言語は、シンプルですが、一般的にコンピューターで解決できる問題を（理論的には）解決できます。 これは、私よりも賢い男-アロンゾチャーチとアランチューリング-が一度、λ計算（ラムダ計算）がチューリングマシンに相当し、λ言語がλ計算を実装することを証明したためです。

これは、たとえ私たちの言語に機会がなくても、すでに持っているものを使って同じことを実現できることを意味します。 または、これが困難な場合は、別の言語のインタープリターを作成できます。

サイクル

再帰があればループは問題になりません。 再帰の上に実装されたループの例をすでに示しました。 もう一度試してみましょう。

 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); 

しかし、ここで問題があります。たとえば、反復回数を1000に増やすと、600の後に「Maximum call stack size exceeded」というエラーが表示されます。これは、インタープリターが再帰的で再帰が最大深度に達するために発生します。

これは深刻な問題ですが、解決策があります。 繰り返しのために（ forまたはwhile ）新しいコンストラクトを追加したいのですが、それらを使わずにやってみましょう。 再帰はきれいに見えるので、それを残しましょう。 この制限を回避する方法については後で説明します。

データ構造（その欠如）

λ言語には、数値、文字列、ブール型の3種類のデータがあります。 配列やオブジェクトなどの複雑なタイプを作成することは不可能に思えるかもしれません。 しかし、これはtatではありません。もう1つのタイプがあります：function。 λ計算に従うと、継承を含めて、オブジェクトを含む任意のデータ構造を作成できることがわかります。

リストの例で示します。 2つの値を含むオブジェクトを作成するcons関数があるとします。 このオブジェクトを「セル」または「ペア」と呼びましょう。 値の1つに「car」、もう1つに「cdr」という名前を付けます。 Lispではそう呼ばれているからです。 オブジェクト「セル」がある場合、関数carおよびcdrを使用してその値を取得できます。

 x = cons(10, 20); print(car(x)); #  10 print(cdr(x)); #  20 

これで、リストを簡単に定義できます。

リストは、「car」の最初の要素と「cdr」の残りの要素を含むペアです。 しかし、 `cdr`には1つの値しか含めることができません！ この値はリストになります。 リストは、「car」の最初の要素と「cdr」の残りの要素を含むペアです。 しかし、 `cdr`には1つの値しか含めることができません！ この値はリストになります。 [...]

これは再帰的なデータ型です。 しかし、1つの問題が残っています。いつ停止する必要があるのでしょうか。 論理的には、 cdrが空のリストになったら停止する必要があります。 しかし、空のリストとは何ですか？ これを行うには、「NIL」という新しいオブジェクトを追加しましょう。 ペアとして使用できます（ cdrとcdrを使用できますが、結果はNILそのものになります）。 それでは、アイテム1、2、3、4、5のリストを作成しましょう。

 x = cons(1, cons(2, cons(3, cons(4, cons(5, NIL))))); print(car(x)); # 1 print(car(cdr(x))); # 2  Lisp  . cadr print(car(cdr(cdr(x)))); # 3 caddr print(car(cdr(cdr(cdr(x))))); # 4 cadddr print(car(cdr(cdr(cdr(cdr(x)))))); # 5     . 

このための特別な構文がない場合、ひどく見えます。 しかし、これは既存のλ言語機能を使用して実行できることを示したかっただけです。 実装は次のとおりです。

 cons = λ(a, b) λ(f) f(a, b); car = λ(cell) cell(λ(a, b) a); cdr = λ(cell) cell(λ(a, b) b); NIL = λ(f) f(NIL, NIL); 

この方法で作成されたcons / car / cdrを最初に見たとき、 ifが1つも必要ないことに驚きました（ただし、元のλ計算にないという事実を考えると、これは奇妙なことではありません）。 もちろん、この方法でこれを行うプログラミング言語はありません。なぜなら、それは非常に非効率的だからです。しかし、λ計算をそれほど美しくしません。 明確な言語では、このコードは次のことを行います。

• cons関数は2つの値（ aおよびb ）を取り、それらを保持する関数を返します。 その関数は、ペアのまさにオブジェクトです。 彼女は引数を取り、ペアの両方の値に対して呼び出します。
• car関数は、渡された引数を呼び出し、最初の引数を返す関数を渡します。
• cdr関数はcdr関数と同じですが、唯一の違いは、渡された関数が2番目の引数を返すことです。
• NIL関数はconsと同じように機能しますが、NILに等しい2つの値を持つペアを返します。

 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)); # 1 println(car(cdr(x))); # 2 println(car(cdr(cdr(x)))); # 3 println(car(cdr(cdr(cdr(x))))); # 4 println(car(cdr(cdr(cdr(cdr(x)))))); # 5 

リストには、再帰的に実装でき、論理的に見える多くのアルゴリズムがあります。 たとえば、次の関数は、リストアイテムごとに渡された関数を呼び出します。

 foreach = λ(list, f) if list != NIL { f(car(list)); foreach(cdr(list), f); }; foreach(x, println); 

そして、ここに番号の範囲のリストを作成する別のものがあります：

 range = λ(a, b) if a <= b then cons(a, range(a + 1, b)) else NIL; #     1  8 foreach(range(1, 8), λ(x) println(x * x)); 

上記で実装したリストは不変です（リストの作成後にcdrまたはcdr変更することはできません）。 ほとんどのLispには、ペアを変更する機能があります。 Schemeでは、これらはset-car!と呼ばset-car! / set-cdr! 。 Common Lispでは、 rplaca / rplacd 。 今回は、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); #  NIL     NIL = cons(0, 0); set-car!(NIL, NIL); set-cdr!(NIL, NIL); ## : x = cons(1, 2); println(car(x)); # 1 println(cdr(x)); # 2 set-car!(x, 10); set-cdr!(x, 20); println(car(x)); # 10 println(cdr(x)); # 20 

これは、可変データ構造を実装できることを示しています。 私はそれがどのように機能するかについて深くは述べませんが、それはコードから明らかです。

さらに進んでオブジェクトを実装することもできますが、構文を変更しないと実行が困難になります。 別の方法は、トークナイザー/パーサーに新しい構文を実装し、インタープリターに処理を追加することです。 すべての主要なプログラミング言語がこれを行い、通常のパフォーマンスを達成する必要があります。 記事の次の部分で新しい構文を追加します。

[翻訳者から：ラムダ計算に興味があるなら、このトピックに特化したHabréのクールな記事があります： JavaScriptのラムダ計算 ]。

新しい構文構成

λ言語には、かなりの構文構造があります。 たとえば、新しい変数を直接追加する方法はありません。 前にも言ったように、IIFEを使用する必要があるため、次のようになります。

 (λ(x, y){ (λ(z){ ## it gets worse when one of the vars depends on another print(x + y + z); })(x + y); })(2, 3); 

letキーワードを追加します。 これにより、次のような記述が可能になります。

 let (x = 2, y = 3, z = x + y) print(x + y + z); 

letブロック内の各変数について、同じブロックからでも以前の変数が利用可能でなければなりません。 したがって、上記のコードは次のコードと同等になります。

 (λ(x){ (λ(y){ (λ(z){ print(x + y + z); })(x + y); })(3); })(2); 

これらの変更は、パーサーで直接行うことができ、インタープリターでの変更は不要です。 新しいletノードを追加する代わりに、それをcallノードとlambda変えることができます。 これは、言語に意味的な変更を加えなかったことを意味します-これは「構文糖」と呼ばれ、これを以前に存在したASTノードに変換する操作は「シュガーレス」（元：「脱糖」）と呼ばれます。

ただし、とにかくパーサーを変更する必要があります。 より効率的に解釈できるため、新しい「let」ノードを追加しましょう（クロージャーを作成してすぐに呼び出す必要はなく、コンテキストをコピーして変更するだけです）。

また、Schemeにあった「let named」のサポートを追加します。 ループの作成が簡単になります。

 print(let loop (n = 10) if n > 0 then n + loop(n - 1) else 0); 

これは、10 + 9 + ... + 0の合計をカウントする「再帰的な」ループです。以前は、次のようにする必要がありました。

 print((λ(loop){ loop = λ(n) if n > 0 then n + loop(n - 1) else 0; loop(10); })()); 

また、これを簡単にするために、「名前付き関数」の構文を追加します。 次のようになります。

 print((λ loop (n) if n > 0 then n + loop(n - 1) else 0) (10)); 

このために行う必要がある変更：

• lambdaキーワードの後のオプション名のサポート。 存在する場合は、関数自体を指す変数を現在のコンテキストに追加する必要があります。 これは、JavaScriptで名前を持つ関数とまったく同じです。
• 新しいletキーワードのサポート。 次に、オプションの名前と、コンマで区切られたfoo = EXPRESSIONという形式の変数定義のリスト（空の場合もあります）が来ます。 let式の本体は単一の式です（もちろん、一連の式にすることもできます）。

パーサーの変更

最初に、トークナイザーの小さな変更、 letキーワードをキーワードのリストに追加します。

 var keywords = " let if then else lambda λ true false "; 

オプションの名前を読み取るparse_lambda関数を変更します。

 function parse_lambda() { return { type: "lambda", name: input.peek().type == "var" ? input.next().value : null, //   vars: delimited("(", ")", ",", parse_varname), body: parse_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(), }; } 

これは2つのケースを処理します。 let後にvarトークンがある場合、これは名前付きのletです。 さらに、括弧で囲まれ、カンマで区切られているため、 delimited関数を使用して定義のリストを読み取り、 parse_vardef示すparse_vardef関数を使用します。 次に、タイプcallノードを返しcall 。これは、（IIFE）という名前の関数をすぐに呼び出します。 関数の引数はletで定義された変数であり、 callノードは値を引数として渡します。 そして、もちろん、関数の本体はparse_expression()を使用してparse_expression()ます。

これが単純なletである場合、 varsフィールドとbodyフィールドを持つlet型のノードを返します。 varsフィールドには、次の形式の変数の配列が含まれます： { name: VARIABLE, def: AST } 、これらは次の関数によって解析されます：

 function parse_vardef() { var name = parse_varname(), def; if (is_op("=")) { input.next(); def = parse_expression(); } return { name: name, def: def }; } 

また、新しいタイプの式のチェックをparse_atom関数にparse_atomます。

 //      parse_if if (is_kw("let")) return parse_let(); 

通訳の変更

ASTの構造を古いタイプのノードに「クラッキング」する代わりに変更することにしたため、インタープリターに新しいロジックの処理を追加する必要があります。

オプションの関数名のサポートを追加するには、 make_lambda関数を変更します。

 function make_lambda(env, exp) { if (exp.name) { //  env = env.extend(); //  env.def(exp.name, lambda); //  } //  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; } 

関数に名前がある場合、クロージャーを作成するときに、コンテキストのコピーを作成し、関数をコンテキストに追加します。 残りは同じままです。

最後に、 let型のノードを処理するために、インタープリターに次のケースを追加します。

 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); 

各変数に対して、新しい変数が追加される新しいコンテキストが作成されることに注意してください。 その後、最後のコンテキストで本体を実行するだけです。

例

 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); #   ..     let # print(x + y + z); let (x = 10) { let (x = x * 2, y = x * x) { println(x); ## 20 println(y); ## 400 }; println(x); ## 10 }; 

— .

. , , , . 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.

, , . , .

おわりに

, . , - ; , , ? — JavaScript. , JavaScript — ? , , JavaScript, , , . JavaScript ( , ).

, , Lisp — : //. , , .. Lisp . Lisp let , , Lisp.

: JavaScript. 3: CPS-