Previous terms: W13 F12 S12 F11 S11 W11 F10 S10 F08 S08 W08 F07 W07 F06 S06 W06
|Date||Speaker||Title (click for abstract)||Location|
|Fri. Mar. 28, 2014 at 1:30 pm||Magnus Madsen||String Analysis for Dynamic Field Access||DC 2310|
|Mon. Mar. 31, 2014 at 10:30 am||Shahram Esmaeilsabzali||Dynamic Package Interfaces||DC 2310|
|Mon. Apr. 14, 2014 at 2:00 pm||David F. Bacon, IBM Research||Liquid Metal: Programming in the Age of Heterogeneous Machines||DC 1304|
|Tue. Apr. 15, 2014 at 10:00 am||Karim Ali||Constructing Call Graphs of Scala Programs||DC 2310|
|Tue. May 13, 2014 at 1:30 pm||Siddharth Subramanian||Live API Documentation||DC 1331|
|Mon. July 21, 2014 at 4:00 pm||Marianna Rapoport||Data Flow Analysis in the Presence of Correlated Calls||DC 1331|
All are welcome.
Talk announcements are also posted to a public mailing list.
To volunteer to give a talk, contact Ondřej Lhoták. Talks can range from informal to formal, and they can be about any of the following:
The purpose is for us all to see what people are interested in, and motivate discussions.
We demonstrate that a dataflow analysis equipped with the H domain
gains significant precision resulting in an analysis speedup of more than
1.5x for 7 out of 10 benchmark programs.
Dynamic Package Interfaces
Mar. 31, 2014
A hallmark of object-oriented programming is the ability to perform computation through a set of interacting objects. A common manifestation of this style is the notion of a package, which groups a set of commonly used classes together. A challenge in using a package is to ensure that a client follows the implicit protocol of the package when calling its methods. Violations of the protocol can cause a runtime error or latent invariant violations. These protocols can extend across different, potentially unboundedly many, objects, and are specified informally in the documentation. As a result, ensuring that a client does not violate the protocol is hard.
We introduce dynamic package interfaces (DPI), a formalism to explicitly
capture the protocol of a package. The DPI of a package is a finite set of
rules that together specify how any set of interacting objects of the package
can evolve through method calls and under what conditions an error can happen.
We have developed a dynamic tool that automatically computes an approximation
of the DPI of a package, given a set of abstraction predicates. A key property
of DPI is that the unbounded number of configurations of objects of a package
are summarized finitely in an abstract domain. This uses the observation that
many packages behave monotonically: the semantics of a method call over a
configuration does not essentially change if more objects are added to the
configuration. We have exploited monotonicity and have devised heuristics to
obtain succinct yet general DPIs. We have used our tool to compute DPIs for
several commonly used Java packages with complex protocols, such as JDBC,
HashSet, and ArrayList.
Liquid Metal: Programming in the Age of Heterogeneous Machines
David F. Bacon, IBM Research
Apr. 14, 2014
The end of frequency scaling means that the search for performance must turn elsewhere, and will inevitably require improvements in transistor efficiency that can only be obtained by specializing hardware to programs. So begins the age of heterogeneous machines.
The goal of the Liquid Metal project at IBM Research is to enable the use of these heterogeneous machines by providing a single programming language that can be compiled, executed, and dynamically migrated across a very diverse set of systems: CPUs, GPUs, reconfigurable hardware (FPGAs), Cell-style processors, etc.
Achieving this goal requires significant innovation across the entire system: language design, compiler technology, interactive development environment, debugging, hardware synthesis, the run-time system, performance analysis, and hardware protocols.
I will give an overview of the Liquid Metal language and the system we have built, demonstrate dynamic execution across multiple platforms, and show how high-level, higher-order data structures can be compiled into efficient hardware.
Joint work with Erik Altman, Joshua Auerbach, Perry Cheng, Stephen Fink, Rodric Rabbah, Sunil Shukla.
Constructing Call Graphs of Scala Programs
Apr. 15, 2014
As a result of Scala's increasing popularity as a programming language, there has been a growing interest in programming tools for Scala. Such tools often require the construction of a call graph, but no call graph construction algorithm has been presented in the literature that handles Scala features such as traits and abstract type members. In principle, one could apply an existing call graph construction algorithm to the JVM bytecodes produced by the Scala compiler. However, such an approach is not viable because the Scala compiler translates several constructs into hard-to-analyze reflection, and because type information is lost during translation of certain Scala idioms. Therefore, in this paper, we present Trait Composition Analysis (TCA), a simple type-based call graph construction algorithm for Scala. We present a formal definition of TCA for Featherweight Scala, a core subset of Scala that features traits, abstract type members, and path-dependent types. We implemented TCA as an extension of the Scala compiler and report on experiments in which TCA’s effectiveness is compared to that of a simple name-based resolution scheme.
Live API Documentation
May 13, 2014
Application Programming Interfaces (APIs) provide powerful abstraction mechanisms that enable complex functionality to be used by client programs. However, this abstraction does not come for free: understanding how to use an API can be difficult. While API documentation can help, it is often insufficient on its own. Online sites like Stack Overflow and Github Gists have grown to fill the gap between traditional API documentation and more example-based resources. Unfortunately, these two important classes of documentation are independent.
In this talk we describe an iterative, deductive method of linking
source code examples to API documentation. We also present an
implementation of this method, called Baker, that is highly precise
to enhance traditional API documentation with up-to-date source
code examples; it can also be used to incorporate links to the API
documentation into the code snippets that use the API.
Data Flow Analysis in the Presence of Correlated Calls
July 21, 2014
This thesis presents a technique to improve the precision of data-flow analyses on object-oriented programs in the presence of correlated calls. We say that two method calls are correlated if they are polymorphic (have multiple targets) and are invoked on the same object. Correlated calls are problematic because they can make existing data-flow analyses consider certain infeasible data-flow paths as valid. This leads to loss in precision of the analysis solution.
We show how infeasible paths can be eliminated for Interprocedural Finite Distributive Subset (IFDS) problems, a large class of data-flow analysis problems. We show how the precision of IFDS problems can be improved in the presence of correlated calls, by using the Interprocedural Distributive Environment (IDE) algorithm to eliminate infeasible paths. Using IDE, we eliminate the infeasible paths and obtain a more precise result of the original IFDS problem.
Our analysis is implemented in Scala, using the WALA framework for static program analysis on Java byte code.