Prototyping a Functional Language using Higher-Order Logic Programming: A Functional Pearl on Learning the Ways of Lambda-Prolog/Makam

Antonis Stampoulis, Adam Chlipala. Prototyping a Functional Language using Higher-Order Logic Programming: A Functional Pearl on Learning the Ways of Lambda-Prolog/Makam. Proceedings of the 23rd ACM SIGPLAN International Conference on Functional Programming (ICFP'18). September 2018.

Coming soon!

We demonstrate how the framework of higher-order logic programming, as exemplified in the Lambda-Prolog language design, is a prime vehicle for rapid prototyping of implementations for programming languages with sophisticated type systems. We present the literate development of a type checker for a language with a number of complicated features, culminating in a standard ML-style core with algebraic datatypes and type generalization, extended with staging constructs that are generic over a separately defined language of terms. We add each new feature in sequence, with little to no changes to existing code. Scaling the higher-order logic programming approach to this setting required us to develop approaches to challenges like complex variable binding patterns in object languages and performing generic structural traversals of code, making use of novel constructions in the setting of Lambda-Prolog, such as GADTs and generic programming. For our development, we make use of Makam, a new implementation of Lambda-Prolog, which we introduce in tutorial style as part of our (quasi-)literate development.

Project site