Environments & Closures

Intro

Slides

Quizzes

cse116-vars-ind -> E

cse116-free-ind -> B

cse116-cscope-ind -> B

cse116-env-ind -> A

cse116-enveval-ind -> D

cse116-enveval2-ind -> C

The Nano Language

Features of Nano:

1. Arithmetic expressions

Evaluator 1

e ::= n
    | e1 + e2
    | e1 - e2
    | e1 * e2

-- haskell representation:
data Binop = Add | Sub | Mul
data Expr = Num Int
            | Bin Binop Expr Expr

-- evaluator:
eval :: Expr -> Int
eval (Num n)         = n
eval (Bin Add e1 e2) = eval e1 + eval e2
eval (Bin Sub e1 e2) = eval e1 - eval e2
eval (Bin Mul e1 e2) = eval e1 * eval e2

2. Variables and let-bindings

e ::= n | x
    | e1 + e2 | e1 - e2 | e1 * e2
    | let x = e1 in e2

-- haskell representation:
type Id = String

data Expr = Num Int                -- number
            | Var Id               -- variable
            | Bin Binop Expr Expr  -- binary op
            | Let Id Expr Expr     -- let expr

thus, expressions must be evaluated in Environments

Evaluator 2

Previous implementation: Evaluator 1

type Value = Int
data Env = ...

-- add new id/value to env
add :: Id -> Value -> Env -> Env

-- lookup id in env
lookup :: Id -> Env -> Value

-- evaluator:
eval :: Env -> Expr -> Value
eval env (Num n)           = n
eval env (Var x)           = lookup x env
eval env (Bin op e1 e2)    = f v1 v2
    where
        v1 = eval env e1
        v2 = eval env e2
        f  = case op of
            Add -> (+)
            Sub -> (-)
            Mul -> (*)
eval env (Let x e1 e2)     = eval env' e2
    where
        v    = eval env e1
        env' = add x v env

Runtime Errors

Lookups can fail when a var is not bound!

How do we ensure that it doesn’t raise a runtime error?

In eval env e, env must contain bindings for all free vars of e. Evaluation only succeeds when all expressions are closed.

3. Functions

Let’s add lambda abstractions and function application!

e ::= n | x
    | e1 + e2 | e1 - e2 | e1 * e2
    | let x = e1 in e2
    | \x -> e  -- abstraction
    | e1 e2    -- application

-- haskell representation:
data Expr = Num Int                -- number
            | Var Id               -- variable
            | Bin Binop Expr Expr  -- binary op
            | Let Id Expr Expr     -- let expr
            | Lam Id Expr          -- abstraction
            | App Expr Expr        -- application

Note

Now, let’s try to evaluate something…

eval [] {let c = 42 in let cTimes = \x -> c * x in cTimes 2}
=> eval [c:42] {let cTimes = \x -> c * x in cTimes 2}
=> eval [cTimes:???, c:42] {cTimes 2}

How do we represent lambdas as a value? Let’s try data Value = VNum Int | VLam Id Expr and evaluate…

eval [] {let c = 42 in let cTimes = \x -> c * x in cTimes 2}
=> eval [c:42] {let cTimes = \x -> c * x in cTimes 2}
=> eval [cTimes:(\x -> c * x), c:42] {cTimes 2}
=> eval [cTimes:(\x -> c * x), c:42] {(\x -> c * x) 2}
=> eval [x:2, cTimes:(\x -> c * x), c:42] {x * c}
=> 42 * 2
=> 84

But what if c is redefined before cTimes is used?

The problem that this brings up is static v. dynamic scoping; static scoping = most recent binding in text, whereas dynamic = most recent binding in execution

How do we implement lexical scoping? See Closures

Now let’s update our evaluator! Previous implementation: Evaluator 2

Evaluator 3

data Value = VNum Int    -- new!
    | VClos Env Id Expr  -- env + formal + body

eval :: Env -> Expr -> Value
eval env (Num n)           = VNum n  -- we must wrap in VNum now!
eval env (Var x)           = lookup x env
eval env (Bin op e1 e2)    = VNum (f v1 v2)
    where
        (VNum v1) = eval env e1
        (VNum v2) = eval env e2
        f  = case op of
            Add -> (+)
            Sub -> (-)
            Mul -> (*)
eval env (Let x e1 e2)     = eval env' e2
    where
        v    = eval env e1
        env' = add x v env
-- new!
eval env (Lam x body)      = VClos env x body
eval env (App fun arg)     = eval bodyEnv body
    where
        (VClos closEnv x body) = eval env fun  -- eval function to closure
        vArg                   = eval env arg  -- eval argument
        bodyEnv                = add x vArg closEnv

But note: this evaluator doesn’t cover recursion!

4. Recursion

We have to do this in homework, yay! See hw4.

Environments

an environment maps all free vars to values

x * y
=[x:17, y:2]=> 34

x * y
=[x:17]=> Error: unbound var y

x * (let y = 2 in y)
=[x:17]=> 34

To evaluate let x = e1 in e2 in env:

• evaluate e2 in an extended env env + [x:v]

• where v = eval e1

Closures

Closure = lambda abstraction (formal + body) + environment at function definition

a closure environment must save all free variables of a function defn!

data Value = VNum Int
    | VClos Env Id Expr  -- env + formal + body

-- our syntax:
-- binding:<env, lambda>

-- now, eval:
eval [] {let c = 42 in let cTimes = \x -> c * x in let c = 5 in cTimes 2}
    => eval [c:42] {let cTimes = \x -> c * x in let c = 5 in cTimes 2}
    => eval [cTimes:<[c:42], \x -> c * x>, c:42] {let c = 5 in cTimes 2}
    => eval [c:5, cTimes:<[c:42], \x -> c * x>, c:42] {cTimes 2}
    => eval [c:5, cTimes:<[c:42], \x -> c * x>, c:42] {<[c:42], \x -> c * x> 2}
    -- restore env to the one inside the closure, then bind 2 to x:
    => eval [x:2, c:42] {c * x}
    => 42 * 2
    => 84