letrec.clj

(ns user
  (:use clojure.walk))

(defn unzip [n s]
  (if (seq s)
    (lazy-seq
      (map cons (first s) (unzip n (rest s))))
    (replicate n ())))

(defn- deref-vars [vars form]
  (let [replacement-map (into {} (map (fn [x] [x `(deref ~x)]) vars))]
    (postwalk-replace replacement-map (macroexpand-all form))))

(defmacro letrec [bindings & body]
  (let [[vars forms] (unzip 2 (partition 2 bindings))
        gensyms (repeatedly gensym)]
    `(let [~@(mapcat (fn [var] `(~var (promise))) vars)
           ~@(mapcat (fn [var form] `(~var ~(deref-vars vars form))) gensyms forms)]
       ~@(map (fn [var val] `(deliver ~var ~val)) vars gensyms)
       (let [~@(mapcat (fn [var] `(~var (deref ~var))) vars)]
         ~@body))))

;; Examples

(letrec [xs (lazy-seq (cons 1 ys))
         ys (lazy-seq (cons 2 xs))]
  (let [zs (take 10 xs)]
    (println "test1:" (identical? xs (rest xs))) ;; false
    (println "test2:" (identical? xs (rest (rest xs)))) ;; true
    (println "test3:" (identical? (rest xs) (rest (rest (rest xs))))) ;; true
    (println zs)))