headers
Toby Murray | 4 Mar 2009 12:21
Picon
Picon

A Taxonomy of Current Object-Cap Systems

Hi all,

(apologies for cross-posting)

I'm trying to put together a taxonomy of current object-capability
systems. I'm hoping people can help fill in some of the many missing
items in my list so far.

The only criteria for inclusion is that there must be a working /
prototype implementation for the system in existence right now -- i.e.
it must be possible (even if very difficult) for /someone/ to write code
for this system today. Notable omissions therefore include KeyKOS and
(D)CCS (the first object-capability OSes) and Gedanken (the first
object-capability language). 

The list omits caps-as-data systems in which objects can handle the bits
of a cap-as-data directly, such as the E sturdyref part and Webkeys.
Partitioned password-capability systems (like Annex) are, however,
included.

The current systems included in the taxonomy are:
E
Cajita (and other JavaScript subsets)
Joe-E
Emily
CaPerl
Sahara
EROS/CapROS
Coyotos
seL4
(Continue reading)

Permalink | Reply |
headers
Charles Landau | 5 Mar 2009 23:10

Re: A Taxonomy of Current Object-Cap Systems

Toby Murray wrote:
> The current systems included in the taxonomy are:
> EROS/CapROS

EROS and CaPROS are two different systems and should be listed 
separately. The CapROS implementation has diverged significantly from 
EROS, and the design has also to a lesser extent.

Bill Frantz wrote:
> toby.murray@... (Toby Murray) on Wednesday, March 4, 2009 wrote:
> 
>> >Notable omissions therefore include KeyKOS and
>> >(D)CCS (the first object-capability OSes) and Gedanken (the first
>> >object-capability language).
> 
> I believe that a direct descendent of KeyKOS was released by Agorics (RIP)
> under an open source license. Every time I try to give it a name, I get
> told, "Oh no, that's not the name. That name has IP problems."

Whatever the name, it's at http://www.cap-lore.com/CapTheory/KK/Apridos/.
It runs on a computer that's no longer for sale (if it ever was), but if 
someone has one, they could run it.

The S/370 version of KeyKOS will run on a S/370 emulator (there's one 
for the PC). It's proprietary, but the owners of the code could write 
code for it today. I'd argue for its inclusion.
Permalink | Reply |
headers
Toby Murray | 6 Mar 2009 09:45
Picon
Picon

Re: A Taxonomy of Current Object-Cap Systems

On Thu, 2009-03-05 at 14:10 -0800, Charles Landau wrote:
> Toby Murray wrote:
> > The current systems included in the taxonomy are:
> > EROS/CapROS
> 
> EROS and CaPROS are two different systems and should be listed 
> separately. The CapROS implementation has diverged significantly from 
> EROS, and the design has also to a lesser extent.
> 

Thanks for that. Can you tell me whether EROS still runs? Could you also
have a look at the current taxonomy
(http://web.comlab.ox.ac.uk/people/toby.murray/tmp/taxonomy.pdf) and
tell me whether CapROS deviates from EROS in any of the items listed
(which are all defined in bullet points after the table.) Is there some
CapROS documentation I can point to to justify assertions that are made
about it in the table? (Ideally, I'd like to provide a reference to
back-up every claim that it makes for all systems there.)

> Bill Frantz wrote:
> > toby.murray@... (Toby Murray) on Wednesday, March 4, 2009 wrote:
> > 
> >> >Notable omissions therefore include KeyKOS and
> >> >(D)CCS (the first object-capability OSes) and Gedanken (the first
> >> >object-capability language).
> > 
> > I believe that a direct descendent of KeyKOS was released by Agorics (RIP)
> > under an open source license. Every time I try to give it a name, I get
> > told, "Oh no, that's not the name. That name has IP problems."
>
(Continue reading)

Permalink | Reply |
headers
Charles Landau | 7 Mar 2009 04:10

Re: A Taxonomy of Current Object-Cap Systems

Toby Murray wrote:
> On Thu, 2009-03-05 at 14:10 -0800, Charles Landau wrote:
>> EROS and CaPROS are two different systems and should be listed 
>> separately. The CapROS implementation has diverged significantly from 
>> EROS, and the design has also to a lesser extent.
>>
> 
> Thanks for that. Can you tell me whether EROS still runs? 

Jonathan Shapiro would of course be the authority on that, but he has 
been notably absent from this list of late. I believe that when 
development stopped around 2004, it did run, but did not do 
checkpointing or persistence. PC's tend to be backward-compatible so it 
would probably run on today's computers - if not, I have a "boat anchor" 
that would run it. You'd need to get an ancient version of Linux to 
build it, but I believe you *could* run it.

> Could you also
> have a look at the current taxonomy
> (http://web.comlab.ox.ac.uk/people/toby.murray/tmp/taxonomy.pdf) and
> tell me whether CapROS deviates from EROS in any of the items listed
> (which are all defined in bullet points after the table.) 

KeyKOS, EROS, and CapROS all have the same taxonomy.

> Is there some
> CapROS documentation I can point to to justify assertions that are made
> about it in the table? (Ideally, I'd like to provide a reference to
> back-up every claim that it makes for all systems there.)
(Continue reading)

Permalink | Reply |
headers
Bill Frantz | 7 Mar 2009 03:49
Favicon

Re: A Taxonomy of Current Object-Cap Systems

toby.murray@... (Toby Murray) on Friday, March 6, 2009 wrote:

>On Thu, 2009-03-05 at 14:10 -0800, Charles Landau wrote:
>> Toby Murray wrote:
>> > The current systems included in the taxonomy are:
>> > EROS/CapROS
>> 
>> EROS and CaPROS are two different systems and should be listed 
>> separately. The CapROS implementation has diverged significantly from 
>> EROS, and the design has also to a lesser extent.
>> 
>
>Thanks for that. Can you tell me whether EROS still runs? Could you also
>have a look at the current taxonomy
>(http://web.comlab.ox.ac.uk/people/toby.murray/tmp/taxonomy.pdf) and
>tell me whether CapROS deviates from EROS in any of the items listed
>(which are all defined in bullet points after the table.) Is there some
>CapROS documentation I can point to to justify assertions that are made
>about it in the table? (Ideally, I'd like to provide a reference to
>back-up every claim that it makes for all systems there.)

I think the taxonomy is the same for Gnosis, KeyKOS, EROS, and CapROS.

For Gnosis/KeyKOS (two of the many names this system has been marketed
under), see:
<http://www.cis.upenn.edu/~KeyKOS/agorics/KeyKos/Gnosis/keywelcome.html>,
and particularly:
<http://www.cis.upenn.edu/~KeyKOS/agorics/KeyKos/Gnosis/17.html#splx3>.

For CapROS, see: <http://www.capros.org/>
(Continue reading)

Permalink | Reply |
headers
Marcus Brinkmann | 5 Mar 2009 21:53
Picon
Favicon

Re: A Taxonomy of Current Object-Cap Systems

Toby Murray wrote:
> If a systems is missing above that you think should be included, please
> let me know.

Mach

> If you think there are distinctive features any current systems that
> should be included in the list above, please let me know. My main
> criterion for inclusion here is that a feature must affect the way
> object-capability programmers might program in the system and the sorts
> of things that can be expressed in the system. 

Operating systems usually provide low level primitives for interprocess
communication that can then be used to build an object system on top of that.
 In addition, the kernel implements its own objects according to some
conventions.  This makes it difficult to give a single definitive answer, as
kernel-implemented objects can behave significantly different from
user-implemented objects, which also can cover quite a range of behaviour.

A taxonomy for operating systems would thus ask for properties of the IPC
system, and, also important, for properties of the resource management
possibilities.

Well, I can tell you that Mach supports synchronous and asynchronous message
send and receive between threads and provides a full EQ? operation for all
kernel-implemented objects.

Thanks,
Marcus
(Continue reading)

Permalink | Reply |
headers
Toby Murray | 6 Mar 2009 09:53
Picon
Picon

Re: A Taxonomy of Current Object-Cap Systems

On Thu, 2009-03-05 at 21:53 +0100, Marcus Brinkmann wrote:
> Toby Murray wrote:
> > If a systems is missing above that you think should be included, please
> > let me know.
> 
> Mach

I wasn't aware that Mach was object-capability (I'm not trying to imply
that I thought it was otherwise however). Is there documentation or a
paper I can refer to that talks about its current incarnation? 

> Well, I can tell you that Mach supports synchronous and asynchronous message
> send and receive between threads and provides a full EQ? operation for all
> kernel-implemented objects.

Great. Could you elaborate on how the asynchronous sends work? Are they
buffered or best-effort? Mach is unique in providing asynchronous
receives. How do they work? (I can't even imagine -- I really need to do
some more reading.)

Cheers

Toby
Permalink | Reply |
headers
Marcus Brinkmann | 6 Mar 2009 16:37
Picon
Favicon

Re: A Taxonomy of Current Object-Cap Systems

Toby Murray wrote:
> On Thu, 2009-03-05 at 21:53 +0100, Marcus Brinkmann wrote:
>> Toby Murray wrote:
>>> If a systems is missing above that you think should be included, please
>>> let me know.
>> Mach
> 
> I wasn't aware that Mach was object-capability (I'm not trying to imply
> that I thought it was otherwise however). Is there documentation or a
> paper I can refer to that talks about its current incarnation? 

The GNU Mach comes with a texinfo document that documents its interface, but
you can just as well refer to the original documentation:

http://www.cs.cmu.edu/afs/cs/project/mach/public/www/doc/osf.html
http://www.gnu.org/software/hurd/gnumach-doc/index.html

You are in particular looking for:

http://www.gnu.org/software/hurd/gnumach-doc/Inter-Process-Communication.html#Inter-Process-Communication

If you are being picky, there is some ambient authority in Mach: There is a
special system call that allows every thread to get its own thread port (and I
think the task port, too).  That's a special system call, which can be
optimized.  I'd rather see this as an extension of the architectures
instruction set.

>> Well, I can tell you that Mach supports synchronous and asynchronous message
>> send and receive between threads and provides a full EQ? operation for all
>> kernel-implemented objects.
(Continue reading)

Permalink | Reply |
headers
Jed Donnelley | 5 Mar 2009 10:09

Re: [e-lang] A Taxonomy of Current Object-Cap Systems

At 03:21 AM 3/4/2009, Toby Murray wrote:
>..
>The list omits caps-as-data systems in which objects can handle the bits
>of a cap-as-data directly, such as the E sturdyref part and Webkeys.

Just for my curiosity, why did you make the above choice?  It seems
odd to me.  What does the implementation of the capability mechanism
mean to you for the purposes of this taxonomy?

>Partitioned password-capability systems (like Annex) are, however,
>included.

Again, why?  I can of course understand the focus on current systems,
but I'd be interested to know what sort of a functional) a criteria would
be used to chose between capabilities as data systems (e.g. I think
Amoeba fits this criteria and is still available if not actively
supported:

http://en.wikipedia.org/wiki/Amoeba_distributed_operating_system
http://www.cs.vu.nl/pub/amoeba/

) and systems that use capabilities as descriptors, whether
partitioned password-capabilities or otherwise.

Why not simply include all current capability systems?  It seems
to me that such a taxonomy would be considerably more useful and
not much more difficult to put together - e.g. for your thesis.

--Jed  http://www.webstart.com/jed-signature.html
(Continue reading)

Permalink | Reply |
headers
Toby Murray | 5 Mar 2009 10:33
Picon
Picon

Re: [e-lang] A Taxonomy of Current Object-Cap Systems

On Thu, 2009-03-05 at 01:09 -0800, Jed Donnelley wrote:
> At 03:21 AM 3/4/2009, Toby Murray wrote:
> >..
> >The list omits caps-as-data systems in which objects can handle the bits
> >of a cap-as-data directly, such as the E sturdyref part and Webkeys.
> 
> Just for my curiosity, why did you make the above choice?  It seems
> odd to me.  What does the implementation of the capability mechanism
> mean to you for the purposes of this taxonomy?

The choice was in pure self-interest. I expect to include the taxonomy
in an introductory chapter of my thesis at which point I'll be using it
to explain the wide diversity of current object-capability systems,
motivating the reader as to why they should care about this
object-capability idea.

I would be more than happy to include other systems on the list,
however, and then just put a subset of the total list in my thesis. 

> >Partitioned password-capability systems (like Annex) are, however,
> >included.
> 
> Again, why?

Because they are object-capability systems as far as I'm concerned --
Mark Miller might quibble here so perhaps I should limit my comments to
the local (i.e. non-distributed) case in which the entire system shares
a common TCB. That keeps it squarely object-capability.

> Why not simply include all current capability systems?
(Continue reading)

Permalink | Reply |
headers
Bill Frantz | 5 Mar 2009 02:47
Favicon

Re: A Taxonomy of Current Object-Cap Systems

toby.murray@... (Toby Murray) on Wednesday, March 4, 2009 wrote:

>Notable omissions therefore include KeyKOS and
>(D)CCS (the first object-capability OSes) and Gedanken (the first
>object-capability language).

I believe that a direct descendent of KeyKOS was released by Agorics (RIP)
under an open source license. Every time I try to give it a name, I get
told, "Oh no, that's not the name. That name has IP problems."

Perhaps, borrowing from U2, Agorics should be called, "The place where the
systems have no name." :-)

Norm Hardy knows more about it than I do.

Cheers - Bill

-------------------------------------------------------------------------
Bill Frantz        | When it comes to the world     | Periwinkle
(408)356-8506      | around us, is there any choice | 16345 Englewood Ave
www.pwpconsult.com | but to explore? - Lisa Randall | Los Gatos, CA 95032
Permalink | Reply |
headers
Mark Seaborn | 5 Mar 2009 01:06

Re: A Taxonomy of Current Object-Cap Systems

Toby Murray <toby.murray@...> wrote:

> The current features of the taxonomy are the following:
> 
> OS / Language - whether the system is an operating system or programming
> language. e.g. EROS is an OS. E is a language.

Perhaps there should be a third category: protocols.  Plash's
object-capability protocol would fit into that category
(http://plash.beasts.org/wiki/PlashObjectCapabilityProtocol).  It is
OS-based but it is not an OS.

Are you only considering pure capability systems?  Unix file
descriptors, and in particular Unix domain sockets could go on the
list.  The comparison would be useful, considering that sockets are
connection-based (unlike EROS/CapROS/Coyotos and typical
language-based objects) and often not message-based.

> Single-Threaded - whether objects in the system all share a single
> thread of control e.g. E and EROS do not. Joe-E does.

Plash: multiple threads (processes in this case).

> Inter-Thread Sync. Sends - whether the system allows objects running in
> different threads of control to send messages to each other
> synchronously, e.g. E does not, EROS does. This is not applicable for
> Single-Threaded systems.

Plash: yes.  Synchronous call-return is layered on top of a core async
protocol.
(Continue reading)

Permalink | Reply |
headers
Charles Landau | 5 Mar 2009 23:15

Re: A Taxonomy of Current Object-Cap Systems

Mark Seaborn wrote:
> Are you only considering pure capability systems?  Unix file
> descriptors, and in particular Unix domain sockets could go on the
> list.  The comparison would be useful, considering that sockets are
> connection-based (unlike EROS/CapROS/Coyotos and typical
> language-based objects) and often not message-based.

I don't see the distinction. EROS/CapROS/Coyotos capabilities can be to 
objects that represent a session or connection.

Rob Meijer wrote:
> In my view UNIX domain sockets when used for IPC have all the properties
> needed to be considered object capabilities.  IMHO to turn a multi process
> application using UNIX domain sockets for IPC into an object capability
> system, all what is needed is to take away everything that could be
> considered to be ambient authority.

AFAIK it's not possible to send a socket through a pipe. That would 
either disqualify them, or call for another taxon: whether capabilities 
can be sent in messages.
Permalink | Reply |
headers
Mark Seaborn | 7 Mar 2009 12:25

Re: A Taxonomy of Current Object-Cap Systems

Charles Landau <clandau@...> wrote:

> Mark Seaborn wrote:
> > Are you only considering pure capability systems?  Unix file
> > descriptors, and in particular Unix domain sockets could go on the
> > list.  The comparison would be useful, considering that sockets are
> > connection-based (unlike EROS/CapROS/Coyotos and typical
> > language-based objects) and often not message-based.
> 
> I don't see the distinction. EROS/CapROS/Coyotos capabilities can be to 
> objects that represent a session or connection.

But EROS/CapROS/Coyotos objects are not limited to being sessions or
connections.  An object can be shared between processes which can
invoke it concurrently, whereas byte stream connections usually can't
usefully be written to or read from by two processes at the same time.

With Unix domain sockets (the SOCK_STREAM kind), if you want to share
a concurrently-invokable object between two processes, you have to
layer a protocol on top of sockets and arrange for the same object to
be exported across two connections.

Mark
Permalink | Reply |
headers
Mark Miller | 5 Mar 2009 23:24
Picon
Gravatar

Re: A Taxonomy of Current Object-Cap Systems

On Thu, Mar 5, 2009 at 2:15 PM, Charles Landau <clandau@...> wrote:
> Mark Seaborn wrote:
>> Are you only considering pure capability systems?  Unix file
>> descriptors, and in particular Unix domain sockets could go on the
>> list.  The comparison would be useful, considering that sockets are
>> connection-based (unlike EROS/CapROS/Coyotos and typical
>> language-based objects) and often not message-based.
>
> I don't see the distinction. EROS/CapROS/Coyotos capabilities can be to
> objects that represent a session or connection.
>
> Rob Meijer wrote:
>> In my view UNIX domain sockets when used for IPC have all the properties
>> needed to be considered object capabilities.  IMHO to turn a multi process
>> application using UNIX domain sockets for IPC into an object capability
>> system, all what is needed is to take away everything that could be
>> considered to be ambient authority.
>
> AFAIK it's not possible to send a socket through a pipe. That would
> either disqualify them, or call for another taxon: whether capabilities
> can be sent in messages.

If a capability cannot be sent in a message, then the system isn't an
object-capability system. That's why I drew such attention to the
Granovetter diagram.

--

-- 
Text by me above is hereby placed in the public domain

    Cheers,
(Continue reading)

Permalink | Reply |
headers
Toby Murray | 5 Mar 2009 10:51
Picon
Picon

Re: A Taxonomy of Current Object-Cap Systems

On Thu, 2009-03-05 at 00:06 +0000, Mark Seaborn wrote:
> Toby Murray <toby.murray@...> wrote:
> 
> > The current features of the taxonomy are the following:
> > 
> > OS / Language - whether the system is an operating system or programming
> > language. e.g. EROS is an OS. E is a language.
> 
> Perhaps there should be a third category: protocols.  Plash's
> object-capability protocol would fit into that category
> (http://plash.beasts.org/wiki/PlashObjectCapabilityProtocol).  It is
> OS-based but it is not an OS.

Wow, I'd totally forgotten about Plash. Thanks Mark.

Can I ask you a few questions since my memory of Plash is a bit foggy.

Suppose we have a single process running in a plash sandbox. That
process has its own object-capability server that it communicates with
to do anything in the system (open files, fork other processes etc.)

1. If it forks a new process, does the new one share the same server?

2. Do Plash servers ever communicate with each other?

On the assumption that 1. is true and 2. is false, each collection of
server+sandboxed-processes can be considered a single object-capability
system.

In this case, the server is akin to an OS kernel and the chroot'd
(Continue reading)

Permalink | Reply |
headers
Mark Seaborn | 7 Mar 2009 19:37

Re: A Taxonomy of Current Object-Cap Systems

Toby Murray <toby.murray@...> wrote:

> Suppose we have a single process running in a plash sandbox. That
> process has its own object-capability server that it communicates with
> to do anything in the system (open files, fork other processes etc.)
> 
> 1. If it forks a new process, does the new one share the same server?

Yes.

> 2. Do Plash servers ever communicate with each other?

Yes, they can do.  If you use pola-run inside a sandbox, it will
create a new (sandboxed) server process, to serve a process running in
a new sandbox (i.e. a newly-allocated UID).

So you might have three processes:

 A) server process 1 (instance of pola-run) - unsandboxed, normal user's UID
 B) server process 2 (instance of pola-run) - sandboxed, UID X
 C) client process, sandboxed, UID Y

Plash's protocol is a point-to-point protocol and connections must be
set up explicitly.  Suppose the processes have connections set up
between them as follows:

    A
   / \
  B   C
(Continue reading)

Permalink | Reply |
headers
David-Sarah Hopwood | 8 Mar 2009 18:48
Picon

Re: A Taxonomy of Current Object-Cap Systems

Mark Seaborn wrote:
> Plash's protocol is a point-to-point protocol and connections must be
> set up explicitly.  Suppose the processes have connections set up
> between them as follows:
> 
>     A
>    / \
>   B   C
> 
> If A invokes (an object defined by) B, passing a reference to (an
> object defined by) C, it does not automatically create a connection
> between B and C.  C gets A's proxy object, which will forward messages
> to B.
> 
> An alternative topology is
> 
>   A
>    \
>     B
>      \
>       C
> 
> This is not so good because if C creates further nested sandboxes, it
> can result in a longer chain of objects forwarded across connections.
> The first topology, where A acts as a hub, avoids that problem.

Any plans to support reference chain shortening in Plash?

> Toby Murray <toby.murray <at> comlab.ox.ac.uk> wrote:
>> An async senc without async receive might look like:
(Continue reading)

Permalink | Reply |
headers
David-Sarah Hopwood | 9 Mar 2009 10:41
Picon

Re: A Taxonomy of Current Object-Cap Systems [correction]

David-Sarah Hopwood wrote:
>    Causal-order
>                If M1 is sent before M2, and both messages are
>                received, then M1 is received before M2.
> 
>    E-order     References are "forked" when sent between processes/vats.
>                If M1 is sent before M2 on the same reference, or if
>                M1 is sent to a reference R and then M2 is sent to a
>                reference forked (maybe indirectly) from R, and both
>                messages are received, then M1 is received before M2.
>                [E, A4]
> 
>    (Point-to-point) FIFO-order
>                If M1 and M2 are sent by process A to process B, and
>                M1 is sent before M2, and both messages are received,
>                then M1 is received before M2. [Erlang, Waterken]

These definitions are slightly weaker than I intended, because it
should not be possible for only M2 to be received without M1 having
been received.

(In systems that support selective or closed-set receives, or that
support both open and closed receives, a process can be modelled as
having a "mailbox" from which messages are selectively extracted.
"Received" means delivered to the target process mailbox, not
necessarily extracted from the mailbox.)

The corrected definitions are:

     Causal-order
(Continue reading)

Permalink | Reply |
headers
David-Sarah Hopwood | 9 Mar 2009 12:21
Picon

Re: A Taxonomy of Current Object-Cap Systems [correction^2]

David-Sarah Hopwood wrote:
> (In systems that support selective or closed-set receives, or that
> support both open and closed receives,

... and that do not use synchronous-order, ...

> a process can be modelled as
> having a "mailbox" from which messages are selectively extracted.
> "Received" means delivered to the target process mailbox, not
> necessarily extracted from the mailbox.)

--

-- 
David-Sarah Hopwood ⚥

_______________________________________________
cap-talk mailing list
cap-talk <at> mail.eros-os.org
http://www.eros-os.org/mailman/listinfo/cap-talk
Permalink | Reply |
headers
Matej Kosik | 4 Mar 2009 13:48
Picon
Favicon

Re: A Taxonomy of Current Object-Cap Systems

Toby Murray wrote:
> Hi all,
> 
> (apologies for cross-posting)
> 
> I'm trying to put together a taxonomy of current object-capability
> systems. I'm hoping people can help fill in some of the many missing
> items in my list so far.
> 
> The only criteria for inclusion is that there must be a working /
> prototype implementation for the system in existence right now -- i.e.
> it must be possible (even if very difficult) for /someone/ to write code
> for this system today. Notable omissions therefore include KeyKOS and
> (D)CCS (the first object-capability OSes) and Gedanken (the first
> object-capability language). 
> 
> The list omits caps-as-data systems in which objects can handle the bits
> of a cap-as-data directly, such as the E sturdyref part and Webkeys.
> Partitioned password-capability systems (like Annex) are, however,
> included.
> 
> The current systems included in the taxonomy are:
> E
> Cajita (and other JavaScript subsets)
> Joe-E
> Emily
> CaPerl
> Sahara
> EROS/CapROS
> Coyotos
(Continue reading)

Permalink | Reply |
headers
Toby Murray | 4 Mar 2009 18:01
Picon
Picon

Tamed Pict (was: Re: A Taxonomy of Current Object-Cap Systems)

On Wed, 2009-03-04 at 13:48 +0100, Matej Kosik wrote:
> Very short description of relationship among Pict, Tamed Pict, Sahara
> can be found here:
> http://altair.sk/uploads/tmp/introduction.pdf
> Relevant text starts at page 4. The paragraph above the figure.
> 
> Pict is finished.
> Tamed Pict is finished.
> Sahara is finished.

That's awesome. I can't wait to read the rest of your thesis. 

In the meantime, could you clarify a few things for me about Tamed Pict.

Processes in Tamed Pict run concurrently. Hence it is multi-threaded.

Sending of messages between processes in Tamed Pict is nominally
asynchronous because it is so in Pict -- quoting from Pierce and
Turner's "Pict: A Programming Language Based on the pi-Calculus":
"We allow only asynchronous output in Pict; this amounts to restricting
the 'continuation' of each output expression to the null process."

(I say nominally because the reduction semantics would still be
synchronous, but the programmer is forced to make all outputs happen in
parallel with, and therefore asynchronously to, whatever else the object
might be doing, due to the restriction that only the null behaviour can
follow an output.)

Tamed Pict has no nominally synchronous communication primitives because
Pict doesn't.
(Continue reading)

Permalink | Reply |
headers
Matej Kosik | 4 Mar 2009 19:10
Picon
Favicon

Re: Tamed Pict

Toby Murray wrote:
> On Wed, 2009-03-04 at 13:48 +0100, Matej Kosik wrote:
>> Very short description of relationship among Pict, Tamed Pict, Sahara
>> can be found here:
>> http://altair.sk/uploads/tmp/introduction.pdf
>> Relevant text starts at page 4. The paragraph above the figure.
>>
>> Pict is finished.
>> Tamed Pict is finished.
>> Sahara is finished.
> 
> That's awesome. I can't wait to read the rest of your thesis. 
> 
> In the meantime, could you clarify a few things for me about Tamed Pict.
> 
> Processes in Tamed Pict run concurrently. Hence it is multi-threaded.

The original Pict has a construct for inlining arbitrary C code, so what
can you do in C (spawning native threads or separate processes) can be
done also in Pict. That ability to inline arbitrary C code is very
useful, although using of `fork' syscall is not necessary because Pict
supports also "green threads" or "green processes"
http://en.wikipedia.org/wiki/Green_threads
For many purposes this is sufficient concurrency mechanism.
(the term "green process" was probably introduced by Erlang folk to
stress certain difference of their language over other languages that
support green threads).

> 
> Sending of messages between processes in Tamed Pict is nominally
(Continue reading)

Permalink | Reply |
headers
Toby Murray | 4 Mar 2009 19:32
Picon
Picon

Recursive Reentrant Invocation (was: Re: Tamed Pict)

On Wed, 2009-03-04 at 19:10 +0100, Matej Kosik wrote:
> Toby Murray wrote:
> > I need to think harder to work out whether Pict's derived forms for
> > recursive functions allow you to write recursively reentrant code (see
> > http://mail.eros-os.org/pipermail/e-lang/2009-February/013002.html for
> > more on what I mean here).
> 
> I cannot give you sure answer because I do not exactly understand what
> problem you discussed there. In this paragraph:
> 
> "The thing that both of these attacks had in common was that they
> exploited reentrancy-via-recursion. In both cases, an object, o,
> implementing some abstraction must maintain some invariant. o must also
> call some untrusted code. While calling the untrusted code, o can be
> invoked recursively. This reentrant invocation of o causes its internal
> invariants to be broken."
> 
> What do you mean by "While calling the untrusted code, o can be
> invoked recursively." ? What do you mean by "recursively"? Who could
> invoke object o "recursively"?

Thinking just in terms of E (although hopefully it will translate easily
to other languages too), let's say have an object o defined as follows.

def o {

   to foo(obj) {
       obj.bar()
   }
   to baz() {
(Continue reading)

Permalink | Reply |
headers
Matej Kosik | 4 Mar 2009 21:51
Picon
Favicon

Re: Recursive Reentrant Invocation

Toby Murray wrote:
> On Wed, 2009-03-04 at 19:10 +0100, Matej Kosik wrote:
>> Toby Murray wrote:
>>> I need to think harder to work out whether Pict's derived forms for
>>> recursive functions allow you to write recursively reentrant code (see
>>> http://mail.eros-os.org/pipermail/e-lang/2009-February/013002.html for
>>> more on what I mean here).
>> I cannot give you sure answer because I do not exactly understand what
>> problem you discussed there. In this paragraph:
>>
>> "The thing that both of these attacks had in common was that they
>> exploited reentrancy-via-recursion. In both cases, an object, o,
>> implementing some abstraction must maintain some invariant. o must also
>> call some untrusted code. While calling the untrusted code, o can be
>> invoked recursively. This reentrant invocation of o causes its internal
>> invariants to be broken."
>>
>> What do you mean by "While calling the untrusted code, o can be
>> invoked recursively." ? What do you mean by "recursively"? Who could
>> invoke object o "recursively"?
> 
> Thinking just in terms of E (although hopefully it will translate easily
> to other languages too), let's say have an object o defined as follows.
> 
> def o {
> 
>    to foo(obj) {
>        obj.bar()
>    }
>    to baz() {
(Continue reading)

Permalink | Reply |

Gmane