[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: A (Low-Level) Opaque Object Proposal for R5RS
> Will Clinger writes:
>
> Aside from that and some uninteresting details of terminology,
> Blair and I are in violent agreement.
>--------------------------------------------------------------------------
I am pleased to hear it. I was beginning to get defensive about this.
>--------------------------------------------------------------------------
> In fact, it appears that my own Twobit compiler performs every
> single one of the general optimizations that Blair appeals to
> in support of his argument. I wouldn't have known this from the
> terminology he used. For example, we seem to disagree on whether [...]
>--------------------------------------------------------------------------
1.
>--------------------------------------------------------------------------
> a lambda-bound variable that is captured by several lambda
> expressions, whose results are stored into global variables,
> constitutes a heap-allocated variable
>--------------------------------------------------------------------------
Agreed. The environment frame that holds the closed over variables resides
in the heap by virtue of the LAMBDA closures being assigned to global
variables. Like:
(BEGIN (DEFINE f 'TBA)
(DEFINE g 'TBA)
(LET ((closed-over 42))
(LET ((escape-f (LAMBDA () closed-over)))
(escape-g (LAMBDA () (- closed-over)))
(SET! f escape-f)
(SET! g escape-g))))
The reason I brought up things like `USE/DEF' was to determine EQ?-ness.
The reason I brought up `closure analysis' was for the LETREC unfolding
(not for whether or not the LAMBDA procedures close over variables and
escape through global assignment). Neither of these are affected by issues
of heap allocation. I thought you were bringing that up for some other
reason.
I was unclear in why I brought up closure analysis originally. And I was
confused by your emphasis on heap allocation. We were looking at two
different parts of the code, I believe. I was looking at the textual
appearance of the LAMBDA expressions and arguing about how they could be
flattened to avoid the STRING=? tests on passkeys (which was the complaint
that Kent Dybvig raised that I was trying to defend against). You, by
contrast, were looking at the fact that these closures, whether flattened
or not, close over LET-bound variables and escape to the top level through
assignment, thus requiring heap allocation of the LET-introduced
environment frames.
You are correct that these frames must be heap allocated. I just didn't
see the relevance of emphasizing that and, at the time, was confused about
why you were bringing it up. I thought you were arguing that the
optimizations I had in mind were somehow invalidated by the fact that the
LET-bound variables must be heap allocated. I could not imagine any other
reason for you're bringing that up.
2.
>--------------------------------------------------------------------------
> and on whether a static
> analysis that must examine the code for the several global
> procedures that result from those lambda expressions constitutes
> an interprocedural analysis.
>--------------------------------------------------------------------------
To me, `interprocedural analysis' carries an implication of things like
separate compilation of two top-level defined procedures sharing only
global variables--- which constitutes two completely distinct code blocks.
This is because the languages for which `interprocedural analysis' is
traditionally discussed in all the standard textbooks and mainstream
conference proceedings (namely, C, Fortran, etc in the `Dragon Book' and in
PLDI and POPL) don't have internally defined or anonymous local (LAMBDA)
procedures. In these situations, the analysis requires a global
optimization and a closed-world assumption (or `block compilation'-- i.e,
that all code files and modules are available at compile time to be lumped
into one massive code block for compilation). This is a notoriously
unrealistic requirement and compilers are notoriously poor at doing global
analysis. It is also expensive (in compiler running time).
For example, two procedures in separate files:
file 1: (define (even? x) (or (zero? x) (odd? (- x 1))))
file 2: (define (odd? x) (and (not (zero? x)) (even? (- x 1))))
...would require global interprocedural analysis to do most interesting
optimizations. Academicians may chatter about this sort of thing, but most
of us just roll our eyes at the mention of `global interprocedural
analysis' since (nearly) no compiler ever does this sort of thing.
By contrast, in the case of a Scheme LET expression whose body introduces
two anonymous LAMBDAs, yes I guess the analysis that involves them both is
`interprocedural' in the sense that it looks at both procedures and infers
information between the two of them, but this is a strictly _local_
optimization, not a _global_ optimization. Thus, the USE/DEF analysis of
any closed over LET-bound variables they may share does not involve
_global_ control flow or USE/DEF analysis: only local analysis is required.
When you brought up the fact that these procedures are `global' that seemed
to me to be a stronger statement than just that these closures will
eventually escape to the global environment through assignment:
specifically, it seemed to be strongly suggestive (to me) that a global
analysis would be required. When you introduced the term `interprocedural
analysis' in this context, it worried me even more. That is why I reacted
so strongly to your wording when you said in:
>--------------------------------------------------------------------------
> I don't think interprocedural USE/DEF
> analysis is terribly common yet in C or Fortran compilers.
> Interprocedural USE/DEF analysis for heap-allocated "variables"
> in C is certainly rare.
>--------------------------------------------------------------------------
and it is why I still think it is misleading for you to say things like:
>--------------------------------------------------------------------------
> a static
> analysis that must examine the code for the several global
> procedures that result from those lambda expressions constitutes
> an interprocedural analysis.
>--------------------------------------------------------------------------
So, yes the analysis is interprocedural regarding the two local LAMBDA
expressions, but it is intra-procedural within the (implied LAMBDA which is
the) enclosing LET contour. This sort of thing is not common in C or
Fortran compilers simply because they don't have local (internal) procedure
definitions. I thought what I was describing was an obvious extension of
normal USE/DEF analysis for local defines, and I thought this was common
among Scheme compilers. MIT Scheme's LIAR compiler does this, for example.
I have had several conversations with the gurus of the MIT Scheme compiler
about this sort of thing. I was once even screwed by it when I tried to
assign a locally defined procedure variable that the compiler had decided
was constant (that compiler bug was later fixed... and I was talked out of
doing it that way anyway since it was deemed to be bad style).
Yes, the resulting closures escape to the global environment through
assignment but no global analysis is required: a local analysis of two
locally defined procedures that are made global through later assignment is
not a `global interprocedural analysis'. A strictly local analysis is
sufficient to flatten out the EQ? tests, as I demonstrated.
Again, I was confused by your apparent emphasis on what I took to be a
claim that `global interprocedural analysis' was required in the same sense
that C and Fortran compiler writers would use the term `global
interprocedural analysis' (which nobody ever implements, to my knowledge).
The sense in which C and Fortran compilers use that term is not at all what
I had in mind and I really wish you would stop using that term to describe
the optimizations I detailed.
>--------------------------------------------------------------------------
> > Huh?! OPAQUE-VEIL in my proposal was a special form. As such, its
> > underlying implementation is not revealed to the Scheme user. It is a
> > reserved identifier that signals to the compiler to emit a hunk of code,
> > possibly at the machine language level, that the Scheme programmer cannot
> > access at the Scheme language level. So the above paragraph makes no sense
> > to me at all.
>
> The fact that something is a special form does not imply that
> its underlying implementation is not revealed to the Scheme
> user. That assumption needs to be made explicit, as I pointed
> out. I am glad to see from the above paragraph that Blair agrees
> with me.
>
> The fact that the underlying implementation of a special form
> is not revealed to the Scheme user is still not enough to justify
> the optimization in question, because the user might be able to
> guess the implementation. We must make the stronger assumption
> that the Scheme programmer has absolutely no way to forge ("access"?)
> the values created by OPAQUE-VEIL. I am glad to infer from the
> above paragraph that Blair agrees with me about the need to make
> this assumption explicit also.
>--------------------------------------------------------------------------
Yes. I agree completely. That is exactly why in the `CORRECTION' followup
I explicitly stated:
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ Since %OPAQUE-OBJECT-NEW, %OPAQUE-OBJECT? and %OPAQUE-OBJECT-TYPE are
+ kernel-level abstractions known to the compiler (e.g., they could be
+ implemented as assembly-level primitives so the user cannot infiltrate them
+ as Scheme source), program flow analysis can reduce the first arm of the
+ outermost AND to TRUE.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++