TAPL de-Brujin index

TAPL読書会(2011/1/9)で第6章にて出てきた、s式の変数名に一意な数値を割り当てるアルゴリズム。

https://gist.github.com/774055

(use '[clojure.contrib.seq-utils])

(defn position [f coll]
  (first (positions f coll)))

(defn de-brujin-index [x coll]
  (position #(= x %) coll))

(defn append [x gamma]
  (cons x gamma))

(defn variable? [sexp]
  (not (coll? sexp)))

(defn abstraction? [sexp]
  (and (= (first sexp) :fn)
       (= (count sexp) 3)))

(defn application? [sexp]
  (coll? sexp))

(defn body [sexp]
  (first (next (next sexp))))

(defn removenames
  ([sexp]
     (removeterm sexp []))
  ([sexp gamma]
     (cond
      (variable? sexp) (de-brujin-index sexp gamma)
      (abstraction? sexp) (seq [:fn (removenames (body sexp) (append (second sexp) gamma))])
      (application? sexp) (map #(removenames % gamma) sexp))))