概要
プログラミング言語を簡単に作ることはPrologが有用であることを示し、Prologの使い方を説明し、実際にPrologを使って簡単な文法定義を行い、インタプリタを作り、型検査器を作ります。構文定義には正規木文法の定義ライブラリを示します。
todo:
- パーサ作る必要もないことも書く
- BNFの読み方を説明する
- 自然演繹の読み方を説明する
- Prologのアリティについて説明する
1. はじめに
プログラミング言語は、プログラマが１度は作ってみたいと夢見るものの１つです。しかし、なかなか簡単に作れるものではありません。一体どうすれば簡単に言語を作ってみることができるのでしょうか？
以下のような四則演算の言語(図1)を考えましょう:
\small
\begin{array}{c}
\begin{array}{ll}
\text{構文}\\
\begin{array}{lcll}
t & ::= & & \text{型}\\
& | & int & \text{整数}\\
\\
v & ::= & & \text{値}\\
& | & i & \text{整数}\\
\\
\end{array} &
\begin{array}{lcll}
e & ::= & & \text{式}\\
& | & i & \text{整数}\\
& | & e + e & \text{足し算}\\
& | & e - e & \text{引き算}\\
& | & e * e & \text{掛け算}\\
& | & e / e & \text{割り算}\\
\end{array} &
\\
\\
\text{型付け規則} \quad \boxed{e : t} & \text{評価規則} \quad \boxed{e \Downarrow v} \\
\\
\begin{array}{cl}
\dfrac{}{i : int } & (\scriptsize\textsf{T-I}\tiny\textsf{NT}\small)
\\ \\
\dfrac{e_1 : int \quad e_2 : int }{e_1 + e_2 : int } & (\scriptsize\textsf{T-A}\tiny\textsf{DD}\small)
\\ \\
\dfrac{e_1 : int \quad e_2 : int }{e_1 - e_2 : int } & (\scriptsize\textsf{T-S}\tiny\textsf{UB}\small)
\\ \\
\dfrac{e_1 : int \quad e_2 : int }{e_1 * e_2 : int } & (\scriptsize\textsf{T-M}\tiny\textsf{UL}\small)
\\ \\
\dfrac{e_1 : int \quad e_2 : int }{e_1 / e_2 : int } & (\scriptsize\textsf{T-D}\tiny\textsf{IV}\small)
\end{array}
&
\begin{array}{cl}
\dfrac{}{i \Downarrow i } & (\scriptsize\textsf{E-I}\tiny\textsf{NT}\small)
\\ \\
\dfrac{e_1 \Downarrow i_1 \quad e_2 \Downarrow i_2 \quad i\;\text{is}\;i_1 + i_2 }{e_1 + e_2 \Downarrow i } & (\scriptsize\textsf{E-A}\tiny\textsf{DD}\small)
\\ \\
\dfrac{e_1 \Downarrow i_1 \quad e_2 \Downarrow i_2 \quad i\;\text{is}\;i_1 - i_2 }{e_1 - e_2 \Downarrow i } & (\scriptsize\textsf{E-S}\tiny\textsf{UB}\small)
\\ \\
\dfrac{e_1 \Downarrow i_1 \quad e_2 \Downarrow i_2 \quad i\;\text{is}\;i_1 * i_2 }{e_1 * e_2 \Downarrow i } & (\scriptsize\textsf{E-M}\tiny\textsf{UL}\small)
\\ \\
\dfrac{e_1 \Downarrow i_1 \quad e_2 \Downarrow i_2 \quad i\;\text{is}\;i_1 / i_2 }{e_1 / e_2 \Downarrow i } &(\scriptsize\textsf{E-D}\tiny\textsf{IV}\small)
\end{array}\\
\end{array}
\\
\\
\text{図1. 四則演算}
\end{array}
あ、これ苦手なやつだと思うかもしれませんが、そんな人にこそ読んでほしいのです。
この簡単な四則演算を行う言語は引き算、割り算を省略するとPrologで以下のように記述できます:
:- use_module(rtg).
:- op(1200,xfx,--).
:- op(750,xfx,⇓).
term_expansion(A--B,A:-B).
% 構文
syntax(integer).
i ::= integer. % 整数
e ::= % 式
| i % 整数
| e + e % 足し算
| e * e % 掛け算
.
% 型付け規則
i(I)
--%---- T-Int
I : int.
E1 : int, E2 : int
--%----------------- T-Add
E1 + E2 : int.
E1 : int, E2 : int
--%----------------- T-Mul
E1 * E2 : int.
% 評価規則
i(I)
--%---- E-Int
I ⇓ I.
E1 ⇓ I1, E2 ⇓ I2, I is I1 + I2
--%--------------------------------- E-Add
E1 + E2 ⇓ I.
E1 ⇓ I1, E2 ⇓ I2, I is I1 * I2
--%--------------------------------- E-Mul
E1 * E2 ⇓ I.
run(E:T⇓V) :- e(E),E:T,E⇓V.
:- run(1:int ⇓ 1).
:- run(1*2+3*4:T ⇓ V),T=int,V=14.
:- halt.
何やらわけのわからない数式が書いてあるだけに見えるかも知れませんが、Prologを使うとこのように短く綺麗に理論的な記述に近くプログラミング言語を作ることが出来ます。ここではこのような言語の作り方を説明します。
もう一つ、四則演算で拡張した単純型付けλ計算(図2)を示します:
\small
\begin{array}{c}
\begin{array}{ll}
\text{構文}\\
\kern{20em}\\
\begin{array}{lcll}
t & ::= & & \text{型}\\
& | & int & \text{整数}\\
& | & t \rightarrow t & \text{関数}\\
\\
v & ::= & & \text{値}\\
& | & i & \text{整数}\\
& | & cls(Γ \vdash x\rightarrow e) & \text{関数閉包}\\
\end{array} &
\begin{array}{lcll}
e & ::= & & \text{式}\\
& | & ... & \text{省略 (図1と同じ)}\\
& | & x & \text{変数}\\
& | & \lambda (x \rightarrow e) & \lambda \text{抽象}\\
& | & e\;e & \text{関数適用}\\
& | & let\;x =e\;in\;e & \text{let 式}\\
\\
\end{array} &
\\
\\
\text{型付け規則} \quad \boxed{\Gamma \vdash e : t} & \text{評価規則} \quad \boxed{\varepsilon \vdash e \Downarrow v} \\
\\
\begin{array}{cl}
\dfrac{}{\Gamma \vdash i : int } & (\scriptsize\textsf{T-I}\tiny\textsf{NT}\small)
\\ \\
\dfrac{\Gamma \vdash e_1 : int \quad \Gamma \vdash e_2 : int }{\Gamma \vdash e_1 + e_2 : int } & (\scriptsize\textsf{T-A}\tiny\textsf{DD}\small)
\\ \\
\dfrac{\Gamma \vdash e_1 : int \quad \Gamma \vdash e_2 : int }{\Gamma \vdash e_1 - e_2 : int } & (\scriptsize\textsf{T-S}\tiny\textsf{UB}\small)
\\ \\
\dfrac{\Gamma \vdash e_1 : int \quad \Gamma \vdash e_2 : int }{\Gamma \vdash e_1 * e_2 : int } & (\scriptsize\textsf{T-M}\tiny\textsf{UL}\small)
\\ \\
\dfrac{\Gamma \vdash e_1 : int \quad \Gamma \vdash e_2 : int }{\Gamma \vdash e_1 / e_2 : int } &(\scriptsize\textsf{T-D}\tiny\textsf{IV}\small)
\\ \\
\dfrac{ x : t \in \Gamma }{\Gamma \vdash x : t } &(\scriptsize\textsf{T-V}\tiny\textsf{AR}\small)
\\ \\
\dfrac{\Gamma,x:t_1 \vdash e : t_2}{\Gamma \vdash \lambda(x \rightarrow e) : t_1 \rightarrow t_2 } &(\scriptsize\textsf{T-A}\tiny\textsf{BS}\small)
\\ \\
\\
\dfrac{\Gamma \vdash e_1 : t_2 \rightarrow t_1 \quad \Gamma \vdash e_2 : t_2}{\Gamma \vdash e_1 \; e_2 : t_1 } &(\scriptsize\textsf{T-A}\tiny\textsf{PP}\small)
\end{array}
&
\begin{array}{cl}
\dfrac{}{\varepsilon \vdash i \Downarrow i } & (\scriptsize\textsf{E-I}\tiny\textsf{NT}\small)
\\ \\
\dfrac{\varepsilon \vdash e_1 \Downarrow i_1 \quad \varepsilon \vdash e_2 \Downarrow i_2 \quad i\;\text{is}\;i_1 + i_2 }{\varepsilon \vdash e_1 + e_2 \Downarrow i } & (\scriptsize\textsf{E-A}\tiny\textsf{DD}\small)
\\ \\
\dfrac{\varepsilon \vdash e_1 \Downarrow i_1 \quad \varepsilon \vdash e_2 \Downarrow i_2 \quad i\;\text{is}\;i_1 - i_2 }{\varepsilon \vdash e_1 - e_2 \Downarrow i } & (\scriptsize\textsf{E-S}\tiny\textsf{UB}\small)
\\ \\
\dfrac{\varepsilon \vdash e_1 \Downarrow i_1 \quad \varepsilon \vdash e_2 \Downarrow i_2 \quad i\;\text{is}\;i_1 * i_2 }{\varepsilon \vdash e_1 * e_2 \Downarrow i } & (\scriptsize\textsf{E-M}\tiny\textsf{UL}\small)
\\ \\
\dfrac{\varepsilon \vdash e_1 \Downarrow i_1 \quad \varepsilon \vdash e_2 \Downarrow i_2 \quad i\;\text{is}\;i_1 / i_2 }{\varepsilon \vdash e_1 / e_2 \Downarrow i } & (\scriptsize\textsf{E-D}\tiny\textsf{IV}\small)
\\ \\
\dfrac{ x = v \in \varepsilon }{\varepsilon \vdash x \Downarrow v } &\scriptsize(\textsf{E-V}\tiny\textsf{AR}\small)
\\ \\
\dfrac{}{\varepsilon \vdash \lambda(x \rightarrow e) \Downarrow cls(\varepsilon \vdash x \rightarrow e) } &(\scriptsize\textsf{E-A}\tiny\textsf{BS}\small)
\\ \\
\dfrac{\begin{matrix}
\varepsilon \vdash e_1 \Downarrow cls(\varepsilon_1 \vdash x \rightarrow e) \quad
\varepsilon \vdash e_2 \Downarrow v_1
\\
\varepsilon_1,x=v_2 \vdash e_2 \Downarrow t_2
\end{matrix}}{\varepsilon \vdash e_1 \; e_2 \Downarrow t_1 } &(\scriptsize\textsf{E-A}\tiny\textsf{PP}\small)
\end{array}
\end{array}
\\
\\
\text{図2. 四則演算で拡張した単純型付け}\lambda\text{計算}
\end{array}
このような図は、プログラミング言語の理論で広く用いられています。BNF風の構文定義や、自然演繹という一階述語論理は標準的な記法なのです。正規表現を自然に使うように使い慣れることが大事です。この中からいくつか規則を取り出してみましょう:
\small
\begin{array}{cc}
\dfrac{
e_1 : int \quad
e_2 : int
}{e_1+e_2 : int}
&
\begin{array}{rll}
typing\;e_1\;:+:\;e_2 \;& = & Int \\
\;where \quad typing\;e_1 & == & Int \\
typing\;e_2 & == & Int
\end{array}
\\
\\
\dfrac{
\Gamma \vdash e_1 : t_2 \rightarrow t_1 \quad
\Gamma \vdash e_2 : t_2
}{\Gamma \vdash e_1\; e_2 : t_1}
&
\begin{array}{rll}
typing\;g\;c\;s\;(e_1:\$:e_2) = & (c_3,s_3,t_3) \\
where \quad (c_1,s_1,t_1) = &typing\;g\;c\;s\;e_1 \\
(c_2,s_2,t_2) = &typing\;g\;c_1\;s_1\;e_2 \\
(c_3,t_3) = &newvar\;c_2\\
s_3 = &unify(s_2,t_1\text{:->}\;t_2,t_3)
\end{array}
\\
\\
\text{自然演繹} & \text{Haskell}
\end{array}
図の左側にある自然演繹は右側の Haskell のプログラムに対応しています。上の２つの図は足し算の型はintになるという型検査器の一部です。下の２つの図は関数適用の型検査器の一部です。左の自然演繹の図は Haskell のプログラムに比べてずっと短いのでプログラミング言語の理論ではよく用いられています。
「いやーしかし訳がわからない。自然演繹だっけ？なんでこんな変な記法を使うのだ？」そう思うかも知れません。
自然演繹が理論的な図に用いられる理由？それは他の雑多な部分を排除してプログラミング言語の本質をうまく取り出し短く書くことでができるからです。一般的に、何らかの本質をうまく取り出して短く記述できる記法は理解に役に立ちます。例えば、C言語で連想配列を理解するよりスクリプト言語で連想配列を理解するほうが楽だったはずです。自然演繹は本質を取り出し短く書けるからプログラミング言語の理解を容易にするのです。
自然演繹を理解したい。自然演繹を理解するにはどうすればよいのでしょうか？自然演繹とは一階の論理型言語のようです。論理型言語といえばPrologがあります。Prolog でこのプログラムを書いたらどうなるのでしょう？以下にPrologで書いたプログラムを示します:
\small
\begin{array}{cc}
\dfrac{
e_1 : int \quad
e_2 : int
}{e_1+e_2 : int}
&
\begin{array}{l}
E1 : int, E2 : int\\
\text{--}\%\text{------------------}\\
E1+E2 : int.
\end{array}
\\
\\
\dfrac{
\Gamma \vdash e_1 : t_2 \rightarrow t_1 \quad
\Gamma \vdash e_2 : t_2
}{\Gamma \vdash e_1\; e_2 : t_1}
&
\begin{array}{l}
\Gamma \vdash E1 : (T1 \rightarrow T2),
\Gamma \vdash E2 : T2\\
\text{--}\%\text{---------------------------------------}\\
\Gamma \vdash E1\;\$\;E2 : T1.
\end{array}
\\
\\
\text{自然演繹} & \text{Prolog}
\end{array}
我々は、自然演繹を理解したいのですが、Prolog で書くと随分似せて書くことができます。
ところで、Prolog では関数型言語に近い記述も可能です:
\small
\begin{array}{cc}
\begin{array}{rl}
typing(E1:+:E2) & : int\\
:- \; typing(E1) & : int,\\
typing(E2) & : int.
\end{array}
&
\begin{array}{rll}
typing\;e_1\;:+:\;e_2 \;& = & Int \\
\;where \quad typing\;e_1 & == & Int \\
typing\;e_2 & == & Int
\end{array}
\\
\\
\begin{array}{rl}
typing(G,C,S,(E1:\$:E2)) & :(C3,S3,T1) \\
:- \quad typing(G,C,S,E1) & :(C1,S1,T1), \\
typing(G,C1,S1,E2) & :(C2,S2,T2),\\
newvar(C2)&:(C3,T3),\\
unify(S2,T1\text{:->}\;T2,T3) & :S3.
\end{array}
&
\begin{array}{rl}
typing\;g\;c\;s\;(e_1:\$:e_2) = & (c_3,s_3,t_1) \\
where \quad (c_1,s_1,t_1) = &typing\;g\;c\;s\;e_1 \\
(c_2,s_2,t_2) = &typing\;g\;c_1\;s_1\;e_2 \\
(c_3,t_3) = &newvar\;c_2\\
s_3 = &unify(s_2,t_1\text{:->}\;t_2,t_3)
\end{array}
\\
\\
\text{Prolog} & \text{Haskell}
\end{array}
全く同じとは行きませんが Prolog は Haskell と論文で用いられる図の間で色々とできる言語です。
「しかしPrologは処理速度が遅いのでは？」と思うかも知れません。Prologは確かに高速に動作する言語ではありません。しかしプログラミング言語の動作を理解するには高速な処理速度は必要ありません。プログラミング言語の本質を理解できればいいのです。多くの実験的な言語を作るだけなら高速性能は必要はないのです。
関数型言語と論理型言語は排他的に選択しなくてはならないものではないのではないでしょうか？論理型言語は本質を取り出し短く書けるので仕様を記述するのに向いていますが処理速度が遅い問題があります。関数型言語は論理型言語に比べると高速に動作しますが自然演繹に近い記述は出来ません。短く書くには論理型言語が向いていて、高速に動作させるには関数型言語が向いています。どちらもすばらしい技術です。
まとめ
プログラミング言語を簡単に作るにはどうしたらよいかを考えました。プログラミング言語をより簡単に理解するには本質をうまく取り出して短く記述することが出来る自然演繹が広く用いられています。自然演繹を理解するには論理型言語であるPrologを使うと便利です。簡単さに処理速度は関係ありません。したがって、プログラミング言語を簡単に作ってみるには Prolog が向いてます。
2. 簡単なProlog入門
一章では、プログラミング言語を理解するのにPrologが向いていることを説明しました。この章ではPrologを簡単に、しかし、プログラミング言語を作る話なので文法などに関しては形式的に説明します。
2.1. インストール
Ubuntu 環境をVMなり実機なり用意して SWI-Prolog をインストールしてください:
$ apt install swi-prolog
2.2. Hello World
% hello.pl
:- writeln('hello world').
:- halt.
Prologのコメントは % から始まる１行コメントと、/* */ でくくるブロックコメントがあります。
Prolog では関数はありませんが代わりに述語があります。
:- の後ろに節を記述し、文の終わりにピリオド . を書くことで即時実行することが出来ます。
Prolog のプログラムは 述語でプログラムを終了させることができます。
''でくくられた atom を writeln/1 述語を使って印字したあと、halt/0 述語を用いてプログラムを終了しています。
$ swipl hello.pl
hello world
2.3. Prologの構文
Prologの構文は極めて単純です。主な構文を示します:
\small
\begin{array}{c}
\begin{array}{lcll}
\kern{3em}&\kern{2em}&\kern{20em}&\kern{3em}\\
\text{atom} & ::= & \text{小文字から始まる識別子} \\
& | & \text{'' でくくられた文字列} \\
\text{変数} & ::= & \text{小文字で始まらない識別子} \\
\text{項} & ::= & \text{atom}\,|\,\text{変数}\,|\,\text{複合項} \,|\,\text{演算子項} \,|\, \text{リスト}\\
\text{複合項} & ::= & \text{atom(項1,...,項n)} \\
\text{演算子項} & ::= & \text{前置演算子 項} \,|\, \text{項 中置演算子 項} \,|\, \text{項 後置演算子} \\
\text{リスト} & ::= & \text{[] | [項1,...,項n] | [項1,...,項n|項]}\\
\text{述語} & ::= & \text{項} \\
& | & ! & \text{カット} \\
\text{頭部} & ::= & \text{項} \\
\text{節} & ::= & \text{述語} \\
& | & \text{節 , 節} & \text{連言} \\
& | & \text{節 ; 節} & \text{選択} \\
\text{文} & ::= & \text{:- 節}. \\
& | & \text{頭部 :- 節.} \\
& | & \text{頭部.} \\
\end{array}\\
\text{図1. Prolog の構文}
\end{array}
2.3.1. atom
\small\begin{array}{lcll}
\kern{3em}&\kern{2em}&\kern{20em}&\kern{3em}\\
\text{atom} & ::= & \text{小文字から始まる識別子} & \\
& | & \text{'' でくくられた文字列} & \\
\end{array}
atom は文字列と扱ってしまってよいと思いますが、Lispでいうインターンされた文字列であるシンボルと考えても良いでしょう。 test や 'test' 、 '+'、 'ABC' 等が atom です。
% test.pl
:- writeln(test).
:- writeln('test').
$ swipl test.pl
test
test
2.3.2 変数
変数は大文字から始まる変数ですが、Unicodeの記号や漢字、ひらがな、カタカナなども使うことが出来ます。
\small\begin{array}{lcll}
\kern{3em}&\kern{2em}&\kern{20em}&\kern{3em}\\
\text{変数} & ::= & \text{小文字で始まらない識別子} \\
\end{array}
例えば
% test2.pl
:- A=test,writeln(A),halt.
このプログラムを実行すると
$ swipl test2.pl
test
と出力されます。
Prologの変数は単一化を行うことが出来ます。
% test3.pl
:- C=D,aaa=A,A=C,writeln(D),halt.
上のプログラムを実行すると
$ swipl test2.pl
aaa
と表示されます。なぜなら、A は aaa なので、A=Cより、C=aaaであり、C=DよりD=aaaなのでDを表示するプログラム test3.pl は aaa を表示します。
論理型言語の変数はこのようなデータの伝搬を行うことができます。この機能を単一化機能といいます。
2.3.3 項
項はS式のようなただのデータです。しかし、Prologの場合は複合項や演算子も使うことが出来ます。
\small\begin{array}{lcll}
\kern{3em}&\kern{2em}&\kern{20em}&\kern{3em}\\
\text{項} & ::= & \text{atom}\,|\,\text{変数}\,|\,\text{複合項} \,|\,\text{演算子項} \,|\, \text{リスト}\\
\text{複合項} & ::= & \text{atom(項1,...,項n)} \\
\text{演算子項} & ::= & \text{前置演算子 項} \,|\, \text{項 中置演算子 項} \,|\, \text{項 後置演算子} \\
\text{リスト} & ::= & \text{[] | [項1,...,項n] | [項1,...,項n|項]}\\
\end{array}
リストは特殊な項です。
2.3.4 述語
\small\begin{array}{lcll}
\kern{3em}&\kern{2em}&\kern{20em}&\kern{3em}\\
\text{述語} & ::= & \text{項} \\
& | & ! &\text{カット} \\
\end{array}
述語は、項あるいは、カットがあります。カットはバックトラックを抑制する機能があります。
2.3.5 節
節は述語を , または ; で述語を複数接続したものです:
\small\begin{array}{lcll}
\kern{3em}&\kern{2em}&\kern{20em}&\kern{3em}\\
\text{節} & ::= & \text{述語}\kern{10em} \\
& | & \text{節 , 節} & \text{連言} \\
& | & \text{節 ; 節} & \text{選択} \\
\end{array}
, で接続された節は順番に実行されます。
; で接続された節は左側の節を実行し成功すれば終了しますが、失敗した場合は右側の節を実行します。
2.3.6 文
文には頭部と節がある文と、頭部のみの文と、節のみの文があります。
頭部がある文は述語を定義し、節のみの文は即実行します。
頭部には項を書くことが出来ます。
\small\begin{array}{lcll}
\kern{3em}&\kern{2em}&\kern{20em}&\kern{3em}\\
\text{頭部} & ::= & \text{項} \\
\text{文} & ::= & \text{:- 節}. \\
& | & \text{頭部 :- 節.} \\
& | & \text{頭部.} \\
\end{array}
2.4 主な述語
:- halt/1 プログラムを終了させます。
:- writeln/1 印字します。
:- maplist リストに対するmapを行います。
:- member/2 リスト内の値を取得します。
3. 簡単な言語の作成(四則演算)
大まかにPrologの機能を説明しましたのでここからはプログラミング言語を実際に作ってみましょう。
3.1. 構文
まずは、構文としてどのようなものが使えるかを考えてみましょう。
整数、足し算、引き算、掛け算、割り算が使えることにします。
3.2. 構文検査
この構文検査をPrologで書くと以下のように記述できます:
e(int(I)). % 整数
e(add(E1,E2)) :- e(E1),e(E2). % 足し算
e(sub(E1,E2)) :- e(E1),e(E2). % 引き算
e(mul(E1,E2)) :- e(E1),e(E2). % 掛け算
e(div(E1,E2)) :- e(E1),e(E2). % 割り算
:- e(int(1)).
:- e(sub(add(div(1,2),mul(2,3)),4)).
:- e(eq(11,2)). % エラー
:- halt.
これはPrologの演算子を使って以下のように書くことも出来ます:
i(I) :- integer(I) % 整数
e(I) :- i(I). % 整数
e(E1+E2) :- e(E1),e(E2). % 足し算
e(E1-E2) :- e(E1),e(E2). % 引き算
e(E1*E2) :- e(E1),e(E2). % 掛け算
e(E1/E2) :- e(E1),e(E2). % 割り算
:- e(1).
:- e(1/2+2*3-4).
:- e(11=2). % エラー
:- halt.
こちらのほうがより自然な式として表現できています。
このような構文定義は木構造に対して行うので、BNF のように文字列に文法を与える正規文法ではありません。木構造に対して文法を与える文法を正規木文法といいます。
3.3. RTG 正規木文法 ライブラリ
Prologのみでもプログラムの構文検査は出来ました。しかしながら、より分かりやすくPrologの木構造に対して正規木文法で構文定義できると便利です。そこで構文定義マクロライブラリ RTG (Regular Tree Grammar) を作成しました。
RTGのマクロを使うと以下のように構文定義を行い構文検査器を作ることができます:
:- use_module(rtg).
syntax(integer).
i ::= integer. % 整数
e ::= % 式
| i % 整数
| e + e % 足し算
| e - e % 引き算
| e * e % 掛け算
| e / e % 割り算
.
:- e(1).
:- e(1/2+2*3-4).
:- e(11=2). % エラー
:- halt.
RTG では ::= を用いて構文を宣言します。 syntax/1 を用いて syntax(integer) のように述語を構文として宣言することで構文内で使用できるようになります。 | で文法要素を区切り、最後にPrologの文の終わりとして . を書きます。
文法要素として | を使いたい場合は (|) または '|' と書くことでエスケープします。
syntax/1 あるいは ::= を用いて構文宣言をしない式はただの式として扱われることに注意が必要です。 RTG の全ソースは付録 A にありますので参照してください。
3.4. 評価器
次にインタプリタを作成してみましょう。
この評価規則は自然演繹スタイルで記述されており、上に書いてある式が成り立つならば、下の式が成り立つと読みます。
自然演繹スタイルの推論規則は、プログラミング言語の理論ではよく使われる表記方法です。型理論の教科書である TAPL や 京都大学の五十嵐先生による CoPL 等でも用いられていますし、論文でも同じような形式の図が多く使われています。
3.4.1 Prologによる実装
ではPrologで実装してみましょう:
% eval.pl
eval(I,I) :- i(I).
eval(E1+E2,I) :- eval(E1,I1),eval(E2,I2), I is I1 + I2.
eval(E1-E2,I) :- eval(E1,I1),eval(E2,I2), I is I1 - I2.
eval(E1*E2,I) :- eval(E1,I1),eval(E2,I2), I is I1 * I2.
eval(E1/E2,I) :- eval(E1,I1),eval(E2,I2), I is I1 div I2.
:- eval(1,1).
:- eval(1+2*3+4/2,9).
:- eval(1+2*3+4/2,R),writeln(R).
:- halt.
図とはだいぶ違いますが、Prologで書くと以上のように四則演算の計算機を記述することが出来ます。以下のようにコマンドラインから実行することが出来ます:
$ swipl eval.pl
9
3.4.2 Prologによる自然演繹スタイル風記述
前の節のPrologのプログラムは推論規則の図とだいぶ見た目が違いました。そこでここでは、Prologのマクロを使って自然演繹スタイルに似せた記述ができるようにしてみましょう:
:- op(1200,xfx,--).
:- op(750,xfx,⇓).
term_expansion(A--B,A:-B).
i(I)
--%---- E-Int
I ⇓ I.
E1 ⇓ I1, E2 ⇓ I2, I is I1 + I2
--%--------------------------------- E-Add
E1 + E2 ⇓ I.
E1 ⇓ I1, E2 ⇓ I2, I is I1 - I2
--%--------------------------------- E-Sub
E1 - E2 ⇓ I.
E1 ⇓ I1, E2 ⇓ I2, I is I1 * I2
--%--------------------------------- E-Mul
E1 * E2 ⇓ I.
E1 ⇓ I1, E2 ⇓ I2, I is I1 div I2
--%----------------------------------- E-Div
E1 / E2 ⇓ I.
:- 1 ⇓ 1.
:- 1+2*3+4/2 ⇓ 9.
:- 1+2*3+4/2 ⇓ R, R=9.
:- halt.
このプログラムの肝は、 -- 演算子と ⇓ 演算子定義と、マクロ定義
term_expansion(A--B,B:-A) です。
:- op(1200,xfx,--).
:- op(750,xfx,⇓).
Prologではop述語を用いることで、ユーザー定義の演算子を定義することが出来ます。ここで、-- 演算子は最高の優先順位 1200 の2項演算子、⇓は750の優先順位を持つ２功演算子として定義されています。
term_expansion は文に対するマクロを記述することが出来ます:
term_expansion(A--B,B:-A).
この定義では、-- 演算子は :- の中身をひっくり返したものと書き換えます。
自然演繹スタイルのプログラムとPrologのぷろぐらむは順番が逆なので--演算子を定義して使えば同じ順番に書けるというわけです。自然演繹スタイルの長い横棒は１行コメントで書くことにすれば好きな長さに変えることも可能です。そのため、見た目は謎な%が現れてしまいますが、分かってしまえばなんということはないはずです。
付録
付録 A. RTG 構文定義ライブラリ
% rtg.pl : Regular Tree Grammer validator generator
:- op(1200, xfx, [::=]).
term_expansion(A::=B, A_ :- syntax(A_,M,B)) :- assert(syntax(A)), apply_expansion(A,[M],A_).
%goal_expansion(syntax(A_,M,A),B_) :- syntax_expansion(M,A,B_), writeln(A_ :- B_).
goal_expansion(A,_) :- writeln(goal(A)),fail.
goal_expansion(syntax(_,M,A),B_) :- syntax_expansion(M,A,B_).
apply_expansion(A,M,L) :- atom(A), L =.. [A|M].
apply_expansion(A,M,L) :- A=..B,append(B,M,R), L =.. R.
syntax_expansion(M,A,R) :- var(A),apply_expansion(call,[A,M],R).
syntax_expansion(M,B|Bs,(B_,!);Bs_) :- syntax_expansion(M,B,B_), syntax_expansion(M,Bs,Bs_).
syntax_expansion(M,A,R) :- syntax(A),apply_expansion(A,[M],R).
syntax_expansion(M,A,M=A) :- atom(A),!.
syntax_expansion(M,A,(M=B,!,B_)) :- A =.. [A_|Ps], maplist(syntax_expansion,Ms,Ps,Es), B =.. [A_|Ms],!,
reverse(Es,Es1),foldl([A1,B1,(A1,B1)]>>!,Es1,!,B_).
syntax(atom).