Exploring Languages
with Interpreters
and Functional Programming

Chapter 42
Calculator Abstract Syntax & Eval

H. Conrad Cunningham

24 November 2018

Copyright (C) 2017, 2018, H. Conrad Cunningham

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

Concrete vs. Abstract Syntax

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

AST for 1 + 1

Abstract Syntax Tree (2)

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

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

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

Evaluation Module (1)

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

Source Code