Environments

Past three weeks

How to use essential language constructs?

  • Data Types
  • Recursion
  • Higher-Order Functions

Next two weeks

How to implement language constructs?

  • Local variables and scope
  • Environments and Closures
  • Type Inference

Interpreter

How do we represent and evaluate a program?










Roadmap: The Nano Language

Features of Nano:

  1. Arithmetic
  2. Variables
  3. Let-bindings
  4. Functions
  5. Recursion










1. Nano: Arithmetic

A “grammar” of arithmetic expressions:


Expressions Values
4 ==> 4
4 + 12 ==> 16
(4+12) - 5 ==> 11



Representing Arithmetic Expressions and Values

Lets represent arithmetic expressions as type

Lets represent arithmetic values as a type





Evaluating Arithmetic Expressions

We can now write a Haskell function to evaluate an expression:









Alternative representation

Lets pull the operators into a separate type









QUIZ

Evaluator for alternative representation

What is a suitable type for evalOp?










The Nano Language

Features of Nano:

  1. Arithmetic [done]
  2. Variables
  3. Let-bindings
  4. Functions
  5. Recursion










2. Nano: Variables

Let’s add variables and let bindings!

Lets extend our datatype


QUIZ

What should the following expression evaluate to?

(A) 0

(B) 1

(C) Error










Environment

An expression is evaluated in an environment

  • A phone book which maps variables to values

A type for environments






Evaluation in an Environment

We write

to mean

When expr is evaluated in environment env the result is value**

That is, when we have variables, we modify our evaluator to take an input environment env in which expr must be evaluated.

First, lets update the evaluator for the arithmetic cases ENum and EBin






QUIZ

What is a suitable ?value such that

(A) 0

(B) 1

(C) Error










QUIZ

What is a suitable env such that

(A) []

(B) [x := 0, y := 9]

(C) [x := 9, y := 0]

(D) [x := 9, y := 10, z := 666]

(E) [y := 10, z := 666, x := 9]










Evaluating Variables

Using the above intuition, lets update our evaluator to handle variables i.e. the EVar case:



Lets confirm that our eval is ok!

The Nano Language

Features of Nano:

  1. Arithmetic expressions [done]
  2. Variables [done]
  3. Let-bindings
  4. Functions
  5. Recursion










2. Nano: Variables

Let’s add variables and let bindings!

Lets extend our datatype

How should we extend eval ?


QUIZ

What should the following expression evaluate to?

(A) Error

(B) 1

(C) 0










QUIZ

What should the following expression evaluate to?

(A) Error

(B) 0

(C) 1

(D) 100

(E) 101










QUIZ

What should the following expression evaluate to?

(A) Error

(B) 0

(C) 1

(D) 100

(E) 101










QUIZ

What should the following expression evaluate to?

(A) Error

(B) 1

(C) 101

(D) 102

(E) 2










Principle: Static/Lexical Scoping

Every variable use gets its value from a unique definition:

  • “Nearest” let-binder in program text

“Static” means you can tell without running the program

Great for readability and debugging

  1. Define local variables
  2. Be sure where each variable got its value

Don’t have to scratch head to figure where a variable got “assigned”

How to implement static scoping?







QUIZ

Lets re-evaluate the quizzes!

(A) env

(B) [ ]

(C) [ ("x" := 0) ]

(D) ("x" := 0) : env

(E) env ++ ["x" := 0]






QUIZ

(A) ("x" := 0) : env

(B) ("y" := 100) : env

(C) ("y" := 100) : ("x" := 0) : env

(D) ("x" := 0) : ("y" := 100) : env

(E) [("y" := 100), ("x" := 0)]






QUIZ

Lets re-evaluate the quizzes!

(A) ("x" := 0) : env

(B) ("x" := 100) : env

(C) ("x" := 100) : ("x" := 0) : env

(D) ("x" := 0) : ("x" := 100) : env

(E) [("x" := 100)]






Extending Environments

Lets fill in eval for the let x = e1 in e2 case!

  1. Evaluate e1 in env to get a value v1
  2. Extend environment with value for x i.e. to (x := v1) : env
  3. Evaluate e2 using extended environment.










Lets make sure our tests pass!

Run-time Errors

Haskell function to evaluate an expression:

QUIZ

Will eval env expr always return a value ? Or, can it crash?

(A) operation at A may fail

(B) operation at B may fail

(C) operation at C may fail

(D) operation at D may fail

(E) nah, its all good…, always returns a Value











Free vs bound variables

Undefined Variables

How do we make sure lookup doesn’t cause a run-time error?

Bound Variables

Consider an expression let x = e1 in e2

  • An occurrence of x is bound in e2

  • i.e. when occurrence of form let x = ... in ... x ...

  • i.e. when x occurs “under” a let binding for x.

Free Variables

An occurrence of x is free in e if it is not bound in e

Closed Expressions

An expression e is closed in environment env:

  • If all free variables of e are defined in env

Successful Evaluation

lookup will never fail

  • If eval env e is only called on e that is closed in env










QUIZ

Which variables occur free in the expression?

(A) None

(B) x

(C) y

(D) x and y











Exercise

Consider the function

What should isOk check for? (Try to implement it for nano…)

The Nano Language

Features of Nano:

  1. Arithmetic expressions [done]
  2. Variables [done]
  3. Let-bindings [done]
  4. Functions
  5. Recursion









Nano: Functions

Let’s add

  • lambda abstraction (aka function definitions)

  • application (aka function calls)

Example





Representation





Representation

Example

is represented as

Functions are Values

Recall the trinity

But… what is the value of a function?

Lets build some intuition with examples.











QUIZ

What does the following expression evaluate to?

(A) Error/Undefined

(B) 10

(C) 11

(D) 0

(E) 1











What is the Value of incr?

  • Is it an Int ?

  • Is it a Bool ?

  • Is it a ???

What information do we need to store (in the Env) about incr?











A Function’s Value is its Code

What information do we store about <code> ?







A Call’s Value

How to evaluate the “call” incr 10 ?

  1. Lookup the <code> i.e. <param, body> for incr (stored in the environment),

  2. Evaluate body with param set to 10!





Two kinds of Values

We now have two kinds of Values

  1. Plain Int (as before)
  2. A function’s “code”: a pair of “parameter” and “body-expression”

Evaluating Lambdas and Applications

Lets make sure our tests work properly!

QUIZ

What should the following evaluate to?

(A) Error/Undefined

(B) 10

(C) 11

(D) 0

(E) 1









QUIZ

And what should this expression evaluate to?

(A) Error/Undefined

(B) 110

(C) 11









The “Immutability Principle”

A function’s behavior should never change

  • A function must always return the same output for a given input

Why?

Oh no! How to find the bug? Is it

  • In myFunc or
  • In a global variable or
  • In a library somewhere else or

My worst debugging nightmare

Colbert “Immutability Principle”

The Immutability Principle ?

How does our eval work?

Oops?

And so we get

Ouch.

Enforcing Immutability with Closures

How to enforce immutability principle

  • inc 10 always returns 11?


Key Idea: Closures

At definition: Freeze the environment the function’s value

At call: Use the frozen environment to evaluate the body

Ensures that inc 10 always evaluates to the same result!

Now we evaluate

tada!

Representing Closures

Lets change the Value datatype to also store an Env

Evaluating Function Definitions

How should we fix the definition of eval for ELam?

Hint: What value should we bind incr to in our example above?


(Recall At definition freeze the environment the function’s value)


Evaluating Function Calls

How should we fix the definition of eval for EApp?


(Recall At call: Use the frozen environment to evaluate the body)


Hint: What value should we evaluate incr 10 to?

  1. Evaluate incr to get <frozenv, "x", x + c>
  2. Evaluate 10 to get 10
  3. Evaluate x + c in x:=10 : frozenv


Let’s generalize that recipe!

  1. Evaluate e1 to get <frozenv, param, body>
  2. Evaluate e2 to get v2
  3. Evaluate body in param := v2 : frozenv

Immutability Achieved

Lets put our code to the test!

QUIZ

What should the following evaluate to?

TODO

Functions Returning Functions Achieved!

TODO

QUIZ

What should the following evaluate to?

TODO

Functions Accepting Functions Achieved!

TODO

The Nano Language

Features of Nano:

  1. Arithmetic expressions [done]
  2. Variables [done]
  3. Let-bindings [done]
  4. Functions [done]
  5. Recursion

… You figure it out Hw4 … :-)