Pythonで書くと数百行かかるというような話をみて、Prologで書いたものあったよな。ないな。書いてみるかと思って書いてみたのですが、Prologに詳しくない人用に解説を加えてみました。
a(V,G,[V|G]).
e(X,I,G,G):-member(X=I,G),!.
e(I,I)-->{integer(I)},!.
e(A+B,I)-->!,e(A,I1),e(B,I2),{I is I1+I2}.
e(X=E,V)-->!,e(E,V),a(X=V),!.
e(E1<E2,I)-->!,e(E1,I1),e(E2,I2),{I1<I2->I=1;I=0},!.
g(I:_,[I:E|Ls],[I:E|Ls]):-!.
g(I:_,[_|Ls],Rs):-!,g(I:_,Ls,Rs).
g(_:_,[],[]).
s(goto(I),_)-->{basic(P),g(I:_,P,Ls)},b(Ls).
s(X=E,Ls)-->!,e(E,V),a(X=V),b(Ls).
s(if(E,E1),Ls)-->!,e(E,V),({V=0} -> b(Ls);s(E1,Ls)).
s(print(E),Ls)-->!,e(E,V),{writeln(V)},b(Ls).
b([])-->!.
b([_:E|Ls])-->s(E,Ls).
run:- basic(P),b(P,[],_).
basic([
10:(a=0),
20:(print(a)),
30:(a=a+1),
40:(if(a<10,goto(20)))
]).
:- run.
:- halt.
SWI-Prologインストール、実行方法と結果
$ apt install swi-prolog
$ swipl a.pl
0
1
2
3
4
5
6
7
8
9
a/1 環境に追加
g/3 gotoの処理
s/4 文の評価
b/3 プログラムの評価
run/0 実行
basic/1 ベーシックのプログラム
最小限の機能しかないですが、これを元に拡張していけば何でも出来るようになると思います。
短くかける秘密は、Prologが数式処理に特化された言語であること。
普通のプログラミング言語とちがって数値演算よりも、数式処理に特化した珍しい言語で、ネストした関数を評価せずに単なる数式として扱い、返す値は論理値のみなので、使いづらく感じるかもしれないのですけど慣れると数式をそのまま扱える利点が生きてきます。
今回の実装ではDCG (通常はパーサに使うための引数を省略してかける機能) を環境の受け渡しに使っている（Haskellのモナドみたいなもん) のでより簡潔に書けました。
BASICの操作的意味を考えるとこんな感じになるんだろうなと思えるところがPrologで実装を書く楽しさでもあります。
どう考えて作ったのか？
たしか、番号付きのリストにプログラムを書いておいてリストを順番に実行すればいいんじゃね？
if文あればfor文とかの代わりにできるしgoto文を入れて変数が定義できて印字できればそれっぽく動くだろう。と漠然と、以下のようなプログラムを書いてみました：
basic([
10:a=0,
20:print(a),
30:a=a+1,
40:if(a<10,goto(20))
]).
SWI-Prologの:は通常パッケージの区切りなのでたしか結構優先順位が高く結合されるんだったような、、、って思って試してみてやっぱりそうだったので、カッコつければいいやということで、最終的な形になりました。
インタプリタはとりあえず１個目の規則を適当に書いてみました：
stmt(Σ,[N:X=E|Ls]):-expr(Σ,E,V),stmt([X=V|Σ],Ls).
ステートメントの実行時に式も評価しないといけないかってことで、
expr(_,I,I):-integer(I). % 整数の評価
expr(Σ,X,V):-member(X=V,Σ). % 変数
expr(Σ,A+B,I):-expr(Σ,A,I1),expr(Σ,A,I2),I is I1+I2. % 加算
くらいまで書いて環境をいちいち書くのめんどくさいなったのでDCGを使うことにしました。
DCGは引数を引き渡して次に渡してっていう以下のようなプログラムを
a(A,E1,E6):- b(A,E1,E2),c(E2,E3),d(A+1,E3,E4),e(E5,E6).
以下のような-->で書いて省略出来るという機能です。
a(A)--> b(A),c,d(A+1),e.
引数がリストだった場合にリストから値を取り出すとか、{}でくくると環境の引き継ぎはしないとかいう機能もあるのでパーサを書く時の入力リストを隠してかけて便利なのですが他にも使えます。
expr(I,I,Σ,Σ):-integer(I). % 整数の評価
expr(X,V,Σ,[X=V|Σ]):-member(X=V,Σ). % 変数
expr(A+B,I,Σ,Σ2):-expr(A,I1,Σ,Σ1),expr(Σ,A,I2,Σ1,Σ2),I is I1+I2. % 加算
としておいて、DCGで引数を省略します:
expr(I,I)-->{integer(I)}. % 整数の評価
expr(X,V,Σ,[X=V|Σ]):-member(X=V,Σ). % 変数
expr(A+B,I)-->expr(A,I1),expr(Σ,A,I2),{I is I1+I2}. % 加算
な感じで書けるんですが、変数を加えるところが悩むところです。
stmt([N:X=E|Ls],Σ,Σ2):-expr(E,V,Σ,Σ1),stmt(Ls,[X=V|Σ1],Σ2).
add 述語で環境を受けとり値を設定する述語を作っておき、DCGで省略するとうまくいきます：
add(XV,Σ,[XV|Σ]). % 環境に値を加える述語
stmt([N:X=E|Ls])--> expr(E,V),add(X=V),stmt(Ls).
普通のプログラマなら述語名は長いほうがいいんですが、操作的意味論の練習を考えると１文字に押し込むのに慣れたほうがいいので１文字にします。嫌がらせではありません。
a(XV,Σ,[XV|Σ]). % 環境に値を加える述語
s([N:X=E|Ls])--> e(E,V),a(X=V),s(Ls).
ということで他にif文やgoto文を追加しました。
b([])-->!.
b([_:E|Ls])-->s(E,Ls).
run:- basic(P),b(P,[],_).
プログラムの実行はrunとかで始めたいのでrun述語でベーシックのプログラムを読み込んで、一個ずつ取り出して実行するようにするなど微調整して完成です。
まとめ
Prolog で適当にBASICのインタプリタを作ってみたら実装は16行程度で書けました。
せっかくなのでどんな気持ちで書いたのか説明してみました。
構文なども書くといいので後で書こうと思います。