0001538: feature wish: tail recursion modulo cons

Notes
(0000144) administrator (administrator) 2003-02-13 15:42	Brian, > As has been discussed on the mailing list, I wish that OCaml > would perform the tail recursion optimization on a larger class of > functions than it does currently. One example is List.map. Several > times I've had customers run programs on some fairly large data and > had the stack blown. One could argue that one shouldn't use lists > for such programs, but that's silly. Lists are a fundamental data > structure in FPLs, like floating point arrays in Fortran, so we > really should maximize their power. I have mixed feelings about this. Yes, lists are often used and a stack overflow is never pleasant. But I feel that lists are often over-used by functional programmers: FP is no excuse for inadequate data structures. Even if the stack consumption can be avoided by tail recursion or setcdr, the time complexity of the list-based program remains higher than what it could be with better data structures... > I can usually make such functions tail recursive at a > significant cost in performace by doing everything backwards and > reversing the result. That's the usual approach I take, but now that > I know that there is a better way, it seems wasteful. It is. My reaction in this situation is to try to come up with better data types, e.g. balanced trees rather than lists. > It turns out that the problem can be fixed by adding a > "set-cdr!" procedure coded using Obj functions, and a similar > approach will work for the same problem with other data structures, > like trees. I've added a module of List functions recoded using this > approach to my library. I'm not opposed to recoding some of the List functions with setcdr, provided execution speed doesn't suffer too much for small lists. Due to the generational and incremental nature of the OCaml GC, in-place modifications entail significant hidden costs. I'd rather not expose setcdr to the programmers, though. It would invalidate important optimizations such as compile-time construction of constant lists, and more generally makes formal reasoning about list-based programs impossible. > However, I dislike this for the same reason I dislike the previous > approach; it appears that there are a few solutions for ML style > languages. Caml should have one. I wouldn't mind it if the compiler > could detect this in the special case of lists and optimize it, > since that's where I get bit currently, but a type system extension > like Minamide's or the Walker/Morrisett alias types would allow this > for arbitrary data structures. Yes, it's more than just doing tail > call optimization, it requires a type system extension, and the > functions would need to be coded differently. But you guys are > language researchers, so it would probably be a lot of fun, and > worth a few papers. Just adding set-cdr! or special casing List.map > and friends isn't really research ;-) Agreed. But I'm very reluctant to complicate the type system by reflecting optimization information (as in Minamide or Walker's systems) inside types. Rich types are good if they enrich the expressive power of the source language, allowing more precise / more reusable types for functions; but there is something unpleasant in reflecting too much of the operational behavior of functions in their types. In other terms, there are ideas that make nice research papers, and then there are ideas worth implementing in an actual compiler :-) Non-type-based optimizations of tail recursion modulo constructors exist -- it was a hot topic in the Lisp community in the 80's -- but I'm not up to date on them; I would have to do some research at the library to see what would be worth implementing. Thanks for your feedback, - Xavier Leroy

Issue History
Date Modified	Username	Field	Change
2005-11-18 10:13	administrator	New Issue

Relationships