shigoto-lisp: はじめてLispを実装するときに 〜 パース編

この記事はNextremer Advent Calendar 2019の1日目の記事です。

また、この記事は以下3つのような連作記事の1つめです。

• shigoto-lisp: はじめてLispを実装するときに 〜 パース編 ←イマココ
• shigoto-lisp: はじめてLispを実装するときに 〜 評価編
• shigoto-lisp: はじめてLispを実装するときに 〜 適用編

あらまし

NextremerのCommon Lispだいすきエンジニア@t-sinです。

以前社内で「言語/Lispってどうやってつくるの？」というテーマで勉強会をしました。言語をつくることの意味や、つくりたいと思ってはいるもののどこから手をつけたらよいかを知らない人を対象としたライブコーディング風味の勉強会でした。

この記事では、何番煎じだかわかりませんが、そのとき話した内容をすこし組替えてLispのつくりかたを解説します。実は以前に発表とか記事とかでLisp実装したよーということは書いたのですが、実装のしかたを知ってる前提の書き方だったので、アリかなと思って書きました。

対象読者

• プログラミング言語 (JavaScript) の基本文法は知っているが、言語処理系のつくりかたは知らない人

実装に用いた環境

• JavaScript (node.js v12.11.0)
• jest (ユニットテストライブラリ)

勉強会成果物

ちなみに勉強会の成果物の処理系はこちらです（勉強会以降に記事のため手を入れています）。
https://github.com/nextremer/shigoto-lisp

なぜLispをつくるのか

じつは言語ををつくる機会というのはそこらじゅうに転がっています。たいていは「プログラムそのものを書き直すことなく外部から動き・値を指定したい」という欲求からくるものです。そのようなとき、以下のようなものを利用して先の目的を達成することができます。

• コマンドライン引数
• 値の書き込まれたCSVファイル
• iniやYAML等の設定ファイル
• 組み込み言語のスクリプト

さてこれらの入力、ライブラリを利用しないとしたら（利用できないとしたら）どのように処理したらよいでしょうか？　あるいは既存のファイル形式や入力形式では自身の求める要件を満たせないとしたら？

このようなときに言語処理系作成の知識があると大変役立ちます。入力文字列から情報を取り出すのには字句・構文解析の知識が役立ちます。スクリプトエンジンを用いるにしても、おおまかに言語処理系がなにをしているかくらいは知っておいたほうがよいでしょう。また、コマンドライン引数を解釈するのはインタプリタの一種と捉えることもできます。既存のファイル・入力形式では不足する場合、もちろん自分で入力の仕様（それはたいてい形式言語の形をしているでしょう）を設計し、さらにインタプリタを実装する必要があります。

これで「入力（という言語）を処理する」には言語処理系の知識があるとよい理由はおわかりいただけたと思います。

じゃあそこでなぜLispなんだということになりそうですが、ちゃんと理由があります。Lispは構文や実行モデルがCなどにくらべて単純なので、言語処理系作成の入門に最適なのです。

どのようなLispをつくるのか

本記事ではこれから述べる仕様に従うLispっぽい処理系を作ります。この処理系をshigoto-lispと呼びます。

構文

shigoto-lispのプログラムは文字列で記述され、以下の仕様を満たします。

1. プログラムは、式の連なりである
2. 式とは、リストかアトムのことである
3. アトムとは、数値かシンボルである
   1. 数値は、数字のみで構成される (正規表現: [0-9]+)
   2. シンボルは、アルファベットで始まり数字やアルファベットで構成される (正規表現: [a-z][0-9a-z]*)
4. リストとは、下記を満たすものである
   1. リストは始まりを(で開始し、)で終わる
   2. 要素の区切りには空白文字や改行を用いる
   3. 空リストはリストである: ()
   4. 式のリストはリストである: (式1 式2 ...)
   5. 上の式nはアトムやリストでもいいことに注意すること

したがって、たとえば以下のようなものはshigoto-lispのプログラムです。

()
123
abc
(1 2 3)
(test (test2 test3) (test4 (test5)))

なお上の構文の定義にはでてきませんが、コード中に説明を入れるため記事中では以下のコメント構文を使用します。

; セミコロンから
(hoge ; 行末までは
 fuga) ; 無視される

組み込みの特殊形式・関数

shigoto-lispでは以下の特殊形式や関数が使えることとします。「特殊形式」「関数」とは何なのかやそれらの違いについては「値の評価」を実装するときに説明します。

特殊形式

• if: 条件分岐
• define: 変数代入
• lambda: 関数オブジェクトの作成

関数

• +: 加算
• -: 減算
• *: 乗算
• /: 除算
• =: 等値判定
• .: 値の出力

どのようにLispをつくるのか

本記事でつくるLispっぽい処理系は以下のような処理をするプログラムです。

1. 標準入力から文字列を受け取る
2. 文字列の読み取り状態を表すオブジェクト(ストリーム)に文字列を詰める
3. ストリームから文字を読み取っていき構文木(式)を取り出す
4. 構文木(式)を評価して値を決定する
5. 評価結果の値を標準出力に書き出す

さて、実際にLispをつくるといっても生えろと念じてぱっとつくれるものではありませんので、段階を踏んでいきます。この記事の中では全体の仕様を最初に出すことはせずに、小さい仕様を実装し、それを膨らませていく形でつくっていきます。

本記事では以下の順番で実装していきます(リポジトリのコミット順とは違うつくりかたなのでコミットログは参考程度にしてください)。

1. 入力文字列をそのまま出力するだけのREPLをつくる (パース編)
2. 数値をパースし評価する (パース編)
3. シンボルをパースし評価する (パース編)
4. リストをパースし評価する (パース編)
5. 特殊形式を評価する (評価編)
6. シンボルを値に束縛する (評価編)
7. 組み込み関数を適用する (評価編)
8. 関数オブジェクトを作成し適用する (適用編)

それではやっていきましょう。

1. 入力文字列をそのまま出力するだけのREPLをつくる

まずはじめに、なにもしない REPLをつくります。npm init等は適宜行いエントリポイントとなるファイルを作成してください。このREPLでやることは3つだけです。

1. プロンプト>を出力する
2. 標準入力から文字列を受け取る
3. 受け取った文字列をただ標準出力に書き出す

そのコードはNode.jsではこのようになるでしょう。

var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});

reader.on('line', (line) => {
  console.log(line);
  process.stdout.write('> ');
});

reader.on('close', () => {
  console.log('bye!');
});

process.stdout.write('> ');

このプログラムを実行した例はたとえば以下のようになるでしょう。

$ npm start
> aaaaa
aaaaa
> bbbbb
bbbbb
> bye!

これが最初の一歩です。このコードを足掛かりにして膨らませていき、終いにはLispっぽいものになるのです。

2. 数値をパースし評価する

まずは文字列から数値を取り出してみましょう。ただし、後のことを意識しつつ。

ここでのプログラムは文字列です。文字列から、数値やネストされたリストやなんやを取り出さなければなりません。あるデータ（バイナリだったりテキストだったり）に埋め込まれた構造を取り出すことをパースする (parse) といいます。ここで必要なのは、入力である文字列からshigoto-lispの式を取り出すためのパーサ (parser) です。ここではsl_readという名前の関数を作っていきます。REPLが"Read Eval Print Loop"の略であることからshigoto-lispのパーサ・評価器・プリンタもそれぞれread eval printという名前にしたいですがJSにはevalという関数があるので接頭辞をつけることにしました。

パーサのつくりかたやその理論は(詳しくないので)ここでは述べませんが、この記事では再帰下降構文解析という方法でパースを行います。再帰下降構文解析はざっくりといえば、式やリストやアトムといった各構文単位の解析はそれぞれ関数を用意して分担し、調べる順番は大きな単位(上)から再帰呼び出しで下降¹していく方法です。

ではさっそく文字列をパースしていきたいですが、その前に準備を一つ。文字列を何文字目まで処理したかを相互再帰の中で持ち回れるよう、データ構造を定義します。いわゆるストリームです。ストリーム (これ自体はただのオブジェクト) をつくる関数と、ストリームから文字を読んだり見るだけだったりする関数を用意します。

const make_stream = (str) => {
  return {
    buf: str,
    pos: 0
  };
};

// 1文字読む
const read_char = (stream) => {
  if (stream.pos >= stream.buf.length) {
    return null
  }
  const char = stream.buf[stream.pos];
  stream.pos++;
  return char;
};

// 1文字チラ見する
const peek_char = (stream) => {
  if (stream.pos >= stream.buf.length) {
    return null
  }
  const char = stream.buf[stream.pos];
  return char;
};

shigoto-lispのプログラムの文法は1文字先読みするLL法でパースできます。できるったらできるんです。その1文字先読みを実現するためにpeek_charがあります。

このストリームを利用してパーサを構築するわけですが、バグったときのためにテストケースを簡単に用意しておきましょう。こんな感じで。

expect(sl_read(make_stream('0'))).toBe(0);
expect(sl_read(make_stream('      0'))).toBe(0);
expect(sl_read(make_stream('0123456789'))).toBe(123456789);
expect(sl_read(make_stream('1 '))).toBe(1);

数字の列がNumber型になるようにパースします。注意したいのは、読み取りたい文字の先頭にある空白は読み飛ばされるということです。この処理によって 0というような文字列からも正しく数値を取り出せるようにするほか、リストをパースするときの区切り文字のスキップにも用います。

上のテストをパスするコードはたとえばこんな感じです。

// 数値を読む。数字が続くかぎり溜めて、数字以外がきたら数値に変換して返す。
const sl_read_number = (stream) => {
  let s = [];
  while (true) {
    if ('0123456789'.includes(peek_char(stream))) {
      s.push(read_char(stream));
    } else {
      return parseInt(s.join(''));
    }
  }
};

// 式を読む。空白は読み飛ばし、最初の文字が数字だったとき数値を読む関数に飛ぶ。
const sl_read = (stream) => {
  while (' '.includes(peek_char(stream))) {
    read_char(stream);
  }
  const char = peek_char(stream);
  if ("0123456789".includes(char)) {
    return sl_read_number(stream);
  }
};

次になにもしないevalをつくりましょう。数値の評価(実行)結果は数値自身²ですので、数値型がきたら単にそれを返します。また、印字関数も書いてしまいましょう。これだけ最終形ですが特に説明はしません。

// 式を評価(実行)する。式の種類によってこれから条件分岐が増えていく。
const sl_eval = (form) => {
  if (char === null) {
    return 'nil';
  } else if (typeof form === 'number') {
    return form;
  }
};

// 値を印字する。最終進化系。
const sl_print = (form) => {
  if (typeof form === 'string') {
    return form;
  } else if (typeof form === 'number') {
    return `${form}`;
  } else if (Array.isArray(form)) {
    return '(' + form.map(sl_print).join(' ') + ')';
  }
};

さて！ 3つの道具が出揃いました。ここで入力行についてループする処理を以下のように書き換えてみましょう。

reader.on('line', (line) => {
  console.log(sl_print(sl_eval(sl_read(make_stream(line)))));
  process.stdout.write('> ');
});

この状態でプログラムを実行すると入力文字列から数値が読み取られ、その結果が表示されるのがわかると思います。
(空白だけとか入力するとundefinedと出会えます……)

ここまでが、REPLの処理の基本形です。

3. シンボルをパースし評価する

次に構文の拡張の練習として、シンボルを処理できるようにしましょう。シンボルとは変数名や関数名のことです。shigoto-lispでは、シンボルは単に名前の文字列で表現しましょう。シンボルに結び付けられた値はまだここでは実現せず、単にシンボルをパースしてそのまま表示するコードを書きます。具体的には以下のことをします。

1. シンボルを読む関数sl_read_symbolを追加する
2. sl_readの中にシンボルを読むような分岐を追加する

ユニットテストの確認項目も追加しておきましょう。

expect(sl_read(make_stream('s'))).toBe('s');
expect(sl_read(make_stream('s12'))).toBe('s12');
expect(sl_read(make_stream('12a'))).toBe(12);

これをパスするのは、たとえば以下のようなコードです。

// シンボルを読む。区切り文字(空白や括弧)がくるまで全ての文字を溜め込んでシンボルとする。
const sl_read_symbol = (stream) => {
  let s = [];
  while (true) {と
    let ch = peek_char(stream);
    if (ch !== null && !' ()'.includes(ch)) {
      s.push(read_char(stream));
    } else {
      return s.join('');
    }
  }
};

// 式を読む。数字以外のときをシンボルとして処理するよう分岐を追加した。
const sl_read = (stream) => {
  while (' '.includes(peek_char(stream))) {
    read_char(stream);
  }
  const char = peek_char(stream);
  if (char === null) {
    return 'nil';
  } else if ("0123456789".includes(char)) {
    return sl_read_number(stream);
  } else {
    return sl_read_symbol(stream);
  }
};

評価器のほうにもシンボルに対応する処理を追加しておきましょう。シンボルは変数名や関数名として利用しますが、ここではシンボルが束縛されている値の取り出し処理はまだ実装しません。後のほうで値の束縛(代入)機構を実現するときに書きます。したがって取り急ぎ、シンボルをそのまま返しましょう。

// 式を評価(実行)する。シンボル(文字列)のときは値をそのまま返す分岐を追加した。
const sl_eval = (form) => {
  if (char === null) {
    return 'nil';
  } else if (typeof form === 'number') {
    return form;
  } else if (typeof form === 'string') {
    return form;
  }
};

これでREPLがシンボルを受けつけるようになりました。npm startしてちょっとテストしてみてください。

4. リストをパースし評価する

さて、いよいよリストをパースします。まず、リストはJavaScriptの配列に対応させることにしましょう。すなわち(1 2 3)というリストがあったときそれをパースすると[1, 2, 3]になるということです。

リストは再帰的な構造なのでパースも再帰的に行います。ここで、リストの構文上の定義を思い出してみましょう。定義はこのような感じでした。

1. リストとは、下記を満たすものである
   1. リストは始まりを(で開始し、)で終わる
   2. 要素の区切りには空白文字や改行を用いる
   3. 空リストはリストである: ()
   4. 式のリストはリストである: (式1 式2 ...)
   5. 上の式nはアトムやリストでもいいことに注意すること

ここからわかることは4つです。

1. 開始文字が(であるため、sl_readの式の種類を判別する分岐に(がきたときの分岐を追加する必要がある
2. リストの中には式がいくつか入っているため、それらの式を個別に読み取らなければならない
3. 式を読んだあとには区切り文字がくるので、それをスキップしてやらなければならない
4. 式を読み区切り文字を飛ばすことを、リストの終了文字)がくるまでやらなければならない

1と3、4はよいでしょう。2について、慣れていないとわからない部分なので説明します。

リストは中に式を持ち、その式がさらにリストであるかもしれません。つまり、このような式が可能です。

;; こんなのや
(1 (2 (3 (4 5) 6) 7 (8 9)))
;; こんなのも
(((((a)))))

おそらくリストをパースするのにsl_read_listなる関数を実装することになるのですが、リストの中に現われる式をパースするにはどうすればよいのか。ここで相互再帰が登場します。再帰下降構文解析では「式やリストやアトムといった各構文単位の解析はそれぞれ関数を用意して分担し、調べる順番は大きな単位(上)から再帰呼び出しで下降していく方法」なのでした。もし構造単位が相互に再帰的になっているならば、構文単位の解析を行う関数が相互に再帰呼び出しを行う形になるはずです。

具体例をだします。たとえば単に数字を読み込むとき、以下のように再帰呼び出しが行われていきます(=>の後に関数次に行われる関数呼び出しとその結果を書いています。インデントで再帰呼び出しを表しています)。

let stream = make_stream("12");
sl_read(stream);  // 式
  => sl_read_number(stream);  // 数値
  => 12
=> 12

ネストのないリストのときは、sl_read_listが実装済みだとして以下のように再帰呼び出しが実行されるとよさそうです。

let stream = make_stream("(1 2 3)");
sl_read(stream);  // 式
  => sl_read_list(stream)  // リスト
  // リストの各要素に対して式を読む関数を呼ぶ
  => [sl_read_number(stream), sl_read_number(stream), sl_read_number(stream)]
  => [1, 2, 3]
=> [1, 2, 3]

ネストが1つだけの場合はこのように。

let stream = make_stream("(1 (2) 3)");
sl_read(stream);  // 式
  => sl_read_list(stream)  // リスト
  // リストの各要素に対して式を読む関数を呼ぶ
  => [sl_read_number(stream), sl_read_list(stream), sl_read_number(stream)]
    => sl_read_list(stream)
    => [sl_read_number(stream)]
    => [2]
  => [1, [2], 3]
=> [1, [2], 3]

そして「式の種類を判別し、対応する関数を呼ぶ」関数はもうありますよね。そう、sl_readです。なのでsl_read_listがすることは、リストの終了文字)がくるまでsl_readを呼び続けることです。

さて、そのようなコードを実際に書いてみます。

// リストを読む。リストの終了文字`)`がくるまでひたすら要素を処理する。要素の処理は`sl_read`に任せている。
const sl_read_list = (stream) => {
  let list = [];
  while (true) {
    if (')' === peek_char(stream)) {
      read_char(stream);
      return list;
    }
    list.push(sl_read(stream));
  }
};

// 式を読む。リストの開始文字`(`が来たらそれを読んだうえでリストの処理に飛ぶ分岐を追加した。
const sl_read = (stream) => {
  while (' '.includes(peek_char(stream))) {
    read_char(stream);
  }
  const char = peek_char(stream);
  if (char === null) {
    return 'nil';
  } else if (char === '(') {
    read_char(stream);
    return sl_read_list(stream);
  } else if ("0123456789".includes(char)) {
    return sl_read_number(stream);
  } else {
    return sl_read_symbol(stream);
  }
};

// 式を評価する。「評価」といいつつまだ入力をそのまま返しているだけ。
const sl_eval = (form) => {
  if (Array.isArray(form)) {
    return form;
  } else if (typeof form === 'number') {
    return form;
  } else if (typeof form === 'string') {
    return form;
  }
};

ここまでのコードを実行してみると、入力したリストがパースされ、そのままリストとして表示されます(S式として表示されるのはsl_printがリストに対応しているからです)。

ちなみに以下のテストコードでテストしました。

expect(sl_read(make_stream('()'))).toEqual([]);
expect(sl_read(make_stream('(1 2 3)'))).toEqual([1,2,3]);
expect(sl_read(make_stream('(1 (2 3) 4)'))).toEqual([1,[2,3],4]);

実はsl_read_listはバグを持っているのですがそれが何かは見つけてみてください。

パース編のおわりに

ここまでが、shigoto-lispパース編です。次の記事shigoto-lisp: はじめてLispを実装するときに 〜 評価編では評価器を高機能にしてプログラミング言語っぽさを増加させます。