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 UAA14151 for caml-redistribution; Thu, 2 Sep 1999 20:41:03 +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 QAA13479 for <caml-list@pauillac.inria.fr>; Wed, 1 Sep 1999 16:11:16 +0200 (MET DST)
Received: from iggy.triode.net.au (iggy.triode.net.au [203.63.235.1])
	by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id QAA24810
	for <caml-list@inria.fr>; Wed, 1 Sep 1999 16:11:07 +0200 (MET DST)
Received: from egret (pm1-24.triode.net.au [203.63.235.40])
	by iggy.triode.net.au (8.9.3/8.8.8) with SMTP id AAA02656;
	Thu, 2 Sep 1999 00:08:24 +1000
Message-Id: <3.0.6.32.19990831215800.009603e0@mail.triode.net.au>
X-Sender: skaller@mail.triode.net.au (Unverified)
X-Mailer: QUALCOMM Windows Eudora Light Version 3.0.6 (32)
Date: Tue, 31 Aug 1999 21:58:00 +1000
To: mottl@miss.wu-wien.ac.at
From: John Skaller <skaller@maxtal.com.au>
Subject: factoring recursive functions
Cc: caml-list@inria.fr
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Sender: weis

In a disucssion with Markus Mottl, I said ocaml forced me to
put a large set of mutually recursive function into
a single module, and Markus said there was a way around this. 

It took me a while to figure out how to do it, and other
beginning ocaml users with procedural programming backgrounds
may find the same, so I am posting the solution here,
hoping perhaps it might find its way into the Beginners-FAQ.

The difficulty arises when procedural programmers are used
to being able to separately compile mutually recursive
functions, which are resolved by the linker; but
the ocaml linker requires a strict ordering.

Here is a reduced example problem, and solution:

(* --------------------------------------------- *)
(* mutually recursive types *)
type t1 = C1 | E1 of t2
and t2 = C2 | E2 if t1

(* mutually recursive functions *)
let rec f1 x = match x with
| C1 -> print_endline "C1"
| E1 y -> print_endline "E2"; f2 y

and f2 x = match x with
| C2 -> print_endline "C2"
| E2 y -> print_endline "E2"; f1 y

(* test data and evaluation *)
let data = E1 (E2 (E1 C2));;
f1 data;;
(* ----------------------------------------------

The solution must be symmetric,
and involve independent definitions
of f1 and f2. It took me a while to figure out:

---------------------------------------------- *)
let rec g1 g2' x = match x with
| C1 -> print_endline "C1"
| E1 y -> print_endline "E1"; g2' y

let rec g2 g1' x = match x with
| C2 -> print_endline "C2"
| E2 y -> print_endline "E2"; g1' y

let rec h1 x = g1 h2 x
and h2 x = g2 h1 x;;

h1 data;;
(* -----------------------------------------------------*)

I observe that the solution can be deduced using
'nested function lifting'. A nested function can
be lifted out of context, by augmenting
it with parameters where values from the context
are implicitly bound, then passing these explicitly
in the call, the latter syntactic annoyance
can be alleviated by defining a new function
currying these arguments, which now accepts the same
signature as the original nested function.

If I had taken the two mutually recursive functions
and replaced the bodies by a dummy function definition,
followed by a call to the dummy, I could have then
lifted the dummies out of the recursion, obtaining
the above result because the recursion parameters
would have become explicit.

Lifting is more familiar to most procedural programmers
than functional ones for the simple reason that
most procedural programming languages do not support
nested functions, so conceptually nested ones must
be lifted routinely by the programmer.

---------------------------------------------------------
QUESTIONS: how much efficiency is lost?
Is there a better technique?
Why is the 'x' required?

To what extent can the reverse transform be automated?
(Have I just implemented what the forward
reference patch does?)

-------------------------------------------------------
John Skaller    email: skaller@maxtal.com.au
		http://www.maxtal.com.au/~skaller
		phone: 61-2-96600850
		snail: 10/1 Toxteth Rd, Glebe NSW 2037, Australia