Introduction
Programs are data structures
AE ::= num
| AE + AE
| AE - AE
| (AE)
Examples----
4
1+3
(2 + 2) + (5 - 7)
1 + 3 - (5 + (8 - 4))
The set AE:
Infinitely big
Elements are finite
Recursive
Inductive
Concrete Syntax - What programmers write
Abstract Syntax - What the interpreter operates over
Example of abstract data type:
data AE where
NUM :: Int -> AE
PLUS :: AE -> AE -> AE
MINUS :: AE -> AE -> AE
deriving (Show, Eq)
AE - Name of the Type
Introduction 1
Num, Plus, Minus - Constructors: construct elements of the type. All elements of the type are
constructed here
“AE → AE → AE” - Signature
We will write an interpreter over AE
This is not the standard syntax for a Haskell algebraic type, but instead uses the GADT form.
It is equivalent to:
data AE =
Num Int
| Plus AE AE
| Minus AE AE
deriving (Show, Eq)
Parser - Concrete syntax → abstract syntax
expr :: Parser AE
expr = buildExpressionParser operators term
operators = [ [ inFix "+" Plus AssocLeft
, inFix "-" Minus AssocLeft ]
]
numExpr :: Parser AE
numExpr = do i <- integer lexer
return (Num (fromInteger i))
term = parens lexer expr
<|> numExpr
parseAE = parseString expr
Introduction 2
Examples:
(parse "3") == (Num 3)
(parse "3 + 4") == (Plus (Num 3) (Num 4))
(parse "((3 - 4) + 7)" == (Plus (Minus (Num 3) (Num 4)) (Num 7))
Parsers are solved problems and this is the last we will speak of them in detail.
Monadic Interpreters
We will learn about languages by building interpreters for them in Haskell
The general notion of an interpreter maps a language to a value.
E : L− > V
E is our interpreter, L is our language, V is our value
Values are good results. Cannot be evaluated further
Starting with the simplest language ever:
AE ::= num
data AE where
Nat :: Int -> AE
(deriving Eq, Show)
Nat - constructor
eval :: AE -> Int
A parser will translate numbers into AE:
Introduction 3
parse "1" == (Nat 1)
parse "2" == (Nat 2)
parse "a" == !
parse "1+2" == !
An interpreter will translate AE into values:
eval::AE -> Int
eval (Nat x) = x
All together now
interp x = eval (parse x)
interp "1" == 1
interp "3" == 3
or
interp = eval . parse
Let’s add addition to our language
data AE where
Nat :: Int -> AE
Plus :: AE -> AE -> AE
(deriving Eq, Show)
This is not much harder:
eval :: AE -> Int
eval (Nat x) = x
eval (Plus x y) = eval x + eval y
Introduction 4
x and y in Plus are bound to input arguments
eval (Plus (Nat 1) (Nat 3))
== (eval (Nat 1) + (eval (Nat 3))
== 1 + 3
== 4
Do programs in AE terminate? - Yes and that’s okay
Do programs in AE ever crash? - No
But you can’t do anything useful with this language
Let’s add Minus
data AE where
Nat :: Int -> AE
Plus :: AE -> AE -> AE
Minus :: AE -> AE -> AE
(deriving Eq, Show)
…Extend eval with a new case
eval :: AE -> Int
eval (Nat x) = x
eval (Plus x y) = eval x + eval y
eval (Minus x y) = eval x - eval y
What does Minus force us to deal with? - Errors (can’t get negative naturals)
Simple error handling using error
eval (Minus l r) = let x = (eval l) - (eval r) in
if x<0 then error "!" else x
Or, to return an error value
Introduction 5
eval (Minus l r) = let x = (eval l) - (eval r) in
if x<0 then else x
Introduction 6