🚀 go-pugleaf

Open Reply to:

| >From: nelan@enuxha.eas.asu.edu (George Nelan)
| Newsgroups: comp.lang.functional
| Subject: Open Letter To Chin About HO=>FO
| Date: 7 May 90 18:20:13 GMT
| Organization: Arizona State Univ, Tempe
| 
|      :
| My algorithm fails for this! (however, it appears that it would be feasible
| to modify the alg. to account for this special case).  This begs the question:
| where in the heck do these special cases come from anyway?  Chin, how long did
| it take you to find all these cases? :-)

It took quite some time. The 'variable/constant-only' parameter criterion was
discovered (or re-discovered?) while I was working on an extension to
Wadler's deforestation algorithm. I find that this criterion is extremely
suitable for the specialisation of 'symbolic' rather than just 'grounded/known'
arguments (which have been the pre-dominant concern of Partial Evaluation
techniques).

|        :
| by what I call "weakening".  I think that further research of that function
| needs to be done: this *may* yield a single general algorithm that can handle 
| all of the special cases you brought up. One of the big questions I have is:
| how can one be sure all the special cases are covered?

There is a large class of recursive functions with 
accumulating parameter arguments, similar to the 'acc_map' example, 
which will provide you with *plenty* of special cases
for extending the ho-removal transformations! These would most likely have to
rely on more sophisticated (and corresponding harder but not impossible
to automate) techniques (needing laws/lemmas), like those illustrated 
in [Wand80].

| Finally Chin, I hardly think it would be fair to stop now without adding
| some more fuel to the fire :-)
|
| I have a question: how do your algorithms deal with indirect mutual recursion?
| For example (under my transformation alg.):
|
|	p where p = (f h 3)
|		(f g x) = (IF (EQ x 0) 1 {x * (g {x - 1})})
|		(h x) = (f h x)
|    =>
|	p where p = (f_1 3)
|		(h x) = (f_2 x)
|		(f_1 x) = (IF (EQ x 0) 1 {x * (h {x - 1})})
|		(f_2 x) = (IF (EQ x 0) 1 {x * (h {x - 1})})
	
The above example can be handled in a straightforward way
by my ho-removal transformation algorithms. I haven't mentioned this
previously, but the way to apply the transformation is 
use a bottom-up transformation strategy ([Feather79] used this
strategy very successfully for his semi-automatic transformations).
The principal idea behind bottom-up transformation strategy is to transform
functions which are 'lower' in the defining hierarchy before those above them.
(Mutually recursive functions are considered to be at the same level).

In the above example, the three functions, 'p', 'f' and 'h' are in 
the following hierachy 'p' > 'h' > 'f'. Applying the transformation
algorithms to the three functions would result in the following:
	
	f g x   = (IF (EQ x 0) 1 {x * (g {x - 1})})  (* no changes to this *)

	h x 	= f h x   			(* unfold f h x*)
		= IF (EQ x 0) 1 (x * (h (x-1))

	p	= f h 3				(* unfold f h 3*)
		= IF (EQ 3 0) 1 (x * (h (3-1))  

Notice that since f is non-recursive, some occurrences of its function 
calls, e.g. `f h x` and `f h 3`, can be *directly* unfolded without the need
to introduce intermediate functions. This is allowed as long as there is
no inefficient duplication of arguments. 

Hence, my transformed first-order program (dropping 'f' which is
not referred directly/indirectly by the main function 'p') would be:

	p where p   = IF (EQ 3 0) 1 (x * (h (3-1)))
		h x = IF (EQ x 0) 1 (x * (h (x-1))

Incidently, partial evaluation technique may be used to simplify the RHS of
'p'.

References
==========
[Feather82] A System for Assisting Program Transformation, ACM TOPLAS 1982
[Wand80] Continuation-Based Prog Transformation, JACM 1980

==============================================================================
Wei N Chin
Dept of Computing,Imperial College, London SW7 2AZ
e-mail wnc@doc.ic.ac.uk
NB Will be moving, after 15June1990, to 
	Dept of IS/CS, Natl Univ of Spore, Kent Ridge,Singapore 0511
=============================================================================