How important is the @tailcall extension in a language(a language like OCaml) which supports looping constructs and mutable data?
Note: I can see its importance(tail call optimization) in languages like Haskell and Elm which don’t don’t support looping constructs and mutable data but what benefit is gained in OCaml?
Tailcall optimization is not an extension but a core feature of OCaml. The [@tailcall] annotation merely checks explicitly that a call can be optimized.
Like many other features, it is a question of expressivity: tailcall optimization makes it possible to write some functions in a natural and efficient way. In fact, there is some ongoing work on tail recursion modulo cons optimizations that allows to write even more function in this style.
But isn’t the truth that recursive functions just provide an accumulator via the stack and that accumulator can exist inside a looping construct too.
I have yet to reach that point in functional programming where recursive functions (written in a tailcall optimized way) feels natural. If anything, it feels contrived.
What feels “natural” is a very subjective matter, and has everything to do with what you’re most used to and comfortable with. I am guessing you’re very familiar with imperative programming, but new to functional programming. So of course, loops would feel more “natural” to you.
Learning new abstractions always feels awkward at first. I would encourage you to not make a judgement before you’re as comfortable with functional programming as with imperative programming. Try to keep an open mind.
By the way, here is an famous related article: http://paulgraham.com/avg.html
FWIW I personally don’t consider writing a tail recursive function in any way natural. For example when I have a complex recursive function to write I usually first write it in a non-tail recursive fashion to make sure I get it right and then proceed to make it tail-recursive.
Once you have realized that the latter process is mostly about trading stack space for heap space via an accumulator it’s mostly outomatic. But I still feel like a monkey each time I’m doing this, especially given the latter insight.
Programming with recursion instead of iteration is actually liberating and clarifying: could I recommend that you check out Peter Henderson’s Functional Programming ? Or maybe The Little MLer ?
@G4143 I just want to make it clear that it’s a tail recursive function that I find unnatural (I suspect @octachron thinks likewise he just had an unfortunate sentence structure).
I do find solving problems using recursive functions rather than looping constructs and mutable data not only natural but also clarifying.
Except for array/signal processing I rarely use looping constructs myself.
@ dbuenzli
I’m not uncomfortable with recursion but I find it odd that all this energy is applied to structuring recursive functions so that they will reduce to a loop.
I also agree that the natural solution for recursive data structures is recursive functions, especially when you have pattern matching/type deconstruction at your disposal.
My phrasing was indeed unfortunate. To be more explicit, I find recursive functions often more natural to write than while loops (outside of function on multidimensional arrays). Tail recursive optimization makes a handful of those functions efficient at no readability cost. Outside of this happy path, I agree that manually tracking the data in the stack to transform a recursive function into a tail recursive function does not feel natural at all. In fact, it feels more like doing half (or more) of the work needed to transform a recursive function into a while loop, while I would prefer to do none of this work.
I remember when I was learning Scheme, back in college (1986, sigh, so old). And this was after having learned C, Pascal, some C++, Mocklisp, maybe some other languages. And one of the big ideas in Scheme, was that you -coded- iteration as recursion. That is, recursion was the primitive thing, and iteration was expressed -via- recursion. And it was explained that this (a) meant one fewer idea to carry around, and (b) you could apply all the same reasoning tools you used for recursion (and function-calls generally) to iteration (expressed as recursion).
This is a matter of taste, for sure. But after many years, I find that this is true. In writing ocaml, I almost -never- reach for the for-loop or while-loop: it’s almost always clearer to write a tail-recursion.
I hope it’s clear from the above, that it’s not merely the ML-family of languages that eschews iteration in favor of recursion: ML got this from Scheme, and it was and remains (I’m guessing) an article of faith in that community to this day.
OK. Some more-concrete reasons for favoring tail-calls over iteration:
(1) it becomes completely clear where and how your loop-variables are updated, rather than having your loop-variables updated bit-by-bit during the loop-body, and your having to keep track of which expressions use new values, and which use old values.
(2) if you believe in functional programming, then you believe that imperative updates should be avoided unless absolutely necessary [cf. the FP Koan about DDR grin] and this is a way of avoiding such imperative update
(3) for those cases where the tail-recursion is really an induction down some well-founded order, it’s easier to make plain what the order is that one is traversing. [ok, this one is weak]