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

[brogoff@speakeasy.net]

On Fri, 31 Jan 2003, Russ Ross wrote:
> 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.

For the particular case being discussed, there is a bit of theory, and if you 
read Minamide's paper you'll see that he comments that six functions from 
the SML Basis can take advantage of the hole abstraction to be written in 
tail recursive form: append, take, map, mapPartial, filter, and tabulate. 

For OCaml's list, we I think it's pretty clear that fold_right can't be written 
this way, since it doesn't necessarily construct lists. I think it's also clear 
that we can write map2, flatten, split, and combine with setcdr (I like 
replace_tl as a name for this :) in tail recursive form, since map2, split, and 
combine are all tweaks of map, likewise flatten is a tweak of append. I just 
hacked up tail recursive versions of all of these functions (including the 
SML ones Minamide mentioned) using setcdr, so it is doable.  

PS: As you may know, you can certainly make functions like fold_right 
tail recursive using a trick called the CPS transformation, like so, from 

let rec fold_right f l accu =
  match l with
      [] -> accu
    | a::l -> f a (fold_right f l accu)

to

let rec fold_rightk f l accu k = 
  match l with 
      [] -> k accu 
    | a::l -> fold_rightk f l accu (fun x -> k (f a x))

let fold_right f l accu = fold_rightk f l accu (fun x -> x)

but as you can see that doesn't help so much, because we create lots of 
closures. So just making things tail recursive isn't really enough, since we 
can make anything tail recursive. This hole abstraction stuff Minamide discusses 
is a bit more, and touches on such areas as linear types. I think "destination 
passing style" will give you a few good hits on Google, if you're looking for 
more refs, but the Minamide paper cited earlier is a good start.

-- 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