Named let in Clojure

December 14, 2022

As you might (or might not) know, Clojure does not have support for named let expressions. Those who used (or still using) Scheme knows that named let is a cool construct to express recursion cleanly, and to be precise, the only way to do iteration in Scheme.

So, how are they used in Scheme? Here is one example you can test in Racket or Guile:

(define lst '(1 2 3 4 5))

(let loop ((lst lst))
  (when (not (null? lst))
    (display (car lst))
    (loop (cdr lst))))

and this will print one number after another. loop name is not part of Scheme built-in special keywords, and you can use whatever name you like (experienced Scheme developers will frequently use lp because it is shorter to write).

In Clojure, we would express it like this:

(def lst [1 2 3 4 5])

(loop [lst lst]
  (when-not (empty? lst)
    (println (first lst))
    (recur (next lst))))

Clojure has built-in loop/recur primitive(s) used for iteration and recursion. Every other construct, like for, doseq et al., is expressed through loop/recur.

As I mentioned at the beginning of this post, Clojure won't let you have something like this:

(let loop [...]
  (loop ...))

but, we can easily have it via a simple macro. Here is the code:

(defmacro letn
  "Named let that allows self-recursion on declared name, like in Scheme.
The expression will be expanded to loop/recur, and no stack will be consumed.
When the name is not given, it behaves like an ordinary 'let'."
  [& exprs]
  (if (vector? (first exprs))
    `(let ~@exprs)
    `(clojure.template/do-template [~(first exprs)]
                                   (loop ~(second exprs)
                                     ~@(drop 2 exprs)) recur)))

As explained in the docstring, it will expand to loop/recur expression, so it can be used for infinite recursion without the stack consumption. Here is the example from the beginning, written with the new macro:

(letn loop [lst (rage 1 10)]
  (when-not (empty? lst)
    (println (first lst))
    (loop (next lst))))

;; Or you can use a different name. Beware, loops indefinitely!
(letn lp [i 0]
  (println i)
  (lp (inc i)))

;; if the name is not given, behaves like "let" from Clojure
(letn [a 1, b 2]
  (println (+ a b)))

The nice thing about this macro is that you can use whatever name you'd like, as the Clojure expression checker will be run after macro expansion. In the end, the above expressions will be expanded to a simple loop/recur.

Technicalities & limitation

Let's discuss limitations in our initial letn version.

First, clojure.template/do-template will blindly replace all occurrences of the assigned name to letn expression with recur keyword, which is OK for most cases. However, if you have nested letn calls, it will end up with nested loop/recur, which is not yet supported in Clojure. To explain it easily, check the code down below:

(letn lp1 [a 1]
  (letn lp2 [b 2]
    (lp1 (inc 1))
    (lp2 (inc 2))))

;; would be expanded to something like this
(loop [a 1]
  (loop [b 2]
    (recur (inc 1))     ;; where to recur, first
    (recur (inc 2))))   ;; or the second one?

The second issue is that our letn doesn't allow you to call the assigned name as a function, inside the places where a function is expected, like map et al. E.g., this won't work:

(letn lp [a 1]
  (map lp ...))

;; would be expanded to something like this, which doesn't make much sense
(loop [a 1]
  (map recur ...))

This is why in Scheme, named let is usually expanded to letrec, something like letfn equivalent in Clojure. But, with a slight difference: in Scheme, letrec allows proper tail calls that won't blow up the stack, but letfn doesn't have that property.

The solution or letn v2.0

Since we can't do much about the aftermentioned limitation of Clojure compiler, we can adjust our letn macro to use both approaches and let the developer decide which one to use. I'm not particularly eager to keep around multiple variations of letn macro, so I'm going to use metadata as deciding factor.

Here is the improved letn macro:

(defmacro letn [& exprs]
  "Named let that allows self-recursion on declared name, like in Scheme.
The expression will be expanded to loop/recur, so no stack will be consumed.
When the name is not given, it behaves as an ordinary 'let'.

If ^:nested metadata was added, expressions would be expanded to use
'letfn', so 'letn' can be nested and/or called inside
functions. Limitation of 'letfn' still applies - recursive calls will
consume stack."
   (vector? (first exprs))
   `(let ~@exprs)
   ;; check if we have attached ^:nested metadata to letn name
   (not (:nested (meta (first exprs))))
   `(clojure.template/do-template [~(first exprs)]
                                  (loop ~(second exprs)
                                    ~@(drop 2 exprs)) recur)
   `(letfn [(~(first exprs) ~(vec (take-nth 2 (second exprs))) ~@(drop 2 exprs))]
      ;; clojure doesn't have drop-nth, so emulate it with keep-indexed;
      ;; in short, keep only second elements from let expression
      (~(first exprs) ~@(keep-indexed #(if (= 1 (mod %1 2)) %2) (second exprs))))))

So, let's quickly overview how it behaves:

;; expands to ordinary 'let'
(letn [a 1, b 2]
  (+ a b))

;; expands to loop/recur
(letn lp [a (range 1 10)]
  (when-not (empty? a)
    (println (first a))
    (lp (next a))))

;; expands to letfn
(letn ^:nested lp1 [a '(a b c d e)]
  (letn ^:nested lp2 [b (range 1 10)]
     (and (seq a) (seq b))
       (println (first a) "|" (first b))
       (lp2 (next b)))

     (seq a) (lp1 (next a)))))

By using ^:nested metadata, now you control how the code is generated and how performant it can be (loop/recur usually should be the fastest option). Beware that the last example, where it displays all combinations between (a b c d e) and (1 ... 9) range, will loop indefinitely if ^:nested is not used. Why? I'm leaving that as an exercise to the reader ;)