1

Incremental Parametric Syntax for Multi-Language Transformation

arXiv:1707.04600v1 [cs.PL] 14 Jul 2017

JAMES KOPPEL, MIT CSAIL
ARMANDO SOLAR-LEZAMA, MIT CSAIL
We present a new approach for building source-to-source transformations that can run on multiple programming languages,
based on a new way of representing programs called incremental parametric syntax. We implement this approach in our
Cubix system, and construct incremental parametric syntaxes for C, Java, JavaScript, Lua, and Python, demonstrating three
multi-language program transformations that can run on all of them. Our evaluation shows that (1) once a transformation is
written, relatively little work is required to configure it for a new language (2) transformations built this way output readable
code which preserve the structure of the original, according to participants in our human study, and (3) despite dealing with
many languages, our transformations can still handle language corner-cases, and pass 90% of compiler test suites.
CCS Concepts: •Software and its engineering → Translator writing systems and compiler generators; Syntax; General programming languages;
ACM Reference format:
James Koppel and Armando Solar-Lezama. 2017. Incremental Parametric Syntax for Multi-Language Transformation. Proc.
ACM Program. Lang. 1, 1, Article 1 (January 2017), 26 pages.
DOI: 10.1145/nnnnnnn.nnnnnnn

1

INTRODUCTION

As the scale of software grows, developers will increasingly depend on program transformation tools to help
maintain software. Programmers use transformation tools to do everything from small-scale refactoring (Fowler
1999) to modernizing entire legacy applications (Akers et al. 2005). Most tools are wedded to one language (or
even one compiler), and often require hundreds of thousands of lines of code to implement (Brown et al. 2016).
Given that developers use hundreds of languages (Lammel and Verhoef 2001), the value of these tools would be
significantly enhanced if they could be easily made to work across multiple languages.
Many program analysis frameworks have addressed the multi-language problem by reducing multiple languages
into a common intermediate representation. Unfortunately, as discussed in Section 1.1, this approach fails when
the goal is program transformation, because unlike analysis systems, transformation systems need to be able to
generate code that is readable by developers, and this is hard to do from a general intermediate representation. An
alternative to reduction is to define languages in a modular way that allows representations of different languages
to share common structures. In the last few decades, researchers have proposed a number of techniques to deal
with different languages modularly, including work on modular semantics (Delaware et al. 2013a; Mosses 2004),
modular interpreters (Liang et al. 1995b), and modular syntax (Bahr and Hvitved 2011; Zhang et al. 2015). The
limitation is that using any of these techniques requires defining an entire language in a specialized manner,
differently from existing tools. Hence, so far they have only been applied to small languages such as DSLs.
In this paper, we present incremental parametric syntax, which enables implementers to define languages
modularly on a much greater scale than previously, and hence write source-to-source transformation tools
that run on multiple real programming languages. We implement this approach in our Cubix system, and
demonstrate it by developing several characteristic program transformations that each can run on several of C,
Java, JavaScript, Lua, and Python. We show that developers can define these transformations in a few lines of code,
and that the output of the tool does not suffer from the readability problems that plague IR-based approaches.
2017. XXXX-XXXX/2017/1-ART1 $15.00
DOI: 10.1145/nnnnnnn.nnnnnnn
Proc. ACM Program. Lang., Vol. 1, No. 1, Article 1. Publication date: January 2017.

In fact, we conducted a human study that showed that the output of our tool is no less readable than code that
was transformed by hand. Note that this work focuses entirely on the transformation half of building tools;
transformations are free to make use of information from any existing analysis.

1.1

Why IRs Don’t Solve Multi-Language Transformation

Although many previous tools exist for writing analyses or even optimizing code-generators for multiple
languages, their design fundamentally prevents them from expressing source-to-source transformations. The
common pattern when implementing tools for multiple languages is to translate programs in each source language
into some abstracted intermediate representation, and then to implement the analysis on that IR. This pattern is
realized by many program analysis frameworks such as SAIL (Dillig et al. 2009), CIL (Necula et al. 2002), and
BAP (Brumley et al. 2011); as well as bytecode VMs such as LLVM (Lattner and Adve 2004), the JVM (Lindholm
et al. 2014), and the .NET CLR. Conceptually, this consists of providing the following functions:
lower :: Java → IR , C → IR , Python → IR , . . .
analyze :: IR → AnalysisResult

The problem becomes much harder when a user wishes to not only analyze but also transform programs.
The natural extension of the above model is to define transformations on the IR, and then further provide a lift
function from the IR to the source language:
transform :: IR → IR
lift
:: IR →Java, IR → C, IR → Python, . . .

By composing it with the lower and lift functions, this allows a programmer to turn a single generic transform
into multiple language-specific transforms transform J :: Java → Java, transformC :: C → C, etc. A close
reader can already see that this approach makes a promise which is too good to be true: note that one can
compose the lower and lift functions to get a translation from any language to any other!
Roughly speaking, there are two ways to construct this IR. One is to normalize everything to lower-level
representation, i.e.: the least-common-denominator of all the languages. This is the approach taken by most
compilers, as well as bytecodes such as LLVM. Doing this will necessarily destroy information. As a common
example, if the IR abstracts multiple kinds of loops into while loops, then any source-to-source transform which
passes through the IR will convert all loops into while loops, even if the transformation otherwise doesn’t modify
the loop. The other approach, seen in frameworks such as Clang and WALA, is to embed the union of all concepts
in the languages into the IR, putting language-specific nodes into the “common” representation. The Clang AST,
for instance, contains separate node types for both Objective-C and C++ exception-handling. This approach
essentially still requires the user to write a transformation separately for each language: it can use the same
node to represent similar constructs in different languages only if they are exactly identical. It also allows the
representation of invalid programs (by, e.g.: freely mixing Objective-C and C++ concepts), and necessitates that
the lift functions be partial.
The end result is: because of these problems with conventional approaches, at time of writing, we are aware of
no previous framework that allows the user to define a single program transformation, run it on programs from
multiple languages, and obtain output suitable for human consumption.
transform :: IR → IR

1.2

Incremental Parametric Syntax

Our approach instead is based on the idea of incremental parametric syntax. Conceptually, one can think of our
approach as offering the functions in Figure 1. Any language can be decomposed into generic and languagespecific parts, so a transformation that can run on the generic parts can be applied to any language for which
the decomposition is supported, but because the language specific information is not lost, it is still possible to
reconstruct high-quality source code. The ideal partitioning between language specific and generic fragments
2

depends on the transformation, but our approach allows the programmer to incrementally shift more of a language
from the language-specific to the generic fragments in order to support new transformations. With relatively
little specification, our code generation tools automatically derive the language specific parts (Rem J and RemC )
from independently-developed frontends for each language, making it possible for developers to add support for
a new language in less than a day of work, focusing their effort on the inherent task of matching the semantics of
the language with the semantics of the generic components.
The composition X ./ Y is done using an approach known in the termdecompose J :: Java →IR ./ Rem J
rewriting community as “sum of signatures” and known in the functionaldecomposeC :: C →IR ./ RemC
programming community as “data types à la carte” (Swierstra 2008). Our key
transform :: ∀x . IR ./ x → IR ./ x
addition is the notion of a sort injection, which solves the problem that,
recompose J :: IR ./ Rem J →Java
recomposeC :: IR ./ RemC →C
when two languages have similar nodes such as assignment nodes, they may
interact differently with the rest of the syntax. A sort injection is a node
Fig. 1
or sequence of nodes which allows terms of one sort to be used at another
sort. For instance, they allow a user to specify that a generic assignment may be used where a language-specific
statement was previously expected, and to independently specify what terms may appear as the left-hand-side and
right-hand-side of an assignment. Using these sort injections, Cubix can generate code for a new representation
of the language which is isomorphic to the original one, and which allows intermixing language-specific and
generic fragments.
Knowing that a language contains a generic component implies that it supports certain operations, and similar
when it has a sort injection. These form a node-level interface on the language’s syntax trees, so a program
can e.g.: take a node of an unknown language that contains assignments, and query whether that node is an
assignment node. Users then define transformations parameterized on these operations, so that they are applicable
to any language which provides the required interfaces. To those, we add a handful of other interfaces providing
primitives such as statement insertion. These are sufficient to implement a rich library for multi-language
program transformation and CFG generation, which we use to build sophisticated transformations.

1.3

Contributions

Overall, our paper introduces the following new ideas:
• We present the concept of parametric syntax, which allows the user to define a family of representations
specific to different languages, but source-to-source transformations that can run on many of them. We further
present techniques for incremental parametric syntax, which allows the user to achieve this with little
work, given 3rd-party parsers and pretty-printers.
• We develop the concept of a sort injection, which provides a typed and modular way to intermix languagespecific and generic fragments.
• We present an algorithm for automatically converting a datatype into the sum-of-products representation, and
present comptrans, a code-generation library for doing so.
We use these techniques, along with existing ones, to produce the following results.
• We demonstrate using incremental parametric syntax to define a representation for C, Java, Python, JavaScript,
and Lua. We show how we can define transformations that can run on all of them, including complicated
transformations based on control-flow, yet still achieve results that are as readable as hand transformed code.
• We present the RWUS (Real World, Unchanged Semantics) suite, consisting of 50 programs across 5 languages
randomly drawn from top Github projects, together with test suites thorough enough to detect any modification
that changes program semantics.
3

• We present the results of a human study comparing the output of our transformations against hand-transformed
code. Our transformations were identical to the hand-transformed code 20% of the time, and, of the rest, human
judges gave ours higher average scores for readability.

2

OVERVIEW

In this section, we show how our approach allows constructing multi-language transformations, and the work
required to add support for a new language. In Section 2.1, we explain the construction of a transformation called
“declaration hoisting,” and how it is configured to run on several languages. Section 2.2 then gives a detailed
explanation of creating an incremental parametric syntax for C.

2.1

Building an Elementary Hoisting Transformation

In this section, we describe the construction of a transformation for declaration hoisting, and how with a small
amount of configuration, we can apply it to C, Java, and JavaScript. This transformation showcases the versatility
of our approach: although it totals only 23 lines for the transformation plus 34 lines for the language-specific
code, it handles multiple language corner-cases, and achieves a high pass rate on the compiler validation test
suites. Full code for the general portion is given in Section 4.3.
The declaration hoisting transformation moves all variable declarations to the top of the scope, using normal
assignments to initialize them. The end result is similar to how C89 requires programs be written. Figure 2 gives
an example C program and its hoisted version.
The elementary hoisting transformation of this section is
a
simplified
version of the hoisting transformation used in
1 int f ( int a, int b, int s ) {
1 int f ( int a , int b, int s ) {
2
int t1 = 0, t2 = 1;
2
int t1 , t2 ; int r2 ;
our benchmarks and described in Section 5.1. Code for the
3
if ( s ) {
3
t1 = 0; t2 = 1;
language-specific operations are shared between the imple4
int r1 = t1 ∗a+t2∗b;
4
if ( s ) {
mentations. The elementary version does not analyze name
5
return r1 ;
5
int r1 ;
6
}
6
r1 = t1 ∗a+t2∗b;
bindings to prevent shadowing, and will not see variable dec7
int r2 = t2 ∗a+t1∗b;
7
return r1 ;
larations within control statements of JavaScript, as those
8
return r2 ;
8
}
are not considered blocks due to the odd scoping rules of
9 }
9
r2 = t2 ∗a+t1∗b;
10
return r2 ;
JavaScript. Despite this, it passes all but 3 of the tests passed
11 }
by the full implementation (discussed in Section 5.3). The
Fig. 2. An example of hoisting a C program
full hoisting transformation also works on Lua, even though
variable declarations work differently in Lua than in the other languages. Neither runs on Python because Python
lacks variable declarations.
The first big idea of writing a multi-language transformation is that the knowledge a transformation has about a language can be parameterized by a set of interfaces. These provide a set of constraints,
realized as Haskell typeclasses, so that the transformation can run on any language that meets the constraints,
and will give a compile error for any language that doesn’t.
For this transformation, the primary constraints are that the language must contain variable declarations,
assignments, blocks, and identifier. These are given in the form of projection/injection functions between these
known node types and the unknown nodes of the language. Furthermore, assignments and variable declarations
must be valid members of blocks. This is expressed using our notion of sort injections, described in Section 2.2.
Finally, there are two small syntactic operations, "variable declaration to l-value" and "variable initialization to
RHS," which must be implemented on a per language-basis. These are both described below. In Section 4, we give
the code listing the constraints for the elementary hoisting transformation.
This setup requires that different languages have compatible representations of a few constructs such as
variable declarations and assignments. The second big idea of multi-language transformation is that we
can accomplish this using our new incremental parametric syntax representation. For instance, take
4

variable declarations. In C, Java, and JavaScript, variable declarations take the form < attributes > decl∗ where decl
takes the form < attributes > var (= init )? . That is, they consist of some shared attributes followed by a sequence of
declarations, with optional initializers, where these initializers are run sequentially. They can hence be modeled
by a common MultiLocalVarDecl node type consisting of a node of sort MultiLocalVarDeclCommonAttrs followed by a sequence
of SingleLocalVarDecl nodes. Each language supplies its own definition of MultiLocalVarDeclCommonAttrs by providing a
sort injection from whichever existing type it uses to represent these attributes (empty nodes in the case of
JavaScript) to the sort MultiLocalVarDeclCommonAttrs. Sort injections similarly allow each language to configure the sort
of MultiLocalVarDecl nodes. For example, variable declarations are normal statements in JavaScript, but a separate
syntactic category in Java and C (e.g.: if (x) int y = 1; is syntactically invalid). Section 2.2 explains how we construct
an incremental parametric syntax for C, modifying an existing representation to use these common nodes.
This setup also excludes Lua from the elementary hoisting transformation because of an important semantic
difference. Unlike in the other languages, multiple variable initializations in the same Lua declaration, as in
local x , y = y, x, will run simultaneously. We hence chose to model declarations in Lua as SingleLocalVarDecl nodes
which may bind multiple values. The full hoisting transformation is written with more liberal constraints and an
extra case, so that it may work on both variants.
To implement hoisting, the user defines a transformation over blocks, and then uses a generic traversal to run
this over every block in the program. The transformation checks if each block item is a variable declaration. If so,
it splits the variable declaration into a variable declaration without initialization, and a sequence of zero or more
assignments. The extracted assignments are inserted where the variable declarations lay previously, while the
extracted variable declarations are prepended to the front of the block.
While the basic implementation is simple, like any program transformation, much of the work comes in dealing
with language subtleties— and, in this case, with variation between languages. We’ll explain briefly how our
implementation deals with a few of these.
One major relevant point of variation is whether a
lang
lang
variable initializer can always be used as the rightlang
lang
hand-side of an assignment. Our implementation
lang
generic
Lang
solves this by adding a new constraint demanding
automatic
semilang
lang
that the user write an operation for each language
automatic
lang
generic
to convert from variable declarations to assignment
right-hand-sides. For instance, in Java this is needed
Incremental
Modular
Original
parametric
to translate int [] x = {1,2}; into x = new int []{1, 2} , while,
representation
syntax
syntax
in JavaScript, this operation is the identity. A similar
Fig. 3. Each language requires three representations in our
operation is needed to convert a variable declaration
approach. The incremental parametric syntax is constructed
into its corresponding l-value, as syntax definitions
from the modularized syntax, which is automatically derived
from the original representation, taken from a 3rd-party library. may use different AST nodes to represent these. Implementing these operations becomes the main way
that this transformation must be configured per language. Figure 14 in Section 4.2 will show how the hoisting
transformation is parameterized over these operations.
For many edge-cases, no special code is needed in the transformation at all, and the problem can instead be
dealt with by enhancing the representation. As an example, in JavaScript directives such as "use␣ strict " ; must be
placed at the top of the block to have effect, meaning that hoisting a declaration above it can break the code.
Because these directives do not directly take part in computation, and are in some ways treated in the JavaScript
specification as a separate kind of syntax, we decided that they should not be considered part of the block, and
modified the representation of JavaScript to store them separately. The hoisting transformation immediately
started handling this special case gracefully, and this also fixed a similar bug in another transformation.

5

3rd-Party
Frontend
3rd-Party
AST Def
Program
Source

PrettyPrinter

User Spec

Code
Generation

Modularized
Syntax

Trans

Modular
AST

AST
Parser

Trans

Incremental
Parametric
Syntax
LangGeneric
Specific
Parts
Parts

Transforms

Fig. 4. At runtime, a program is progressively transformed through each representation, until it is decomposed into generic
and language-specific components, so that a multi-language transformation can be applied. To render a program back into
source, this process is then run in reverse.

We have shown how our implementation of the elementary hoisting transformation allows us to leverage the
overlapping syntaxes of C, Java, and JavaScript to build a transformation that runs on each, while still being
flexible enough to handle language-specific edge cases. Overall, these techniques allow transformations for
different languages to share code to the extent that the two languages are syntactically similar. The techniques
of this section readily combine with others in order to address the full spectrum of problems when writing
source-to-source transformations. For instance, the user may constrain a transformation to require some static
analysis be available for whatever languages the transformation runs on. This static analysis may either be
implemented separately for each language, or in a multi-language fashion using techniques not discussed in this
paper. Later in this paper, we present more complicated transformations which make more interesting use of
semantics. The full hoisting transformation requires a simple name-binding analysis to function correctly, for
example, while some of the transformations discussed in Section 5.1 are based on the CFG.

2.2

Modularizing C

In Section 2.1, we outlined how to build a multi-language transformation, which works on any language that
contains some common notion of variable declarations and a few other constructs. In this section, we give the
detailed example of constructing an incremental parametric syntax for C, in which parts of of the language are
recast in terms of these common components, so that mullti-language transformations can be applied.
To support a language, our approach requires that it have three representations. The final form is the
incremental parametric syntax mentioned above. The starting point is some already-existing syntax definition
of the language from a 3rd-party library, with its accompanying parser and pretty-printer. In between is the
“modularized” representation. Figure 3 depicts the three representations and their relation. The modularized
representation is derived automatically from the original representation, but splits the language into many
components. This enables the user to define the final incremental-parametric representation by replacing some
components of the modularized representation with their generic equivalents. These three representations are
mutually isomorphic. Translations between the original and modularized definitions are derived completely
automatically, while translations between the modularized and incremental-parametric representations are
generated mostly-automatically, with the user only needing to write code to replace removed node types with
their generic equivalents. Figure 4 depicts how these representations and their translations are generated, and
how a program is transformed through each of them so that it may be transformed using a transformation defined
only on generic components.
In the remainder of this section, we demonstrate how to construct an incremental parametric syntax for C,
using the Haskell library language-c (Huber Huber) as a starting point.
Figure 5 depicts a fragment of the language-c’s datatype for C programs. Consider a hypothetical transformation
that swaps the two branches of an if-statement. Conceptually, this can be defined for any language that supports
6

if-statements. Unfortunately, the recursion in the datatype prevents this kind of modularity. Following the
structure of the datatype, the implementation must recurse into substatements. In doing so, it must be defined
for every kind of statement. Without generic-programming techniques like the kind we are about to discuss, this
ties the implementation to the exact set of statements available, and hence to a single language.

CStmt

While

If

CExpr
Fig. 5. Fragment of a typical representation of C.

The goal of the modularized representation is
to solve this problem by removing the recursion
t
from (“unfixing”) the datatype, and then splitting
the resulting unfixed language into fragments.
CStmt
+
The left column of Figure 6 depicts one such
t
fragment, while the right column shows how
they are combined back into a representation of
While
If
+
the whole language. The modularized represen- t
t
tation has an independent component for each
sort of the original representation. In each comtExpr
tStmt
+
ponent, all recursive occurences of the datatype
t
have been replaced with a type variable, allowing the system to later specify what is allowed
as a subterm of each node. These fragments are Fig. 6. In the sum-of-signatures representation, a language is repsignatures that define the shape of each node in resented by a list of subsignatures like the one on the left. Each
C. They are combined to give a signature for all signature has a type variable for subterms, in lieu of self-reference.
allowed nodes in C. The final step in construct- The subsignatures are combined into a signature for the whole language, which is then closed by specifying that allowed subterms of
ing this representation is to close the recursion
terms of this signature are other terms of this signature (right). This
by applying a type-level fixpoint, declaring that makes it easy to add and remove subsignatures of the language.
the relevant sort of C node may be used anywhere where a type variable is indicated, thus obtaining a representation isomorphic to the original. This is the
sum-of-products representation, or datatypes à la carte (Swierstra 2008).
We have implemented the modularization transformation in a Template Haskell library called comptrans, which
takes an AST definition as a Haskell algebraic data type, and generates code for the modularized representation,
along with translations to and from the original. We describe comptrans and the modularization process in more
detail in Section 3.2. The user simply writes a small amount of boilerplate to invoke comptrans on language-c,
and the modularized representation is generated automatically, along with accompanying translations to and
from the language-c representation. We will show the code for doing this in Section 4.1.
Because the modularized representation is composed of a list of signatures, it is easy to construct a new
representation by adding and removing items from this list. In doing so, the user can slowly swap out C-specific
7

parts for generic ones, gradually creating a parametric syntax for C. This process is depicted in Figure 3. The
user initially only needs to genericize enough of the language to support whatever analyses and transformations
are currently desired, and can incrementally replace more of the language with generic components as they wish
to add more transformations. This is the incremental parametric syntax.
In this case, in order to support the hoisting transformation, the user must replace C assignments, variable
declarations, blocks, and identifiers with their corresponding generic components. Each of these generic components comes with an informal semantics. The user must first check these semantics against the C specification to
ensure that the generic components properly model the relevant portion of C.
The user must next add nodes which determine the interactions between the C-specific and generic components.
The user adds nodes indicating that assignments are C expressions, and that C expressions form the left-hand
and right-hand sides of an assignment. They must also add nodes indicating that generic blocks may be used
where a C block is expected, and that variable declarations and C statements form the entries of a block. These
nodes establish sort injections (Section 3.3) between the generic and C-specific sorts, controlling what may be
used where. Figure 7 depicts a mixed C/generic AST using these sort injection nodes. Because hoisting requires a
sort injection from variable declarations and assignments to block item, the user also implements two derived
sort injections. For instance, the sort injection from assignments to block items is a chain of nodes: assignments
are expressions, expressions may be used as statements in C, and statements are block items.
The incremental-parametric sigCBlockStmt
nature for C can now be defined
by taking the list of signatures auCExprStmt
tomatically constructed from the
language-c datatype, adding the sigAssignIsCExpr
natures for the generic components
=
and sort injection nodes, and subCLhsIsLhs
CExprIsRhs
tracting the now-redundant signatures for C-specific identifiers and
blocks. Code for doing so will be
x
1
given in Figure 13 in Section 4.1. If
Fig.
7.
Portion
of
an
example
term
in
the
modular
representation of C, showing
the user were to replace the other
the
intermixing
of
language-specific
and
generic
components,
with sort injection
C expressions with generic componodes
at
the
boundary.
nents, or define a new type for all C
expressions except assignments, they
could also remove the existing CExpression type from our signature. The final incremental parametric syntax is
obtained by taking a type-level fixpoint of this signature, indicating that the children of each node of this signature
are other nodes of this signature. This yields the end result: a modularized representation of C, isomorphic to the
original, but with generic components for assignments, blocks, variable declarations, and identifiers.
The final step is to write code that translates back-and-forth between individual nodes of types that have been
removed from the language, and the generic components that have replaced them. Because the remainder of the
two representations are the same, Cubix then uses these to construct the translations between the modularized
and incremental-parametric representations. Our actual implementation of these translations for C totals 130
lines of Haskell code, about 40 of which are boilerplate.

3

CORE IDEAS

In this section, we explain the core new ideas that make our multi-language transformations possible. Section 3.1
presents the terminology and goals of incremental parametric syntax. We achieve this through the concepts in
8

the following sections: Section 3.2 explains the translation of a syntax into its modularized version, and Section
3.3 presents sort injections.

3.1

Incremental Parametric Syntax

Consider sorting a list. By parameterizing out the compare function, one can write a single sort function which can
operate on lists of any datatype, and yet be equivalent to having a separate sort function for each type. With
some basic compiler optimizations, it can even be as efficient. It is this exact combination of generality and
specialization which we aim to get for program transformations using parametric syntax.
Definition 3.1. A parametric syntax defines a language as a composition of fragments, in a manner that
allows operations to be defined on all languages which contain a given fragment.
We have already presented a function over parametric syntax, the function transform :: ∀ x . IR./x →IR./x from
Section 1.1. We defer a full presentation of these types till Section 4.2, but we can now give more detail. The elementary hoisting transformation from Section 2.1 has a type similar to elemHoist :: ∀ f . (Block ≺ f , VarDecl ≺ f ) ⇒ f → f ,
where x ≺ f indicates that signature f contains a fragment x. The incremental parametric syntax for C developed
in Section 2.2 is a parametric syntax, and the hoist function can be applied to it.
Strictly speaking, the modularized version of language-c from Section 2.2 is already a fully parametric syntax
— the representation makes it possible to e.g.: write a transformation over any language which contains the
CStatement fragment. Since this gives no advantage over writing a transformation specific to C, we henceforth use
the term “parametric syntax” only to refer to syntax fragments which may usefully be shared between languages,
and a fully parametric syntax to refer to a representation where all syntax fragments are generic.
Our notion of parametric syntax is closely related to the Expression Problem (Wadler 1998), which concerns
being able to separately extend a language with new terms and new operations. Any parametric syntax must
also be a solution to the Expression Problem, since defining languages and operations using syntax fragments
allows a language to be extended with new terms and operations. However, a solution to the Expression Problem
need not allow for expressing multiple languages.
Previous work on modular syntax such as datatypes à la carte achieves the ideas of modular syntax. However,
they require the user to define a language through a fully parametric syntax, which can be extremely difficult.
With an incremental parametric syntax, a comparatively small initial effort is needed.
Definition 3.2. An incremental parametric syntax expresses a language as a hybrid between languagespecific and parametric syntax, in a manner which allows the language-specific components to be converted
piecewise into parametric ones.
For an example, see the incremental parametric syntax for C that we described in Section 2.2. The remainder
of this section explains the concepts we use to achieve incremental parametric syntax.

3.2

Generating the Modularized Representation

Our comptrans tool takes as input a syntax definition as a system of mutually recursive algebraic datatypes, and
outputs code for a new syntax definition in the sum-of-signatures format isomorphic to the original. The latter is
represented as a compositional data type (Bahr and Hvitved 2011). An example is given in Figure 8. The left hand
side gives a representation of an abstract syntax as an ADT. comptrans transforms this input into the GADTs on the
right. Summing these together and taking a type-level fixpoint gives a representation isomorphic to the original.
Code is given in Figure 10: the type Term (Arith : + : Atom : + : Lit) ArithL is isomorphic to Arith . However, by modifying
that sum, this representation makes it easy to add or replace components of the syntax. The algorithm is formally
described in Appendix A.
9

The transformation is straightforward. For each inputted algebraic datatype of kind ∗ , the ADT Arith of kind ∗ is
translated into a GADT of kind (∗ → ∗) → (∗ → ∗) , also named Arith . This GADT is similar to the one depicted in
the left column of Figure 6. In the type Arith t l , l is a type-level tag indicating the sort, and t is a type function
indicating all allowed subnodes. The type t AtomL then indicates any node that has been tagged with sort AtomL.
comptrans generates the empty datatype ArithL to serve as the sort of Arith , and similarly for the others. This indirection
leaves the language definition open: if the user later adds new nodes of sort AtomL, they may be used as the
children of an Arith node. Combined with sort injections, this enables the user to replace nodes with generic ones
defined separately, while leaving the rest of the syntax definition intact.
The modularized representation has advantages
1
data Arith =
1
data ArithL ; data AtomL; data LitL
over the original mutually-recursive ADT represen2
Add Atom Atom 2 data Arith t l where
3
data Atom
3
Add :: t AtomL →t AtomL
tation, even when writing transformations for only
4
= Var String
4
→ Arith t ArithL
one dialect of one language. For instance, this rep5
| Const Lit
5
data Atom t l where
resentation allows giving a type Term Sig l → Term Sig l
6
data Lit
6
Var :: String → Atom t AtomL
7
= Lit Int
7
Const :: t LitL → Atom t AtomL
to sort-preserving rewrites that can be applied to
8
data Lit ( t :: ∗ → ∗) l where
terms of any sort, and also enables many generic9
Lit :: Int → Lit t LitL
programming techniques. See Bahr and Hvitved
Fig. 8. Example input (left) and output (right) of comptrans.
(2011) for a full discussion of this representation.

3.3

Sort Injections

While C, Java, and Lua may share similar notions of variable decla1 data (:+:) f g e l = Inl ( f e l ) | Inr (g e l )
rations, the details are different. For instance, variable declarations
2 data Term f l = Term (f (Term f) ) l
are statements in Lua, but not in C or Java (e.g.: if (x) int y = 1;
3 type LangSig = Arith :+: Atom :+: Lit
4 type LangTerm = Term LangSig
is syntactically invalid). In Java, variable declarations are given
a type, but in C they may also be given type qualifiers like const, Fig. 9. Combining the fragments produced by
storage specifiers like register , etc. Sort injections allow all three comptrans in Figure 8
languages to share a common notion of variable declarations, while allowing each to control where in an AST a
variable declaration may go, and to specify what sorts of nodes may be the attributes associated with a variable
declaration. While sum-of-signatures representation offers a way to modularize what nodes can be in an AST,
sort injections modularize what edges may be in an AST.
In addition to configuring where nodes may appear in an AST, sort injections also allow abstracting over the
details of different syntaxes. For instance, a user can write a transformation in terms of a sort injection from
assignments to block items, meaning the transformation can be run on any language in which assignments can
be inserted into blocks, regardless of the chain of nodes used to do this.
Definition 3.3. A sort injection is a constraint stating that a term of one sort may be used at another sort.
Definition 3.4. A sort injection node is an unary production in a syntax definition added for the purpose of
enabling a sort injection
An example sort injection node, and the typeclass instance providing its associated sort injection, are given in
Figure 10. The GADT declaration creates a new node type called AssignIsCExpr of sort CExprL (C expressions), whose
child is of sort AssignL (generic assignments). Hence, any signature which contains AssignIsCExpr can use generic
assignments as C expressions. This induces a sort injection, as encoded in the succeeding instance declaration.
For any signature which contains AssignIsCExpr nodes, the instance declaration provides functions injF and projF ,
stating that an assignment node may be converted into a C expression, and that a C expression may be tested to
see if it’s an assignment.
The inclusion of sort injection nodes in a representation allows it to modularly configure the interaction of
components. For instance, our generic component for assignments has children of sorts Lhs, Rhs, and AssignOp, and
10

is itself of sort Assign. An incremental parametric syntax which wishes to include the assignment component will
then include sort injection nodes from its own relevant language-specific sorts into Lhs, Rhs, and AssignOp, and from
Assign to wherever assignments may be inserted in the language. For example, C and Java contain sort injection
nodes from Assign to CExpression and JavaExpression , while Lua contains one from Assign to LuaStatement.
Sort injections may also be provided through a chain of existing
1
data AssignIsCExpr e l where
nodes
rather than through a dedicated sort injection node. Figure 11
2
AssignIsCExpr :: e AssignL
depicts how assignments insert into blocks differently between our
3
→ AssignIsCExpr e CExprL
4
instance (AssignIsCExpr ≺ f )
syntaxes for C and JavaScript, and how sort injections abstract across
5
⇒ InjF (Term f) AssignL CExprL where
these differences. A transformation may then be written against any
6
injF = AssignIsCExpr
syntax which provides a sort injection from assignments to block
7
projF x = case project x of
8
Just (AssignIsCExpr x) → Just x
items.
9

_

→ Nothing

Fig. 10. An example sort injection node and its
associated sort injection

4

IMPLEMENTATION

We have implemented our approach in the Cubix system, named for
a fictional robot composed of modular parts that can be reassembled
for many purposes. Cubix is organized as a collection of libraries which users can use to assist in building
incremental parametric syntaxes and multi-language transformations. Our implementation totals approximately
10,500 lines of Haskell, providing support for five languages and several transformations. We build heavily on
the compdata library (Bahr and Hvitved 2011) for representing modular syntax, and extend it with support for
our new concept of sort injections and the comptrans library for converting a third-party syntax definition into
modular syntax. We provide a small library of generic language components, and modules to assist in dealing
with labeled terms, control-flow graphs, and higher-order tree traversals.
The code is split between approximately 3500 lines
BlockItem
BlockItem
BlockItem
in our language implementations, 1600 in our transformations and their harness, 1000 in comptrans, 3300 CBlockStmt
JSStmt
in our other libraries, and the rest in various examples,
...
CStmt
tests, and minor extensions to 3rd-party libraries. Note
JSExprStmt
Assign
CExpr
that our language implementations do contain a lot of
code clones, due to the limits of metaprogramming in
Assign
Assign
Assign
Haskell.
The remainder of this section discusses our infras- Fig. 11. An example of how sort injections abstract the intructure in more detail. Section 4.1 describes the pro- sertion of assignments into blocks between the language−c and
cess of supporting a language in Cubix. Section 4.2 language− javascript syntaxes
describes how to implement transformations using Cubix.

4.1

Languages

As evidenced in Figure 4, adding support for a language consists of selecting a 3rd-party frontend for that
language, and then constructing two derived representations. First, the modularized representation is created by
invoking comptrans on a 3rd-party syntax definition. For example, the main line used to generate a modularized
representation of C from the language−c library is runCompTrans (deriveMultiComp ’’CTranslationUnit). This code is Template
Haskell (Sheard and Jones 2002), meaning that it runs at compile-time and generates a set of Haskell declarations.
Here, CTranslationUnit is the top symbol of the syntax definition exported by language−c. comptrans will recursively walk
this type definition, generating GADT fragments similar to those in Figure 8. Another command extracts the
names of all types in that tree into the list cSigNames. This aids the user in defining the incremental parametric syntax
below, and allows the user to sum these into signature for C by writing runCompTrans (makeSumType "CSig"; cSigNames). The
11

1
2
3
4
5
6
7
8
9
10
11

data MultiLocalVarDeclCommonAttrsL; data LocalVarInitL; data MultiLocalVarDeclL; data OptLocalVarInitL ;
data LocalVarDeclAttrsL ; data SingleLocalVarDeclL ; data AssignOpL; data AssignL; data LhsL; data RhsL
data OptLocalVarInit e l where
JustLocalVarInit :: e LocalVarInitL → OptLocalVarInit e OptLocalVarInitL
NoLocalVarInit
:: OptLocalVarInit e OptLocalVarInitL
data SingleLocalVarDecl e l where
SingleLocalVarDecl :: e LocalVarDeclAttrsL → e VarDeclBinderL → e OptLocalVarInitL → SingleLocalVarDecl e SingleLocalVarDeclL
data MultiLocalVarDecl e l where
MultiLocalVarDecl :: e MultiLocalVarDeclCommonAttrsL → e [SingleLocalVarDeclL] →MultiLocalVarDecl e MultiLocalVarDeclL
data Assign e l where
Assign :: e LhsL → e AssignOpL → e RhsL → Assign e AssignL

Fig. 12. Generic nodes used to model variable declarations and assignments
1
2
3

do let cSortInjections = [ ’ ’MultiLocalVarDeclIsCCompoundBlockItem, ’’AssignIsCExpression, . . . ]
let names = (cSigNames \\ [mkName "Ident"]) ++ cSortInjections ++ [ ’ ’MultiLocalVarDecl, ’ ’P . Ident , ’ ’Assign , . . . ]
runCompTrans (makeSumType "MCSig" names)

Fig. 13. Generating the incremental parametric syntax from the modularized syntax

declaration type CTerm = Term CSig then creates a type for terms of that signature, and an additional comptrans command
generates the translations from the language−c representation into the modularized representation.
The incremental parametric syntax is defined by adding and removing node types from the signature of the
modularized representation. Shortened code for doing this is given in Figure 13. This example uses our Cubix’s
pre-existing definitions of generic nodes for constructs such as assignments and variable declarations, shown in
Figure 12, and assumes the user has already generated sort injection nodes allowing these to be inserted into a
C AST. cSigNames, as mentioned above, contains the names of all types included in the modularized C signature.
This code then defines names to consist of these same names, except adding new generic syntax and sort injection
nodes, and removing C-specific identifiers. The code then generates a new type declaration, summing these types
together into the new incremental parametric signature, MCSig. Although this representation replaces all CAssign
nodes with generic assignment nodes, we choose to allow these nodes to remain in the signature, as they are part
of the larger CExpression type. A more precise type could be given by also removing CExpression from the signature,
replacing it with a new fragment which can represent all C expressions except for assignments. The final step is
to define translations from the modularized to the incremental parametric representations. Because these two
representations share node types, most of this translation is covered by default cases. The user need only write
code for the points where they differ, e.g.: to convert between C-specific and generic assignments. The user is
then free to build additional infrastructure for C, such as a control-flow graph generator.
In our experience, creating an incremental parametric syntax for a new language takes 1-2 days. We have
implemented support for C, Java, JavaScript, Lua, and Python, using the parsers, pretty-printers, and syntax
definitions from the Haskell libraries language−c (Huber Huber), language−java (Broberg 2015), language− javascript (Zimmerman 2016), language−lua (Ömer Sinan AÄ§acan and Mertens 2016), and language−python (Pope 2016), respectively.
Despite their names, these libraries were all implemented independently by different authors, and share no
common infrastructure beyond the Haskell standard libraries. We fixed bugs in all of their pretty printers, but
otherwise had no involvement with their development. Some of our fixes have yet to be merged upstream.
One exception is that, in a previous project, we had already built a translation between the JAPA parser
(van Bruggen van Bruggen) and the language−java AST, as the JAPA parser is substantially higher quality than
language-java’s. We used this instead of the language−java parser. However, our translation is built on a version of
JAPA for Java 1.5. Because some samples in the RWUS suite (Section 5.2.1) use Java 1.8 syntax, our implementation
falls back to the language-java parser if JAPA fails.

12

1
2
3
4

type HasSyntax f = ( SingleLocalVarDecl ≺ f , MultiLocalVarDecl ≺ f , OptLocalVarInit ≺ f , Ident ≺ f , Assign ≺ f
, AssignOpEquals ≺ f , ListF ≺ f , ExtractF [] (Term f ))
type CanHoist f = ( VarDeclFragment f, AssignFragment f, Block ≺ f , VarInitToRhs (Term f ), VarDeclBinderToLhs (Term f)
, HTraversable f , InjF f MultiLocalVarDeclL BlockItemL, InjF f AssignL BlockItemL)

Fig. 14. Constraints used by the elementary hoist transformation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

declToAssign :: (CanHoist f) ⇒ Term f MultiLocalVarDeclCommonAttrsL →Term f SingleLocalVarDeclL → [Term f BlockItemL]
declToAssign mattrs ( SingleLocalVarDecl 0 lattrs b optInit ) = case optInit of
NoLocalVarInit 0
→ []
JustLocalVarInit 0 init → [ injF (Assign 0 (varDeclBinderToLhs b) AssignOpEquals0 ( varInitToRhs mattrs lattrs init ))]
removeInit :: (CanHoist f) ⇒ Term f SingleLocalVarDeclL → Term f SingleLocalVarDeclL
removeInit ( SingleLocalVarDecl 0 a n _) = SingleLocalVarDecl 0 a n NoLocalVarInit 0
splitDecl :: (CanHoist f) ⇒ Term f BlockItemL → ([ Term f BlockItemL], [Term f BlockItemL])
splitDecl ( projF → ( Just (MultiLocalVarDecl0 attrs decls )))
= ([ injF (MultiLocalVarDecl0 attrs (mapF removeInit decls ))],
concat (map (declToAssign attrs ) ( extractF decls )))
splitDecl t = ([], [ t ])
hoistBlockItems :: (CanHoist f) ⇒ [Term f BlockItemL] → [Term f BlockItemL]
hoistBlockItems bs = concat decls ++ concat stmts
where (decls, stmts) = unzip (map splitDecl bs)
elementaryHoist :: (CanHoist f) ⇒ Term f l → Term f l
elementaryHoist t = transform hoistInner t
where hoistInner :: (CanHoist f) ⇒ Term f l → Term f l
hoistInner ( project → ( Just (Block bs e ))) = Block0 ( liftF hoistBlockItems bs) e
hoistInner t
= t

Fig. 15. Implementation of the elementary hoist transformation

4.2

Transformation Support

In Section 1.1, we explained that our system decomposes a language into two parts IR ./ Rem, and then a transformation is written with type ∀ x . IR ./ x → IR ./ x. The truth is slightly more complicated. Each transformation may
require different nodes in the common IR. Hence, instead of fixing a set of generic nodes in the common IR, we
instead specify the set of common nodes required by a transformation. It can then run on any language whose
incremental parametric syntax contains those common nodes. The type of a node also indicates the sort of that
node. So, a transformation that runs on any language with assignments and blocks, and which runs at a root
node of sort BlockL, may have type ∀ f . (Assign ≺ f , Block ≺ f) ⇒ Term f BlockL → Term f BlockL.
Every transformation requires that a language satisfy certain interfaces, expressed through Haskell typeclasses,
and can then run on any language that satisfies these interfaces. These interfaces are used to provide:
(1) Requirements that the language contain certain nodes, expressed through projection and insertion functions.
For instance, the constraint Assign ≺ f offers the ability to test if a node is an assignment node, and to insert an
assignment node into a tree anywhere that accepts the assignment sort.
(2) Sort injections, indicating where in an AST nodes of certain sorts may be inserted
(3) Miscellaneous functions satisfying a certain interface. These are typically used to either require that a static
analysis be available for a language, or to provide language-specific special cases.
Figure 14 depicts the constraints used by the elementary hoisting declaration: the hoisting transformation can
run on any language that satisfies these constraints. The first several lines indicate what generic syntax nodes must
be part of the language. VarInitToRHS and VarDeclBinderToLhs are the low-level language-specific syntactic operations
discussed in Section 2.1. InjF f AssignL BlockItemL and InjF f MultiLocalVarDecl BlockItemL are sort injections indicating that
assignments and variable declarations may be inserted into blocks; the former was depicted in Figure 11. HTraversable
13

is an interface from compdata (Bahr and Hvitved 2011) offering generic tree-traversal operations. There are also a
couple more technical constraints. MaybeF and ListF provide nodes similar to Haskell’s built-in optional and list
types except that they function like the other tree nodes. Then e.g.: a node representing a list of block items
may have sort [BlockItemL]. Together with the ExtractF constraint, these provide operations extractF and insertF which
witness the isomorphism between between terms of sort "list of l " (type Term f [ l ] ) and lists of terms of type l
(type [Term f l ] ). Overall, this example illustrates how our transformations can handle the intricate details of many
languages while maintaining a high level of generality. This example also illustrates how language-specific code
fits into a larger transformation.
Knowing that a language contains certain nodes and having access to generic tree-traversal operations is enough
to begin writing multi-language program transformations. However, to make writing transformations more
convenient, we offer the compstrat library providing higher-order traversal operators called strategy combinators
(Lämmel and Visser 2002). Strategy combinators allow the user to take a set of simple single-node rewrites, and, in
a single line of code, lift them into complicated traversal patterns involving contextual and conditional rewriting.
We do not discuss the design of compstrat in detail here, other than noting that it provides similar functionality to
other strategy combinator libraries such as Scrap Your Boilerplate (Zhang et al. 2015), Strafunski (Lämmel and
Visser 2003), and KURE (Gill 2009).
We have also built miscellaneous other infrastructure to support our transformations. The most interesting
of these is the control-flow based inserter, which can e.g.: allow the user to declare that a statement must be
inserted before evaluating the condition of a loop, causing it to be inserted before the loop, before the end of the
loop, and before every continue statement.

4.3

Example: Implementing the Elementary Hoisting Transformation

In this section, we present the full implementation of the elementary hoisting transformation from Section 2.1.
The code listing is given in Figure 15. The definition of the CanHoist constraint was given in Figure 14. We omit the
34 lines of code giving the three language-specific instances of VarInitToRhs and VarDeclBinderToLhs.
The code implements the algorithm described in Section 2.1. Execution begins at elementaryHoist, which runs the
hoistBlockItems function over every block. A key aspect is the interplay between generic and specific operations.
The transform traversal from compdata runs a function over every node, viewing them as generic tree nodes, while
the project function is used to test whether that node is a block. Later, the sort injections are used via the projF and
injF functions to operate on the subset of BlockItem’s that the transformation knows about.
In this example, we have tried to avoid many of the vagaries of Haskell syntax as well as more advanced
features of Cubix. In particular, we avoided the use of compstrat, our higher-order traversal library. Nonetheless,
some advanced features are present. The syntax f (view → Just x) = . . . is a Haskell view pattern (Wadler 1987)
which is syntactic sugar for f t = case view t of Just x → . . . , with pattern match failure proceeding to the next case.
The "vanilla" data constructors defined in Figure 12 construct nodes of a signature fragment, rather than of the
entire language. Addressing this, Cubix also defines Haskell pattern synonyms, named as primed variants. For
example, Assign 0 l o r has type (Assign ≺ f ) ⇒ Term f AssignL, whereas Assign l o r has type forall e . Assign e AssignL. (Note
that these are defined using project .) Finally, we explained the extractF and insertF functions in Section 4.2; these are
used to implement the liftF and mapF functions, which are used to operate on trees of type Term f [ l ] .

5

EVALUATION

In the previous section, we argued that the insights of Cubix make multi-language transformations easy to write.
In this Section, we further evaluate the following two claims:
• Readability: These transformations produce readable output, similar to what a human would write. They do
not needlessly destroy the program’s structure, as do IR-based transformations.
14

Transformation
Hoist
Testcov
TAC

Languages Supported
C, Java, JavaScript, Lua
All
JavaScript, Lua, Python

Core LOC Extra LOC per language
84
17
62
22
350
87

Table 1. Transformations implemented and their size. Line counts are split into the core code of the transformation, plus the
per-language code to support language-specific operations and customization. Line counts exclude the file prologue, i.e.:
they count from the first line of code which is not an import statement.

• Correctness: Despite the low effort needed per language, transformations can maintain correctness even when
faced with the intricacies of multiple languages

5.1

Benchmark Transformations

To evaluate our system, we have implemented three source-to-source transformations. These were chosen to
explore the space of operations employed by program transformations, and as transformations that require a
minimum of user input. Table 1 lists the transformations and their line counts. We explain them below:
• The hoisting transformation Hoist, which lifts variable declarations to the top of their scope. This is similar
to the elementary hoisting transformation explained in Sections 2.1 and 4.3, except that it also handles the
parallel assignments of Lua, and does additional name-checking to avoid hoisting shadowed variables. This
transformation supports all languages except Python, which lacks variable declarations.
• The test-coverage instrumentation transformation Testcov, which prefixes each basic block in the source code
with something which marks that that block has executed. This produces data that could be fed into a test
coverage tool. This transformation was inspired by the Semantic Designs test-coverage tool, which implements
this transformation separately for a dozen languages (Semantic Designs, Inc 2005). This transformation
supports all languages. Example input/output for Python is given in Figure 16.
• The three-address code transformation TAC hoists all nested computations into temporary variables, e.g.:
changing 1+1+1 into t=1+1; t+1. This is a deceptively complicated transformation, difficult to write at the source
level for even one language. Two major sources of complexity are that it must properly handle short-circuiting
operators, and must compute the condition of a for loop in multiple places, including before every continue
statement. Doing this properly requires the control-flow based inserter mentioned in Section 14. TAC must
also handle a plethora of language-specific special cases. This transformation only supports JavaScript, Lua,
and Python. It does not support Java or C because declaring the temporary variables would require type
inference, which in turn requires symbol-table construction, a heavyweight piece of language infrastructure.
Bringing a transformation to 100% correctness is a time-consuming endeavor, even for one language. Because
our goal is to demonstrate the power of our system rather than develop these specific transformations, while we
have worked to bring each transformation to a high pass rate, we have none gone the full length to bring them to
a 100% pass rate on compiler test suites. Doing this for the dynamic languages (JavaScript, Lua, Python) is also
infeasible because these languages have self-referential tests, where introducing formatting changes can break
some tests. As such, our transformations do have bugs and unhandled cases, all of which can be fixed with some
more work. Two examples of remaining bugs in these transformations is that TAC for Python does not properly
handle chained-comparison notation (e.g.: if a ≤ b ≤ c : . . . ) due to a weakness in the underlying representation,
and that Hoist for Lua may move a declaration past a goto statement, which is not allowed by the language spec.
The line counts Table 1 give evidence that extending a transformation for a new language is typically much
less work than writing the transformation anew. Not evidenced here is that the language-specific code needed is
also less complex, typically consisting of simple "configuration" code.
15

5.2

Readability: Human Study

We ran a study to evaluate the readability of our transformations’ output.
The overall setup of our experiment is like a Turing test. First, we ask a
set of human contributors to transform programs by hand. We then give
a separate set of human judges these programs, alongside the corresponding automatically transformed programs, and ask them to rate them both
on correctness and quality. Because low-level code formatting is outside
the scope of our claims, we automatically reformat the human-written
code before presenting them for comparison. Outside of formatting, we
attempted to bias the experiment in favor of the humans, allowing them
to resubmit until their transformed programs were correct according to
our extremely thorough test suites. Despite this, in our final results, the
judges gave the automatically transformed programs a higher average
Fig. 16
rating for every languages.
Our experiment proceeds in three phases. In the first phase, we construct the RWUS suite, providing suitable
programs on which to run the study. In the second phase, we ask human participants to manually apply each of
the two studied transformations on a code sample. In the final phase, human judges from Mechanical Turk rate
the manually-transformed code against the same code transformed by our system.
1 def countF ():
2 count = 0
3 for i in range(9):
4
if f ( i ):
5
count += 1
6
break
7
else :
8
print i
9 return count

1 def countF ():
2 TC.cov[0] = True
3 count = 0
4 for i in range(9):
5
TC.cov[1] = True
6
if f ( i ):
7
TC.cov[2] = True
8
count += 1
9
break
10
else :
11
TC.cov[3] = True
12
print i
13 TC.cov[4] = True
14 return count

5.2.1 Phase 1: Constructing the RWUS Suite. As objects in our study, we needed (1) representative samples of
real-world code, and (2) an objective measure of whether a transformed sample was semantically equivalent to
the original. The second criterion is the main difficulty, as random samples of code typically do not come with
thorough tests, and certainly not tests that are easy to run. Hence, we created our own.
The RWUS (Real World, Unchanged Semantics) suite consists of 50 functions across 5 languages randomly
selected from top GitHub projects. For each, it also includes a test suite designed with the intention that only
functions semantically equivalent to that function will pass. Each function is distributed as an entry. An entry is
a file containing the original sample, mocks for all referenced symbols, tests, and a wrapper main procedure which
invokes the tests. The files can all be compiled and executed without any dependencies. The tests are used by
invoking a script that replaces the sample with a transformed version, and then executes the resulting file.
We selected the functions for the RWUS suite as follows: For each of C, Java, JavaScript, Lua, and Python, we
downloaded the top 20 projects in that language on Github from those with at least 500 lines, sorted by number
of users who "starred" that project. We then uniformly at random selected a line of code from the projects. If this
line of code lies within a function, we took the innermost such function as a sample; else, we repeated the process.
We discarded all samples which were not between 5 and 50 lines of code, excluding function signatures, blank
lines, and comments. We repeated this process until we had 10 samples for each language. One shortcoming of
this approach is that the top-rated projects on Github vary in size by orders of magnitude. As the extreme, 90% of
our C corpus and all 10 C samples come from Linux. The other 40 samples come from 24 different projects.
For each sample, we constructed test cases ensuring full path coverage, and added checks to ensure all mocked
functions are called in the expected order with the expected arguments. The resulting tests are incredibly
thorough. While the actual samples total 1158 lines of code, the RWUS suite totals 8070 lines of code.
5.2.2 Phase 2: Obtaining Human-Written Transformations. We recruited programmers through department
mailing lists, flyers posted around the department, and social media. Due to the relative scarcity of Lua programmers, we also posted on Lua forums, and asked Lua participants to spread the study by word of mouth.
Participants were sent to a website, where they would download a single sample from the RWUS suite along
with its tests, and were asked to perform each of our transformations by hand on the file. They were allowed to
contribute one sample per language, and were offered a $10 Amazon gift card for each.
16

We inspected each submission by hand. Participants were asked to resubmit until their transformed samples
passed all tests, and had no significant transformation errors, such as unhoisted variables.
5.2.3 Preparing the Samples. After we had collected all 50 human-transformed samples, we ran them through
the corresponding parser and pretty printer to normalize formatting. We then ran our transformations on each
of the RWUS samples, and evaluated them with the RWUS test suites.
We did not run any transformation on the RWUS samples until all development on the transformations
had ceased. We also attempted to avoid allowing knowledge of the samples in the RWUS suite to influence
development of the transformations, although a single researcher was responsible for both.
Of the 90 transformed pairs, for 24 of them, the automatically transformed version was identical to the human
written one after reformatting. These are broken down per language in Table 2. Six automatically transformed
samples either failed their test suites or caused an error in the transformation program, while, for one sample, a
pretty-printer bug caused both the human-transformed and automatically transformed versions to fail to compile.
The remaining 63 pairs were sent to human judges for evaluation in Phase 3.
5.2.4 Phase 3: Comparing Human and Machine-Written Transformations. In Phase 3, we asked human judges from Mechanical
Turk to rate the manually-transformed code from Phase 2 along
with their automatically transformed counterparts.
Table 2. Counts of programs where presentation
We created one task on Mechanical Turk for each language/to the human judges was inappropriate
transformation combination. For each judge entering our website
interface, we began by presenting an explanation and example of the transformation, before presenting the
questions. Each question shows a sample program, along with the automatically transformed version produced
by our system, and the manually-transformed version collected in Phase 1. They were asked to rate both on a
1–5 scale. We instructed that they should first rate the transformed programs on correctness vs. the original
program, second on faithfulness to the intended transformation, and only third on general prettiness and code
quality. Both the order of questions and the order of the transformed pairs were randomized.
C Java JS Lua Python
Identical 6
9 1
5
3
Failed 0
1 4
0
1

5.2.5 Quality Control. The setup described above does not preclude someone from rating programs randomly,
so we employed two quality-control mechanisms. Our primary form of quality control was the creation of
"canary" questions. Canaries appear as normal questions, except that the programs contained therein were
contrived. In two of the canaries, one of the programs was clearly not a transformed version of the original. In
the third canary, both displayed programs were identical. We rejected any submission in which the worker did
not rate the correct program higher for the first two canaries, or did not rate both programs of the third canary
the same. Second, if a worker ever submitted two answers within 11 seconds of each other, we marked this
worker as untrustworthy, and rejected all submissions by him. We picked this value after observing the times
spent on each question in dry runs of the study.
We noticed substantial differences between workers who did and did not pass the quality controls. Workers with
one rejected submission typically had rejected submissions for many different languages. Workers with accepted
submissions were much more likely to only submit for one language. Workers typically either had all their
submissions accepted or all rejected. Furthermore, we noticed that rejected submissions were typically completed
in much less time than accepted ones, although many workers who failed the canaries were substantially slower
than the fastest correct workers.
The experimenters manually inspected a selection of judgments from accepted submissions, and found them
all reasonable. Overall, our observations suggest that our quality control mechanisms did effectively classify
workers on skill, and that our data is high-quality.
17

Fig. 17. Counts of differences between the ratings of the machine transformations and the human transformations. The
leftmost bars represent cases where the judge rated the machine-produced output higher than the human-produced.

5.2.6 Results. For each language, we tabulated the difference in ratings between the human-written and
automatically transformed programs. Our results are given in Figure 17. The average differences in ratings
ranged from −0.075 for Python (favoring the humans) to +0.633 for Java (favoring the machine). The differences
for C, JavaScript, and Lua were −0.014, +0.396, and −0.052 respectively.
Our goal was to show that the output of our transformations is not less readable than the human-transformed
code. This is a problem in statistics known as non-inferiority testing (Wellek 2010). For each language, we
formulated a hypothesis that the average difference in ratings between each the machine- and human- transformed
code is at least −1. We then factored in the pairs that were not sent to Phase 3: each identical pair was counted
as 10 judgments of equality (difference 0), and each pair where the machine-transformed version was incorrect
was counted as 10 judgments that maximally penalize the machine version (difference −4). We tested each of
the 5 hypotheses using a paired t-test. For each language, it showed that the machine-transformed code was
non-inferior by a non-inferiority margin of at least −1 with p < 10−9 . In retrospect, this data had the power to
prove the hypothesis with a much smaller non-inferiority margin.
Considering both the raw data and the statistical tests, our study provides strong evidence that the output of
transformations in Cubix is no less readable than hand-transformed code, showing that implementing source-tosource transformations with incremental parametric syntax avoids the mangling common to IR-based approaches.
5.2.7 Threats to Validity. Our results are potentially biased by using a real-world distribution of programming
constructs, as opposed to intentionally constructing a suite filled with corner cases. The humans are hindered
by a lack of learning: they only perform each transformation once per language. Finally, we cannot be certain
of the quality of the data from Mechanical Turk. In our dry runs, we found that workers on Mechanical Turk
tend to rate simple programs more highly, even when the transformation is incorrect. Two of our canaries are
specifically designed to prevent this behavior.

5.3

Correctness

As the third part of our evaluation, we claim that incremental parametric syntax makes it possible to write
transformations which are semantics-preserving, even against the complexities of multiple languages. We
ran our transformations on language test suites for each of the 5 languages, and checked whether they still
passed. Our results are promising, showing pass rates of 98.2%, 97.8%, and 95.8% for the Hoist, Testcov, and TAC
transformation respectively.
A caveat is that we depend on 3rd-party parsers and pretty printers, which exhibit incorrect behavior on many
of these tests. We hence could only evaluate our transformations on the tests for which they worked correctly.
Additionally, many of the tests are self-referential, and can fail if the formatting changes. Although we fixed
some bugs in all of our pretty-printers, only 90% of tests passed the identity transformation Ident, consisting of
a simple parse+pretty-print pass.
18

Table 3 lists the language implementations and test suites used in our evaluation. The C, Java, and Lua tests
come from their respective implementations, while the JavaScript ones come from the official specification
conformance test suite. The authors of K-Java report that no Java language tests are publicly available (Bogdanas
and Roşu 2015), and hence created their own specification tests, which we use. We restricted ourselves to the
core language tests of test262, and omitted a small handful of multi-file Java tests among the Java ones, which
caused problems with our test harness. We used the entirety of the Lua, Python, and C test suites.
The C, Java, and JavaScript tests are each distributed as standalone files, effectively containing a single test.
The Python ones are built using PyTest. Each test file contains potentially dozens of tests, but we report at file
granularity: if any tests in that file fail, we report that the file fails. The Lua ones are described below.
Table 4 shows the number of passing tests for each language and transformation. The Ident transformation is
a baseline transformation which simply parses and pretty prints a program, in order to filter out test cases which
fail due to bugs in our underlying parsers and pretty-printers, or due to overly self-referential test-cases. The
Hoist, Testcov, and TAC columns show the results of their respective transformations.
While only 93.9% of the lanLang
Implementation Test Suite
guage tests work with our 3rdC
GCC 6.3.0_1
gcc-torture (FSF 2016)
party infrastructure, of those,
Java
JDK 1.8.0_65
K-Java (Bogdanas and Roşu 2015)
our hoist transformation passes
JS
Node.js v0.10.24
test262 (TC39 2014)
98.2%, our test coverage passes
Lua
Lua.org 5.3.3
Lua Tests (PUC-Rio 2016)
97.8%, and our TAC transformaPython CPython 3.7.0a0
CPython Tests (Foundation 2017)
tion passes 95.8%. Our inspecTable 3. Language implementations and test suites used in our evaluation
tion shows the failures result
from minor bugs that would require small changes to correct, similar to the ones mentioned in Section 2.1.
Furthermore, one of the failing Java hoist tests resulted in a crash of javac. Manual inspection shows that this
program is indeed correct. The bug has been confirmed by the JDK developers (?).
We had substantial issues working with the Lua test suite. The Lua test suite is distributed as a single test
program, containing 28 files and 12,000 lines of code. The tests are highly self-referential, and include checks that
a symbol is defined on a certain line number, as well as checks that the current file has a certain character in a
certain position. The test suite also makes heavy use of the dynamism of Lua, including multiple points where it
undefines every global variable. Furthermore, the test suite is designed to stop at the first failed assertion. With
tests that break if a file changes character encoding, let alone a format-altering identity transformation, using
them to test correctness of our transformations would be a substantial endeavor.
We decided to modify the Lua test suite to maintain a count of passed assertions, instead of stopping at the first
failure, and to delete some of the overly self-referential assertions. In our resulting modified test suite, we found
that the total number of calls to assert was nondeterministic, but the number of failing assertions was not. In one
set of runs, we obtained the following numbers: 70440/70456 passing assertions for the original, 70279/70295
for the identity transformation, and 70463/70479 for hoisting. We gave up attempting to get it working for the
test coverage transform, due to crashes related to its metaprogramming around global variables. We similarly
gave up for the TAC transformation, because the Lua VM does not allow for more than 200 local variables in any
scope, and the TAC transformation easily overwhelms this on the test suite. We conclude that the Lua test suite
is overall unsuitable for testing program transformations.

6

RELATED WORK

Our work is most directly based on the data types à la carte approach to modular syntax (Swierstra 2008), and its
extensions in Bahr’s work on compositional datatypes (Bahr and Hvitved 2011). The extension of data types à la
carte to multi-sorted terms was introduced in Yakushev et al (Yakushev et al. 2009). Other approaches to modular
syntax include tagless-final (Kiselyov 2012), object algebras, and modular reifiable matching (Oliveira et al. 2016).
19

This work in modular syntax is joined by work in
Lang
Total Ident Hoist Testcov TAC
modular semantics, such as modular monadic semanC
1394
1304
1228
1280 N/A
tics (Liang et al. 1995a) and its cousin modular monadic
∗ 732
Java
755
738
726 N/A
meta-theory (Delaware et al. 2013b), as well as mod2638
2478
2478
2414 2420
JS
ular structural operation semantics (Mosses 2004).
Python
404
353
N/A
345
293
Sort injections are an instance of the concept of
Lua
Reported separately
feature interactions from the field of software product
* Not including test which crashed javac
lines (Van Gurp et al. 2001). A similar idea is seen in
Table 4. Results running each transformation on the language
the TruffleVM (Grimmer et al. 2015). The TruffleVM test suites
allows languages to read and write data structures
defined in other languages, by translating operations into language-independent "message nodes," and then into
operations in the target language for cross-language runtime compatibility. Their approach only addresses runtime
interoperation, and does not allow for use of language-independent nodes in an abstract syntax definitions.
The past decade has seen extensive work in language workbenches, which are designed to make it easy to
implement languages and transformations on them. They include Spoofax and its component Stratego (Kats and
Visser 2010), Rascal (Klint et al. 2009), TXL (Cordy 2006), Semantic Designs DMS (Baxter et al. 2004), and JetBrains
MPS (Voelter and Pech 2012). These were extensively surveyed in Erdweg et al (Erdweg et al. 2013). All these
share the limitation that, while they make it easy to define languages and write transformations, the resulting
transformations can only run on one representation of one language. At best they can be used to implement the
"Clang-style" common representation, discussed in Section 1.1.
One recent work that echoes our own is Brown et al’s (Brown et al. 2016) work using island grammars (Moonen
2001) to write static analyzers for multiple languages. They show that they only need to represent fragments of a
language to construct an analyzer. Their analyzers are still built for a single language, and they resort to cloning
code to implement them for others. They do not address transformation.
Incremental concrete syntax (Dinkelaker et al. 2013) is a technique for using island grammars to construct
parsers. It focuses on concrete syntax (i.e.: parsing), while ours focuses on abstract syntax (i.e.: representation).

7

CONCLUSION

Incremental parametric syntax fulfills a simple promise: when writing similar transformations for multiple
languages, they should be able to share code to the extent the languages are similar. It would be a straightforward
exercise to represent expressions in both C and Lisp using common fragments, and to then build a transformation
that operates on expressions of both. Handling C and Prolog, on the other hand, would be much more difficult.
Although this work focuses on the syntactic representation of programs, it is orthogonal to the problem of
using semantic information to guide a transformation: any transformation can simply demand that some semantic
information be available for a language, computed in whatever fashion. All of the transformations in this paper
use some form of static analysis, and, furthermore, we found that incremental parametric syntax made it vastly
easier to build analyses such as a CFG generator for multiple languages, although we’ve yet to attempt to build
multi-language dataflow analyzers or abstract interpreters atop it.
Incremental parametric syntax is just the beginning of building multi-language tools, and there is much more
work to be done. Verifying a multi-language transformation will require use of modular semantics, while using
parametric syntax to write a type-directed transformation will require integration with modular type systems.
The work in this paper is, to our knowledge, the first to allow a single program to perform source-to-source
transformations on multiple real languages while preserving the information of each. We believe incremental
parametric syntax solves a key problem in writing multi-language tools, and we believe this work is an important
step towards radically altering the economics of the software tools industry.
All code will be released on Github with the final version of the paper.
20

REFERENCES
Robert L. Akers, Ira D. Baxter, Michael Mehlich, Brian J. Ellis, and Kenn R. Luecke. 2005. Case Study: Re-engineering C++ Component Models
Via Automatic Program Transformation. Information & Software Technology 49 (2005), 275–291.
Patrick Bahr and Tom Hvitved. 2011. Compositional Data Types. In ICFP.
Ira D Baxter, Christopher Pidgeon, and Michael Mehlich. 2004. DMS®: Program Transformations for Practical Scalable Software Evolution.
In Proceedings of the 26th International Conference on Software Engineering. IEEE Computer Society, 625–634.
Denis Bogdanas and Grigore Roşu. 2015. K-Java: A Complete Semantics of Java. In ACM SIGPLAN Notices, Vol. 50. ACM, 445–456.
Niklas Broberg. 2015. language-java: Manipulating Java source: abstract syntax, lexer, parser, and pretty-printer. http://hackage.haskell.org/
package/language-java-0.2.8. (November 2015).
Fraser Brown, Andres Nötzli, and Dawson Engler. 2016. How to Build Static Checking Systems Using Orders of Magnitude Less Code. In
Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems. ACM,
143–157.
David Brumley, Ivan Jager, Thanassis Avgerinos, and Edward J. Schwartz. 2011. BAP: A Binary Analysis Platform. In CAV.
James R Cordy. 2006. The TXL Source Transformation Language. Science of Computer Programming 61, 3 (2006), 190–210.
Benjamin Delaware, Steven Keuchel, Tom Schrijvers, and Bruno C. d. S. Oliveira. 2013a. Modular Monadic Meta-Theory. In ICFP.
Benjamin Delaware, Steven Keuchel, Tom Schrijvers, and Bruno CdS Oliveira. 2013b. Modular Monadic Meta-Theory. ACM SIGPLAN Notices
48, 9 (2013), 319–330.
Isil Dillig, Thomas Dillig, and Alex Aiken. 2009. SAIL: Static Analysis Intermediate Language with a Two-level Representation.
Tom Dinkelaker, Michael Eichberg, and Mira Mezini. 2013. Incremental Concrete Syntax for Embedded Languages with Support for Separate
Compilation. Science of Computer Programming 78, 6 (2013), 615–632.
Sebastian Erdweg, Tijs Van Der Storm, Markus Völter, Meinte Boersma, Remi Bosman, William R Cook, Albert Gerritsen, Angelo Hulshout,
Steven Kelly, Alex Loh, and others. 2013. The State of the Art in Language Workbenches. In International Conference on Software Language
Engineering. Springer, 197–217.
Python Software Foundation. CPython Test Suite. Version 3.7.0a0. https://docs.python.org/devguide/runtests.html. (????).
Martin Fowler. 1999. Refactoring: Improving the Design of Existing Code. In XPU.
FSF. 2016. C Language Testsuites: “C-torture”. Revision 240758. http://gcc.gnu.org/onlinedocs/gccint/C-Tests.html. (October 2016).
Andy Gill. 2009. A Haskell Hosted DSL for Writing Transformation Systems. In Domain-Specific Languages. Springer, 285–309.
Matthias Grimmer, Chris Seaton, Roland Schatz, Thomas Würthinger, and Hanspeter Mössenböck. 2015. High-Performance Cross-Language
Interoperability in a Multi-Language Runtime. In ACM SIGPLAN Notices, Vol. 51. ACM, 78–90.
Benedikt Huber. language-c: Analysis and generation of C code. http://hackage.haskell.org/package/language-c. (????).
Lennart CL Kats and Eelco Visser. 2010. The Spoofax Language Workbench: Rules for Declarative Specification of Languages and IDEs. Vol. 45.
ACM.
Oleg Kiselyov. 2012. Typed Tagless Final Interpreters. In Generic and Indexed Programming. Springer, 130–174.
Paul Klint, Tijs Van Der Storm, and Jurgen Vinju. 2009. EASY Meta-programming with Rascal. In International Summer School on Generative
and Transformational Techniques in Software Engineering. Springer, 222–289.
Ralf Lammel and Chris Verhoef. 2001. Cracking the 500-language Problem. IEEE software 18, 6 (2001), 78–88.
Ralf Lämmel and Joost Visser. 2002. Typed Combinators for Generic Traversal. In International Symposium on Practical Aspects of Declarative
Languages. Springer, 137–154.
Ralf Lämmel and Joost Visser. 2003. A Strafunski Application Letter. In International Symposium on Practical Aspects of Declarative Languages.
Springer, 357–375.
Chris Lattner and Vikram S. Adve. 2004. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In CGO.
Sheng Liang, Paul Hudak, and Mark Jones. 1995a. Monad Transformers and Modular Interpreters. In Proceedings of the 22nd ACM SIGPLANSIGACT symposium on Principles of programming languages. ACM, 333–343.
Sheng Liang, Paul Hudak, and Mark P. Jones. 1995b. Monad Transformers and Modular Interpreters. In POPL.
Tim Lindholm, Frank Yellin, Gilad Bracha, and Alex Buckley. 2014. The Java Virtual Machine Specification: Java SE 8 Edition. Pearson
Education.
Leon Moonen. 2001. Generating Robust Parsers using Island Grammars. In Reverse Engineering, 2001. Proceedings. Eighth Working Conference
on. IEEE, 13–22.
Peter D. Mosses. 2004. Modular Structural Operational Semantics. J. Log. Algebr. Program. 60-61 (2004), 195–228.
George C. Necula, Scott McPeak, Shree Prakash Rahul, and Westley Weimer. 2002. CIL: Intermediate Language and Tools for Analysis and
Transformation of C Programs. In CC.
Bruno C d S Oliveira, Shin-Cheng Mu, and Shu-Hung You. 2016. Modular Reifiable Matching: A List-Of-Functors Approach to Two-Level
Types. ACM SIGPLAN Notices 50, 12 (2016), 82–93.

21

Ömer Sinan AÄ§acan and Eric Mertens. 2016. language-lua: Lua parser and pretty-printer. http://hackage.haskell.org/package/language-lua-0.
10.0. (August 2016).
Bernard James Pope. 2016. language-python: Parsing and pretty printing of Python code. http://hackage.haskell.org/package/
language-python-0.5.4. (July 2016).
PUC-Rio. 2016. Lua: Test suites. Version 5.3.3. https://www.lua.org/tests/. (2016).
Semantic Designs, Inc. 2005. Test Coverage tools. http://www.semanticdesigns.com/Products/TestCoverage/. (2005).
Tim Sheard and Simon Peyton Jones. 2002. Template Meta-programming for Haskell. In Proceedings of the 2002 ACM SIGPLAN Workshop on
Haskell. ACM, 1–16.
Wouter Swierstra. 2008. Data types à la Carte. Journal of functional programming 18, 04 (2008), 423–436.
Ecma TC39. 2014. Test262: ECMAScript Language Conformance Test Suite. Version 5.1. http://test262.ecmascript.org. (2014).
Danny van Bruggen. JavaParser: Process Java code programmatically. http://javaparser.org. (????).
Jilles Van Gurp, Jan Bosch, and Mikael Svahnberg. 2001. On the Notion of Variability in Software Product Lines. In Software Architecture, 2001.
Proceedings. Working IEEE/IFIP Conference on. IEEE, 45–54.
Markus Voelter and Vaclav Pech. 2012. Language Modularity with the MPS Language Workbench. In 2012 34th International Conference on
Software Engineering (ICSE). IEEE, 1449–1450.
Philip Wadler. 1987. Views: A way for pattern matching to cohabit with data abstraction. In Proceedings of the 14th ACM SIGACT-SIGPLAN
symposium on Principles of programming languages. ACM, 307–313.
Philip Wadler. 1998. The Expression Problem. Java-genericity mailing list (1998).
Stefan Wellek. 2010. Testing Statistical Hypotheses of Equivalence and Noninferiority. CRC Press.
Alexey Rodriguez Yakushev, Stefan Holdermans, Andres Löh, and Johan Jeuring. 2009. Generic Programming with Fixed Points for Mutually
Recursive Datatypes. In ACM Sigplan Notices, Vol. 44. ACM, 233–244.
Haoyuan Zhang, Zewei Chu, Bruno C. d. S. Oliveira, and Tijs van der Storm. 2015. Scrap Your Boilerplate with Object Algebras. In OOPSLA.
Alan Zimmerman. 2016. language-javascript: Parser for JavaScript. http://hackage.haskell.org/package/language-javascript-0.6.0.9. (November
2016).

A

THE ADT MODULARIZATION TRANSFORMATION

This section gives a formal definition for the ADT modularization transformation implemented in comptrans.
This algorithm transforms a syntax definition given as a family of mutually recursive ADTs into an equivalent
definition in the sum-of-signatures representations, expressed as a collection of GADT definitions combined with
an explicit sum and fixpoint.
Figure 18 gives a syntax for GADTs. GADTs and ADTs are given as a set of constructors with a given type. We
assume that there is a corresponding set of type constructors. We assume that ADTs have monomorphic types,
and their associated constructors have the base kind. Conversely, GADTs may have polymorphic types with
equality constraints, and their constructors may have higher kinds. We use the syntax ∀ν : k.D ⇒ σ as sugar for
nested forall types. The language includes two “container” functors, lists and pairs, to give an example of how
the transformation deals with containers embedded in syntax trees. Figure 19 gives the kinding rules for ADTs
and GADTs which check if the constructor types are well-formed. Γ is a local context storing all type variables in
scope, while we assume Φ has been populated with the types of all constructors declared.
To close a set of GADT definitions into a sum-of-signatures repreentation of a syntax, the language must be
extended with sum and recursive types, and with the ability to instantiate a polymorphic type. Figure 20 gives
this extension and the corresponding typing rules. Note that the sum types in this language are of polymorphic
kind. To avoid the need to track constraints with variables, the rule for polymorphic type application recurses
into the left-hand side until the constraint can be checked syntactically. This has the unfortunate consequence
that kind-checking may become circular. These typing rules should hence be interpreted with greatest fixed
point semantics, meaning that circularly-defined judgments hold.
Figure 22 gives the transformation algorithm. The transformation replaces every ADT constructor with a type
of kind ∗ with a GADT constructor with a type constructor of kind (∗ → ∗) → ∗ → ∗. More importantly, these
GADT type constructors do not refer to any other type definitions, with the exception of the “label” types, which
are purely nominal and uninhabited. It makes use of three auxilary functions. newcon(con) returns a fresh name
22

Kinds k ::= ∗ | k → k
Primitive types P ::= Int | Bool | . . .
Container functors F ::= List | Pair
Base types
Monotypes
Constraints
Polytypes

ν ::= α
τ ::= ν
D ::= ·
σ ::= τ

| C | F | P | νν
|ν →τ
|α ∼ν
| ∀α : k.D ⇒ τ

Constructors c ::= conσ
Fig. 18. A syntax for GADTs

for a GADT constructor. newconType(ν ) does similar for the corresponding type constructors. lab(C) maps each
constructor C to a corresponding “label” constructor of kind ∗.
Of final note, in order to inhabit terms of sort List γ or Pair γ ι, there are three specially-defined constructors,
given in Figure 21. These are given Curry-style types, meaning their types contain an unbound variable, and
they may be given a type for any instantiation of that variable.
We are now ready to state the property this transformation was designed to satisfy: For a family of mutually
recursive ADTs defined by conσ with root type C, C is equivalent to the sum of the generated GADTs at sort
lab(C). Formally, if Φ contains the types for all declared ADT constructors and Φ ` con σ okay, then
Õ
Φ ` C ≡ (µα : ∗ → ∗.(PairF + ListF +
transType(s)) α) lab(C)
s ∈σ

Here, ≡ denotes the classical notion of a type isomorphism, i.e.: the presence of a pair of mutually inverse
functions that convert from one to the other. This is still an informal statement, albeit in formal notation, as
we have not fully defined the language of terms which is needed to make this statement fully rigorous. The
description in this section is meant only to unambiguously describe the algorithm.

23

Γ; Φ ` P : ∗

PRI M

Γ; Φ ` List : ∗ → ∗

LIST

Γ; Φ ` Pair : ∗ → ∗ → ∗

PAIR

α :k ∈ Γ
V AR
Γ; Φ ` α : k
C :k ∈Φ
CON
Γ; Φ ` C : k
Γ; Φ ` ν 1 : k 1 → k ) Γ; Φ ` ν 2 : k 2
APP
Γ; Φ ` ν 1ν 2 : k 2
Γ; Φ ` ν : ∗ Γ; Φ ` τ : ∗
ARR
Γ; Φ ` ν → τ : ∗
Γ, α : k; Φ ` τ : ∗
FORALL
Γ; Φ ` ∀α : k.D ⇒ τ : ∗
·; Φ ` σ : ∗
Φ ` conσ okay
Fig. 19

24

σ ::= . . . | σ + σ | µα : k.σ | σν
Γ; Φ ` σ1 : k Γ; Φ ` σ2 : k
POLY − SU M
Γ; Φ ` σ1 + σ2 : k
Γ, α : k; Φ ` σ : k
REC
Γ; Φ ` µα : k.σ : k
Γ, Φ ` σν : k
POLY − APP − SU M − LEFT
Γ, Φ ` (σ + σ 0)ν : k
Γ, Φ ` σ 0ν : k
POLY − APP − SU M − RIGHT
Γ, Φ ` (σ + σ 0)ν : k
Γ, Φ ` ([(µα : k.σ )/α]σ )ν : k
POLY − APP − REC
Γ, Φ ` (µα : k.σ )ν : k
Γ, Φ ` ν : k 0 Γ, Φ ` σ 0[ν /α] : k
POLY − APP
Γ, Φ ` (∀α : k 0 .· ⇒ τ )ν : k 0 → k
Γ, Φ ` σ 0[ν /α] : k
Γ, Φ ` (∀α : k.α ∼ ν ⇒ τ )ν : k

POLY − APP − CON ST RAI NT

Fig. 20

ConsF :
NilF :
PairF :

∀ (α : ∗ → ∗) (γ : ∗).γ ∼ List ι ⇒ α ι → α γ → ListF α γ

for any ι

∀ (α : ∗ → ∗) (γ : ∗).γ ∼ List ι ⇒ ListF α γ

for any ι

∀(α : ∗ → ∗) (γ : ∗).γ ∼ (Pair ι κ) ⇒ α ι → α κ → PairF α γ

for any ι, κ

Fig. 21

25

trans(conτ )
trans(conτ ) = newcon(con)transTypeTop(τ )
transTypeTop(τ )
transTypeTop(τ ) = ∀(α : ∗ → ∗) (γ : ∗).transType(τ , α, γ )
transType(τ , α, γ )
transType(ν → τ , α, γ )
transType(C, α, γ )

= transTypeBase(ν, α, γ ) → transType(τ , α, γ )
= newconType(C) α γ
transTypeBase(ν, α, γ )

transTypeBase(P, α, γ )
transTypeBase(Fν, α, γ )
transTypeBase(C, α, γ )

=P
= α (F transTypeBase(ν ))
= α lab(C)

Fig. 22

26

