[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: A (Low-Level) Opaque Object Proposal for R5RS
> Will Clinger wrote:
>--------------------------------------------------------------------------
> [...] I'm a little concerned that
> Blair is overestimating the powers of certain general-purpose
> optimizations and underestimating the degree to which his
> proposed optimizations require a more specialized analysis.
>--------------------------------------------------------------------------
Sigh. This may be true, Clinger. Below I demonstrate exactly, step by
step, in full detail all the optimizations involved. Others will have to
judge if this requires an unacceptable degree of ``more specialized''
analysis than the standard general-purpose optimizations available in
optimizing Scheme compilers.
I still believe that these are pretty run-o-the-mill Scheme optimizations.
I've had partial evaluation (specialization) on the brain for over a year
now. There at least this stuff is completely standard.
>--------------------------------------------------------------------------
> Blair wrote:
>
> using USE/DEF/ESCAPE analysis (or whatever you want to call it)
>
> I would call it a specialized escape analysis. This begins to
> matter when Blair says
>
> This is standard USE/DEF analysis that even C and Fortran compilers do.
> Any compiler that claims to be an `optimizing' compiler surely must be
> doing USE/DEF/ESCAPE analysis.
>
> Blair's example shows that he is talking about an interprocedural
> analysis for heap-allocated variables.
>--------------------------------------------------------------------------
I don't believe so. I am talking about the analysis of the LET-bound
variables <hidden-passkey> and <hidden-underlying-opaque-type>. They are
bound by the LET form (bind = DEF) and within the scope of the body of the
LET, each textual appearance (USE) of the LET-bound variable is EQ?
because there are no SET!'s (DEF's) to these variables inside the body of
the LET form. This is not interprocedural analysis and it has nothing to
do with the heap.
I hope the details that follow will make this obvious.
>--------------------------------------------------------------------------
> In the C and Fortran world, USE/DEF analysis usually refers to
> the problem of finding all definitions (that is, assignments)
> that reach a given use.
>--------------------------------------------------------------------------
Exactly. And when there is exactly one such `reaching definition' then
there are no assignments (SET!'s) to the variable. Therefore, all textual
instances of the variable within the LET body (assuming alpha renaming to
avoid shadowing) must be EQ?. That is why I used the term USE/DEF
analysis. It is to determine the validity of copy propagation of variables
by name within a lexical contour where all textual instances are provably
EQ?.
I hope the details that follow will make this obvious.
>--------------------------------------------------------------------------
> 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.
>--------------------------------------------------------------------------
I'm not talking about _inter_procedural (cross-block) analysis. I'm
talking about _intra_procedural (internal block) analysis. And I'm not
talking about heap-allocated "variables". I'm talking about LET-bound
"variables"... which can be stack or register allocated if they don't
escape.
I hope the details below will make this obvious.
>--------------------------------------------------------------------------
> On the other hand, Blair's example doesn't really require USE/DEF
> analysis because the <hidden-passkey> is never assigned or side-
> effected.
>--------------------------------------------------------------------------
To deduce that it is not assigned or side effected is to have done USE/DEF
analysis. Perhaps I was abusing the term `USE/DEF' analysis to mean
`deciding if a variable is assigned or if its value remains constant' but I
thought that is exactly what USE/DEF analysis means, as defined in Aho et
al's `Dragon Book', to cite a canonical reference.
To me, a LET-bound parameter is DEF'd by its (right-hand side) binding:
(LET ((x 'xs-DEF-value)) ...)
And any textual appearance of the variable in the body of the LET which is
not the target of a SET! (or another shadowing LET) is a `USE'.
To deduce that all textual appearances of a LET-bound variable within the
body of the LET form are `USE' instances--- specifically, none are `DEF'
instances--- is to have done USE/DEF analysis. To perform this analysis
requires a program flow analysis to follow the thread of control through
the source, so when Dybvig pounded his chest about his mighty `program flow
analysis' I assumed that part of that would include this kind of classic
`USE/DEF' analysis... which is why I brought it up in the first place.
If this is a misapplication of the term `USE/DEF' then I apologize. Forgive
me please if I stick with this terminology at least for the remainder of
this post. If there is some more appropriate term form what I am
describing then I will certainly adopt the more appropriate term in the
future. Thanks.
>--------------------------------------------------------------------------
> Although his example can be handled by escape analysis,
> I would point out that no existing Scheme compiler performs the
> specific escape analysis that would be required.
>--------------------------------------------------------------------------
You may be correct. I have not looked at every existing Scheme compiler.
On the other hand, the escape analysis required is not as aggressive as you
make it out to be.
I hope the details below will make this obvious.
>--------------------------------------------------------------------------
> It probably wouldn't be difficult to add that specific escape
> analysis, but I can't blame Dybvig or any other compiler writer
> for thinking that their time might be better spent on different
> optimizations.
>--------------------------------------------------------------------------
I cannot judge how other people's time should be spent. I also do not
blame people for how they spend their time. It is not my place to do so.
Some day when I become responsible for supervising others, I will have to
change that attitude.
>--------------------------------------------------------------------------
> Blair also writes:
>
> Moreover, each textual occurrence of the <hidden-underlying-opaque-type> in
> the code can likewise be compile-time proven to be EQ?. Therefore, all
> VEIL/UNVEIL calls in the code above can be flattened out to not bother
> checking the passkey at run time, and the <record-id>? predicate can
> likewise be partial evaluated into a flattened test that also does not
> bother to check the passkey at run time (since it is compile-time provable
> that <hidden-passkey> _is_ the passkey for this opaque type).
>
> This requires only Orbit-style closure analysis. Such closure analysis has
> been a standard technique for at least a decade. It (among other things)
> is the bread and butter of LISP optimization. Any Scheme compiler that
> claims to be an `optimizing' compiler surely must be doing closure
> analysis.
>
> Yes, closure analysis is a standard optimization, but calling
> this a closure analysis seems bizarre to me. Lots of compilers perform
> closure analysis.
>--------------------------------------------------------------------------
Perhaps ``closure analysis'' is not the best way to have described this.
I hope what follows will clarify what I meant.
>--------------------------------------------------------------------------
> No existing Scheme compiler performs the optimization Blair is talking
> about.
>--------------------------------------------------------------------------
Again, I have not scrutinized every existing Scheme compiler so I cannot
say whether or not this is correct. My belief is that MIT Scheme's LIAR
compiler comes very close to this, as I explain below. For all I know,
it does the EQ?-ness (USE/DEF) analysis as well, but I am not sure.
>--------------------------------------------------------------------------
> They can't, because the correctness of Blair's optimization
> depends upon the inability to take apart and to forge objects
> created by OPAQUE-VEIL, and this inability cannot be known by
> existing compilers.
>--------------------------------------------------------------------------
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.
Specifically, my proposed straw-man weak implementation explicitly identified
the kernel-level underlying opaque data abstractions as hidden from the user
and known to the compiler. They were:
;; Kernel-level data representations
(define *opaque-object-tag* ; Unique object not EQ? to any other
(list '*opaque-object-tag*))
(define (%opaque-object-new <opaque-type> <datum>) ; Tagged 2-tuple
`( ,*opaque-object-tag* ,<opaque-type> . ,<datum>))
(define (%opaque-object? <datum>)
(and (pair? <datum>)
(eq? (car <datum>)
*opaque-object-tag*)))
(define %opaque-object-type cadr)
(define %opaque-object-datum cddr)
(define %passkey-match? equal?) ; Not EQ? since tests two dotted params
=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=
Following are the details which I hope will make everything obvious.
=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=o=
On the unlikely chance that anyone is still reading this, I will now try
one last time to spell it out completely with nothing left to the
imagination.
Consider:
(DEFINE-RECORD 'recordfoo "Record Foo" 'fieldfoo)
I proposed that this expand into the following (with the LET-capture of the
hidden passkey as I described last time so we don't need to worry about
EQ?-ness of constant string literals):
(BEGIN (DEFINE make-recordfoo 'TBA)
(DEFINE recordfoo? 'TBA)
(DEFINE recordfoo-fieldfoo 'TBA)
(DEFINE set-recordfoo-fieldfoo! 'TBA)
;;
;; `record's will be opaque vectors tagged by the <record-type-name>
;;
(LET ((<hidden-passkey> "42"))
(LET ((<hidden-underlying-opaque-type>
(MAKE-OPAQUE-TYPE <hidden-passkey>)))
(SET! make-recordfoo
(LAMBDA (fieldfoo)
(OPAQUE-VEIL <hidden-underlying-opaque-type> ; opaque
(VECTOR "Record Foo" ; tagged vect
fieldfoo)
<hidden-passkey>)))
(SET! recordfoo?
(LAMBDA (object) ; recall: an `op type' is a predicate
(<hidden-underlying-opaque-type> object
<hidden-passkey>)))
(SET! recordfoo-fieldfoo
(LAMBDA (opaque-record)
(VECTOR-REF (OPAQUE-UNVEIL opaque-record
<hidden-passkey>)
1)))
(SET! set-recordfoo-fieldfoo!
(LAMBDA (opaque-record new-value)
(VECTOR-SET! (OPAQUE-UNVEIL opaque-record
<hidden-passkey>)
1
new-value)))
)))
With the proposal that MAKE-OPAQUE-TYPE, OPAQUE-VEIL, and OPAQUE-UNVEIL be
reserved keywords, and given the sample weak implementation from the opaque
type proposal as an example of the kind of hidden underlying mechanism an
implementation might choose, a compiler can in-line these as follows
(making <passkey>s non-optional to avoid needlessly complicating things
with dotted param lists):
(BEGIN (DEFINE make-recordfoo 'TBA)
(DEFINE recordfoo? 'TBA)
(DEFINE recordfoo-fieldfoo 'TBA)
(DEFINE set-recordfoo-fieldfoo! 'TBA)
;;
;; `record's will be opaque vectors tagged by the <record-type-name>
;;
(LET ((<hidden-passkey> "42"))
(LET ((<hidden-underlying-opaque-type> ; in-lined MAKE-OPAQUE-TYPE call
(LETREC ((<opaque-type>-pred
(LAMBDA (<object> <<passkey>>)
(AND (EQ? (AND (%OPAQUE-OBJECT? <object>)
(%OPAQUE-OBJECT-TYPE <object>))
<opaque-type>-pred)
;;; in-lined %PASSKEY-MATCH?
(OR (EQ? <hidden-passkey> <<passkey>>)
(STRING=? <hidden-passkey> <<passkey>>))))))
<opaque-type>-pred)))
(SET! make-recordfoo
(LAMBDA (fieldfoo) ; in-lined OPAQUE-VEIL call
(LET ((attempt
(%OPAQUE-OBJECT-NEW <hidden-underlying-opaque-type>
(VECTOR "Record Foo" ; tagged vect
fieldfoo))))
(IF (<hidden-underlying-opaque-type> attempt <hidden-passkey>)
attempt
(ERROR "OPAQUE-VEIL: Non-matching <passkey>"
<hidden-underlying-opaque-type>
<hidden-passkey>)))))
(SET! recordfoo?
(LAMBDA (object) ; recall: an `op type' is a predicate
(<hidden-underlying-opaque-type> object
<hidden-passkey>)))
(SET! recordfoo-fieldfoo
(LAMBDA (opaque-record) ; in-lined OPAQUE-UNVEIL call
(VECTOR-REF (LET ((<opaque-type>
(AND (%OPAQUE-OBJECT? opaque-record)
(%OPAQUE-OBJECT-TYPE opaque-record))))
(IF <opaque-type> ; I.e., really _is_ opaque obj
(LET ((win? (<opaque-type> opaque-record
<hidden-passkey>)))
(IF win?
(%OPAQUE-OBJECT-DATUM opaque-record)
(ERROR "OPAQUE-UNVEIL: key mismatch"
<opaque-type>
<hidden-passkey>)))
(ERROR "OPAQUE-UNVEIL: not an opaque-object"
opaque-record)))
1)))
(SET! set-recordfoo-fieldfoo!
(LAMBDA (opaque-record new-value) ; in-lined OPAQUE-UNVEIL call
(VECTOR-SET! (LET ((<opaque-type>
(AND (%OPAQUE-OBJECT? opaque-record)
(%OPAQUE-OBJECT-TYPE opaque-record))))
(IF <opaque-type> ; I.e., really _is_ opaque
(LET ((win?
(<opaque-type> opaque-record
<hidden-passkey>)))
(IF win?
(%OPAQUE-OBJECT-DATUM opaque-record)
(ERROR "OPAQUE-UNVEIL: key mismatch"
<opaque-type>
<hidden-passkey>)))
(ERROR "OPAQUE-UNVEIL: not an opaque-object"
opaque-record)))
1
new-value)))
)))
Now. USE/DEF analysis of the body of (LET ((<hidden-passkey> ...))) reveals
that <hidden-passkey> is never DEF'd except in its initial LET-bound
appearance. This is not _inter_procedural analysis of a heap-allocated
variable. It is USE/DEF analysis of a LET-bound variable within the body
of the LET form. Let me explain:
Insofar as a LET body can be desugared into an explicit implied LAMBDA
application [spec., ((LAMBDA (<hidden-passkey>) ...) "42")], it might be
argued that this is an _intra_procedural analysis of a LAMBDA-bound
parameter. The fact that the body of the LET form contains LAMBDA
expressions does not alone make this a problem of inter-procedural
analysis. The fact that they are closed in a mutual lexical LET contour
makes the analysis of these LET-bound variables an intraprocedural
analysis. Bare in mind that the sole purpose of this USE/DEF analysis is
to determine at compile time if two textual occurrences of a variable are
EQ?. This will become important when we've in-lined various procedure
calls.
A similar analysis of <hidden-underlying-opaque-type> reveals it to be
DEF'd only at its LET-bound initial appearance as well. I.e., it is not
SET!'d either.
This (given the implied alpha renaming to avoid any capture/shadowing
problems) means two very important things:
1. every textual appearance of <hidden-passkey> is EQ? to every other textual
appearance of <hidden-passkey>.
2. <hidden-underlying-opaque-type> can be in-lined anywhere it appears in
operator position since its value is constant.
Now we are ready to consider the details of the flattening I keep alluding
to.
------------------------
Flattened MAKE-RECORDFOO
------------------------
Now consider:
(LET ((<hidden-underlying-opaque-type>
(MAKE-OPAQUE-TYPE <hidden-passkey>)))
(SET! make-recordfoo
(LAMBDA (fieldfoo)
(OPAQUE-VEIL <hidden-underlying-opaque-type> ; opaque
(VECTOR "Record Foo" ; tagged vect
fieldfoo)
<hidden-passkey>)))
became (after in-lining of OPAQUE-VEIL):
(LET ((<hidden-underlying-opaque-type> ; in-lined MAKE-OPAQUE-TYPE call
(LETREC ((<opaque-type>-pred
(LAMBDA (<object> <<passkey>>)
(AND (EQ? (AND (%OPAQUE-OBJECT? <object>)
(%OPAQUE-OBJECT-TYPE <object>))
<opaque-type>-pred)
;;; in-lined %PASSKEY-MATCH?
(OR (EQ? <hidden-passkey> <<passkey>>)
(STRING=? <hidden-passkey> <<passkey>>))))))
<opaque-type>-pred)))
(SET! make-recordfoo
(LAMBDA (fieldfoo) ; in-lined OPAQUE-VEIL call
(LET ((attempt
(%OPAQUE-OBJECT-NEW <hidden-underlying-opaque-type>
(VECTOR "Record Foo" ; tagged vect
fieldfoo))))
**===> (IF (<hidden-underlying-opaque-type> attempt <hidden-passkey>)
attempt
(ERROR "OPAQUE-VEIL: Non-matching <passkey>"
<hidden-underlying-opaque-type>
<hidden-passkey>)))))
In-lining the call to <hidden-underlying-opaque-type> results in:
(SET! make-recordfoo
(LAMBDA (fieldfoo) ; in-lined OPAQUE-VEIL call
(LET ((attempt
(%OPAQUE-OBJECT-NEW <hidden-underlying-opaque-type>
(VECTOR "Record Foo" ; tagged vect
fieldfoo))))
(IF (AND (EQ? (AND (%OPAQUE-OBJECT? attempt))
(%OPAQUE-OBJECT-TYPE attempt))
<hidden-underlying-opaque-type>)
;;; in-lined %PASSKEY-MATCH?
(OR (EQ? <hidden-passkey> <hidden-passkey> )
(STRING=? <hidden-passkey> <hidden-passkey>)))
attempt
(ERROR "OPAQUE-VEIL: Non-matching <passkey>"
<hidden-underlying-opaque-type>
<hidden-passkey>)))))
The reason the arguments to the LETREC-enshrouded LAMBDA in operator
position can be pushed through by unfolding the LETREC are detailed in Bill
Rozas' S.B. thesis [citation 70 in R4RS... and I think presented at an L&FP
conference a few years ago as well].
Any Scheme compiler that does not do this sort of LETREC-unfolding closure
optimization will not result in the passkey flattening I have argued for.
This is perhaps the greatest weakness in my argument. In my defense,
however, I believe that ML compilers and functional language compilers
(like those described in Simon Peyton-Jones' and John Reynolds' classic
texts) do. I robustly assert that any Scheme compiler that does in-lining
and closure folding should be capable of LETREC unrolling like this too.
To continue then, at this point, USE/DEF analysis of `attempt' reveals that
it is not side-effected so program flow analysis can conclude that the test
in the IF form must evaluate to TRUE. The (PAIR? attempt) test result can
be deduced from mere type analysis but the test for the value specific (EQ?
(CAR attempt) *opaque-object-tag*) where *opaque-object-tag* is a hidden
implementation constant used to tag opaque objects requires either a very
aggressive
Therefore, the result is this:
(SET! make-recordfoo
(LAMBDA (fieldfoo) ; in-lined OPAQUE-VEIL call
(LET ((attempt
(%OPAQUE-OBJECT-NEW <hidden-underlying-opaque-type>
(VECTOR "Record Foo" ; tagged vect
fieldfoo))))
attempt)))
which becomes:
(SET! make-recordfoo
(LAMBDA (fieldfoo) ; in-lined OPAQUE-VEIL call
(%OPAQUE-OBJECT-NEW <hidden-underlying-opaque-type>
(VECTOR "Record Foo" ; tagged vect
fieldfoo))))
The <hidden-passkey> does not appear. Therefore, record construction is
not made ``inefficient'' regardless of the passkey-based opaque object
implementation and its general (implementation dependent) %PASSKEY-MATCH?
(which could be string based). This is because OPAQUE-VEIL buried inside
the make-record constructor can be compile-time flattened out. Therefore,
Dybvig and Clinger, all bets are not off in record construction if
string-based passkey matching is used. And all that is required of a
compiler is EQ?-ness tracking of variables and LETREC unfolding a la LIAR,
along with the compiler knowledge that %PASSKEY-MATCH? is reflexive--- that
is, that (EQ? x y) implies (%PASSKEY-MATCH? x y). I don't think this is so
much to expect from an optimizing Scheme compiler.
--------------------
Flattened RECORDFOO?
--------------------
Similarly,
(SET! recordfoo?
(LAMBDA (object) ; recall: an `op type' is a predicate
(<hidden-underlying-opaque-type> object
<hidden-passkey>)))
can become (after in-lining of <hidden-underlying-opaque-type>):
(SET! recordfoo?
(LAMBDA (object) ; recall: an `op type' is a predicate
(AND (EQ? (AND (%OPAQUE-OBJECT? <object>)
(%OPAQUE-OBJECT-TYPE <object>))
<hidden-underlying-opaque-type>)
(OR (EQ? <hidden-passkey> <hidden-passkey>)
(STRING=? <hidden-passkey> <hidden-passkey>)))))
which flattens to:
(SET! recordfoo?
(LAMBDA (object) ; recall: an `op type' is a predicate
(EQ? (AND (%OPAQUE-OBJECT? <object>)
(%OPAQUE-OBJECT-TYPE <object>))
<hidden-underlying-opaque-type>)))
which likewise suffers no ``inefficiency'' at the hands of passkey matching.
----------------------------
Flattened RECORDFOO-FIELDFOO
----------------------------
And finally:
(SET! recordfoo-fieldfoo
(LAMBDA (opaque-record)
(VECTOR-REF (OPAQUE-UNVEIL opaque-record
<hidden-passkey>)
1)))
became (after in-lining of OPAQUE-UNVEIL):
(SET! recordfoo-fieldfoo
(LAMBDA (opaque-record) ; in-lined OPAQUE-UNVEIL call
(VECTOR-REF (LET ((<opaque-type>
(AND (%OPAQUE-OBJECT? <object>)
(%OPAQUE-OBJECT-TYPE <object>))))
(IF <opaque-type> ; I.e., really _is_ opaque obj
(LET ((win? (<opaque-type> opaque-record
<hidden-passkey>)))
(IF win?
(%OPAQUE-OBJECT-DATUM opaque-record)
(ERROR "OPAQUE-UNVEIL: key mismatch"
<opaque-type>
<hidden-passkey>)))
(ERROR "OPAQUE-UNVEIL: not an opaque-object"
opaque-record)))
1)))
Here no further in-lining is possible. The instance of <opaque-type>
cannot be deduced to be EQ? to <hidden-underlying-opaque-type>. This is
purely intentional. It allows, for example, the passkeys to be used to
concoct some partial order on opaque types (opaque subtyping) using the
%PASSKEY-MATCH? in some interesting implementation dependent way.
Nonetheless, in the case where no opaque subtyping is being used (which is
the case for the opaque record implementation presented here), the textual
instance of <opaque-type> here will be run-time EQ? to the textual instance
of <hidden-underlying-opaque-type>, so the textual instance of <<passkey>>
inside <hidden-underlying-opaque-type> will be run-time EQ? to
<hidden-passkey>. So again we will not have to resort to the more
expensive STRING=? for the passkey match. So, even though the run-time EQ?
test cannot be compile-time flattened out in this case, the run-time
EQ?-ness is certain.
Even in a native opaque DEFINE-RECORD implementation like the one Dybvig
has been advocating, such a test to see if an object really is a record and
that it really is the right kind of record is unavoidable: it is part of
the semantic specification of record accessors. Compliant implementations
must do it. So no extraneous ``inefficiency'' is introduced by this
proposed opaque object based implementation.
---------------------------------
Flattened SET-RECORDFOO-FIELDFOO!
---------------------------------
The analysis is identical to that for RECORDFOO-FIELDFOO. So too is the
conclusion: a run-time EQ? test against the passkey will be required, but
the more expensive STRING=? will be avoided. Although this cannot be
proved at compile time, it is nonetheless true at run time (assuming no
interesting opaque subtyping is involved, which is the case for the opaque
record case).
=======================
Conclusions:
1. An implementation can offer a very general, possibly STRING=? based,
hidden %PASSKEY-MATCH? predicate to guard the opaque VEIL/UNVEIL without
forcing ``inefficiency'' like that which Dybvig insisted would be
unavoidable.
2. Opaque records could be implemented atop the more general opaque
object proposal without requiring unwanted ``inefficiency'' due to
passkey matching.
3. The sort of optimizations necessary to allow a compiler to achieve this
level of ``efficiency'' is not beyond the pale of common Scheme compiler
techniques (if you allow that LETREC unfolding is not ``beyond the
pale'').
Therefore:
1. Dybvig's claim that this is necessarily too expensive an implementation
technique for optimizing Scheme compilers to handle is unfounded.
2. Clinger's claim that ``Blair is overestimating the powers of certain
general-purpose optimizations and underestimating the degree to which
his proposed optimizations require a more specialized analysis'' is
likewise unsupported: The USE/DEF analysis involved is classic
intraprocedural USE/DEF analysis of LET-bound "variables" and the LETREC
unfolding required is classic ML/functional-language style closure
folding. The MIT Scheme LIAR compiler, for example, handles this kind
of LETREC unfolding.
Naturally, I cannot make any claim about every existing Scheme compiler.
--
So. Am I full of shit or are these conclusions valid?