■

SKIコンビネータをばらすプログラムをgauche書いた。

やっぱものまね鳥の本はすごいと思う。初心者でもこんなことが出来るようになるとは。

てゆーかアルゴリズムがまんま書いてくれてあるだけだが。

(toSK '(x y) '(x y y)) => (S S (K I))
(toSK '(x y) '(y x)) => (S (S (K S) (K I)) K)

(define (car_combinator l)
  (define (car-combiter l2)
    (cond   ((not (pair? l2)) l2)
            ((null? l2) '())
            ((null? (cdr l2)) '())
            (else (cons (car l2) (car-combiter (cdr l2))))))
  (let ((result (car-combiter l)))
    (if (and (pair? result) (null? (cdr result))) (car result)
        (if (and (pair? l) (null? (cdr l))) (car l) result))))
 
 
(define (cdr_combinator l)
  (cond ((not (pair? l)) '())
        ((null? l) '())
        ((null? (cdr l)) (car l))
        (else (cdr_combinator (cdr l)))))
 
 
(define (find_var v l)
  (if (eq? v l) #t
      (find (lambda (m)
              (cond ((not (pair? m)) (eq? m v))
                    ((null? m) #f)
                    (else (find_var v m)))) l)))
 
 
 
(define (var_delete v X)
  (let ((Y (car_combinator X))
        (Z (cdr_combinator X)))
    (cond ((null? Z)
           (cond ((eq? v Y) 'I)
                 (else `(K ,Y))))
          ((and (eq? v Z) (not (find_var v Y))) Y)
          ((not (find_var v X)) `(K ,X))
          (else `(S ,(var_delete v Y) ,(var_delete v Z))))))
 
 
(define (toSK vars body)
  (define (toSK-iter r-vs l)
    (if (null? r-vs) l
        (toSK-iter (cdr r-vs) (var_delete (car r-vs) l))))
  (toSK-iter (reverse vars) body))

パターンマッチとか華麗に使いたかったけど、分からんので断念した。

gaucheで、
(a b c ... x y)
のようなリストを取って、
(a b c ... x) と y にパターンマッチさせてバラすようなことって出来ないのかな？

他の言語ではどうなのかしら。

しかしcoqどこ行った。