From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 50154BCAE for ; Wed, 13 Jul 2005 21:02:56 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j6DJ2til014415 for ; Wed, 13 Jul 2005 21:02:56 +0200 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 VAA23070 for ; Wed, 13 Jul 2005 21:02:55 +0200 (MET DST) Received: from mailx.valdosta.edu (mailx.valdosta.edu [168.18.130.251]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j6DJ2sdu005113 for ; Wed, 13 Jul 2005 21:02:55 +0200 Received: from blazemail.valdosta.edu (valdosta.edu [168.18.130.208]) by mailx.valdosta.edu (8.13.4/8.13.4) with ESMTP id j6DJ2riQ026403 for ; Wed, 13 Jul 2005 15:02:53 -0400 (EDT) (envelope-from jtbryant@valdosta.edu) Received: from starlight.valdosta.edu (starlight.valdosta.edu [168.18.148.146]) by blazemail.valdosta.edu (iPlanet Messaging Server 5.2 HotFix 2.04 (built Feb 8 2005)) with ESMTP id <0IJK0090RY8T03@blazemail.valdosta.edu> for caml-list@inria.fr; Wed, 13 Jul 2005 15:02:53 -0400 (EDT) Date: Wed, 13 Jul 2005 15:03:45 -0400 From: Jonathan Bryant Subject: Mututal Recursion and Tail Recursion To: caml-list@inria.fr Reply-To: jtbryant@valdosta.edu Message-id: <1121281425.30107.36.camel@starlight.valdosta.edu> Organization: Valdosta State University Information Technology (System Operations) MIME-version: 1.0 X-Mailer: Evolution 2.0.2 (2.0.2-16) Content-type: multipart/mixed; boundary="Boundary_(ID_dQFHwh0l2WLvpunnLSxzSQ)" X-PMX-Version: 5.0.1.144180, Antispam-Engine: 2.0.3.2, Antispam-Data: 2005.7.13.21 X-Miltered: at concorde with ID 42D5655F.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 42D5655E.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; recursion:01 recursion:01 recursive:01 recursive:01 flatten:01 stack:01 tailcall:01 mistaken:01 compiler:01 rec:01 printf:01 printf:01 rec:01 flatten:01 stdout:01 X-Attachments: cset="UTF-8" name="list_aux.ml" name="list_aux.ml" X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: --Boundary_(ID_dQFHwh0l2WLvpunnLSxzSQ) Content-type: text/plain Content-transfer-encoding: 7BIT Is is possible to have mutually recursive functions that are also tail recursive? For example, attached is some code I wrote to flatten a list of lists using mutually recursive functions. I've tried this with large lists (5,000,000+) and have not encountered a stack overflow, but that does not necessarily mean that tail recursion is happening. Also, I know that there are ZAM opcodes that indicate a tail recursive function (TAILCALL, if I am not mistaken) and one or two of the undocumented compiler options will dump the opcodes. Could someone briefly explain what each of those options do so I wouldn't have to take up everybody's time asking if this is tail recursive? --Jonathan -- *=========================* |Jonathan Bryant | |Valdosta State University| |Information Technology | |System Operations | |-------------------------| |jtbryant@valdosta.edu | |x6358 | *=========================* --Boundary_(ID_dQFHwh0l2WLvpunnLSxzSQ) Content-type: text/plain; name=list_aux.ml; charset=UTF-8 Content-transfer-encoding: 7BIT Content-disposition: attachment; filename=list_aux.ml let print l = let rec aux l1 = match l1 with [] -> Printf.printf "[]"; | h::[] -> Printf.printf "%d]" h | h::t -> Printf.printf "%d; " h; aux t in Printf.printf "["; aux l;; let print_ll ll = let rec aux l1 = match l1 with [] -> Printf.printf "[]"; | h::[] -> print h; Printf.printf "]" | h::t -> print h; Printf.printf "; "; aux t in Printf.printf "["; aux ll;; let flatten ll = let rec flat_out ol oa = match ol with [] -> oa | h::t -> flat_in h t oa and flat_in il ot ia = match il with [] -> flat_out ot ia | h::t -> flat_in t ot (h::ia) in List.rev (flat_out ll []);; let interpolate l1 l2 = let rec inter x y a = match x,y with [],[] -> a | [],h::t -> inter t x (h::a) | h::t,[] -> inter t y (h::a) | h1::t1,h2::t2 -> inter y t1 (h1::a) in List.rev (inter l1 l2 []);; let range x m s = let rec aux c a = if c > m then a else aux (c + s) (c :: a) in List.rev (aux x []);; let range_ll min max step division = let l = range min max step in let rec aux1 l1 a1 = match l1 with [] -> (List.rev a1) | h::t -> aux2 l1 0 [] a1 and aux2 l2 len a2 a1 = if len < division then match l2 with [] -> aux2 [] division a2 a1 | h::t -> aux2 t (len + 1) (h::a2) a1 else aux1 l2 ((List.rev a2)::a1) in aux1 l [];; let _ = let min = 1 and max = 5000000 in Printf.printf "Generating lists"; flush stdout; Printf.printf "."; flush stdout; let my_list = range min max 2 in Printf.printf "."; flush stdout; let my_other_list = range (min + 1) max 2 in Printf.printf "."; flush stdout; let my_list_list = range_ll min max 1 1 in Printf.printf "\n"; flush stdout; Printf.printf "\nMy List: "; flush stdout; (* print my_list; *) Printf.printf "\nMy Other List: "; flush stdout; (* print my_other_list; *) Printf.printf "\nMy List and My Other List Interpolated: "; flush stdout; (* print (interpolate my_list my_other_list); *) Printf.printf "\nMy List List: "; flush stdout; (* print_ll my_list_list; *) Printf.printf "\nMy List List Flattened: "; flush stdout; (* print (flatten my_list_list); *) Printf.printf "\n\n"; flush stdout; if (interpolate my_list my_other_list) = (flatten my_list_list) then ( Printf.printf "The interpolated and flattened lists are equal!\n"; flush stdout ) else ( Printf.printf "Hmmm...\n"; flush stdout );; --Boundary_(ID_dQFHwh0l2WLvpunnLSxzSQ)--