Re: Dependency analysis on internal DEFINE's

[Eric S. Tiedemann <tiedeman@acf3.NYU.EDU>]

	From: willc@tekchips.crl
	
	I guess I don't understand what is being proposed, because it doesn't 
	look computable to me.  Here are the proposals, followed by a couple 
	of examples that illustrate my lack of understanding.
	
	  [Tiedeman:]
	  This can also be made to work by having LETREC's implement an 
	  applicative order fixpoint rather than the restriction of it 
	  specified in R3RS.  This amounts to performing dependency analysis 
	  to transform the above into a LET*.  Alas, this requires static 
	  analysis which an interpreter can't afford.  Some compilers, however,
	  already do it.

I wasn't actually making a proposal, just using the idea for purposes of 
conceptual ellucidation.  However, I'd like to try to answer your questions.

I used the term "the applicative order fixpoint" because I think what I have 
in mind is the most general fixpoint allowed by applicative order evaluation 
(I could well be wrong.) and I'll continue to use it in describing what I 
meant.  I'll refer to the behavior specified in the report as a "R3RS 
fixpoint."

The only place I fault R3RS fixpoints is where they are used for LETREC's that 
don't involve mutual recursion among all the bindings.  Such LETREC's can be 
broken up into subsets of mutually recursive bindings (i.e. the condensation 
of the LETREC's dependency graph.)  These subsets can further be ordered by 
their interdependencies (by topologically sorting the condensation) and then 
implemented as nested LETREC's (or LET's when they have but one binding which 
is non-recursive.)  Since all the LETREC's now represent true recursions we 
can safely treat them as R3RS fixpoints.  This treatment of LETREC's is a 
generalization of R3RS fixpoints.

Here's an example of a applicative order fixpoint which R3RS wouldn't handle:

	(letrec ((x 2)
	         (y (+ x 2)))
	 ....)

which, by the above method, is the same as:

	(let ((x 2))
	 (let ((y (+ x 2)))
	  ....)

In both of your examples the DEFINE's are mutually recursive and so R3RS 
semantics would be followed.

Note, however...

	Example 2:
	
	  (let ((x '(a b c)))
	    (define y
	      (map (lambda (a) (cons a z)) x))
	    (define z
	      (map (lambda (a) (cons y a)) x))
	    (append y z))
	
	  This is not allowed by the wording in the R3RS.

According to R3RS this is "undefined, and an error may be signalled."  Is 
"undefined" defined in the report?  Presumably the wording was designed to 
leave room for the plethora of "compatible extensions" out there--sometimes 
more than one in the same implementation.  Ceteris paribus I would prefer that 
it were "an error."

	                                                            ...The
	thing I don't understand is how an "applicative order" fixed point can
	be a generalization of the current state of affairs while remaining
	computable through static analysis.

I hope I've made this clear.  Whether the applicative order fixpoint is
actually defined for any given LETREC is, of course, not computable.  You can,
however, always set it up in linear time.

Eric