LOLA 2010

Syntax and Semantics of Low Level Languages

Friday 9th July 2010, Edinburgh, Scotland, U.K.

A satellite workshop of Logic in Computer Science (LICS 2010).

It has been understood since the late 1960s that tools and structures arising in mathematical logic and proof theory can usefully be applied to the design of high level programming languages, and to the development of reasoning principles for such languages. Yet low level languages, such as machine code, and the compilation of high level languages into a low level ones have traditionally been seen as having little or no essential connection to logic.

However, a fundamental discovery of this past decade has been that low level languages are also governed by logical principles. From this key observation has emerged an active and fascinating new research area at the frontier of logic and computer science. The practically-motivated design of logics reflecting the structure of low level languages (such as heaps, registers and code pointers) and low level properties of programs (such as resource usage) goes hand in hand with the some of the most advanced contemporary researches in semantics and proof theory, including classical realizability and forcing, double orthogonality, parametricity, linear logic, game semantics, uniformity, categorical semantics, explicit substitutions, abstract machines, implicit complexity and sublinear programming.

The LOLA workshop, affiliated with LICS, will bring together researchers interested in many aspects of the relationship between logic and low level languages and programs. Topics of interest include, but are not limited to:

- Typed assembly languages,
- Certified compilation,
- Proof-carrying code,
- Program optimization,
- Modal logic and realizability in machine code,
- Realizability and double orthogonality in assembly code,
- Implicit complexity, sublinear programming and Turing machines,
- Parametricity, modules and existential types,
- General references, Kripke models and recursive types,
- Closures and explicit substitutions,
- Linear logic and separation logic,
- Game semantics, abstract machines and hardware synthesis,
- Monoidal and premonoidal categories, traces and effects.

Invited Speakers :

• Gérard Berry (INRIA, Collège de France)
  
  What could be the right balance between abstract and fine-grain computational properties?

• Alex Simpson (LFCS, Edinburgh University)
  
  Linear types for continuations

Invited Tutorial :

• Dan Ghica (University of Birmingham)
  
  Geometry of Synthesis: Semantics-directed hardware compilation

Program of the workshop:

08.50 – 09.00 : Reception

09.00 – 10.00 : Invited talk

Gérard Berry (INRIA, Collège de France)
What could be the right balance between abstract and fine-grain computational properties?

10.00 – 10.30 : Coffee break

10.30 – 11.30 : Invited tutorial

Dan Ghica (University of Birmingham)
Geometry of Synthesis: Semantics-directed hardware compilation

11.30 – 12.00

Magnus O. Myreen & Michael J. C. Gordon
Machine code: architecture-independent formal verification and proof-producing compilation

12.00 – 12.30

Ugo Dal Lago
On the Role of Interaction in Implicit Computational Complexity

12.30 – 14.00 : Lunch

14.00 – 15.00 : Invited talk

Alex Simpson (LFCS, University of Edinburgh)
Linear types for continuations

15.00 – 15.30 : Coffee break

15.30 – 15.50

Nick Benton & Chung-Kil Hur
Step-Indexing: The Good, the Bad and the Ugly

15.50 – 16.10

Guilhem Jaber & Nicolas Tabareau
Krivine realizability for compiler correctness

16.10 – 16.30

Shin-ya Katsumata & Rasmus Mogelberg
Fullness of monadic translation by TT-lifting

16.30 – 17.00 : Panel discussion

17.00 – 17.20

Rasmus Mogelberg & Sam Staton
Full abstraction in a metalanguage for state

17.20 – 17.40

Antoine Madet & Roberto Amadio & Patrick Baillot
An Affine-Intuitionistic System of Types and Effects: Confluence and Termination

17.40 – 18.00

Nathaniel Charlton & Bernhard Reus
A deeper understanding of the deep frame axiom

Program Committee:

• Amal Ahmed (Indiana University)

• Nick Benton (MSR Cambridge, co-chair)

• Lars Birkedal (IT University of Copenhagen)

• Dan Ghica (University of Birmingham)

• Paul-André Melliès (CNRS & Université Paris Diderot, co-chair)

• François Pottier (INRIA)

• Ulrich Schöpp (LMU Munich)

• Hayo Thielecke (University of Birmingham)

Submission instructions:

LOLA is an informal workshop aiming at a high degree of useful interaction amongst the participants, welcoming proposals for talks on work in progress, overviews of larger programmes, position presentations and short tutorials as well as more traditional research talks describing new results.

The programme committee will select the workshop presentations from submitted proposals, which may take the form either of a short abstract or of a longer (published or unpublished) paper describing completed work.

The submissions will be made by easychair at LOLA submission site until Monday 19th April 2010, included.

Important dates:

• Deadline for submission : Monday 19th April 2010

• Notification to the authors : Saturday 1st May 2010

• Workshop : Friday 9th July 2010

Contact:

Please contact us at lola2010@easychair.org for any additional information.