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 UAA01312 for caml-red; Thu, 26 Oct 2000 20:41:31 +0200 (MET DST)
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA02041 for <caml-list@pauillac.inria.fr>; Thu, 26 Oct 2000 19:21:17 +0200 (MET DST)
Received: from isil.localdomain (exodus-rtr-2.arsdigita.com [216.34.106.252])
	by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id e9QHLGv04280
	for <caml-list@inria.fr>; Thu, 26 Oct 2000 19:21:17 +0200 (MET DST)
Received: by isil.localdomain (Postfix, from userid 1000)
	id 757433696D; Thu, 26 Oct 2000 13:24:29 -0400 (EDT)
To: datta@math.berkeley.edu
Cc: caml-list@inria.fr
Subject: Re: Why Not Tail-Recursive?
References: <20001025235738.A7286@blue1.berkeley.edu>
From: John Prevost <jmp@arsdigita.com>
Date: 26 Oct 2000 13:24:29 -0400
In-Reply-To: <20001025235738.A7286@blue1.berkeley.edu>
Message-ID: <87r953ms6q.fsf@localhost.localdomain.>
User-Agent: Gnus/5.0808 (Gnus v5.8.8) Emacs/20.7
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Sender: weis@pauillac.inria.fr

>>>>> "rd" == Ruchira Datta <datta@math.berkeley.edu> writes:

    rd> I am interested in the following problem: given a set of
    rd> elements with weights, enumerate all subsets with a given
    rd> total weight.  I wrote the function
    rd> find_subsets_of_total_weight to do this in OCaml.  It works
    rd> exactly as I expect on small inputs.  But on larger (not
    rd> extremely large) inputs, I get a stack overflow.

    rd> The function deepen within find_subsets_of_total_weight
    rd> originally had an accumulating parameter subsets, but I took
    rd> that out in favor of printing out each subset as it was found,
    rd> in case that was what was causing the stack to overflow.
    rd> Unfortunately it wasn't.  I have inserted and deleted print
    rd> statements at numerous places, and in every case the function
    rd> is doing as I expect right up until the stack overflows, or at
    rd> least so it seems to me.

    rd> The only thing I can think of is that the functions deepen and
    rd> next_path are not actually tail-recursive as I expected them
    rd> to be.  But why not?

    rd> I have appended here the file weights.ml, which includes test
    rd> data leading to a stack overflow on my OCaml system.  (Bonus
    rd> points if you can guess where the test data came from.)  Any
    rd> help anyone can give me with this problem would be greatly
    rd> appreciated.  Thanks in advance.

------------------------------weights.ml------------------------------
  ...
  let rec deepen ( elts_so_far, wgt_so_far, undecided_elts ) =
>>> try (
      match undecided_elts with
      | [] -> 
        let new_path = next_path ( elts_so_far, wgt_so_far, undecided_elts ) 
        in deepen new_path
      | elt :: elts ->
        let new_wgt = wgt_so_far +. wgt_fn elt in
        if new_wgt < desired_wgt then
          deepen ( ( ( elt, true ) :: elts_so_far ), new_wgt, elts )
        else if new_wgt = desired_wgt then
          let _ = print_fn ( ( elt, true ) :: elts_so_far ) in
          deepen ( ( ( elt, false ) :: elts_so_far ), wgt_so_far, elts )
        else (* new_wgt > desired_wgt *)
          let new_path = next_path ( elts_so_far, wgt_so_far, undecided_elts ) 
          in deepen new_path
>>> ) with Done -> ()
  in deepen ( [], 0., elts_sorted_by_wgt )
------------------------------------------------------------------------

Your problem is marked with >>> above.  try ... match ... around the
tail recursive call makes your call not be tail recursive.  Try
wrapping the use of deepen instead:

  in try deepen ( [], 0., elts_sorted_by_wgt) with Done -> ()

John.