fluorite-8 実装の軌跡 Part 4 関数と識別子名管理

初回

←前回

今回の目標

今回は関数オブジェクトの生成と、その呼び出しが出来るようにします。

JavaScriptでいうと次のようなものです。

JavaScript

(function(a) {
  return a * 10;
})(123)

このコードでは、与えた引数を10倍にする関数に123を与えたので、1230が返ってきます。

ラムダ式を使うと、次のようになります。

JavaScript

(a => a * 10)(123)

この式をfluorite-8では次のように書けるようにします。

fl8

(a -> a * 10)(123)

関数オブジェクトの追加

目標

fl8

a -> a * 10

と書いたら、

JavaScript

(function(a) {
  return a * 10;
})

のようなものが出るようにします。

->は右優先結合で、結合優先度はこれまでで最弱です。

ごり押し

とりあえずごり押しで実装してみます。

通常の中置演算子と全く同じ手法で->演算子を追加します。->の左辺は通常の式ではありませんが、構文解析上は通常の式と同じ扱いにしておきます。

ごり押し

  registry.identifier = argument => {                    // 識別子トークンの挙動を登録
    if (argument === "PI") return "(" + Math.PI + ")";   // 内容がPIだった場合は円周率を出力する
    return "(" + argument + ")";                         // そうでない場合は内容をそのまま出力する
  };

  // ->トークンの挙動を登録
  // 単純な文字列結合
  registry.minus_greater = argument => "(function(" + argument[0].argument + ") {\n  return " + compile(argument[1]) + ";\n})";

ごり押し

Formula  = Lambda
Lambda   = head:(Add _ (
             "->" { return "minus_greater"; }
           ) _)* tail:Add {
             let result = tail;
             for (let i = head.length - 1; i >= 0; i--) {
               result = token(head[i][2], [head[i][0], result]);
             }
             return result;
           }
Add      = head:Term tail:(_ (
             "+" { return "plus"; }
           / "-" { return "minus"; }
           ) _ Term)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = token(tail[i][1], [result, tail[i][3]]);
             }
             return result;
           }

うまくいきました。fl8側のコード上で引数名を変えると、中間コード上の引数名も連動して変わります。identifierトークンの挙動を変えて未知の識別子をそのまま中間コードに渡すようにしたので、ちゃんとaと書いたらaとして扱われます。

識別子をそのままJavaScriptコードにするのは危険

識別子をそのままJavaScriptコードにする仕様のまま次のコードを実行するとどうなるでしょうか。

fl8

String + Number

実行すると、「変な文字列」になります。

この仕様では、以下のような問題が現れます。

• JavaScriptにおける予約語を識別子にすると中間コードが構文エラーになる。
• MathのようなJavaScriptで標準で提供される定数と同名の引数を取ることで、中間コードをバグらせることができる。
• evalのような危険なJavaScript関数にアクセスできる。

そこで、識別子辞書を作り、ソースコード上でaと入力しても中間コード上ではv_0のような無意味な識別子名になるようにします。

識別子辞書のために

ソースコード上でaと書いたらv_0が出て来るようにするためには、identifierトークンの挙動定義の段階で、識別子辞書が必要です。

識別子辞書は、変数・引数・組み込み定数のような名前で呼べる対象と、呼ぶ名前の対応を管理します。

現状のトークン挙動定義部分

  const registry = {};

  registry.identifier = argument => {
    /* この場所から識別子辞書が見えなければならない。 */
    if (argument === "PI") return "(" + Math.PI + ")";
    return "(" + argument + ")";
  };

  function compile(token) {
    return registry[token.type](token.argument);
  }

識別子辞書はどこで定義されるべきでしょうか？

ここで、compile関数の役割は何だったかを思い出してみましょう。compile関数の役割は、「構文木オブジェクトを入れると対応するJavaScript中間コードが出て来る」です。しかし構文木オブジェクトには識別子トークンが入ることがあります。そのような構文木オブジェクトをJavaScript中間コードに変換するには、識別子辞書が必要となります。すなわち、compile関数が動作するには構文木オブジェクトのほかに辞書が必要です。

compileが識別子辞書を要求するようにする

compile関数が環境オブジェクトenvを受け取り(1)、それをトークン挙動定義関数に渡します(2)。トークン挙動定義関数は、渡された環境オブジェクトを通じて識別子辞書を利用します(3)。

compileが辞書を要求するようになった

  const registry = {};

  registry.identifier = (env, argument) => {          // トークン挙動定義関数は環境オブジェクトを受け取る
    const code = env.resolveAlias(argument);          // (3) 環境オブジェクト経由で識別子辞書にアクセスできる
    if (code !== undefined) return code;              // 識別子が解決できた場合、成功
    throw new Error("Unknown identifier");            // 識別子が解決できなかった場合、エラー
  };

  function compile(env, token) {                      // (1) 構文木の評価には環境オブジェクトが必要
    return registry[token.type](env, token.argument); // (2)
  }

識別子辞書を与える環境オブジェクトの実装

環境オブジェクトenvは、構文木オブジェクトをコンパイルする際に必要な、構文木の外部から与えられる情報をまとめたオブジェクトです。

構文木の外部から与えられる情報には、今のところ次のものが相当します。

1. 識別子辞書
2. その時点で利用可能なUID

2は、v_0のような連番によって自動的に作られる識別子名が、どこまで作られたかを管理します。

---

識別子の名前は、スタック構造になったフレーム上に定義されます。

フレームには親子関係があり、子フレームは親フレーム上で定義された識別子を継承しつつ、上書きもできます。定義済みの識別子と同名の識別子を子フレームで定義すると、親フレームの識別子は見えなくなります。

これは、下記ではJavaScriptのprototype機能を使って実装されています。

ソースコード

  (a -> (b -> (a -> a + b + a + 1)(a + b) + 2)(a) + 3)(4) + 5
                  +--------------+
                  | a            |
            +-----+--------------+-----------+
            | b                              |
      +-----+--------------------------------+-------+
      | a                                            |
+-----+----------------------------------------------+----------+
|                                                               |
+---------------------------------------------------------------+

---

以下が具体的なコードです。

  class Environment {
    constructor() {
      this.nextUid = 0;                       // 次に発行するユニーク番号
      this.aliasFrame = Object.create(null);  // 識別子→コード　辞書
    }
    getNextUid() {                            // ユニークな番号を新規発行する
      return this.nextUid++;
    }
    registerAlias(alias, code) {              // 現在のフレームに識別子を登録する
      this.aliasFrame[alias] = code;
    }
    resolveAlias(alias) {                     // 識別子を解決する
      return this.aliasFrame[alias]; // prototypeによって親フレームが継承されている
    }
    pushAliasFrame() {                        // 識別子フレームを新規作成する
      this.aliasFrame = Object.create(this.aliasFrame);
    }
    popAliasFrame() {                         // 識別子フレームを1段階破棄する
      this.aliasFrame = Object.getPrototypeOf(this.aliasFrame);
    }
  }

Object.create(null)を使っているのは、__proto__のようなObject.prototypeで定義された名前を使っても困らないためです。

使い方としては、env.pushAliasFrame();して、色々env.registerAlias(alias, code);して識別子を登録した状態のenvをcompile関数に渡して構文木をコンパイルし、env.popAliasFrame();により元の状態に戻します。

env.getNextUid()は呼び出すごとに新しいUIDを発行してくれます。

compile関数の呼び出し部分

呼び出し部分も色々変わります。compile関数を初めて呼び出すRootでは、組み込み定数だけが入った環境オブジェクトを生成して与えます。

compileが環境を要求するようになった

Root     = _ main:Formula _ {
             const token = main;
             const env = new Environment();
             env.registerAlias("PI", "(" + Math.PI + ")");
             const code = compile(env, main)
             const result = eval(code);
             return [result, code, token];
           }

トークン挙動定義関数では、渡された環境オブジェクトenvを、子の構文木オブジェクトのcompile呼び出しの引数に渡します。

  registry.left_plus = (env, argument) => "(+" + compile(env, argument[0]) + ")";

ラムダ式が識別子辞書を扱うようにする

ラムダ式a -> a * 10の右辺a * 10をコンパイルするには、aという識別子をv_0のような中間コードに変換できなければなりません。そのために、ラムダ式の挙動定義関数内でフレームを作り、aという識別子を登録します。

何を登録するかというと、ラムダ式の引数が現れる度に新規発行されるUIDを含む識別子です。

また、登録後、右辺の評価が終わったらその識別子の登録を解除しなければなりません。

識別子辞書を利用するようになったラムダ式

  registry.minus_greater = (env, argument) => {
    const uid = env.getNextUid();                               // UIDを発行する
    env.pushAliasFrame();                                       // 識別子フレームを作る
    env.registerAlias(argument[0].argument, "(v_" + uid + ")"); // 識別子を登録する
    const code = "(function(v_" + uid + ") {\n  return " + compile(env, argument[1]) + ";\n})";
    env.popAliasFrame();                                        // 上で作った識別子フレームを破棄する
    return code;
  };

この章のまとめ

これで関数オブジェクトを作るラムダ演算子が出来ました。

この時点でのPEG.jsコードです。

**[開閉]**

{
  class Environment {
    constructor() {
      this.nextUid = 0;
      this.aliasFrame = Object.create(null);
    }
    getNextUid() {
      return this.nextUid++;
    }
    registerAlias(alias, code) {
      this.aliasFrame[alias] = code;
    }
    resolveAlias(alias) {
      return this.aliasFrame[alias];
    }
    pushAliasFrame() {
      this.aliasFrame = Object.create(this.aliasFrame);
    }
    popAliasFrame() {
      this.aliasFrame = Object.getPrototypeOf(this.aliasFrame);
    }
  }
  const registry = {};
  registry.integer = (env, argument) => "(" + parseInt(argument, 10) + ")";
  registry.identifier = (env, argument) => {
    const code = env.resolveAlias(argument);
    if (code !== undefined) return code;
    throw new Error("Unknown identifier");
  };
  registry.left_plus = (env, argument) => "(+" + compile(env, argument[0]) + ")";
  registry.left_minus = (env, argument) => "(-" + compile(env, argument[0]) + ")";
  registry.plus = (env, argument) => "(" + compile(env, argument[0]) + " + " + compile(env, argument[1]) + ")";
  registry.minus = (env, argument) => "(" + compile(env, argument[0]) + " - " + compile(env, argument[1]) + ")";
  registry.asterisk = (env, argument) => "(" + compile(env, argument[0]) + " * " + compile(env, argument[1]) + ")";
  registry.slash = (env, argument) => "(" + compile(env, argument[0]) + " / " + compile(env, argument[1]) + ")";
  registry.circumflex = (env, argument) => "(Math.pow(" + compile(env, argument[0]) + ", " + compile(env, argument[1]) + "))";
  registry.minus_greater = (env, argument) => {
    const uid = env.getNextUid();
    env.pushAliasFrame();
    env.registerAlias(argument[0].argument, "(v_" + uid + ")");
    const code = "(function(v_" + uid + ") {\n  return " + compile(env, argument[1]) + ";\n})";
    env.popAliasFrame();
    return code;
  };
  function compile(env, token) {
    return registry[token.type](env, token.argument);
  }
  function token(type, argument) {
    return {type, argument};
  }
}
Root     = _ main:Formula _ {
             const token = main;
             const env = new Environment();
             env.registerAlias("PI", "(" + Math.PI + ")");
             const code = compile(env, main)
             const result = eval(code);
             return [result, code, token];
           }
Formula  = Lambda
Lambda   = head:(Add _ (
             "->" { return "minus_greater"; }
           ) _)* tail:Add {
             let result = tail;
             for (let i = head.length - 1; i >= 0; i--) {
               result = token(head[i][2], [head[i][0], result]);
             }
             return result;
           }
Add      = head:Term tail:(_ (
             "+" { return "plus"; }
           / "-" { return "minus"; }
           ) _ Term)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = token(tail[i][1], [result, tail[i][3]]);
             }
             return result;
           }
Term  = head:Left tail:(_ (
             "*" { return "asterisk"; }
           / "/" { return "slash"; }
           ) _ Left)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = token(tail[i][1], [result, tail[i][3]]);
             }
             return result;
           }
Left     = head:((
             "+" { return "left_plus"; }
           / "-" { return "left_minus"; }
           ) _)* tail:Pow {
             let result = tail;
             for (let i = head.length - 1; i >= 0; i--) {
               result = token(head[i][0], [result]);
             }
             return result;
           }
Pow      = head:Factor _ operator:(
             "^" { return "circumflex"; }
           ) _ tail:Left {
             return token(operator, [head, tail]);
           }
         / Factor
Factor   = Integer
         / Identifier
         / Brackets
Integer  = main:$[0-9]+ {
             return token("integer", main);
           }
Identifier = main:$([a-zA-Z_] [a-zA-Z0-9_]*) {
             return token("identifier", main);
           }
Brackets = "(" _ main:Formula _ ")" {
             return main;
           }
_        = [ \t\r\n]*

ちゃんと入れ子の関数にできます。

関数呼び出しの追加

目標

以下の性質を持つ関数呼び出し演算子func(arg)を追加します。

1. func(arg)で関数オブジェクトfuncをargという引数で呼び出しできる。
2. -func(arg) ^ 2は-((func(arg)) ^ 2)と解釈される。
3. func(arg1)(arg2)は(func(arg1))(arg2)と解釈される。

argはとりあえず常に1個で固定です。

戦略

2より、関数呼び出しは符号およびべき乗よりも強い結合優先度を持ちます。

3より、関数呼び出し演算子は基底の部分の後に関数呼び出し部分が0個以上反復されたものです。つまり後置演算子に近いです。

実装

因子Factorとべき乗Powの間に後置系演算子をまとめたルールRightを作り、そこに関数呼び出し演算子を定義します。

実装

  registry.right_round = (env, argument) => "(" + compile(env, argument[0]) + "(" + compile(env, argument[1]) + "))";

実装

Pow      = head:Right _ operator:(
             "^" { return "circumflex"; }
           ) _ tail:Left {
             return token(operator, [head, tail]);
           }
         / Right
Right    = head:Factor tail:(_ (
             "(" _ main:Formula _ ")" { return ["right_round", main] }
           ))* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = token(tail[i][1][0], [result, tail[i][1][1]]);
             }
             return result;
           }

入れ子にした関数を多段で呼び出すことができます。関数に関数を渡すこともできるので、ループ的な構文も書けます（停止方法がないけど）。

テストケース

(a -> b -> c -> a * b + c)(5)(4)(3)

---

この世界の値には、現在数値と関数オブジェクトが存在します。数値と関数オブジェクトは特に区別されずに扱われるので、関数 + 関数のような式を書くと、変な感じの挙動になります。

これを解決するには、コンパイル時の型チェックや、実行時のチェックが必要となります。

三項演算子の追加

目標

以下の性質を持つ三項演算子a ? b : cを追加します。

1. a ? b : cと書いたら、JavaScriptの同様の演算子になる。
2. a ? b ? c : d : e ? f : gはa ? (b ? c : d) : (e ? f : g)と解釈される。
3. 結合優先度は加減算Addより弱く、ラムダ式Lambdaより強い。

戦略

2より、三項演算子の中辺と右辺にも三項演算子が来れることが分かります。べき乗と符号のような、特殊な結合ルールを持ったパターンです。

三項演算子のルールIfは、再帰的な定義によりIf = Add "?" If ":" If / Addとして定義されることができます。

実装

実装

  registry.ternary_question_colon = (env, argument) => "(" + compile(env, argument[0]) + " ? " + compile(env, argument[1]) + " : " + compile(env, argument[2]) + ")";

実装

Lambda   = head:(If _ (
             "->" { return "minus_greater"; }
           ) _)* tail:If {
             let result = tail;
             for (let i = head.length - 1; i >= 0; i--) {
               result = token(head[i][2], [head[i][0], result]);
             }
             return result;
           }
If       = head:Add _ "?" _ body:If _ ":" _ tail:If {
             return token("ternary_question_colon", [head, body, tail]);
           }
         / Add

できました。右優先結合になっています。

細かい挙動はJavaScriptの三項演算子の仕様に従います。

• 左辺が0以外のときに中辺、0のときに右辺が評価される。
• 評価されない方の辺は、計算そのものが行われない。

階乗を作ってみる

実はこの時点で階乗の計算ができます。

(f -> n -> f(f)(n))(f -> n -> n ? n * f(f)(n - 1) : 1)(  5  )

---

---

---

ちゃんと階乗になっています。

まとめ

ここまでに出来上がったPEG.jsコードです。

**[開閉]**

{
  class Environment {
    constructor() {
      this.nextUid = 0;
      this.aliasFrame = Object.create(null);
    }
    getNextUid() {
      return this.nextUid++;
    }
    registerAlias(alias, code) {
      this.aliasFrame[alias] = code;
    }
    resolveAlias(alias) {
      return this.aliasFrame[alias];
    }
    pushAliasFrame() {
      this.aliasFrame = Object.create(this.aliasFrame);
    }
    popAliasFrame() {
      this.aliasFrame = Object.getPrototypeOf(this.aliasFrame);
    }
  }
  const registry = {};
  registry.integer = (env, argument) => "(" + parseInt(argument, 10) + ")";
  registry.identifier = (env, argument) => {
    const code = env.resolveAlias(argument);
    if (code !== undefined) return code;
    throw new Error("Unknown identifier");
  };
  registry.left_plus = (env, argument) => "(+" + compile(env, argument[0]) + ")";
  registry.left_minus = (env, argument) => "(-" + compile(env, argument[0]) + ")";
  registry.right_round = (env, argument) => "(" + compile(env, argument[0]) + "(" + compile(env, argument[1]) + "))";
  registry.plus = (env, argument) => "(" + compile(env, argument[0]) + " + " + compile(env, argument[1]) + ")";
  registry.minus = (env, argument) => "(" + compile(env, argument[0]) + " - " + compile(env, argument[1]) + ")";
  registry.asterisk = (env, argument) => "(" + compile(env, argument[0]) + " * " + compile(env, argument[1]) + ")";
  registry.slash = (env, argument) => "(" + compile(env, argument[0]) + " / " + compile(env, argument[1]) + ")";
  registry.circumflex = (env, argument) => "(Math.pow(" + compile(env, argument[0]) + ", " + compile(env, argument[1]) + "))";
  registry.ternary_question_colon = (env, argument) => "(" + compile(env, argument[0]) + " ? " + compile(env, argument[1]) + " : " + compile(env, argument[2]) + ")";
  registry.minus_greater = (env, argument) => {
    const uid = env.getNextUid();
    env.pushAliasFrame();
    env.registerAlias(argument[0].argument, "(v_" + uid + ")");
    const code = "(function(v_" + uid + ") {\n  return " + compile(env, argument[1]) + ";\n})";
    env.popAliasFrame();
    return code;
  };
  function compile(env, token) {
    return registry[token.type](env, token.argument);
  }
  function token(type, argument) {
    return {type, argument};
  }
}
Root     = _ main:Formula _ {
             const token = main;
             const env = new Environment();
             env.registerAlias("PI", "(" + Math.PI + ")");
             const code = compile(env, main)
             const result = eval(code);
             return [result, code, token];
           }
Formula  = Lambda
Lambda   = head:(If _ (
             "->" { return "minus_greater"; }
           ) _)* tail:If {
             let result = tail;
             for (let i = head.length - 1; i >= 0; i--) {
               result = token(head[i][2], [head[i][0], result]);
             }
             return result;
           }
If       = head:Add _ "?" _ body:If _ ":" _ tail:If {
             return token("ternary_question_colon", [head, body, tail]);
           }
         / Add
Add      = head:Term tail:(_ (
             "+" { return "plus"; }
           / "-" { return "minus"; }
           ) _ Term)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = token(tail[i][1], [result, tail[i][3]]);
             }
             return result;
           }
Term  = head:Left tail:(_ (
             "*" { return "asterisk"; }
           / "/" { return "slash"; }
           ) _ Left)* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = token(tail[i][1], [result, tail[i][3]]);
             }
             return result;
           }
Left     = head:((
             "+" { return "left_plus"; }
           / "-" { return "left_minus"; }
           ) _)* tail:Pow {
             let result = tail;
             for (let i = head.length - 1; i >= 0; i--) {
               result = token(head[i][0], [result]);
             }
             return result;
           }
Pow      = head:Right _ operator:(
             "^" { return "circumflex"; }
           ) _ tail:Left {
             return token(operator, [head, tail]);
           }
         / Right
Right    = head:Factor tail:(_ (
             "(" _ main:Formula _ ")" { return ["right_round", main] }
           ))* {
             let result = head;
             for (let i = 0; i < tail.length; i++) {
               result = token(tail[i][1][0], [result, tail[i][1][1]]);
             }
             return result;
           }
Factor   = Integer
         / Identifier
         / Brackets
Integer  = main:$[0-9]+ {
             return token("integer", main);
           }
Identifier = main:$([a-zA-Z_] [a-zA-Z0-9_]*) {
             return token("identifier", main);
           }
Brackets = "(" _ main:Formula _ ")" {
             return main;
           }
_        = [ \t\r\n]*

この時点で次の特徴があります。

• ソースコードから構文木の生成
• 構文木から中間コードの生成
• 中間コードの評価
• スペース
• 整数リテラル
• 識別子
  • 定数
    • PI
  • 引数 (NEW)
• 演算子
  • 括弧
  • 関数呼び出し (NEW)
  • べき乗
  • 符号
  • 加減乗除
  • 三項演算子 (NEW)
  • ラムダ式 (NEW)

辛うじてプログラミング言語と言い張れるレベルになりました。

次回→