Waterloo Programming Languages Seminars

Previous terms: F06 S06 W06

Current term:

Date Speaker Title (click for abstract) Location
Jan. 17, 2007 Nomair Naeem Precise and Efficient Must-Alias Analysis DC 3313
Jan. 24, 2007 Peter Kim On-Demand Materialization of Aspects for Multilevel Customization DC 3313
Jan. 31, 2007 Nomair Naeem Continuation of Precise and Efficient Must-Alias Analysis DC 3313
Feb. 14, 2007 No seminar this week No seminar this week DC 3313
Feb. 28, 2007 Brad Lushman Unknowns---Not Quite Variables, Not Quite Constants DC 3313
Mar. 14, 2007 No seminar this week No seminar this week DC 3313
Mar. 21, 2007 Michael McCool The RapidMind Development Platform and Parallel Programming Model DC 3313
Mar. 28, 2007 No seminar this week No seminar this week DC 3313

Seminars are Wednesdays at 2:30 pm, unless otherwise indicated.

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.


Continuation of Precise and Efficient Must-Alias Analysis

Nomair Naeem
Jan. 31, 2007
Must-alias information tells us when two pointers must point to the same location. Although precise must-alias analysis can significantly improve the performance of compiler optimizations, until recently little work had been done in this field due to the high cost of the said analyses. In this talk we discuss two recent papers dealing with efficient must-alias information. We survey: "Compile time deallocation of Individual objects" (Cherem and Rugina, ISMM'06) and "Effective typestate verification in the presence of aliasing" (Fink et. al., ISSTA'06).

An inspection of the two approaches shows the importance of modeling individual heap locations to get efficient must-alias information. We derive similarities and differences in the two implementations and come to the conclusion that the two approaches can be easily combined to produce an even better must-alias analysis.

Unknowns---Not Quite Variables, Not Quite Constants

Brad Lushman
Feb. 28, 2007
Unification is the well-known problem (with well-known solutions) of solving systems of equations in some term algebra. Semiunification is a more general problem, in which we also admit term inequalities---an inequality tau <= mu is considered satisfied if for some substitution S, mu S is a substitution instance of tau S. In other words, extra substitutions are allowed on the left-hand side of the inequality. Notable among SUP's applications are its connections to various polymorphic type systems.

Within semiunification problem (SUP) instances, there are two classes of identifiers: variables and functors. Variables may be the targets of substitutions as part of the solution process for SUP; functors may not. Constants may be viewed as nullary functors. We present a new generalization of SUP, in which we introduce a third class of identifier---the unknown. Unknowns are like variables, in that they may be the targets of substitutions, but like functors, since semantically, they are to be regarded as constants. Moreover, a single identifier may play the role of unknown over part of a SUP instance, and of variable over the rest.

We show that the known decidable subsets of SUP, and indeed even the full SUP itself, are not appropriate targets for a full syntax-directed translation from typability in rank-2 System F to a set of unification-style constraints. Instead, a translation to SUP with unknowns (which we call USUP) provides a much more natural target. We present a formal definition of USUP, detail the new reduction rules for solving instances with unknowns, and outline the connection between unknowns and monomorphic abstractions with broad scope.

The RapidMind Development Platform and Parallel Programming Model

Michael McCool
Mar. 21, 2007
Massively multi-core processors such as GPUs and the Cell BE have the potential to deliver high performance computation to many applications. However, these processors require parallel programming on several levels and have some novel architectural features. The RapidMind development platform enables portable access to the power of these processors. It provides a simple, safe, data-parallel model of execution and takes care of many of the low-level details of mapping this processing model to each hardware target. It combines a dynamic compiler with a runtime streaming execution manager, and provides a single system image for computations running on any number of cores. The interface to this system is embedded inside ISO standard C++, where it can capture arbitrary computations specified at runtime. The use of a dynamic compiler means that high-level C++ abstractions can be used without sacrificing performance.