28 Years of Types for Untyped Languages: A Random Walk Thru TypeLand
Adding type systems to dynamically typed programming languages is a research topic with a 40 year history. With the wide-spread use of scripting languages – many of which are dynamically typed – this research agenda has gained a new urgency. It is thus a good time to stop and look back so that we don’t repeat past mistakes in the future.
Over the past three decades, people have referred to the area by various names, including “Typed Lisp” and “broad-spectrum” languages. My research group has investigated the topic for 28 years now. For the first 15 years, we explored the approach of soft-typing untyped programs via type inference based on Hindley-Milner and on set-based analysis. For the past few years, we have explored two novel ideas: the use of explicit type annotations and a focus on incremental program conversion based on large-grained units of code.
In this talk, I will report on our successes and our failures. I will state the parameters of the field and argue for and against the decisions that we made within this space. The goal is to help others with their work as they enter this important research area.
Matthias Felleisen, a Trustee Professor at Northeastern University’s College of Computer Science, has spent 30 years exploring programming languages and the pedagogy of software development. After receiving his PhD at Indiana University in 1987, he launched his academic career at Rice University; in 2001, he moved to Northeastern.
For the first decade of his career, Felleisen developed a new theoretical framework for modeling programming languages. Over time, this framework has provided the most widely used technique for proving type soundness theorems, the fundamental correctness claims for programming languages.
In 1995, Felleisen launched two related projects: (1) a K-12 outreach project with the goal of synthesizing mathematics and programming education and (2) the Racket language design project in support of the outreach project. Felleisen and his team taught dozens of intensive 5-day teacher training workshops over 20 years, focusing on program design as systematic problem solving. Working with Northeastern undergraduates, they also created the Bootstrap curriculum for middle schools; the curriculum has been adopted by code.org. The team’s Racket programming language has become a test bed for language design ideas from mixins to frameworks for domain-specific languages, from software contracts to gradual typing systems, and from web programming disciplines to distributed interactions. It is used in many applications, from DoD software to Naughty Dog’s games.
For his research on programming languages, Felleisen was inducted as an ACM Fellow in 2006 and received ACM SIGPLAN’s Achievement Award in 2012. Also in 2012, his paper on contracts for higher-order languages was picked asthe most influential ICFP 2002 publication. Felleisen has delivered keynote addresses at many programming language conferences, including POPL, ECOOP, and ICFP. For his educational outreach, ACM honored Felleisen with the Karl V. Karlstrom Award in 2010. ACM SIGCSE named Felleisen Outstanding Educator of the Year in 2011. In conjunction with the latter, he delivered the keynote at the annual Symposium on Computer Science Education.