COSAK

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

更新履歴

概要

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

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

入力:




出力:

仕様

構文:

formのことをと呼び、これがCOSAKで扱う唯一の入力である。 また、(form form)に含まれるform部分式と呼ぶ。(*)

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

値:
式(部分式)を評価して得られるものをと呼ぶ。 値は次のように再帰的に定義される。 また、値はそれぞれλ式としての意味を持つ。
意味
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(出力)
kk
ss
(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}のような表現はここで説明のために使ったものであり、実際の値の表示は次のようになっている。
表示
kk
ss
k1{C}(k C)
s1{C1}(s C1)
s2{C1, C2}((s C1) C2)
ただし、C, C1, C2は任意の値。

補足説明

サンプルコード

算術演算(0+1)

(((s ((s ((s k) k)) ((s ((s (k s)) ((s (k k)) (k k)))) ((s ((s (k s)) (k k))) (k k))))) (k s)) (((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s ((s (k s)) (k k))) (k k)))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) ((s k) k)))))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s ((s (k s)) (k k))) (k k))))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s (k k)) (k k))))) ((s (k k)) (k k))))) ((s ((s (k s)) (k k))) (k k))))

=> (k s) /* kの数が1つ = 1 */
符号化された数0に1を加え、分かりやすく表示する。
赤色表示を整形する
緑色符号化された数に1を加える
青色符号化された数0

算術演算(0+1+1)

(((s ((s ((s k) k)) ((s ((s (k s)) ((s (k k)) (k k)))) ((s ((s (k s)) (k k))) (k k))))) (k s)) (((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s ((s (k s)) (k k))) (k k)))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) ((s k) k)))))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s ((s (k s)) (k k))) (k k))))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s (k k)) (k k))))) ((s (k k)) (k k))))) (((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s ((s (k s)) (k k))) (k k)))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) ((s k) k)))))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s ((s (k s)) (k k))) (k k))))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s (k k)) (k k))))) ((s (k k)) (k k))))) ((s ((s (k s)) (k k))) (k k)))))

=> (k (k s)) /* kの数が2つ = 2 */
符号化された数0に1を加え、それにもう一度1を加え、分かりやすく表示する。
赤色表示を整形する
緑色符号化された数に1を加える
青色符号化された数0

高階関数( (λfx.f(fx))[suc][0] )

(((s ((s ((s k) k)) ((s ((s (k s)) ((s (k k)) (k k)))) ((s ((s (k s)) (k k))) (k k))))) (k s)) ((((s ((s (k s)) ((s (k k)) ((s k) k)))) ((s ((s (k s)) ((s (k k)) ((s k) k)))) ((s ((s (k s)) (k k))) (k k)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s ((s (k s)) (k k))) (k k)))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) ((s k) k)))))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s ((s (k s)) (k k))) (k k))))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s (k k)) (k k))))) ((s (k k)) (k k)))))) ((s ((s (k s)) (k k))) (k k))))

=> (k (k s)) /* kの数が2つ = 2 */
『1を加える関数に"関数を受け取り、二回適用する関数を返す関数"を適用したもの』を符号化された数0に適用して、分かりやすく表示する。
赤色表示を整形する
緑色符号化された数に1を加える
青色符号化された数0
水色関数を二回適用する関数

算術演算(2+3)

(((s ((s ((s k) k)) ((s ((s (k s)) ((s (k k)) (k k)))) ((s ((s (k s)) (k k))) (k k))))) (k s)) ((((s ((s (k s)) ((s ((s (k s)) ((s (k k)) ((s k) k)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k s)))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k s)))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k)))))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k s)))))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k s)))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k)))))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k)))))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k s)))))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k))))))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k)))))))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k s)))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k s)))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k)))))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k s)))))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k s)))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k s)))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k)))))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k s)))))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k s)))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k)))))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k)))))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k)))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s (k k)) (k k))))) ((s (k k)) (k k)))))))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k s)))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k)))))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k)))))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k s)))))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k))))))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k))))))))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k s)))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k s)))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k)))))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k s)))))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k)))))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k))))))))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k s)))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k)))))) ((s ((s (k s)) ((s (k k)) (k k)))) ((s (k k)) (k k)))))))))) ((s ((s (k s)) (k k))) (k k))) ((s ((s (k s)) ((s (k k)) ((s k) k)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k ((s ((s (k s)) ((s (k k)) ((s k) k)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k ((s ((s (k s)) (k k))) (k k)))))) ((s (k k)) ((s k) k))))) ((s ((s (k s)) (k k))) (k k)))))))) ((s (k k)) ((s k) k))))) ((s ((s (k s)) (k k))) (k k))))) ((s ((s (k s)) ((s (k k)) ((s k) k)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k ((s ((s (k s)) ((s (k k)) ((s k) k)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k ((s ((s (k s)) ((s (k k)) ((s k) k)))) ((s ((s (k s)) ((s ((s (k s)) ((s (k k)) (k ((s ((s (k s)) (k k))) (k k)))))) ((s (k k)) ((s k) k))))) ((s ((s (k s)) (k k))) (k k)))))))) ((s (k k)) ((s k) k))))) ((s ((s (k s)) (k k))) (k k)))))))) ((s (k k)) ((s k) k))))) ((s ((s (k s)) (k k))) (k k))))))

=> (k (k (k (k (k s))))) /* kの数が5つ = 5 */
符号化された2に符号化された3を足して、分かりやすく表示する。
赤色表示を整形する
緑色符号化された数の足し算を行う
青色符号化された数2
水色符号化された数3

終わりに

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

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

このように定義されたΛx.Mはλ式のλx.Mと同等の役割を果たします。 なので、機械的にこの変換を行えば、どんなλ式もSとKだけで置き換えられてしまいます。(*) 詳しくは『計算論 計算可能性とλ計算』 高橋正子を参照してください。

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

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

関数抽象

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

xは任意の変数(空白を含まない文字の並び)、Mは任意の式。ただし、Mは任意の変数を含むことが出来る。 この式を評価して得られるのは、関数抽象を通常のに変換したものであり、それを評価したものではないことに注意。 つまり、関数抽象の変換と、それの評価は二回に分けて行う必要がある。

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

本当の終わりに

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

作るまでの経緯としては

  1. 講義中に『計算論 計算可能性とλ計算』のSK式の練習問題を解く
  2. 講義中にSK式のインタプリタをどうにか作れないかと思案
  3. 講義中に評価関数が(紙の上で)完成
  4. 講義終了後、実際に開発を開始
  5. プログラムが完成
微妙な出来具合となっているのは勢いで作ったため、 ということでお赦しください。