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

Lisp in Dart 2.0

github.com

Post reply on HN
Print view View original

11–20 of 22 posts

Re: Lisp in Dart 2.0

#11

Post by ikfmpwdsoz »

uryga wrote: post #9
decafbad wrote: post #4

"Tail call optimization, which also implies tail recursion optimization" I thought those were exactly same thing.

You can also optimize non-recursive tail calls: def add10(y: int) -> int: return y+10 def def add11(x: int) -> int: # won't get optimized return add10(x)+1 def add11_tail(x: int) -> int: # should get optimized return add10(x+1) in `add11_tail` the call to `add10` is in the tail position, i.e. you can "forget" about `add11_tail`'s stack frame since it's not needed anymore. It's still needed in `add10`, because you sta…

I was under the assumption that that was called sibling call optimization, and TCO referred exclusively to recursive calls. Was that just an LLVM-ism, or did I also get that wrong?

Re: Lisp in Dart 2.0

#12

Post by cwzwarich »

patrec wrote: post #6
decafbad wrote: post #4

"Tail call optimization, which also implies tail recursion optimization" I thought those were exactly same thing.

In a language with guranteed tail call optimization, the below consumes no stack, although there's no recursion. def f(a): return g(2*a) def g(a): return a + 1

How does your definition distinguish between stack space used for call frames and stack space used for storage of temporaries? It's not possible to capture the difference without an asymptotic property, which wouldn't matter in this case because there's a constant number of function calls.

Re: Lisp in Dart 2.0

#13

Post by mehrdadn »

ikfmpwdsoz wrote: post #11
uryga wrote: post #9

Earlier quoted context omitted.

You can also optimize non-recursive tail calls: def add10(y: int) -> int: return y+10 def def add11(x: int) -> int: # won't get optimized return add10(x)+1 def add11_tail(x: int) -> int: # should get optimized return add10(x+1) in `add11_tail` the call to `add10` is in the tail position, i.e. you can "forget" about `add11_tail`'s stack frame since it's not needed anymore. It's still needed in `add10`, because you sta…

I was under the assumption that that was called sibling call optimization, and TCO referred exclusively to recursive calls. Was that just an LLVM-ism, or did I also get that wrong?

Nope, if that's what LLVM says then they're wrong here. Tail call optimization has nothing inherently to do with recursion. Rather, "tail call" means that the call is the last (tail) thing the caller does. "Sibling call" doesn't really make a lot of sense to me either, since most calls are sibling calls, and most of them can't be optimized away like that.

For reference, back in 2001, Microsoft's .NET CIL specs already had [1] a "tail call" prefix, described as follows:

> Tail call prefix [indicates] that a method should relinquish its stack frame before executing a method call.

(LLVM's first release was in 2003.)

[1] https://www.ecma-international.org/publications/files/ECMA-S...

Re: Lisp in Dart 2.0

#14

Post by cwzwarich »

decafbad wrote: post #4

"Tail call optimization, which also implies tail recursion optimization" I thought those were exactly same thing.

There are three distinct concepts that are often conflated:

1) The syntactic construct of a tail call.

2) Abstract space efficiency properties that guarantee asymptotic space usage of programs using tail calls.

3) The implementation techniques used to guarantee 2).

Even though the implementation techniques of 3) apply to all calls, the space efficiency properties in 2) are asymptotic and thus are only meaningful when applied to programs with unbounded recursive function invocations. Applying the techniques of 3) only to function calls that might potentially be involved in a recursive chain would still satisfy any of the standard definitions of 2).

See Will Clinger's paper Proper Tail Recursion and Space Efficiency (https://dl.acm.org/citation.cfm?id=277719) for details regarding the standard definition of "proper tail recursion" used in the Scheme spec and elsewhere.

Re: Lisp in Dart 2.0

#15

Post by codebje »

cwzwarich wrote: post #12
patrec wrote: post #6

Earlier quoted context omitted.

In a language with guranteed tail call optimization, the below consumes no stack, although there's no recursion. def f(a): return g(2*a) def g(a): return a + 1

How does your definition distinguish between stack space used for call frames and stack space used for storage of temporaries? It's not possible to capture the difference without an asymptotic property, which wouldn't matter in this case because there's a constant number of function calls.

There's no difference.

When you exit a function, you must clean up local stack allocations. It doesn't matter if you exit with a return or a jump. It doesn't matter where you jump. If you leave the stack with temporary allocations in place, they'll leak space.

(A compiler pipeline may, at some point, observe that releasing stack space, jumping, then claiming the same amount of stack space could be optimised to just a jump, but it may equally observe that releasing, jumping, and claiming a different amount could be optimised to either releasing or claiming the difference, then jumping, too - there's still no difference between recursive, co-recursive, and non-recursive tail calls.)

Re: Lisp in Dart 2.0

#16

Post by codebje »

patrec wrote: post #8
chc4 wrote: post #5

Earlier quoted context omitted.

Tail call optimization is returning the result of any function, with tail recursion being the specific case where it's the same function. I think I've seen some languages where they special-case recursion by doing a code transformation, but would stack overflow if you called anything else instead.

I don't think this is strictly correct. The below is (mutually) tail recursive: def even(x): return x == 0 or odd(abs(x)-1) def odd(x): return x == 1 or even(abs(x)-1)

That's co-recursion, rather than strict recursion.

It's plausible that a compiler might catch the tail recursion case but ignore non-recursive and co-recursive tail calls.

Consider:

    def even(x, useless, arguments);
        return x == 0 or odd(abs(x) - 1)

    def odd(x):
        return x == 1 or even(abs(x) - 1, 6, 9)
There are two more formal parameters to even(), which means the stack frame when calling even from odd() includes two more actual parameters.

If the compiler follows the usual stack management approach of having the caller allocate and release space for actual parameters, this means the caller has to be aware that the stack space for odd's actual parameters is larger than the size needed for its formal parameters.

If odd() is tail calling odd(), there's no difference in actual parameter space, and so the caller can be ignorant of it.

It's a minor enough difference that any compiler implementing TCO should handle it anyway (just keep track of the maximum parameter size required in a function's tail call tree, and have the caller allocate and free enough space, or have the cleanup of actual parameters performed by callee) but big enough that a toy or experimental compiler, or one in which TCO is being slowly added, might just do the simple case only.

Re: Lisp in Dart 2.0

#17

Post by dreamcompiler »

ikfmpwdsoz wrote: post #11
uryga wrote: post #9

Earlier quoted context omitted.

You can also optimize non-recursive tail calls: def add10(y: int) -> int: return y+10 def def add11(x: int) -> int: # won't get optimized return add10(x)+1 def add11_tail(x: int) -> int: # should get optimized return add10(x+1) in `add11_tail` the call to `add10` is in the tail position, i.e. you can "forget" about `add11_tail`'s stack frame since it's not needed anymore. It's still needed in `add10`, because you sta…

I was under the assumption that that was called sibling call optimization, and TCO referred exclusively to recursive calls. Was that just an LLVM-ism, or did I also get that wrong?

TCO is a bigger concept than just recursion. Applying it to non-recursive tail calls makes code more efficient because it doesn't create a superfluous stack frame. But it's harder to debug because -- it doesn't create a superfluous stack frame.

Re: Lisp in Dart 2.0

#18

Post by dreamcompiler »

cwzwarich wrote: post #12
patrec wrote: post #6

Earlier quoted context omitted.

In a language with guranteed tail call optimization, the below consumes no stack, although there's no recursion. def f(a): return g(2*a) def g(a): return a + 1

How does your definition distinguish between stack space used for call frames and stack space used for storage of temporaries? It's not possible to capture the difference without an asymptotic property, which wouldn't matter in this case because there's a constant number of function calls.

If function A tail-jumps to function B and B exits with a Return instruction (rather than another JMP) then B's Return cleans up A's stack frame automatically. It doesn't have to care that the current frame actually belongs to A rather than B.

If A has local variables, the compiler will insert an instruction to increment the SP before the final JMP, which cleans up the space for the locals.

[This requires stack frames to push local variables after pushing the return address (if any), but that's easy to arrange.]

The point is that the compiler can make the TCO decision statically just by inspecting the function in question. Dynamic analysis of who-calls- who is not necessary.

Re: Lisp in Dart 2.0

#19

Post by patrec »

codebje wrote: post #16
patrec wrote: post #8

Earlier quoted context omitted.

I don't think this is strictly correct. The below is (mutually) tail recursive: def even(x): return x == 0 or odd(abs(x)-1) def odd(x): return x == 1 or even(abs(x)-1)

That's co-recursion, rather than strict recursion. It's plausible that a compiler might catch the tail recursion case but ignore non-recursive and co-recursive tail calls. Consider: def even(x, useless, arguments); return x == 0 or odd(abs(x) - 1) def odd(x): return x == 1 or even(abs(x) - 1, 6, 9) There are two more formal parameters to even(), which means the stack frame when calling even from odd() includes two mo…

Do you have a source where co-recursion is used to describe mutual recursion as above? I'm under the impression it refers to a different concept, see e.g. https://softwareengineering.stackexchange.com/questions/1442...

Re: Lisp in Dart 2.0

#20

Post by iuoershg »

cwzwarich wrote: post #14
decafbad wrote: post #4

"Tail call optimization, which also implies tail recursion optimization" I thought those were exactly same thing.

There are three distinct concepts that are often conflated: 1) The syntactic construct of a tail call. 2) Abstract space efficiency properties that guarantee asymptotic space usage of programs using tail calls. 3) The implementation techniques used to guarantee 2). Even though the implementation techniques of 3) apply to all calls, the space efficiency properties in 2) are asymptotic and thus are only meaningful when…

If so, can a purely functional language require no more than one stack frame?
Post reply on HN