[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: ramsdell%linus@MITRE-BEDFORD.ARPA, tiedeman@ACF3.NYU.EDU, willc@tekchips.crl*Subject*: Re: Dependency analysis on internal DEFINE's*From*: Eric S. Tiedemann <tiedeman@acf3.NYU.EDU>*Date*: Sat, 18 Jun 88 07:13:58 EDT*Cc*: rrrs-authors@mc.lcs.mit.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

- Prev by Date:
**Re: days-after-J2000.0** - Next by Date:
**Meetings** - Prev by thread:
**Re: parallel argument evaluation** - Next by thread:
**Meetings** - Index(es):