Pi-calculusでプログラミング
並行プロセス計算モデルで、Pi計算というのがあります。*1
lambda計算のような無闇やたらに抽象的な記述ですが、一応チューリング完全です。
とりあえず、pure Lispの5つ組が実現できればチューリング完全なのは示せるよね。
5つ組とは、car/cdr/cons/atom/eqのことで、。
cons(a,b)は(a.b)のペアを返す。
car(a.b)=a, cdr(a.b)=bである。
atom(a.b)=False,それ以外はTrueである。
eq(a,b)=True iff a==bである。
cons
KCons(head,tail,ret) = 'ret<head,tail>.KCons<head,tail,ret>
Cons(cons) = cons(head, tail, ret).(^newcons)('ret<newcons>.0 | KCons<head,tail,newcons>)
car/cdr
Car(car) = car(list, ret).list(head,tail).'ret<head>.0 Cdr(cdr) = cdr(list, ret).list(head,tail).'ret<tail>.0
atom
時間切れなのでまた次回。
*1:Pi計算って何って人は研究室にきてください :D
