Re: Why would anyone want opacity?

["R. Kent Dybvig" <dyb@cs.indiana.edu>]

> Although I apparently misconstrued what he meant by ``expensive'',
> ``complicated'', ``cost'' and ``efficient'', I felt compelled to detail the
> small set of fairly simple optimizations that would lead to an efficient
> implementation despite a fully general %PASSKEY-MATCH?.

The misunderstanding related not to what I meant by these terms, but
rather to what they were applied.  I was talking not about the fairly
straightforward problem of flattening out the veil/unveil calls, but
about the analysis that comes after that, which requires proving
properties that range from annoying to prove to impossible, depending
upon the generality of %passkey-match?

> Dybvig has dug in his heals insisting on full absolute unbreakable opacity.
> He has a good reason for doing so and I respect that.  His system would
> certainly be implemented that way. For him, the set of optimizations I
> pounded out will certainly be valid.

I haven't dug in my heels or insisted on "full absolute unbreakable
opacity".  I would, however, prefer that any transparency included in a
standardized record facility not come at the expense of programmer and
compiler program analyses.  The record proposal Bill and I are hashing
out certainly does not involve "full absolute unbreakable opacity".

> So Kent could, for example, generate the hidden record implementation
> passkeys as unique objects using the ``make-unique-object'' hack I
> presented some months ago on the Scheme Digest (or see the `Aside' below if
> this sounds unappealing).  If his implementation does not provide the
> kernel-level mechanisms for ripping apart opaque data to expose their
> hidden passkeys and if his implementation does not provide kernel-level
> tools for ripping apart ``unique objects'' (which were opaque LAMBDAs with
> hidden state), then he can safely know that users will not be able to CONs
> up passkeys on the fly that will satisfy %PASSKEY-MATCH?.
> 
> At the same time, using strings as passkeys elsewhere, of course, would not
> impact this.  So users could enjoy the full generality of passkeys and
> passkey matching while Kent could still secure the validity of an opaque
> record implementation by a self-imposed discipline of using unique objects
> as passkeys where he wants his flow analysis to carry through... while
> arranging for the kernel-level %PASSKEY-MATCH to do The Right Thing with
> both unique objects (EQ?) and strings (STRING=?, or whatever).
> 
> So have I finally gotten this right or is there still something I'm
> missing?

This is closer, but you'll still need to specify what %passkey-match?
does, or my program analyses won't be portable.  An implementation X 
well define %passkey-match? as follows, for example:

  (define %passkey-match?
    (lambda (x y)
      (if (and (string? x) (string? y))
          (string=? x y)
          #t)))

I should also point out that even your assumption that eq? implies
%passkey-match? is not guaranteed by the wording of your proposal.  It
would certainly be worth adding a guarantee to this effect.  As it
stands, an implementation may define %passkey-match? as follows, for
example:

  (define %passkey-match?
    (lambda (x y)
      (and (not (eq? x y))
           (equal? x y))))

This would be silly, of course, but valid.

Have you considered predicates in place of passkeys?  This would give
the programmer control over the matching process rather than the
implementation.

> (Aside: I'm going out on a limb on this, but consider this: you could even
> use as a passkey... the result of a call to MAKE-OPAQUE-TYPE !!  Since 1)
> each new opaque type is specified to not be EQ? to any other datum, and
> since 2) Kent's kernel-level %PASSKEY-MATCH? could be made to return #F on
> non-EQ?  opaque types, and since 3) one presumably could not crack an
> OPAQUE-VEILed datum to expose its passkey in Kent's Scheme implementation,
> using an opaque type as a passkey for your record implementation would be
> completely system trackable and not user forgeable.  This way you would not
> even need a separate ``make unique object'' hack like the one I posted to
> the Scheme Digest.  Anyway, this was too amusing to me not to mention it.
> It also dramatizes the comment from my proposal that with MAKE-UNIQUE-TYPE
> one would need no other additional mechanism for making new unique data
> types.)

Unfortunately, since this presumes a particular %passkey-match?
implementation, my analysis would again not be portable.  Moreover, it
ruins the orthogonality that you've been working to preserve, since the
opacity of opaque records depends upon the design of %passkey-match.

Kent