A Useless Compiler in PureScript
This week I’ve decided to write some code in PureScript that resembles a compiler. As for the last few posts, I’ve limited the scope to the smallest possible unit.
That means, I haven’t had much time to learn about compilers myself. Hopefully, this will prove useful foundation when I’ll decide to dive deeper.
As long as I understand, a compiler consists of a series of steps that take some input code and transforms it into the target language.
As an input we will use a language that supports two operations (i.e.
sub) on integers. In particular, we will use as an input the following code:
add 1 sub 6 add 3 2.
The first thing we want to do is to parse the code into an Abstract Syntax Tree (AST). In other words, a structure that enables us to work easily with the code. The AST for the example code provided above would look like
add / \ 1 sub / \ 6 add / \ 3 2
The code to do that is the following
data Ast = Node Op Ast Ast | Value Int instance showAst :: Show Ast where show (Node op ast1 ast2) = "(" <> show op <> " " <> show ast1 <> " " <> show ast2 <> ")" show (Value i) = show i data Op = Add | Sub instance showOp :: Show Op where show Add = "Add" show Sub = "Sub" astParser :: Parser Ast = do astParser skipSpaces<- opParser op skipSpaces<- valueParser <|> astParser ast1 skipSpaces<- valueParser <|> astParser ast2 pure $ Node op ast1 ast2 opParser :: Parser Op = opParser <|> subParser addParser addParser :: Parser Op = do addParser <- string "add" _ pure Add subParser :: Parser Op = do subParser <- string "sub" _ pure Sub intParser :: Parser Int = do intParser <- many1 anyDigit ds case fromString $ fromChars ds of Just i -> pure i Nothing -> fail "I was expecting an int!" valueParser :: Parser Ast = do valueParser <- intParser i pure $ Value i
Generation / Evaluation
With the AST at our disposal we can either compile to some other language or evaluate the code:
generate :: Ast -> String Value i) = show i generate (Node Add ast1 ast2) = generate ("(" <> generate ast1 <> " + " <> generate ast2 <> ")" Node Sub ast1 ast2) = generate ("(" <> generate ast1 <> " - " <> generate ast2 <> ")" evaluate :: Ast -> Int Value i) = i evaluate (Node Add ast1 ast2) = evaluate (+ evaluate ast2 evaluate ast1 Node Sub ast1 ast2) = evaluate (- evaluate ast2 evaluate ast1
input :: String = input "add 1 sub 6 add 3 2" main :: Effect Unit = do main $ runParser astParser input logShow -- (Right (Add 1 (Sub 6 (Add 3 2)))) $ map generate $ runParser astParser input logShow -- (Right "(1 + (6 - (3 + 2)))") $ map evaluate $ runParser astParser input logShow -- (Right 2)
If you want to read more, this is what inspired me to take a few steps into the compilers world:
- The Super Tiny Compiler
- Tiny Interepter and Compiler
If you liked the post and want to help spread the word, please make some noise 🤘 But only if you really liked it. Otherwise, please feel free to comment or tweet me with any suggestions or feedback. And please do cause I need help with my FP!
Support my work by tweeting this article! 🙏