Re: Dependency analysis on internal DEFINE's

[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.

  [Ramsdell:]
  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.

Example 1:

  (let ((x '(a b c)))
    (define y
      (list (lambda (a) (cons a z)) x))
    (define z
      (list (lambda (a) (cons y a)) x))
    (append y z))

  This is allowed by the wording in the R3RS, and returns
  (#<PROCEDURE> (a b c) #<PROCEDURE> (a b c)).  Presumably it would
  also be allowed by the new proposal and would return the same thing.
  If not, the new proposal would not be a generalization of the current
  state of affairs since it would be less general in this case.

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.  It signals an error
  in MacScheme, and probably does something similar in most other
  implementations.  I do not know whether it would be allowed by the
  proposal.  If it would be allowed, what would it return?  If it is
  not allowed, then how can the proposal possibly be implemented while
  still allowing separate compilation for procedures like list and map?


  [Ramsdell:]
  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.

I understand how to implement general fixed points for non-strict
languages, which are the kind that Peyton Jones is concerned with.  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.

Peace, Will