Hacker News Reader

Comment by pgorczak | Hacker News Reader

Clojure’s loop expression hits this spot for me. It sets a recursion point to which you can jump using any logic inside the body you want, as long as it is from tail position. It’s like a while loop turned into an expression. I haven’t encountered any other way to write iterative expressions whose number of iterations isn’t known at the top (like map and reduce).

View on HN

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 for more. Or SICP might be a good resource. https://sarabander.github.io/sicp/html/1_002e2.xhtml

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

Those 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)

If you don't have to change a function's name twice when you rename it, that implies it is not called anywhere. :)

It's also nice to get an error when you `recur` from a non-tail position rather than the function just quietly becoming truly recursive.

If that's your worry then you can probably use the site's namesake. Though simple recursion is generally easy to spot.

Which site's namesake? Hacker News?

The Y combinator.

Oh is this some Common Lisp thing? Never done it.

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

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

Oh 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

> without relying on automatic optimization

I didn't think Clojure had any automatic optimization at all, due to the JVM not supporting it.

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

> I haven’t encountered any other way to write iterative expressions whose number of iterations isn’t known at the top (like map and reduce).

`unfold`, Rust's `loop`, generators, working tail recursion elimination (the lack of which loop/recur is a workaround for)

Is that like using "continue" in most C-syntax languages?

Only if you could pass parameters to "continue" (which you can't).

for x in y: yield x

Job done

Also known as (in Python, that is):

  yield from y

They were providing a partial example, "yield from" does not actually do what the original poster asks about, it merely proxies the inner iterable.

Reply on news.ycombinator.com