Motivation

A short discussion on the #clojure-berlin channel ( Clojurians on Slack) got me interested in the letfn special form of clojure.core. The question was raised if the docstring of letfn describes it well. Wether it is, or not, I got interested in how it works and more specifically why it’s syntax is different from let for example.

Here is the documentation for letfn:

(doc letfn)

-------------------------
clojure.core/letfn
  (letfn [fnspecs*] exprs*)
Special Form
  fnspec ==> (fname [params*] exprs) or (fname ([params*] exprs)+)

  Takes a vector of function specs and a body, and generates a set of
  bindings of functions to their names. All of the names are available
  in all of the definitions of the functions, as well as the body.

As you can see it takes a vector of function specs and every function spec has the form (fname [params\*] exprs). I was quite surprised to see such a syntax for the specs: Each spec is a list, but it’s not quoted. So outside of the letfn special form the spec would be evaluated.

Why is this implemented this way? I am going to explore this and take this as an opportunity to dive into Clojure special forms, macros and evaluation.

What letfn does

You might wonder why letfn exists at all. Can’t it be simply replaced by let? Let’s investigate this a bit:

(let [foo (fn [] "abc")
      bar (fn [] "def")]
  (str (foo) (bar)))

;; => abcdef

We used let to define two functions in a local scope. We can also refer from one function to the other:

(let [foo (fn [] "abc")
      bar (fn [] (str (foo) "def"))]
  (bar))

;; => abcdef

However, the let bindings are evaluated sequentially, so we cannot refer from the first function to the second:

(let [bar (fn [] (str (foo) "def"))
      foo (fn [] "abc")]
  (bar))

;; Unable to resolve symbol: foo in this context

In this simple example you could of course just switch the positions of the bindings and define foo first and it would work just fine, as we saw in a previous example. Using let is not possible though, if you need to have mutually recursive function, that means each function calling the other, like this:

(let [recursive-even
      (fn [n] (if (= n 0)
               true
               (recursive-odd (dec n))))
      recursive-odd
      (fn [n] (if (= n 0)
               false
               (recursive-even (dec n))))]
  (recursive-even 7))

;; Unable to resolve symbol: recursive-odd in this context

(based on example in C on Wikipedia)

This will always fail, because each function depends on the other. A common way to resolve this, is inlining one function in the other.

letfn allows to keep separate functions calling each other:

(letfn [(recursive-even [n]
          (if (= n 0)
           true
          (recursive-odd (dec n))))
        (recursive-odd [n]
          (if (= n 0)
           false
           (recursive-even (dec n))))]
  (recursive-odd 7))

;; => true

Please pay attention to the different syntax of the bindings with let and letfn. In letfn there is no explicit usage of fn, instead a simple, unquoted list with the function name as the first element is provided. The other two elements are a vector of function parameters and the function body. In a nutshell, the function specifications resemble the usage of defn without the optional parameters:

(doc defn)

-------------------------
clojure.core/defn
([name doc-string? attr-map? [params*] prepost-map? body] [name doc-string? attr-map? ([params*] prepost-map? body) + attr-map?])
Macro
  Same as (def name (fn [params* ] exprs*)) or (def
    name (fn ([params* ] exprs*)+)) with any doc-string or attrs added
    to the var metadata. prepost-map defines a map with optional keys
    :pre and :post that contain collections of pre or post conditions.

Application of letfn

If you do not need to use mutual recursion in a local scope you should not need to use letfn at all. In the global scope you can make use of declare to have the functions names available and thus allowing mutual recursion. In a local scope without mutual recursion you simply can use let.

Implementation of letfn

Let’s have a look how letfn is implemented and see if it helps to understand why it uses this syntax.

(source letfn)

(defmacro letfn
  "fnspec ==> (fname [params*] exprs) or (fname ([params*] exprs)+)

  Takes a vector of function specs and a body, and generates a set of
  bindings of functions to their names. All of the names are available
  in all of the definitions of the functions, as well as the body."
  {:added "1.0", :forms '[(letfn [fnspecs*] exprs*)],
   :special-form true, :url nil}
  [fnspecs & body]
  `(letfn* ~(vec (interleave (map first fnspecs)
                             (map #(cons `fn %) fnspecs)))
           ~@body))

Let’s have a look what this pretty simple macro expands to, when applied to our example usage:

(->  '(letfn [(recursive-even [n]
                (if (= n 0)
                 true
                 (recursive-odd (dec n))))
              (recursive-odd [n]
                (if (= n 0)
                 false
                 (recursive-even (dec n))))]
        (recursive-odd 7))
     macroexpand-1
     clojure.pprint/pprint)

This expands to:

(letfn*
 [recursive-even
  (clojure.core/fn
    recursive-even
    [n]
    (if (= n 0) true (recursive-odd (dec n))))
  recursive-odd
  (clojure.core/fn
    recursive-odd
    [n]
    (if (= n 0) false (recursive-even (dec n))))]
 (recursive-odd 7))

Okay, that’s interesting. As you can see, this looks like the normal let binding now. The argument to letfn* is a normal binding vector, consisting of symbol - expression pairs, just like let.

The letfn macro is very simple. The use of the unquoted list in the function specs allows to have a very concise macro with a simple logic.

But what is letfn*? You won’t even find it in clojure.core. Well, at least not in the Clojure code. Instead you would need to have a look at the Clojure compiler, written in Java. letfn\* gets mapped to LetFnExpr. The compiler than also takes care of handling the mutual recursion and scoping. You can already dig into the code from the last link. I might myself get into this, but that’s the story of another blog post…. ;)

Nils