6 ms·
Tail call optimization can get you that, too. If you've written Scheme and/or gone through SICP you might be familiar with this: you write a recursive function,
by wging 4y ago
Tail call optimization can get you that, too. If you've written Scheme and/or gone through SICP you might be familiar with this: you write a recursive function, with the recursive function call as the last thing the function does ('tail-recursion'), and the compiler/runtime is able to optimize those recursive calls out rather than consuming one stack frame of space per call ('tail call optimization'). Clojure has loop/recur at least partially because it doesn't support tail-call optimization.
See https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call for more. Or SICP might be a good resource. https://sarabander.github.io/sicp/html/1_002e2.xhtml https://sarabander.github.io/sicp/html/1_002e2.xhtml
- amalgamated_inc 4y agoInterestingly, I almost prefer Clojure's `recur` semantically. Means you don't have to change the function name twice if you rename it, and it's hard to miss that you're recursing.
- masklinn 4y agoIf that's your worry then you can probably use the site's namesake. Though simple recursion is generally easy to spot.
- amalgamated_inc 4y agoWhich site's namesake? Hacker News?
- masklinn 4y agoThe Y combinator.
- amalgamated_inc 4y agoOh is this some Common Lisp thing? Never done it.
- masklinn 4y agoIt's much older, it's lambda calculus stuff. It's a way to implement recursion in a language which doesn't have recursive functions (but for some reason does have first-class functions). However it allows making anonymous functions recurse as well.
- wging 4y agoThose are cool properties. Another one is that you get a compilation error if your recursive call isn't in the tail position (and thus would actually grow the stack when you thought it didn't). One thing I don't think you can do with loop/recur, though, is optimize more complicated bits of recursion than a single function that calls itself. I.e. imagine a recursive call pattern that goes like f -> g -> f -> g -> ... (edit: I'm pretty sure this is why trampoline exists, though I've never really played with it... https://clojuredocs.org/clojure.core/trampoline https://clojuredocs.org/clojure.core/trampoline)
- 613style 4y agoIt's also nice to get an error when you `recur` from a non-tail position rather than the function just quietly becoming truly recursive.
- kazinator 4y agoIf you don't have to change a function's name twice when you rename it, that implies it is not called anywhere. :)
- dragonwriter 4y agoTCO also, unlike special syntax for direct tail recursion, works when the last call is not (directly) recursive (which supports indirect/mutual recursion, and just structures with deep call heirarchies that aren’t necessarily recursive.)
- pgorczak 4y agoOh I didn’t know it was kind of a workaround. I do like the fact that loop is not a function though but an expression like if or case. FWIW I think in Clojure you can use “recur” inside functions too to specifically indicate tail call recursion without relying on automatic optimization
- LandR 4y ago> without relying on automatic optimization I didn't think Clojure had any automatic optimization at all, due to the JVM not supporting it.
- fulafel 4y agoI think you mean automatic tail call optimization? (JVM has quite a lot of automatic optimizations that Clojure enjoys automatically, and clojure itself also has some automatic optimizations).