[mhitza]

> Any recursive function can be transformed into a tail recursive form, exchanging stack allocation for heap allocation.

You know, I got spoiled by Haskell, doing recursion everywhere without a care, and all I had to think was the evaluation order (when things blew up). Now that I'm doing some OCaml, I have to stop and think "am I writing a tail recursive function". It's easy to write multiple levels of recursion and lose track if you're writing a tail recursive function that the compiler will optimize.

I think recursions are really easy to make unbounded by mistake. Maybe not so much as for loops and off by ones.

[noelwelsh]

Agreed, and this is why some languages have annotations that ask the compiler to check a function is indeed tail recursive.

However I don't think that is the case in Expat. If the algorithm is tail recursive, but accidentally not expressed in that way, its a simple (but perhaps tedious to manually apply) program transform to express it in a way that does not consume unbounded memory (heap or stack). From the scant details on the fix in the article it appears the parsing algorithm itself was completely changed. ("The third variant "Parameter entities" reuses ... the same mechanism of delayed interpretation.") If this is the case the issue is not recursion, as the original parsing algorithm would consume unbounded resources no matter how it was expressed in C.

[digibeet]

Ah, I find myself in similar waters. In your experience does the [@@tailcal] annotation not cover enough of the cases?

[mhitza]

I'm aware of the tailcall annotation but I didn't have to rely on it yet. For me the benefit of picking up OCaml is that I can do imperative constructs on a first pass (mutation and for loops), and refactor it after to pure code, when needed.