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

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

独自のプログラミング言語を作ることは、驚くほど簡単です（あまり高度なものを目指さなければ）。そして非常に有益です。

この章で主に示したいのは、プログラミング言語の構築に魔法は一切含まれていないということです。私はしばしば、人間の発明の中には、あまりに巧妙で複雑すぎて理解できないものがあると感じてきました。しかし、少し読んで実験してみると、多くの場合、それらは非常にありふれたものであることが分かります。

私たちはEggというプログラミング言語を構築します。それは小さくシンプルな言語ですが、考えられるあらゆる計算を表現できるだけの能力を持っています。関数に基づいた単純な抽象化を可能にします。

構文解析

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

私たちの言語は、シンプルで統一された構文を持ちます。Eggではすべてが式です。式は、バインディングの名前、数値、文字列、または適用にすることができます。適用は関数呼び出しに使用されますが、ifやwhileなどの構成要素にも使用されます。

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

適用は、JavaScriptと同様に、式の後に括弧を置き、それらの括弧間に任意の数の引数をコンマで区切って記述します。

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

Egg言語の統一性とは、JavaScriptにおける演算子（>など）がこの言語では通常のバインディングであり、他の関数と同様に適用されることを意味します。構文にブロックの概念がないため、複数の処理を順番に実行するdo構成要素が必要です。

パーサーがプログラムを記述するために使用するデータ構造は、expressionオブジェクトで構成され、それぞれには、それがどのような種類の式であるかを示す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);
  let 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) {
  let first = string.search(/\S/);
  if (first == -1) return "";
  return string.slice(first);
}

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

先頭の空白をスキップした後、parseExpressionは3つの正規表現を使用して、Eggがサポートする3つの原子要素（文字列、数値、単語）を検出します。パーサーは、どの式が一致するかによって、異なる種類のデータ構造を構築します。入力がこれらの3つの形式のいずれにも一致しない場合、それは有効な式ではなく、パーサーはエラーをスローします。ここではSyntaxErrorコンストラクターを使用します。これは、Errorと同様に標準によって定義された例外クラスですが、より具体的です。

次に、プログラム文字列から一致した部分を切り取り、式に対するオブジェクトとともにparseApplyに渡します。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] != ")") {
    let 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を解析できます。式を解析した後に入力文字列の末尾に到達したことを確認する便利なparse関数でラップします（Eggプログラムは単一の式です）。そして、プログラムのデータ構造を得ます。

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

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

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

評価器

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

const specialForms = Object.create(null);

function evaluate(expr, scope) {
  if (expr.type == "value") {
    return expr.value;
  } else if (expr.type == "word") {
    if (expr.name in scope) {
      return scope[expr.name];
    } else {
      throw new ReferenceError(
        `Undefined binding: ${expr.name}`);
    }
  } else if (expr.type == "apply") {
    let {operator, args} = expr;
    if (operator.type == "word" &&
        operator.name in specialForms) {
      return specialForms[operator.name](expr.args, scope);
    } else {
      let op = evaluate(operator, scope);
      if (typeof op == "function") {
        return op(...args.map(arg => evaluate(arg, scope)));
      } else {
        throw new TypeError("Applying a non-function.");
      }
    }
  }
}

評価器には、各式のタイプに対するコードがあります。リテラル値式は、その値を生成します。（たとえば、式100は数値100になります。）バインディングの場合、それが実際にスコープ内で定義されているかどうかを確認し、定義されている場合は、バインディングの値を取得する必要があります。

適用はさらに複雑です。ifのような特別な形式の場合、何も評価しません。引数の式とスコープを、この形式を処理する関数に渡すだけです。通常の呼び出しの場合、演算子を評価し、それが関数であることを確認し、評価された引数で呼び出します。

プレーンなJavaScript関数の値を使用して、Eggの関数の値を表します。特別な形式funが定義されるとき、後でこれに戻ります。

evaluateの再帰的な構造は、パーサーの構造と似ており、どちらも言語自体の構造を反映しています。パーサーと評価器を1つの関数に結合し、解析中に評価することも可能ですが、このように分割することで、プログラムはより明確で柔軟になります。

これは、Eggを解釈するために本当に必要なすべてです。それほど簡単です。しかし、いくつかの特別な形式を定義し、環境にいくつかの便利な値を追加しないと、この言語ではまだあまり多くのことはできません。

特別な形式

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

specialForms.if = (args, scope) => {
  if (args.length != 3) {
    throw new SyntaxError("Wrong number of args to if");
  } else if (evaluate(args[0], scope) !== false) {
    return evaluate(args[1], scope);
  } else {
    return evaluate(args[2], scope);
  }
};

Eggのif構成要素は、正確に3つの引数を期待します。最初の引数を評価し、結果が値falseでない場合、2番目の引数を評価します。そうでない場合、3番目の引数が評価されます。このif形式は、JavaScriptのifよりもJavaScriptの三項?:演算子により似ています。それは式であり、ステートメントではなく、値（つまり、2番目または3番目の引数の結果）を生成します。

Eggは、`if`文の条件値の扱いにおいてもJavaScriptとは異なります。`false`という値のみを偽として扱い、ゼロや空文字列などは偽とは見なしません。

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

`while`形式も同様です。

specialForms.while = (args, scope) => {
  if (args.length != 2) {
    throw new SyntaxError("Wrong number of args to while");
  }
  while (evaluate(args[0], scope) !== false) {
    evaluate(args[1], scope);
  }

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

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

specialForms.do = (args, scope) => {
  let value = false;
  for (let arg of args) {
    value = evaluate(arg, scope);
  }
  return value;
};

バインディングを作成し、新しい値を与えるために、`define`と呼ばれる形式も作成します。これは、最初の引数として単語を、そしてその単語に代入する値を生成する式を2番目の引数として期待します。`define`は他のすべてと同様に式であるため、値を返す必要があります。JavaScriptの`=`演算子と同様に、代入された値を返すようにします。

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

環境

`evaluate`で受け入れられるスコープは、プロパティ名とバインディング名、プロパティ値とバインディング値が対応するオブジェクトです。グローバルスコープを表すオブジェクトを定義しましょう。

先ほど定義した`if`構造を使用するには、ブール値にアクセスする必要があります。ブール値は2つしかないため、特別な構文は必要ありません。単に2つの名前に`true`と`false`の値をバインドして使用します。

const topScope = Object.create(null);

topScope.true = true;
topScope.false = false;

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

let prog = parse(`if(true, false, true)`);
console.log(evaluate(prog, topScope));
// → false

基本的な算術演算子と比較演算子を提供するために、いくつかの関数値をスコープに追加します。コードを短く保つために、個別に定義する代わりに、ループ内で`Function`を使用して一連の演算子関数を合成します。

for (let op of ["+", "-", "*", "/", "==", "<", ">"]) {
  topScope[op] = Function("a, b", `return a ${op} b;`);
}

値を出力する方法も有用なので、`console.log`を関数でラップして`print`と呼びます。

topScope.print = value => {
  console.log(value);
  return value;
};

これで、単純なプログラムを作成するための十分な基本的なツールが揃いました。次の関数は、プログラムを解析し、新しいスコープで実行する便利な方法を提供します。

function run(program) {
  return evaluate(parse(program), Object.create(topScope));
}

ネストされたスコープを表すためにオブジェクトのプロトタイプチェーンを使用します。これにより、プログラムはトップレベルのスコープを変更せずにローカルスコープにバインディングを追加できます。

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

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

関数

関数が無いプログラミング言語は、貧弱なプログラミング言語と言えるでしょう。幸いにも、最後の引数を関数の本体として扱い、それより前のすべての引数を関数の引数の名前として扱う`fun`コンストラクトを追加するのは難しくありません。

specialForms.fun = (args, scope) => {
  if (!args.length) {
    throw new SyntaxError("Functions need a body");
  }
  let body = args[args.length - 1];
  let params = args.slice(0, args.length - 1).map(expr => {
    if (expr.type != "word") {
      throw new SyntaxError("Parameter names must be words");
    }
    return expr.name;
  });

  return function(...args) {
    if (args.length != params.length) {
      throw new TypeError("Wrong number of arguments");
    }
    let localScope = Object.create(scope);
    for (let i = 0; i < args.length; i++) {
      localScope[params[i]] = args[i];
    }
    return evaluate(body, localScope);
  };
};

Eggの関数は、独自のローカルスコープを持ちます。`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プログラムに変換し、`Function`を使用してJavaScriptコンパイラを呼び出し、その結果を実行する代替評価戦略を書くことができます。正しく行えば、これはEggを非常に高速に実行しながら、実装も非常にシンプルになります。

このトピックに興味があり、時間をかける意思があれば、このようなコンパイラを実装することを練習としてお勧めします。

ズル

`if`と`while`を定義したとき、それらがJavaScript独自の`if`と`while`のほぼ自明なラッパーであることに気付いたかもしれません。同様に、Eggの値はただの通常のJavaScript値です。プロセッサが理解する機械語のようなよりプリミティブなシステムへのギャップを埋めるには、より多くの努力が必要ですが、その動作はここで行っていることと似ています。

この章のトイ言語は、JavaScriptでより良くできないことは何もしていませんが、小さな言語を書くことで実際の作業が進む状況はあります。

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

あるいは、解析する必要がある言語の論理的な記述を提供することで、パーサーをすばやく作成できるようにするプログラムを構築していると想像してみてください。それのために特定の表記法と、それをパーサープログラムにコンパイルするコンパイラを定義できます。

expr = number | string | name | application

number = digit+

name = letter+

string = '"' (! '"')* '"'

application = expr '(' (expr (',' expr)*)? ')'

これは通常、ドメイン固有言語と呼ばれ、狭い知識領域に合わせて調整された言語です。このような言語は、そのドメインで記述する必要があるものだけを記述するように設計されているため、汎用言語よりも表現力豊かになります。

演習

配列

トップスコープに次の3つの関数 `array(...values)`（引数の値を含む配列を作成する）、`length(array)`（配列の長さを取得する）、`element(array, n)`（配列からn番目の要素を取得する）を追加することで、Eggに配列のサポートを追加します。

// Modify these definitions...

topScope.array = "...";

topScope.length = "...";

topScope.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) {
  let 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.hasOwnを使用できることを忘れないでください。

specialForms.set = (args, scope) => {
  // 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