JavaScript
プログラミング
自作

まったりプログラミング言語自作したい 〜 JavaScript上で作るぞ!

前書き

 みなさん、こんにちは。突然ですが、プログラム言語や、コンパイラを、自分で作ってみたいと思ったことはありませんか。

 私はあります。というわけで、さっそく作っていきましょう!私は自作初心者なので、筋の悪いところや間違っている所などありましたら、指摘いただけると嬉しいです。

目標

 プログラム言語を作るというからには、文法を決めることが必要です。さらに、その文法に従って作られたプログラムは、実行出来ないといけません。文法はどのプログラム言語にもありますが、実行方式は様々です。

 たとえば、C言語は機械語というCPUへの命令を生成して、その機械語を実行します。他の言語では、機械語を生成せずに命令を実行するものもあります。もちろん、真に機械語を生成しないで命令を実行するのは不可能です。ここでいう機械語を生成しないとは、他の機械語を生成できるようなプログラム言語の機能を呼び出すことで、自分自身は機械語を生成しないというものです。

 いきなり機械語を生成する本格的なコンパイラを作るのは無理があると思いますし、機械語はCPUごとに違うので、勉強も大変です。なので今回は、既存の他のプログラム言語の上で動く、自作言語をまずは目指したいと思います。

 しかし、私はもっと細かい所や、より低いレイヤーでの、プログラム言語についても分かりたいので、欲を言えば機械語やアセンブリ言語にも手を出してみたいと思っています。これを踏まえて、JavaScriptを実行環境として、その上に自作言語を作ろうと思いました。

なぜJavaScriptか

  • JavaScriptは、ブラウザさえあれば動くから。どうせなら色んな環境で動く言語にしたい。
  • JavaScriptは、高水準な言語だし、開発者ツールもブラウザに最初から付いてるし、便利で手軽。
  • JavaScriptには、なんとアセンブリ言語もある。(wasm)なので、最終的にアセンブリ言語に変換したいなー作りたいなーと思ったら作れると思う。

 どこでも動くという利点に、高度な開発者ツールもあり、しかもアセンブリ言語、つまりはほとんど機械語のようなものを実行できる環境さえある。これで決まりだ!

ソースコード構造 〜仕様策定に向けて〜

 皆さん、データ構造とアルゴリズムについて、ある程度詳しいですか?

 問題を解決するには、適切なデータ構造が必要です。例えば生徒10人のテストの成績の平均点を出したいとします。

 そういった時、例えば配列のようなデータ構造で情報が存在したら、楽に計算できますよね。

var score = [90, 85, 60, 70, 55, 100, 80, 70, 80, 50];

 なぜなら、配列は数を使って各要素にアクセス出来るので、数字を一つずつ増やすことで、生徒全員に順番にアクセスできるからです。アクセスした上で全員足せば合計となり、それを10で割れば平均になります。

 配列には「.length」というメンバ変数も含まれるので、この10という数字も簡単に取得出来ます。そうすると、10人どころか、生徒n人に対応する平均点が簡単に計算できます。

var sum = 0;
for (var i = 0; i < score.length; i++) {
  sum += score[i];
}

console.log(sum / score.length);

 しかし、もし与えられたデータが、こんな感じだったらどうでしょう。

var score = "90点 85点、60点、 70点、55点、百点満点、80,  70, 80 50";

 恐ろしいデータです。全ての情報が単一の文字列になっているので、添字を使ってそれぞれの点数にアクセス出来ません。

 しかも、文字列なのでそもそもまず数字に変換する必要がありますが、"点"などの余分な情報が困難さを上げています。"点"を全て削除して対応しようとすると、"百点満点"が"百満"になって、謎の単語が生まれてしまったりします。

 それぞれの点数が、"、"で区切られていたり、","で区切られていたりして、簡単にはそれぞれの生徒ごとに区切らせてくれません。数字も全角だったり半角だったりしますし、百点満点に至っては漢字です。とにかく非常に扱いづらいデータだと言えるでしょう。

 この例で伝えたかったのは、データ構造の素晴らしさです。配列という、連続して要素にアクセスする際に有用なデータ構造と、そういった要素をまったく考えていない上の文字列を比較すれば分かると思います。

 しかし、プログラム言語を作って、コンパイラを作って、という行為には、こういった難しさがあります。ソースコードは、最初、文字列の塊でしかありませんから。

 自作言語を作るに当たっても、その処理をする時には、ソースコードから扱いやすいデータ構造に変換する必要があります。そしてそのデータ構造から、実際の計算をしたり、アセンブリや機械語を生成する、という段階を踏むべきなのです。

ソースコード → 中間表現(データ構造) → 最終的な生成物(機械語や、直接実行出来る形式)
 
 また、データ構造は「処理しやすい」形式である必要がありますし、ソースコードの文法も、そういったデータ構造に「変換しやすい文法」である方が、便利です。そのため、まず決めるべきは文法ではなく、中間表現のデータ構造だと考えられます。自分の好きな文法を何も考えず作ると、それがコンピュータにとって処理しやすいかということが抜け落ちて、いざコンパイラを作ろうと思った時に、非常に困難になると思います。

 それは、上記の生徒ごとの成績の例から明らかですね。こんな自由気ままな書式ではいけないということです。

// 腹が立つくらい自由気ままな書式の例
var score = "90点 85点、60点、 70点、55点、百点満点、80,  70, 80 50";

 では、どういう中間構造を作れば良いか、今回でいえば、「JavaScript上で処理しやすいデータ構造で、そのデータ構造は、プログラム実行時に必要な要素を網羅することが出来、アクセスも簡単」という感じでしょうか。プログラムにとって必要な要素とは、例えば値を表現出来たり、式を表現出来たり、文を表現できたり、ということです。

 私はそういった中間表現のデータ構造を勝手にソースコード構造と読んでいます。具体的には、例えば以下のようなものです。これは私が考えたもので、私がいま作成中の自作言語の中間表現です。JSONの表記法を使って、必要な要素を整理して記述してあります。

var program = {
  "add": {
    param: ["a", "b"],
    block: [{
      type: "return",
      exp: [{
        type: "eval",
        value: 'locals["a"] + locals["b"]'
      }]
    }]
  }
}

 これは、加算を実行する関数の定義で、JavaScriptで言えばこういう関数に対する中間表現です。

function add(a, b) {
  return a + b;
}

 こういったデータ構造を作れば、"add"という関数が呼ばれた時に、program["add"]でその関数の定義を呼び出せます。
 さらに、paramにアクセスして仮引数名をとりだして、その変数名でその関数内でのみ有効なローカル変数を作成し、その上でblockの中身を実行していって、・・・という風に処理を進めていくことが出来ます。

 このように、情報を取り出しやすいデータ構造を決めれば、それを元にした処理がしやすいです。さらに、こういったデータ構造を生成しやすい文法を考えることで、文法の仕様も決められます。

 その仕様を元に、中間表現から実際の命令を行う処理や、ソースコードから中間表現を作成する処理を書いていけば、プログラム言語が自作できる気がしてきませんか?

プログラミング言語に必要な5つの要素とは

 突然ですが、コンピュータの五大装置というものがあります。基本情報技術者試験などで問われる知識なので、知っている人も多いでしょう。コンピュータの五大装置とは、

  • 演算装置
  • 記憶装置
  • 制御装置
  • 入力装置
  • 出力装置

の5つのことです。現行のコンピュータは、この五大装置によって成り立っているそうです。プログラミング言語というのは、コンピュータがどのように動作するかを指し示すものであるはずです。なので、プログラミング言語にも、この五大装置に対応する要素が必要ではないかと思います。そういった考えのもと、プログラミング言語を設計していこうと思います。具体的には

  • 演算装置 -> 式
  • 記憶装置 -> 変数
  • 制御装置 -> 制御文
  • 入力装置 -> 引数
  • 出力装置 -> 戻り値  

 という対応付けを行います。この5つの要素が全てそろえば、プログラミング言語としては十分だと考えます。では、まずは「式」からその仕様決定と実装を行っていこうと思います。

式とは 

 この記事の中で言う式とは、値及び、評価すると値になるもののこととします。評価とは、関数に引数を与えて戻り値を返すことです。例えば、以下はいずれも式です。

// 値は式
5;
//値をもとに計算したものも式
3 + 5;
//関数を実行して値が返ってくるなら式
plus(3, 5);

function plus(a, b) {
  return a + b;
}

処理しやすい式とは

 ソースコード構造で、まずコンピュータに処理しやすいデータ構造を決めるべきだ!という考えを述べました。なので、どのような形式で式を表せば、コンピュータによって処理しやすいかを考えて、仕様を決めます。今回は、逆ポーランド記法によって式を表したいと思います。逆ポーランド記法とは、ざっくり言うと値の後に演算子(関数)を書く形式のことです。詳しくはwikipediaをどうぞ。例としては、下記の通りです。

通常の関数呼び出しの例:
plus(3, 5)
逆ポーランド記法の例:
3 5 plus
 
 逆ポーランド記法で式を表すと、非常に計算しやすくなります。その計算手順としては、まずスタックを用意します。その後、式の要素を左から順番に見ていき、その要素が値ならば、スタックにpushします。要素が関数名ならば、その関数の引数の数だけ、スタックからpopします。その値を関数に渡し、その評価した値を、またスタックにpushします。これを繰り返して、最後にスタックに残った値が計算結果です。コードは以下の通りです。

//関数名をキーに、その関数の引数の長さと、処理を記述する。
var functions = {
  //加算
  plus: {
    length: 2,
    body: (params) => params[1] + params[0]
  },
  //減算
  minus: {
    length: 2,
    body: (params) => params[1] - params[0]
  },
  //掛け算
  mul: {
    length: 2,
    body: (params) => params[1] * params[0]
  },
  //割り算
  div: {
    length: 2,
    body: (params) => params[1] / params[0]
  }
};


function calc(list) {
  //処理用スタック
  var stack = [];

  //式を左から順番に見ていく。
  for (var i = 0; i < list.length; i++) {
    var e = list[i];
    if (e in functions) {
      // 要素が関数名だったら、計算する。

      // 引数の数だけ、スタックから取り出す。
      var args = [];
      for (var j = 0; j < functions[e].length; j++) {
        args.push(stack.pop());
      }

      // スタックに計算結果をpushする。
      stack.push(functions[e].body(args));

    } else {
      // 要素が関数名でなかったら、数値と判断して格納する。
      stack.push(parseFloat(e));
    }
  }

  return stack[0];
}

//逆ポーランド記法で記述された式 (3 - 5) * 2 
var list = ["3", "5", "minus", "2", "mul"];

// - 4
console.log(calc(list));

 逆ポーランド記法で書かれた式を計算することが出来ました。次は、通常の関数呼び出しの形、例えば「plus(1, 2)」などで書かれた式を逆ポーランドに変換したいと思います。

関数呼び出しを逆ポーランド記法に変換

〜プログラムは書きましたが、解説は明日書きます!〜

// 逆ポーランド記法に変換
function toRPN(words) {
  while (true) {
    var start = [];
    var mid = [];

    var notClose = true;
    while (words.length > 0) {
      var w = words.shift();
      if (w == ")") {
        notClose = false;
        break;
      }
      start.push(w);
    }

    if (notClose) {
      return start;
    }

    while (start.length > 0) {
      var w = start.pop();
      if (w == "(") {
        break;
      }
      mid.push(w);
    }

    mid.reverse();
    mid.push(start.pop());

    words = start.concat(mid).concat(words);
  }
}

// (3 - 5) * 4
var exp = "mul(minus(3,5),4)";
// 字句ごとに区切る
var words = exp.split("(").join(" ( ").split(")").join(" ) ").split(",").join(" ").split(" ").filter(e => e.length > 0)
//逆ポーランド記法に変換
var rpn = toRPN(words);
//逆ポーランド記法から計算
console.log(calc(rpn));

後書き

 前からプログラミング言語を作ってみたいな〜(思うだけ)でしたのですが、今回ついに挑戦しようと思ってしまいました。少しずつ作っていって、この記事も更新しようと思います。とりあえず今回は、逆ポーランド記法で式を表し、それをもとに計算する方法を書いて終わりです。