I often see casual mention that the Hewit/Agha Actor Model is equivalent in capability to process algebra, like CSP, CCS and ACP. Ie, one can be implemented in the other. Is there a paper that actually contains the proof of this? I'm specifically looking for a citable reference.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
This question is too vague to admit a clearcut answer, but it points towards a fascinating research field. The key problem is that neither is the actor model formally well-defined, nor is the notion of equivalency between (formalised) models of computation clear. Defining what expressivity of programming languages means precisely is a wide open problem, particularly for models of concurrent computation. It's unlikely that there is one clearcut notion of expressivity. Instead, language expressivity would appear to be parametric in properties of interest. Joachim Parrow's paper Expressiveness of Process Algebras gives an overview of the problem area, and explains some approaches that have been used to tackle it. There's even an annual conference -- Express -- dedicated to this question.
Process calculi such as CCS, CSP or π-calculi were developed in parts to offer a formalisation of actors, but are themselves of varying expressivity w.r.t. various elaborations of the latter concept. Even seemingly small variations in the operations a process calculus offers leads to huge expressivity gaps w.r.t. various notions of expressivity.
answered Jul 27, 2011 at 9:57
-
$\begingroup$ Specifically what I'm looking for is can one be implemented in the other? And if so, is there a paper with the proof? (I'm not concerned with expressiveness because of the inexact meaning of that.) $\endgroup$ Jul 27, 2011 at 14:03
-
$\begingroup$ I think it would be useful if you spelt out what you mean by 'implemented'. $\endgroup$– Vijay DJul 28, 2011 at 10:15
-
2$\begingroup$ Chris, the 'curse' of the Church-Turing thesis means that you can implement actors as cellular automata, or in Fortran. The study of expressivity starts with the realisation that implementability according to the Church-Turing thesis is too coarse a criterion for equivalency of programming languages. Theoretical musings aside, I suggest that the asynchronous pi-calculus is a good starting point if you are interested in formal models of actors. $\endgroup$ Jul 28, 2011 at 11:17
-
$\begingroup$ @Martin I think I see what you mean. From Parrow's paper, since there are numerous ways to interpret semantic preservation, so as long as a transition system is Turing-complete, we've pretty much hit the end of our investigation of equivalence. Am I getting that right? $\endgroup$ Jul 28, 2011 at 14:37
-
2$\begingroup$ I'd stay it's the other way round: as programmers we know that some kinds software is more easily written and maintained in some languages than others (e.g. garbage collected vs manual memory management, message-passing vs shared memory), as language implementors, we know that some features are more easily implemented than others (e.g. resumable vs 'normal' exceptions, or asynchronous vs synchronous message passing, or atomic broadcast in distributed systems). The study of expressivity seeks to work out in detail what makes a language feature expressive, and what makes it hard to implement. $\endgroup$ Jul 28, 2011 at 15:13