uu.seUppsala University Publications
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
Structured Data
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-0002-0949-0291
2018 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

References are a programming language construct that lets a programmer access a datum invariant of its location.

References permit aliasing -- several references to the same object, effectively making a single object accessible through different names (or paths). Aliasing, especially of mutable data, is both a blessing and a curse: when used correctly, it can make a programmer's life easier; when used incorrectly, for example through accidental aliases that the programmer is unaware of, aliasing can lead to hard to find bugs, and hard to verify programs.

Aliases allow us to build efficient data structures by connecting objects together, making them immediately reachable. Aliases are at the heart of many useful programming idioms. But with great power comes great responsibility: unless a programmer carefully manages aliases in a program, aliases propagate changes and make parts of a program's memory change seemingly for no reason. Additionally, such bugs are very easy to make but very hard to track down.

This thesis presents an overview of techniques for controlling how, when and if data can be aliased, as well as how and if data can be mutated. Additionally, it presents three different projects aimed at conserving the blessings, but reducing the curses. The first project is disjointness domains, a type system for expressing intended aliasing in a fine-grained manner so that aliasing will not be unexpected; the second project is Spencer, a tool to flexibly and precisely analyse the use of aliasing in programs to improve our understanding of how aliasing of mutable data is used in practise; and the third project is c flat, an approach for implementing high-level collection data structures using a richer reference construct that reduces aliasing problems but still retains many of aliasing's benefits.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2018. , p. 85
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1749
Keywords [en]
Aliasing, mutable state, imperative, programming, programming languages.
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-366932ISBN: 978-91-513-0515-8 (print)OAI: oai:DiVA.org:uu-366932DiVA, id: diva2:1266019
Public defence
2019-01-23, Room 2446, Institutionen för informationsteknologi, Polacksbacken, Lägerhyddsvägen 2, Uppsala, 13:15 (English)
Opponent
Supervisors
Available from: 2018-12-20 Created: 2018-11-27 Last updated: 2019-01-21
List of papers
1. Disjointness Domains for Fine-Grained Aliasing
Open this publication in new window or tab >>Disjointness Domains for Fine-Grained Aliasing
2015 (English)Conference paper, Published paper (Refereed)
Abstract [en]

Aliasing is crucial for supporting useful implementation patterns, but it makes reasoning about programs difficult. To deal with this problem, numerous type-based aliasing control mechanisms have been proposed, expressing properties such as uniqueness. Uniqueness, however, is black-and-white: either a reference is unique or it can be arbitrarily aliased; and global: excluding aliases throughout the entire system, making code brittle to changing requirements. Disjointness domains, a new approach to alias control, address this problem by enabling more graduations between uniqueness and arbitrary reference sharing. They allow expressing aliasing constraints local to a certain set of variables (either stack variables or fields) for instance that no aliasing occurs between variables within some set of variables but between such sets or the opposite, that aliasing occurs within that set but not between different sets. A hierarchy of disjointness domains controls the flow of references through a program, helping the programmer reason about disjointness and enforce local alias invariants. The resulting system supports fine-grained control of aliasing between both variables and objects, making aliasing explicit to programmers, compilers, and tooling. This paper presents a formal account of disjointness domains along with examples. Disjointness domains provide novel means of expressing may-alias kinds of constraints, which may prove useful in compiler optimisation and verification.

Series
ACM SIGPLAN NOTICES, ISSN 0362-1340
Keywords
Design; Theory; Aliasing; mutable state; type systems; uniqueness; linear types
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-268747 (URN)10.1145/2814270.2814280 (DOI)000367256500051 ()
Conference
ACM International Conference on Object Oriented Programming Systems Languages and Applications (OOPSLA)
Available from: 2015-12-09 Created: 2015-12-09 Last updated: 2018-11-27Bibliographically approved
2. Spencer: Interactive Heap Analysis for the Masses
Open this publication in new window or tab >>Spencer: Interactive Heap Analysis for the Masses
2017 (English)In: 2017 IEEE/ACM 14th International Conference on Mining Software Repositories (MSR 2017), IEEE, 2017, no 14, p. 113-123Conference paper, Published paper (Refereed)
Abstract [en]

Programming language-design and run-time-implementation require detailed knowledge about the programs that users want to implement. Acquiring this knowledge is hard, and there is little tool support to effectively estimate whether a proposed tradeoff actually makes sense in the context of real world applications. Ideally, knowledge about behaviour of "typical" programs is 1) easily obtainable, 2) easily reproducible, and 3) easily sharable. We present Spencer, an open source web service and API framework for dynamic analysis of a continuously growing set of traces of standard program corpora. Users do not obtain traces on their own, but can instead send queries to the web service that will be executed on a set of program traces. Queries are built in terms of a set of query combinators that present a high level interface for working with trace data. Since the framework is high level, and there is a hosted collection of recorded traces, queries are easy to implement. Since the data sets are shared by the research community, results are reproducible. Since the actual queries run on one (or many) servers that provide analysis as a service, obtaining results is possible on commodity hardware. Data in Spencer is meant to be obtained once, and analysed often, making the overhead of data collection mostly irrelevant. This allows Spencer to collect more data than traditional tracing tools can afford within their performance budget. Results in Spencer are cached, making complicated analyses that build on cached primitive queries speedy.

Place, publisher, year, edition, pages
IEEE, 2017
Series
IEEE International Working Conference on Mining Software Repositories, E-ISSN 2160-1852
Keywords
tracing, dynamic analysis, heap analysis, tracing
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-334818 (URN)10.1109/MSR.2017.35 (DOI)000425917100013 ()978-1-5386-1544-7 (ISBN)
Conference
IEEE/ACM 14th International Conference on Mining Software Repositories (MSR), Buenos Aires, Argentina, May 20-21, 2017
Available from: 2017-11-28 Created: 2017-11-28 Last updated: 2018-11-27Bibliographically approved
3. Mining for Safety using Interactive Trace Analysis
Open this publication in new window or tab >>Mining for Safety using Interactive Trace Analysis
2017 (English)In: Pre-Proceedings - Fifteenth International Workshop on Quantitative Aspects of Programming Languages and Systems, 2017, no 15, article id 14Conference paper, Published paper (Refereed)
Keywords
tracing, dynamic analysis, heap analysis, tracing
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-334817 (URN)
Conference
Fifteenth International Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL)
Available from: 2017-11-28 Created: 2017-11-28 Last updated: 2018-11-27Bibliographically approved
4. C♭: A New Modular Approach to Implementing Efficient and Tunable Collections
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

Open Access in DiVA

fulltext(839 kB)70 downloads
File information
File name FULLTEXT01.pdfFile size 839 kBChecksum SHA-512
08d77ec8ffb7928a4ce6a0e62fb64cc8b05fe6367a4611326e66e5aa99db38491de9500fcbd40eeb444867d91f5d8d311fd0b8659beb44075f697d65fbba11ac
Type fulltextMimetype application/pdf
Buy this publication >>

Authority records BETA

Brandauer, Stephan

Search in DiVA

By author/editor
Brandauer, Stephan
By organisation
Division of Computing ScienceComputing Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 70 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: 528 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