COSAK

初めての方は、仕様やサンプルソースをお読みください。

更新履歴

• [2007/04/14] 完成
• [2007/07/13] 公開
• [2011/06/19] Iコンビネータおよび、Iコンビネータを生成する^^を追加

概要

COSAK(Constructed from Only S And K)はその名の通り、"S"と"K"だけから構成される関数型(?)言語です。 構文として、sとkと、それらを使った関数適用しか用意していません。関数抽象なんてどうでもいいです。 もちろん変数なんてありません。これで変数のスコープがどうとかいうことで悩む必要はなくなりましたね。

こう書くと、何も出来なさそうですが、実は、高階関数(のようなもの)を使えるなど、その表現力は意外と高いです。 実用的かどうかは、サンプルソースを見て実際に試してみて考えてください。すぐに分かります(笑)

構文：

• form ::= atom | (form form)
• atom ::= s | k

(*)式全体も部分式という。

値：
式(部分式)を評価して得られるものを値と呼ぶ。 値は次のように再帰的に定義される。 また、値はそれぞれλ式としての意味を持つ。

値	意味
k	λxy.x
s	λxyz.(x z)(y z)
k1{C}	λy.C
s1{C1}	λyz.(C1 z)(y z)
s2{C1, C2}	λz.(C1 z)(C2 z)

ただし、C, C1, C2は任意の値。

評価：
評価関数Eval[E] = Xを以下のように再帰的に定義する。^(*)

(*)Eは式でも値でも、両者が混ざったものでも許されるが、Xは必ず値になる。

E(入力)	X(出力)
k	k
s	s
(k M)	k1{Eval[M]}
(k1{C} N)	C
(s M)	s1{Eval[M]}
(s1{C1} N)	s2{C1, Eval[N]}
(s2{C1, C2} O)	Eval[((C1 O) (C2 O))]
(L N)	Eval[(Eval[L] N)]

ただし、M, N, Oは任意の式、Lはs, k以外の式、C, C1, C2は任意の値。

印字：
k1{C}のような表現はここで説明のために使ったものであり、実際の値の表示は次のようになっている。

値	表示
k	k
s	s
k1{C}	(k C)
s1{C1}	(s C1)
s2{C1, C2}	((s C1) C2)

ただし、C, C1, C2は任意の値。

補足説明

• 式(M N)のことを関数適用と呼び、NにMを適用するという。 また、このときのMを関数と呼ぶ。
• COSAKでは通常の数を扱えないので、適当に符号化して扱う。ここではChurch数に基づくものを使っている。
• Church数はそのままでは読みにくいので、最後には別の符号化を施す。
  • 0 = s
  • 1 = (k s)
  • 2 = (k (k s))
  • 3 = (k (k (k s)))

算術演算(0+1)

算術演算(0+1+1)

算術演算(2+3)

終わりに

SとKの世界はどうだったでしょうか？ 「こんなソース書けるか！」という意見が多いかと思いますが、ごもっともです。 私もこんなソース書けるわけがありません(笑) この言語、関数抽象を用意していませんが、関数抽象の代わりとなることを機械的に行えるんです。

関数抽象を行うために、以下のように再帰的にΛx.Mを定義します。

• Λx.x := ((s k) k)
• Λx.y := (k y)
• Λx.s := (k s)
• Λx.(M N) := ((S(Λx.M)) (Λx.N))

(*)実際は、atomに任意の変数を加える必要があります。

本当はY-combinatorを使って再帰を行うところまでやりたかったんですが、処理時間が異常に長いため諦めました。 まあ、処理速度のことを何も考えていなかったから仕方ないですね。 どれだけ再帰してたのやら……。 以下に関数抽象のやり方を載せておきます。興味がある人は色々試してみてください。

関数抽象

以下の式を評価すると、λx.Mという関数抽象を通常の式に変換したものを得られる。

• ((^ x) M)

(2011/06/19) ^の代わりに^^を使用すると、Iを使用する式を生成します。 Iはλx.xと同等のものです。

本当の終わりに

一応、書いておきますが、これはネタですよ。 この仕組みも、私が思いついたものでもなく、既にあるアイディアです。 SとKだけで上手くいくことの証明は『計算論 計算可能性とλ計算』 高橋正子の練習問題として用意されています。

作るまでの経緯としては

1. 講義中に『計算論 計算可能性とλ計算』のSK式の練習問題を解く
2. 講義中にSK式のインタプリタをどうにか作れないかと思案
3. 講義中に評価関数が(紙の上で)完成
4. 講義終了後、実際に開発を開始
5. プログラムが完成