Tellur52の日記: コンビネータ論理のお勉強
ふむう、型付き言語の関数でコンビネータそのものを表現しようとすると無理があるのか。
そういう言語の場合、結局コンビネータはただのデータとして処理する方が見て確認するのも楽そうだなあ。
lispっぽい言語での実装例:
(defun ski (x)
(cond
((null x) '(I))
((listp (car x)) (ski (append (car x) (cdr x))))
((eq (car x) 'I) (ski (cdr x)))
((and (eq (car x) 'K) (not (null (caddr x))))
(ski (cons (cadr x) (cdddr x))))
((and (eq (car x) 'S) (not (null (cadddr x))))
(ski (append (list (cadr x) (cadddr x) (ski (list (caddr x) (cadddr x)))) (cddddr x))))
(t x)))(ski '((S (S (K S) K) I) (S (S (K S) K) I) a b))
(a (a (a (a b))))(ski '((S (S (K S) K) I) (S (S (K S) K)) I a b))
(a (a (a b)))
ところで、Lazy Kなる関数型言語があるのだが、これがコードの書式に「SKI()」による表現と、Unlamba形式の表現と、「*i」の組(とおまけで「sk」)によるIota形式の表現と、「01」だけで表現するJot形式の表現を交ぜ書きできることになっていて、訳が分からない。
インタープリタを構成するとき、括弧のネストだけでなく、ネストのレベルそれぞれでの、「`*」の数と後ろの関数の数のチェックが要るのが面倒っぽい。
あと、定義を見る限り、以下は同じになってはいけないというのも面倒だ。
*(SI)i
`(SI)i
Zotみたいな考え方を適用すれば、以下のような関数定義で、「`*」を無理矢理「i」などと等価に扱ってチェックしない事にすることができそうな気もするが、うまくいくのかなあ。
- syntax
- semantics
- E → F
- [F] (K(KI))
- F → F B
- [F]([B])
- F → ε
- ^c.c(SK)(^f.fI)I
- B → i
- ^ujc.u(cujj)(^g.guj(cI))
- B → `
- ^ujcL.LK(^f.fI)(^lR.RK(^f.fI)(^rg.guj(c(lr)))
- B → *
- ^ujcL.LK(^f.fSK)(^lR.RK(^f.fSK)(^rg.guj(c(lr)))
- 以下略
コンビネータ論理のお勉強 More ログイン