この記事はNextremer Advent Calendar 2019の2日目の記事です。
また、この記事は以下3つのような連作記事の2つめです。
- shigoto-lisp: はじめてLispを実装するときに 〜 パース編
- shigoto-lisp: はじめてLispを実装するときに 〜 評価編 ←イマココ
- shigoto-lisp: はじめてLispを実装するときに 〜 適用編
前回のあらすじ
言語実装の知識があると、自作プログラムのためにちょっとした設定言語を設計し、それをパースしたり実行したりできるのでとってもよいです。前回の記事では言語実装の入門としてLispプログラム(S式)のパーサのつくりかたを、数値、シンボル(変数名/関数名)、リストの順で解説しました。
この記事では
前回の記事でできたなにもしない評価器に機能を追加します。本記事では以下の5、6、7を実装します。
- 入力文字列をそのまま出力するだけのREPLをつくる (パース編)
- 数値をパースし評価する (パース編)
- シンボルをパースし評価する (パース編)
- リストをパースし評価する (パース編)
- 特殊形式を評価する (評価編)
- シンボルを値に束縛する (評価編)
- 組み込み関数を適用する (評価編)
- 関数オブジェクトを作成し適用する (適用編)
ちなみに成果物の処理系はこちらです(社内勉強会でつくったためこの記事とつくった順番が違います。コミットログは参考程度に参照してください)。
https://github.com/nextremer/shigoto-lisp
それではやっていきましょう。
5. 特殊形式を評価する
現時点での評価器のコードはこんなものでした。
// 式を評価する。「評価」といいつつまだ入力をそのまま返しているだけ。
const sl_eval = (form) => {
if (Array.isArray(form)) {
return form;
} else if (typeof form === 'number') {
return form;
} else if (typeof form === 'string') {
return form;
}
};
この節ではこの評価器に条件分岐を導入します。
その前にまず、これまで説明なしで使っていた用語の説明をしておきましょう。「オペレータ」「特殊形式」「関数」の3つです。オペレータは特殊形式と関数の総称です。Lispではオペレータ呼び出しはリストの形で記述されます。たとえば1と2の等値性を調べるオペレータ呼び出しは(eq 1 2)と記述します。リスト先頭のeqがオペレータ名、その後ろが引数です。
関数は組み込み関数やユーザが作成した関数オブジェクトのことで、関数の実行の前に引数の式が全て評価されます。特殊形式は、シンボル名についての条件分岐が評価器の中に直接記述されているもので、引数の式は評価されない場合もあります。両者の違いは要するに2つです。
- 特殊形式の引数の評価のタイミングは特殊形式によって異なる
- 関数はその実行の前に全ての引数が評価される
この節では条件分岐のオペレータifを導入しますが、ifは特殊形式であるべきでしょうか。それとも関数であるべきでしょうか。ifを用いたコードを書いてみて、どう動いてほしいかを検討します。代入のためのオペレータsetと足し算のためのオペレータ+があると仮定し、以下のようなコードを考えます(ちょっと恣意的なコードです)。
(set n 1) ; nに1を代入
(if (eq n 1) ; 条件式
(set n (+ n 1)) ; nが1のときだけ実行される
(set n (+ n 2))) ; nが1でないときだけ実行される
このコードが実行されたあとnの値は2になっていてほしい気がします。つまり条件が真のほうの式(set n (+ n 1))が一度だけ評価されてほしいです。
ここでもしifが関数だとすると、ifの引数はifの処理の実行前にすべて評価されなければなりません。(eq n 1)も(set n (+ n 1))も(set n (+ n 2))もすべて評価されifの処理がなんであれ、nの値は3になることでしょう。なのでifは「条件に合わないほうの式は評価すらしない」というふうに実装されるべきです。
したがって、ifは特殊形式です。条件に合うほうの式だけを評価するように実装します。真偽値は空リストを偽、それ以外の値は真とします。するとifは以下のように実装できます。
// 式を評価する。
// 式が配列(リスト)のときは先頭の要素(オペレータ名)によって分岐する。
// オペレータ名が`if`のときは条件式を評価して空リスト(偽)かどうか調べ、評価する式を決める。
const sl_eval = (form) => {
if (Array.isArray(form)) {
const name = form[0];
switch (name) {
case 'if':
if (sl_eval(form[1]) !== []) {
return sl_eval(form[2]);
} else {
return sl_eval(form[3]);
}
}
} else if (typeof form === 'number') {
return form;
} else if (typeof form === 'string') {
return env[form];
}
};
この状態でnpm startして条件分岐を楽しんでみてください。といっても上のようにset等のオペレータはなにもないのでまだおもしろいことはできませんが……。
6. シンボルを値に束縛する
つぎはシンボルを値に束縛(変数に値を代入)できるようにします。束縛(結び付いているシンボルと値の組)を表現するデータ構造と、評価器へのルールの追加、そして束縛を変更する特殊形式defineを用意することによって実現します。これらはREPLで以下のように使うことができるイメージです。
> (define n 42) ; シンボルの束縛
42
> n ; 束縛を参照
42
> (define n 44) ; シンボルの束縛を変更
44
> n ; 束縛を参照
44
まず、束縛のデータ構造を考えます。束縛はシンボルと値を結びつけるような構造で、同じシンボルへの操作は上書きでよいです。JSのオブジェクト(他の言語だとハッシュテーブル、辞書等)を用いることにしましょう。defineの引数は(define シンボル 値)とし、束縛のオブジェクトにシンボル(文字列)をキーとして値を設定します。束縛を参照するときは単にオブジェクトのフィールドを参照します。
実装はこのようになるでしょう。
// 束縛それ自体を表すオブジェクト。
var bindings = {};
// 式を評価する。
const sl_eval = (form) => {
if (Array.isArray(form)) {
const name = form[0];
switch (name) {
case 'if':
if (sl_eval(form[1]) !== []) {
return sl_eval(form[2]);
} else {
return sl_eval(form[3]);
}
// 特殊形式として`define`を追加。束縛を1つ追加し、値を返す。
case 'define':
let val = sl_eval(form[2]);
bindings[form[1]] = val;
return val;
}
} else if (typeof form === 'number') {
return form;
} else if (typeof form === 'string') {
// シンボルがきたときは、束縛の中を調べて値を返すように変更。
return bindings[form];
}
};
これで、この節の冒頭の例が動くようになります。
評価編のおわりに
ここまでが、shigoto-lisp評価編です。次の記事shigoto-lisp: はじめてLispを実装するときに 〜 適用編では関数を実行したり定義したりできるようにします。