lf-lang / lingua-franca

Intuitive concurrent programming in any language
https://www.lf-lang.org
Other
235 stars 63 forks source link

Related work #1

Closed lhstrh closed 5 years ago

lhstrh commented 5 years ago

Other actor frameworks can be mentioned in the introduction. That's where we can immediately distinguish our approach as a segue into a description of what our definitions are. In the relation work section, we need to compare ourselves to other programming languages that incorporate timing specs...

MarjanSirjani commented 5 years ago

Timed Actors are few. There are the old ones that inspired us. I copied the following from http://rebeca-lang.org/assets/papers/2014/Modelling%20and%20simulation%20of%20asynchronous%20real-time%20systems%20using%20Timed%20Rebeca.pdf

RT-synchronizer A real-time actor model: RT-synchronizer, is proposed in [16], where a centralized synchronizer is responsible for enforcing real-time relations between events. Actors are extended with timing assumptions, and the functional behaviours of actors and the timing constraints on patterns of actor invocation are separated. The semantics for the timed actor-based language is given in [17]. Two positive real-valued constants, called release time and deadline, are added to the send statement and are considered as the earliest and latest time when the message can be invoked relative to the time that the method executing the send is invoked. In Timed Rebeca, we have the constructs after and deadline, which are representing the same concepts, respectively, except that they are relative to the time that the message (itself) is sent. So, it more directly reflects the computation architecture including the network delays. In our language, it is also possible to consider a time delay in the execution of a computation where in [17] it is possible to specify an upper bound on the execution time of a method. While RT-synchronizer is an abstraction mechanism for the declarative specification of timing constraints over groups of actors, our model allows us to work at a lower level of abstraction. Using Timed Rebeca, a modeller can easily capture the functional features of a system, together with the timing constraints for both computation and network latencies, and analyze the model from various points of view.

[16] S. Ren, G. Agha, RT-synchronizer: Language support for real-time specifications in distributed systems, in: Workshop on Languages, Compilers and Tools for Real-Time Systems, 1995, pp. 50–59. [17] B. Nielsen, G. Agha, Semantics for an actor-based real-time language, in: Proceedings of the Fourth International Workshop on Parallel and Distributed Real-Time Systems, WPDRS’96, IEEE Computer Society Press, Los Alamitos, CA, USA, 1996.

MarjanSirjani commented 5 years ago

Other timed languages are also in the following papers. I'll add a few to the paper during the weekend and next week.

Modelling and simulation of asynchronous real-time systems using Timed Rebeca http://rebeca-lang.org/assets/papers/2014/Modelling%20and%20simulation%20of%20asynchronous%20real-time%20systems%20using%20Timed%20Rebeca.pdf

and the FTTS paper http://rebeca-lang.org/assets/papers/2014/Timed-Rebeca-Shift-Equivalency-published.pdf

MarjanSirjani commented 5 years ago

There is also this one: A Survey of Active Object Languages http://einarj.at.ifi.uio.no/Papers/deboer17csur.pdf

We start with Rebeca, which is closest to the classical actor model [3], but nevertheless provides communication by a form of asynchronous method invocation. The three other languages—ABS, ASP, and Encore—are precise representatives of active object frameworks. Additionally, each of them implements replies to asynchronous method calls in the form of futures (see Section 2.1), which enables advanced synchronization between the active objects.

MarjanSirjani commented 5 years ago

And Theatre work of https://dblp.org/pers/hd/n/Nigro:Libero

MarjanSirjani commented 5 years ago

Its a good idea if you have a look at RTSynchrozer: http://osl.cs.illinois.edu/media/papers/ren-1995-lctrts-rtsynchronizer.pdf

edwardalee commented 5 years ago

We should definitely cite this paper.

I suggest we say something like this:

In \cite{FIXME}, Ren and Agha also propose giving actors a temporal semantics. As in our work, they assume a sufficiently well synchronized common physical time base shared by all actors, and they express timing requirements as constraints on message handling. Their work differs from ours, however, in that they build off a standard actor language, thereby inheriting its nondeterministic ordering of message handling, and they rely on separately imposing timing constraints to control the order when needed. In contrast, we use logical time stamps to define the order of message handling and ensure determinism. Timing constraints are imposed after ensuring that a computation is performed ``correctly'' (yielding the one deterministic result) rather than to ensure that the computation is performed correctly.

Marten: Can you integrate this in the related work section if it fits?

Thanks. Edward

On 3/9/19 1:27 AM, MarjanSirjani wrote:

Its a good idea if you have a look at RTSynchrozer: http://osl.cs.illinois.edu/media/papers/ren-1995-lctrts-rtsynchronizer.pdf

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/icyphy/lingua-franca/issues/1#issuecomment-471161451, or mute the thread https://github.com/notifications/unsubscribe-auth/AIHnNqBkC49-CfK_6H1QvYPVZumX3jY8ks5vU36VgaJpZM4bbqXV.

-- Edward A. Lee Professor of the Graduate School and Robert S. Pepper Distinguished Professor Emeritus EECS Department, UC Berkeley http://ptolemy.eecs.berkeley.edu/~eal

lhstrh commented 5 years ago

Will do. I already cited it in section 2, but hadn’t remarked anything specific on it. This is perfect for the related work section...

On Mon, Mar 11, 2019 at 6:52 PM Edward A. Lee notifications@github.com wrote:

We should definitely cite this paper.

I suggest we say something like this:

In \cite{FIXME}, Ren and Agha also propose giving actors a temporal semantics. As in our work, they assume a sufficiently well synchronized common physical time base shared by all actors, and they express timing requirements as constraints on message handling. Their work differs from ours, however, in that they build off a standard actor language, thereby inheriting its nondeterministic ordering of message handling, and they rely on separately imposing timing constraints to control the order when needed. In contrast, we use logical time stamps to define the order of message handling and ensure determinism. Timing constraints are imposed after ensuring that a computation is performed ``correctly'' (yielding the one deterministic result) rather than to ensure that the computation is performed correctly.

Marten: Can you integrate this in the related work section if it fits?

Thanks. Edward

On 3/9/19 1:27 AM, MarjanSirjani wrote:

Its a good idea if you have a look at RTSynchrozer:

http://osl.cs.illinois.edu/media/papers/ren-1995-lctrts-rtsynchronizer.pdf

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <https://github.com/icyphy/lingua-franca/issues/1#issuecomment-471161451 , or mute the thread < https://github.com/notifications/unsubscribe-auth/AIHnNqBkC49-CfK_6H1QvYPVZumX3jY8ks5vU36VgaJpZM4bbqXV .

-- Edward A. Lee Professor of the Graduate School and Robert S. Pepper Distinguished Professor Emeritus EECS Department, UC Berkeley http://ptolemy.eecs.berkeley.edu/~eal

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/icyphy/lingua-franca/issues/1#issuecomment-471816166, or mute the thread https://github.com/notifications/unsubscribe-auth/ATA-fO8UtzEugqTBcSBYWWkqQgDeGPPyks5vVwhegaJpZM4bbqXV .

--

-- Marten Lohstroh, MSc. | Ph.D. Candidate University of California | 545Q Cory Hall Berkeley, CA 94720 | +1 510 282 9135

MarjanSirjani commented 5 years ago

Have a look at this one too: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.204.9139&rep=rep1&type=pdf

MarjanSirjani commented 5 years ago

I don't understand the following: In contrast, we use logical time stamps to define the order of message handling and ensure determinism. Timing constraints are imposed after ensuring that a computation is performed ``correctly'' (yielding the one deterministic result) rather than to ensure that the computation is performed correctly.

MarjanSirjani commented 5 years ago

I'm just thinking loud here: In RTSynchronizer they have: separation of the functional behaviors of actors and the timing constraints on patterns of actor invocation. They count 3 advantages: First, it simpli es code development by separating design concerns. Second, multiple timing constraints can be independently speci ed and composed. And finally, a speci cation of timing constraints can be reused even if the representation of the functional behavior of actors has changed, and conversely.

They are collecting different timing constraints in RTSynchronizer: the timing features that can be controlled by one actor (by some deterministic behavior) with properties over a bunch of actors.

In some aspect RTSynchronizer is similar to a director in Ptolemy.

In Rebeca we don't have any central view on anything.

edwardalee commented 5 years ago

Yes, it's not well said. We could just drop the last sentence.

Edward

On 3/12/19 6:34 AM, MarjanSirjani wrote:

I don't understand the following: In contrast, we use logical time stamps to define the order of message handling and ensure determinism. Timing constraints are imposed after ensuring that a computation is performed ``correctly'' (yielding the one deterministic result) rather than to ensure that the computation is performed correctly.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/icyphy/lingua-franca/issues/1#issuecomment-472002616, or mute the thread https://github.com/notifications/unsubscribe-auth/AIHnNg6pDXmTfvhMdblRDzUfp21i4yrpks5vV6z-gaJpZM4bbqXV.

-- Edward A. Lee Professor of the Graduate School and Robert S. Pepper Distinguished Professor Emeritus EECS Department, UC Berkeley http://ptolemy.eecs.berkeley.edu/~eal

MarjanSirjani commented 5 years ago

Right.

From the paper: The actor model has a number of advantages in modeling distributed real-time systems. First, the lack of interruptability of invocations guarantees that the computation time will only depend on the behavior of the invoked actor and the content of the invoking message. Thus, computation time is a deterministic function of incoming messages. Second, the Actor model only requires the speci fication of the logical order of events; it thus allows scheduling to be separately speci ed.

MarjanSirjani commented 5 years ago

In Section 4 of the paper we have to be clear how LF will guarantee determinism while RTSynchronizer does not.

goens commented 5 years ago

This looks a lot like LF, probably worth keeping in mind: http://caph.univ-bpclermont.fr/CAPH/CAPH.html (they have this paper about it too https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6972018)

edwardalee commented 5 years ago

I've started a page on related work and added this and also the pointer to I/O Automata:

https://github.com/icyphy/lingua-franca/wiki/Related-Work

CAPH is a dataflow language, of which there are probably hundreds by now. It doesn't look to me like the CNRS authors know much about the prior work on dataflow, however. Their use of firing rules looks a bit like cyclo-static dataflow, but they don't seem to know about consistency analysis nor about the constraints on firing rules to ensure determinism.

Edward

On 4/23/19 4:49 AM, goens wrote:

This looks a lot like LF, probably worth keeping in mind: http://caph.univ-bpclermont.fr/CAPH/CAPH.html (they have this paper about it too https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6972018)

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/icyphy/lingua-franca/issues/1#issuecomment-485769752, or mute the thread https://github.com/notifications/unsubscribe-auth/ACA6ONRBTXIEXA2HHDUVEBLPR3ZUNANCNFSM4G3OUXKQ.

-- Edward A. Lee Professor of the Graduate School and Robert S. Pepper Distinguished Professor Emeritus EECS Department, UC Berkeley http://ptolemy.eecs.berkeley.edu/~eal

cdgill commented 5 years ago

Hi Edward,

Another piece of related work is my student Justin Wilson’s PhD dissertation, titled “A Transactional Model and Platform for Designing and Implementing Reactive Systemshttps://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=1218&context=eng_etds” which is also linked at https://openscholarship.wustl.edu/eng_etds/217/

Justin’s reactive components model doesn’t address time, but provides a transactional concurrency model that combines and extends features from I/O Automata and UNITY.

I hope this helps,

Chris

From: "Edward A. Lee" notifications@github.com<mailto:notifications@github.com> Reply-To: icyphy/lingua-franca reply@reply.github.com<mailto:reply@reply.github.com> Date: Tuesday, April 23, 2019 at 8:43 AM To: icyphy/lingua-franca lingua-franca@noreply.github.com<mailto:lingua-franca@noreply.github.com> Cc: Subscribed subscribed@noreply.github.com<mailto:subscribed@noreply.github.com> Subject: Re: [icyphy/lingua-franca] Related work (#1)

I've started a page on related work and added this and also the pointer to I/O Automata:

https://github.com/icyphy/lingua-franca/wiki/Related-Work

CAPH is a dataflow language, of which there are probably hundreds by now. It doesn't look to me like the CNRS authors know much about the prior work on dataflow, however. Their use of firing rules looks a bit like cyclo-static dataflow, but they don't seem to know about consistency analysis nor about the constraints on firing rules to ensure determinism.

Edward

On 4/23/19 4:49 AM, goens wrote:

This looks a lot like LF, probably worth keeping in mind: http://caph.univ-bpclermont.fr/CAPH/CAPH.html (they have this paper about it too https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6972018)

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/icyphy/lingua-franca/issues/1#issuecomment-485769752, or mute the thread https://github.com/notifications/unsubscribe-auth/ACA6ONRBTXIEXA2HHDUVEBLPR3ZUNANCNFSM4G3OUXKQ.

-- Edward A. Lee Professor of the Graduate School and Robert S. Pepper Distinguished Professor Emeritus EECS Department, UC Berkeley http://ptolemy.eecs.berkeley.edu/~eal

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHubhttps://github.com/icyphy/lingua-franca/issues/1#issuecomment-485808440, or mute the threadhttps://github.com/notifications/unsubscribe-auth/AAG52PRY4Z2PDJXGJKQWBT3PR4HALANCNFSM4G3OUXKQ.

ChadliaJerad commented 5 years ago

There is no composition/hierarchy in CAPH. It is connecting actors in a flattened way.

It is more like the Chisel https://chisel.eecs.berkeley.edu/ approach, with adoption of Dataflow MoC and much less features than Chisel.

On Tue, Apr 23, 2019 at 2:43 PM Edward A. Lee notifications@github.com wrote:

I've started a page on related work and added this and also the pointer to I/O Automata:

https://github.com/icyphy/lingua-franca/wiki/Related-Work

CAPH is a dataflow language, of which there are probably hundreds by now. It doesn't look to me like the CNRS authors know much about the prior work on dataflow, however. Their use of firing rules looks a bit like cyclo-static dataflow, but they don't seem to know about consistency analysis nor about the constraints on firing rules to ensure determinism.

Edward

On 4/23/19 4:49 AM, goens wrote:

This looks a lot like LF, probably worth keeping in mind: http://caph.univ-bpclermont.fr/CAPH/CAPH.html (they have this paper about it too https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6972018)

— You are receiving this because you commented. Reply to this email directly, view it on GitHub <https://github.com/icyphy/lingua-franca/issues/1#issuecomment-485769752 , or mute the thread < https://github.com/notifications/unsubscribe-auth/ACA6ONRBTXIEXA2HHDUVEBLPR3ZUNANCNFSM4G3OUXKQ .

-- Edward A. Lee Professor of the Graduate School and Robert S. Pepper Distinguished Professor Emeritus EECS Department, UC Berkeley http://ptolemy.eecs.berkeley.edu/~eal

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/icyphy/lingua-franca/issues/1#issuecomment-485808440, or mute the thread https://github.com/notifications/unsubscribe-auth/AI6EI5A6W5PL5VXDRVBDX53PR4HANANCNFSM4G3OUXKQ .