More suitable Common Lisp abstraction to implement "self recursive let"

Question

Yesterday i ran into this pipes library for common lisp. It looks to some extent quite like clojure's lazy sequences abstraction, so i decided using it to implement the classic (and classy) clojure example of recursive lazy Fibonacci sequence definition in Common Lisp (for purely educational purpose).

that is what it looks like in clojure:

(def fibs (lazy-cat [0 1] (map +' fibs (rest fibs))))

(nth fibs 100)
;;=> 354224848179261915075N

that is quite simple, but the problem is that it keeps possibly huge lazy sequence in a global scope forever, so with some hacks i rewrote it so it can be used inside let binding:

(let [f (memoize (fn [f] 
                   (lazy-cat [0 1] 
                             (let [data (f f)]
                               (map +' data (rest data))))))
      fibs (f f)]
  (nth fibs 100))

;;=> 354224848179261915075N

the whole memoize and (f f) thing is to emulate data recursion in let.

then i've implemented it using the same approach in CL.

first, some utilities:

;; analogue of `list*` for pipes
(defmacro make-pipe* (x1 &rest xs)
  (if xs
      `(pipes:make-pipe ,x1 (make-pipe* ,@xs))
      x1))

;; wraps function so that it always returns the result of its first invocation
(defun once (f)
  (let ((called (cons nil nil)))
    (lambda (&rest args)
      (if (car called)
          (cdr called)
          (let ((res (apply f args)))
            (setf called (cons t res))
            res)))))

;; map over two pipes
(defun pipe-map2 (fn pipe1 pipe2)
  (if (or (eq pipe1 pipes:+empty-pipe+)
          (eq pipe2 pipes:+empty-pipe+))
      pipes:+empty-pipe+
      (pipes:make-pipe (funcall fn (pipes:pipe-head pipe1) (pipes:pipe-head pipe2))
                       (pipe-map2 fn (pipes:pipe-tail pipe1) (pipes:pipe-tail pipe2)))))

and then here goes the actual implementation:

(let* ((f (once (lambda (f) 
                  (make-pipe* 0 1 
                              (let ((data (funcall f f)))
                                (pipe-map2 #'+ data (pipes:pipe-tail data)))))))
       (fibs (funcall f f)))
  (pipes:pipe-values fibs 10))
;;=> (0 1 1 2 3 5 8 13 21 34 55 . #<CLOSURE (LAMBDA () :IN PIPE-MAP2) {10096C6BBB}>)

ok. it works. But the question is: as common lisp provides much more metaprogramming and compilation control utilities than clojure has, are there any proper ones that could make "self recursive let" (as i call it) more elegant, eliminating the need for ugly hack with memoized function calls, preferably avoiding mutable state (though i'm not sure it is possible at all)?

no need to avoid well hidden fully encapsulated internal semantically unobservable mutable state! all you need is LOVE (I mean, SETF). :) (that last one was a joke; are we allowed to make jokes still, on SO?) I don't know clojure nor pipes, but I once implemented these SICP-type lazy lists with nothing but RPLACA and RPLACD (which are equivalent to (setf (car...)) and (setf (cdr ...)) by putting a lambda-under-let into a list's tail cons cell, so that the function had access to that cell as "self" and could extend the list by setf'ing that cell to (cons value next-lambda). — Will Ness
(contd.) naturally I had to have special stream-car and stream-cdr that would check the type of an object in a list's cons cell and if that was a function, they'd just call that function. so I couldn't have lists of functions. that could be easily remedied of course (or worked around), but I didn't need it. — Will Ness
For a really different approach to lazy sequences see the SERIES library. cliki.net/SERIES — Rainer Joswig
(I misremembered; the generating function was in the cdr of the last cons cell, so there was no problem having functions as the elements in a list) — Will Ness
@WillNess thanks! i'm aware of the SICP style, still i've got a feeling i'm missing some concept from common lisp, i'm just unaware of. — leetwinski

leetwinski leetwinski · Accepted Answer · 2019-10-24T16:18:46

after some meditation, i've got this solution:

(defmacro letr ((name val) &body body)
  (let ((f-name (gensym)))
    `(let ((,name (symbol-macrolet ((,name (funcall ,f-name ,f-name)))
                    (let* ((,f-name (once (lambda (,f-name) ,val))))
                      ,name))))
       ,@body)))

which is in fact the rewrite of the initial solution by the means of symbol-macrolet

that one can be used this way:

CL-USER> (letr (fibs (make-pipe* 0 1 (pipe-map2 #'+ fibs (pipes:pipe-tail fibs))))
           (pipes:pipe-values fibs 10))
;;=> (0 1 1 2 3 5 8 13 21 34 55 . #<CLOSURE (LAMBDA () :IN PIPE-MAP2) {1001D3FCBB}>)

which is expanded into this:

(LET ((FIBS
       (SYMBOL-MACROLET ((FIBS (FUNCALL #:G596 #:G596)))
         (LET* ((#:G596
                 (ONCE
                  (LAMBDA (#:G596)
                    (CONS 0
                          #'(LAMBDA ()
                              (CONS 1
                                    #'(LAMBDA ()
                                        (PIPE-MAP2 #'+ (FUNCALL #:G596 #:G596)
                                                   (PIPES:PIPE-TAIL
                                                    (FUNCALL #:G596
                                                             #:G596)))))))))))
           (FUNCALL #:G596 #:G596)))))
  (PIPES:PIPE-VALUES FIBS 10))

it is, of course, only usable in quite a narrow field of situations, where the recursive (funcall f f) is delayed, like in this case. otherwise it leads to infinite resursion causing stack overflow. (Though i'm pretty sure it can still be improved somehow)

More suitable Common Lisp abstraction to implement "self recursive let"

2 Answers