第11章

プロジェクト：プログラミング言語

プログラミング言語における式の意味を決定する評価器は、単なる別のプログラムにすぎません。

データと制御のサイクルの本質について弟子が師に尋ねると、ユアン・マは「コンパイラが自身をコンパイルすることを考えよ」と答えた。

自身のプログラミング言語を構築することは、（あまり高い目標を掲げない限り）驚くほど簡単で、非常に啓発的です。

この章で私が示したい主なことは、独自の言語を構築することに魔法のようなものは何も無いということです。私は、いくつかの人間の発明が非常に賢く複雑で、理解することは決してできないだろうと感じてきました。しかし、少し読み、いじってみると、そのようなものはしばしば非常に平凡であることがわかります。

私たちはEggと呼ばれるプログラミング言語を構築します。それは小さく、単純な言語ですが、あなたが考えられるあらゆる計算を表現するのに十分な強力なものです。また、関数に基づく単純な抽象化も可能にします。

構文解析

プログラミング言語の最も目に見える部分は、その構文、または表記法です。パーサーは、テキストの一部を読み取り、そのテキストに含まれるプログラムの構造を反映するデータ構造を生成するプログラムです。テキストが有効なプログラムを形成しない場合、パーサーはエラーを指摘して文句を言う必要があります。

私たちの言語は、シンプルで均一な構文を持ちます。Eggのすべては式です。式は、変数、数値、文字列、または適用にすることができます。適用は、関数呼び出しだけでなく、ifやwhileなどの構造にも使用されます。

パーサーをシンプルに保つために、Eggの文字列はバックスラッシュエスケープのようなものをサポートしていません。文字列は、二重引用符で囲まれた、二重引用符ではない文字のシーケンスです。数値は数字のシーケンスです。変数名は、空白ではなく、構文で特別な意味を持たない任意の文字で構成できます。

適用は、JavaScriptと同じように記述され、式の後に括弧を付け、その括弧の間にコンマで区切られた任意の数の引数を持たせます。

do(define(x, 10),
   if(>(x, 5),
      print("large"),
      print("small")))

Egg言語の均一性により、JavaScriptでは演算子（>など）であるものは、この言語では他の関数のように適用される通常の変数になります。また、構文にはブロックの概念がないため、複数のことを順番に行うことを表すにはdo構造が必要です。

パーサーがプログラムを記述するために使用するデータ構造は、式オブジェクトで構成され、それぞれのオブジェクトには、それがどの種類の式であるかを示すtypeプロパティと、その内容を記述するその他のプロパティがあります。

型"value"の式は、リテラル文字列または数値を表します。それらのvalueプロパティには、それらが表す文字列または数値の値が含まれています。型"word"の式は、識別子（名前）に使用されます。このようなオブジェクトには、識別子の名前を文字列として保持するnameプロパティがあります。最後に、"apply"式は適用を表します。それらには、適用されている式を参照するoperatorプロパティと、引数式の配列を参照するargsプロパティがあります。

前のプログラムの>(x, 5)の部分は、このように表現されます。

{
  type: "apply",
  operator: {type: "word", name: ">"},
  args: [
    {type: "word", name: "x"},
    {type: "value", value: 5}
  ]
}

このようなデータ構造は、構文木と呼ばれます。オブジェクトをドットとして、オブジェクト間のリンクをドット間の線として想像すると、木のような形になります。式が他の式を含み、それがさらに他の式を含む可能性があるという事実は、枝が分岐し、再び分岐する方法に似ています。

これを、第9章の設定ファイル形式用に記述したパーサーと比較してください。これは、入力を行に分割し、それらの行を一度に1つずつ処理するというシンプルな構造を持っていました。行に許可される単純な形式はわずかしかありませんでした。

ここでは、異なるアプローチを見つける必要があります。式は行に分割されておらず、再帰的な構造を持っています。適用式は、他の式を含んでいます。

幸いなことに、この問題は、言語の再帰的な性質を反映した方法で再帰的なパーサー関数を記述することで、エレガントに解決できます。

関数parseExpressionを定義します。この関数は、文字列を入力として受け取り、文字列の先頭にある式のデータ構造と、この式の解析後に残った文字列の部分を含むオブジェクトを返します。サブ式（たとえば、適用の引数）を解析する場合、この関数を再度呼び出すことができ、引数式と残りのテキストが生成されます。このテキストには、さらに多くの引数を含めることも、引数のリストを終了する閉じ括弧にすることもできます。

これがパーサーの最初の部分です。

function parseExpression(program) {
  program = skipSpace(program);
  var match, expr;
  if (match = /^"([^"]*)"/.exec(program))
    expr = {type: "value", value: match[1]};
  else if (match = /^\d+\b/.exec(program))
    expr = {type: "value", value: Number(match[0])};
  else if (match = /^[^\s(),"]+/.exec(program))
    expr = {type: "word", name: match[0]};
  else
    throw new SyntaxError("Unexpected syntax: " + program);

  return parseApply(expr, program.slice(match[0].length));
}

function skipSpace(string) {
  var first = string.search(/\S/);
  if (first == -1) return "";
  return string.slice(first);
}

Eggは、要素間に任意の量の空白を許可するため、プログラム文字列の先頭から空白を繰り返し切り取る必要があります。これは、skipSpace関数が役立つ理由です。

先頭のスペースをスキップした後、parseExpressionは3つの正規表現を使用して、Eggがサポートする3つの単純な（原子）要素（文字列、数値、および単語）を特定します。パーサーは、どれが一致するかによって、異なる種類のデータ構造を構築します。入力がこれら3つの形式のいずれにも一致しない場合、それは有効な式ではなく、パーサーはエラーをスローします。SyntaxErrorは、無効なJavaScriptプログラムを実行しようとした場合に発生する標準のエラーオブジェクト型です。

次に、一致した部分をプログラム文字列から切り取り、式用のオブジェクトとともに、式が適用であるかどうかを確認するparseApplyに渡します。もしそうなら、括弧で囲まれた引数のリストを解析します。

function parseApply(expr, program) {
  program = skipSpace(program);
  if (program[0] != "(")
    return {expr: expr, rest: program};

  program = skipSpace(program.slice(1));
  expr = {type: "apply", operator: expr, args: []};
  while (program[0] != ")") {
    var arg = parseExpression(program);
    expr.args.push(arg.expr);
    program = skipSpace(arg.rest);
    if (program[0] == ",")
      program = skipSpace(program.slice(1));
    else if (program[0] != ")")
      throw new SyntaxError("Expected ',' or ')'");
  }
  return parseApply(expr, program.slice(1));
}

プログラム内の次の文字が開き括弧でない場合、これは適用ではなく、parseApplyは与えられた式を返すだけです。

それ以外の場合は、開き括弧をスキップし、この適用式の構文木オブジェクトを作成します。次に、閉じ括弧が見つかるまで、各引数を解析するためにparseExpressionを再帰的に呼び出します。再帰は、parseApplyとparseExpressionが互いに呼び出すことによって間接的に行われます。

適用式自体を適用できるため（multiplier(2)(1)など）、parseApplyは適用を解析した後、別の括弧のペアが続くかどうかを確認するために、自分自身を再度呼び出す必要があります。

これで、Eggを解析するために必要なものがすべて揃いました。式を解析した後に入力文字列の末尾に到達したことを確認し（Eggプログラムは単一の式です）、プログラムのデータ構造を提供する便利なparse関数でラップします。

function parse(program) {
  var result = parseExpression(program);
  if (skipSpace(result.rest).length > 0)
    throw new SyntaxError("Unexpected text after program");
  return result.expr;
}

console.log(parse("+(a, 10)"));
// → {type: "apply",
//    operator: {type: "word", name: "+"},
//    args: [{type: "word", name: "a"},
//           {type: "value", value: 10}]}

うまくいきました！失敗したときに非常に役立つ情報を提供せず、各式の開始位置の行と列を保存しません。これは後でエラーを報告する際に役立つ可能性がありますが、私たちの目的には十分です。

評価器

プログラムの構文木で何ができますか？もちろん、実行します！そして、それが評価器の役割です。構文木と、名前と値を関連付ける環境オブジェクトを与えると、木が表す式を評価し、これが生成する値を返します。

function evaluate(expr, env) {
  switch(expr.type) {
    case "value":
      return expr.value;

    case "word":
      if (expr.name in env)
        return env[expr.name];
      else
        throw new ReferenceError("Undefined variable: " +
                                 expr.name);
    case "apply":
      if (expr.operator.type == "word" &&
          expr.operator.name in specialForms)
        return specialForms[expr.operator.name](expr.args,
                                                env);
      var op = evaluate(expr.operator, env);
      if (typeof op != "function")
        throw new TypeError("Applying a non-function.");
      return op.apply(null, expr.args.map(function(arg) {
        return evaluate(arg, env);
      }));
  }
}

var specialForms = Object.create(null);

評価器には、各式の型に対するコードがあります。リテラル値式は、単にその値を生成します。（たとえば、式100は、単に数値100に評価されます。）変数の場合、それが環境内で実際に定義されているかどうかを確認し、もしそうであれば、変数の値を取得する必要があります。

適用はより複雑です。ifのような特殊な形式の場合、何も評価せず、環境とともに引数式をこの形式を処理する関数に渡すだけです。それが通常の呼び出しである場合、演算子を評価し、それが関数であることを確認し、引数を評価した結果を使用して呼び出します。

Eggの関数値を表すために、プレーンなJavaScript関数値を使用します。funと呼ばれる特殊な形式が定義されたら、この点については後で戻ってきます。

evaluateの再帰的な構造は、パーサーの同様の構造に似ています。どちらも言語自体の構造を反映しています。パーサーと評価器を統合し、解析中に評価することも可能ですが、このように分割することでプログラムがより読みやすくなります。

これがEggを解釈するために本当に必要なすべてです。とてもシンプルです。しかし、いくつかの特殊形式を定義し、環境にいくつかの便利な値を追加しないと、この言語で何もできません。

特殊形式

specialFormsオブジェクトは、Eggで特殊な構文を定義するために使用されます。これは、単語と、そのような特殊形式を評価する関数を関連付けます。現在、これは空です。いくつかの形式を追加しましょう。

specialForms["if"] = function(args, env) {
  if (args.length != 3)
    throw new SyntaxError("Bad number of args to if");

  if (evaluate(args[0], env) !== false)
    return evaluate(args[1], env);
  else
    return evaluate(args[2], env);
};

Eggのif構文は、厳密に3つの引数を期待します。最初に評価を行い、結果がfalseの値でなければ、2番目を評価します。そうでなければ、3番目が評価されます。このif形式は、JavaScriptのifよりもJavaScriptの三項演算子?:に似ています。これは文ではなく式であり、値、つまり2番目または3番目の引数の結果を生成します。

Eggは、ifへの条件値の処理方法がJavaScriptとは異なります。ゼロや空の文字列のようなものをfalseとして扱うのではなく、厳密な値falseのみをfalseとして扱います。

ifを通常の関数ではなく特殊形式として表現する必要がある理由は、関数へのすべての引数は関数が呼び出される前に評価されますが、ifは最初の値に応じて、2番目または3番目の引数のいずれかのみを評価する必要があるためです。

while形式も同様です。

specialForms["while"] = function(args, env) {
  if (args.length != 2)
    throw new SyntaxError("Bad number of args to while");

  while (evaluate(args[0], env) !== false)
    evaluate(args[1], env);

  // Since undefined does not exist in Egg, we return false,
  // for lack of a meaningful result.
  return false;
};

もう1つの基本的な構成要素はdoで、これはすべての引数を上から下へ実行します。その値は、最後の引数によって生成された値です。

specialForms["do"] = function(args, env) {
  var value = false;
  args.forEach(function(arg) {
    value = evaluate(arg, env);
  });
  return value;
};

変数を作成して新しい値を割り当てることができるように、defineという形式も作成します。これは、最初の引数として単語を、2番目の引数としてその単語に割り当てる値を生成する式を期待します。defineは、他のすべてのものと同様に式であるため、値を返す必要があります。割り当てられた値を返すようにします（JavaScriptの=演算子と同様）。

specialForms["define"] = function(args, env) {
  if (args.length != 2 || args[0].type != "word")
    throw new SyntaxError("Bad use of define");
  var value = evaluate(args[1], env);
  env[args[0].name] = value;
  return value;
};

環境

evaluateによって受け入れられる環境は、名前が変数名に対応し、値がそれらの変数にバインドされている値に対応するプロパティを持つオブジェクトです。グローバルスコープを表す環境オブジェクトを定義しましょう。

定義したばかりのif構文を使用できるようにするには、ブール値にアクセスできる必要があります。ブール値は2つしかないため、特別な構文は必要ありません。単純に2つの変数をtrueとfalseの値にバインドして使用します。

var topEnv = Object.create(null);

topEnv["true"] = true;
topEnv["false"] = false;

これで、ブール値を否定する簡単な式を評価できます。

var prog = parse("if(true, false, true)");
console.log(evaluate(prog, topEnv));
// → false

基本的な算術演算子と比較演算子を提供するために、いくつかの関数値を環境に追加します。コードを短く保つために、すべてを個別に定義するのではなく、ループでnew Functionを使用して、多数の演算子関数を合成します。

["+", "-", "*", "/", "==", "<", ">"].forEach(function(op) {
  topEnv[op] = new Function("a, b", "return a " + op + " b;");
});

値を出力する方法も非常に便利なので、console.logを関数でラップしてprintと呼びます。

topEnv["print"] = function(value) {
  console.log(value);
  return value;
};

これで、簡単なプログラムを作成するのに十分な基本的なツールが揃いました。次のrun関数は、プログラムを作成して実行するのに便利な方法を提供します。これは、新しい環境を作成し、指定された文字列を単一のプログラムとして解析および評価します。

function run() {
  var env = Object.create(topEnv);
  var program = Array.prototype.slice
    .call(arguments, 0).join("\n");
  return evaluate(parse(program), env);
}

Array.prototype.slice.callの使用は、argumentsなどの配列のようなオブジェクトを、joinを呼び出すことができる実際の配列に変換するトリックです。runに与えられたすべての引数を取り、それらをプログラムの行として扱います。

run("do(define(total, 0),",
    "   define(count, 1),",
    "   while(<(count, 11),",
    "         do(define(total, +(total, count)),",
    "            define(count, +(count, 1)))),",
    "   print(total))");
// → 55

これは、以前に何度か見たことがあるプログラムであり、Eggで表現された1から10までの数の合計を計算します。明らかに同等のJavaScriptプログラムよりも見苦しいですが、150行未満のコードで実装された言語としては悪くありません。

関数

関数のないプログラミング言語は、実に貧弱なプログラミング言語です。

幸いなことに、fun構文を追加するのは難しくありません。この構文は、最後の引数を関数の本体として扱い、その前のすべての引数を関数の引数の名前として扱います。

specialForms["fun"] = function(args, env) {
  if (!args.length)
    throw new SyntaxError("Functions need a body");
  function name(expr) {
    if (expr.type != "word")
      throw new SyntaxError("Arg names must be words");
    return expr.name;
  }
  var argNames = args.slice(0, args.length - 1).map(name);
  var body = args[args.length - 1];

  return function() {
    if (arguments.length != argNames.length)
      throw new TypeError("Wrong number of arguments");
    var localEnv = Object.create(env);
    for (var i = 0; i < arguments.length; i++)
      localEnv[argNames[i]] = arguments[i];
    return evaluate(body, localEnv);
  };
};

Eggの関数には、JavaScriptと同様に独自のローカル環境があります。Object.createを使用して、外部環境（そのプロトタイプ）の変数にアクセスできるだけでなく、その外部スコープを変更せずに新しい変数を含めることができる新しいオブジェクトを作成します。

fun形式で作成された関数は、このローカル環境を作成し、そこに引数変数を追加します。次に、この環境で関数本体を評価し、結果を返します。

run("do(define(plusOne, fun(a, +(a, 1))),",
    "   print(plusOne(10)))");
// → 11

run("do(define(pow, fun(base, exp,",
    "     if(==(exp, 0),",
    "        1,",
    "        *(base, pow(base, -(exp, 1)))))),",
    "   print(pow(2, 10)))");
// → 1024

コンパイル

作成したのはインタープリターです。評価中に、パーサーによって生成されたプログラムの表現に直接作用します。

コンパイルは、プログラムの解析と実行の間に別のステップを追加するプロセスであり、可能な限り事前に多くの作業を行うことで、より効率的に評価できるものにプログラムを変換します。たとえば、適切に設計された言語では、変数の使用ごとに、実際にプログラムを実行することなく、どの変数が参照されているかが明らかです。これは、アクセスするたびに名前で変数を検索するのを回避し、あらかじめ決められたメモリ位置から直接フェッチするために使用できます。

伝統的に、コンパイルには、プログラムを、コンピューターのプロセッサーが実行できる生の形式であるマシンコードに変換することが含まれます。ただし、プログラムを別の表現に変換するプロセスはすべて、コンパイルと考えることができます。

Eggの代替評価戦略を作成することも可能です。最初にプログラムをJavaScriptプログラムに変換し、new Functionを使用してJavaScriptコンパイラを呼び出し、結果を実行します。正しく行われれば、これはEggを非常に高速に実行させながら、実装は非常に単純になります。

このトピックに興味があり、時間を費やす意思がある場合は、練習としてそのようなコンパイラを実装してみてください。

チート

ifとwhileを定義したとき、それらがJavaScript自身のifとwhileの多かれ少なかれ些細なラッパーであることに気づいたかもしれません。同様に、Eggの値は通常の古いJavaScriptの値にすぎません。

JavaScriptの上に構築されたEggの実装と、マシンによって提供される生の機能の上に直接プログラミング言語を構築するために必要な作業量と複雑さを比較すると、その違いは非常に大きいです。それでも、この例は、プログラミング言語がどのように機能するかについての印象を与えてくれることを願っています。

何かを成し遂げるとなると、チートはすべてを自分でやるよりも効果的です。この章のトイ言語は、JavaScriptでより良くできることは何もしていませんが、小さな言語を作成することが実際の作業を完了するのに役立つ状況はあります。

このような言語は、一般的なプログラミング言語に似ている必要はありません。JavaScriptに正規表現が装備されていなかった場合は、そのようなサブ言語用に独自のパーサーと評価器を作成できます。

または、巨大なロボット恐竜を構築していて、その動作をプログラムする必要があると想像してください。JavaScriptは、これを行うのに最も効果的な方法ではないかもしれません。代わりに、次のような言語を選択するかもしれません。

behavior walk
  perform when
    destination ahead
  actions
    move left-foot
    move right-foot

behavior attack
  perform when
    Godzilla in-view
  actions
    fire laser-eyes
    launch arm-rockets

これは通常、ドメイン固有言語と呼ばれるものであり、特定の狭い知識ドメインを表現するように調整された言語です。このような言語は、そのドメインで表現する必要のあるものを正確に表現するように設計されており、それ以外は何も表現しないため、汎用言語よりも表現力が高い場合があります。

演習

配列

次の3つの関数をトップスコープに追加して、配列のサポートをEggに追加します。引数の値を含む配列を構築するarray(...)、配列の長さを取得するlength(array)、配列からn番目の要素をフェッチするelement(array, n)。

// Modify these definitions...

topEnv["array"] = "...";

topEnv["length"] = "...";

topEnv["element"] = "...";

run("do(define(sum, fun(array,",
    "     do(define(i, 0),",
    "        define(sum, 0),",
    "        while(<(i, length(array)),",
    "          do(define(sum, +(sum, element(array, i))),",
    "             define(i, +(i, 1)))),",
    "        sum))),",
    "   print(sum(array(1, 2, 3))))");
// → 6

クロージャ

funを定義した方法では、Eggの関数が周囲の環境を「クロージャ」できるため、関数本体は、関数が定義されたときに表示されていたローカル値を使用できます。これはJavaScript関数と同様です。

次のプログラムは、これを示しています。関数fは、引数をfの引数に追加する関数を返します。つまり、変数aを使用できるようにするには、f内のローカルスコープにアクセスする必要があります。

run("do(define(f, fun(a, fun(b, +(a, b)))),",
    "   print(f(4)(5)))");
// → 9

fun形式の定義に戻って、これが機能する原因となるメカニズムを説明してください。

コメント

Eggでコメントを記述できると便利です。たとえば、ハッシュ記号（#）を見つけた場合は常に、行の残りの部分をコメントとして扱い、JavaScriptの//と同様に無視できます。

これをサポートするために、パーサーに大きな変更を加える必要はありません。skipSpaceを、コメントを空白のようにスキップするように変更するだけで、skipSpaceが呼び出されるすべてのポイントで、コメントもスキップされるようになります。この変更を行ってください。

// This is the old skipSpace. Modify it...
function skipSpace(string) {
  var first = string.search(/\S/);
  if (first == -1) return "";
  return string.slice(first);
}

console.log(parse("# hello\nx"));
// → {type: "word", name: "x"}

console.log(parse("a # one\n   # two\n()"));
// → {type: "apply",
//    operator: {type: "word", name: "a"},
//    args: []}

スコープの修正

現在、変数に値を代入する唯一の方法はdefineです。この構造は、新しい変数を定義する手段と、既存の変数に新しい値を代入する手段の両方として機能します。

この曖昧さが問題を引き起こします。非ローカル変数に新しい値を代入しようとすると、代わりに同じ名前のローカル変数を定義してしまうことになります。（一部の言語は仕様としてこのように動作しますが、私は常にこれがスコープを扱う愚かな方法だと考えています。）

defineと同様の特殊形式setを追加してください。これは、変数に新しい値を代入し、内側のスコープに存在しない場合は、外側のスコープの変数を更新します。変数がまったく定義されていない場合は、ReferenceError（これも標準的なエラータイプです）をスローします。

これまで便利だったスコープを単純なオブジェクトとして表現する手法は、この時点で少し邪魔になるかもしれません。オブジェクトのプロトタイプを返すObject.getPrototypeOf関数を使ってみると良いでしょう。また、スコープはObject.prototypeから派生したものではないため、hasOwnPropertyを呼び出したい場合は、この扱いにくい式を使う必要があることを覚えておいてください。

Object.prototype.hasOwnProperty.call(scope, name);

これは、ObjectプロトタイプからhasOwnPropertyメソッドを取得し、それをスコープオブジェクトに対して呼び出します。

specialForms["set"] = function(args, env) {
  // Your code here.
};

run("do(define(x, 4),",
    "   define(setx, fun(val, set(x, val))),",
    "   setx(50),",
    "   print(x))");
// → 50
run("set(quux, true)");
// → Some kind of ReferenceError