Logo: to the web site of Uppsala University

uu.sePublications from Uppsala University
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Abstractions to Control the Future
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.ORCID iD: 0000-0001-8654-118X
2021 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Multicore and manycore computers are the norm nowadays, and users have expectations that their programs can do multiple things concurrently. To support that, developers use concur- rency abstractions such as threads, promises, futures, and/or channels to exchange information. All these abstractions introduce trade-offs between the concurrency model and the language guarantees, and developers accept these trade-offs for the benefits of concurrent programming.

Many concurrent languages are multi-paradigm, e.g., mix the functional and object-oriented paradigms. This is beneficial to developers because they can choose the most suitable approach when solving a problem. From the point of view of concurrency, purely functional programming languages are data-race free since they only support immutable data. Object-oriented languages do not get a free lunch, and neither do multi-paradigm languages that have imperative features.

The main problem is uncontrolled concurrent access to shared mutable state, which may inadvertently introduce data-races. A data-race happens when two concurrent memory operations target the same location, at least one of them is a write, and there is no synchronisation operation involved. Data-races make programs to exhibit (unwanted) non-deterministic behaviour.

The contribution of this thesis is two-fold. First, this thesis introduces new concurrent abstractions in a purely functional, statically typed programming language (Paper I – Paper III); these abstractions allow developers to write concurrent control- and delegation-based patterns. Second, this thesis introduces a capability-based dynamic programming model, named Dala, that extends the applicability of the concurrent abstractions to an imperative setting while maintaining data-race freedom (Paper IV). Developers can also use the Dala model to migrate unsafe programs, i.e., programs that may suffer data-races, to data-race free programs.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2021. , p. 85
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1986
Keywords [en]
concurrent, programming, type system, future, actors, active objects
National Category
Computer Systems
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-425128ISBN: 978-91-513-1062-6 (print)OAI: oai:DiVA.org:uu-425128DiVA, id: diva2:1502080
Public defence
2021-01-18, Room 2446, ITC, Lägerhyddsvägen 2, hus 2, Uppsala, 16:00 (English)
Opponent
Supervisors
Available from: 2020-12-21 Created: 2020-11-18 Last updated: 2021-01-25
List of papers
1. ParT: An asynchronous parallel abstraction for speculative pipeline computations
Open this publication in new window or tab >>ParT: An asynchronous parallel abstraction for speculative pipeline computations
2016 (English)In: Coordination Models and Languages / [ed] Lafuente, AL; Proenca, J, Springer, 2016, p. 101-120Conference paper, Published paper (Refereed)
Abstract [en]

The ubiquity of multicore computers has forced programming language designers to rethink how languages express parallelism and concurrency. This has resulted in new language constructs and new combinations or revisions of existing constructs. In this line, we extended the programming languages Encore (actor-based), and Clojure (functional) with an asynchronous parallel abstraction called ParT, a data structure that can dually be seen as a collection of asynchronous values (integrating with futures) or a handle to a parallel computation, plus a collection of combinators for manipulating the data structure. The combinators can express parallel pipelines and speculative parallelism. This paper presents a typed calculus capturing the essence of ParT, abstracting away from details of the Encore and Clojure programming languages. The calculus includes tasks, futures, and combinators similar to those of Orc but implemented in a non-blocking fashion. Furthermore, the calculus strongly mimics how ParT is implemented, and it can serve as the basis for adaptation of ParT into different languages and for further extensions.

Place, publisher, year, edition, pages
Springer, 2016
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9686
National Category
Computer Systems
Identifiers
urn:nbn:se:uu:diva-309764 (URN)10.1007/978-3-319-39519-7_7 (DOI)000388794200007 ()9783319395180 (ISBN)
Conference
COORDINATION 2016
Projects
UpScaleUPMARC
Funder
EU, FP7, Seventh Framework Programme, FP7-612985
Available from: 2016-05-24 Created: 2016-12-07 Last updated: 2020-11-18Bibliographically approved
2. Forward to a Promising Future
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: 2020-11-18Bibliographically approved
3. Godot: All the Benefits of Implicit and Explicit Futures
Open this publication in new window or tab >>Godot: All the Benefits of Implicit and Explicit Futures
Show others...
2019 (English)In: 33rd European Conference on Object-Oriented Programming (ECOOP 2019), 2019Conference paper, Published paper (Refereed)
Abstract [en]

Concurrent programs often make use of futures, handles to the results of asynchronous operations. Futures provide means to communicate not yet computed results, and simplify the implementation of operations that synchronise on the result of such asynchronous operations. Futures can be characterised as implicit or explicit, depending on the typing discipline used to type them. Current future implementations suffer from "future proliferation", either at the type-level or at run-time. The former adds future type wrappers, which hinders subtype polymorphism and exposes the client to the internal asynchronous communication architecture. The latter increases latency, by traversing nested future structures at run-time. Many languages suffer both kinds. Previous work offer partial solutions to the future proliferation problems; in this paper we show how these solutions can be integrated in an elegant and coherent way, which is more expressive than either system in isolation. We describe our proposal formally, and state and prove its key properties, in two related calculi, based on the two possible families of future constructs (data-flow futures and control-flow futures). The former relies on static type information to avoid unwanted future creation, and the latter uses an algebraic data type with dynamic checks. We also discuss how to implement our new system efficiently.

Series
Leibniz International Proceedings in Informatics (LIPIcs), ISSN 1868-8969 ; 134
National Category
Computer Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-396199 (URN)10.4230/LIPIcs.ECOOP.2019.2 (DOI)978-3-95977-111-5 (ISBN)
Conference
33rd European Conference on Object-Oriented Programming (ECOOP 2019), London, UK, 15-19 july 2019
Available from: 2019-10-31 Created: 2019-10-31 Last updated: 2020-11-18Bibliographically approved
4. Dala: A Simple Capability-Based Dynamic Language Design For Data-Race Freedom
Open this publication in new window or tab >>Dala: A Simple Capability-Based Dynamic Language Design For Data-Race Freedom
Show others...
(English)Manuscript (preprint) (Other academic)
Abstract [en]

Dynamic languages like Erlang, Clojure, JavaScript, and E adopted data-race freedom by design. To enforce data-race freedom, these languages either deep copy objects during actor (thread) communication or proxy back to their owning thread. We present Dala, a simple programming model that ensures data-race freedom while supporting efficient inter-thread communication. Dala is a dynamic, concurrent, capability-based language that relies on three core capa- bilities: immutable values can be shared freely; isolated mutable objects can be transferred between threads but not aliased; local objects can be aliased within their owning thread but not dereferenced by other threads. The addition of a fourth capability, unsafe, allows data races and we show how data-race free programs interact with unsafe programs. We present a formal model of Dala, prove data race-freedom and the dynamic gradual guarantee. These theorems guarantee data race-freedom when using safe capabilities and show that the addition of capabili- ties is semantics preserving modulo permission and cast errors.

National Category
Computer Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-425127 (URN)
Available from: 2020-11-12 Created: 2020-11-12 Last updated: 2021-01-29Bibliographically approved

Open Access in DiVA

fulltext(575 kB)501 downloads
File information
File name FULLTEXT01.pdfFile size 575 kBChecksum SHA-512
98706658666d8af9a486464d29c8b48f7e695f05a43fbd82d94cd3e964871c06819e0221598749ff4620c61948f3429612e3b506fb5ef34114eb7e070304804a
Type fulltextMimetype application/pdf

Other links

Online defence

Search in DiVA

By author/editor
Fernández Reyes, Francisco Ramón
By organisation
Division of Computing ScienceComputing Science
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 502 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1704 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf