概要

プログラミングをやったことのある人なら，一度は考えたことのある．

自作プログラミング言語の製作

私自身，何度か作ろうと考えたことがありますが，今一つ完成しませんでした．
しかし，最近，

TypeScript + PEG.jsでデータフロープログラミング専用のDSL言語AsyncFlowを作った

という記事を書くために改めて，プログラミング言語を構築しました．
その時に，

自作プログラミング言語を仕様を決めずに作る

ということを行いました．その時に，どのように作ったか？そのHowToをまとめました．

仕様を決めずにプログラミング言語を作ることはできるのか？

究極的に言ってしまえば無理です．
しかし，おそらく「プログラミング言語を作りたい」と思った人は，何かおぼろげながら言語の仕様が頭にあるのではないでしょうか？そのような

断片的にある自作言語の仕様を実装する

ということを，このドキュメントで行います．

言語を作る難しさ

私が大学時代，yacc/lexの演習ということでC言語のパーサーを組んだことがあります．
以下のパーサーはネットにあったものですが，400行ぐらいあります．

それほど大きなサイズのコードではありません．しかし，このパーサー制作には非常に厄介なことがあって，バグを作りこみやすい性質があります．自分では変数の定義の部分を書き換えているつもりが，for文の文法にバグを作りこんでいたりします．普通のプログラムであれば，１つのモジュールにバグを作りこんでも，全体が動かなくなることは稀です．しかし，パーサーに関しては1つのバグで全体が容易に崩壊します．そのため，完成させるにはかなり完全性の高いプログラムを要求されます．
以上のことより，プログラミング言語を作る難しさは

パーサー部分が相互に密結合しているためにバグを作りこみやすい
少々のバグで全体が動かなくなりやすい

という2つがあります．しかも，プログラミング言語を作ったことのない素人が，仕様がふわふわの状態で作り始めてしまうと容易に崩壊しうることは想像に難くないです．
そのため，自作プログラミング言語を作るためには，

小さな仕様から徐々に作成できる手法
バグを作りこまない工夫

という2つのアプローチが必要です．

言語のコンセプト

入門で作る言語というのは簡単であるほうが良いです．では，「簡単である」言語とは何でしょう？

行が翻訳単位である
プログラムの糖衣構文である

という2点です．例えば，AsyncFlowはただのライブラリの一種でした．
以下は，AsyncFlowを作る前のライブラリとして利用した場合のコードの一部です．

relay.subscribe(pub.content);
inc.subscribe(relay.content);
relay.subscribe(inc.content);
init.subscribe(relay.content);
dec.subscribe(init.content);
check.subscribe(dec.content);
dec.subscribe(check.trueContent);
isPrime.subscribe(check.falseContent);
sub.subscribe(isPrime.trueContent);

この表記を見たときに「冗長で読みにくいなぁ．」と思いました．そのため，それらを簡単にする言語，置換ルールみたいなものを定義したい．

pub.c -> relay
relay.c -> inc
inc.c -> relay
relay.c -> init
init.c -> dec
dec.c -> check
check.t -> dec
check.f -> isPrime
isPrime.t -> sub

と表記し，それらを変換することを目標に作りました．
「行が翻訳単位である」というメリットは，パーサーのデバッグが非常にしやすいです．そのため，「言語をちょっとずつ作る」というところには向いています．また，「プログラムの糖衣構文である」というメリットは，プログラムの実行部が非常に簡単になる．というメリットがあります．実行部の制作が難しければ，トランスレーターのようにプログラムを別のプログラムに変換する機構を作り，インタープリターを作らなくて良いので，「ちょっと作る」程度には向いています．

言語を作る準備

今回，AsyncFlowと同じようにTypeScriptで制作します．

$ npm init
$ npm i @types/pegjs pegjs
$ npm i --save-dev jest typescript @types/jest @types/node

言語自体は，特に何でもよいのですが，重要なのは厳密なテスト駆動で実装することです．そのため，テストライブラリのjestを使っています．

パーサーを実装

今回，AsyncFlowの文法の

A.c -> B

という部分を作ってみます．
今回，かなり厳密にテスト駆動するので，かなり冗長な部分があります．

Phase01. Red

まず初めにテストを書きます．

MyParser.test.ts

import pegjs from 'pegjs';
import {MyParser} from './MyParser';

describe('MyParserのテスト', () => {
  it('フロー宣言のテスト', () => {
    const parser: pegjs.Parser = new MyParser().parser();
    expect(() => {
      parser.parse('A.c->B');
    }).not.toThrow();
  });
});

その次にパーサーを実装します

MyParser.ts

import pegjs from 'pegjs';

const definition = ``;

export class MyParser {
  public parser(): pegjs.Parser {
    return pegjs.generate(definition);
  }
}

$ npx tsc
$ npx jest
 FAIL  ./MyParser.test.js
  MyParserのテスト
    ✕ フロー宣言のテスト (25ms)

  ● MyParserのテスト › フロー宣言のテスト

(中略)

Test Suites: 1 failed, 1 total
Tests:       1 failed, 1 total
Snapshots:   0 total
Time:        1.09s
Ran all test suites.

テストに失敗しました．ここから実装の詳細を詰めていきます．

Phase02. Green

ここからはpeg.jsの書き方の話になりますが，わかりやすかったのは3つのドキュメントです．

この辺の資料をなんとなく見ながらやっていきました．
では，MyParser.tsのdefinitionを改造します．

const definition = `
var_def = "A.c->B"
`;

これでテストが通るようになります．

→ npx tsc && npx jest
 PASS  ./MyParser.test.js
  MyParserのテスト
    ✓ フロー宣言のテスト (26ms)

Test Suites: 1 passed, 1 total
Tests:       1 passed, 1 total
Snapshots:   0 total
Time:        1.075s
Ran all test suites.

Phase03. Red

さすがに上記のパーサーでは使い物にならないので，拡張していきます．
そのためにテストを追加します．冗長になるので，一部コードを省略して表記します．

MyParser.test.ts

  it('フロー宣言のテスト', () => {
    const parser: pegjs.Parser = new MyParser().parser();
    expect(() => {
      parser.parse('A.c->B');
    }).not.toThrow();
    expect(() => {
      parser.parse('C.c->D');
    }).not.toThrow();
  });

テストを実行してみましょう．

→ npx tsc && npx jest
 FAIL  ./MyParser.test.js
  MyParserのテスト
    ✕ フロー宣言のテスト (55ms)

  ● MyParserのテスト › フロー宣言のテスト

(中略)

Test Suites: 1 failed, 1 total
Tests:       1 failed, 1 total
Snapshots:   0 total
Time:        1.193s
Ran all test suites.

エラーになりました．

Phase04. Green

ここから，再度実装を考えてみましょう．

MyParser.ts

const definition = `
var_def = "A.c->B" / "C.c->D"
`;

これでテストが通ります．

$ npx tsc && npx jest
 PASS  ./MyParser.test.js
  MyParserのテスト
    ✓ フロー宣言のテスト (30ms)

Test Suites: 1 passed, 1 total
Tests:       1 passed, 1 total
Snapshots:   0 total
Time:        1.063s
Ran all test suites.

Phase05. Refactoring

さすがにこの実装はないだろう．ということでリファクタリングします．

MyParser.ts

const definition = `
var_def = [_A-Za-z][_A-Za-z0-9]* "." [_A-Za-z][_A-Za-z0-9]* "->" [_A-Za-z][_A-Za-z0-9]*
`;

そして，テストを実行する．

$ npx tsc && npx jest
 PASS  ./MyParser.test.js
  MyParserのテスト
    ✓ フロー宣言のテスト (31ms)

Test Suites: 1 passed, 1 total
Tests:       1 passed, 1 total
Snapshots:   0 total
Time:        1.062s
Ran all test suites.

テストが通った．
見通しが悪い実装なので，少し変更します．

MyParser.ts

const definition = `
var_def = var_name "." var_name "->" var_name
var_name = [_A-Za-z][_A-Za-z0-9]*
`;

テストが通ることを確認します．

$ npx tsc && npx jest
 PASS  ./MyParser.test.js
  MyParserのテスト
    ✓ フロー宣言のテスト (33ms)

Test Suites: 1 passed, 1 total
Tests:       1 passed, 1 total
Snapshots:   0 total
Time:        0.928s, estimated 1s
Ran all test suites.

Phase06. Red

慣れてきた場合，少しアグレッシブに変更します．
今作っているパーサーであれば，

A.c->B
C.c->D

のような文法は受け付けます．しかし，

A.c -> B
A.c-> B
A.c ->B

のような空白を許容していません．そのため，この空白を許容してみましょう．
そのためには，まず初めにテストを書きます．

MyParser.test.ts

  it('フロー宣言のテスト', () => {
    const parser: pegjs.Parser = new MyParser().parser();
    expect(() => {
      parser.parse('A.c->B');
      parser.parse('C.c->D');
      parser.parse('A.c->B');
      parser.parse('A.c -> B');
      parser.parse('A.c-> B');
      parser.parse('A.c ->B');
    }).not.toThrow();
  });

テストが失敗することを確認します．

→ npx tsc && npx jest
 FAIL  ./MyParser.test.js
  MyParserのテスト
    ✕ フロー宣言のテスト (55ms)

  ● MyParserのテスト › フロー宣言のテスト

(中略)

Test Suites: 1 failed, 1 total
Tests:       1 failed, 1 total
Snapshots:   0 total
Time:        1.193s
Ran all test suites.

Phase07. Green

空白文字を許容する実装をします．

MyParser.ts

const definition = `
var_def = var_name "." var_name _ "->" _  var_name
var_name = [_A-Za-z][_A-Za-z0-9]*
_ = [ \\t]* 
`;

テストを実行し，成功することを確認します．

$ npx tsc && npx jest
 PASS  ./MyParser.test.js
  MyParserのテスト
    ✓ フロー宣言のテスト (33ms)

Test Suites: 1 passed, 1 total
Tests:       1 passed, 1 total
Snapshots:   0 total
Time:        0.902s, estimated 1s
Ran all test suites.

Phase08. Red

ここから若干難しくなってきます．
次は複数行にわたるプログラムの対応です．どういうことか．というと，今は1行のプログラムしかパース出来ません．しかし，そのようなプログラムでは実用に耐えないので，複数の行のプログラムに対応します．
まず初めにテストを書きます．

MyParser.test.ts

  it('フロー宣言のテスト', () => {
    const parser: pegjs.Parser = new MyParser().parser();
    expect(() => {
      //基本文法
      parser.parse('A.c->B');
      parser.parse('C.c->D');

      //空白対応
      parser.parse('A.c->B');
      parser.parse('A.c -> B');
      parser.parse('A.c-> B');
      parser.parse('A.c ->B');

      //複数文の対応
      parser.parse('A.c->B\nC.c->D')
      parser.parse('A.c->B\nC.c->D\nE.c->F');
    }).not.toThrow();
  });

失敗することを確認します．

→ npx tsc && npx jest
 FAIL  ./MyParser.test.js
  MyParserのテスト
    ✕ フロー宣言のテスト (55ms)

  ● MyParserのテスト › フロー宣言のテスト

(中略)

Test Suites: 1 failed, 1 total
Tests:       1 failed, 1 total
Snapshots:   0 total
Time:        1.193s
Ran all test suites.

Phase09. Green

では実装のほうを改造します．

MyParser.ts

const definition = `
var_defs = var_def_line* var_def
var_def_line = var_def "\\n"
var_def = var_name "." var_name _ "->" _  var_name
var_name = [_A-Za-z][_A-Za-z0-9]*
_ = [ \\t]* 
`;

今までは，var_defという部分しか実装していませんでした．
それに加えて，var_def_lineという末尾に改行がある文法を許容します．
そのあと，var_defsという文法で，var_def_lineを任意個，var_defを必ず1つ以上．という文法を許容します．
この状態だとテストが成功します．

$ npx tsc && npx jest
 PASS  ./MyParser.test.js
  MyParserのテスト
    ✓ フロー宣言のテスト (33ms)

Test Suites: 1 passed, 1 total
Tests:       1 passed, 1 total
Snapshots:   0 total
Time:        0.902s, estimated 1s
Ran all test suites.

このようにテスト駆動で行うと，ちょっとずつ文法が広げられることが分かると思います．

構文木の構築

現状だと，文法的に正しいか正しくないかが分かる機能しかありません．これをプログラムが実行しやすい構文木の形式に変換します．

Phase01. Red

A.c -> B

というプログラムを与えられた場合，どのようなデータ構造が返ってくると使いやすいか考えます．ここでは以下のような構造が返ってくると想定しましょう．

{
  "from" : {
    "name": "A",
    "attr": "c"
  },
  "to" : {
    "name" : "B"
  }
}

では，テストを書きます．

MyParser.test.ts

  it('構文木のテスト', () => {
    const parser: pegjs.Parser = new MyParser().parser();
    const obj = parser.parse('A.c->B');
    expect(obj).toEqual(
      {
        "from" : {
          "name": "A",
          "attr": "c"
        },
        "to" : {
          "name" : "B"
        }
      }
    );
  });

もちろんエラーで失敗します．

$ npx tsc && npx jest
 FAIL  ./MyParser.test.js
  MyParserのテスト
    ✓ フロー宣言のテスト (37ms)
    ✕ 構文木のテスト (15ms)

  ● MyParserのテスト › 構文木のテスト

    expect(received).toEqual(expected)

    Expected value to equal:
      {"from": {"attr": "c", "name": "A"}, "to": {"name": "B"}}
    Received:
      [[], [["A", []], ".", ["c", []], [], "->", [], ["B", []]]]

    Difference:

      Comparing two different types of values. Expected object but received array.

      22 |         var parser = new MyParser_1.MyParser().parser();
      23 |         var obj = parser.parse('A.c->B');
    > 24 |         expect(obj).toEqual({
         |                     ^
      25 |             "from": {
      26 |                 "name": "A",
      27 |                 "attr": "c"

      at Object.toEqual (MyParser.test.js:24:21)

Test Suites: 1 failed, 1 total
Tests:       1 failed, 1 passed, 2 total
Snapshots:   0 total
Time:        1.13s
Ran all test suites.

Phase02. Green

では，実装してみます．

MyParser.ts

const definition = `
var_defs = var_def_line* var_def {
  return {
    "from" : {
      "name": "A",
      "attr": "c"
    },
    "to" : {
      "name" : "B"
    }
  };
}
var_def_line = var_def "\\n"
var_def = var_name "." var_name _ "->" _  var_name
var_name = [_A-Za-z][_A-Za-z0-9]*
_ = [ \\t]* 
`;

テスト駆動をする際に書く，割と無意味なコードですが，テストを動かします．

$ npx tsc && npx jest
 PASS  ./MyParser.test.js
  MyParserのテスト
    ✓ フロー宣言のテスト (37ms)
    ✓ 構文木のテスト (9ms)

Test Suites: 1 passed, 1 total
Tests:       2 passed, 2 total
Snapshots:   0 total
Time:        1.097s
Ran all test suites.

通りました．

Phase03. Red

次は，

C.c->D

を構文木に落とします．これは，

{
  "from" : {
    "name": "C",
    "attr": "c"
  },
  "to" : {
    "name" : "D"
  }
}

になるとします．そこで，テストを書きます．

MyParser.test.ts

  it('構文木のテスト2', () => {
    const parser: pegjs.Parser = new MyParser().parser();
    const obj = parser.parse('C.c->D');
    expect(obj).toEqual(
      {
        "from" : {
          "name": "C",
          "attr": "c"
        },
        "to" : {
          "name" : "D"
        }
      }
    );
  });

もちろんエラーで終了します．

$ npx tsc && npx jest
 FAIL  ./MyParser.test.js
  MyParserのテスト
    ✓ フロー宣言のテスト (37ms)
    ✓ 構文木のテスト (9ms)
    ✕ 構文木のテスト2 (22ms)

  ● MyParserのテスト › 構文木のテスト2

(中略)

Test Suites: 1 failed, 1 total
Tests:       1 failed, 2 passed, 3 total
Snapshots:   0 total
Time:        1.22s
Ran all test suites.

Phase04. Refactoring

ここからちょっとずつリファクタリングします．
まず初めに，var_defsの定義を書き換えます．

MyParser.ts

const definition = `
var_defs = var_def_line* def:var_def {
  return def;
}
var_def_line = var_def "\\n"
var_def = var_name "." var_name _ "->" _  var_name {
  return {
    "from" : {
      "name": "A",
      "attr": "c"
    },
    "to" : {
      "name" : "B"
    }
  };
}
var_name = [_A-Za-z][_A-Za-z0-9]*
_ = [ \\t]* 
`;

先ほど書いた処理をvar_defのほうに持っていき，var_defsのほうはreturnするだけにします．ここでテストを動かすと，

$ npx tsc && npx jest
 FAIL  ./MyParser.test.js
  MyParserのテスト
    ✓ フロー宣言のテスト (37ms)
    ✓ 構文木のテスト (9ms)
    ✕ 構文木のテスト2 (22ms)

  ● MyParserのテスト › 構文木のテスト2

(中略)

Test Suites: 1 failed, 1 total
Tests:       1 failed, 2 passed, 3 total
Snapshots:   0 total
Time:        1.22s
Ran all test suites.

となり，「構文木のテスト」は機能的に変わっていないことが分かります．
その次に，変数名を移植します．

MyParser.ts

const definition = `
var_defs = var_def_line* def:var_def {
  return def;
}
var_def_line = var_def "\\n"
var_def = from:var_name "." attr:var_name _ "->" _  to:var_name {
  return {
    "from" : {
      "name": from,
      "attr": attr
    },
    "to" : {
      "name" : to
    }
  };
}
var_name = name:[_A-Za-z][_A-Za-z0-9]*  {
  return name;
}
_ = [ \\t]* 
`;

var_nameの定義を書き換え，変数名が変えるようにリファクタリングします．
また，var_defの変数の部分をfrom,attr,toと書き換え，それを返り値に使用します．
ここでテストを動かします．

npx tsc && npx jest
 PASS  ./MyParser.test.js
  MyParserのテスト
    ✓ フロー宣言のテスト (40ms)
    ✓ 構文木のテスト (9ms)
    ✓ 構文木のテスト2 (6ms)

Test Suites: 1 passed, 1 total
Tests:       3 passed, 3 total
Snapshots:   0 total
Time:        0.97s, estimated 1s
Ran all test suites.

テストが動くようになりました！！

Phase05. Red

最後に複数行の対応をします．

E.c -> F
G.c -> H

は，

[
  {
    "from" : {
      "name": "E",
      "attr": "c"
    },
    "to" : {
      "name" : "F"
    }
  },
  {
    "from" : {
      "name": "G",
      "attr": "c"
    },
    "to" : {
      "name" : "H"
    }
  }
]

と返ってくるとしましょう．
では，テストを書きます．

MyParser.test.ts

  it('構文木のテスト3', () => {
    const parser: pegjs.Parser = new MyParser().parser();
    const obj = parser.parse('E.c -> F\nG.c -> H');
    expect(obj).toEqual(
      [
        {
          "from" : {
            "name": "E",
            "attr": "c"
          },
          "to" : {
            "name" : "F"
          }
        },
        {
          "from" : {
            "name": "G",
            "attr": "c"
          },
          "to" : {
            "name" : "H"
          }
        }
      ]
    );
  });

もちろんエラーで失敗します．

$ npx tsc && npx jest
 FAIL  ./MyParser.test.js
  MyParserのテスト
    ✓ フロー宣言のテスト (32ms)
    ✓ 構文木のテスト (9ms)
    ✓ 構文木のテスト2 (5ms)
    ✕ 構文木のテスト3 (17ms)

  ● MyParserのテスト › 構文木のテスト3

    expect(received).toEqual(expected)

    Expected value to equal:
      [{"from": {"attr": "c", "name": "E"}, "to": {"name": "F"}}, {"from": {"attr": "c", "name": "G"}, "to": {"name": "H"}}]
    Received:
      {"from": {"attr": "c", "name": "G"}, "to": {"name": "H"}}

    Difference:

      Comparing two different types of values. Expected array but received object.

      48 |         var parser = new MyParser_1.MyParser().parser();
      49 |         var obj = parser.parse('E.c -> F\nG.c -> H');
    > 50 |         expect(obj).toEqual([
         |                     ^
      51 |             {
      52 |                 "from": {
      53 |                     "name": "E",

      at Object.toEqual (MyParser.test.js:50:21)

Test Suites: 1 failed, 1 total
Tests:       1 failed, 3 passed, 4 total
Snapshots:   0 total
Time:        1.209s
Ran all test suites.

Phase06. Refactoring

では，実装のほうを調整します．

MyParser.ts

const definition = `
var_defs = defs:var_def_line* def:var_def {
  if(defs.length > 0) {
    return defs.concat([def]);
  } else {
    return def;
  }
}
var_def_line = def:var_def "\\n" {
  return def;
}
var_def = from:var_name "." attr:var_name _ "->" _  to:var_name {
  return {
    "from" : {
      "name": from,
      "attr": attr
    },
    "to" : {
      "name" : to
    }
  };
}
var_name = name:[_A-Za-z][_A-Za-z0-9]*  {
  return name;
}
_ = [ \\t]* 
`;

まず，var_def_lineのほうが変数の定義を返せるように調整します．
そのあと，var_defsの部分を調整し，var_def_lineの繰り返しがあった場合は，配列として返すように調整します．

$ npx tsc && npx jest
 PASS  ./MyParser.test.js
  MyParserのテスト
    ✓ フロー宣言のテスト (40ms)
    ✓ 構文木のテスト (8ms)
    ✓ 構文木のテスト2 (5ms)
    ✓ 構文木のテスト3 (5ms)

Test Suites: 1 passed, 1 total
Tests:       4 passed, 4 total
Snapshots:   0 total
Time:        1.172s
Ran all test suites.

これで一通り完成しました！！

プログラミング言語の作り方

ここから，自分流のプログラミング言語の作り方をまとめます．

パーサー部の作り方

自分が書きたい言語の文法の例を考えます．(例：A.c -> B)
1.をパースするテストを書きます．
2.を満たす実装を書きます．
同じ文法の別の例を考えます．(例：C.c -> D)
4.をパースするテストを書きます．
全てのテストを満たす実装を書きます．
4.-7.を自分が満足するまで書きます．

構文木の作り方

自分が書きたい言語の文法とそれに対応するデータ構造の例を考えます．(A.c -> Bとjsonの関係)
1.を満たすテストを書きます．
2.を満たす実装を書きます．
同じ文法の別の例を考えます．(例：C.c -> D)
4.を満たすテストを書きます．
全てのテストを満たす実装を書きます．
4.-7.を自分が満足するまで書きます．

究極的に言ってしまえば，

自分の言語の例を考える
テストを書く
実装する
同様の文法の別の例を満足するまで書く．

ということを繰り返し続けます．

テスト駆動と言語製作

自作プログラミング言語を作るためには

小さな仕様から徐々に作成できる手法
バグを作りこまない工夫

という2つのアプローチが必要だと書きました．
今回，このドキュメントで，小さな仕様から大きくしていく方法を示しました．そして，バグを作りこまない工夫としてテスト駆動で行いました．
最初に書いたように，パーサーの制作は密結合になりやすく，バグが発生しやすいです．そこで，テスト駆動，テストライブラリを使うことで，手軽に回帰テストできる環境が重要になってきます．そのため，プログラミング言語をテスト駆動で作ることは，結構マッチしているのではないか．と思います．

まとめ

今回のドキュメントでは，プログラミング言語の作り方をまとめました．実際に自分で作ってみましたが，TDDの手法が非常に有用でした．自分の個人的なプロダクトにTDDを導入するのは初めてでしたが，実際にやってみると非常に良かったです．
テストを書くと，実装以外に時間がとられて，完成が遅くなるのでは？と言われます．ここに関しては，はっきりとした結論はでません．しかし，言えるとすれば，プログラミング言語を作る上では有用でした．
皆さんもプログラミング言語を作りたいと思ったらこのドキュメントを思い出していただけたらと思います．

自作プログラミング言語を仕様を決めずに作る入門

概要

仕様を決めずにプログラミング言語を作ることはできるのか？

言語を作る難しさ

言語のコンセプト

言語を作る準備

パーサーを実装

Phase01. Red

Phase02. Green

Phase03. Red

Phase04. Green

Phase05. Refactoring

Phase06. Red

Phase07. Green

Phase08. Red

Phase09. Green

構文木の構築

Phase01. Red

Phase02. Green

Phase03. Red

Phase04. Refactoring

Phase05. Red

Phase06. Refactoring

プログラミング言語の作り方

パーサー部の作り方

構文木の作り方

テスト駆動と言語製作

まとめ