Programming Language Semantics Seminar, 1998-99

Mitchell Wand
College of Computer Science, Northeastern University
360 Huntington Avenue #161CN,
Boston, MA 02115
Internet: wand@ccs.neu.edu
Phone: (617) 373-2072 / Fax: (617) 373-5121

[Semantics at NU | College of Computer Science | Northeastern University]

Current schedule


Wednesday, 7 June 1999 (10 o'clock until noon, in 206 Egan)

Galen Williamson will continue his presentation of

Jonathan Sobel, Erik Hilsdale, R. Kent Dybvig, and Daniel P. Friedman, Abstraction and Performance from Explicit Monadic Reflection.


Wednesday, 26 May 1999 (10 o'clock until noon, in 206 Egan)

Galen Williamson will present

Jonathan Sobel, Erik Hilsdale, R. Kent Dybvig, and Daniel P. Friedman, Abstraction and Performance from Explicit Monadic Reflection.

Abstract:

Much of the monadic programming literature gets the types right but the abstraction wrong. Using monadic parsing as the motivating example, we demonstrate standard monadic programs in Scheme, recognize how they violate abstraction boundaries, and recover clean abstraction crossings through monadic reflection. Once monadic reflection is made explicit, it is possible to construct a grammar for monadic programming. This grammar, in turn, enables the redefinition of the monadic operators as macros that eliminate at expansion time the overhead imposed by functional representations. The result is very efficient monadic programs; for parsing, the output code is competitive with good handcrafted parsers.


Wednesday, 19 May 1999 (10 o'clock until noon, in 206 Egan)

Will Clinger will present

Christian Collberg and Clark Thomborson, Software Watermarking: Models and Dynamic Embeddings. PLDI '99.

Abstract:

Watermarking embeds a secret message into a cover message. In media watermarking the secret is usually a copyright notice and the cover a digital image. Watermarking an object discourages intellectual property theft, or when such theft has occurred, allows us to prove ownership.

The Software Watermarking problem can be described as follows. Embed a structure W into a program P such that W can be reliably located and extracted from P even after P has been subjected to code transformations such as translation, optimization and obfuscation; W is stealthy; W has a high data rate; embedding W into P does not adversely affect the performance of P; and W has a mathematical structure that allows us to argue that its presence in P is the result of deliberate actions.

In the first part of the paper we construct an informal taxonomy of software watermarking techniques. In the second part we formalize these results. Finally, we propose a new software watermarking technique in which a dynamic graphic watermark is stored in the execution state of a program.


Wednesday, 12 May 1999 (10 o'clock until noon, in 206 Egan)

Johan Ovlinger will present

Ralf Lammel, Declarative Aspect Oriented Programming.

Johan's abstract:

The term "aspect oriented programming" has been kicked around the OO community for some time now, and I've long wanted to get a better grasp of what it means. This paper presents a version of AOP for a declarative language, which hopefully will help me figure out AOP.


Wednesday, 5 May 1999 (10 o'clock until noon, in 206 Egan)

Will Clinger will present

Ole Agesen, David Detlefs, and J Eliot B Moss, Garbage Collection and Local Variable Type-Precision and Liveness in Java (TM) Virtual Machines. Proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and Implementation (PLDI), pages 269--279.

Full precision in garbage collection implies retaining only those heap allocated objects that will actually be used in the future. Since full precision is not computable in general, garbage collectors use safe (i.e. conservative) approximations such as reachability from a set of root references. Ambiguous roots collectors (commonly called "conservative") can be overly conservative because they overestimate the root set, and thereby retain unexpectedly large amounts of garbage. We consider two more precise collection schemes for Java virtual machines (JVMs). One uses a type analysis to obtain a type-precise root set (only those variables that contain references); the other adds a live variable analysis to reduce the root set to only the live reference variables. Even with the Java programming language's strong typing, it turns out thtat the JVM specification has a feature that makes type-precise root sets difficult to compute. We explain the problem and ways in which it can be solved.

Our experimental results include measurements of the cost of the type and liveness analyses at load time, of the incremental benefits at run time of the liveness analysis over the type analysis alone, and of various map sizes and counts. We find that the liveness analysis often produces little or no improvement in heap size, sometimes modest improvements, and occasionally the improvement is dramatic. While further study is in order, we conclude that the main benefit of liveness analysis is preventing bad surprises.


Wednesday, 28 April 1999 (10 o'clock until noon, in 206 Egan)

Lars Hansen will present

Matteo Frigo, Charles E. Leiserson, Keith H. Randall, The Implementation of the Cilk-5 Multithreaded Language. Proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and Implementation (PLDI), pages 212--223.

The fifth release of the multithreaded language Cilk uses a provably good "work-stealing" scheduling algorithm similar to the first system, but the language has been completely redesigned and the runtime system completely reengineered. The efficiency of the new implementation was aided by a clear strategy that arose from a theoretical analysis of the scheduling algorithm: concentrate on minimizing overheads that contribute to the work, even at the expense of overheads that contribute to the critical path. Although it may seem counterintuitive to move overheads onto the critical path, this "work-first" principle has led to a portable Cilk-5 implementation in which the typical cost of spawning a parallel thread is only between 2 and 6 times the cost of a C function call on a variety of contemporary machines. Many Cilk programs run on one processor with virtually no degradation compared to equivalent C programs. This paper describes how the work-first principle was exploited in the design of Cilk-5's compiler and its runtime systems. In particular, we present Cilk-5's novel "two-clone" compilation strategy and its Dijkstra-like mutual-exclusion protocol for implementing the ready deque in the work-stealing scheduler.


Wednesday, 21 April 1999 (10 o'clock until noon, in 206 Egan)

Will Clinger will present

Andrew Ayers, Robert Gottlieb, and Richard Schooler (all of HP Chelmsford), Aggressive Inlining. Proceedings of the ACM SIGPLAN '97 Conference on Programming Language Design and Implementation (PLDI), pages 134-145.

Abstract: Existing research understates the benefits that can be obtained from inlining and cloning, especially when guided by profile information. Our implementation of inlining and cloning yields excellent results on average and very rarely lowers performance. We believe our good results can be explained by a number of factors: inlining at the intermediate-code level removes most technical restrictions on what can be inlined; the ability to inline across files and incorporate profile information enables us to choose better inline candidates; a high-quality back end can exploit the scheduling and register allocation opportunities presented by larger subroutines; an aggressive processor architecture benefits from more predictable branch behavior; and a large instruction cache mitigates the impact of code expansion. We describe the often dramatic impact of our inlining and cloning on performance: for example, the implementation of our inlining and cloning algorithms in the HP-UX 10.20 compilers boost SPECint95 performance on a PA8000-based workstation by a factor of 1.32.


Wednesday, 14 April 1999 (10 o'clock until noon, in 149 Cullinane)

Mitch Wand will give an informal talk on some open problems.


Wednesday, 3 March 1999 (10 o'clock until noon, in 206 Egan)

Greg Sullivan will continue his presentation of

Oscar Waddell and R. Kent Dybvig, Extending the Scope of Syntactic Abstraction. Conference Record of POPL'99: The 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. January 1999.


Wednesday, 24 February 1999 (10 o'clock until noon, in 206 Egan)

Greg Sullivan will present

Oscar Waddell and R. Kent Dybvig, Extending the Scope of Syntactic Abstraction. Conference Record of POPL'99: The 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. January 1999.

Abstract: The benefits of module systems and lexically scoped syntactic abstraction (macro) facilities are well-established in the literature. This paper presents a system that seamlessly integrates modules and lexically scoped macros. The system is fully static, permits mutually recursive modules, and supports separate compilation. We show that more dynamic module facilities are easily implemented at the source level in the extended language supported by the system.

Will


Friday, 19 February 1999 (10 o'clock until noon, in 206 Egan)

Tim Sheard of the Oregon Graduate Institute will present a talk on staged programming and MetaML.

Abstract:

The purpose of staged programming in general, and MetaML in particular, is to produce efficient programs. We wish to move beyond programs that compute the "correct" output, to those that also have better control over resources (both space and time). The mechanism for doing this is to use program annotations to control the order of evaluation of terms. MetaML allows programmers to move beyond a fixed evaluation strategy, and to specify precisely the desired evaluation order.

This provides a mechanism which allows general purpose programs (written in an interpretive style that eases both maintenance and construction) to perform without the interpretive overhead usually associated with such programs.

Tim Sheard is an Associate Professor of Computer Science at the Oregon Graduate Institute, and a founding member of the Pacific Software Research Center. The Center explores techniques for improving processes for software development, including the use of high-level languages, design automation tools for software generation, and formal methods for specification, analysis and verification. Tim Sheard is currently on sabbatical at Yale University.


Wednesday, 27 January 1999 ten o'clock to noon in 206 Egan (see below)

Will Clinger will present "Implementation Strategies for First-Class Continuations", by Clinger, Hartheimer, and Ost, to appear in HOSC (formerly LaSC).

Abstract:

Scheme and Smalltalk continuations may have unlimited extent. This means that a purely stack-based implementation of continuations, as suffices for most languages, is inadequate. We review several implementation strategies for continuations and compare their performance using instruction counts for the normal case and continuation-intensive synthetic benchmarks for other scenarios, including coroutines and multitasking. All of the strategies constrain a compiler in some way, resulting in indirect costs that are hard to measure directly. We use related measurements on a set of benchmarks to calculate upper bounds for these indirect costs.


Wednesday, 13 January 1999 10 o'clock until noon

Eliot Moss of the University of Massachusetts (Amherst) will give a talk based on Darko Stefanovic's recent PhD thesis (under Moss's direction) on "Properties of Age-Based Automatic Memory Reclamation Algorithms".

Abstract:

Dynamic memory management enables a programmer to allocate objects for arbitrary preiods of time. It is an important feature of modern programming languages, and is fundamental to object-oriented languages. Automatic reclamation, also known as garbage collection, automates the detection of the time when a data item can no longer be used.

The work described herein considers garbage collection algorithms that base their decisions solely upon the relative age of data. This age-based class of algorithms generalizes previously defined generational garbage collection algorithms and includes promising new algorithms. The work identifies relevant performance factors and reports them for a set of object-oriented benchmark programs, establishing a fair comparison by imposing uniform maximum space constraints. A precise tracing and garbage collection algorithm evaluation framework provides accurate results and thus meaningful comparisons.

The results indicate, contrary to assumptions in the literature, that the new algorithms copy less data than the generational algorithms, even though they retain a higher percentage of reclaimable data. In agreement with the assumptions in the literature, the results indicate that generational algorithms do less pointer-tracking work. Thus, given suitable relative costs of copying and pointer-tracking, the new algorithms perform better. Estimations of the relative costs for a typical modern processor suggest that the new algorithms are usually superior.


Wednesday, 9 December 1998

Allyn Dimock continues his presentation of "Monotone Data Analysis Frameworks" by Kam & Ullman (Acta Informatica 7, 305-317. 1977), and from "A Unified Approach To Global Program Optimization" by Kildall (POPL 1973).


Wednesday, 2 December 1998

Allyn Dimock will present material from "Monotone Data Analysis Frameworks" by Kam & Ullman (Acta Informatica 7, 305-317. 1977), and from "A Unified Approach To Global Program Optimization" by Kildall (POPL 1973).

Abstract:

Intuitive understanding of dataflow analysis is based on considering solutions that are safe at a program point no matter what path out of a potentially infinite set of paths through the program was taken to reach that program point. The "Meet Over all Paths" _MOP_ solution is the least restrictive such solution.

Kildall's algorithm for data flow analysis (still in use today in varying forms) computes a "Greatest Fixed Point" _GFP_ solution, and shows that his algorithm terminates and approximates the MOP solution.

Kam and Ullman show that GFP is equal to MOP if and only if the dataflow transfer functions are "distributive": f(a ^ b) = f(a) ^ f(b) They also show that the MOP solution is not recursive.


Wednesday, 18 November 1998

Arthur Nunes will finish his presentation of Amr Sabry and Matthias Felleisen's paper "Reasoning about Programs in Continuation Passing Style", from Lisp and Symbolic Computation, 1994.

Abstract:

Plotkin's lambda_v-calculus for call by value programs is weaker than the lambda-beta-eta calculus for the same programs in CPS. To identify the call by value axioms that correspond to beta-eta on CPS terms, we define a new CPS transformation and an inverse mapping, both of which are interesting in their own right. Using the new CPS transformations, as well as the call by value axioms that correspond to the administrative beta-eta reductions on CPS terms. Using the inverse mapping, we map the remaining beta and eta equalities on CPS terms to axioms on call by value terms. On the pure set of Lambda terms, the resulting set of axioms is equivalent to Moggi's computational lambda calculus. If the call by value language includes control operators abort and call/cc, the axioms are equivalent to an extension of Felleisen et al's lambda_v-C calculus and to the equational subtheory of Talcott's logic IOCC.


Wednesday, 4 November 1998

Will Clinger will finish his presentation of "Compiling Standard ML to Java Bytecodes", from ICFP '98, by Nick Benton, Andrew Kennedy, and George Russell.

Then Arthur Nunes will begin his presentation of Amr Sabry and Matthias Felleisen's paper "Reasoning about Programs in Continuation Passing Style", from Lisp and Symbolic Computation, 1994.

Abstract:

Plotkin's lambda_v-calculus for call by value programs is weaker than the lambda-beta-eta calculus for the same programs in CPS. To identify the call by value axioms that correspond to beta-eta on CPS terms, we define a new CPS transformation and an inverse mapping, both of which are interesting in their own right. Using the new CPS transformations, as well as the call by value axioms that correspond to the administrative beta-eta reductions on CPS terms. Using the inverse mapping, we map the remaining beta and eta equalities on CPS terms to axioms on call by value terms. On the pure set of Lambda terms, the resulting set of axioms is equivalent to Moggi's computational lambda calculus. If the call by value language includes control operators abort and call/cc, the axioms are equivalent to an extension of Felleisen et al's lambda_v-C calculus and to the equational subtheory of Talcott's logic IOCC.


Wednesday, 28 October 1998

pl-seminar resumes (in new location; see below)

Mitch, Will, and whoever else would like to speak will start off with short presentations about open problems of current interest.

Then Will Clinger will present "Compiling Standard ML to Java Bytecodes", from ICFP '98, by Nick Benton, Andrew Kennedy, and George Russell.

Abstract:

MLJ compiles SML'97 into verifier-compliant Java bytecodes. Its features include type-checked interlanguage working extensions which allow ML and Java code to call each other, automatic recompilation management, compact compiled code and runtime performance which, using a `just in time' compiling Java virtual machine, usually exceeds that of existing specialised bytecode interpreters for ML. Notable features of the compiler itself include whole-program optimization based on rewriting, compilation of polymorphism by specialisation, a novel monadic intermediate language which expresses effect information in the type system and some interesting data representation choices.