Qiitaで見つけたOrelang(俺言語)をTypeScriptで実装し、さらにif式や関数定義を追加したりS式で書けるようにしてみた

とりあえず、先にリポジトリを...

ここで公開しています: Orelang_TS

実装に至る経緯

(いつもD言語を書いてる僕がなぜ、TypeScriptで実装したかという話で興味のない人はスキップしてもらって構いません。)

昨日帰宅してから久しぶりにQiitaを眺めていると
プログラミング言語を作る。１時間で。
という記事を発見しました。

Safariでそのリンクをクリックして、記事が表示されるまでの間にGVim(MacVim)を起動し、D言語で実装するぞ！と意気込んで記事を読み進めながらD言語で実装を進めました。
で、結局タイトルにある通りD言語ではなく、TypeScriptを用いて実装したわけですが、チョット楽をするためにいつものD言語ではなく、TypeScriptを使いました。
なぜこうなったかという単純に、元の記事はJavaでList<?>という表現を使っていたのですが、これをD言語で再現しようとすると代数的データ型みたいなものを実装する必要があり、面倒くさくなってしまって諦めました(そこまで難しくはないのですが混乱してコードがぐちゃぐちゃになったので破棄しました...)。
そこで、僕が使える静的に型検査される言語はTypeScriptぐらいしか他になかったのでTypeScriptで実装することにしました。(ここでは簡単にDではつらいとしか書いていませんが、具体的にどのように辛いかということはここに書くには長くなりすぎてしまうため割愛します。)

実装について

基本的に元記事のJavaによる実装をTypeScriptでほぼそのまま実装しました。
元の記事の説明は大変わかりやすいので実装についての詳細は元記事をご参照ください。(Orelangの仕様についてもそちらをご参照ください)

元記事で紹介されている機能の実装では、困った事はあまりなかったのですが、強いていえば何故かMacのVisualStudio CodeのIntellisenseが動かなくて補完なし(キーワード補完の身)の状態で書くことになってなんで動かないのかなぁと思ってモヤモヤしたことぐらいですかね...

実装は元記事の内容でしたら本当に1時間ぐらいで実装できてしまうので是非一度自分で実装してみると楽しいかと思います。

また、この記事とは関係ありませんが以前実装したJSONパーサーやパーサーコンビネータの実装やLisp処理系の実装などを思い出して楽しい気分のままサクサク実装を進めています笑。

次の節でOrelang_TSに実装した元記事にはなかった機能について紹介します。

追加した機能一覧

• if オペレーター
• while オペレーター
• 比較演算オペレーター(>, <, >=, <=)
• 論理演算オペレーター(!, ||, &&)
• 標準出力オペレーター(print)
• 差,商,剰余(-, /, %)
• 関数定義(def)
• S式のトランスパイラ(Orelang_TSでは元記事の実装と同様、構文木をJSONの配列を内部表現として採用しています。従って、Lispのような記法をJSONの配列ですることでOrelangは記述出来るのですが、これはあまりにも書きにくかったのでS式をJSONの配列にトランスパイルするコードを書きました)
• 関数/オペレーターを第1級オブジェクトとして扱えるように改造
• ラムダ式(lambda オペレーターの実装)

これらの機能を元の実装に加えました。

基本的にオペレーターを新規に実装する場合は、引数を適切に取り出して、TypeScript(実装する言語)の構文に当てはめて評価するというだけなので難しくないです。
例えばif式の場合
(if cond trueExpr falseExpr)
という式であり、第1引数のcondが条件式、続く第2,3引数はそれぞれ条件式が真・偽のときに評価される式です。(Orelangの式は即値とオペレーター呼び出しのどちらかのみです。ちなみに、if式はオペレーター呼び出しです。このような定義から、オペレーター呼び出しはネストすることが出来ます)。
よってif式を実装する場合は(実際の実装とは少し異なりますが)このような感じになります。(本当は元の実装でもしたほうがいいのですが、ここでは引数の個数チェックは省略します(Orelang_TSでの引数チェックは今後実装します))

// EngineはOrelang_TSの言語エンジン
function ifExpr (engine: Engine, args: Array<any>): Object {
  var ret: Object = null;// 戻り値

  if (<boolean>engine.eval(args[0])) {
    // 真の場合、args[1]すなわちtrueExprを評価する。
    ret = engine.eval(args[1]);
  } else {
    // 同様に、儀の場合はfalseExprを評価する。
    ret = engine.eval(args[2]);
  }

  // if式の評価値を返す。
  return ret;
}

つまり、基本的に引数をengine.eval(args[idx])で取り出して適当に処理するという流れとなります。

さて、この拡張機能の実装では一つだけ困ったことがありました。
それは関数定義についてです。詳細は次の節に書きます。
また、S式で書けるようにしたことが個人的には大きいのでそれについても書きます。

関数定義の実装について。

上で困ったとは書きましたが、実際、実装自体に困ったわけではなく、実装をするにあたってある問題に気がついてしまい、結果として困ってるという感じです。(実際、コード自体は1,2秒ぐらいで頭に浮かびその数秒後にその問題を気がついたぐらいなので実装は本当に単純です。)

とりあえず先にコードを示してそれから詳細を書きます。

DeffunOperator.ts

import {Engine} from "../Engine";
import {IOperator} from "../operator/IOperator";

export class DeffunOperator implements IOperator {
  /**
   * call
   */
  public call(engine: Engine, args: Array<any>): Object {
    var funcName: string   = String(engine.eval(args[0]));
    var funcArgs: string[] = <string[]>args[1];
    var funcBody: Object   = args[2];

    /**
     * Dynamic Operator Generating with inner class
     */

    class X implements IOperator {
      private funcArgs: string[];
      private funcBody: Object;

      constructor(funcArgs: string[], funcBody: Object) {
        this.funcArgs = funcArgs;
        this.funcBody = funcBody;
      } 

      public call(engine: Engine, args: Array<any>): Object {
        var i: number = 0;
        var targ: any = ["step"];

        /*
          TODO: This arguments passing style has a problem, which can confilict with already used name and argument name.  
        */
        this.funcArgs.forEach(key => {
          targ.push(["set", key, args[i]]);
        });

        // 1 offset for step operator
        if (targ.length > 1) {
          engine.eval(targ);
        }

        return engine.eval(this.funcBody);
      }
    }

    var x: X = new X(funcArgs, funcBody);
    engine.operators[funcName] = x;
    return x;
  }
}

とりあえず、実装は上のとおりです。

関数定義とは書きましたが実際には動的なオペレーターの定義です。(Orelang自体には関数は定義されていません。オペレーター呼び出しと即値のみが値として定義されています。(ここで注意したいのはオペレーター呼び出しは値ですがオペレーターは値ではないです。つまり、オペレーター(以後関数と書きます)はOrelangに置いて第一級オブジェクトではありません。)

追記: 先ほど関数/オペレーターを第1級オブジェクトとして扱えるように改良しました。 該当コミット

つまり、新しくオペレーターを定義することでそれをオペレーター呼び出しによって、関数定義と関数呼び出しを実現します。(オペレーターと関数を区別するように書きましたが、これは便宜上このように書いただけであり、実際は区別する必要はありません。)

上に示したコードの説明に入る前に、Orelang_TSではどのようにしてオペレーターを定義しているかと変数の実装をしているかについて説明します。

まず、Orelang_TSのエンジンであるEngineクラスはパブリックな変数にoperatorsとvariablesがあります。
名前からわかるようにそれぞれオペレーターと変数を保持する変数です。
それらはEngine.tsの中で

  /**
   * This holds Operators as a hash table by string key.
   */
  public operators: {[key: string]: IOperator} = {};
  /**
   * This holds global variables.
   * Current Orelang_TS provides global varibale only.
   */
  public variables: {[key: string]: Object} = {};

として定義されています。(それぞれstringをキーとする連想配列です。)
(IOperatorはオペレーターのインターフェースです。)

つまり、Orelang_TSにおいてはオペレーターはEngine.operatorsで、変数はEngine.variablesで一元管理されます。
従って、Engine.operatorsに新しくオペレーターを登録すれば自動的にそれがディスパッチされます。(任意のオペレーターを受け付けるため登録されていればそれがディスパッチされ、登録されていない場合は例外が発生します。)
よって、動的に新しく関数をオペレーターとしてEngine.operatorsに追加すれば関数定義が実装できます。

さて、関数とは何かということを考えてみましょう。

関数とは0以上の引数をとり、式を評価することによって値を返すという概念です。
式の評価は単純にEngine.evalをコールするだけなのでどうでもよく、ここで問題となってくるのは引数です。より具体的には引数の受け渡しです。
引数の受け渡しを実現するには通常スタックフレームのようなものを作ったりして実現します。しかし、関数の引数の受け渡しのためにそれを実装するのは(深夜に実装していたことも有り)あまり気が進みませんでした。
そのため、上の実装は簡単ではありますが問題を含んでいます。
上の実装では、引数を変数としてわたしています。
ここで、感の良い方(と、定義部分のコメントを読んだ方)は気がついているかもしれませんが、Orelang_TSは全ての変数はグローバルです。つまり、引数の名前が既存の変数名と衝突する可能性が存在します。(この問題は名前空間を分離しない限り発生します)。これが実装で困ったことです。
1番簡単なのはコールされた時点のEngineの状態をオペレーターの内部でstaticな変数で保持することですがこれは名前空間の衝突を避けることが出来ても、また別の問題が発生します。(例えば、関数内でグローバルな値を参照していた場合、その変更が受け継がれなくなります(関数コール時に新しいengineのインスタンスの複製を作って同期すればこの問題も解決できますが、それをすると今度は引数が増えた場合に毎回シーケンシャルなコピーが発生してパフォーマンスが低下します。←などと書いていますが、この記事を書いているときに浮かんだ方法なので記事を書き終えたら一度実装してみようと思います。)
関数呼び出しの実装って難しいんだなぁと勉強になりました。(なにより、普段使ってる言語の裏ではこのようなことが行われているということを実際に実装することで気がつけたので良かったです。)

なんだかまとまりのない節になってしまい何を主張したかったかが曖昧になってしまいました...

ここまでで、この実装の問題点について記述したので、ここからは簡単に上の実装にいて簡単に解説をします。

実装は単純で関数定義(def)オペレーターを次のように定義します。
(def funcName funcArgs funcBody)
つまり、第一引数にstringで関数名を、第2引数で変数名のリストを(変数名をここで取得しておき、コールされたときにこのリストの順にその引数を変数にセットすることで引数の受け渡しを実現します。)、第3引数に関数本体となる式を受け取ります。

実際の動作は、まずdefオペレーターのコール時にその3つの引数を受け取ります。
そして、動的にオペレーターを生成するために、そのオペレーターのためのクラスXをdefオペレーターの内部で作ります。(ここが強いての工夫点。とはいえ、こうする以外無いので工夫とも言えないか。)
続いて、Xのコンストラクタにdefが受け取った引数名のリスト(funcArgs)と関数本体となる式(funcBody)をわたすことでインスタンスxを得ます。
このxが今、動的に生成されたオペレーターです(つまり、関数)。
あとはfuncNameをキーとしてengine.operatorsにxを登録することで動的にオペレーターを定義することが出来、結果として関数定義が実現出来ます。

このようにして実装しました。

S式のトランスパイラ

(多分これは厳密にはS式ではなく、S式風という感じだと思います...(S式の範囲内に収まってはいますが、S式で可能な表現のうちの一部という意味。))

上でも書いたとおり、Orelang_TSでは内部表現(構文木)にJSONの配列を用いています。(ヘテロなリストとして扱いやすいため。また、オリジナルのJava実装ではJSONの配列を受け取ってList<?>として使ってました(JSONのJava側の表現として)。)
従って、そのまま書こうとなると些か面倒くさくなります。

例えば、1から10までの整数を和は

["step",
  ["set", "sum", 0 ],
  ["set", "i", 1 ],
  ["while", ["<=", ["get", "i"], 10],
    ["step",
      ["set", "sum", ["+", ["get", "sum"], ["get", "i"]]],
      ["set", "i", ["+", ["get", "i"], 1]]]],
  ["print", ["get", "sum"]]]

というコードになります。しかし、これは一見するとS式に見えないこともないけどどう考えても書きづら過ぎます(シンボルを書く場合にクオートで囲まないといけない...)

だったらS式をトランスパイルしてこれを吐かせてしまえばいいや〜となるわけで

(step
  (set sum 0)
  (set i 1)
  (while (<= (get i) 10)
    (step
      (set sum (+ (get sum) (get i)))
      (set i (+ (get i) 1))))
  (print (get sum)))

これをトランスパイルすると上のJSONが吐かれるようにすればいいわけです。
トランスパイルは普通にパーサーを書いてもいいんですけど、もうなんか泥臭くていいや〜って思ったのでとりあえず、正規表現をガリガリに重ねてreplaceしまくってトランスパイラを書いてしまいました(今度時間があるときにパーサーを書こうかなぁと思っていますが)。

実装は次のコードです:

追記(2016/10/02): 以下のグロテスクな正規表現列は多くの不具合を含んでいるため、いい感じの再帰降下S式パーサーを実装しました(以下にコードも貼ります)該当コミット

Transpiler.ts

// Transpile Lisp(S-Expression) into internal expression of Orelang_Ts(JSON Array) 

export class Transpiler {
  constructor() {}

  /**
   * Current implementation uses many regex conversion as you see, this looks aweful.
   * I'll impliment more useful and efficient transpiler to replace with this. 
   */
  transpile(code: string): JSON {
    code = code
            .replace(/\(/g, "[")// ( -> [
            .replace(/\)/g, "]")// ( -> ]
            .replace(/;.*/g, "")// remove comments
            .replace(/\n/g, "")// remove line return
            .replace(/\=/g, "\"=\"")// escape =
            .replace(/(\<)/g, "\"$1\"")// escape <
            .replace(/(\>)/g, "\"$1\"")// escape >
            .replace(/(\"\<\"\"\=\")/g, "\"<=\"")// fix "<""="" -> "<="
            .replace(/(\"\>\"\"\=\")/g, "\">=\"")//fix ">""=" -> ">="
            .replace(/\+/g, "\"+\"")// escape +
            .replace(/\-/g, "\"-\"")// escape -
            .replace(/\*/g, "\"*\"")// escape *
            .replace(/\//g, "\"/\"")// escape /
            .replace(/\!/g, "\"!\"")// escape !
            .replace(/\|\|/g, "\"||\"")// escape ||
            .replace(/&&/g, "\"&&\"")// escape &&
            .replace(/\s\s+/g, " ")// folds spaces into one space
            .split(" ").join(", ")// join by space with ,
            .replace(/,\s*\]/g, "]")// remove comma of last elements [a, b, c,] -> [a, b, c
            .replace(/\[(?!\")(([a-z]|[A-Z]|_)([a-z]|[A-Z]|[0-9])*)/g, "[\"$1\"")// escape symbols
            .replace(/\s(([a-z]|[A-Z]|_)([a-z]|[A-Z]|[0-9])*)\s/g, "\"$1\"")// escape symbols
            .replace(/,\s(([a-z]|[A-Z]|_)([a-z]|[A-Z]|[0-9])*)/g, ", \"$1\"");// escape symbols
      return JSON.parse(code);
    }
}

なんかグロテスクな正規表現列な感じですけどとりあえず、これでトランスパイルできます....

追記(2016/10/02): 以下に上のトランスパイラがグロテスクすぎるために実装した再帰降下のS式パーサーの実装を貼ります(上のトランスパイラのコードは内部でこのパーサーを呼ぶように書き換えました)。

Parser.ts

// Parser
export class Parser {
  static nextBracket(code: string): number {
    var i: number = 0
    var leftCount: number = 1;
    var rightCount: number = 0;

    while (leftCount != rightCount) {
      if (code[i] == "(") { leftCount++ }
      if (code[i] == ")") { rightCount++ }
      ++i;
    }

    return i;
  }

  static parse(code: string): Array<any> {
    var out: Array<any> = [];
    var symbol: string;

    for (var i:number = 0; i < code.length; i++) {
      var ch = code[i];
      if (ch == ' ') {
        continue;
      } else {
        if (ch == "(") {
          var j = Parser.nextBracket(code.slice(i+1));
          out.push(Parser.parse(code.slice(i+1, i + j)));
          i = i + j;
        } else if (ch == ")") {
          return out;
        } else {
          if (!isNaN(Number(ch))) {
            var tmp: string = "";
            var j = i;

            do {
              tmp += code[j];
              j++;
            } while (!isNaN(Number(code[j])))

            i = j-1;

            out.push(Number(tmp));
            continue;
          } else if (ch == "\"" || ch == "\'") {
            var tmp: string = "";
            var j = i+1;

            while (code[j] != ch && code[j] ) {
              if (j < code.length) {
                tmp += code[j];
              } else {
                throw new Error("Syntax Error");
              }
              j++;
            }

            i = j;
            out.push(tmp);
            continue;
          } else {
            var tmp: string = "";
            var j = i;

            while (code[j] && code[j] != "\"" && code[j] != "\'" && code[j] != "(" && code[j] != ")" && code[j] != " ") {
              tmp += code[j];
              j++;
            }
            i = j;
            out.push(tmp);
          }
        }
      }
    }

    return out;
  }
}

今後はSchemeの文法に近いS式のサポートとかも考えたりしています。

とりあえず、このような実装でOrelang_TSは実装されています。(なんかよくわからない文章になってしまった....)

追記: 関数/オペレーターを第1級オブジェクトとして扱えるようにした

拡張のために上のXクラスをDynamicOperatorクラスとして一つのモジュールへ分離し、GetfunOperatorを定義し、Engine.getExpressionを改造することで、関数/オペレーターを第1級オブジェクトとして扱えるようになりました。
これにより、高階関数を書くことが出来るようになりました。

DynamicOperatorはXの名前を変えて独立させただけなので割愛します。

GetfunOperatorではreturn engine.operators[<string>engine.eval(args[0])];として、関数/オペレーターの名前から該当する関数/オペレーターをreturnします。(これはここにコードを貼るまでもないので割愛します。)

また、Engine.tsのgetExpressionを次のようにしました。
詳細については内部のコメントで解説しました。

public getExpression(script: Object): IExpression {
  if (script instanceof Array) {
    var scriptList:Array<any> = script;
    if (scriptList[0] instanceof Array) {//ここを追加
      // 例えば、fという変数にintの引数を1つとる関数funを代入したとして
      // それを ((get f) 10) として関数を呼び出そうとした場合、その内部表現は
      // script == [["get", "f"], 10]
      // となる。
      // ここで、["get", "f"]がオペレーターのコールなのでそこを先に評価することで関数/オペレーターを取り出す。
      // 取り出されたオペレーターをretとして、ret.eval(this)で評価し"f"が持つ値(関数/オペレーター)(== fun)を取り出す
      // 取り出したfunにscriptの第2引数以降(ここでは第2引数の10だけ)を渡し、その結果を即値ImmediateValueとして返却
      var ret = new CallOperator(this.operators[scriptList[0][0]], scriptList[0].slice(1));
      return new ImmediateValue((<IOperator>ret.eval(this)).call(this, scriptList.slice(1)) );
    }
    return new CallOperator(this.operators[scriptList[0]], scriptList.slice(1));
  } else {
    return new ImmediateValue(script);
  }
}

追記(2016/10/02): ラムダ式を実装した

関数/オペレーターを第1級オブジェクトにするためにDynamicOperatorクラスを作っておいたお陰で10秒ぐらいでラムダ式の実装が出来ました。

具体的には以下のコードで実装できました。

LambdaOperator.ts

import {Engine} from "../Engine";
import {IOperator} from "../operator/IOperator";
import {DynamicOperator} from "../operator/DynamicOperator";

export class LambdaOperator implements IOperator {
  /**
   * call
   */
  public call(engine: Engine, args: Array<any>): Object {
    var funcArgs: string[] = <string[]>args[0];
    var funcBody: Object   = args[1];

    return new DynamicOperator(funcArgs, funcBody);
  }
}