[SOLVED] CS Haskell interpreter | A simple expression language with two types.

| A simple expression language with two types.
module IntBool where

import Prelude hiding (not,and,or)

Syntax of the core IntBool language

int::=(any integer)

exp::=intinteger literal
| exp + expinteger addition
| exp * expinteger multiplication
| exp = expcheck whether two expressions are equal
| exp ? exp : expconditional expressions

1. Define the abstract syntax as a Haskell data type.

data Exp
= Lit Int
| Add Exp Exp
| Mul Exp Exp
| Equ Exp Exp
| IfExp Exp Exp
deriving (Eq,Show)

Here are some example expressions:
* encode the abstract syntax tree as a Haskell value
* what should the result be?

| 2 * (3 + 4)=>14
ex1 :: Exp
ex1 = Mul (Lit 2) (Add (Lit 3) (Lit 4))

| 2 * (3 + 4) = 10=>false
ex2 :: Exp
ex2 = Equ ex1 (Lit 10)

| 2 * (3 + 4) ? 5 : 6=>type error!
ex3 :: Exp
ex3 = If ex1 (Lit 5) (Lit 6)

| 2 * (3 + 4) = 10 ? 5 : 6=>6
ex4 :: Exp
ex4 = If ex2 (Lit 5) (Lit 6)

2. Identify/define the semantic domain for this language.
* what types of values can we have?
* how can we express this in Haskell?

Types of values we can have:
* Int
* Bool
* Error

data Value
= I Int
| B Bool
| Error
deriving (Eq,Show)

Alternative semantics domain using Maybe and Either:

data Maybe a = Nothing | Just a
data Either a b = Left a | Right b

type Value = Maybe (Either Int Bool)

Example semantic values in both representations:

I 5 <=>Just (Left 5)
B True<=>Just (Right True)
Error <=>Nothing

Isomorphic to the above:
type Value = Maybe (Either Bool Int)
type Value = Either (Maybe Int) Bool
type Value = Either Int (Maybe Bool)
type Value = Either (Either Int Bool) ()

Not isomorphic to the above
type Value = Either (Maybe Int) (Maybe Bool)
(reason: two different Nothings! Left Nothing and Right Nothing)

3. Define the semantic function.
eval :: Exp -> Value
eval (Lit i)= I i
eval (Add l r)= case (eval l, eval r) of
(I i, I j) -> I (i + j)
_-> Error
eval (Mul l r)= case (eval l, eval r) of
(I i, I j) -> I (i * j)
_-> Error
eval (Equ l r)= case (eval l, eval r) of
(I i, I j) -> B (i == j)
(B a, B b) -> B (a == b)
_-> Error
eval (If c t e) = case eval c of
B True-> eval t
B False -> eval e
_ -> Error

4. Syntactic sugar.

Goal: extend the syntax of our language with the following operations:

* boolean literals
* integer negation
* boolean negation (not)
* conjunction (and)
* disjunction (or)

How do we do this? Can we do it without changing the abstract syntax
or the semantics?

true :: Exp
true = Equ (Lit 1) (Lit 1)

false :: Exp
false = Equ (Lit 0) (Lit 1)

neg :: Exp -> Exp
neg e = Mul (Lit (-1)) e

not :: Exp -> Exp
not e = If e false true
not e = Equ false e

and :: Exp -> Exp -> Exp
and l r = If l (If r true false) false

or :: Exp -> Exp -> Exp
or l r = If l true (If r true false)

| Example program that uses our syntactic sugar.
not true || 3 = -3 && (true || false)->false
ex5 :: Exp
ex5 = or (not true) (and (Equ (Lit 3) (neg (Lit 3))) (or true false))

* Statically typed variant (later!)

1. Define the syntax of types.

2. Define the typing relation.
typeOf = undefined

3. Define the semantics of type-correct programs.
evalChecked = undefined

| Helper function to evaluate an Exp to an Int.
evalInt :: Exp -> Int
evalInt e = case evalChecked e of
Left i -> i
_ -> error internal error: expected Int, got something else!

| Helper function to evaluate an Exp to an Bool.
evalBool :: Exp -> Bool
evalBool e = case evalChecked e of
Right b -> b
_ -> error internal error: expected Bool, got something else!

4. Define our interpreter.
checkAndEval = undefined