Prolog
単一化変数やバックトラックが使えるので操作的意味論の評価規則や型システムの型付け規則が簡単に書けて便利です。
SWI-Prolog インストール:
code:bash
brew install swi-prolog
apt install swi-prolog
構文
$ e ::= i\;|\;e+e
$ t ::= int
評価規則 $ e \darr i
$ \frac{}{i \darr i} EInt $ \frac{e_1 \darr i_1\;\;\;e_2 \darr i_2\;\;\;i_1\;plus\;i_2\;is\;i}{e_1+e_2 \darr i} EAdd
型付け規則 $ e : t
$ \frac{}{i:int}TInt $ \frac{e1:int\;\;\;e2:int}{e_1+e_2:int} TAdd
Prolog実装例:
code:prolog
% e.pl
% 評価規則 e(e,i)
e(I,I):- integer(I).
e(E1+E2, I):- e(E1,I1), e(E2,I2), I is I1+I2.
% 型付け規則 t(e,t)
t(I,int):- integer(I).
t(E1+E2,int):- t(E1,int), t(E2,int).
:- e(1+2+3,I),writeln(I),I=6.
:- t(1+2+3,T),writeln(T),T=int.
:- halt.
実行方法:
code:bash
$ swipl e.pl
10
int