PL Colloquium Series

Our weekly meeting and talk series, known affectionately as “PL-wonks”, is open to everyone interested in discussing programming languages research happening here at IU. Our talks include original research, experience reports, and tutorials. We also sometimes present papers from the literature that we're interested in.

Unless otherwise noted, PL talks happen every Friday at 4:15pm in Lindley Hall Room 101. All are welcome to attend. We have a tradition of baking cookies and other treats for our meetings.

At this meeting, we'll have four practice talks leading up to the Off the Beaten Track workshop at POPL:

• Language Design: A Cognitive Science Approach (Mike Hansen)
• Revisiting APL in the Modern Era (Aaron W. Hsu)
• Rule-Based Interactive Fiction (Chris Martens)
• Embracing the Laws of Physics (Amr Sabry)

Speaker: Zach Sparks

Most widely-used programming languages have some mechanism that allows programmers to write modular code. Haskell's typeclass system in particular seems quite popular, as it allows programmers to take advantage of abstract types with low syntactic overhead.

In this talk, I will give a brief introduction to ML-style module systems, specifically using the one implemented in the SML/NJ compiler. Starting from “representation-independent” dynamically typed code, I will show how to use the module system to achieve true representation independence. The main tools needed to do this are abstract types, submodules, and functors; if there is time, I may also demonstrate some of the more advanced features of the module system.

Speaker: Yin Wang

In this talk, I will discuss the design of a structural comparison tool for programs which compare programs not by their text, but by their parse tree structures. I will give demos for structural editing and structural comparison. I will talk about their design space and the algorithms used in structural comparison: Tree Editing Distance, Substructure Extraction. I will show how to implement those algorithms with simple and efficient functional programs. I will also discuss the design of a parser combinator library in Scheme, and the lessons learned from my experience of writing parsers for JavaScript and C++. In the end, I will propose a design of a structural version control system based on the ideas of structural comparison.

Slides:

http://www.cs.indiana.edu/~yw21/slides/ydiff-slides.pptx

http://www.cs.indiana.edu/~yw21/slides/ydiff-slides.pdf

Speaker: Wren Thornton

Unification has many diverse applications, from logic programming and implementing type analysis, to parsing natural language and performing case analysis for algebraic data types. However, naive implementation is horrifically inefficient. The inefficiencies are not due to mere constant factors, but rather unification plays on the boundary of decidability and the unwary can easy fall prey to a number of asymptotic inefficiencies. These inefficiencies and many optimizations to avoid them are well-known within the community, but this knowledge is folklore and seldom written down or taught. I will be sharing some of these folklore techniques, as well as a few optimizations which are (to my knowledge) novel.

Slides:

http://llama.freegeek.org/~wren/pubs/unification-intro-mcmaster.pdf

http://llama.freegeek.org/~wren/pubs/unification-opt-mcmaster.pdf

Haskell implementation:

http://hackage.haskell.org/package/unification-fd

Speaker: William E. Byrd

Declarative languages allow programmers to specify *what* a program should do, without specifying *how* to do it. Expressing the “what”, and leaving the “how” to the compiler and runtime system, leads to shorter, simpler, and safer programs. The declarative approach is especially promising for difficult programming tasks, which is why declarative programming has been popular in artificial intelligence research for decades. One notoriously difficult task is the programming of multi-core and multi-processor computers, which are now found not only in supercomputers, but also laptops, cell phones, and gaming consoles. Graphics processors (GPUs) are essentially parallel supercomputers, and are also difficult to program. The recent introduction of hybrid CPU/GPU clusters adds even more complexity.

To address the complexity of programming modern parallel hardware, my colleagues and I in the Declarative Parallel Programming project at Indiana University are developing two related declarative languages: Kanor, a language for specifying collective communication on clusters; and Harlan, a language for describing computational kernels on GPUs and other accelerators.

I will describe how Kanor allows programmers to declaratively, but explicitly, specify the essence of communication patterns. The programmer lets the implementation handle the details when appropriate, but retains the option to hand-encode communications when necessary, providing a balance between declarativeness and performance predictability and tunability. Similarly, Harlan allows the user to declaratively, but explicitly, describe computational kernels and to coordinate computation, data layout, and memory movement. As with Kanor, this approach gives the programmer enough control to write efficient code, while abstracting over the low-level details that make GPU programming so difficult. Integrating Harlan into Kanor results in a unified, high-level, flexible language suitable for efficiently programming hybrid clusters, traditional (CPU-based) clusters, and GPUs on a single machine.

Speaker: Aaron W. Hsu

Concurrent Collections is a dataflow style parallel programming model that utilizes single-assignment global stores to achieve deterministic behavior. It allows one to describe task parallelism through high-level, declarative descriptions. In this talk I will introduce CnC and describe my research in extending the language to enable richer analysis of the data access patterns described by CnC programs. Hopefully, there will also be a demo.

Speaker: Eric Holk

Regions are a means of combining many objects into a single unit of memory allocation. As a form of memory management, they provide many of the efficiency benefits of stack allocation, yet regions also provide more flexibility for objects that outlive their stack frame. Although conceptually simple, regions have proven useful in a variety of applications. The Apache web server uses regions to amortize the cost of deallocation for large data structures. Regions have been used in ML to statically place allocation and deallocation points and avoid the need for a tracing garbage collector. Cyclone uses regions to eliminate dangling pointer references.

In my talk, I will provide a brief overview of region-based memory management, including approaches to region influence. I will discuss how different projects have used regions to achieve their goals. Finally, I will provide some speculation on how regions might be used to support richer data structures and efficient memory movement for GPU computing in Harlan.

Speaker: Rebecca Swords

These three mythical beasts each provide a different interface for composing (possibly effectful) computations. In the presence of side effects, they also give us a way to identify code that may be “infected” by these effects. What exactly is the relationship between these three concepts? What characteristics differentiate monads from arrows and applicative functors (also known as idioms), and why would we want to have all three?

In order to actually use a monad, arrow, or applicative functor, we have to have a concrete instance: for example, the State or Maybe monads. Each instantiation must obey certain laws in order to qualify as a valid implementation. What are these laws? More importantly, given one of these concrete instantiations for a monad, can we translate it into an instance of an arrow or applicative functor, or vice versa?

I will be giving an introduction to monads, arrows, and applicative functors; discussing the relationships between the three; and offering answers to the questions posed above.

Speaker: Lindsey Kuper

Kahn process networks, Haskell's monad-par library, and Intel's Concurrent Collections language are three diverse examples of deterministic-by-construction models of parallel computation. In a deterministic-by-construction model, all programs written using the model are guaranteed to behave deterministically, so they offer programmers the promise of freedom from subtle, hard-to-reproduce nondeterministic bugs like race conditions.

As I'll show in my talk, the determinism of all of these models hinges on a notion of monotonic data structures—data structures in which mutators may only add information, never destroy it. In each case, a monotonicity property on some data structure captures the essence of why the model is deterministic. With monotonic data structures as a guiding principle, then, we should be able to develop a deterministic parallel programming model that is general enough to express existing models, as well as guide the design of new ones. Ryan Newton, Amr Sabry, and I are working on developing such a model, and I'll discuss what we've accomplished so far and where we're headed next. (Warning to implementors: this talk may contain theorems and inference rules! Warning to theorists: this talk may contain running code!)

Speaker: Andy Keep

Many languages include a syntax for declaring programmer-defined structured data types, i.e., structs or records. At a minimum, the syntax defines the record's name and a set of named fields. Because it is defined syntactically, the compiler can open-code allocation operations and compile field references and assignments into single memory references, with field offsets calculated at compile time. R6RS supports syntactic record definitions but also allows records to be defined procedurally, i.e., via a set of run-time operations. Indeed, the procedural interface is considered to be the primitive interface, and the syntactic interface is designed to be macro expandable into code that uses the procedural interface.

The procedural layer allows arbitrary new record types to be created at run time, facilitating the creation of portable interpreters that interoperate with compiled code. It also supports the creation of portable printers and debuggers, which can obtain an RTD from a record instance and use it to access or even modify the fields of the instance. This added flexibility comes at a potentially substantial cost, since the information required to open-code allocation, field reference, and field assignment operations is not generally available until run time. In many cases, however, such as when the record operators are produced by the syntactic interface, the information can be determined statically, enabling the generation of efficient code. In this talk, I (briefly) describe the syntactic, procedural, and inspection layers of the record system and then describe how Chez Scheme utilizes cp0 to generate efficient record code.

Speaker: Kyle Blocher

K is a rewrite-based executable semantic framework in which programming languages, type systems and formal analysis tools can be defined using configurations, computations and rules. Configurations organize the state in units called cells, which are labeled and can be nested. Computations carry computational meaning as special nested list structures sequentializing computational tasks, such as fragments of program. Computations extend the original language abstract syntax. K (rewrite) rules make it explicit which parts of the term they read-only, write-only, read-write, or do not care about. This makes K suitable for defining truly concurrent languages even in the presence of sharing. Computations are like any other terms in a rewriting environment: they can be matched, moved from one place to another, modified, or deleted. This makes K suitable for defining control-intensive features such as abrupt termination, exceptions or call/cc.

Speaker: Chris Frisz

Tail-call optimization allows programmers to write interesting tail-recursive functions without worry of overflowing the program's stack memory. This is achieved by reusing the stack frame of the calling function for the recursive call. A number of languages, such as Scheme and Standard ML, require tail-call optimization as part of their language standards, making tail-recursion a primary means of iteration in these languages. In this talk we discuss the state of tail-call optimization in Clojure, a Lisp dialect targeting the JVM. Specifically, we examine the language's current limitation on constant-space tail calls that are only available to programmers through manual code transformations. We then present a method to extend support for tail-call optimization to arbitrary mutual recursion via well-known code transformations such as CPS and trampolining. Finally, we present a prototype for a source-to-source compiler embedded in Clojure for performing these transformations.

Speaker: Adam Foltzer

Modern parallel computing hardware demands increasingly specialized attention to the details of scheduling and load balancing across heterogeneous execution resources that may include GPU and cloud environments, in addition to traditional CPUs. Many existing solutions address the challenges of particular resources, but do so in isolation, and in general do not compose within larger systems. We propose a general, composable abstraction for execution resources, along with a continuation-based meta-scheduler that harnesses those resources in the context of a deterministic parallel programming library for Haskell. We demonstrate performance benefits of combined CPU/GPU scheduling over either alone, and of combined multithreaded/distributed scheduling over existing distributed programming approaches for Haskell.

This will be a short talk (~20 minutes) to practice for a possible future presentation in a conference venue. As such, I'd very much appreciate feedback on presentation style and delivery in addition to comments on the substance of the work. This is joint work with Abhishek Kulkarni, Rebecca Swords, Sajith Sasidharan, Eric Jiang, and Ryan R. Newton.

Speaker: Cameron Swords

Software contracts provide a mechanism for programmers to safely provide libraries and quickly pinpoint program errors by specifying certain pre- and post-conditions for function calls. A number of features and extensions have been developed for the field, such as lazy and temporal contracts. Each of these features contributes a new mechanism for contract implementation and evaluation, providing a number of unique approaches to contract enforcement. In this talk we introduce and discuss the state of these extensions, demonstrating the limitations and errors that exist in current implementations. We present the generally-accepted criterion for effective contract implementations and demonstrate how each implementation we consider fails to fulfill one of these requirements.

Speaker: Will Byrd

After much cheesing, ROFL-stomping, and obsessive laddering, I'll finally be giving my long-promised talk on StarCraft, the greatest and most addictive game ever made.

• Fall 2011 archive
• Spring 2011 archive
• Fall 2010 archive

For older talks, please refer to the announcements in the PL-wonks archives.