Anonymous recursive functions in Racket

In Clojure...

  ((fn [xs ret]
     (if (empty? xs)
       ret
       (recur (rest xs)
              (+ ret (first xs)))))
   (range 5) 0)

  => 10

nb. Clojure doesn't have automatic tail call optimisation. We need to explicitly emulate it with`recur`.

Do the clojure folks still insist this is a feature, as opposed to an incomplete compiler leaking limitations into their world?

Without the explicit recur it's far too easy to misidentify a tail call and use recursion where it's not safe.

Recur has zero inconvenience. It's four letters, it verifies that you are in a tail position, and it's portable if you take code to a new function or rename a function. What's not to love?

That doesn't work for mutual recursion, what is quite common in Scheme programs. Besides, tail call optimization is not only useful in recursion.

Tails calls are especially useful in languages with macros. You don't know what context you are in, you just generate the call that makes sense. If the call happens to be in tail-position, you get the benefit of it.

Moreover, you can design cooperating macros that induce and take advantage of tail-position calls.

Here's a simple example that motivates tail-calls that are not tail-recursive:

https://cs.brown.edu/~sk/Publications/Papers/Published/sk-au...

It's not the same thing. `recur` in Clojure must be in tail-position. This program

https://news.ycombinator.com/item?id=45154253

would therefore not work.

I was trying to say something like that with my note in the GP comment:

  > "nb. Clojure doesn't have automatic tail call optimisation. We need to explicitly emulate it with`recur`."

Just an average joe programmer here... advanced macrology is way above my pay grade :sweat-smile:.

Yeah, absent automatic TCO, we have to do it all, explicitly, by hand... `recur` and `trampoline`.

recur: https://clojuredocs.org/clojure.core/recur

  > Evaluates the exprs in order, then, in parallel, rebinds the bindings of

the recursion point to the values of the exprs.

  (def factorial
    (fn [n]
      (loop [cnt n
             acc 1]
         (if (zero? cnt)
              acc
            (recur (dec cnt) (* acc cnt))
  ; in loop cnt will take the value (dec cnt)
  ; and acc will take the value (* acc cnt)
  ))))

trampoline: https://clojuredocs.org/clojure.core/trampoline

  > trampoline can be used to convert algorithms requiring mutual recursion without stack consumption.

i.e. these emulate TCO, with similar stack consumption properties (they don't implement real TCO).

(edit: formatting)

Thanks for the pointers. Trampolining is an old idea for obtaining tail-calls. It's a kind of folk-wisdom that has been rediscovered many times, as the related work here shows:

https://dl.acm.org/doi/pdf/10.1145/317636.317779

Usually the trampoline is implemented automatically by the language rather than forcing the author to confront it, though I can see why Clojure might have chosen to put the burden on the user.

Yeah, Rich's HOPL lecture covers that ground...

https://clojure.org/about/history

  > Clojure is not the product of traditional research
  > and (as may be evident) writing a paper for this setting 
  > was a different and challenging exercise.
  > I hope the paper provides some insight into why 
  > Clojure is the way it is and the process and people
  > behind its creation and development.

Ah, I didn't know there was a HOPL paper! Some day I will have time to run a course reading HOPL papers. Some day I will have the time to read HOPL papers myself (-:. Thanks for the pointer.