Environments

Recap: Our Evaluator

data Expr  = Var     VarName            -- variable
           | Exactly Value              -- a value (doesn't need evaluation)
           | Apply   Expr Expr          -- application
           | Let     VarName Expr Expr  -- let expression
           | BinOp   Expr Op Expr       -- built-in operator
           | If      Expr Expr Expr     -- conditional
    deriving (Show, Eq, Ord)
    
data Value = Lambda  VarName Expr       -- function value (closed function)
           | Number  Integer            -- numeric value
           | Str     String             -- string value
           | Boolean Bool               -- boolean value
    deriving (Show, Eq, Ord)

data Op = Plus | Minus | Times | Divide 
        | Equals | NotEquals | LessThan | GreaterThan
        | Concat
    deriving (Show, Eq, Ord)

eval :: Expr -> Value
eval (Var v)          = error ("Unsubstituted variable: " ++ v)
eval (Exactly val)    = val
eval (Apply eFn eArg) = 
      let vFn  = eval eFn
          vArg = eval eArg
      in case vFn of
             Lambda v eBody ->  eval (substC eBody v vArg)
             _              ->  error "Can't apply a non-function"
eval (Let v eDef eBody)   = eval (Apply (Exactly (Lambda v eBody)) eDef)
eval (BinOp eLHS op eRHS) = evalOp (eval eLHS) op (eval eRHS)
eval (If eCond eT eF)     = if toBool (eval eCond) then eval eT else eval eF

(Note: Previously we called our evaluator cbv, now we'll just call it eval.)

Helper functions

-- freeVars: the set of free variables in an expression

freeVars ::  Expr -> Set VarName
freeVars (Var v)                = Set.singleton v
freeVars (Apply e1 e2)          = freeVars e1 `union` freeVars e2
freeVars (BinOp e1 op e2)       = freeVars e1 `union` freeVars e2
freeVars (If e1 e2 e3)          = freeVars e1 `union` freeVars e2
freeVars (Exactly (Lambda x e)) = freeVars e \\ Set.singleton x
freeVars (Exactly _)            = Set.empty

-- substC: the expression that results from the substitution e1 [x -> e2]
-- (e2 must be a closed expression)

substC :: Expr -> VarName -> Expr -> Expr
substC e1 x e2 | Set.null fv = doSubst e1
               | otherwise   = error ("Bad substitution:" ++ show fv)
  where
    fv = freeVars e2
    doSubst (Var y)
        | x == y                    =  e2
        | otherwise                 =  Var y
    doSubst (Exactly (Lambda y eBody))
        | x == y                    =  Exactly (Lambda y eBody)
        | otherwise                 =  Exactly (Lambda y (doSubst eBody))
    doSubst (Apply eFn eArg)        =  Apply (doSubst eFn) (doSubst eArg)
    doSubst (BinOp eLhs op eRhs)    =  BinOp (doSubst eLhs) op (doSubst eRhs)
    doSubst (Let y eDef eBody)
        | x == y                    =  Let y eDef' eBody
        | otherwise                 =  Let y eDef' (doSubst eBody)
      where 
        eDef' = doSubst eDef
    doSubst (If eCond eT eF)        =  If (doSubst eCond) (doSubst eT) (doSubst eF)
    doSubst other                   =  other


-- Evaluation for built-in operators

evalOp :: Value -> Op -> Value -> Value
-- error out for operands of different types (neat use of a complex guard!)
evalOp lhs op rhs | misMatchedTypes =
    error ("Mismatched types to " ++ show op ++ " operator")
  where misMatchedTypes = case (lhs, rhs) of
                              (Boolean _,  Boolean _)   -> False
                              (Number  _,  Number  _)   -> False
                              (Str     _,  Str     _)   -> False
                              (Lambda _ _, Lambda _ _)  -> False
                              _                         -> True
-- evaluation for function operations & operands (none)
evalOp (Lambda _ _) op (Lambda _ _) = 
    error ("No implementation of " ++ show op ++ " for functions")
-- evaluation of comparison operators for everything (except functions)
evalOp lhs Equals      rhs = Boolean (lhs == rhs)                -- a = b
evalOp lhs NotEquals   rhs = Boolean (lhs /= rhs)                -- a ≠ b
evalOp lhs LessThan    rhs = Boolean (lhs < rhs)                 -- a < b
evalOp lhs GreaterThan rhs = Boolean (lhs > rhs)                 -- a > b
-- evaluation for boolean operations & operands (nothing beyond comparison ops)
evalOp (Boolean _) op (Boolean _) = 
    error ("No implementation of " ++ show op ++ " for booleans")
-- evaluation for numeric operations & operands (beyond comparison ops)
evalOp (Number lhs) Plus   (Number rhs) = Number (lhs + rhs)     -- a + b
evalOp (Number lhs) Minus  (Number rhs) = Number (lhs - rhs)     -- a - b
evalOp (Number lhs) Times  (Number rhs) = Number (lhs * rhs)     -- a * b
evalOp (Number lhs) Divide (Number rhs) = Number (lhs `div` rhs) -- a / b
evalOp (Number _)   op     (Number _) =
    error ("No implementation of " ++ show op ++ " for numbers")
-- evaluation for string operations & operands (beyond comparison ops)
evalOp (Str lhs) Concat (Str rhs) = Str (lhs ++ rhs)             -- a · b
evalOp (Str lhs) op     (Str rhs) =
    error ("No implementation of " ++ show op ++ " for strings")

-- Convert a value to a Haskell Bool

toBool (Boolean b)  = b
toBool (Number  n)  = n /= 0
toBool (Str     s)  = s /= ""
toBool (Lambda _ _) = error "Can't use a function as a Boolean" 

Performance Issue (Trouble in Paradise part 1)

Consider

let x1 = 1
in let x2 = 2
   in let x3 = 3 in
       ...
         in let xn = n
            in x1+x2+x3+ ... +xn 

which is just syntactic sugar for

(\a.(\b.(\c.(\d.(\e.(\f.a+b+c+d+e+f) 6) 5) 4) 3) 2) 1

or, consider the six-argument curried function,

(\a.\b.\c.\d.\e.\f.a+b+c+d+e+f) 1 2 3 4 5 6

This current functionality has bad algorithmic runtime of O(n²) (since substituting a variable into an expression takes time linear in the size of the expression and we do this operations for the n arguments), and has a nasty constant factor based on the size of the function body. Thus this expression

(\a.\b.\c.\d.\e.\f.a+b+c+d+e+f+a+b+c+d+e+f+a+b+c+d+e+f) 1 2 3 4 5 6

takes longer to substitute than this one (which also has poor time complexity, O(n²), but is not quite as bad)

(\a.\b.\c.\d.\e.\f."Oink!") 1 2 3 4 5 6

The solution is to avoid substitution, which means we need an alternative. (We could use S-K combinators to eliminate variables entirely, but we'll find a solution that keeps variables)

K (K (K (K (K (K "Oink!")))))

S (K (S (K (S (K (S (K (S (K (+)))))))))) (S (K (S (K (S (K (S (K (+)))))))) (S (K (S (K (S (K (+)))))) (S (K (S (K (+)))) (+))))

B (Bstar (Bstar (Bstar (B (+)) (+)) (+)) (+)) (+)

S (S (K S) (S (K (S (K S))) (S (K (S (K (S (K S))))) (S (K (S (K (S (K (S (K S))))))) (S (K (S (K (S (K (S (K (S (K S))))))))) (S (K (S (K (S (K (S (K (S (K (S (K (+)))))))))))) (S (S (K S) (S (K (S (K S))) (S (K (S (K (S (K S))))) (S (K (S (K (S (K (S (K S))))))) (S (K (S (K (S (K (S (K (S (K S))))))))) (S (K (S (K (S (K (S (K (S (K (S (K (+)))))))))))) (S (S (K S) (S (K (S (K S))) (S (K (S (K (S (K S))))) (S (K (S (K (S (K (S (K S))))))) (S (K (S (K (S (K (S (K (S (K S))))))))) (S (K (S (K (S (K (S (K (S (K (S (K (+)))))))))))) (S (S (K S) (S (K (S (K S))) (S (K (S (K (S (K S))))) (S (K (S (K (S (K (S (K S))))))) (S (K (S (K (S (K (S (K (S (K S))))))))) (S (K (S (K (S (K (S (K (S (K (S (K (+)))))))))))) (S (S (K S) (S (K (S (K S))) (S (K (S (K (S (K S))))) (S (K (S (K (S (K (S (K S))))))) (S (K (S (K (S (K (S (K (S (K S))))))))) (S (K (S (K (S (K (S (K (S (K (S (K (+)))))))))))) (S (S (K S) (S (K (S (K S))) (S (K (S (K (S (K S))))) (S (K (S (K (S (K (S (K S))))))) (S (K (S (K (S (K (S (K (S (K S))))))))) (S (K (S (K (S (K (S (K (S (K (S (K (+)))))))))))) (S (S (K S) (S (K (S (K S))) (S (K (S (K (S (K S))))) (S (K (S (K (S (K (S (K S))))))) (S (K (S (K (S (K (S (K (S (K S))))))))) (S (K (S (K (S (K (S (K (S (K (S (K (+)))))))))))) (S (S (K S) (S (K (S (K S))) (S (K (S (K (S (K S))))) (S (K (S (K (S (K (S (K S))))))) (S (K (S (K (S (K (S (K (S (K S))))))))) (S (K (S (K (S (K (S (K (S (K (S (K (+)))))))))))) (S (S (K S) (S (K (S (K S))) (S (K (S (K (S (K S))))) (S (K (S (K (S (K (S (K S))))))) (S (K (S (K (S (K (S (K (S (K S))))))))) (S (K (S (K (S (K (S (K (S (K (S (K (+)))))))))))) (S (S (K S) (S (K (S (K S))) (S (K (S (K (S (K S))))) (S (K (S (K (S (K (S (K S))))))) (S (K (S (K (S (K (S (K (S (K S))))))))) (S (K (S (K (S (K (S (K (S (K (S (K (+)))))))))))) (S (S (K S) (S (K (S (K S))) (S (K (S (K (S (K S))))) (S (K (S (K (S (K (S (K S))))))) (S (K (S (K (S (K (S (K (S (K S))))))))) (S (K (S (K (S (K (S (K (S (K (S (K (+)))))))))))) (S (S (K S) (S (K (S (K S))) (S (K (S (K (S (K S))))) (S (K (S (K (S (K (S (K S))))))) (S (K (S (K (S (K (S (K (S (K S))))))))) (S (K (S (K (S (K (S (K (S (K (S (K (+)))))))))))) (S (K (S (K (S (K (S (K (S (K (+)))))))))) (S (K (S (K (S (K (S (K (+)))))))) (S (K (S (K (S (K (+)))))) (S (K (S (K (+)))) (+))))))))))) (S (K K) (S (K K) (S (K K) (S (K K) K))))))))))) (K (S (K K) (S (K K) (S (K K) K))))))))))) (K (K (S (K K) (S (K K) K))))))))))) (K (K (K (S (K K) K))))))))))) (K (K (K (K K))))))))))) (K (K (K (K (K I)))))))))))) (S (K K) (S (K K) (S (K K) (S (K K) K))))))))))) (K (S (K K) (S (K K) (S (K K) K))))))))))) (K (K (S (K K) (S (K K) K))))))))))) (K (K (K (S (K K) K))))))))))) (K (K (K (K K))))))))))) (K (K (K (K (K I)))))

S (K (S (K (S (K (S (K (S (K (S (K (S (+) (S (+) I))))))))))))) (S (K (S (K (S (K (S (K (S (K (+)))))))))) (S (K (S (K (S (K (S (K (+)))))))) (S (K (S (K (S (K (+)))))) (S (K (S (K (+)))) (+)))))

Prelude> f = s (k (s (k (s (k (s (k (s (k (s (k (s (+) (s (+) i))))))))))))) (s (k (s (k (s (k (s (k (s (k (+)))))))))) (s (k (s (k (s (k (s (k (+)))))))) (s (k (s (k (s (k (+)))))) (s (k (s (k (+)))) (+)))))
Prelude> :t f
f :: Num t3 => t3 -> t3 -> t3 -> t3 -> t3 -> t3 -> t3
Prelude> f 1 2 3 4 5 6 
63
Prelude> (1+2+3+4+5+6)*3
63

B (Bstar (Bstar (Bstar (Bstar (B (S (+) (S (+) I))) (+)) (+)) (+)) (+)) (+)

Solution: Environments

In order to fix this, we add an extra level of indirection by storing the variable bindings. Now, we can look up a variables value when we evaluate it, rather than having to substitute it ahead of time.

Map takes in a key and a value. When it finds a new assignment, then it gets added to the table.

    type Env = Map VarName Value

Note: In Haskell, the Map type provides us with the following useful operations

    Map.empty  :: Map k a
    Map.insert :: Ord k => k -> a -> Map k a -> Map k a
    Map.lookup :: Ord k => k -> Map k a -> Maybe a

Map.lookup gives a Maybe type, which Haskell defines as

    data Maybe a = Nothing
                 | Just a

Remark: In most languages, insert and lookup in a dictionary/map takes O(1) time because they use a hash table (which gets modified as we make changes). However, in Haskell, the Map type is tree-based so insert and lookup actually take O(log n) (and it returns a new tree leaving the old one unchanged; you can keep it or throw it away— if you keep the old one, it costs O(log n) space.), so in the previous example, we would still only get O(n log n), not O(n). Nonetheless, this is still a substantial improvement over O(n²).

Our Evaluator (After)

To incorporate the environment into our eval function, we can just as an argument (and therefore pass it to all recursive calls), and then use the environment to look up the value of a variable when we eval a Var and add the value of a variable to the environment pass to the recursive eval call when we evaluate a Lambda.

eval :: Env -> Expr -> Value
eval env (Exactly val)    = val
eval env (Var v)          = case Map.lookup v env of
                                Just val -> val
                                Nothing  -> error ("Unbound var " ++ v)
eval env (Apply eFn eArg) = 
      let vFn  = eval env eFn
          vArg = eval env eArg
      in case vFn of
             Lambda v eBody ->  eval (Map.insert v vArg env) eBody
             _              ->  error ("Can't apply a non-function "
                                       ++ showValue vFn)
eval env (BinOp eLHS op eRHS) = evalOp (eval env eLHS) op (eval env eRHS)
eval env (If eCond eT eF)     = if toBool (eval env eCond)
                                then eval env eT
                                else eval env eF
eval env (Let v eDef eBody)   = eval env  (Apply (Exactly (Lambda v eBody)) eDef)

Sample Session

Looks good! Running envInterpreter ...

env> λx.x
λx.x
env> 1
1
env> 1+2
3
env> (λx.x + 7) 3
10
env> let y = λf.(λx.f (λv.((x x) v))) (λx.f (λv.((x x) v))) in let fact = y (λfact.λn.if n == 0 then 1 else n * fact (n - 1)) in fact 6 + fact 3 + fact 1
727
env>
env> let a = 1 in let b = 2 in let c = 3 in let d = 4 in a+b+c+d
10
env> (λa.(λb.(λc.(λd.a+b+c+d) 4) 3) 2) 1
10

Are We Happy? (Trouble in Paradise part 2)

env> let a = 40 in let b = 2 in a + b
42
env> (λa.(λb.a + b) 2) 40
42
env> (λa.λb.a + b) 40 2
!! caught exception: Unbound var a
env> (λa.λb.a + b) 40
λb.a + b

In contrast, in the substitution-based interpreter, we saw

cbv> (λa.λb.a + b) 40
λb.40 + b

Our environments-based interpreter returned a function that has free variables (a.k.a. an open expression) but our substitution-based interpreter returned a function with no free variables (a.k.a. a closed expression).

As a reminder, here's what (λa.λb.a + b) 40 is represented as

Apply (Exactly (Lambda "a" (Exactly (Lambda "b" (BinOp (Var "a") Plus (Var "b")))))) (Exactly (Number 40))

More Problems

Also, consider how this works in a substitution-based interpreter:

cbv> let x = 10 in let f = λy.x + y in f 7
17
cbv> let x = 10 in let f = λy.x + y in let x = 20 in f 7
17
cbv> let x = 10 in let f = λy.x + y in let z = 20 in f 7
17

But in our environments-based interpreter (so far):

env> let x = 10 in let f = λy.x + y in f 7
17
env> let x = 10 in let f = λy.x + y in let x = 20 in f 7
27
env> let x = 10 in let f = λy.x + y in let z = 20 in f 7
17

Here we can see that usually x refers to the x that existed at the point where f was defined, but in the middle example for our environments-based interpreter, we used the value from the more-recently-defined x.

*NewEval1> readExpr "let x = 10 in let f = λy.x+y in let x = 20 in f 7"
Let "x" (Exactly (Number 10)) (Let "f" (Exactly (Lambda "y" (BinOp (Var "x") Plus (Var "y")))) (Let "x" (Exactly (Number 20)) (Apply (Var "f") (Exactly (Number 7)))))

env> (λx.(λf.f 7) (λy.x + y)) 10
17
env> (λx.(λf.(λx.f 7) 20) (λy.x + y)) 10
27
env> (λx.(λf.(λz.f 7) 20) (λy.x + y)) 10
17

*NewEval1> readExpr "let x = 10 in let f = λy.x+y in let x = 20 in f 7"
Apply (Exactly (Lambda "x" (Apply (Exactly (Lambda "f" (Apply (Exactly (Lambda "x" (Apply (Var "f") (Exactly (Number 7))))) (Exactly (Number 20))))) (Exactly (Lambda "y" (BinOp (Var "x") Plus (Var "y"))))))) (Exactly (Number 10))

Terminology

Static Scope (a.k.a. Lexical Scope):

• This is the name for what happens in the substitution-based interpreter we saw above. It's what you're used to and expect.
• At compile-time there is a way of matching uses of variables with declarations of variables.

Dynamic Scope:

• This the name for what happens in the broken environments-based interpreter.
• The matching-up depends on how the program runs.
• The value of a variable is determined by what is in the environment at the time it is evaluated.
• More difficult for programmers to reason about
  • Cannot just look at the program and reason about the assignments.

Note: This doesn't say how the matching takes place!

Wiki Extra: Variable Scoping in Languages

Static Scoping

• Fortran, Pascal, C, C++, Java, SML, Scheme, ...

Dynamic Scoping

• APL, Snobol, (Original) LISP, Emacs LISP, Perl 4, ...

Both

• Perl 5, Common LISP

Wiki Extra: An Argument for Dynamic Scope

Customization of subroutines (implicit arguments)

    (defvar base 10)
    (defun print_int (n)
        (... print the number n in base base ...))
    (defun foo (y)  
        (... do computation then call print_int ...))
    (let ((base 8))
        (print_int 42))
    (print_int 100)
    (let ((base 2))
       (foo 7))
    (print_int 72)

Wiki Bonus: Why elisp is dynamically scoped

“Dynamic binding is especially useful for elements of the command dispatch table. For example, the RMAIL command for composing a reply to a message temporarily defines the character Control–Meta–Y to insert the text of the original message into the reply. The function which implements this command is always defined, but Control–Meta–Y does not call that function except while a reply is being edited. The reply command does this by dynamically binding the dispatch table entry for Control–Meta–Y and then calling the editor as a subroutine. When the recursive invocation of the editor returns, the text as edited by the user is sent as a reply”

Richard Stallman
EMACS: The Extensible, Customizable Display Editor

Solving the Problem

env> (λx.λy.x) 17
λy.x

• To solve the problem, we add closures. They keep track of what the bound variables are.
  • One way of phrasing the problem is that in the Exactly case where we had just a Lambda, we were "forgetting" the environment when we returned (even though it might be relevant inside the Lambda). Thus the solution is to simply "remember" the environment we built up, i.e., add a closure to the Lambda.
    • In more detail, the Exactly case refers to the situation where the eval function is passed an Expr whose value is of type Exactly and with a value of Lambda (which has its own values associated with it). This is the situation in which we are using eval on a lambda expression.

Revised Code

data Expr = Var     VarName           -- variable
          | Apply   Expr Expr         -- application
          | BinOp   Expr Op Expr      -- built-in operator
          | If      Expr Expr Expr    -- if statement
          | Let     VarName Expr Expr -- let statement
          | Lambda  VarName Expr      -- lambda expression
          | Exactly Value             -- a value (doesn't need evaluation)
    deriving (Show, Eq, Ord)
    
data Value = Closure Env VarName Expr
           | Number  Integer
           | Str     String 
           | Boolean Bool
    deriving (Show, Eq, Ord)

eval env (Lambda v eBody) = Closure env v eBody
eval env (Apply eFn eArg) = 
      case vFn of
         Closure cEnv v eBody ->  eval (Map.insert v vArg cEnv) eBody
         _  ->  error ("Can't apply a non-function " ++ showValue vFn)
    where
        vFn  = eval env eFn
        vArg = eval env eArg
... everything else stays the same ...

env> (λx.λy.x) 10
<<CLOSURE[x = 10]: λy.x >>
env> let x = 10 in let f = λy.x+y in let x = 20 in f 7
17
env> let x = 10 in let f = λy.x+y in let x = 20 in f
<<CLOSURE[x = 10]: λy.x + y >>

Wasted Space (?)

env> let nellie = "A huge elephant" in (λx.λy.x) 10
<<CLOSURE[nellie = "A huge elephant",x = 10]: λy.x >>

restrict :: Env -> Set VarName -> Env

eval env expr@(Lambda v eBody) = Closure (restrict env (freeVars expr)) v eBody
eval env (Apply eFn eArg) = 
      case vFn of
         Closure cEnv v eBody ->  eval (Map.insert v vArg cEnv) eBody
         _  ->  error ("Can't apply a non-function " ++ showValue vFn)
    where
        vFn  = eval env eFn
        vArg = eval env eArg
... everything else stays the same ...

env> let nellie = "A huge elephant" in (λx.λy.x) 10
<<CLOSURE[x = 10]: λy.x >>

*EnvEval4> readExpr "λx.x+y"
Lambda (fromList ["y"]) "x" (BinOp (Var "x") Plus (Var "y"))

In order to avoid having to scan all of the code to evaluate the free variables of each expression, we can pre-compute them once and store the values with the code.

Note: this method saves space, but using "restrict" is time-consuming. So this is actually a trade-off between space and time.

Wiki Extra: Lambdas and Closures in C++11

C++11 adds lambda functions to C++. Interestingly, you can specify what to put in the closure, and whether to capture by value or by reference.

#include <iostream>

int main()
{
    auto f =
        [](int a) {
                return [a](int b){
                        return [a,b](int c) {
                                return [a,b,c](int d) {
                                        return a+b+c+d;
                                };
                        };
                };
        };

    std::cout << f(1)(2)(3)(4) << std::endl;

    return 0;
}

Helpful Link: http://www.cprogramming.com/c++11/c++11-lambda-closures.html

-- MelissaONeill - 21 Feb 2020