Visible to the public Programmable Semantic Fragments: The Design and Implementation of Typy

TitleProgrammable Semantic Fragments: The Design and Implementation of Typy
Publication TypeConference Paper
Year of Publication2016
AuthorsOmar, Cyrus, Aldrich, Jonathan
Conference NameProceedings of the 2016 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences
Date PublishedOctober 2016
Conference LocationNew York, NY, USA
ISBN Number978-1-4503-4446-3
Keywordsbidirectional typechecking, composability, compositionality, foreign function interfaces, metaprogramming, Pattern matching, pubcrawl

This paper introduces typy, a statically typed programming language embedded by reflection into Python. typy features a fragmentary semantics, i.e. it delegates semantic control over each term, drawn from Python's fixed concrete and abstract syntax, to some contextually relevant user-defined semantic fragment. The delegated fragment programmatically 1) typechecks the term (following a bidirectional protocol); and 2) assigns dynamic meaning to the term by computing a translation to Python. We argue that this design is expressive with examples of fragments that express the static and dynamic semantics of 1) functional records; 2) labeled sums (with nested pattern matching a la ML); 3) a variation on JavaScript's prototypal object system; and 4) typed foreign interfaces to Python and OpenCL. These semantic structures are, or would need to be, defined primitively in conventionally structured languages. We further argue that this design is compositionally well-behaved. It avoids the expression problem and the problems of grammar composition because the syntax is fixed. Moreover, programs are semantically stable under fragment composition (i.e. defining a new fragment will not change the meaning of existing program components.)

Citation Keyomar_programmable_2016