Hacker News Reader

Comment by jacquesm | Hacker News Reader

In FP loops are typically frowned upon and then the tail call is presented as an elegant solution, because it can be optimized into a loop but still look like a function call with all the goodies a function call normally gives you, minus the new stack frame.

I'm really not convinced of this, it looks like a function call but it is a loop. If it is a loop under the hood then I'd like to see that loop, in my mind I always see this 'stackoverflow' neon sign hover over every tail call (of course it doesn't but years of debugging stuff have ingrained all kinds of interesting detection habits).

Making it look like a loop would introduce all kinds of syntactical complexity, and suddenly you'd be re-using your local variables. So that's not a solution either. But it feels a bit like a kludge.

View on HN

It looks like a function call and it is a function call. There's nothing about a function call that requires pushing a stack frame ... as the existence of TCO demonstrates.

I'd argue that's the wrong interpretation. Function-calls absolutely require pushing a stack-frame, and TCO is no exception. TCO just says "Oh hey, we're done with the current stack-frame, let's toss it out before we call the next function". That's why TCO can apply to function-calls which aren't recursive. The recursive case still follows this rule, it's just the old and new stack-frames are identical. The compiler makes another optimization of not bothering to remove the stack-frame and just reuses it for the next call (Since it's going to be the same size anyway). Even noting that, there are still some cases where this also doesn't apply, because if (in C) you use VLA's at the beginning which depend on a supplied argument, then even with TCO, you still have to remove and create a new stack-frame every call.

I suggest you read "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO": <http://library.readscheme.org/page1.html>, in particular section C.

I'm not so sure that in FP communities recursive call based algorithms are thought of as elegant solution; rather higher abstractions are desirable (e.g. map, filter, fold, etc)

It's considered elegant because that way you only need functions, no other constructs required.

How do you implement map without tco or loops?(I'm not saying this is impossible just that I can't think of a way to do it of the top of my head)

Sure, it's all gotos at the machine level. There's nothing wrong with implementing map that way. The point is to use a higher-level, less free-form control structure when it matches the problem, because it gives the reader more information.

Basically you want to always use the least powerful tool you can to solve a problem. When applicable, map is better than foldl not because it's more concise, but because it tells the reader that the result is a list of the same length of the input, and the elements of the input are processed independently. Similarly, foldl is better than raw recursion because it tells the reader that every element in the input list is being processed in order, rather than potentially anything happening.

There's nothing wrong with using the more powerful tools when you need them (such as when implementing the more restricted tools). It's just that needing them frequently is a sign that you're doing weird things and should take a second look at your design to make sure there isn't a better way to do things.

If you look at it from the perspective of continuations then tail calls are very natural. A function call is always a goto, the only difference is that calls in tail position do not need to add extra data to the continuation.

Of course! But that still doesn't mean you should use them most of the time. Continuations are great for writing compilers but confusing to use elsewhere. Just like you don't normally write assembly (but it's necessary sometimes), you shouldn't normally use these exceptionally flexible but unstructured abstractions in a program you want other people to read.

Instead you want to use constructs that are familiar and easy to reason about. It's hard to beat a for loop.

By continuations I believe Jules means Continuation-passing style, a popular optimization/intermediate format in compilers:

http://en.wikipedia.org/wiki/Continuation-passing_style

Sure, whether you should use them is a software engineering question. I was merely speaking to their theoretical elegance, pointing out that from a continuation perspective tail call optimization isn't really an optimization, it's just the most natural way to implement procedure calls to begin with.

Reply on news.ycombinator.com