Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

feature wish: tail recursion modulo cons #8010

Closed
vicuna opened this issue Feb 9, 2003 · 2 comments
Closed

feature wish: tail recursion modulo cons #8010

vicuna opened this issue Feb 9, 2003 · 2 comments

Comments

@vicuna
Copy link

vicuna commented Feb 9, 2003

Original bug ID: 1538
Reporter: administrator
Status: closed (set by @mshinwell on 2016-12-06T20:43:06Z)
Resolution: not a bug
Priority: normal
Severity: feature
Category: ~DO NOT USE (was: OCaml general)

Bug description

Full_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

@vicuna
Copy link
Author

vicuna commented Feb 13, 2003

Comment author: administrator

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

@vicuna
Copy link
Author

vicuna commented Dec 6, 2016

Comment author: @mshinwell

I think this issue is superfluous. Frederic Bour has a TRMC implementation that may be discussed further.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant