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

Re: New types; also opacity without passkeys [portable R4RS impl]

Aubrey Jaffer writes:
>  From: Michael R. Blair <ziggy@martigny.ai.mit.edu>
>  Date: Wed, 22 May 96 21:39:58 EDT
>  Will Clinger writes in his proposal:
>  >---------------------------------------------------------------------------
>  > Although this proposal does not explicitly require any opacity,
>  > the requirement that the predicate P? returns #T if and only if
>  > its argument was created by a call to U cannot be implemented
>  > without some kind of opacity.  In particular, this proposal
>  > cannot be implemented in R4RS Scheme.
>  >---------------------------------------------------------------------------
>    Yes, it can.  Following is a portable R4RS implementation that I have
>    tested in both MIT Scheme and Scheme 48.  It relies _only_ on the
>    opacity of LAMBDA closures.
> I think Will meant that this condition could not be satisfied
> simultaneously with new-types being distinct from R4RS-defined types.

It is possible that Will has this in mind, but there is no mention of
the R4RS-defined type predicates from Sec.3.4 in his ``new types'' proposal.
I thought this was intentional on his part so as not to force the issue of
type disjointness w.r.t. system types (like PAIR?).

To wit, merely abstractly axiomatizing the mutual disjointness of
predicates returned by GET-NEW-PREDICATE (using his nomenclature, P?) as he
has done does not address their disjointness from the predicates in Sec.3.4
(like PAIR?). I thought that was intentional on his part, but if this _was_
what he was thinking about in claiming that his proposal could not be
implemented in R4RS then his proposal needs to add some language to bring
in that issue, at which point I would concur that his proposal cannot be
implemented in R4RS Scheme.

Was this what you had in mind then, Will?

For example, the opaque object proposal I had offered included this:

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

and the ``weak'' prototype was prefaced with:

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

As the ``new types'' proposal currently stands, no mention is made of
disjointness w.r.t. the type predicates of Sec.3.4 so this is not an issue
in that proposal...  unless I've overlooked something (very) subtle.  For
that reason, the ``new types'' proposal offers no new mechanism that could
not be implemented as a compliant, portable R4RS library module, as I
demonstrated.  So that proposal serves _only_ to standardize the names,
interface and minimal behavior of four new procedures:


    (GET-NEW-SELECTOR <type>), and
    (GET-NEW-PREDICATE <type>)

I think this is a fine thing and I would not oppose their inclusion in the
R5RS for that reason, although I do suggest to re-name MAKE-NEW-TYPE to
MAKE-NEW-TYPE-DESCRIPTOR just to highlight the fact that no new
disjointness w.r.t. the system-defined type predicates of Sec.3.4 is
implied nor should be assumed.

At the same token, however, since the ``new type'' proposal offers no
portable, guaranteed disjointness from _system_ types (like PAIR?), it does
not address one important motivation behind my OPAQUE-OBJECT proposal.  The
OPAQUE-OBJECT proposal, therefore, still stands.

> Continuing your transcript session:
> (pair? <object>)
> ;Value: #t
> I also tried to write such a program using only procedure opacity and
> convinced myself that there was no way to redefine PAIR? or PROCEDURE?
> so that new-types were disjoint from R4RS types while preserving
> opacity.


 (define sys:pair? pair?)  ; Globally capture system PAIR?
 (define pair?    'TBA)    ; Global hook for opaquely redefining below

 (define make-new-type
   (let* ((*UID-counter* 0)       ; Global counter so each <type> unique

          ;; Some kernel level data abstractions for U'd data
          (*U-tag*    (list 'U-tag))

          (%U-tag     (lambda (x) (cons *U-tag* x)))
          (%U-tagged? (lambda (x) (and (pair? x) (eq? (car x) *U-tag*))))
          (%U-untag   (lambda (U-tagged-obj) (cdr U-tagged-obj)))

          (sys:pair?  sys:pair?)  ; Locally capture system PAIR? at def'n time

     (set! pair? (lambda (x)      ; Opaque re-definition of global PAIR?
                   (and (sys:pair? x)
                        (not (eq? (car x) *U-tag*)))))
     (lambda ()



This gets you about as far as you can go in portable R4RS and IEEE Scheme,
but other procedures (user- and system-defined) which precede this could
have also locally captured the system default PAIR?, so how pervasive this
forged disjointness will be is a function of the environment pending at the
time the MAKE-NEW-TYPE is loaded/defined.  For example, the system default
LIST? may have locally captured the system global PAIR? at its (system)
definition point, so (LIST? (MAKE-NEW-TYPE)) might legitimately still
return #T.  Note, on the other hand, that LIST? is pointedly _not_ in the
list of assured mutually disjoint R4RS type predicates of Sec.3.4.

This, of course, is precisely the motivation in explicitly proposing a
distinct mechanism for generating new disjoint types (and for creating
objects with those types).  My OPAQUE-OBJECT proposal subsumed such a
mechanism.  Will's ``new type'' proposal does not, as presently worded.

Finally, SYS:PAIR? could be better anchored in the true R4RS system
defaults by using (EVAL 'PAIR? (SCHEME-REPORT-ENVIRONMENT)), which was
approved for R5RS nearly four years ago [1] but which has not appeared in
print in an R4.9RS or any other working draft that I am aware of.  Again,
however, there is no mechanism I know of to force the new U-tag sensitive
PAIR? to replace global PAIR? pervasively (since the environment specifier
returned by (SCHEME-REPORT-ENVIRONMENT) can be immutable).  This is a
feature.  And, again, this is why a separate ``disjoint type'' generation
mechanism is necessary.


[1] Date: Fri, 9 Oct 92 14:57:51 -0700
    From: William Clinger <will@skinner.cs.uoregon.edu>
    Message-Id: <9210092157.AA24693@skinner.cs.uoregon.edu>
    To: rrrs-authors@ai.mit.edu
    Subject: draft minutes of June 1992 meeting

           Draft Minutes of the RnRS Authors meeting
                        25 June 1992
                         Xerox PARC
            recorded and edited by William Clinger