**Next message:**Friedman Roy: "Y2K related changes"**Previous message:**Markus Mottl: "Re: flush file buffer, etc"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

Message-Id: <3.0.6.32.19990831215800.009603e0@mail.triode.net.au>

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

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

**Next message:**Friedman Roy: "Y2K related changes"**Previous message:**Markus Mottl: "Re: flush file buffer, etc"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

*
This archive was generated by hypermail 2b29
: Sun Jan 02 2000 - 11:58:25 MET
*