第12章プロジェクト: プログラミング言語
自分でプログラミング言語を作るのは、驚くほど簡単であり（高望みをしなければ）、非常に啓発的なことです。
この章で私が示したい主なことは、独自の言語を構築することに魔法は何も関わっていないということです。私は、人間の発明の中には非常に巧妙で複雑なものがあり、決して理解できないだろうと感じることがよくありました。しかし、少し読んだり実験したりすることで、それらは実際にはごくありふれたものであることがわかることが多いのです。
私たちは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); 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は、Eggがサポートする3つのアトミック要素（文字列、数値、および単語）を検出するために、3つの正規表現を使用します。パーサーは、どれが一致するかによって異なる種類のデータ構造を構築します。入力がこれらの3つの形式のいずれにも一致しない場合、それは有効な式ではなく、パーサーはエラーをスローします。例外コンストラクターとしてErrorの代わりにSyntaxErrorを使用します。これは、別の標準エラー型であり、より具体的であるためです。また、無効なJavaScriptプログラムを実行しようとしたときにスローされるエラー型でもあります。
次に、プログラム文字列から一致した部分を切り取り、式に対応するオブジェクトとともに、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のような特別な形式である場合、何も評価せず、引数式とスコープを、この形式を処理する関数に渡します。通常の呼び出しである場合は、演算子を評価し、それが関数であることを確認し、評価された引数を使用して呼び出します。
Eggの関数値を表すために、プレーンなJavaScript関数値を使用します。funという特別な形式が定義される後で、これについて再度説明します。
evaluateの再帰的な構造は、パーサーの同様の構造に似ており、どちらも言語自体の構造を反映しています。パーサーを評価器と統合し、解析中に評価することもできますが、このように分割することでプログラムがより明確になります。
これが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番目の引数の *いずれか* のみを評価する必要があるからです。
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; };
もう1つの基本的な構成要素は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() { if (arguments.length != params.length) { throw new TypeError("Wrong number of arguments"); } let localScope = Object.create(scope); for (let i = 0; i < arguments.length; i++) { localScope[params[i]] = arguments[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
コンパイル
私たちが構築したのはインタプリタです。評価中に、パーサーによって生成されたプログラムの表現に直接作用します。
*コンパイル*とは、プログラムの解析と実行の間にもう1つのステップを追加するプロセスで、可能な限り多くの作業を事前に行うことで、プログラムをより効率的に評価できるものに変換します。たとえば、適切に設計された言語では、束縛を使用するたびに、プログラムを実際に実行しなくても、どの束縛が参照されているかが明確です。これは、アクセスするたびに名前で束縛を検索するのを避け、代わりに事前に決定されたメモリ位置から直接フェッチするために使用できます。
従来、コンパイルでは、プログラムをコンピュータのプロセッサが実行できる生形式であるマシンコードに変換することが含まれます。しかし、プログラムを別の表現に変換するプロセスは、コンパイルと考えることができます。
Eggの代替評価戦略を作成することは可能でしょう。まず、プログラムをJavaScriptプログラムに変換し、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
これは通常、*ドメイン固有言語*と呼ばれ、狭い知識の領域を表現するように調整された言語です。そのような言語は、そのドメインで記述する必要があるものを正確に記述するように設計されており、それ以外のものは記述しないため、汎用言語よりも表現力が高くなります。
演習
配列
引数値を含む配列を構築するarray(...values)、配列の長さを取得するlength(array)、および配列からn番目の要素を取得するelement(array, n)という3つの関数をトップスコープに追加して、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のメカニズムを利用しています。特殊形式は、評価されるローカルスコープを渡され、そのスコープ内でサブフォームを評価できます。funによって返される関数は、それを囲む関数に渡されたscope引数にアクセスし、それを使って関数が呼び出されたときにローカルスコープを作成します。
これは、ローカルスコープのプロトタイプが関数が作成されたスコープになることを意味し、それによって関数からそのスコープ内のバインディングにアクセスすることが可能になります。これがクロージャの実装のすべてです（ただし、実際に効率的な方法でコンパイルするには、さらに作業が必要です）。
コメント
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.関数を使用することをお勧めします。また、スコープはObject.prototypeから派生しないため、hasOwnPropertyを呼び出す場合は、この厄介な式を使用する必要があることに注意してください。
Object.prototype.hasOwnProperty.call(scope, name);
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