#:authentic

[Matthew Flatt]

There are many structure types that are private to some library (such
as the expander) and will never have impersonators. The compiler can't
know that, though, and the possibility of an impersonator means that
the structure type's predicate has to be twice as expensive. Field
selection is also more expensive in certain cases. I'm not sure about
the current Racket VM, but the cost is measurable when running the
Racket expander on Chez Scheme.

So, I'm thinking of adding a `prop:authentic` structure type property
--- with an `#:authentic` shorthand for `struct` --- that prevents
instances of a structure type from being impersonated or chaperoned.
Naturally, an authentic structure type's supertype and subtypes must
also be authentic.

Any opinions?

[Jay McCarthy]

This means that trying to contract them will fail or that it will default back to just protecting the underlying functions?

Jay

--
You received this message because you are subscribed to the Google Groups "Racket Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-dev+...@googlegroups.com.
To post to this group, send email to racke...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/59148060.14da620a.a334b.158bSMTPIN_ADDED_MISSING%40gmr-mx.google.com.
For more options, visit https://groups.google.com/d/optout.

--

-=[     Jay McCarthy               http://jeapostrophe.github.io    ]=-

-=[ Associate Professor        PLT @ CS @ UMass Lowell     ]=-

-=[ Moses 1:33: And worlds without number have I created; ]=-

[Matthew Flatt]

Using `struct/c` or `struct/dc` would work only with flat contracts for
the fields.

[Scott Moore]

Out of curiosity, where does the additional overhead come from? Without looking at the struct predicate code, I would have expected this to be a relatively-well predicted branch on the Scheme_Type of the object. I haven’t been following the Chez port though—are impersonators being implemented at a higher level of abstraction?

That aside, I don’t think there is too much lost from doing this—as you mention, it was already possible to create structs that could not be easily impersonated. 

There are some edge cases this would change though, where you use the program structure to make sure you have the right inspector around. For something like the expander, that’s probably not an issue, as the expander will be running before the program has a chance to intervene.

I think the main danger would be if it was abused for the performance benefit in libraries where a client might reasonably want to interpose...

[Matthew Flatt]

It's not a level-of-abstraction difference. A predicate use

(s? o)

is compiled as

(or (authentic-s? o) (and (impersonator? o)
(authentic-s? (impersonator-original o))))

where `authentic-s?` and `impersonator?` are a type-tag tests. I agree
that the extra `impersonator?` test should be well predicted, but it
still has a measurable cost in the one program I tied. I don't know
whether the cost is due to the branch or just the extra code involved.


I agree that generally don't want performance declarations that
interfere with reasonable interposition. The good uses of `#:authentic`
would be in places where the struct representation of a value is not
exposed or where the values themselves are not exposed (so any
interposition means being on the "inside" where you can change the
code, anyway).

[Scott Moore]

I agree that generally don't want performance declarations that
interfere with reasonable interposition. The good uses of `#:authentic`
would be in places where the struct representation of a value is not
exposed or where the values themselves are not exposed (so any
interposition means being on the "inside" where you can change the
code, anyway).

Yes, I agree with this. I think as far as how this changes Racket’s data abstraction model, the key is “where the values themselves are not exposed.”

#:authentic only has an interesting effect in the other case, where “outside” code gets its hands on a value of the struct type. Previously, I could write a program that used inspectors to impersonate this value regardless of the “inside” code’s intent. Now that would no longer be possible.

I doubt there is much code that currently relies on being able to do this and so I would say go ahead. (Perhaps DrRacket or other debugging tools?)

On the other hand, Spencer already asked if this would be something the optimization coach would recommend. I think it would be important for the documentation of #:authentic or the implementation of such a coach to stress the importance of the rules of thumb you just laid out.

[Matthias Felleisen]

@ Christos

#:authentic explicitly introduces a channel of communication that it is not protectable by contracts. This makes Racket’s contract system explicitly incomplete. It might have been incomplete in the past for other reasons.

If the name isn’t fixed, #:no-proxy-allowed would be my preference.

— Matthias

> --
> You received this message because you are subscribed to the Google Groups "Racket Developers" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-dev+...@googlegroups.com.
> To post to this group, send email to racke...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/3c430798-e93a-4900-8215-198f77d9b991%40Spark.

[Robby Findler]

What if #:authentic (or whatever) were only allowed on immutable
objects and we allowed them to be copied? Then contracts could protect
them.

Robby

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/D688771A-C477-40D8-B209-D9506362C5CB%40ccs.neu.edu.

[Robby Findler]

Indeed: if we did that, then these structs would be much like cons
cells currently are.

Robby

[Matthias Felleisen]

Yes except that you can contract cons cells. So why couldn’t you contract authentic structs then?

[Robby Findler]

They would be the same. We currently cannot chaperone or impersonate cons cells. We copy them. 

Robby

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/1AFE0571-C48C-4B22-B445-D96B283C6885%40ccs.neu.edu.

[Matthias Felleisen]

Oh right.

[Matthew Flatt]

I think a better analogy is to values like #<thread>, #<input-port>, or
#<regexp>. Although those kinds of values are implemented with structs,
the accessor and mutator functions are not exported (and, as Scott
says, there's no way to get the accessors and mutations by reflection),
so there's no way to impersonate the values. In general, it's up to the
implementation of a new kind of value to supply impersonator/chaperone
support for those values, and implementations usually don't.

> https://groups.google.com/d/msgid/racket-dev/1AFE0571-C48C-4B22-B445-D96B283C68
> 85%40ccs.neu.edu.

> > For more options, visit https://groups.google.com/d/optout.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Racket Developers" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to racket-dev+...@googlegroups.com.
> To post to this group, send email to racke...@googlegroups.com.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/racket-dev/77B4F4BC-74B9-4838-AFC1-B65BCF8BE6
> 95%40ccs.neu.edu.

[Robby Findler]

This perspective suggests a gap in the design in some sense, I would
say. The PL construct cannot, on its own, guarantee that the values
from #:authentic structs end up behaving like those kinds of values.

(also: threads and regexps don't seem problematic from the contract
perspective, but ports do, since they are a communication channel and
the others aren't.)

Robby

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/5915b006.5639620a.b51d4.83dcSMTPIN_ADDED_MISSING%40gmr-mx.google.com.

[Matthew Flatt]

At Thu, 11 May 2017 18:38:00 -0400, Matthias Felleisen wrote:
> If the name isn’t fixed, #:no-proxy-allowed would be my preference.

We haven't been using the word "proxy" in this context, but I can see
why you'd want something that more clearly connects to
"impersonator"/"chaperone" terminology. (I haven't been sure that
disallowing impersonators/chaperones would be the only implication of
the property, but that seems to be the case, so far.)

Also, I'd prefer an adjective, but `#:nonimpersonatable` is awkward.

Any other suggestions?

[Matthias Felleisen]

#:non-chaperoned #:adult :(

> --
> You received this message because you are subscribed to the Google Groups "Racket Developers" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-dev+...@googlegroups.com.
> To post to this group, send email to racke...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/5915b5a2.c68d620a.c7f2.7b01SMTPIN_ADDED_MISSING%40gmr-mx.google.com.

[Matthias Felleisen]

I tend to agree though there is some information flowing from a thread to its context (thread CML events). I have to think whether this is a channel of communication.

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/CAL3TdOPTT8-8CuJt86VE-_z%3DnZ%2B-Hxf92HyNW%3DvUtiVy9-5yAg%40mail.gmail.com.

[Robby Findler]

I would say that the event value is the channel of communication. But,
if this expression:

(sync (thread (lambda () 3)))

returned 3, then I'd say that thread itself is a channel of
communication. But threads give themselves back to sync, not the
values that their thunks return.

Robby

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/752ED434-8FB1-4F9A-89C2-153070098FF8%40ccs.neu.edu.

[Scott Moore]

(define (component-1 value)

  (define t

    (thread (lambda ()

              (thread-suspend t)

              (for ([i (in-range value)])

                (thread-suspend t)))))

  t)

(define (component-2 thread)

  (thread-resume thread)

  (let* ([suspend-evt (thread-suspend-evt thread)]

         [dead-evt (thread-dead-evt thread)]

         [result (sync suspend-evt dead-evt)])

    (if (eq? result dead-evt)

        0

        (add1 (component-2 thread)))))

> (define t (component-1 2))

> (component-2 t)

2

> (define t (component-1 5))

> (component-2 t)

5

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/CAL3TdOOm1sH2GxLqn1ZtG49XUwSa_A2Pvo2Wp09Uzuw-zzL1zw%40mail.gmail.com.

[Scott Moore]

I think the interesting distinction is that threads, regexps, ports, etc, are communication channels, but not for higher-order values.

[Matthias Felleisen]

What your (cool little) program demonstrates is that *information* can flow from one thread to another, not *data*. You need to convince me that data flows and then we need to figure out how to protect/monitor this data. And at that point, you can possibly see lambdas flow too.

[Matthew Flatt]

Here's an implementation to try:

https://github.com/racket/racket/pull/1689

So far, I like "authentic" better than the alternatives, so the PR uses
that term.

If you try something like

(struct posn (x y))

(time
(let ([p (posn 1 -1)])
(for/fold ([n 0]) ([i (in-range 100000000)])
(+ (+ n (posn-x p)) (posn-y p)))))

then the difference with `#:authentic` is in the noise. But with an
example that involves more code, as below, then you can see a 5-10%
overall effect (even though the number of relevant field accesses is
the same).

----------------------------------------

#lang racket/base
(require (for-syntax racket/base))

(struct posn (x y)
#:authentic)

(define-syntax (dispatch stx)
(syntax-case stx ()
[(_ e body)
(let ([bits 5]) ; <- determines amount of code
(with-syntax ([(c ...) (for/list ([i (expt 2 bits)])
i)]
[mask (sub1 (expt 2 bits))])
#'(case (bitwise-and e mask)
[(c) body] ...)))]))

(time
(let ([p (posn 1 -1)])
(for/fold ([n 0]) ([i (in-range 100000000)])
(dispatch
i
(+ (+ n (posn-x p)) (posn-y p))))))

[Robby Findler]

Yes, I agree with this analysis of Scott's very cool program. I also
think that this means that maybe we should not be using the phrase
"channel of communication" (or, perhaps, we should treat it as an
abbreviation of some longer phrase and we need to work out what it is
exactly). I think Scott's on to something with the interesting
distinction comment. If I am communicating only flat values around,
then I have to run an interpreter to evaluate some arbitrary unknown
program; it doesn't run directly. That seems like an important
distinction somehow, even if it isn't a very crisp one.

Robby

On Fri, May 12, 2017 at 10:06 AM, Matthias Felleisen

[Scott Moore]

Reading a bit further in the docs, there is a bigger hole:

(define (component-1 value channel)

  (thread-send channel value))

(define-values (component-2 channel)

  (let ()

    (define main (current-thread))

    (define th

      (thread (lambda () (thread-send main (thread-receive)))))

    (values (lambda () (thread-receive)) th)))

> (component-1 (lambda () "hello world") channel)

> ((component-2))

"hello world"

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/575116A1-A4C1-4548-92B0-C06008276A6F%40ccs.neu.edu.

[Robby Findler]

Yeah, that's a real one. :)

Robby

> https://groups.google.com/d/msgid/racket-dev/b3e1d2fb-c559-4015-80b4-d15a016edeb4%40Spark.

[Scott Moore]

Yes, in my thinking this is about the relationship between “complete monitoring” and “capability safety,” but I will have to think longer before I can put my finger on exactly why it matters…

As far as complete monitoring goes, I think the justification for dropping boundaries around flat values once they’ve been checked is that at the boundary, you’ve had the opportunity to check any property you wanted. Interestingly, this reasoning does not provide a justification for un-monitored channels that only transmit flat values. For example, it would still lead you to reject the ports interface, which can only communicate bytes, but doesn’t let you check the property that the sequence of bytes received has a particular pattern, or is a valid racket program, etc. The lack of chaperones doesn’t seem to bad here though, as I imagine you can use a custom port to implement some sort of proxy (modulo issues with equals? etc…).

(Note, I think my original thread program is somewhat similar, though the ‘data’ is a slightly more abstract stream of bits…)

PS- I agree with Matthias---I have no objection about #:authentic. Just an interesting topic of discussion.

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/CAL3TdOP7TE7o7jPxy64ZP0weOEjnzbsiz3_KMDiS_rNt_Y0Lhw%40mail.gmail.com.

[Matthias Felleisen]

> On May 12, 2017, at 11:30 AM, Robby Findler <ro...@eecs.northwestern.edu> wrote:
>
> Yes, I agree with this analysis of Scott's very cool program. I also
> think that this means that maybe we should not be using the phrase
> "channel of communication" (or, perhaps, we should treat it as an
> abbreviation of some longer phrase and we need to work out what it is
> exactly

We did. See Christos’s 2012 ESOP paper:

http://www.ccs.neu.edu/racket/pubs/#esop12-dthf

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/CAL3TdOP7TE7o7jPxy64ZP0weOEjnzbsiz3_KMDiS_rNt_Y0Lhw%40mail.gmail.com.

[Matthias Felleisen]

I cannot turn this one into a problem with Typed Racket though. th must have type Thread and the -> Any of thread-receive requires a cast already, which covers our ‘soundness’ behind.

[Gustavo Massaccesi]

Somewhat related ...

I always thought it was strange that mutable pairs can’t be
chaperoned, but boxes and vectors of length 2 can. Moreover, there was
(is?) a plan to replace the implementation of mcons with structs. Does
#:authentic make this more consistent / efficient?

Also, what would happen in an alternative word where all the structs
were #:authentic by default and chaperones/impersonators must be
explicitly allowed with some keyword like #:chaperonable?

Gustavo

[Matthew Flatt]

At Fri, 12 May 2017 13:38:44 -0300, Gustavo Massaccesi wrote:
> I always thought it was strange that mutable pairs can’t be
> chaperoned, but boxes and vectors of length 2 can. Moreover, there was
> (is?) a plan to replace the implementation of mcons with structs. Does
> #:authentic make this more consistent / efficient?

Yes: with `#:authentic`, mutable pairs could be implemented as structs
and continue to be uncooperative while avoiding an extra check in
`mpair?`. (I think we'd more likely want to take advantage of structs
to get chaperones for mutable pairs, though.)

> Also, what would happen in an alternative word where all the structs
> were #:authentic by default and chaperones/impersonators must be
> explicitly allowed with some keyword like #:chaperonable?

The author of a library that exposes a structure type would have to
think harder about whether chaperones/impersonators should be allowed
--- which I think would mean almost always remembering to add
`#:chaperonable`.

It's awkward to need `#:authentic` in one context or `#:chaperonable`
in the other, but favoring cooperation via chaperones (and therefore
contracts) seems like a better default to me.

[Sam Tobin-Hochstadt]

The problem with Typed Racket would come from sending a higher order value to an untyped thread. I'm pretty sure you could get unsoundness there.

On Fri, May 12, 2017, 12:00 PM Matthias Felleisen <matt...@ccs.neu.edu> wrote:

I cannot turn this one into a problem with Typed Racket though. th must have type Thread and the -> Any of thread-receive requires a cast already, which covers our ‘soundness’ behind.

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/C8683D03-E19C-414E-9710-C79D350452F4%40ccs.neu.edu.

[Scott Moore]

Can confirm. ;)

[Matthias Felleisen]

Ouch. (I should have thought of this.)

So we need proxies for channels.

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/b7b5d049-87ed-438c-b825-4269f157adda%40Spark.

[Sam Tobin-Hochstadt]

We have proxies for channels, but not for threads.

On Fri, May 12, 2017, 1:25 PM Matthias Felleisen <matt...@ccs.neu.edu> wrote:

Ouch. (I should have thought of this.)

So we need proxies for channels.




> On May 12, 2017, at 1:21 PM, Scott Moore <sc...@thinkmoore.net> wrote:
>

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/b7b5d049-87ed-438c-b825-4269f157adda%40Spark.

[Matthias Felleisen]

I should have written thread-channels. (I did try regular channels, and I found the types and proxies.)

[Sam Tobin-Hochstadt]

Unfortunately they aren't a separate data type, so the proxy has to be on the thread.

On Fri, May 12, 2017, 1:28 PM Matthias Felleisen <matt...@ccs.neu.edu> wrote:

I should have written thread-channels. (I did try regular channels, and I found the types and proxies.)


> On May 12, 2017, at 1:27 PM, Sam Tobin-Hochstadt <sa...@cs.indiana.edu> wrote:
>

[Matthias Felleisen]

That’s what the (mail) thread started with. See below.

[Asumu Takikawa]

On 2017-05-12 17:30:26 +0000, Sam Tobin-Hochstadt wrote:
> Unfortunately they aren't a separate data type, so the proxy has to be on
> the thread.

JFYI, there is a bug # for the soundness issue with thread mailboxes:

http://bugs.racket-lang.org/query/?cmd=view audit-trail&database=default&pr=13589

Cheers,
Asumu

[Matthias Felleisen]

Oh Sam was supposed to move the Gnats issues into Github issues. Cool.