A Syntax for Composable Data Types in Haskell, A User-friendly Syntax for Solving the Expression Problem
Ladda ner
Typ
Examensarbete för masterexamen
Master's Thesis
Master's Thesis
Program
Computer science – algorithms, languages and logic (MPALG), MSc
Publicerad
2023
Författare
Romeborn, Anna
Albers, Fredrik
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
The expression problem is the problem of designing a programming language such that it has both extensible data types and extensible sets of functions over those data types. This means that it should be possible to add new functions, new variants to a
data type, and function cases for these new variants, without modification or recompilation of existing code. There exist a number of different approaches to solving the expression problem, which have different qualities in expressiveness or simplicity.
In this thesis, we have designed a syntax, with an accompanying transformation into compilable code, that acts as a solution to the expression problem in Haskell. By designing this syntax, we can make simplifications that would not be possible for solutions written directly in Haskell. In particular, we can, behind our syntax, abstract away some syntactic overhead that can be generated by the transformation.
To demonstrate that our designed syntax is feasible and works as an extension to Haskell, we have implemented the transformation, which transforms code written using our syntax into code that uses the Haskell library compdata. That library is an existing solution to the expression problem, and is based on another solution:Data Types à la Carte. Both of these solutions share many similarities in semantics with our syntax.
Similarly to compdata and Data Types à la Carte, data types in our syntax are composable; that is, variants of a data type are manually combined to form a type with a fixed set of possible variants. We introduce a new concept, called categories, with the purpose of grouping variants and compositions of data types and simplifying the syntax into one closer to that of regular data types. This means that compositions of variants can only be formed of variants belonging to the same category, as opposed to freely being able to combine any variants. Again, similar to compdata and Data Types à la Carte, functions over composable data types are extended automatically in our syntax. This means that a function can be used for a variant of the data type as long as the function has a case defined for the variant. Through the introduction of categories and the abstractions possible through the transformation, we are able to conclude that our syntax provides several improvements compared to existing solutions to the expression problem in Haskell.
Beskrivning
Ämne/nyckelord
The expression problem , Haskell , programming language design , programming language , composable , extensible , functional programming