uu.seUppsala University Publications
Change search
Link to record
Permanent link

Direct link
BETA
Publications (10 of 18) Show all publications
Castegren, E., Clarke, D., Fernandez-Reyes, K., Wrigstad, T. & Yang, A. M. (2018). Attached and Detached Closures in Actors. In: Proceedings of the 8th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control: . Paper presented at AGERE'18 (8th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control), Boston, MA, USA, November 05, 2018 (pp. 54-61). ACM Digital Library
Open this publication in new window or tab >>Attached and Detached Closures in Actors
Show others...
2018 (English)In: Proceedings of the 8th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control, ACM Digital Library, 2018, p. 54-61Conference paper, Published paper (Refereed)
Abstract [en]

Expressive actor models combine aspects of functional programming into the pure actor model enriched with futures. Such functional features include first-class closures which can be passed between actors and chained on futures. Combined with mutable objects, this opens the door to race conditions. In some situations, closures may not be evaluated by the actor that created them yet may access fields or objects owned by that actor. In other situations, closures may be safely fired off to run as a separate task.

This paper discusses the problem of who can safely evaluate a closure to avoid race conditions, and presents the current solution to the problem adopted by the Encore language. The solution integrates with Encore's capability type system, which influences whether a closure is attached and must be evaluated by the creating actor, or whether it can be detached and evaluated independently of its creator.

Encore's current solution to this problem is not final or optimal. We conclude by discussing a number of open problems related to dealing with closures in the actor model.

Place, publisher, year, edition, pages
ACM Digital Library, 2018
Keywords
closures, parallel programming, concurrent programming, type systems
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-367318 (URN)10.1145/3281366.3281371 (DOI)000458146800006 ()978-1-4503-6066-1 (ISBN)
Conference
AGERE'18 (8th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control), Boston, MA, USA, November 05, 2018
Funder
Swedish Research Council, 2012-4967Swedish Research Council, 2014-05545
Available from: 2018-11-29 Created: 2018-11-29 Last updated: 2019-02-28Bibliographically approved
Castegren, E., Wallin, J. & Wrigstad, T. (2018). Bestow and Atomic: Concurrent programming using isolation, delegation and grouping. The Journal of logical and algebraic methods in programming, 100, 130-151
Open this publication in new window or tab >>Bestow and Atomic: Concurrent programming using isolation, delegation and grouping
2018 (English)In: The Journal of logical and algebraic methods in programming, ISSN 2352-2208, E-ISSN 2352-2216, Vol. 100, p. 130-151Article in journal (Refereed) Published
Abstract [en]

Any non-trivial concurrent system warrants synchronisation, regardless of the concurrency model. Actor-based concurrency serialises all computations in an actor through asynchronous message passing. In contrast, lock-based concurrency serialises some computations by following a lock-unlock protocol for accessing certain data. Both systems require sound reasoning about pointers and aliasing to exclude data-races. If actor isolation is broken, so is the single-thread-of-control abstraction. Similarly for locks, if a datum is accessible outside of the scope of the lock, the datum is not governed by the lock. In this paper we discuss how to balance aliasing and synchronisation. In previous work, we defined a type system that guarantees data-race freedom of actor-based concurrency and lock-based concurrency. This paper extends this work by the introduction of two programming constructs; one for decoupling isolation and synchronisation and one for constructing higher-level atomicity guarantees from lower-level synchronisation. We focus predominantly on actors, and in particular the Encore programming language, but our ultimate goal is to define our constructs in such a way that they can be used both with locks and actors, given that combinations of both models occur frequently in actual systems. We discuss the design space, provide several formalisations of different semantics and discuss their properties, and connect them to case studies showing how our proposed constructs can be useful. We also report on an on-going implementation of our proposed constructs in Encore. 

National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-336020 (URN)10.1016/j.jlamp.2018.06.007 (DOI)000444363000008 ()
Projects
UPMARC
Funder
EU, FP7, Seventh Framework Programme, 612985Swedish Research Council, 2012-4967
Available from: 2018-06-30 Created: 2017-12-11 Last updated: 2018-11-14Bibliographically approved
Brandauer, S., Castegren, E. & Wrigstad, T. (2018). C♭: A New Modular Approach to Implementing Efficient and Tunable Collections. In: Proceedings of the 2018 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward! 2018): . Paper presented at SPLASH 2018 - Systems, Programming, Languages and Applications: Software for Humanity, Boston, 4-9 November, 2018 (pp. 57-71). ACM
Open this publication in new window or tab >>C♭: A New Modular Approach to Implementing Efficient and Tunable Collections
2018 (English)In: Proceedings of the 2018 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward! 2018), ACM , 2018, p. 57-71Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
ACM, 2018
Keywords
data structure design, domain specific language, performance tuning
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-366812 (URN)10.1145/3276954.3276956 (DOI)000455805700005 ()
Conference
SPLASH 2018 - Systems, Programming, Languages and Applications: Software for Humanity, Boston, 4-9 November, 2018
Projects
UPMARC2012-04867 Structured Aliasing
Funder
Swedish Research Council, 2012-04967
Available from: 2018-11-26 Created: 2018-11-26 Last updated: 2019-02-04Bibliographically approved
Fernandez-Reyes, K., Clarke, D., Castegren, E. & Vo, H.-P. (2018). Forward to a Promising Future. In: Conference proceedings COORDINATION 2018: . Paper presented at COORDINATION - 20th International Conference on Coordination Models and Languages, Madrid, June 18-21, 2018..
Open this publication in new window or tab >>Forward to a Promising Future
2018 (English)In: Conference proceedings COORDINATION 2018, 2018Conference paper, Published paper (Refereed)
Abstract [en]

In many actor-based programming models, asynchronous method calls communicate their results using futures, where the fulfilment occurs under-the-hood. Promises play a similar role to futures, except that they must be explicitly created and explicitly fulfilled; this makes promises more flexible than futures, though promises lack fulfilment guarantees: they can be fulfilled once, multiple times or not at all. Unfortunately, futures are too rigid to exploit many available concurrent and parallel patterns. For instance, many computations block on a future to get its result only to return that result immediately (to fulfil their own future). To make futures more flexible, we explore a construct, forward, that delegates the responsibility for fulfilling the current implicit future to another computation. Forward reduces synchronisation and gives futures promise-like capabilities. This paper presents a formalisation of the forward construct, defined in a high-level source language, and a compilation strategy from the high-level language to a low-level, promised-based target language. The translation is shown to preserve semantics. Based on this foundation, we describe the implementation of forward in the parallel, actor-based language Encore, which compiles to C.

Keywords
parallel, concurrency, futures, actors, tasks
National Category
Computer Systems
Identifiers
urn:nbn:se:uu:diva-351352 (URN)
Conference
COORDINATION - 20th International Conference on Coordination Models and Languages, Madrid, June 18-21, 2018.
Available from: 2018-05-23 Created: 2018-05-23 Last updated: 2018-05-24Bibliographically approved
Castegren, E. & Wrigstad, T. (2018). OOlong: An Extensible Concurrent Object Calculus. In: Proceedings of SAC 2018: Symposium on Applied Computing. Paper presented at 33rd Annual ACM Symposium on Applied Computing (ACM SAC), Pau, France, April 9–13, 2018. (pp. 1022-1029).
Open this publication in new window or tab >>OOlong: An Extensible Concurrent Object Calculus
2018 (English)In: Proceedings of SAC 2018: Symposium on Applied Computing, 2018, p. 1022-1029Conference paper, Published paper (Refereed)
Abstract [en]

We present OOlong, an object calculus with interface inheritance, structured concurrency and locks. The goal of the calculus is extensibility and reuse. The semantics are therefore available in a version for LaTeX typesetting (written in Ott), and a mechanised version for doing rigorous proofs in Coq.

Series
33RD ANNUAL ACM SYMPOSIUM ON APPLIED COMPUTING
Keywords
Object Calculi, Semantics, Mechanisation, Concurrency
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-335174 (URN)10.1145/3167132.3167243 (DOI)000455180700147 ()978-1-4503-5191-1 (ISBN)
Conference
33rd Annual ACM Symposium on Applied Computing (ACM SAC), Pau, France, April 9–13, 2018.
Note

Book Group Author(s): Assoc Comp Machinery

Available from: 2017-12-01 Created: 2017-12-01 Last updated: 2019-06-27Bibliographically approved
Åkerblom, B., Castegren, E. & Wrigstad, T. (2018). Parallel Programming With Arrays in Kappa. In: 5th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming: . Paper presented at PLDI, 18-22 June, 2018,Philadelphia, USA.
Open this publication in new window or tab >>Parallel Programming With Arrays in Kappa
2018 (English)In: 5th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming, 2018Conference paper, Oral presentation with published abstract (Refereed)
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-357241 (URN)
Conference
PLDI, 18-22 June, 2018,Philadelphia, USA
Projects
UPMARC
Available from: 2018-08-14 Created: 2018-08-14 Last updated: 2019-01-09Bibliographically approved
Castegren, E. & Wrigstad, T. (2017). Actors without Borders: Amnesty for Imprisoned State. In: : . Paper presented at Programming Language Approaches to Concurrency- and Communication-cEntric Software (pp. 10-20). (246)
Open this publication in new window or tab >>Actors without Borders: Amnesty for Imprisoned State
2017 (English)Conference paper, Published paper (Refereed)
Abstract [en]

In concurrent systems, some form of synchronisation is typically needed to achieve data-race freedom, which is important for correctness and safety. In actor-based systems, messages are exchanged concurrently but executed sequentially by the receiving actor. By relying on isolation and non-sharing, an actor can access its own state without fear of data-races, and the internal behavior of an actor can be reasoned about sequentially. However, actor isolation is sometimes too strong to express useful patterns. For example, letting the iterator of a data-collection alias the internal structure of the collection allows a more efficient implementation than if each access requires going through the interface of the collection. With full isolation, in order to maintain sequential reasoning the iterator must be made part of the collection, which bloats the interface of the collection and means that a client must have access to the whole data-collection in order to use the iterator. In this paper, we propose a programming language construct that enables a relaxation of isolation but without sacrificing sequential reasoning. We formalise the mechanism in a simple lambda calculus with actors and passive objects, and show how an actor may leak parts of its internal state while ensuring that any interaction with this data is still synchronised.

National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-331909 (URN)10.4204/EPTCS.246.4 (DOI)000405454500003 ()
Conference
Programming Language Approaches to Concurrency- and Communication-cEntric Software
Available from: 2017-10-20 Created: 2017-10-20 Last updated: 2018-01-13Bibliographically approved
Wrigstad, T. & Castegren, E. (2017). Mastery Learning-Like Teaching with Achievements. In: : . Paper presented at SPLASH 2017, October 22-27, 2017, Vancouver..
Open this publication in new window or tab >>Mastery Learning-Like Teaching with Achievements
2017 (English)Conference paper, Published paper (Refereed)
National Category
Educational Sciences Computer Sciences
Identifiers
urn:nbn:se:uu:diva-333724 (URN)
Conference
SPLASH 2017, October 22-27, 2017, Vancouver.
Available from: 2017-11-16 Created: 2017-11-16 Last updated: 2018-01-13Bibliographically approved
Castegren, E. & Wrigstad, T. (2017). Reference Capabilities for Concurrency & Scalability: an Experience Report. In: : . Paper presented at OCAP: Object-Capability Languages, Systems, and Applications.
Open this publication in new window or tab >>Reference Capabilities for Concurrency & Scalability: an Experience Report
2017 (English)Conference paper, Oral presentation with published abstract (Refereed)
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-333726 (URN)
Conference
OCAP: Object-Capability Languages, Systems, and Applications
Available from: 2017-11-16 Created: 2017-11-16 Last updated: 2018-01-13Bibliographically approved
Castegren, E. & Wrigstad, T. (2017). Relaxed Linear References for Lock-free Data Structures. In: Peter Müller (Ed.), : . Paper presented at European Conference on Object-Oriented Programming (ECOOP) (pp. 47:1-47:31). , Article ID 47.
Open this publication in new window or tab >>Relaxed Linear References for Lock-free Data Structures
2017 (English)In: / [ed] Peter Müller, 2017, p. 47:1-47:31, article id 47Conference paper, Published paper (Refereed)
Abstract [en]

Linear references are guaranteed to be free from aliases. This is a strong property that simplifies reasoning about programs and enables powerful optimisations, but it is also a property that is too strong for many applications. Notably, lock-free algorithms, which implement protocols that ensure safe, non-blocking concurrent access to data structures, are generally not typable with linear references because they rely on aliasing to achieve lock-freedom.

This paper presents LOLCAT, a type system with a relaxed notion of linearity that allows an unbounded number of aliases to an object as long as at most one alias at a time owns the right to access the contents of the object. This ownership can be transferred between aliases, but can never be duplicated. LOLCAT types are powerful enough to type several lock-free data structures and give a compile-time guarantee of absence of data-races when accessing owned data. In particular, LOLCAT is able to assign types to the CAS (compare and swap) primitive that precisely describe how ownership is transferred across aliases, possibly across different threads. The paper introduces LOLCAT through a sound core procedural calculus, and shows how LOLCAT can be applied to three fundamental lock-free data structures. It also discusses a prototype implementation which integrates LOLCAT with an object-oriented programming language.

National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-333668 (URN)10.4230/LIPIcs.ECOOP.2017.47 (DOI)
Conference
European Conference on Object-Oriented Programming (ECOOP)
Projects
Structured AliasingUPSCALEUPMARC
Funder
Swedish Research CouncilEU, FP7, Seventh Framework Programme
Available from: 2017-11-15 Created: 2017-11-15 Last updated: 2018-01-13Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0003-4918-6582

Search in DiVA

Show all publications