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

Re: A (Low-Level) Opaque Object Proposal for R5RS



> R. Kent Dybvig writes:
>--------------------------------------------------------------------------
> The proposed separate opaque object facility will not yield the
> same benefits, for at least two reasons:
>--------------------------------------------------------------------------

Thanks for responding.  You've raised some important concerns.  I hope to
convince you that they are not fatal ones, at least for something like
implementing your winning opaque record proposal as portable Scheme source.

>--------------------------------------------------------------------------
> (1) with the passkey
> mechanism, it will be very difficult to determine all points where
> access to an object may occur,
>--------------------------------------------------------------------------

How is this any more or less difficult than determining all points where a
slot may be accessed using your record proposal?  Let me be very concrete
in case there's something subtle I'm overlooking.

I imagine, for example, that your syntactic DEFINE-RECORD opaque records
could be efficiently implemented using a portable (LETREC-style) macro atop
the opaque object proposal, along the lines of the following:

...........................................................................
CAVEAT: The following pseudo-code macro expansion abuses the backquoted
        macro body to avoid STRING->SYMBOL clutter. It also abuses the
        `<record-id> ...' notation to avoid MAP clutter.  Still, the
        intended non-abusive (real) macro definition should be obvious.
--------------------------------------------------------------------------
(DEFINE-RECORD <record-id> <record-type-name> <field-id>...)

==>

`(BEGIN (DEFINE make-,<record-id>             'TBA) ; abused backquote
        (DEFINE ,<record-id>?                 'TBA) ; abused backquote
        (DEFINE ,<record-id>-,<field-id>      'TBA) ; abused backquote
        ...
        (DEFINE set-,<record-id>-,<field-id>! 'TBA) ; abused backquote, etc
        ...
  ;;
  ;; `record's will be opaque vectors tagged by the <record-type-name>
  ;;
  ,(let* ((<hidden-passkey>            ; Magic secret hidden passkey that
            (number->string (random))) ;  the compiler could compile out!
          (         <field-name-list> (list <field-id>...))
          (<permuted-field-name-list> (permute <field-name-list>))
          (list-elt-number (lambda (lst elt) ; NB: elt must be in list
                             (if (eq? (car lst) elt)
                                 1
                                 (+ 1 (list-elt-number (cdr lst) elt))))))
     `(LET ((<hidden-underlying-opaque-type>
              (MAKE-OPAQUE-TYPE ,<hidden-passkey>)))
         (SET! make-,<record-id>
               (LAMBDA ,<field-name-list>
                 (OPAQUE-VEIL <hidden-underlying-opaque-type> ; opaque
                              (VECTOR ,<record-type-name>     ; tagged vect
                                      ,@<permuted-field-name-list>)
                              ,<hidden-passkey>)))
         (SET! ,(STRING->SYMBOL  ; non-abuse of backquote, for example
                  (STRING-APPEND (SYMBOL->STRING ,<record-id>)
                                 "?"))
               (LAMBDA (object)  ; recall: an `op type' is a predicate
                  (<hidden-underlying-opaque-type> object
                                                   ,<hidden-passkey>)))
         (SET! ,<record-id>-,<field-id>
               (LAMBDA (opaque-record ,<field-id>)
                 (VECTOR-REF (OPAQUE-UNVEIL opaque-record
                                            ,<hidden-passkey>)
                             ,(list-elt-number <permuted-field-name-list>
                                               <field-id>))))
         ...
         (SET! set-,<record-id>-,<field-id>!
               (LAMBDA (opaque-record ,<field-id> new-value)
                 (VECTOR-SET! (OPAQUE-UNVEIL opaque-record
                                             ,<hidden-passkey>)
                              ,(list-elt-number <permuted-field-name-list>
                                                <field-id>)
                              new-value)))
         ...)))
-------------------------------------------------------------------------------

I assume that whatever clever program flow analysis you may be thinking of
that could drop slots from your DEFINE-RECORD proposal would be able to
pull the same tricks with this sort of macro definition since the secret
passkey is uniquely generated for each new record type created and it never
escapes the scope of the macro expansion...  in fact, your analysis
technique should be able to compile out all the VEIL/UNVEIL stuff and just
tag the resulting record with a tag bit (or segregate it in a `secure'
segment of the heap analogous to your `immutable' segment) so that DISPLAY,
WRITE, PRETTY-PRINT, etc won't expose the underlying tagged vector
representation.  Under such an optimization VEIL/UNVEIL carry no run-time
overhead other than toggling a tag bit.  This should not be a perceptible
overhead.

>--------------------------------------------------------------------------
> and (2) programmers will likely neglect
> to use the separate opaque object facility when they construct records
> because of the added syntactic and conceptual baggage and (likely)
> performance hit.
>--------------------------------------------------------------------------

By providing programmers with the standard, portable, macro above for
DEFINE-RECORD using a (presumably) standardized OPAQUE-TYPE mechanism, no
special effort on the programmer's part is necessary.  They would just use
this macro.

And using your clever program flow analysis on the above macro, no extra
overhead should be required since all the VEIL/UNVEIL ops could be compiled
out, just as one would elide all the boxing/unboxing of numbers with a
clever flow analysis.

Let me emphasize again that I am explicitly _NOT_ trying to de-rail the
fine DEFINE-RECORD proposal that you and Bill are converging on.  If
anything, I am just suggesting that there might be a nice, portable way to
implement your record proposal using macros and a standardized opaque
object mechanism.  Your effort towards standardizing the semantics and
interface, I believe, are completely independent of the portable
implementation mechanism that OPAQUE-TYPEs would offer.

If your record proposal passes with no reference whatsoever to a general
opaque object mechanism like the one I've proposed, that's A OK by me.  For
instance, even in the presence of an orthogonal opaque object mechanism, it
would still be ``The Right Thing (tm)'' to all agree on and standardize a
semantics and interface for an opaque record mechanism like the one you
have proposed.

(Of course, one could also build a non-opaque, record-like efficient
access-by-slot-name mechanism just like your DEFINE-RECORD mechanism,
(called something like DEFINE-TRANSLUCENT-RECORD) that is just like the
above opaque macro-based DEFINE-RECORD, only without an underlying opacity
being involved.  My agenda being that if/when we get around to a module
proposal or the next neat thing, we won't deadlock on any opacity concerns
since those could be ironed out later after a non-opaque interface and
semantics is agreed upon.  In theory, any opaque version could be
implemented portably by augmenting a non-opaque implementation with the
right hidden VEIL/UNVEIL stuff.  This at least is my own personal pipe
dream. ``Some may say I'm a dreamer... but I'm not the only one.'')

>--------------------------------------------------------------------------
> It may be that we should consider including a separate, secure opaque
> object facility.  If so, I propose that we first add some form of weak
> pointer and allow programmers to implement their own opaque object
> facilities in the manner Bill has outlined.  If the facilities appear
> to be widely used, we can then include some variant in a standard
> library or build it more directly into the language.
>--------------------------------------------------------------------------

Huh?  You've totally lost me here.  The weak pointer question that Aubrey
posted, and Bill's reply to it, were a complete operational side-track
(read: red herring).  Although an interesting detail that an implementation
might use to reclaim storage in the general case, weak pointers are no more
necessary to an `efficient' opaque object mechanism than they are to an
`efficient' record mechanism.

Whatever clever tricks you imagine playing with your underlying opaque
record mechanism to reclaim slots and whatnot should apply equally to the
hidden (lexically closed) passkey-based opaque type macro I've suggested
above.  Certainly there are general cases where such an analysis would
fail, but that's not the point: it should certainly succeed in the narrow
example I provided above.

If you disagree that the same efficiency could be achieved in my above
macro for DEFINE-RECORD then I'd appreciate learning more about the flow
analysis you imagine yourself doing for your clever record mechanism.  I'm
sure I would learn an exciting new lesson from you, since it seems evident
to me that something not much more aggressive than closure analysis would
be required to optimize the hidden-passkey-based VEIL/UNVEIL above.

(I did casually browse your web page in search of some hint as to the
program analysis you have in mind, but I didn't see any titles in your
on-line publications that suggested such an analysis was discussed. I must
admit though that I didn't look very carefully.  I'm therefore relying on
the naive analogy of T/Orbit/Krantz-style closure analysis as a guide to
what I think you probably have in mind.  Please set me straight if this is
off the mark.)