ScalaのクアシクオートとPrologとクォートデータ構築子を持った処理系

## はじめに

Prolog は難しいという話題がよくあります。
Prologの難しさの１つは直接構文木を操作できることにあります。
そこでPrologのコードを Scala のクアシクォートを用いて書き換えてみました。

## 1. 加算のみの処理系

## 1.1. Scala のパーサコンビネータと代数的データ型

これをScalaで書くと以下のようになります:

```scala
// t0.scala
import scala.util.parsing.combinator._
object t0 extends App {
  trait E
  case class EInt(a:Int) extends E
  case class EAdd(a:E,b:E) extends E
  case class EMul(a:E,b:E) extends E
  object parser extends RegexParsers {
    def int = """(0|[1-9]\d*)""".r ^^ { _.toInt }
    def expr: Parser[E]
            = (term~("+"~>term).* ^^{case(a~b)=>b.foldLeft(a){(a,b)=>EAdd(a,b)}})
    def term= (fact~("*"~>fact).* ^^{case(a~b)=>b.foldLeft(a){(a,b)=>EMul(a,b)}})
    def fact= (int                ^^{EInt(_)}).
            | ("("~>expr<~")")
  }
  import parser._
  def eval(e:E):E = e match {
    case EInt(i) => EInt(i)
    case EAdd(a,b) => (eval(a),eval(b)) match {
                        case(EInt(a),EInt(b))=>EInt(a+b)
                        case(_,_)=> throw new Exception("error")
                      }
    case EMul(a,b) => (eval(a),eval(b)) match {
                        case(EInt(a),EInt(b))=>EInt(a*b)
                        case(_,_)=> throw new Exception("error")
                      }
  }
  def p(s:String):E =
    parse(expr,s) match {
      case Success(r,_)=>r
      case v=>throw new Exception("error:"+v)
    }
  println(eval(p("1+2+3")))
}
```

このプログラムはパーサコンビネータを使ってパースした後構文木Eを作り、evalで実行しています。

## 1.2. Scala のクォートで足し算のできる処理系

このプログラムをクアシクォートを使って書くと以下のように書くことが出来ます:

```scala
// t1.scala
import scala.reflect.runtime.universe._
object t1 extends App{
  def e:Tree=>Tree={
  case q"${i:Int}"=> q"$i"
  case q"$a+$b"=> val q"${i1:Int}"=e(a); val q"${i2:Int}"=e(b); q"${i1+i2}"
  }
  println(e(q"1+2+3"))
}
```

だいぶ短く書くことが出来ました。
クォートを使って式を表しクォートを使ってパターンマッチし結果をまたクォートして返却しています。
足し算を行う場合はクォートを使って計算した結果を取り出し足し合わせたものをまたクォートして返却しています。

## 1.3. Prolog で足し算のできる処理系

```prolog
% t1.pl
e(I,I) :- integer(I).
e(A+B,I) :- e(A,I1),e(B,I2),I is I1+I2.
:- e(1+2+3,R),writeln(R),halt.
```

Prologの場合クォートすることなく式を扱えるためより短く記述できます。
Scalaのパーサコンビネータがバックトラックを使うようにPrologのプログラムもバックトラックが使われています。

## 2. ラムダ計算

より複雑な例を見てみましょう。以下はラムダ計算とlet束縛をScalaの構文木を用いて実装してみたものです:

```scala
// t5.scala
import scala.reflect.runtime.universe._

object t5 extends App{
  def lookup(x:Name,g:Tree):Tree=g match{
  case q"($_,${y:Name}=$v)" if x==y=>v
  case q"($g,$_)"=>lookup(x,g)
  case q"()"=>throw new Error("not found "+x)
  }
  def e:Tree=>Tree={
  case q"$g|-${i:Int}"=>q"$i"
  case q"$a+$b"=> val q"${i1:Int}"=e(a); val q"${i2:Int}"=e(b); q"${i1+i2}"
  case q"$g|-${a:Name}"=>lookup(a,g)
  case q"$g|-($x=>$e)"=>q"$g|-(${x.name},$e)"
  case q"$g|-{..$h}" if h.length>1=>
    h.foldLeft(g){
    case(g,q"val $x=$e1")=>q"($g,$x=${e(q"$g|-$e1")})"
    case(g,e1)=>e(q"$g|-$e1")
    }
  case q"$g|-$v(...$h)" if h.length>0=>
    h.foldLeft(e(q"$g|-$v")){
    case(q"$h|-($x,$v)",List(b))=>e(q"($h,$x=${e(q"$g|-$b")})|-$v")
    }
  }
  println(e(q"()|-{val x=1+2;val y=x+4;y+x}"))
  println(e(q"()|-((x=>(y=>x+y))(1)(2))"))
  if(args.length > 0) {
    import scala.tools.reflect.ToolBox
    //def toolbox = scala.reflect.runtime.currentMirror.mkToolBox()
    def parse = runtimeMirror(ClassLoader.getSystemClassLoader()).mkToolBox()
      .parse(_)
    println(e(parse("()|-"+args(0))))
  }
}
```

最後の数行では、引数からScalaのtoolboxにあるパーサを使って読み込み実行するようにしてあります。
このようにすればわざわざパーサや構文木用の代数的データ型を定義することなくプログラム言語を実装し試してみることが出来ます。
結果として短いコードで言語を作成し実験してみることが出来ます。
ScalaのASTは関数呼び出しやブロックがリストとして認識されてくるので工夫が必要でした。

同様のPrologのコードは以下のとおりです:

```prolog
% t5.pl
:- op(650,yfx,$), op(10,fx,val).
e(_,I,I):-integer(I).
e(G,A+B,I):-e(G,A,I1),e(G,B,I2),I is I1+I2.
e(G,A,V):-member(A=V,G).
e(G,X->E,G|X->E).
e(G,val(X)=E1;E2,V2) :- e(G,E1,V1),e([X=V1|G],E2,V2).
e(G,A$B,V2) :- e(G,A,(H|X->E)),e(G,B,V),e([X=V|H],E,V2).
:- e([],val x=1+2;val y=x+4;x+y,R),writeln(R).
:- e([],(x->y->x+y)$1$2,R),writeln(R).
:- current_prolog_flag(argv, [X|_]),!,term_to_atom(T,X),e([],T,R),writeln(R);!.
:- halt.
```

## 3. クォートなどが演算子だった場合の考察

この話を調べ始めた動機は
「このような Prolog 上でクォートアンクォートを持った関数型言語を実装するにはどうしたら良いのか？」
という疑問を解くことにありました。

## 3.1. クォート、クアシクォート、アンクォート

```prolog
% t7.pl
:- op(650,yfx,$), op(10,fy,[#,*,\]).
e(_,I,I):-integer(I).
e(G,A+B,I):-e(G,A,I1),e(G,B,I2),I is I1+I2.
e(G,A,V):-member(A=V,G).
e(G,X->E,G|X->E).
e(G,X=E1;E2,V2) :- e(G,E1,V1),e([X=V1|G],E2,V2).
e(G,A$B,V2) :- e(G,A,H|X->E),e(G,B,V),e([X=V|H],E,V2).
e(G,A$B,A_$R) :- q(A),e(G,A,A_),e(G,B,R).
e(G,#A,R) :- e(G,A,A_),e(G,A_,R).
e(_,\A,A).
e(G,*A,A_) :- l(G,A,A_).
e(G,$A,A_) :- q(G,A,A_).
l(G,A$B,A_$B_) :- l(G,A,A_),l(G,B,B_).
l(G,A,A2) :- compound(A),A=..[O|L],maplist(l(G),L,L_),A_=..[O|L_],e(G,A_,A2).
l(_,A,A).
q(G,#A,A_) :- e(G,A,A_).
q(G,A,A_) :- compound(A),A=..[O|L],maplist(q(G),L,L_),A_=..[O|L_].
q(_,A,A).
:- begin_tests(e).
test(plus) :- e([],1+2,R),!,R=3.
test(val) :- e([], x=1+2; y=x+4;x+y,R),!,R=10.
test(let_binding) :- e([], x=1; x=x+1;x,R),!,R=2.
test(add_fun) :- e([], add=(x->y->x+y);add$1$2,R),!,R=3.
test(lambda) :- e([],(x->y->x+y)$1$2,R),!,R=3.
test(quote) :- e([],\(a$1+2$2+3),R),!,R=a$1+2$2+3.
test(quasiquote) :- e([],$(a$1+2$2+3),R),!,R=a$1+2$2+3.
test(list_quote) :- e([],*(a$1+2$2+3),R),!,R=a$3$5.
test(unquote) :- e([],$(a$ #(1+2)$2+3),R),!,R=a$3$2+3.
test(ref_of_exp) :- e([], x= $(1+2); y= #x;$(y$ #y$ #x),R),!,R=y$3$1+2.
test(eval_of_unquote) :- e([], x= $(1+2); y= #x;y,R),!,R=3.
test(ununquote) :- e([], x= $(1+2); y= $(x$ #x$ # #x);y,R),!,R=x$1+2$3.
test(quote_unquote) :- e([], x= $(1+2); y= *(add$x$ #x);y,R),!,R=add$1+2$3.
test(e_add_fun_of_exp) :-
    e([], add=(x->y->x+y); x= $(add$1$2); $(result$ #x $ # #x),R),
    !,R= result$(add$1$2)$3.
:- end_tests(e).
:- current_prolog_flag(argv, [X|_]),!,
   term_to_atom(T,X),e([],T,R),!,writeln(R);run_tests.
:- halt.
```

かなり普通にリスト的クォートと、クォート、クアシクォート、アンクォートを実装してみました。

`*` は Lisp の list に対応しており、引数はすべて評価されます。
`\` は Lisp のクォートに対応しており、単純に式として扱います。
`$` は Lisp のクアシクォートに対応しています。式の内部に`#`があるとその箇所のみ評価を行います。
`#` が通常の文脈で現れた場合は式は２度評価されます。Lisp の eval に相当します。

Scheme や Commpn Lisp 、 Template Haskell 、Elixir などを調べたなかで最も Prolog の式を扱うように扱えたのが Scala のクアシクォートでした。
この処理系は Scala の実装がありません。
Scala に単純に移植しようとするとこの規則をそのままかけないことに気がつくはずです。
Prolog の バックトラックの強力さを理解できることでしょう。

## 3.2 クォートデータ構築子

ここで少し風変わりなクアシクォート、アンクォートの機能を加えた処理系をPrologで試作してみました:

```prolog
% t6.pl
:- op(650,yfx,$), op(10,fy,[val,#,*]).
e(_,I,I):-integer(I).
e(G,A+B,I):-e(G,A,I1),e(G,B,I2),I is I1+I2.
e(G,A,V):-member(A=V,G).
e(G,X->E,G|X->E).
e(G,val(X)=E1;E2,V2) :- e(G,E1,V1),e([X=V1|G],E2,V2).
e(G,A$B,V2) :- e(G,A,H|X->E),e(G,B,V),e([X=V|H],E,V2).
e(_,*A,A).
e(G,A$B,A_$R) :- q(A),e(G,A,A_),e(G,B,R).
e(_,$A,A).
e(G,#A,R) :- e(G,A,R1),e(G,R1,R).
e(G,A$B,R$V) :- e(G,A,R),u(G,B,V).
u(G,#A,R) :- e(G,A,R).
u(_,A,A).
q(*_).
q(A$_) :- q(A).

:- begin_tests(e).
test(plus) :- e([],1+2,R),!,R=3.
test(val) :- e([],val x=1+2;val y=x+4;x+y,R),!,R=10.
test(let_binding) :- e([],val x=1;val x=x+1;x,R),!,R=2.
test(add_fun) :- e([],val add=(x->y->x+y);add$1$2,R),!,R=3.
test(lambda) :- e([],(x->y->x+y)$1$2,R),!,R=3.
test(quasiquote) :- e([],$a$1+2$2+3,R),!,R=a$1+2$2+3.
test(orginal_left_assoc_list) :- e([],*a$1+2$2+3,R),!,R=a$3$5.
test(unquote) :- e([],$a$ #(1+2)$2+3,R),!,R=a$3$2+3.
test(ununquote) :- e([],val x= $(1+2);val y= $x$ #x$ # #x;y,R),!,R=x$1+2$3.
test(list_unquote) :- e([],val x= $(1+2);val y= *add$x$ #x;y,R),!,R=add$1+2$3.
test(eval_of_unquote) :- e([],val x= $(1+2);val y= #x;y,R),!,R=3.
test(ref_of_exp) :- e([],val x= $(1+2);val y= #x;$y$ #y$ #x,R),!,R=y$3$1+2.
test(eval_add_fun_of_exp) :-
    e([],val add=(x->y->x+y);
         val x= $add$1$2;
         $result$ #x $ # #x
    ,R),!,R= result$(add$1$2)$3.
test(argv_eval) :- current_prolog_flag(argv, [X|_]),!,
                   term_to_atom(T,X),e([],T,R),writeln(R);!.
:- end_tests(e).
:- run_tests.
:- halt.
```

クォートはデータ構築子として実装してあります。
通常クォートをする場合、外側からプログラムを囲い込む形で行います。
一方この処理系は最初のデータにクォート演算子を付けそこに付随する引数の動作が通常の関数呼び出しではなくデータを構築するような動きをします。

## 3.2.1. アイディア

どうしてこのような演算子を思いついたを少し説明したいと思います。
まず、Elixirはすごいと O-Prolog の作者である LAL さんがいい始めました。そして、新しい Prolog を作りたいと言い始めました。
そこで自分も再度、考えてみました。 AST や Delphin といった処理系は依存型を持った素晴らしい処理系なのですが記法が独特で扱いにくいものでした。記号空間の枯渇しているのです。
Rust においてプログラムのリストは `;` の有無で値を返すかどうかを選択できます。
OCaml のリストは `[]` でくくられ `;` により分割されます。また、`::` で接続するという２通りの演算子を用います。
もったいないと考えました。プログラムは `;` で分割し `;` を最後に書いてあればリストにしてはどうかそう考えたのです。

```
a;b   プログラム
a;b;  リスト
```

後置演算子 `;` をリスト構築子のように考えれば `::` と `[]` を別の用途に使えるようになるでしょう。
そう考え始めたのがきっかけでした。
そこに 論理型言語と関数型言語のハイブリット言語である Picat の処理系を扱ったときにデータ構築子のようなかたちで `$` が使われていることをも合わせて、順番が逆のリストも構築できるのではないかと考えました。

```
a$b   関数呼び出し
$a$b  逆向きのリスト
```

このようにして今回のクォートデータ構築子のアイディアは生まれました。

Prolog の univ と呼ばれる複合型のデータをリストに分解する面倒さやcallの実装の複雑さも問題に感じていました。
Lisp の関数がカリー化されていないことも複雑に感じていました。
SML、 OCaml から Haskell にかけて変更が加えられた代数的データ型のコンストラクタがタグの形から関数呼び出しの形へと進化していることも関連しています。
アンクォートに `#` を採用したのは Ruby の影響です。
関数呼び出しに `$` を用いているのは Haskell の影響です。


## 4. まとめ

Prologはネストした関数を記述できない代わりに、クォートすることなく式のデータを簡潔に記述できます。
ScalaではPrologのわけの分からなさは減りますが、クアシクォートを使って若干記述量が増えますが同様のことが出来ます。
どちらも一長一短ありますが、型理論を学ぶ上ではPrologのような考え方が必要になってくるので両方理解できていると良いでしょう。

拡張した処理系としてクォートの機能を作成し、またクォートデータ構築子と呼んでいるちょっと違った形の関数型言語を実装しました。

Prologはクォートをせずに式を扱えます。
Scalaのクォートはとても柔軟に出来ているのでProlog的に式を扱うことが出来ます。
それらを組み合わせて考え新しいクォートの処理系を作ることが出来ました。