Tail Recursion on Map, Append, etc.

Tail Recursion on Map, Append, etc.

[Tyson Whitehead]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I was wondering about the status of map and friends with regard to tail
recursion.  There was a big discussion back in 2003 about specific solutions 
(implementation of the those functions using Obj) and more general compiler 
support for holes/destination passing.  It started with the following 
message:

http://caml.inria.fr/pub/ml-archives/caml-list/2003/01/4a9754e53ff07723caf21b4496d1d267.en.html

It sounded to me like the general consensus was to immediately implement the 
specific tail recursive versions of these functions for List and friends 
(which were provided in the discusion), and then improve the compiler by 
adding support for advanced hole/destination passing solutions.

Looking at the list implementation in the OCaml Debian unstable source, it 
doesn't look like the more efficient version has been implemented.  Further, 
looking at the assembler emitted for the code it doesn't look like the 
compiler supports holes/destination passing either.

January 2003 was quite a while ago, anybody know what's up here?

Thanks!  -T

- --
 Tyson Whitehead  (-twhitehe at uwo.ca -- WSC-)
 Computer Engineer                        Dept. of Applied Mathematics,
 Graduate Student- Applied Mathematics    University of Western Ontario,
 GnuPG Key ID# 0x8A2AB5D8                 London, Ontario, Canada
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)

iD8DBQFCOFldRXbLmIoqtdgRArjXAKDX1ntabSketcJX37uy/GnjMBXclACgnl7i
D2JY8tHbtwrY6/HtErXpy5c=
=X6rG
-----END PGP SIGNATURE-----

Re: [Caml-list] Tail Recursion on Map, Append, etc.

[Richard Jones]

On Wed, Mar 16, 2005 at 11:05:45AM -0500, Tyson Whitehead wrote:
> I was wondering about the status of map and friends with regard to tail
> recursion.

The extlib implementations are supposedly all tail-recursive.

http://cvs.sourceforge.net/viewcvs.py/ocaml-lib/extlib-dev/extList.mli?rev=1.18&view=markup

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Caml-list] Tail Recursion on Map, Append, etc.

[Jacques Garrigue]

From: Tyson Whitehead <twhitehe@uwo.ca>

> I was wondering about the status of map and friends with regard to tail
> recursion.  There was a big discussion back in 2003 about specific solutions 
> (implementation of the those functions using Obj) and more general compiler 
> support for holes/destination passing.  It started with the following 
> message:
> 
> http://caml.inria.fr/pub/ml-archives/caml-list/2003/01/4a9754e53ff07723caf21b4496d1d267.en.html
> 
> It sounded to me like the general consensus was to immediately implement the 
> specific tail recursive versions of these functions for List and friends 
> (which were provided in the discusion), and then improve the compiler by 
> adding support for advanced hole/destination passing solutions.

The result of this consensus is the extlib library. It provides those
tail-recursive functions.
               http://ocaml-lib.sourceforge.net/
There is no project to include specific support in the compiler, but
the extlib implementation shows that this is not required if a bit of
magic is permitted.

Note that this list is not the core developers list, so the result of
discussions here does not imply anything on the ocaml distribution
itself.

> Looking at the list implementation in the OCaml Debian unstable source, it 
> doesn't look like the more efficient version has been implemented.  Further, 
> looking at the assembler emitted for the code it doesn't look like the 
> compiler supports holes/destination passing either.

To correct a misunderstanding: tail-recursive versions are not
necessarily more efficient (at least on short lists; short meaning
less than 10000 elements), but they are safer.
Non tail-recursive functions are carefully marked in the list module,
and alternative functions are included.
For instance:
  let safe_map f l = List.rev (List.rev_map f l)
  let safe_append l1 l2 = List.rev_append (List.rev l1) l2
provide you with tail recursive versions of map and append.
In practice they perform relatively well, if you don't want to
download extlib.

Jacques Garrigue

Re: [Caml-list] Tail Recursion on Map, Append, etc.

[Christophe Raffalli]

[-- Attachment #1: Type: text/plain, Size: 938 bytes --]


A small remark:

on map, the rev_map function composed with rev (which are purely
function and tail-rec) may be often faster than a tail recursive version
of map on large list, especially if each function call
from map does some allocation, because the tail recursive version of map
does assignments and this cost a lot for the GC ...

I did some testing, and the timings where similar for both solution ...
which is not what I expected.

-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]