Re: [Caml-list] @, List.append, and tail recursion

[Russ Ross <caml@russross.com>]

I'd just like to agree with Brian on this.  We seem to have a split
in this thread and the two branches should be addressed separately:

1. Help with the specific case being mentioned.  I think this has
been addressed nicely with several helpful suggestions.

2. Discussions about solving this class of problems.

Practical workarounds are an essential part of writing software, but
eliminating the need for them is where the computer science comes
into play.  I was reading Paul Graham's "On Lisp" the other day and
came across an example that made me cringe.  He pointed to a simple
Lisp code fragment and then rewrote it for performance, proudly
pointing to the result as an example of what efficient Common Lisp
looks like and claiming that the result is competitive with C for
speed.

That's great that the capability is there, but whenever there is a
significant difference between the clean, simple way to do something
and the efficient way to do it (where the primary different is
language or compiler related, not a fundamental algorithm or data
structure change) it indicates an opportunity to improve the
language or compiler design.  If a systematic rewrite can transform
inefficient code into efficient code, why doesn't the language
and/or compiler just do it for you or prevent the problem in the
first place?  (the answers "because it is hard to do" and "I don't
see you doing it" are both equally valid, but let's consider the
question rhetorical for now)

In Graham's example (if I recall correctly) the solution involved
annotating variable types (Lisp is dynamically typed) and
transforming a recursive function to use an accumulator to allow
tail recursion.  Lisp is full of this pattern and it does make a big
different in performance.  ML is statically typed so one could argue
that it fixes the first problem already (annotating the types
effectively removes dynamic typing from the Lisp function) but the
second is still there.

Tail recursion is a powerful and efficient construct, but it still
requires care on the part of the programmer to make sure that the
calls are proper tail calls.  I think there are many recursive
functions which cannot be transformed easily into tail calls, but
there is a large class of functions that can be mechanically
transformed using techniques discussed here and elsewhere.  I would
be interested personally if anyone could point to papers or other
resources about this topic.  Right now I think there is some
low-hanging fruit to be plucked--recognizing and transforming a few
simple patterns (code that looks like List.map) would make a big
difference in a lot of code.  Handling more complex cases is
undoubtedly harder, but I think the potential benefits are
considerable.

I appreciate everyone's input on this subject so far.  I was
attracted to Caml in the first place because it seemed to be one of
the best examples of a language where writing code that is clean and
natural coincides with writing code that is efficient.  I hope that
discussions like this can bridge the gap even more.

- Russ

p.s. I don't mean to sound critical of Paul Graham here--in the
context of Common Lisp his examples were very valuable--he just
nicely illustrated my point for me so I picked on him.


On Fri, Jan 31, 2003 at 11:13:26AM -0600, Brian Hurt wrote:
> I did get it the first time.  I'm just using List.append to illustrate a 
> problem I'm having.
> 
> The problem is *constructing* lists.  If you can construct your list 
> backwards, fine- but if you can't, you end up either not being tail 
> recursive (and blowing up for long lists) or allocating the list twice.
<snip>
> Now minor uglification becomes major uglification.  It'd be nicer just to 
> be able to be able to construct lists forwards instead of backwards.
> 
> List.append is just an obvious example to be talking about, but the 
> problem is signifigantly more general.
> 
> Brian
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners