Copenhagen Programming Language
Shifting the Stage: Staging with Delimited Control
Monday, November 3, 2008, 15:30-16:30
DIKU South, Njalsgade 128, 2300 Copenhagen S, Room 24.5.62
It is often hard to write programs that are efficient yet reusable.
For example, an efficient implementation of Gaussian elimination
should be specialized to the structure and known static properties of
the input matrix. The most profitable optimizations, such as choosing
the best pivoting or memoization, cannot be expected of even an
advanced compiler because they are specific to the domain, but
expressing these optimizations directly makes for ungainly source
code. Instead, a promising and popular way to reconcile efficiency
with reusability is for a domain expert to write code generators.
Two pillars of this approach are types and effects. Typed multilevel
languages such as MetaOCaml ensure safety: a well-typed code
generator neither goes wrong nor generates code that goes wrong. Side
effects such as state and control ease correctness: an effectful
generator can resemble the textbook presentation of an algorithm, as
is familiar to domain experts, yet insert let for memoization and
if for bounds-checking, as is necessary for efficiency. However,
adding effects blindly renders multilevel types unsound.
We introduce the first two-level calculus with control effects and a
sound type system. We give small-step operational semantics as well
as a continuation-passing style (CPS) translation. For soundness,
our calculus restricts the code generator's effects to the scope of
generated binders. Even with this restriction, we can finally write
efficient code generators for dynamic programming and numerical methods
in direct style, like in algorithm textbooks, rather than in CPS or
(Joint work with Yukiyoshi Kameyama and Oleg Kiselyov.)
Scientific host:Torben Mogensen Administrative host:
All are welcome.
The Copenhagen Programming
Language Seminar (COPLAS) is a collaboration between DIKU,
ITU, KVL and
COPLAS is sponsored by the FIRST Graduate School.
To receive information about COPLAS talks by email, send a message to
email@example.com with the word 'subscribe' as subject or in the body.
For more information about COPLAS, see