Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0001538OCamlOCaml generalpublic2003-02-09 07:162003-02-11 14:02
Reporteradministrator 
Assigned To 
PrioritynormalSeverityfeatureReproducibilityalways
StatusacknowledgedResolutionopen 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version 
Summary0001538: feature wish: tail recursion modulo cons
DescriptionFull_Name: Brian Rogoff
Version:
OS:
Submission from: 12-234-80-157.client.attbi.com (12.234.80.157)


Hi,
    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 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 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. 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 ;-)

-- Brian

TagsNo tags attached.
Attached Files

- Relationships

-  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


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker