From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id KAA24183 for caml-redistribution; Wed, 15 Dec 1999 10:50:04 +0100 (MET)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id WAA04320 for <caml-list@pauillac.inria.fr>; Tue, 14 Dec 1999 22:20:26 +0100 (MET)
Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35])
	by concorde.inria.fr (8.8.7/8.8.7) with ESMTP id WAA10343;
	Tue, 14 Dec 1999 22:20:16 +0100 (MET)
Received: (from vouillon@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id WAA06925; Tue, 14 Dec 1999 22:20:15 +0100 (MET)
Message-ID: <19991214222015.46916@pauillac.inria.fr>
Date: Tue, 14 Dec 1999 22:20:15 +0100
From: Jerome Vouillon <Jerome.Vouillon@inria.fr>
To: Norman Ramsey <nr@eecs.harvard.edu>, caml-list@inria.fr
Cc: nr@labrador.eecs.harvard.edu
Subject: Re: OCaml and tail recursion
References: <199912131727.MAA20344@labrador.eecs.harvard.edu>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
X-Mailer: Mutt 0.89.1
In-Reply-To: <199912131727.MAA20344@labrador.eecs.harvard.edu>; from Norman Ramsey on Mon, Dec 13, 1999 at 12:27:37PM -0500
Sender: weis


Hello,

> I have just completed my first nontrival Caml program (an implementation
> of the rsync algorithm) and I am distressed about the treatment of
> tail calls.  My code has to go through files one character at a time,
> and as an SML programmer from way back, I wrote the code using three
> mutually recursive functions that make tail calls to each other.
> Imagine my surprise when I started getting errors with stack overflow!
> Apparently ocamlc doesn't optimize tail calls.

[Benjamin Pierce sent me your code]

You have written some functions such as this one:
  let string s = 
    let rec next k sum =
      try next (k+1) (append sum (String.get s k))
      with Invalid_argument _ -> sum in
    next 0 0
This function is not tail-recursive.  Indeed, an exception handler
need to be pushed on the stack at each invocation of the function
"next" and must remain until the recursive call terminates. It may be
possible here to only keep the last handler on the stack, but this
optimization cannot be done in the general case.

By the way, this kind of function does not use constant space under
SML/NJ either: the following function will happily eat all available
memory:
   fun f x = f x handle _ => 1;

-- Jérôme