Recently I thought it would be good to start compiling the small functional language mimsa I’ve been messing around with for the last few years to LLVM. There’s a few really helpful resources - Joseph Morag’s Micro-C series, and Mapping High Level Concepts to LLVM IR in particular, but neither go into converting functional programming paradigms such as pattern matching, lambdas and ADTs in much depth.
So, here we’re going to give it a go. The plan is that we start with an entirely working but tiny language, get it all working, and then as we add features to the language, we’ll also add a typechecker and introduce more LLVM concepts. The source code for the whole working calculator, along with a basic repl, can be found at llvm-calc.
Our language
The first iteration of our language is going to be the most basic of calculators. Here is a valid program in our language:
1 + 2 * ( 1 + 100 ) - 100 + 2+ 100100
Here are the datatypes for our language. We will use this to represent our programs internally.
data Expr ann ann = -- | An integer value EPrim ann Int ann | -- | Two values combined with an operator EInfix ann Op ( Expr ann) ( Expr ann) annann) (ann) deriving stock ( Eq , Ord , Show , Functor , Foldable , Traversable ) stock ( -- | Operators for combining integers data Op = OpAdd | OpMultiply | OpSubtract deriving stock ( Eq , Ord , Show ) stock (
Here’s some example values:
-- | the number `1` one :: Expr () () = EPrim () 1 one() -- | the expression `2 + 3` twoPlusTwo :: Expr () () = EInfix () OpAdd ( EPrim () 2 ) ( EPrim () 3 ) twoPlusTwo()()) (()
We call datatypes like Expr Abstract Syntax Trees (or ASTs).
... continue reading