Dependency analysis on internal DEFINE's

[John D. Ramsdell <ramsdell%linus@mitre-bedford.ARPA>]

>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 strongly agree that a dependency analysis should be done on local
defines.  One simply finds the strong component of the dependency
graph and then does a topological sort on the graph in which a strong
component has been replaced by a single node.  A strong component
with no cycles (a single node) maps to a LET, and other strong
components map to a LETREC.  Thus both:

	    (define y (z))
	    (define x (car y))

and

	    (define x (car y))
	    (define y (z))

map to:

	    (let ((y (z)))
	      (let ((x (car y))) .....

There are linear algorithms for both topological sorting and finding
strong components.
John
PS. By the way, many pure functional programming languges do the above
analysis; see Simon L. Peyton Jones' recent book on implementing
functional programming languages.