Acknowledgements: These slides accompany Chapter 10 “Expression Language Syntax and Semantics” of the in-work textbook “Introduction to Functional Programming Using Haskell”.

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 2017 is a recent version of Firefox from Mozilla.

Lecture Goals

Examine language processing in context of interpreter for simple Expression Language
- concrete syntax – both infix and prefix
- abstract syntax
- values
- environment
- semantics and evaluation
- REPL
- simplification

Expression Language Modules

Expression Language (Ch. 10)

Abstract_Synax module AbSynExpr
Values module Values
Environments module Environments
Evaluator module EvalExpr

Expression Language (Ch. 11)

Lexical_analyzer module LexExpr common to both parsers
Prefix syntax
- Recursive descent Parser module ParsePrefixExpr
- Read-Exwcute-Print Loop (REPL) module PrefixExprREPL
Infix syntax
- Recursive descent Parser module ParseInfixExpr
- REPL module InfixExprREPL

Grammars

See discussion in “textbook” on Grammars
Familiar from CSci 311 Models of Computation
Only informal understanding required

Concrete vs. Abstract Syntax

Concrete syntax: express language details in text strings (source code)
Abstract syntax: express essential structure, ignore incidental representation issues (intermediate representation)

Concrete Infix Syntax

Examples – familiar syntax

    3 
    -3 
    x 
    1+1 
    x + 3
    (x + y)  * (2 - z)

Infix Grammar

    -- Context-free grammar
    <expression> ::= <term> { <addop> <term> }
    <term>       ::= <factor> { <mulop> <factor> }
    <factor>     ::= <var> | <val>
                   | '(' <expression> ')'
    <val>        ::= [ '-' ] <unsigned>
    <var>        ::= <id>
    <addop>      ::=  '+'  |  '-' 
    <mulop>      ::=  '*'  |  '/' 
    -- Regular grammar
    <id>         ::=  <firstid>  |  <firstid> <idseq>
    <idseq>      ::=  <restid>   |  <restid> <idseq>
    <firstid>    ::=  <alpha>    | '_'
    <restid>     ::=  <alpha>    | '_'  | <digit>
    <unsigned>   ::=  <digit>    |  <digit> <unsigned> 
    <digit>      ::=  any numeric character
    <alpha>      ::=  any alphabetic character

Infix Parse Tree `1 + 1`

Infix parse tree of `1+1`

Concrete Prefix Syntax

Examples – parenthesized syntax (Lisp-like)

    3 
    -3 
    x 
    (+ 1 1) 
    (+ x 3) 
    (* (+ x y) (- 2 z))

Prefix Grammar

    -- Context-free Grammar
    <expression> ::=  <var> | <val> | <operexpr>
    <var>        ::=  <id>
    <val>        ::=  [ "-" ] <unsigned> 
    <operexpr>   ::=  '(' <operator> <operandseq> ')'
    <operandseq> ::=  { <expression> }
    <operator>   ::=  '+'  |  '*'  |  '-'  |  '/' | ...
    -- Reglar grammar (same as infix grammar)
    <id>         ::=  <firstid>  |  <firstid> <idseq>
    <idseq>      ::=  <restid>   |  <restid> <idseq>
    <firstid>    ::=  <alpha>    | '_'
    <restid>     ::=  <alpha>    | '_'  | <digit>
    <unsigned>   ::=  <digit>    |  <digit> <unsigned> 
    <digit>      ::=  any numeric character
    <alpha>      ::=  any alphabetic character

Prefix Parse Tree `(+ 1 1)`

Prefix parse tree of `(+ 1 1)`

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:: mapping from variables’ names to their values

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

Expression 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 AbSynExpr    ( 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

Read-Evaluate-Print Loop (REPL)

Read expression from command line
Evaluate expression after parsing
Print resulting value
Loop back for next expression

Expression Language REPL

Uses Parser and Evaluator modules
Separate versions
- infix: InfixExprREPL
- prefix: PrefixExprREPL
REPL commands :set, :display, :quit

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

CSci 450/503: Programming Languages

Expression Language Syntax and Semantics

Lecture Goals

Expression Language Modules

Expression Language (Ch. 10)

Expression Language (Ch. 11)

Grammars

Concrete vs. Abstract Syntax

Concrete Infix Syntax

Infix Grammar

Infix Parse Tree `1 + 1`

Concrete Prefix Syntax

Prefix Grammar

Prefix Parse Tree `(+ 1 1)`

Abstract Syntax Data Type

Abstract Syntax Show Instance (1)

Abstract Syntax Show Instance (2)

Abstract Syntax Examples

Abstract Syntax Tree (1)

Abstract Syntax Tree (2)

Values Module

Environment

Environments Module (General)

Expression Language Environment

Informal Semantics of AST

Evaluation Module (1)

Evaluation Module (2)

Evaluation Module (3)

Read-Evaluate-Print Loop (REPL)

Expression Language REPL

Simplification (Optional Phase)

Symbolic Manipulation of AST

Key Ideas

CSci 450/503: Programming Languages Expression Language Syntax and Semantics

Lecture Goals

Expression Language Modules

Expression Language (Ch. 10)

Expression Language (Ch. 11)

Grammars

Concrete vs. Abstract Syntax

Concrete Infix Syntax

Infix Grammar

Infix Parse Tree 1 + 1

Concrete Prefix Syntax

Prefix Grammar

Prefix Parse Tree (+ 1 1)

Abstract Syntax Data Type

Abstract Syntax Show Instance (1)

Abstract Syntax Show Instance (2)

Abstract Syntax Examples

Abstract Syntax Tree (1)

Abstract Syntax Tree (2)

Values Module

Environment

Environments Module (General)

Expression Language Environment

Informal Semantics of AST

Evaluation Module (1)

Evaluation Module (2)

Evaluation Module (3)

Read-Evaluate-Print Loop (REPL)

Expression Language REPL

Simplification (Optional Phase)

Symbolic Manipulation of AST

Key Ideas

CSci 450/503: Programming Languages

Expression Language Syntax and Semantics

Infix Parse Tree `1 + 1`

Prefix Parse Tree `(+ 1 1)`