Incremental development is an essential feature of modern software
engineering and greatly improves programmer productivity. Software
teams rapidly develop prototypes and then iteratively refine the
prototypes into production systems. However, today’s programming
systems do not support a smooth transition from prototyping to
production. On one hand, dynamic languages such as MATLAB and Python
support prototyping while on the other hand static languages such as
C++ and Java support the development of reusable and efficient
production codes. Neither support both prototyping and production, so
developers use a mixture of programming systems. This practice incurs
many costs such as the impedance mismatches of inter-language data
transfers and the time to translate programs between languages.

The goal of the project "CAREER: Bridging the Gap Between Prototyping
and Production" was to make progress towards having a single
programming system that would support a gradual transition from
prototyping to production. To accomplish the research objective, the
long-standing conflicts between flexibility and safety and between
abstraction and performance need to be resolved.  Regarding flexibilty
versus safety, the project investigated the idea of gradual typing,
which combines both static and dynamic type checking within the same
language. Regarding abstraction and performance, the project
investigated the compilation of a high-level language for matrix
algebra into high-performance code. We discuss the scientific
accomplishments on these two lines of research in the following
paragraphs.  But to summarize the outputs of the project, we published
18 papers including 9 at high-impact conferences and journals. We
graduated 2 Ph.D. students and 2 M.S. students and 3 more
Ph.D. students are in progress. The project also produced two software
artifacts that have been released to the public, a gradually typed
version of the Python programming language, and the Build-to-Order
Basic Linear Algebra Subroutines, about which we will say more below.

The project made significant discoveries regarding both the theory and
practice of gradual typing. On the theory side, we discovered how to
integrate gradual typing with parametric polymorphism (aka. generics)
in a way that preserves "parametricity", which is import for reasoning
about the correctness of polymorphic procedures.  We solved the space
complexity problem that arises from the use of proxies to ensure the
safety of statically typed code that interacts with dynamically typed
code. We also solved problems regarding runtime overhead in statically
typed code (not just in partially typed or dynamically typed
code). Finally, we developed formal criteria to better characterize
when a language design satisfies the intent of gradual typing.

Regarding the practice of gradual typing, we designed and implemented
a gradually typed variant of Python, named Reticulated Python.  We
encountered a number of challenges along the way and invented
solutions to them, including "transient casts", which guarantee the
safety of statically typed code without using proxies, thereby
avoiding interoperability problems that we encountered regarding plain
Python code and with code written in C (parts of the Python standard
library, and many extensions). Another significant challenge to
gradual typing is that the performance of partially typed code can
degrade significantly. To solve this problem, we have initiated two
projects. We are investigating whether just-in-time compilation can
improve performance by implementing the Racket language using the
RPython framework. In the second project, we are building a native
code ahead-of-time compiler that implements the theoretical advances
mentioned above.  So far, both the just-in-time and ahead-of-time
compilers are showing promise and delivering good performance on
benchmark programs.

The second line of research in this project was in the compilation of
a language for matrix algebra into high-performance parallel code.
The goal of our compiler was to produce the best-possible code for a
particular combination of matrix operations. For example, it compiles
the input program
    y := b * A' * (A * x)
into low-level C code that is organized to make best use of multiple
processors and the multiple levels of cache memory within a computer.
The code transformations to accomplish this are well known: loop
fusion, array contraction, and data parallel loops.  However, the the
techniques are not beneficial in every situation, so the challenge is
finding the the best combination of transformations for a given input
program and target computer architecture. Thus, the essense of the
problem is mathematical optimization and search. We evaluated a wide
variety of search techniques, including genetic algorithms and
hill-climbing, and we developed a new heuristic/greedy search
algorithm.  We found that the best approach was a hybrid that started
with our greedy search and then finished with a genetic search.  With
this approach we were able to generate code for a wide range of
real-world matrix computations that was just as efficient as code
produced by a human expert and that out-performed the best
general-purpose loop-optimizing compilers.

Last Modified: 11/17/2016
Modified by: Jeremy G Siek