Hacker News Reader

Hacker News

Comment by brrrrrm | Hacker News Reader

Parent Full thread

brrrrrm

Edit: this is wrong.

For posterity my original comment was:

“From what I understand, tail calls can always (?) be lowered to while loops[1], which are expressible in WASM.

1. https://en.wikipedia.org/wiki/Tail_call#Relation_to_the_whil...

View on HN

This is possible, and trivial, when self-recursing: A -> A

If you have an A -> B, or A -> [indirect] call, that is not the case.

I am genuinely asking, is your position that a compiler cannot convert:

g(): a = 1+1; b = 2+a; print(b); return f()

into code that does not allocate stack space and just reuses the frame allocated for g()?

It depends on the calling convention used -- whether it is caller clean-up or callee clean-up. With caller clean-up, the stack pointer is left below the argument list when the function returns. With callee clean-up, it gets popped above the argument list. You can perform tail calls naturally if it's callee clean-up. (With caller clean-up, a compiler might hypothetically pull off a tail call if the callee's argument list takes less memory, but it's not something you could add as a language feature.)

Thanks, that explains the trouble I was having. I was thinking about it without any consideration to calling-convention.

When you have a set of functions that may recourse into each other, you can convert them into a iterative one by doing a `while cond {switch function_selector {..}}` block.

It's an ugly piece of code, but because of parsers, there is a huge amount of know how on it.

You really can't.

For example, what if those functions are in different modules or libraries? Tail calls are still supposed to work.

If they are statically linked, it's not a problem, and since AFAIK wasm doesn't support dynamic linking, the only problem is on crossing security boundaries, that will be probably kept unsolved anyway. (IMO, this one is better left unsolved, it's to complicated a problem to require for interoperability.)

Only tail recursion, not tail calls in general.

Reply on news.ycombinator.com