Waterloo Programming Languages Seminars

Previous terms: W13 F12 S12 F11 S11 W11 F10 S10 F08 S08 W08 F07 W07 F06 S06 W06

Current term:

Date	Speaker	Title (click for abstract)	Location
Tue. Feb. 25, 2014 at 3:00 pm	Magnus Madsen	Practical Static Analysis of JavaScript Applications in the Presence of Frameworks and Libraries	DC 2310
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:

completed research
research that you plan to start ("half-baked ideas" to be critiqued by your peers)
interesting paper(s) you have read

The purpose is for us all to see what people are interested in, and motivate discussions.

Abstracts

Practical Static Analysis of JavaScript Applications in the Presence of Frameworks and Libraries

Magnus Madsen
Feb. 25, 2014
JavaScript is a language that is widely-used for both web-based and standalone applications such as those in the Windows 8 operating system. Analysis of JavaScript has long been known to be challenging due to the language’s dynamic nature. On top of that, most JavaScript applications rely on large and complex libraries and frameworks, often written in a combination of JavaScript and native code such as C and C++. Stubs have been commonly employed as a partial specification mechanism to address the library problem; alas, they are tedious and error-prone. However, the manner in which library code is used within applications often sheds light on what library APIs return or pass into callbacks declared within the application. In this paper, we propose a technique which combines pointer analysis with a novel use analysis to handle many challenges posed by large JavaScript libraries. Our techniques have been implemented and empirically validated on a set of 25 Windows 8 JavaScript applications, averaging 1,587 lines of code, together with about 30,000 lines of library code, demonstrating a combination of scalability and precision.

String Analysis for Dynamic Field Access

Magnus Madsen
Mar. 28, 2014
In JavaScript, and scripting languages in general, dynamic field access is a commonly used feature. Unfortunately, current static analysis tools either completely ignore dynamic field access or use overly conservative approximations that lead to poor precision and scalability. We present new string domains to reason about dynamic field access in a static analysis tool. A key feature of the domains is that the equal, concatenate and join operations take O(1) time.

Experimental evaluation on four common JavaScript libraries, including jQuery and Prototype, shows that traditional string domains are insufficient. For instance, the commonly used constant string domain can only ensure that at most 21% dynamic field accesses are without false positives. In contrast, our string domain H ensures no false positives for up to 90% of all dynamic field accesses.

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

Shahram Esmaeilsabzali
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.

http://www.research.ibm.com/liquidmetal/

Constructing Call Graphs of Scala Programs

Karim Ali
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

Siddharth Subramanian
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 (0.97) and supports both Java and JavaScript. Baker can be used 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

Marianna Rapoport
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.