Clojure 의 매크로 시스템의 튜링완전 (애매한) 증명 feat SKI

우리가 하는 일반적 (Generic)  프로그래밍 언어는 튜링완전하다.

즉 튜링완전 관점에서 완전히 동치이고, 튜링완전한 언어 A 에서 가능한 일은 이론적으로 B 에서도 가능하다.

 

Scala / Haskel / F# .... TypeScript 등 언어의 "타입 시스템" 구조 자체가 튜링 완전하며, Type System 만을 이용해서 모든 기능을 이론적으로 구현 할 수 있다. - 타입스크립트 타입 레벨 프로그래밍 (velog.io) 참고

타입 레벨 프로그래밍이라고도 하는데, 정적타입언어에서 안전한 프로그래밍을 만들기 위하여 종종 쓰는 패턴이다

 

암튼, 튜링완전 조건은 다음과 같은데 (나무위키 피셜)

- 조건 분기문이 있다. if (...) then goto (...). 또는 branch if zero 등. for, while 등의 루프문은 모두 조건 분기문으로 바꿔 쓸 수 있다.
- 임의 위치의 메모리 값을 바꿀 수 있다.

인데, 람다 대수 는 튜링머신과 동치이고, 람다대수에서는 SKI 콤비네이터가 존재 하면 튜링완전하다.

따라서 SKI 콤비네이터의 존재만 증명하면 해당 시스템은 튜링완전 하다고 할수 있을텐데, 

 

clojure 의 macro 또한 튜링완전 하다고 하니, macro 로 SKI 콤비네이터를 만들수 있을것이다.

 

그래서 만들어보았다.

(require '[clojure.walk :as walk])
(def ma walk/macroexpand-all)

(defmacro eval-ski [& body]
  (let [f (first body) 
        ff (first (first body))
        ss (second (first body))
        ]
    (if (= ff `user/I) `(~ss)
        (let [fff (first (first (first body)))
              sss (second (first (first body)))] 
          (if (= fff `user/K) `(~sss) 
              (let [ffff (first (first (first (first body))))
                    ssss (second (first (first (first body))))]
                `((~ssss ~ss (~sss ~ss)))))))))

(defmacro Xfn [a b] (+ a (eval b)))
(defmacro Yfn [a] (* 2 a))

(ma `(eval-ski (I 1)))
;; => (1)

(ma `(eval-ski ((K 20) 10)))
;; => (20)

(ma `(eval-ski (((S Xfn) Yfn) 3)))
;; => (9)

(walk/macroexpand-all) 로 풀리면 컴파일 타임 맞겠지..?

아무리, Clojure 의 메크로라고 할지언정, function 은 아니기 때문에 도저히 compile Time 에 Closure 같은걸 구현해서 Local variable 같은 걸 챕처해올수 있는 방법을 도저히 모르겠어서, 그냥 eval-ski 메크로로 않에 값을 평가하는식으로 구현하였다. 뭔가 macro 에서 사용하는 seq 가 소비하면 없어지는듯;; 하여 일단 if 문 중첩함..

(defmacro K [x y] x) ;이건 가능

(defmacro K [x] `(fn [y#] ~x)); 이건 런타임 평가됨 (function)

(defmacro K [x]
  (defmacro inner [y#]
    x)) ; 요런건 안되는듯..

 

당빠 가장 기본적인 혼자쓰는.. 거밖에 안되긴 하는데 저 정도의 eval 이 되는거 보면, SKI 콤비네이터를 컴파일타임에 구현할수있지 않나 싶다.

 

(defmacro Mul [x y] (* (eval x) y))

(defmacro factorial [n]
  (let [nextn (dec n)]
    (if (zero? n)
      1
      `(Mul (factorial ~nextn) ~n ))))

(macroexpand-1 '(factorial 5))
(ma `(factorial 5))
;; => 120

이건 이것저것 테스트해보면서 확인한 컴파일 타임에 돌아가는 펙토리얼..

 

p.s.

Eval 을 쓰긴했는데;; 대충 main 함수에서 돌려보니까 compile time 맞는듯~