Open Effects: A Hybrid Type-and-Effect System to Tackle Open World Assumption and its Application to Optimistic Concurrency

Thumbnail Image
Date
2014-03-25
Authors
Long, Yuheng
Bagherzadeh, Mehdi
Rajan, Hridesh
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Person
Rajan, Hridesh
Professor and Department Chair of Computer Science
Research Projects
Organizational Units
Organizational Unit
Computer Science

Computer Science—the theory, representation, processing, communication and use of information—is fundamentally transforming every aspect of human endeavor. The Department of Computer Science at Iowa State University advances computational and information sciences through; 1. educational and research programs within and beyond the university; 2. active engagement to help define national and international research, and 3. educational agendas, and sustained commitment to graduating leaders for academia, industry and government.

History
The Computer Science Department was officially established in 1969, with Robert Stewart serving as the founding Department Chair. Faculty were composed of joint appointments with Mathematics, Statistics, and Electrical Engineering. In 1969, the building which now houses the Computer Science department, then simply called the Computer Science building, was completed. Later it was named Atanasoff Hall. Throughout the 1980s to present, the department expanded and developed its teaching and research agendas to cover many areas of computing.

Dates of Existence
1969-present

Related Units

Journal Issue
Is Version Of
Versions
Series
Department
Computer Science
Abstract

This work tackles the challenge of applying a type-and-effect system to reason about object-oriented programs with an open world assumption. An open world assumption challenges the design of a type-and-effect system when (1) all subclasses of a class are not known, and (2) an upper bound on effects of all subclasses is not available, e.g. when an effect specification is not available for that class – a common phenomenon in modern OO programs. The main problem is in the computation of the effects of a dynamically dispatched method invocation, because all possible dynamic types of its receiver are not known statically, and no static upper bound in the form of effect specification is available. Our new concept open effects solves these problems. The basic idea is to take a programmer-guided hybrid approach. Instead of using a predefined upper bound, our type-and-effect system takes the effects of a programmer-selected dynamically dispatched method call as open effects that encapsulate statically known information about the call, e.g. static type of receiver. The static part of our type-and-effect systems treats open effects as unknown, but the dynamic part of our type-and-effect systems reifies open effects. We also apply open effects to create a sound trust-but-verify type-and-effect system, to better enable concurrent execution of dynamically dispatched method invocations. If a programmer annotates the receiver of a certain method invocation as open, then the type system trusts the programmer and assigns an open effect to the method. The open effect is, optimistically, not supposed to conflict with other effects. Such optimistic assumptions are verified statically, if possible, or at runtime otherwise. Performance evaluations of an open effects-based type system for concurrency, on various benchmarks, show that it incurs negligible annotation and runtime overheads.

Comments

Copyright © 2013, Yuheng Long, and Mehdi Bagherzadeh and Hridesh Rajan.

Description
Keywords
Citation
DOI
Source
Copyright
Collections