[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
A (Low-Level) Opaque Object Proposal for R5RS
======================================
A (Low-Level) Opaque Object Proposal
======================================
I proposal the following four procedures be standardized for Scheme and
their names be added to the list of reserved identifiers:
---------------------------------------------------------------------------
[1]. (MAKE-OPAQUE-TYPE . <passkey>)
[2]. ( OPAQUE-UP <opaque-type> <object> . <passkey>)
[3]. ( OPAQUE-DOWN <opaque-object> . <passkey>)
[4]. ( OPAQUE-TYPE <object> )
---------------------------------------------------------------------------
Both MAKE-OPAQUE-TYPE and OPAQUE-UP must be reserved identifiers so that
users cannot re-define them to subvert the abstraction barriers they are
designed to enforce. By contrast, however, OPAQUE-DOWN and OPAQUE-TYPE
need be reserved keywords only so they can be recognized syntactically by
clever compilers to permit potentially more efficient code. If they are
re-bound by a user, no security breach could ensue.)
The formal proposal follows in two pages:
The first page (79 lines) is the proposed addition to the next R^5 Report.
The short (41-line) page after it consists of two explanatory notes
(for possible re-worded inclusion in the Report) accompanied by a
question for discussion by the Authors.
Following that are informal reference matter:
- 1 short (54-line ) page of ``Comments on Possible Implementations''
- 1 page (76 lines) ``Using Opaque Types'' to clarify how one might use them.
- 1 page (74 lines) ``Sample Weak Implementation'' as a toy to play with.
- 2 pages (75+53 lines) showing a sample session with the weak straw-man impl.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Those who categorically oppose any opaque type facility whatsoever should
read the short (24-line) ``Latitude'' subsection of ``Comments on
Possible Implementations'', which offers a possible compromise: giving
implementations enforcement latitude through implementation back doors.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
I would appreciate comments on the strengths, weaknesses, and shortcomings
of this proposal. Its _sole_ purpose is to provide an opaque type/object
facility completely orthogonal from any other language mechanism.
*****************************
*** BEGIN FORMAL PROPOSAL ***
*****************************
=================================================
A (Low-Level) Opaque Object Facility for Scheme
=================================================
-------------------------
I. Opaque Object Creation
-------------------------
[1]. (MAKE-OPAQUE-TYPE . <passkey>)
Returns a predicate (a procedure of one or more arguments) that returns
#T only on objects coerced to this opaque type by a call to OPAQUE-UP
with this predicate as the <opaque-type> argument and with matching
<passkey>, if any was supplied in the call to MAKE-OPAQUE-TYPE.
The resulting ``opaque type'' predicate is not EQ? to any datum except
itself (i.e., it is a ``unique'' object).
------
Note The resulting ``opaque object'' predicate does not require that the
------ number of optional arguments given it match the arity of the call
to MAKE-OPAQUE-TYPE that created it. (It is explained below why.)
--------------------------
II. Opaque Object Coercion
--------------------------
[2]. (OPAQUE-UP <opaque-type> <object> . <passkey>)
Coerces an <object> into an opaque object that satisfies the
<opaque-type> predicate (with matching <passkey>).
The resulting object will not satisfy any type predicate in R4RS Sec.3.4.
(My straw-man prototype below does not satisfy this constraint.)
------
Note If the <opaque-type> was created with a <passkey>, then the
------ <passkey> argument to OPAQUE-UP must match that <passkey>.
Otherwise, the coercion fails and the result is implementation
dependent (e.g., could signal an error or just return #F or some
unique datum indicating an exception).
[3]. (OPAQUE-DOWN <opaque-object> . <passkey>)
Coerces an <opaque-object> (of opaque type <opaque-type>) into the
underlying <object> that was supplied to OPAQUE-UP when it was made
opaque.
------
Note If <opaque-object> is not an opaque object then the result is
------ unspecified.
When <opaque-object> _is_ an opaque object, then it must have been
created by a call to OPAQUE-UP with an <opaque-type> and (optional)
<passkey>. The <passkey> argument to OPAQUE-DOWN must match
that <passkey>.
Otherwise, the coercion fails and the result is implementation
dependent (e.g., could signal an error or just return #F or some
unique datum indicating an exception).
--------------------------
III. Opaque Type Discovery
--------------------------
[4]. (OPAQUE-TYPE <object>)
Returns the <opaque-type> that was used in the call to OPAQUE-UP which
resulted in the <object>.
If <object> was not created by a call to OPAQUE-UP, then it returns
#F (which is not a valid <opaque-type> (since it is not a predicate)).
[Rationale: By returning #F in the non-opaque object case, this subsumes
defining an OPAQUE? type predicate for opaque objects.]
---------------------
IV. Explanatory Notes
---------------------
--------
Note 1 This proposal explicitly does not define what it means for two
-------- <passkey>s to ``match''. For example, the OPAQUE-UP <passkey>
could CONS a per-instance token onto the <opaque-type>'s <passkey>
while still allowing it to ``match'' the <opaque-type> key for
purposes of the coercion up. The OPAQUE-DOWN coercion could then
require this additional per-instance part of the <passkey>, giving
fine-grained control over capability issuance. Generalizing the
notion of passkey matching in this way gives implementations wide
latitude in exploring ideas of ADT subtyping, multiple
inheritance, and multi-layered authentication and certification.
--------
Note 2 This proposal is also intentionally silent about what sort of data
-------- structure a <passkey> is. This is so implementors can experiment
with a variety of data, from simple lists to more interesting
encrypted strings to filenames of encrypted key escrow boondoggles
to user-interactive challenge/response procedures, and so on.
***************************
*** END FORMAL PROPOSAL ***
***************************
----------
Question (MAKE-OPAQUE-TYPE . <passkey>) ==> ``opaque type'' predicate
----------
Should an ``opaque type'' predicate be EQ? to other opaque type
predicates created from an EQ? <passkey>? That is, should opaque
types be hashed on the <passkey> argument(s) when supplied? The
dotted argument for the (optional) <passkey> CONSes a fresh list
with each invocation, but one could hash on the list components
rather than on the list as a whole. Or we could restrict this to a
single optional argument rather than accept numerous optionals as
an aggregate <passkey>. The reason I raise this question is to
address whether reloading a file of MAKE-OPAQUE-TYPE defines
should result in new opaque types being created or not.
....................................
Comments on Possible Implementations
....................................
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.
Gerry and Bill could then run in a system that allows this. Matthias and
Kent could run in a system that does not. To support development of
portable code, an implementation could even supply a toggle flag to
enable/disable the back doors. This is necessarily implementation
dependent, and that is a good thing. It does not belong in the Report.
Under such a diversity, sharing source code would still be possible.
Sharing executables and/or marshalling opaque data and exchanging it
between incompatible systems is already quite _im_possible, no nothing is
lost by giving implementors this latitude. And people worried about
shipping proprietary code to binary compatible sites with unknown opaque
type enforcement could either encrypt the passkeys embedded in their code
on a per-site basis (requiring site registration) or they could adopt some
site certification protocol, or they could require a legally binding
contract to be signed. Whatever.
Implementation Strategies
-------------------------
I can imagine a couple ways this might be implemented. My purpose here is
not to propose any particular implementation strategy. Conceptually, this
is no different really from the distinction between mutable and immutable
values.
And as I mentioned in my earlier post (where I informally proposed that we
separate the opacity issue from other pending proposals)...
Any given opacity implementation could pervade the objects in the system
(marking them with bits) or it could be quite separate (defining a new
aggregate data type that satisfies no existing type predicates, like
PAIR? or VECTOR?). Different Scheme implementors will naturally choose
different strategies, as they should. This is good.
All that said, following is a straw-man, weak (read: not really opaque)
prototype for purposes of grounding the discussion in something concrete.
But first, a short scenario demonstrating how such a low-level opaque type
facility might be used both by opacity liberals and opacity conservatives.
..................
Using Opaque Types - A Tale of Two Schemers (Totally hypothetical scenario)
..................
----
Bill has a data abstraction he'd like to share but he has not decided on
---- what might be the best underlying representation of it. So he decides
to hide the representation for now by defining an opaque type called
<Bill>, with passkey "Bill me later. Rel.0.1". He advertises this passkey
and releases his code for his friends to play with. If he later chooses to
change the underlying representation, he will release it under a different
passkey, along with a transformer that can be used to map old Rel.0.1
<Bill>s into new <Bill97>s (that is, the opaque objects of the opaque
<Bill> type get transformed into instances of the new <Bill97> type).
Bill defines a series of handy abstract accessor and/or mutator procedures
defined to manipulate <Bill>s. Each procedure coerces OPAQUE-DOWN inside
its body to do whatever low-level hacks are called for, then coerces the
result back OPAQUE-UP afterward (if it wants to return a new or altered
<Bill> object). He releases all this code along with his new opaque type
definition.
He is happy in the knowledge that if and when he changes the representation
of these <Bill>s, any outdated datum will be properly flagged and the
coercion can take place on the fly to bring old fasdumped data up to date,
etc. And if anything unexpected turns up, he has at least made the passkey
public so people can craft their own transformers and other tools.
--------
Matthias defines a data abstraction which he wants his compiler to be able
-------- to make some strong representational assumptions about (like one
part of it is always a fixnum and the other part is an immutable list
structure). He freezes the representation and constrains access to
instances of his new data type (so folks can't clobber the immutable part
or violate the type constraint of the fixnum part) by defining an opaque
type called <Mat>, with passkey ``Auto-Mat-ich 451'' which he does not
publicize to anyone except his compiler.
He then defines a series of manipulation procedures for instances of
<Mat>s. Each procedure coerces its <Mat> arguments OPAQUE-DOWN on entry,
manipulates the underlying datum, then coerces back OPAQUE-UP to return
them (if it needs to return a <Mat> instance).
So far this is just like Bill's <Bill>'s, but with a non-public passkey.
But then Matthias takes this a dramatic step further.
He seals each of these manipulation procedures by coercing each of them
OPAQUE-UP as opaque instances of a yet another opaque type, the <Matter>
opaque type (with the passkey ``WhatsaMatter4U?''). The <Matter> opaque
type is for the procedures that manipulate <Mat> opaque objects (just as a
``batter'' is one who bats). This way, if Matthias ever finds himself
typing the <Mat> passkey in his own compiler code, he knows he might be
violating an assumption he wanted his compiler to be able to make about
<Mat> data and the procedures that can manipulate it. By restricting
himself to using only the <Matter> procedures to do that he is secure in
the knowledge that he has prevented himself (or his fellow compiler module
developers) from accidental abstraction violations.
Matthias then happily extends his compiler by teaching it to look for and
recognize <Mat>'s and optimize manipulation of them by teaching it about
the internals and invariants of the <Matter> manipulators, and so on.
His final step is to define trivial wrapper procedures around each <Matter>
procedure that takes no passkey but just coerces the corresponding opaque
<Matter> procedure to the underlying real datum manipulator using the
<Matter> passkey. This way he does not have to bother with typing passkeys
all over his compiler code but he is secure in the knowledge that he is
violating no abstractions of either of the <Mat> data or of the <Matter>
manipulators of <Mat> data. He has built an opacity firewall between
himself and the data/procedure invariants he wishes to encapsulate.
And the compiler can compile out all these up/down coercions as part of what
he taught it about the invariants of <Mat> data and <Matter> procedures.
This makes all these <Mat> and <Matter> ADT's strictly a compile-time fiction
to ensure safe encapsulation of intended data and procedure abstractions.
..........................
Sample Weak Implementation (``weak'' since rep types exposed by REPL)
..........................
;;;
;;; In a _real_ opaque type implementation, the ``kernel-level data
;;; representations'' would be built beneath the level of the programmer's
;;; ability to penetrate the abstraction barrier. For instance, a new data
;;; type disjoint from all others would need to be implemented, called an
;;; ``opaque object''.
;;;
;;; That done, any additional new disjoint unique data types anyone might
;;; ever want could be defined as instances of new opaque types generated
;;; using the facility defined by this proposal.
;;;
(define (MAKE-OPAQUE-TYPE . <passkey> )
(letrec ((<opaque-type>-pred
(lambda (<object> . <<passkey>>)
(and (eq? (opaque-type <object>)
<opaque-type>-pred)
(%passkey-match? <passkey>
<<passkey>>)))))
<opaque-type>-pred))
(define (OPAQUE-UP <opaque-type> <object> . <passkey>)
(let ((attempt (%opaque-object-new <opaque-type> <object>)))
;;
;; Test <passkey> by forging an <opaque-type> UPPER
;;
(if (apply <opaque-type> ; See above weak MAKE-OPAQUE-TYPE
(cons attempt <passkey>))
attempt
(error "OPAQUE-UP: Non-matching <passkey>"
<opaque-type> <passkey>))))
(define (OPAQUE-DOWN <opaque-object> . <passkey>)
(let ((<opaque-type> (opaque-type <opaque-object>)))
(if <opaque-type> ; I.e., this really _is_ an opaque object
(let ((win? (apply <opaque-type>
(cons <opaque-object> <passkey>))))
(if win?
(%opaque-object-datum <opaque-object>)
(error "OPAQUE-DOWN: Non-matching <passkey>"
<opaque-type> <passkey>)))
(error "OPAQUE-DOWN: argument is not an opaque-object"
<opaque-object>))))
(define (OPAQUE-TYPE <object>)
(and (%opaque-object? <object>)
(%opaque-object-type <object>)))
;; 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
..............
Sample Session
..............
;;;----------------------------------------------
;;; Define an opaque type w/ passkey: MOBY FOO
(define <ot> (make-opaque-type 'moby 'foo))
;;;---------------------------------
;;; ``Opaque Types'' are predicates
<ot>
;Value 6: #[compound-procedure 6 <opaque-type>-pred]
(pp <ot>)
(named-lambda (<opaque-type>-pred <object> . <<passkey>>)
(and (eq? (opaque-type <object>) <opaque-type>-pred)
(%passkey-match? <passkey> <<passkey>>)))
;;;---------------------------------------------------------------------
;;; Separate calls to MAKE-OPAQUE-TYPE result in different opaque types
(define <adt> (make-opaque-type 'moby 'foo))
<adt>
;Value 8: #[compound-procedure 8 <opaque-type>-pred]
(eq? <adt> <ot>)
;Value: #f
;;;---------------------------------------------------------------
;;; OPAQUE-UP: ``weak'' abstraction since PRINT exposes the rep.
(define ot-42 (opaque-up <ot> 42 'moby 'foo))
ot-42
;Value 9:
; ((*opaque-object-tag*) #[compound-procedure 6 <opaque-type>-pred] . 42)
(define adt-23 (opaque-up <adt> 23 'moby 'foo))
adt-23
;Value 10:
; ((*opaque-object-tag*) #[compound-procedure 8 <opaque-type>-pred] . 23)
;;;------------------------------------------------------------------------
;;; OPAQUE-OBJECT's opaque types are discriminated by opaque type preds
(<ot> ot-42 'moby 'foo)
;Value: #t
(<ot> ot-42 'wrong-passkey)
;Value: #f
(<ot> 'not-opaque 'moby 'foo)
;Value: #f
(<adt> ot-42 'moby 'foo)
;Value: #f
(<adt> adt-23 'moby 'foo)
;Value: #t
;;;-------------------------------
;;; OPAQUE-UP with wrong pass key
(define nogo (opaque-up <ot> 17 'snark))
;OPAQUE-UP: Non-matching <passkey>
; #[compound-procedure 6 <opaque-type>-pred]
; (snark)
;Quit!
;;;-------------
;;; OPAQUE-DOWN
(opaque-down ot-42 'moby 'foo)
;Value: 42
(opaque-down adt-23 'moby 'foo)
;Value: 23
;;;--------------------------------
;;; OPAQUE-DOWN with wrong passkey
(opaque-down ot-42 'snark)
;OPAQUE-DOWN: Non-matching <passkey>
; #[compound-procedure 6 <opaque-type>-pred]
; (snark)
;Quit!
;;;
;;; OPAQUE-DOWN on a non-opaque datum
(opaque-down "translucent" 'lose)
;OPAQUE-DOWN: argument is not an opaque-object
; "translucent"
;Quit!
;;;-------------
;;; OPAQUE-TYPE
(opaque-type ot-42)
;Value 6: #[compound-procedure 6 <opaque-type>-pred]
(eq? <ot> (opaque-type ot-42))
;Value: #t
(opaque-type adt-23)
;Value 8: #[compound-procedure 8 <opaque-type>-pred]
(eq? <adt> (opaque-type adt-23))
;Value: #t
(eq? <ot> (opaque-type adt-23))
;Value: #f
;;;-----------------------------------
;;; OPAQUE-TYPE of a non-opaque datum
(opaque-type 42)
;Value: #f