Re: Why would anyone want opacity?

[Michael R. Blair <ziggy@martigny.ai.mit.edu>]

> Will Clinger writes:
>
> Users of MacScheme+Toolsmith may recall that I do not hesitate
> to provide horribly low-level abstraction-breaking facilities,
> provided everyone understands that the precise result of a call
> to %%RECORD-PEEK (e.g. "Application unexpectedly quit: ID = 1"
> or "segmentation fault; core dumped") will depend upon the
> implementation.
> 
> Michael Blair has been banging the drum for a compiler
> optimization that would be incorrect in the presence of a
> well-defined OPAQUE-THINGY-POKE!, so he and/or Kent Dybvig
> might have a contrary attitude.
>--------------------------------------------------------------------------

Sigh. After reading this and Kent Dybvig's response to my latest fury of
details, I think I've finally gotten it through my thick head what Will and
Kent were objecting to.

I have tried to bend over backwards to accommodate everyone.  That is why I
explicitly said in the proposal (and I will repeat it again here) that...

  Latitude
  --------
  Whether and how a given Scheme implementation chooses to address and/or
  enforce opacity should be up to the implementors.  For instance, an
  implementation may chose to leave a kernel-level back door for examining
  opaque objects, to be used by the garbage collector and debugger or other
  run-time system tools or code walkers that systems programmers might want
  to build.  This could be as simple as giving the programmer access to the
  ``kernel-level'' data abstractions in the straw-man prototype
  implementation below.

This means that if some implementation wants OPAQUE-THINGY-POKE! then they
have every right to provide it.

The reason I went into horrid detail about a possible set of optimizations
for making passkey-based opacity ``efficient'' was that Kent Dybvig made
some remark about it requiring:

  a two-level analysis problem, which is at
  least more expensive and conceptually more complicated than with an
  opaque define-record

and

  While this can be done, I'm not enthusiastic about doing it or
  the cost associated with doing it, and I'll bet that enough other
  implementations won't do it that programmers will learn that the
  portable define-record is not efficient enough for their purposes.

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?.

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.

To be fair, though, Kent then followed this by clarifying that:
>--------------------------------------------------------------------------
> For our program analyses, we want to be able to find all places where a
> given field accessor or mutator is used.  We can't do so if equivalent
> accessors and mutators can be created on the fly from instances of a
> record type, as in the original record proposal, except in the limited
> case where we never lose track of any instance of the record type.
> This is true as well with records implemented as you described, as long
> as passkeys are matched by anything as general as, say, string=?.
>--------------------------------------------------------------------------

I thought I had already dealt with that issue.  For the code which
implements records using OPAQUE-VEIL, etc, he does not have to use strings.
I thought I had already addressed that (in a reply to Aubrey Jaffer
earlier, which is why I thought Kent was complaining about something else).
Users can certainly still use strings (or whatever) elsewhere in their own
opaque objects but Kent does not have to do so in an implementation of
opaque records atop opaque objects.

I now regret having used ``(NUMBER->STRING (RANDOM))'' as the
<hidden-passkey> in my latest example.  I now finally understand that it is
_that_ which is the heart of his complaint. Even if the %PASSKEY-MATCH? is
as general as EQUAL?, if he uses some more easily trackable and
non-forgeable datum for passkeys in an opaque record implementation then
his analysis should still go through.  For opaque objects that a user may
create in some other abstraction of their own, the user may choose to use
strings as passkeys _but_you_don't_have_to_do_it_in_the_opaque_record_
_implementation_that_you_give_to_them.

That is why I responded to Aubrey Jaffer's query about security, encryption
and passkeys by saying:

  I think it is up to you to find a passkey mechanism that fulfills your
  personal needs and desires.  This is precisely why I left the details of
  implementing passkeys up to the implementor.

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?

(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.)


For others who are not so adamant about utterly unbreakable opacity, the
set of optimizations I argued for may or may not go through in their
implementations.  Presumably, Will, you would opt for this `latitude' by
exposing the kernel-level abstractions for the user to crack anything they
want.  So too would MIT Scheme, I imagine.

But my proposal, of course, said nothing about these optimizations or what
latitude an implementation might exercise that might invalidate them.

Specifically, the one and only reason I brought up those optimizations was
to argue for the potential efficiency of an opaque record implementation
atop a very general passkey-based opaque object mechanism.  Although it did
not address the _real_ objection Kent was raising, I think it was probably
still a useful exercise, if only to anticipate any ``efficiency'' concerns
anyone else might have brought up.

> Will continues..
>--------------------------------------------------------------------------
> On the other hand, the need for Blair's optimization would go
> away if we made a couple of minor changes to his proposal.
>--------------------------------------------------------------------------

Since I cannot figure out what minor changes you have in mind, could you
please be more explicit?  At this point, I'd be willing to agree to almost
anything.

>--------------------------------------------------------------------------
> More to the point, Blair's optimization would still be valid
> so long as the semantics of OPAQUE-THINGY-POKE! and its ilk
> were left sufficiently unspecified.
>--------------------------------------------------------------------------

See the ``latitude'' section above.  As I have no idea at all what you
really have in mind when you say ``OPAQUE-THINGY-POKE!'', I cannot comment
further (but I do appreciate your effort to re-inject some levity into this
discussion).