Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Anonymous recursive functions in Racket

github.com

Post reply on HN
Print view View original

51–60 of 65 posts

Re: Anonymous recursive functions in Racket

#51

Post by skrishnamurthi »

rgherdt wrote: post #49
jayceedenton wrote: post #40

Earlier quoted context omitted.

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...

Re: Anonymous recursive functions in Racket

#52

Post by skrishnamurthi »

adityaathalye wrote: post #34

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`.

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.

Re: Anonymous recursive functions in Racket

#54

Post by adityaathalye »

skrishnamurthi wrote: post #52
adityaathalye wrote: post #34

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`.

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:.

Re: Anonymous recursive functions in Racket

#55

Post by adityaathalye »

skrishnamurthi wrote: post #51
rgherdt wrote: post #49

Earlier quoted context omitted.

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/P…

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)

Re: Anonymous recursive functions in Racket

#56

Post by skrishnamurthi »

adityaathalye wrote: post #55
skrishnamurthi wrote: post #51

Earlier quoted context omitted.

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/P…

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 w…

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.

Re: Anonymous recursive functions in Racket

#57

Post by fooker »

CyberDildonics wrote: post #30
skrishnamurthi wrote: post #22

Earlier quoted context omitted.

This isn't meant to be a good programming mechanism, it's meant to be an illustration of how to use the macro system. But also, if you're processing non-linear data, you're going to want to do with a recursive function anyway. E.g., when dealing with a tree. Code below; can't seem to get multi-line code-formatting so it looks hideous: #lang racket (require "anon-rec.rkt") (require rackunit) (struct mt ()) (struct nod…

Recursion just ends up using the call stack as a stack data structure. I would much rather use an actual stack data structure, that will be easier to debug and have better locality since there isn't an entire call frame overhead to put one value into the stack.

You’d be right if this was 1950. Since then literally all hardware, and compilers, have this specific use case so optimized that you’ll likely see the opposite if you benchmark it.

Re: Anonymous recursive functions in Racket

#58

Post by CyberDildonics »

fooker wrote: post #57
CyberDildonics wrote: post #30

Earlier quoted context omitted.

Recursion just ends up using the call stack as a stack data structure. I would much rather use an actual stack data structure, that will be easier to debug and have better locality since there isn't an entire call frame overhead to put one value into the stack.

You’d be right if this was 1950. Since then literally all hardware, and compilers, have this specific use case so optimized that you’ll likely see the opposite if you benchmark it.

Prove it. You can put your stack data structure on the stack anyway. A balanced tree isn't going to have more depth than your memory address bit length. Why would copying a single value be slower than pushing an entire call frame to the stack? Locality is what matters and there is no truth to what you're saying.

More important is the debugability. If you have a normal data structure you can see the full stack of values. If you use recursion you have to unwind through multiple call frames and look at each one individually.

Recursion is for people who want to show a neat clever trick, it isn't the best way to program.

Re: Anonymous recursive functions in Racket

#59

Post by adityaathalye »

skrishnamurthi wrote: post #56
adityaathalye wrote: post #55

Earlier quoted context omitted.

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 w…

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.

Re: Anonymous recursive functions in Racket

#60

Post by skrishnamurthi »

adityaathalye wrote: post #59
skrishnamurthi wrote: post #56

Earlier quoted context omitted.

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.
Post reply on HN