Generating Well-typed Programs that Use their Arguments

Random generation of well-typed terms lies at the core of effective random testing of compilers for functional languages. Existing techniques have had success following a top-down type-oriented approach to generation, which suffers from a fundamental flaw: the type of an expression is sometimes generated independently from the expression itself. Such generation often yields functions with argument types that cannot be used to produce a result in a meaningful way, leaving those arguments unused. Such functions can hinder both performance, as the argument generation code is dead but still needs to be compiled, and effectiveness, as a lot of interesting optimizations are tested less frequently.

In this talk, we present a novel method that generates functions that (almost) always use their arguments, by construction. We formalize both the "top-down" and our method as step-relations in an extension of the simply typed lambda calculus with typed and arguments holes, demonstrating how the new method leads to functions that use their arguments by delaying the generation of argument types for a function until they're needed in its body.

Zypr: A New Approach to Structural Editing

Existing structure editors often seem to make it difficult to rearrange programs — a problem known as high viscosity. Even though they have advanced actions available to the user for making structure-preserving changes, still, many changes that are straightforward in a text editor are very complicated in many structured editors. In this presentation we present a new generic structured editing system that preserves structure like other structured editors but is as simple and low-viscosity as a text editor. The system handles tree-like grammars by allowing the user to select sub-nodes of the program (exists in other structured editors) and zippers into sub-nodes of the program (our contribution). This style of selection is general enough to encapsulate all actions the user can make in our editor. We argue that this style of selection is analogous to the cursor and span selections respectively in text editing.