On: Anonymous recursive functions in Racket

[adityaathalye]

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)

[skrishnamurthi → adityaathalye]

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.

[adityaathalye → skrishnamurthi]

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.

[skrishnamurthi → adityaathalye]

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.