factoring recursive functions
 John Skaller
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  John Skaller <skaller@m...> 
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 BeginnersFAQ. 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: 61296600850 snail: 10/1 Toxteth Rd, Glebe NSW 2037, Australia