PRL recently produced three papers for the SNAPL conference.

• Linking Types for Multi-Language Software: Have Your Cake and Eat It Too, by Daniel Patterson and Amal Ahmed.
• Search for Program Structure, by Gabriel Scherer
• Migratory Typing: Ten Years Later, by Sam Tobin-Hochstadt, Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, Ben Greenman, Andrew M. Kent, Vincent St-Amour, T. Stephen Strickland and Asumu Takikawa

Linking Types for Multi-Language Software: Have Your Cake and Eat It Too

Daniel Patterson and Amal Ahmed, 2017

Software developers compose systems from components written in many different languages. A business-logic component may be written in Java or OCaml, a resource-intensive component in C or Rust, and a high-assurance component in Coq. In this multi-language world, program execution sends values from one linguistic context to another. This boundary-crossing exposes values to contexts with unforeseen behavior—that is, behavior that could not arise in the source language of the value. For example, a Rust function may end up being applied in an ML context that violates the memory usage policy enforced by Rust’s type system. This leads to the question of how developers ought to reason about code in such a multi-language world where behavior inexpressible in one language is easily realized in another.

This paper proposes the novel idea of linking types to address the problem of reasoning about single-language components in a multi-lingual setting. Specifically, linking types allow programmers to annotate where in a program they can link with components inexpressible in their unadulterated language. This enables developers to reason about (behavioral) equality using only their own language and the annotations, even though their code may be linked with code written in a language with more expressive power.

Search for Program Structure

Gabriel Scherer, 2017.

The community of programming language research loves the Curry-Howard correspondence between proofs and programs. Cut-elimination as computation, theorems for free, ‘call/cc’ as excluded middle, dependently typed languages as proof assistants, etc.

Yet we have, for all these years, missed an obvious observation: “the structure of programs corresponds to the structure of proof search”. For pure programs and intuitionistic logic, more is known about the latter than the former. We think we know what programs are, but logicians know better!

To motivate the study of proof search for program structure, we retrace recent research on applying the logical technique of focusing to study the canonical structure of simply-typed λ-terms. We then motivate the open problem of extending canonical forms to support richer type systems, such as polymorphism, by discussing a few enticing applications of more canonical program representations.

Migratory Typing: Ten Years Later

Sam Tobin-Hochstadt, Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, Ben Greenman, Andrew M. Kent, Vincent St-Amour, T. Stephen Strickland and Asumu Takikawa, 2017.

In this day and age, many developers work on large, untyped code repositories. Even if they are the creators of the code, they notice that they have to figure out the equivalent of method signatures every time they work on old code. This step is time consuming and error prone.

Ten years ago, the two lead authors outlined a linguistic solution to this problem. Specifically they proposed the creation of typed twins for untyped programming languages so that developers could migrate scripts from the untyped world to a typed one in an incremental manner. Their programmatic paper also spelled out three guiding design principles concerning the acceptance of grown idioms, the soundness of mixed-typed programs, and the units of migration.

This paper revisits this idea of a migratory type system as implemented for Racket. It explains how the design principles have been used to produce the Typed Racket twin and presents an assessment of the project’s status, highlighting successes and failures.

.

SNAPL is not dissimilar to the (french-speaking) JFLA that I am more familiar with — with an added irritating call for paper and unreasonable registration price. It has an interesting diversity of topics of presentation: see also the complete list of accepted papers this year, and the list of the previous edition.