Is this behavior with recur and pre/post a bug?

212 views
Skip to first unread message

Michael O'Keefe

unread,
Jul 24, 2014, 6:56:22 PM7/24/14
to clo...@googlegroups.com
Hello All,

I encountered the following behavior in Clojure 1.6 and wanted to check if it should be considered a bug or not. I would say yes but wanted to double check on the list first.

Here's a minimal test case that elicited the error:

(defn f
  [xs acc]
  (if (nil? xs)
    acc
    (recur (next xs) (+ (first xs) acc))))

(f [1 2 3 4] 0) => 10

Now, if I want to add pre/post conditions, the following happens:

(defn g 
  [xs acc]
  {:pre [(or (nil? xs) (sequential? xs)) (number? acc)]
   :post [number?]}
  (if (nil? xs)
    acc
    (recur (next xs) (+ (first xs) acc))))

=> this fails to compile with "CompilerException java.lang.UnsupportedOperationException: Can only recur from tail position"

In fact, it is only the post-condition that triggers the issue.

My guess would be that the recur statement is being knocked out of tail position by the mechanism for handling the post-condition assertion. It can be fixed in the code by adding an explicit loop:

(defn g2 [xs acc]
  {:pre [(or (nil? xs) (sequential? xs)) (number? acc)]
   :post [number?]}
  (loop [xs xs
         acc acc]
    (if (nil? xs)
      acc
      (recur (next xs) (+ (first xs) acc)))))
 
Thanks,

Michael O'Keefe

adrian...@mail.yu.edu

unread,
Jul 24, 2014, 7:27:16 PM7/24/14
to clo...@googlegroups.com
Indeed this is the case and no; I would not consider it a bug. Because you have specified a post condition on the return value, the clojure.core/fn macro is macroexpanding properly to support that post condition. By recursively macroexpanding the form, you can see the what the form will eventually look like to the compiler: https://gist.github.com/aamedina/49b4f8caf28c8b78c26b 

If you're using CIDER with Emacs, you can do this on any form by invoking M-x cider-macroexpand-all. 

Special forms, like recur, are handled by the compiler as special cases. The semantics of Clojure's recur special form forbid it from being used anywhere but the tail position of the body of either a fn* or loop*. As you can see from the gist, the return value is validated by the number? predicate before returning, or else it throws an error.

Andy Fingerhut

unread,
Jul 24, 2014, 7:34:23 PM7/24/14
to clo...@googlegroups.com
I do not know whether it is considered a bug or not, but it is definitely caused by the postcondition handling causing the recur to be knocked out of tail position.  Here is a reference to the code:

https://github.com/clojure/clojure/blob/master/src/clj/clojure/core.clj#L4185-L4192

Andy


--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Ambrose Bonnaire-Sergeant

unread,
Jul 24, 2014, 11:17:23 PM7/24/14
to clojure
Hi Michael,

I believe your post condition should read {:post [(number? %)]}.

Thanks,
Ambrose


--

Michael O'Keefe

unread,
Jul 25, 2014, 12:13:34 AM7/25/14
to clo...@googlegroups.com, abonnair...@gmail.com
Thank you everyone, for the replies:

  • The macro expansion was helpful
  • Andy, thanks for pointing out where the lines are -- very helpful
  • Ambrose, both (number? %) and number? are valid post-condition forms; the issue is that the post-condition check bumps the recur out of tail position
I guess the real question: is this worth filing a ticket for?

Thanks all,

Michael

Ambrose Bonnaire-Sergeant

unread,
Jul 25, 2014, 12:20:57 AM7/25/14
to clojure
On Fri, Jul 25, 2014 at 12:13 PM, Michael O'Keefe <michael....@gmail.com> wrote:
  • Ambrose, both (number? %) and number? are valid post-condition forms; the issue is that the post-condition check bumps the recur out of tail position


I'm aware of the context, I just wanted to make sure you were aware that {:post [number?]} is a no-op.

Thanks,
Ambrose

Andy Fingerhut

unread,
Jul 25, 2014, 12:25:10 AM7/25/14
to clo...@googlegroups.com
I do not see any straightforward change to Clojure that would enable this to work (someone else might, though).  Given that adding a loop form inside the function is a fairly straightforward workaround to the limitation, and the difficulty of enhancing it to avoid the limitation, I would personally be a bit surprised to see such a ticket accepted.

It doesn't cost anything but some time to create one, though.

Andy

Michael O'Keefe

unread,
Jul 25, 2014, 12:27:59 AM7/25/14
to clo...@googlegroups.com, abonnair...@gmail.com
Ambrose, thanks -- I was NOT aware of that. Sorry I misunderstood your original.

Andy, good advice and I agree. Thanks. I'll think on it then.

Cheers,

Michael

Bob Hutchison

unread,
Jul 25, 2014, 7:30:31 AM7/25/14
to clo...@googlegroups.com

On Jul 25, 2014, at 12:27 AM, Michael O'Keefe <michael....@gmail.com> wrote:

> Andy, good advice and I agree. Thanks. I'll think on it then.

Would you want one of your users going though this kind of thought process: I won’t file a ticked because I don’t think it can be fixed? It’s a bug, file the ticket. At the very least it can be documented.

Cheers,
Bob


Andy Fingerhut

unread,
Jul 25, 2014, 9:56:20 AM7/25/14
to clo...@googlegroups.com
Sorry, I forgot the following disclaimer: I am in no way an official voice for what will or will not be changed in Clojure in the future.  I am merely an interested observer of what has changed in Clojure in the past.  I've created and edited some tickets, written some Clojure patches, some of which have been accepted, many of which have been rejected.

I was providing Michael advice based upon my best guess of what would happen if he filed a ticket for this issue.  I could be completely 100% wrong.  Do whatever you like.

Andy


Steve Miner

unread,
Jul 25, 2014, 9:58:51 AM7/25/14
to clo...@googlegroups.com
I will call it a bug. It's definitely surprising to the user, and therefore worthy of a ticket. On first glance, it seems that the fix isn't too hard. In core.clj where the macro fn is redefined, we just need to wrap the section that handles the post condition either with a loop* or a fn* so that the body has the proper recur target. I'll try to make a patch and a test. If it works, I'll file a bug with the patch.

Michael O'Keefe

unread,
Jul 25, 2014, 10:12:14 AM7/25/14
to clo...@googlegroups.com
Thanks Bob, Steve, and Andy. I was trying to get logged into JIRA to file the bug report but I seem to be having a heck of a time -- I have a CA and am signed up at dev.clojure.org but when I try to log into JIRA, it gives me a nice "System Error" saying " user should not be null!". I've run out of time to deal with this right now but, Steve, if you get to it before me, feel free to submit the bug report.

Thanks all for the helpful discussions!

Michael

adrian...@mail.yu.edu

unread,
Jul 25, 2014, 10:35:25 AM7/25/14
to clo...@googlegroups.com
I do not believe this should be considered a bug. Recur is a special form that rebinds the bindings at the point of recursion with new values. It does not return a value. It does not get evaluated in the normal sense of the word. You cannot type check a value on a valueless expression. Just think about the implications of what a post condition on a recur form means. Even if you wanted to give value semantics to the evaluation of a recur form, there would be no single value it could check against. If you wanted the post condition to only be evaluated on the termination of the loop, or when the recur form is not conditionally present in the expression, then you are essentially asking the impossible for the compiler: it cannot know your intentions better than you do. 

Ambrose Bonnaire-Sergeant

unread,
Jul 25, 2014, 10:41:47 AM7/25/14
to clojure
Now that Steve mentions it, I have fixed this kind of issue in my own defn macros. IIRC adding an inner loop form did the trick.

Thanks,
Ambrose


--

Steve Miner

unread,
Jul 25, 2014, 10:58:19 AM7/25/14
to clo...@googlegroups.com
Ticket CLJ-1475 with my patch.

http://dev.clojure.org/jira/browse/CLJ-1475

Michael O'Keefe

unread,
Jul 25, 2014, 11:36:36 AM7/25/14
to clo...@googlegroups.com, abonnair...@gmail.com
Adrian, thanks for your input on whether this is a bug or not. Your viewpoint may yet prove to be the "accepted" one but I still felt like the original way I wrote the function should have meant: <check pre-conditions> <function runs> <check final return to caller>. In that sense, it feels like my original function g should have been semantically equivalent to g2... but we'll see.

Thanks for the ticket and patch, Steve! Also, I seem to now be able to finally log into JIRA -- I'll sign up to watch the ticket.

Anyhow, thanks everyone! We'll see what happens.

Michael

adrian...@mail.yu.edu

unread,
Jul 25, 2014, 12:00:14 PM7/25/14
to clo...@googlegroups.com, abonnair...@gmail.com
I hear what you're saying. Given that recur is a special form, there exists a closed set of exceptions to be worked around like this even theoretically, so I could see the argument for having this patch accepted and not opening pandora's box. 

Steve Miner

unread,
Jul 25, 2014, 6:27:24 PM7/25/14
to clo...@googlegroups.com
My first patch was buggy with destructured args so I had to withdraw it.

While working on a better patch, I came up against a related issue: Should the :pre conditions apply to every recur "call". I'm saying no. The :pre conditions should be checked just once on the initial function call and never during a recur. Any other opinions?

Ambrose Bonnaire-Sergeant

unread,
Jul 25, 2014, 6:37:51 PM7/25/14
to clojure
Yes :pre should apply to every recur, like usual without :post.

user=> ((fn [a] {:pre [(number? a)]} (recur 'a)) 1)
AssertionError Assert failed: (number? a)  user/eval5376/fn--5377 (form-init687485383035947214.clj:1)

That probably means that if :post is present, the preconditions should be moved inside the inner loop instead.

I can see how destructuring makes this a little tricky.

Thanks,
Ambrose


Daniel Kersten

unread,
Jul 26, 2014, 4:26:37 AM7/26/14
to clo...@googlegroups.com
The intuitive behaviour (to me) would be that :pre is applied to every recur as stated and post is applied only to the eventually returned value and this _should_ be considered a bug. My logic is as follows:

  1. A (pure, for simplicity of this argument) function, in the absence of erroneous inputs or bugs, should behave the exact same with and without pre/post conditions.
  2. The function body should be the same with and without pre/post conditions. That is I expect to be able to take any function and add pre/post conditions - given #1 above, there shouldn't be any difference except that the version with conditions will throw an exception when bad inputs/outputs are detected. That is, I think of pre/post conditions like I think of logging.
  3. Pre conditions should be applied to the function inputs whenever the function is given inputs - since recur essentially calls the function again, pre conditions should therefore be applied to each recur.
  4. Post conditions should be applied to the function return value. Since recur doesn't really return anything (and is working on intermediary possibly incomplete state anyway), post conditions should be applied only to the final returned value.
The reason I consider this a bug is because it violates 1, 2 and 3. Not considering it a bug because of implementation details is, IMHO, not the right approach, even if the patch never gets accepted and this never gets fixed.

That's my opinion anyway, hopefully its useful in some way.

Steve Miner

unread,
Jul 26, 2014, 10:00:03 AM7/26/14
to clo...@googlegroups.com
I'm giving up on this bug. My approach was adding too much complexity to handle an edge case. Hacking the fn macro is not as easy as it looks. :-)

I recommend the loop work-around if you run into this problem. Or refactor the recursive code into a separate function and call it from another function with the :pre and :post conditions in the non-recursive function.

http://dev.clojure.org/jira/browse/CLJ-1475

Ambrose Bonnaire-Sergeant

unread,
Jul 26, 2014, 10:39:31 AM7/26/14
to clojure
I'll give it a shot..


Ambrose Bonnaire-Sergeant

unread,
Jul 26, 2014, 11:30:42 AM7/26/14
to clojure
Hi Steve,

I think I got it right, please have a look: http://dev.clojure.org/jira/browse/CLJ-1475

Thanks,
Ambrose

Ambrose Bonnaire-Sergeant

unread,
Jul 26, 2014, 11:34:48 AM7/26/14
to clojure
Doh! I forgot preconditions :D

Fixing..
Ambrose

Michael O'Keefe

unread,
Jul 26, 2014, 11:52:49 AM7/26/14
to clo...@googlegroups.com, abonnair...@gmail.com
Nice work everyone on the patches -- I'm very impressed!

There's been a couple of questions about how to interpret this. My thought is we should try and mimic an explicit recursion:

In other words:

(defn g
  [xs acc]
  {:pre [(or (nil? xs) (sequential? xs)) (number? acc)]
   :post [(number? %)]}
  (if (seq xs)
    (recur (next xs) (+ (first xs) acc))
    acc))

... should act like:

(defn g3
  [xs acc]
  {:pre [(or (sequential? xs) (nil? xs)) (number? acc)]
   :post [(number? %)]}
  (if (seq xs)
    (g3 (next xs) (+ (first xs) acc))
    acc))

(g [1 2 3] 0)
(g3 [1 2 3] 0)

... where g3 actually works (but runs the risk of blowing the stack).

Michael

Ambrose Bonnaire-Sergeant

unread,
Jul 26, 2014, 12:44:40 PM7/26/14
to clojure
I handled preconditions, and added a new patch.

Thanks,
Ambrose

Ambrose Bonnaire-Sergeant

unread,
Jul 26, 2014, 12:50:54 PM7/26/14
to clojure
I reuploaded the patch 3 times for various reasons, please refresh to get the latest.

Thanks,
Ambrose

Steve Miner

unread,
Jul 26, 2014, 5:09:56 PM7/26/14
to clo...@googlegroups.com
I tried the latest patch from Ambrose for CLJ-1475. Looks good to me. Well done.

Michael O'Keefe

unread,
Jul 26, 2014, 7:12:49 PM7/26/14
to clo...@googlegroups.com
Awesome job, everyone! You guys rock!

Michael

Ambrose Bonnaire-Sergeant

unread,
Jul 27, 2014, 12:25:58 AM7/27/14
to clojure
Thanks for checking Steve.

Ambrose


On Sun, Jul 27, 2014 at 5:09 AM, Steve Miner <steve...@gmail.com> wrote:
I tried the latest patch from Ambrose for CLJ-1475.  Looks good to me.  Well done.
Reply all
Reply to author
Forward
0 new messages