When does Clojure check if recur appears in tail position?

Question

I'm trying to understand how Clojure's protection for recur in non-tail position works.

Clojure throws an exception if one writes code like that:

(def some_var (recur))

But what if I evaluate dynamically created code?

(def code '(recur))
(def some_var (eval code))

If you try to run this code in the REPL it seems to loop indefinitely. I expected it to throw an exception.

My questions:

When exactly does Clojure check if a recur was in tail position?

What are the exact semantics of my second code example (a recur in non-tail position executed dynamically)?

In your code using eval none of the lexical variables would be present, recur included. The error you get otherwise clearly shows it happens when compiling. — Sylwester
Thank you for your response! Am I understanding this correctly: If I eval code it gets it's own scope where recur is not defined? — le_me
Not exactly.. eval never uses the lexical scope of the code. Thus (let [x 19] (eval 'x)) will either evaluate to the global variable x or throw an error that x is not bound. Thus you cannot even call a local function from within eval since the binding doesn't exist in the environment where it gets evaluated. This is true for the other lexically scoped lisp languages as well. — Sylwester
ah I see, thanks! So what my eval does is evaluating recur in the global environment? Do you know if the semantics of doing so are defined somewhere? — le_me
@Sylwester, recur is a special form, so I don't think this has anything to do with lexical bindings. — Nathan Davis

Michał Marczyk Michał Marczyk · Accepted Answer · 2017-01-16T10:33:22

Explanation of the observed behaviour (infinite loop)

Your eval call actually results in the compilation of code in which recur does occur in tail position.

This is because of how eval is implemented – if you pass a form to eval which is a Clojure persistent collection, but which doesn't look like a def form, it gets wrapped in an fn form, that fn form is what is actually compiled, and then the resulting function is called.

Here's how this applies to your example:

(eval '(recur))

;; does '(recur) look like a def form?
;; → no, so transform the above, in effect, to
((eval '(fn [] (recur)))

;; more precisely, before handing off `'(recur)` to lower-level
;; compilation methods, wrap it in `(fn [] …)`:
(fn [] (recur))

;; then immediately call the resulting function with no arguments

;; ultimate result: loop endlessly

If you want to see where this happens, have a look at the public static Object eval(Object form, boolean freshLoader) method of clojure.lang.Compiler – link to the code as of Clojure 1.8.

Note that for the same reason typing (recur) into the built-in REPL currently (as of 1.9.0-alpha14) also loops endlessly. Different REPL implementations may or may not preprocess input forms in ways that prevent this before handing them off to eval.

Semantics of `recur`

These are exactly as explained in the official docs that Alex Miller linked to, in his answer and in comments thereon. To summarize, recur must be used inside a form that establishes a recur target; loop, fn and reify (inside method implementations) are all examples of such forms.

How the semantics are enforced

The above semantics are enforced at compilation time through the use of a handful of dynamic Vars that the compiler binds appropriately as it descends into various subforms of the top-level form passed for compilation. If you want to follow the control flow in detail, search for usages of NO_RECUR, LOOP_LABEL and LOOP_LOCALS in Compiler.java. The gist of it is that if a form is not in tail position, these Vars will be bound to values that indicate that this is the case while it is compiled.

ClojureScript uses a setup that's probably a little easier to follow, although it's based on the same basic idea. See analyzer.clj (stable link using the v1.9 tag); specifically *recur-frames* and disallowing-recur.

When does Clojure check if recur appears in tail position?

3 Answers

Explanation of the observed behaviour (infinite loop)

Semantics of recur

How the semantics are enforced

Semantics of `recur`