←back to thread

Anonymous recursive functions in Racket

(github.com)
88 points azhenley | 5 comments | 04 Sep 25 00:39 UTC | HN request time: 0s | source
Show context
adityaathalye ◴[07 Sep 25 04:10 UTC] No.45155326[source]▶
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`.
replies(2): >>45156609 #>>45161445 #
JonChesterfield ◴[07 Sep 25 09:09 UTC] No.45156609[source]▶
Do the clojure folks still insist this is a feature, as opposed to an incomplete compiler leaking limitations into their world?
replies(1): >>45156665 #
jayceedenton ◴[07 Sep 25 09:19 UTC] No.45156665[source]▶
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?

replies(1): >>45160242 #
rgherdt ◴[07 Sep 25 17:27 UTC] No.45160242[source]▶
That doesn't work for mutual recursion, what is quite common in Scheme programs. Besides, tail call optimization is not only useful in recursion.
replies(1): >>45161417 #
1. skrishnamurthi ◴[07 Sep 25 19:33 UTC] No.45161417[source]▶
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...

replies(1): >>45161707 #
2. adityaathalye ◴[07 Sep 25 20:11 UTC] No.45161707[source]▶
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)

replies(1): >>45161973 #
3. skrishnamurthi ◴[07 Sep 25 20:47 UTC] No.45161973[source]▶
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.

replies(1): >>45165731 #
4. adityaathalye ◴[08 Sep 25 08:04 UTC] No.45165731{3}[source]▶
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.
replies(1): >>45168937 #
5. skrishnamurthi ◴[08 Sep 25 14:42 UTC] No.45168937{4}[source]▶
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.