Acknowledgements: I originally created these slides in Fall 2017 to accompany what is now Chapter 42, Calculator: Abstract Syntax & Evaluation, in the 2018 version of the textbook Exploring Languages with Interpreters and Functional Programming.

Browser Advisory: The HTML version of this document may require use of a browser that supports the display of MathML. A good choice as of November 2018 is a recent version of Firefox from Mozilla.

Calculator: Abstract Syntax & Evaluation

Lecture Goals

Examine interpreter for simple ELI Calculator language
- abstract syntax
- values
- environments
- semantics and evaluation
- simplification (code improvement, optimization)

Concrete vs. Abstract Syntax

Concrete syntax: express language details in text strings (source code) — Ch. 41
Abstract syntax: express essential structure, ignore incidental representation issues (intermediate representation) — this chapter

Abstract Syntax Data Type

Abstract Syntax module exports data type definition

    import Values ( ValType, Name ) 

    data Expr = Add Expr Expr 
              | Sub Expr Expr 
              | Mul Expr Expr 
              | Div Expr Expr 
              | Var Name 
              | Val ValType 
                -- deriving Show? or custom?

Abstract Syntax Show Instance (1)

Abstract Syntax module encapsulates instance definition

    instance Show Expr where 
        show (Val v)   = show v 
        show (Var n)   = n 
        show (Add l r) = showParExpr "+" [l,r]
        show (Sub l r) = showParExpr "-" [l,r]
        show (Mul l r) = showParExpr "+" [l,r]
        show (Div l r) = showParExpr "/" [l,r]

Abstract Syntax Show Instance (2)

    showParExpr :: String -> [Expr] -> String
    showParExpr op es = 
        "(" ++ op ++ " " ++ showExprList es ++ ")"
    
    showExprList :: [Expr] -> String
    showExprList es = Data.List.intercalate " " (map show es)

Abstract Syntax Examples

    Val 3                  -- 3   -- left if "deriving Show"
    Val (-3)               -- -3
    Var "x"                -- x 
    Add (Val 1) (Val 1)    -- 1+1    -- (+ 1 1)
    Add (Var "x") (Val 3)  -- x + 3  -- (+ x 3)
                           -- (x + y) * (2 - z)
                           -- (* (+ x y) (- 2 z))
    Mul (Add (Var "x") (Var "y")) (Sub (Val 2) (Var "z"))

Abstract Syntax Tree (1)

AST for 1 + 1

Abstract Syntax Tree (2)

AST for (x + y) * (2 - z)

Values Module

Values module encapsulates representation of values (e.g. Int vs. Integer) — flexibility for future

    type Name    = String 
    type NumType = Int 
    type ValType = NumType 

    defaultVal :: ValType
    -- several other functions

Environment

Environment:: Map variable names to value

Look up value of variable in expression during evaluation
Given environment { x -> 5 }, expression x + 3 yields 8
Can use association list [("x",5)], Data.Map, etc.

Environments Module (General)

Environments module encapsulates representation of environment (polymorphic) — flexibility for future

    import Values ( ValType, Name, defaultVal ) 
    type AnEnv a = [(Name,a)]

    newEnv     :: AnEnv a 
    toList     :: AnEnv a -> [(Name,a)]
    getBinding :: Name -> AnEnv a -> Maybe a 
    hasBinding :: Name -> AnEnv a -> Bool 
    newBinding :: Name -> a -> AnEnv a -> AnEnv a 
    setBinding :: Name -> a -> AnEnv a -> AnEnv a 
    bindList   :: [(Name,a)] -> AnEnv a -> AnEnv a

Calculator Language Environment

From Evaluator module

    import Values       ( ValType, Name, defaultVal ) 
    import Environments ( AnEnv, Name, newEnv, toList, getBinding,
                          hasBinding, newBinding, setBinding, bindList )

    type Env = AnEnv ValType  -- map Name to ValType value

Informal Semantics of AST

Val c — constant (NumType) value c
Var n — value of variable n in current environment, gives error if not defined
Add l r — sum of values of expressions l, r
Sub l r — difference between values of expressions l, r
Mul l r — product of values of expressions l, r
Div l r — quotient of values of expressions l, r

Evaluation Module (1)

Encapsulates semantics (evaluation function)
Exports evaluation function eval primarily

Evaluation Module (2)

    import Values       ( ValType, Name, defaultVal )
    import AbSynCalc    ( Expr(..) )
    import Environments ( AnEnv, Name, newEnv, toList, getBinding,
                          hasBinding, newBinding, setBinding, bindList )
    type EvalErr = String
    type Env     = AnEnv ValType

    eval :: Expr -> Env -> Either EvalErr ValType
    eval (Val v) _   = Right v
    eval (Var n) env = 
        case getBinding n env of
            Nothing -> Left ("Undefined variable " ++ n)
            Just i  -> Right i
    eval (Add l r) env =
        case (eval l env, eval r env) of
            (Right lv, Right rv) -> Right (lv + rv)
            (Left le,  Left re ) -> Left (le ++ "\n" ++ re)
            (x@(Left le),  _   ) -> x
            (_,     y@(Left le)) -> y

Evaluation Module (3)

    eval (Sub l r) env = 
        case (eval l env, eval r env) of
            (Right lv, Right rv) -> Right (lv - rv)
            (Left le,  Left re ) -> Left (le ++ "\n" ++ re)
            (x@(Left le),  _   ) -> x
            (_,     y@(Left le)) -> y
    eval (Mul l r) env = 
        case (eval l env, eval r env) of
            (Right lv, Right rv) -> Right (lv * rv)
            (Left le,  Left re ) -> Left (le ++ "\n" ++ re)
            (x@(Left le),  _   ) -> x
            (_,     y@(Left le)) -> y
    eval (Div l r) env =
        case (eval l env, eval r env) of
            (Right _,  Right 0 ) -> Left "Division by 0"
            (Right lv, Right rv) -> Right (lv `div` rv)
            (Left le,  Left re ) -> Left (le ++ "\n" ++ re)
            (x@(Left le),  _   ) -> x
            (_,     y@(Left le)) -> y

Simplification (Optional Phase)

Simplify items based on operator properties to give faster execution, smaller trees (code improvement)

    simplify :: Expr -> Expr  -- parts left as exercise
    simplify (Add l r) =
        case (simplify l, simplify r) of
            (Val 0, rr)    -> rr
            (ll, Val 0)    -> ll
            (Val x, Val y) -> Val (x+y)
            (ll, rr)       -> Add ll rr
    simplify (Mul l r) =
        case (simplify l, simplify r) of
            (Val 0, rr)    -> Val 0
            (ll, Val 0)    -> Val 0
            (Val 1, rr)    -> rr
            (ll, Val 1)    -> ll
            (Val x, Val y) -> Val (x*y)
            (ll, rr)       -> Mul ll rr
    simplify t@(Var _) = t
    simplify t@(Val _) = t

Symbolic Manipulation of AST

Derivative (probably should change ValType to Double to be practical)

     deriv :: Expr -> Name -> Expr
     deriv (Add l r) v = Add (deriv l v) (deriv r v)
     deriv (Mul l r) v = Add (Mul l (deriv r v)) (Mul r (deriv l v))
     deriv (Var n)   v
           | v == n    = Val 1
     deriv _         _ = Val 0
     -- other constructors left as exercise

Key Ideas

Interpreter for simple ELI Calculator language
- concrete syntax — both infix and prefix (Ch. 41)
- abstract syntax tree
- value representation separate
- environment representation separate
- semantics and evaluation
- simplification (code improvement)

Source Code

Abstract Synax module AbSynCalc
Values module Values
Environments module Environments
Evaluator module EvalCalc
Process AST module ProcessAST

Exploring Languages with Interpreters and Functional Programming Chapter 42 Calculator Abstract Syntax & Eval