More than 3 years have passed since last update.

fluorite-8　実装の軌跡　Part 10　静的型と静的オーバーロード

fluorite-8

Posted at 2020-12-13

初回

←前回

今回の目標

四則演算が重い

前回の実行時ライブラリの導入によって、次のコードは以下のようにコンパイルされるようになりました。

fl8

1 + 2 * (3 - 4) / 5

中間コード

const v_4 = Symbol("<root>(OnlineDemo,L:33,C:3)");
const v_5 = {[v_4]: function(library) {
  const v_0 = library.sub((3), (4), "(OnlineDemo,L:33,C:12)");
  const v_1 = library.mul((2), (v_0), "(OnlineDemo,L:33,C:7)");
  const v_2 = library.div((v_1), (5), "(OnlineDemo,L:33,C:17)");
  const v_3 = library.add((1), (v_2), "(OnlineDemo,L:33,C:3)");
  return (v_3);
}}[v_4];
(v_5)

四則演算の部分だけ抜き出すとこうです。

中間コード：四則演算の部分だけ

const v_0 = library.sub((3), (4), "(OnlineDemo,L:33,C:12)");
const v_1 = library.mul((2), (v_0), "(OnlineDemo,L:33,C:7)");
const v_2 = library.div((v_1), (5), "(OnlineDemo,L:33,C:17)");
const v_3 = library.add((1), (v_2), "(OnlineDemo,L:33,C:3)");
v_3

library.addの中身は次のようになっています。

library.add

    add(a, b, location) {
      if (typeof a !== "number") throw new Error("" + a + " is not a number " + location);
      if (typeof b !== "number") throw new Error("" + b + " is not a number " + location);
      return a + b;
    },

元のコードが1 + 2 * (3 - 4) / 5という4回の演算子呼び出しで終わっているのに対して、中間コードでは、

libraryから3引数のメソッドを呼び出す
左辺に対して型チェックを行う
右辺に対して型チェックを行う
四則演算の演算子を呼び出す

という4回の演算を行っており、実行速度の点で気になります。

library.sub((3), (4), "～～")という部分は両辺が数値であることは分かり切っているので、単に3 + 4のように書きたいです。さらに3 + 4という式の値も数値であることが確定するので、それが代入されたv_0を使ったlibrary.mul((2), (v_0), "～～")という部分も単に2 * (v_0)のように直接演算子を書きたいです。

目標

型を静的に管理して、数値同士の四則演算は中間コード上に直接演算子が現れるようにします。

論理値と文字列も同様に静的に型を管理します。関数型や配列型といった複雑な型はまだ扱いません。

fl8

1 + 2 * (3 - 4) / 5

中間コード：目標

const v_4 = Symbol("<root>(OnlineDemo,L:33,C:3)");
const v_5 = {[v_4]: function(library) {
  const v_0 = (3) - (4);
  const v_1 = (2) * (v_0);
  const v_2 = (v_1) / (5);
  const v_3 = (1) + (v_2);
  return (v_3);
}}[v_4];
(v_5)

いくつかの組み込み定数の追加

目標

論理値のリテラルとして次の組み込み定数を追加します。

TRUE
FALSE

また、ついでに次の組み込み定数も追加しておきます。

UNDEFINED
NULL
INFINITY
NAN

これらはJavaScript上の同様のキーワードを直接中間コード上に配置します。

これによりfl8の世界に論理値やundefinedなどのいくつかの新しい型の値がもたらされます。

実装

PIの下に色々追加します。

customizeEnvironment内に追加

    // TRUEという識別子が来たら(true)という中間コードにする
    env.registerAlias("TRUE", {
      get: (env, token) => toOperation("", "(true)"),
    });
    env.registerAlias("FALSE", {
      get: (env, token) => toOperation("", "(false)"),
    });
    env.registerAlias("UNDEFINED", {
      get: (env, token) => toOperation("", "(undefined)"),
    });
    env.registerAlias("NULL", {
      get: (env, token) => toOperation("", "(null)"),
    });
    env.registerAlias("INFINITY", {
      get: (env, token) => toOperation("", "(Infinity)"),
    });
    env.registerAlias("NAN", {
      get: (env, token) => toOperation("", "(NaN)"),
    });

Githubリポジトリ

ソースコードも長くなってきたので、ついにfluorite-8のリポジトリをオープンしました。

https://github.com/MirrgieRiana/fluorite-8/tree/part10

まだライセンスのファイルLICENSEとPEG.jsコードfluorite8.pegjsしかありません。

この章の実装は次のコミットで示されます。

テスト

呼び出すことが出来ました。

fl8

[PI; TRUE; FALSE; UNDEFINED; NULL; INFINITY; NAN]

中間コード上ではどこかで定義された定数にアクセスしているわけではなく直接値が書かれているので、どちらかというと定数というよりも識別子の姿をしたリテラルや演算子が近いです。

中間コード

const v_1 = Symbol("<root>(OnlineDemo,L:33,C:1)");
const v_2 = {[v_1]: function(library) {
  const v_0 = [];
  v_0[v_0.length] = (3.141592653589793);
  v_0[v_0.length] = (true);
  v_0[v_0.length] = (false);
  v_0[v_0.length] = (undefined);
  v_0[v_0.length] = (null);
  v_0[v_0.length] = (Infinity);
  v_0[v_0.length] = (NaN);
  return (v_0);
}}[v_1];
(v_2)

キャスト演算子`+value` `-value` `?value` `!value` `&value`追加

目標

ここでは次の仕様を満たす「キャスト演算子」を追加します。

+valueと書くとvalueを数値に変換する。
-valueと書くとvalueを数値に変換し、その負の値を返す。
?valueと書くとvalueを論理値に変換する。
!valueと書くとvalueを論理値に変換し、その否定を返す。
&valueと書くとvalueを文字列に変換する。

変換方式の定義です。

変換元＼変換先	数値	論理値	文字列
数値	そのまま	0またはNaNなら、偽それ以外の場合、真	無限大なら`INFINITY` 負の無限大なら`-INFINITY` 非数なら`NAN` それ以外の場合、 `toString`メソッドを呼び出す
論理値	真なら1 偽なら0	そのまま	真なら`TRUE` 偽なら`FALSE`
文字列	大文字小文字の区別なく `INFINITY`なら無限大 `-INFINITY`なら負の無限大 `NAN`なら非数それ以外の場合、 `parseFloat`関数を呼び出す	空文字列なら、偽それ以外の場合、真	そのまま

前置+および-はこれまで符号の演算子でしたが、ここで演算子の意味が数値化・数値化の負に変わります。

元ネタと考察

fl8のキャスト演算子は、Rakuにおける同様の演算子である前置+ - ? !に似通った見た目と、JavaにおけるtoStringメソッドに似通った仕様と、C言語等における(int) valueのようなキャスト演算子に似通った性質を持ちます。

2.1. 一般的な演算子 - Raku 入門

文字列を表す記号が&なのは、Visual Basicの文字列連結演算子の&が元ネタです。

fl8では、
+は数値を足し合わせる記号であり、値を数値に変換する記号でもあります。
&は文字列を足し合わせる記号であり、値を文字列に変換する記号でもあります。

ちなみに、これらの演算子を後置演算子として定義すると(a)+(b)が(n1)+(n2)なのか(func)+(arg)なのか混乱が発生します。

実際にJavaでは(Integer) - (10)のような構文で同様の問題が生じており、Integerの部分をintにすると異なる構文木が生成されるようになっています。

実装

新しい演算子の文法を定義します。

改変後

Left     = head:((
             "+" { return ["left_plus", location()]; }
           / "-" { return ["left_minus", location()]; }
           / "?" { return ["left_question", location()]; }    // 追加された
           / "!" { return ["left_exclamation", location()]; } // 追加された
           / "&" { return ["left_ampersand", location()]; }   // 追加された
           / "$#" { return ["left_dollar_hash", location()]; }
           ) _)* tail:Pow {
             let result = tail;
             for (let i = head.length - 1; i >= 0; i--) {
               result = token(head[i][0][0], [result], head[i][0][1]);
             }
             return result;
           }

演算子の挙動を定義します。

改変前

    env.registerOperatorHandler("get", "left_plus", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const uid = env.getNextUid();
      return toOperation(
        o1.head + "const v_" + uid + " = library.toPositive(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "left_minus", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const uid = env.getNextUid();
      return toOperation(
        o1.head + "const v_" + uid + " = library.toNegative(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });

↓

改変前


    env.registerOperatorHandler("get", "left_plus", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const uid = env.getNextUid();
      return toOperation(
        //           この演算子の意味は「正にする」から「数値化する」に変わった
        //                                           ↓
        o1.head + "const v_" + uid + " = library.toNumber(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    env.registerOperatorHandler("get", "left_minus", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const uid = env.getNextUid();
      return toOperation(
        //                               ↓数値化し、負にするの意味
        o1.head + "const v_" + uid + " = -library.toNumber(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    // 論理値化も追加
    env.registerOperatorHandler("get", "left_question", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const uid = env.getNextUid();
      return toOperation(
        o1.head + "const v_" + uid + " = library.toBoolean(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    // 論理値化して否定する演算子も追加
    env.registerOperatorHandler("get", "left_exclamation", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const uid = env.getNextUid();
      return toOperation(
        o1.head + "const v_" + uid + " = !library.toBoolean(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });
    // 文字列化も追加
    env.registerOperatorHandler("get", "left_ampersand", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const uid = env.getNextUid();
      return toOperation(
        o1.head + "const v_" + uid + " = library.toString(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });

実行時ライブラリの内容も対応します。

改変前

    toPositive(number, location) {
      if (typeof number !== "number") throw new Error("" + number + " is not a number " + location);
      return number;
    },
    toNegative(number, location) {
      if (typeof number !== "number") throw new Error("" + number + " is not a number " + location);
      return -number;
    },

↓

改変後

    toNumber(value, location) {
      // 数値の数値化はそのまま返す
      if (typeof value === "number") return value;
      // 文字列の数値化はparseFloatする
      if (typeof value === "string") {
        if (value.length === 8 && value.toUpperCase() === "INFINITY") return Infinity;
        if (value.length === 9 && value.toUpperCase() === "-INFINITY") return -Infinity;
        if (value.length === 3 && value.toUpperCase() === "NAN") return NaN;
        return parseFloat(value);
      }
      // 論理値の数値化は1と0
      if (typeof value === "boolean") return value ? 1 : 0;
      // それ以外の値の数値化はエラー
      throw new Error("" + value + " cannot convert to number " + location);
    },
    toBoolean(value, location) {
      // 論理値の論理値化はそのまま返す
      if (typeof value === "boolean") return value;
      // 数値の論理値化は0とNaN以外かどうか
      if (typeof value === "number") return !(value === 0 || Number.isNaN(value));
      // 文字列の論理値化は空文字でないかどうか
      if (typeof value === "string") return value !== "";
      // それ以外の値の論理値化はエラー
      throw new Error("" + value + " cannot convert to boolean " + location);
    },
    toString(value, location) {
      // 文字列の文字列化はそのまま返す
      if (typeof value === "string") return value;
      // 数値の文字列化はtoStringを呼び出す
      if (typeof value === "number") {
        if (value === Infinity) return "INFINITY";
        if (value === -Infinity) return "-INFINITY";
        if (Number.isNaN(value)) return "NAN";
        return value.toString();
      }
      // 論理値の文字列化はTRUEとFALSE
      if (typeof value === "boolean") return value ? "TRUE" : "FALSE";
      // それ以外の値の文字列化はエラー
      throw new Error("" + value + " cannot convert to string " + location);
    },

テスト

fl8コードinに対して、実際にJavaScript内に生成された値outの対応表です。

**[開閉]**

fl8

[
  +0;
  +1;
  +INFINITY;
  +-INFINITY;
  +NAN;
  +FALSE;
  +TRUE;
  +'';
  +'0';
  +'3.14';
  -0;
  -1;
  -INFINITY;
  --INFINITY;
  -NAN;
  -FALSE;
  -TRUE;
  -'';
  -'0';
  -'3.14';
  ?0;
  ?1;
  ?INFINITY;
  ?-INFINITY;
  ?NAN;
  ?FALSE;
  ?TRUE;
  ?'';
  ?'0';
  ?'3.14';
  !0;
  !1;
  !INFINITY;
  !-INFINITY;
  !NAN;
  !FALSE;
  !TRUE;
  !'';
  !'0';
  !'3.14';
  &0;
  &1;
  &INFINITY;
  &-INFINITY;
  &NAN;
  &FALSE;
  &TRUE;
  &'';
  &'0';
  &'3.14'
]

また、特殊な数値を表す文字列も正しく数値型の値に変換されています。

**[開閉]**

fl8

[
  +'infinity';
  +'-infinity';
  +'nan';
  +'Infinity';
  +'-Infinity';
  +'Nan';
  +'InFiNiTy';
  +'-InFiNiTy';
  +'nAn';
  +'INFINITY';
  +'-INFINITY';
  +'NAN'
]

これでキャスト演算子が完成しました。

式が静的に型を持つようにする

fl8では整数リテラルはどのような内容でも必ず数値型の値を生成することにします。これに反するような機能（整数リテラルが複素数オブジェクトを生成するなど）を追加したい場合は、拡張された環境カスタマイザー（今のcustomizeEnvironment関数の亜種）を導入して実現させることにします。

すると、整数リテラルは数値型を持つと静的に確定します。その情報をコンパイル時に管理し、静的な最適化に活用します。

コンパイル時に管理される型を静的型と呼ぶことにします。

戦略

整数リテラルの構文木オブジェクトはget文脈ドメインでコンパイルされると中間コードを生成するための前文headと本文bodyを含むオブジェクトを返しますが、さらにここに本文の型を与えるプロパティtypeを追加します。

get挙動オブジェクトの例

{
  head: "const v_0 = (50);\n",
  body: "(v_0)",
  type: {
    name: "number"
  }
}

実装

`toOperation`系関数の改変

挙動オブジェクトを生成する関数に対して次の4個の改変をしました。

toOperationの名前をtoOperationGetに変更
各関数をクラス化してコンストラクタを呼び出すように変更
- それに伴い名前からtoが消えた
OperationGetクラスに静的型を管理するtypeプロパティとセッターを追加
OperationSetクラスにおいてsuggestedNameはセッターで与えるように変更

改変前

    function toOperation(head/* string */, body/* string */) {
      return {head, body};
    }
    function toOperationSet(accept/* operationGet => operationRun */, suggestedName = undefined/* string */) {
      return {accept, suggestedName};
    }
    function toOperationArray(generate/* operationSet => operationRun */) {
      return {generate};
    }
    function toOperationRun(head/* string */) {
      return {head};
    }

↓

改変後

    // 関数からコンストラクタに変わった
    class OperationGet {         // Getが追加された
      constructor(head/* string */, body/* string */) {
        this.head = head;
        this.body = body;
        this.setType("any");     // 静的型の初期値はany
      }
      // 静的型を与えるセッター
      setType(name/* string */, argument = {}/* object */) {
        this.type = {name, ...argument};
        return this;
      }
    }
    class OperationSet {
      // 省略可能な推測名を取らなくなった
      constructor(accept/* operationGet => operationRun */) {
        this.accept = accept;
        this.setSuggestedName(undefined);
      }
      // 推測名を与えるセッター
      setSuggestedName(suggestedName/* string */) {
        this.suggestedName = suggestedName;
        return this;
      }
    }
    class OperationArray {
      constructor(generate/* operationSet => operationRun */) {
        this.generate = generate;
      }
    }
    class OperationRun {
      constructor(head/* string */) {
        this.head = head;
      }
    }

これに合わせて呼び出し側もコンストラクタを呼び出すように置換します。具体的にはtoOperation～の呼び出しがnew Operation～となります。

上記の改変ではOperationGet#setTypeはnameとargumentに分けて呼び出す仕様にしていましたが、これでは型をコピーするときに不便なので第一引数がオブジェクトだった場合はそのまま代入することにします。

改変前

      setType(name/* string */, argument = {}/* object */) {
        this.type = {name, ...argument};
        return this;
      }

↓

改変後

      setType(name/* string */, argument = {}/* object */) {
        if (typeof name === "object") { // nameの型によって挙動を変える
          this.type = name;
        } else {
          this.type = {name, ...argument};
        }
        return this;
      }

生成されるget挙動オブジェクトは次のようなものです。

例

operationGet = {
  head: "const v_0 = (50);\n",
  body: "(v_0)",
  type: {
    name: "number"
  }
}

operationGet.typeオブジェクトには関数の戻り値の型のような「型引数」がプロパティとして別途追加される可能性があります。operationGet.type.nameは型の情報が無い場合はanyという文字列になっています。

静的型の一覧です。

静的型	`operationGet.type.name`
静的型情報なし	`any`
数値型	`number`
論理値型	`boolean`
文字列型	`string`

これ以外の型は複雑なので今は扱いません。

とりあえずこれで式は静的に型を持てるようになりました。

整数・文字列リテラルと論理値組み込み定数を静的型に対応させる

手始めに数値・論理値・文字列を生み出すもっとも原始的な式を静的型に対応させてみます。

実装

静的型の付与にはOperationGet#setTypeを呼び出せばいいので、そのままセッターメソッドをメソッドチェーン的に呼び出すように改変します。

改変前

    env.registerOperatorHandler("get", "integer", (env, token) => new OperationGet("", "(" + parseInt(token.argument, 10) + ")"));
    env.registerOperatorHandler("get", "string", (env, token) => new OperationGet("", "(" + JSON.stringify(token.argument) + ")"));

    env.registerAlias("TRUE", {
      get: (env, token) => new OperationGet("", "(true)"),
    });
    env.registerAlias("FALSE", {
      get: (env, token) => new OperationGet("", "(false)"),
    });

↓

改変後

    env.registerOperatorHandler("get", "integer", (env, token) => new OperationGet("", "(" + parseInt(token.argument, 10) + ")").setType("number"));
    env.registerOperatorHandler("get", "string", (env, token) => new OperationGet("", "(" + JSON.stringify(token.argument) + ")").setType("string"));

    env.registerAlias("TRUE", {
      get: (env, token) => new OperationGet("", "(true)").setType("boolean"),
    });
    env.registerAlias("FALSE", {
      get: (env, token) => new OperationGet("", "(false)").setType("boolean"),
    });

これで静的型を提供してくれるトークンが生まれました。

キャスト演算子を静的型と静的オーバーロードに対応させる

オーバーロードとは、一般に、同一の見た目を持つ関数や演算子の動作を複数定義して、型等によって実際に呼び出される動作を切り替えることです。

fl8では今までこれをライブラリ関数内で実行時（動的）に行っていましたが、ここではその判定をコンパイル時（静的）に行うように改変します。コンパイル時に動作を解決するオーバーロードを静的オーバーロードと呼ぶことにします。

戦略

キャスト演算子は前置+ - ? ! &の5種類でした。これらの演算子は、それぞれ次のライブラリ関数の呼び出しを行っています。

演算子	ライブラリ関数の呼び出し
前置`+`	`library.toNumber`
前置`-`	`-library.toNumber`
前置`?`	`library.toBoolean`
前置`!`	`!library.toBoolean`
前置`&`	`library.toString`

呼び出されるライブラリ関数の中では、次のようにif分岐が大量に並んでいます。

    toNumber(value, location) {
      if (typeof value === "number") return value;
      if (typeof value === "string") {
        if (value.length === 8 && value.toUpperCase() === "INFINITY") return Infinity;
        if (value.length === 9 && value.toUpperCase() === "-INFINITY") return -Infinity;
        if (value.length === 3 && value.toUpperCase() === "NAN") return NaN;
        return parseFloat(value);
      }
      if (typeof value === "boolean") return value ? 1 : 0;
      throw new Error("" + value + " cannot convert to number " + location);
    },

この中で、ライブラリ関数を呼び出すまでもないような処理、例えば論理値の数値化value ? 1 : 0や数値の数値化valueは、事前に型が分かっているなら中間コード上にインライン展開した方が良いです。

逆に数値と文字列のやり取りは無限大や非数の扱いが異なるため、少し長い処理になっています。またどうせ最後にparseFloatやtoStringのような別の重い関数を呼ぶことになってオーバーヘッドは大して変わらないため、インライン展開してもそれほど美味しくないです。

よって、ここでは次のキャストのパターンを静的オーバーロードすることにします。

同じ型へのキャスト
- 数値→数値
- 論理値→論理値
- 文字列→文字列
論理値と他とのやり取り
- 論理値→数値
- 論理値→文字列
- 数値→論理値
- 文字列→論理値

実装

前置+のみ掲載します。

改変前

    env.registerOperatorHandler("get", "left_plus", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const uid = env.getNextUid();
      return new OperationGet(
        o1.head + "const v_" + uid + " = library.toNumber(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      );
    });

↓

改変後

    env.registerOperatorHandler("get", "left_plus", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      if (o1.type.name === "number") {  // 項が数値の場合、
        return o1;                      // 何もせずそのまま返す
                                        // ※setTypeするまでもなくo1.type.nameは既にnumber
      }
      if (o1.type.name === "boolean") { // 論理値の場合
        const uid = env.getNextUid();
        return new OperationGet(
                                        // 三項演算子をインラインで置く
          o1.head + "const v_" + uid + " = " + o1.body + " ? 1 : 0;\n",
          "(v_" + uid + ")"
        ).setType("number");            // 式の静的型に数値型をセット
      }
      const uid = env.getNextUid();
      return new OperationGet(
        o1.head + "const v_" + uid + " = library.toNumber(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      ).setType("number");              // library.toNumberの場合も数値型をセット
    });

他のキャスト演算子も概ねこれと同じようにします。

テスト

次のコードの中間コードを整形して見てみます。

fl8

[
  + 1;
  - 1;
  ? 1;
  ! 1;
  & 1;
  + TRUE;
  - TRUE;
  ? TRUE;
  ! TRUE;
  & TRUE;
  + 'a';
  - 'a';
  ? 'a';
  ! 'a';
  & 'a'
]

成形された中間コード

const v_13 = Symbol("<root>(OnlineDemo,L:14,C:1)");
const v_14 = {[v_13]: function(library) {
  const v_0 = [];

// + 1    数値から数値なので何もしない
          v_0[v_0.length] = (1);
// - 1    負にする
          const v_1 = -(1);
          v_0[v_0.length] = (v_1);
// ? 1    0とNaNのみ偽で他は真
          const v_2 = !((1) === 0 || Number.isNaN((1)));
          v_0[v_0.length] = (v_2);
// ! 1    0とNaNのみ真で他は偽
          const v_3 = (1) === 0 || Number.isNaN((1));
          v_0[v_0.length] = (v_3);
// & 1    数値の文字列表現を得る
          const v_4 = library.toString((1), "(OnlineDemo,L:14,C:3)");
          v_0[v_0.length] = (v_4);

// + TRUE    真なら1、負なら0
          const v_5 = (true) ? 1 : 0;
          v_0[v_0.length] = (v_5);
// - TRUE    真なら-1、負なら0
          const v_6 = (true) ? -1 : 0;
          v_0[v_0.length] = (v_6);
// ? TRUE    論理値から論理値なので何もしない
          v_0[v_0.length] = (true);
// ! TRUE    論理否定
          const v_7 = !(true);
          v_0[v_0.length] = (v_7);
// & TRUE    論理値を表す文字列にする
          const v_8 = (true) ? "TRUE" : "FALSE";
          v_0[v_0.length] = (v_8);

// + 'a'    パースする
          const v_9 = library.toNumber(("a"), "(OnlineDemo,L:20,C:3)");
          v_0[v_0.length] = (v_9);
// - 'a'    パースして負にする
          const v_10 = -library.toNumber(("a"), "(OnlineDemo,L:21,C:3)");
          v_0[v_0.length] = (v_10);
// ? 'a'    文字列の論理値化は、空文字でないか否か
          const v_11 = ("a") !== "";
          v_0[v_0.length] = (v_11);
// ! 'a'    空文字の場合に真になる
          const v_12 = ("a") === "";
          v_0[v_0.length] = (v_12);
// & 'a'    文字列から文字列なので何もしない
          v_0[v_0.length] = ("a");

  return (v_0);
}}[v_13];
(v_14)

ちゃんと該当する部分はライブラリ関数の呼び出しではなくインラインで演算が行われています。

結果は次のようになります。

出力

   [
      1,
      -1,
      true,
      false,
      "1",
      1,
      -1,
      true,
      false,
      "TRUE",
      NaN,
      NaN,
      true,
      false,
      "a"
   ]

もう1個テストをしておきます。次のコードには大量の同じキャスト演算子が書かれていますが、同じ型へのキャストは無意味なので中間コードは簡単なものになるはずです。

fl8

[
  ++++++++++++++++++++ 1;
  ???????????????????? TRUE;
  &&&&&&&&&&&&&&&&&&&& 'a'
]

中間コード

const v_1 = Symbol("<root>(OnlineDemo,L:21,C:1)");
const v_2 = {[v_1]: function(library) {
  const v_0 = [];
  v_0[v_0.length] = (1);
  v_0[v_0.length] = (true);
  v_0[v_0.length] = ("a");
  return (v_0);
}}[v_1];
(v_2)

結果は、ちゃんと簡単な中間コードになりました。静的オーバーロードが無かった場合、それぞれ20回のライブラリ関数の呼び出しが発生していたので、無駄な型チェックが消えて高速化されたことになります。

その他のトークンも静的型と静的オーバーロードに対応させる

リテラルとキャスト演算子以外のトークンも静的型と静的オーバーロードを対応させます。

これには以下のものが該当します。

トークン	静的オーバーロード	静的型
丸括弧`(formula)`	無条件	`formula`の型
セミコロン`head1; ...; body`	無条件	`body`の型
長さ演算子`$#array`	無条件	数値型
加算演算子`a + b`	`a`：数値型 `b`：数値型	数値型
減算演算子`a - b`	`a`：数値型 `b`：数値型	数値型
乗算演算子`a * b`	`a`：数値型 `b`：数値型	数値型
除算演算子`a / b`	`a`：数値型 `b`：数値型	数値型
べき乗演算子`a ^ b`	`a`：数値型 `b`：数値型	数値型
三項演算子`cond ? then : else`	`cond`：論理値型 `then`：数値型 `else`：数値型	数値型
三項演算子`cond ? then : else`	`cond`：論理値型 `then`：論理値型 `else`：論理値型	論理値型
三項演算子`cond ? then : else`	`cond`：論理値型 `then`：文字列型 `else`：文字列型	文字列型

丸括弧`(formula)`

丸括弧(formula)は、実は何も変更する必要はありません。このトークンはあらゆる型のformulaを受け取ることができるという点で静的オーバーロードの必要はなく、formulaの挙動オブジェクトを一切変更することなくそのまま返すため、formulaが静的型を持っていればそれをそのままパスするため、静的型を改めて付与する必要がないためです。

改変なし

    env.registerOperatorHandler("get", "round", (env, token) => {
      env.pushAliasFrame();
      // これはformulaのget挙動オブジェクト
      const o1 = env.compile("get", token.argument[0], {
        suggestedName: env.getSuggestedName(),
      });
      env.popAliasFrame();
      return o1; // そのまま返している
    });

セミコロン`head1; ...; body`

セミコロンhead1; ...; bodyの挙動は、前文しか持たないhead_nの前文を順番に実行し、bodyの前文を実行し、最後にbodyの本文を返すというものでした。

セミコロンはbodyの本文をそのまま返しているため、bodyの静的型をそのままパスするのがよいです。

改変後

    env.registerOperatorHandler("get", "semicolons", (env, token) => {
      const heads = [];
      for (let i = 0; i < token.argument.length - 1; i++) {
        const operation = env.compile("run", token.argument[i]);
        heads.push(operation.head);
      }
      const operation = env.compile("get", token.argument[token.argument.length - 1]);
      return new OperationGet(
        heads.join("") +
        operation.head,
        operation.body
      ).setType(operation.type); // 静的型をパスする
    });

長さ演算子`$#array`

長さ演算子$#arrayは型チェックが必要ですが、配列型はまだ扱わないため、静的オーバーロードの必要はありません。この演算子を適用できない値に対して使用した場合はエラーになるため、静的型は数値型で固定です。

改変後

    env.registerOperatorHandler("get", "left_dollar_hash", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const uid = env.getNextUid();
      return new OperationGet(
        o1.head + "const v_" + uid + " = library.getLength(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      ).setType("number"); // 固定の静的型を与える
    });

加減乗除およびべき乗演算子

これらの演算子は、今のところは、両辺の静的型が整数型だった場合は直接演算子を中間コード上に記述し、そうでない場合は実行時ライブラリを呼び出すようにします。これらの演算子の戻り値の静的型は数値型で固定です。

改変後

    env.registerOperatorHandler("get", "plus", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const o2 = env.compile("get", token.argument[1]);
      // 両辺が数値型の場合は実行時ライブラリを呼び出さない
      if (o1.type.name === "number" && o2.type.name === "number") {
        const uid = env.getNextUid();
        return new OperationGet(
          //                                                         ↓
          o1.head + o2.head + "const v_" + uid + " = " + o1.body + " + " + o2.body + ";\n",
          "(v_" + uid + ")"
        ).setType("number"); // 数値型で固定
      }
      const uid = env.getNextUid();
      return new OperationGet(
        o1.head + o2.head + "const v_" + uid + " = library.add(" + o1.body + ", " + o2.body + ", " + JSON.stringify(loc(env, token)) + ");\n",
        "(v_" + uid + ")"
      ).setType("number"); // 数値型で固定
    });

三項演算子`cond ? then : else`

三項演算子cond ? then : elseは、現状はcondの型チェックも含めてすべての処理を実行時に行っています。

真面目に考えると次のように様々なパターンがありますが、ここでは1・2・3・8のみ実装します。

No	`cond`	`then`	`else`	三項演算子の挙動
1	論理値型	数値型	数値型	数値型
2	論理値型	論理値型	論理値型	論理値型
3	論理値型	文字列型	文字列型	文字列型
4	論理値型	何かしらの型	何かしらの型	`any`型
5	型なし	数値型	数値型	`cond`を型チェックして数値型
6	型なし	論理値型	論理値型	`cond`を型チェックして論理値型
7	型なし	文字列型	文字列型	`cond`を型チェックして文字列型
8	型なし	何かしらの型	何かしらの型	`cond`を型チェックして`any`型

改変後

    env.registerOperatorHandler("get", "ternary_question_colon", (env, token) => {
      const o1 = env.compile("get", token.argument[0]);
      const o2 = env.compile("get", token.argument[1]);
      const o3 = env.compile("get", token.argument[2]);
      // ↓これを追加
      if (o1.type.name === "boolean" && o2.type.name === "number" && o3.type.name === "number") {
        const uid = env.getNextUid();
        return new OperationGet(
          o1.head +
          "let v_" + uid + ";\n" +
          // ここにあった型チェックが消えている
          "if (" + o1.body + ") {\n" +
          indent(
            o2.head +
            "v_" + uid + " = " + o2.body + ";\n"
          ) +
          "} else {\n" +
          indent(
            o3.head +
            "v_" + uid + " = " + o3.body + ";\n"
          ) +
          "}\n",
          "(v_" + uid + ")"
        ).setType("number"); // 静的型を付与
      }
      // ↓これを追加
      if (o1.type.name === "boolean" && o2.type.name === "boolean" && o3.type.name === "boolean") {
        const uid = env.getNextUid();
        return new OperationGet(
          o1.head +
          "let v_" + uid + ";\n" +
          // ここにあった型チェックが消えている
          "if (" + o1.body + ") {\n" +
          indent(
            o2.head +
            "v_" + uid + " = " + o2.body + ";\n"
          ) +
          "} else {\n" +
          indent(
            o3.head +
            "v_" + uid + " = " + o3.body + ";\n"
          ) +
          "}\n",
          "(v_" + uid + ")"
        ).setType("boolean"); // 静的型を付与
      }
      // ↓これを追加
      if (o1.type.name === "boolean" && o2.type.name === "string" && o3.type.name === "string") {
        const uid = env.getNextUid();
        return new OperationGet(
          o1.head +
          "let v_" + uid + ";\n" +
          // ここにあった型チェックが消えている
          "if (" + o1.body + ") {\n" +
          indent(
            o2.head +
            "v_" + uid + " = " + o2.body + ";\n"
          ) +
          "} else {\n" +
          indent(
            o3.head +
            "v_" + uid + " = " + o3.body + ";\n"
          ) +
          "}\n",
          "(v_" + uid + ")"
        ).setType("string"); // 静的型を付与
      }
      const uid = env.getNextUid();
      return new OperationGet(
        o1.head +
        "let v_" + uid + ";\n" +
        "library.checkNumber(" + o1.body + ", " + JSON.stringify(loc(env, token)) + ");" +
        "if (" + o1.body + ") {\n" +
        indent(
          o2.head +
          "v_" + uid + " = " + o2.body + ";\n"
        ) +
        "} else {\n" +
        indent(
          o3.head +
          "v_" + uid + " = " + o3.body + ";\n"
        ) +
        "}\n",
        "(v_" + uid + ")"
      );
    });

本当は、condを前置?相当の挙動で論理値化し、演算子の静的型はthenとelseの最も近い共通祖先にしたいところです。

テスト

上記の5種類の演算子を使った簡易的なテストです。

静的オーバーロードがうまく機能していれば、次のコード中にはlibrary.toNumberが一切出現しないはずです。

fl8

+(dummy : 'string'; TRUE ? $#[0] : 1 + 2 - 3 * 4 / 5 ^ 6)

中間コード

const v_9 = Symbol("<root>(OnlineDemo,L:4,C:1)");
const v_10 = {[v_9]: function(library) {
  let v_0;
  v_0 = ("string");
  let v_8;
  if ((true)) {
    const v_1 = [];
    v_1[v_1.length] = (0);
    const v_2 = library.getLength((v_1), "(OnlineDemo,L:4,C:28)");
    v_8 = (v_2);
  } else {
    const v_3 = (1) + (2);
    const v_4 = (3) * (4);
    const v_5 = Math.pow((5), (6));
    const v_6 = (v_4) / (v_5);
    const v_7 = (v_3) - (v_6);
    v_8 = (v_7);
  }
  return (v_8);
}}[v_9];
(v_10)

うまく実行時ライブラリの呼び出し回数を減らすことが出来ました。

まとめ

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

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

GitHub公開リポジトリ （新規）
言語機能
- ソースコードから構文木の生成
- 構文木から中間コードの生成
- 中間コードの評価
- 副作用を持つ演算の適切な順序での実行
- エラー出力の改善
- トークンの文脈の管理
- 識別子の文脈の管理
- トークンの出現場所の管理
- ソースファイル名の管理
- 関数名の推測
- 文脈ドメインごとのコンパイラの管理
- 実行時ライブラリ
- 静的型 （新規）
- 静的オーバーロード （新規）
スペース
識別子
- 組み込み定数　（ドメイン：get）
  - PI
  - TRUE FALSE （新規）
  - UNDEFINED NULL INFINITY NAN （新規）
- 引数　（ドメイン：get）
- 変数　（ドメイン：get set）
getドメイントークン
- 整数リテラル123 （改善）
- 文字列リテラル'string' （改善）
- 識別子identifier （改善）
- 丸括弧(formula) （改善）
- 空配列初期化子[]
- 配列初期化子[values]
- 関数呼び出しfunction(argument)
- 配列要素アクセサarray[index]
- べき乗a ^ b （改善）
- キャスト演算子 +a -a ?a !a &a （改善） （新規）
- 長さ演算子$#array （改善）
- 加減乗除 a + b a - b a * b a / b （改善）
- 三項演算子cond ? then ? else （改善）
- ラムダ式arg -> formula
- 文; （改善）
setドメイントークン
- 識別子 identifier
arrayドメイントークン
- 配列要素区切り;
runドメイントークン
- 変数宣言variable : value
- 代入acceptor = value

今回は型を静的に管理する機能を追加することで実行時のオーバーヘッドを減らしました。
また、いくつかの組み込み定数とキャスト演算子が追加されました。

[次回→](

)

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

fluorite-8 実装の軌跡 Part 10 静的型と静的オーバーロード

今回の目標

四則演算が重い

目標

いくつかの組み込み定数の追加

目標

実装

Githubリポジトリ

テスト

キャスト演算子+value -value ?value !value &value追加

目標

元ネタと考察

実装

テスト

式が静的に型を持つようにする

戦略

実装

toOperation系関数の改変

整数・文字列リテラルと論理値組み込み定数を静的型に対応させる

実装

キャスト演算子を静的型と静的オーバーロードに対応させる

戦略

実装

テスト

その他のトークンも静的型と静的オーバーロードに対応させる

丸括弧(formula)

セミコロンhead1; ...; body

長さ演算子$#array

加減乗除およびべき乗演算子

三項演算子cond ? then : else

テスト

まとめ

fluorite-8　実装の軌跡　Part 10　静的型と静的オーバーロード

キャスト演算子`+value` `-value` `?value` `!value` `&value`追加

`toOperation`系関数の改変

丸括弧`(formula)`

セミコロン`head1; ...; body`

長さ演算子`$#array`

三項演算子`cond ? then : else`