1

Programming Languages and Compilers (CS 421)

Talia Ringer (they/them)

4218 SC, UIUC

https://courses.grainger.illinois.edu/cs421/fa2023/

Based heavily on slides by Elsa Gunter, which were based in part on slides by Mattox Beckman, as updated by Vikram Adve and Gul Agha

• On Tuesday, we saw some great language features, like tuples, patterns, pattern matching, and partial function application.
• We also saw how currying gets us between a function that takes a tuple as an argument, and a function that takes its arguments one at a time.
• Finally, we saw how closures map from patterns.
• Today, we will briefly look at recursion coupled with pattern matching in OCaml.
• We will then finally get to evaluating expressions in OCaml!

Objectives for Today

2

• On Tuesday, we saw some great language features, like tuples, patterns, pattern matching, and partial function application.
• We also saw how currying gets us between a function that takes a tuple as an argument, and a function that takes its arguments one at a time.
• Finally, we saw how closures map from patterns.
• Today, we will briefly look at recursion coupled with pattern matching in OCaml.
• We will then finally get to evaluating expressions in OCaml!

Objectives for Today

3

4

​

​

​

Questions from last time?

5

​

​

​

Intro to Recursion in OCaml

Recursive Functions

# (* rec needed for recursive function declarations *)

let rec factorial n =

if n = 0 then

1

else

n * factorial (n - 1);;

val factorial : int -> int = <fun>

# factorial 5;;

- : int = 120

*

6

Recursion in OCaml

Recursive Functions

# (* rec needed for recursive function declarations *)

let rec factorial n =

if n = 0 then

1

else

n * factorial (n - 1);;

val factorial : int -> int = <fun>

# factorial 5;;

- : int = 120

*

7

Recursion in OCaml

Recursive Functions

# (* rec needed for recursive function declarations *)

let rec factorial n =

if n = 0 then

1

else

n * factorial (n - 1);;

val factorial : int -> int = <fun>

# factorial 5;;

- : int = 120

*

8

Recursion in OCaml

Recursive Functions

# (* rec needed for recursive function declarations *)

let rec factorial n =

if n = 0 then

1

else

n * factorial (n - 1);;

val factorial : int -> int = <fun>

# factorial 5;;

- : int = 120

*

9

Recursion in OCaml

Recursive Functions

# (* rec needed for recursive function declarations *)

let rec factorial n =

if n = 0 then

1

else

n * factorial (n - 1);;

val factorial : int -> int = <fun>

# factorial 5;;

- : int = 120

*

10

Recursion in OCaml

Without the rec keyword, we’d get “Error: Unbound value factorial.”

Pattern Matching and Recursion

Compute n² recursively using:

n² = (2 * n - 1) + (n - 1)²

​

# let rec sq n = (* rec for recursion *)

match n with (* pattern matching for cases *)

| 0 -> 0 (* base case *)

| n -> (2 * n -1) + sq (n -1);; (* recursive case *)

val sq : int -> int = <fun>

# sq 3;;

• : int = 9

​

​

11

Recursion in OCaml

Pattern Matching and Recursion

Compute n² recursively using:

n² = (2 * n - 1) + (n - 1)²

​

# let rec sq n = (* rec for recursion *)

match n with (* pattern matching for cases *)

| 0 -> 0 (* base case *)

| n -> (2 * n -1) + sq (n -1);; (* recursive case *)

val sq : int -> int = <fun>

# sq 3;;

• : int = 9

​

​

12

Recursion in OCaml

Pattern Matching and Recursion

Compute n² recursively using:

n² = (2 * n - 1) + (n - 1)²

​

# let rec sq n = (* rec for recursion *)

match n with (* pattern matching for cases *)

| 0 -> 0 (* base case *)

| n -> (2 * n -1) + sq (n -1);; (* recursive case *)

val sq : int -> int = <fun>

# sq 3;;

• : int = 9

​

​

13

Recursion in OCaml

Pattern Matching and Recursion

Compute n² recursively using:

n² = (2 * n - 1) + (n - 1)²

​

# let rec sq n = (* rec for recursion *)

match n with (* pattern matching for cases *)

| 0 -> 0 (* base case *)

| n -> (2 * n -1) + sq (n -1);; (* recursive case *)

val sq : int -> int = <fun>

# sq 3;;

• : int = 9

​

​

14

Recursion in OCaml

Pattern Matching and Recursion

Compute n² recursively using:

n² = (2 * n - 1) + (n - 1)²

​

# let rec sq n = (* rec for recursion *)

match n with (* pattern matching for cases *)

| 0 -> 0 (* base case *)

| n -> (2 * n -1) + sq (n -1);; (* recursive case *)

val sq : int -> int = <fun>

# sq 3;;

• : int = 9

​

​

15

Recursion in OCaml

Pattern Matching and Recursion

Compute n² recursively using:

n² = (2 * n - 1) + (n - 1)²

​

# let rec sq n = (* rec for recursion *)

match n with (* pattern matching for cases *)

| 0 -> 0 (* base case *)

| n -> (2 * n -1) + sq (n -1);; (* recursive case *)

val sq : int -> int = <fun>

# sq 3;;

• : int = 9

​

​

16

Recursion in OCaml

Pattern Matching and Recursion

Compute n² recursively using:

n² = (2 * n - 1) + (n - 1)²

​

# let rec sq n = (* rec for recursion *)

match n with (* pattern matching for cases *)

| 0 -> 0 (* base case *)

| n -> (2 * n -1) + sq (n -1);; (* recursive case *)

val sq : int -> int = <fun>

# sq 3;;

• : int = 9

​

​

17

Aside: Recursion and induction are deeply, beautifully related. (Discussed in thesis, if curious.)

Recursion in OCaml

Pattern Matching and Recursion

Compute n² recursively using:

n² = (2 * n - 1) + (n - 1)²

​

# let rec sq n = (* rec for recursion *)

match n with (* pattern matching for cases *)

| 0 -> 0 (* base case *)

| n -> (2 * n -1) + sq (n -1);; (* recursive case *)

val sq : int -> int = <fun>

# sq 3;;

• : int = 9

​

​

18

Aside: Recursion and induction are deeply, beautifully related. (Discussed in thesis, if curious.)

Recursion in OCaml

Pattern Matching and Recursion

Compute n² recursively using:

n² = (2 * n - 1) + (n - 1)²

​

# let rec sq n = (* rec for recursion *)

match n with (* pattern matching for cases *)

| 0 -> 0 (* base case *)

| n -> (2 * n -1) + sq (n -1);; (* recursive case *)

val sq : int -> int = <fun>

# sq 3;;

• : int = 9

​

​

19

Aside: Recursion and induction are deeply, beautifully related. (Discussed in thesis, if curious.)

Recursion in OCaml

Pattern Matching and Recursion

Compute n² recursively using:

n² = (2 * n - 1) + (n - 1)²

​

# let rec sq n = (* rec for recursion *)

match n with (* pattern matching for cases *)

| 0 -> 0 (* base case *)

| n -> (2 * n -1) + sq (n -1);; (* inductive case *)

val sq : int -> int = <fun>

# sq 3;;

• : int = 9

​

​

20

Aside: Recursion and induction are deeply, beautifully related. (Discussed in thesis, if curious.)

Recursion in OCaml

Pattern Matching and Recursion

Compute n² recursively using:

n² = (2 * n - 1) + (n - 1)²

​

# let rec sq n = (* rec for recursion *)

match n with (* pattern matching for cases *)

| 0 -> 0 (* base case *)

| n -> (2 * n -1) + sq (n -1);; (* inductive case *)

val sq : int -> int = <fun>

# sq 3;;

• : int = 9

​

​

21

Aside: Recursion and induction are deeply, beautifully related. (Discussed in thesis, if curious.)

Recursion in OCaml

Pattern Matching and Recursion

Compute n² recursively using:

n² = (2 * n - 1) + (n - 1)²

​

# let rec sq n = (* rec for recursion *)

match n with (* pattern matching for cases *)

| 0 -> 0 (* base case *)

| n -> (2 * n -1) + sq (n -1);; (* inductive case *)

val sq : int -> int = <fun>

# sq 3;;

• : int = 9

​

​

22

Aside: Recursion and induction are deeply, beautifully related. (Discussed in thesis, if curious.)

Recursion in OCaml

23

​

​

​

Questions so far?

Recursion in OCaml

24

​

​

​

More Recursion Next Week

Recursion in OCaml

25

​

​

​

Evaluating OCaml Programs

Evaluating declarations

• Evaluation uses an environment ρ
• To evaluate a (simple) declaration let x = e
• Evaluate expression e in ρ to value v
• Update ρ with x v: {x → v} + ρ
• Update: ρ₁+ ρ₂ has all the bindings in ρ₁ and all those in ρ₂ that are not rebound in ρ₁

{x → 2, y → 3, a → “hi”} + {y → 100, b → 6} =

{x → 2, y → 3, a → “hi”, b → 6}

​

*

26

Evaluation

Evaluating declarations

• Evaluation uses an environment ρ
• To evaluate a (simple) declaration let x = e
• Evaluate expression e in ρ to value v
• Update ρ with x v: {x → v} + ρ
• Update: ρ₁+ ρ₂ has all the bindings in ρ₁ and all those in ρ₂ that are not rebound in ρ₁

{x → 2, y → 3, a → “hi”} + {y → 100, b → 6} =

{x → 2, y → 3, a → “hi”, b → 6}

​

*

27

Evaluation

Evaluating declarations

• Evaluation uses an environment ρ
• To evaluate a (simple) declaration let x = e
• Evaluate expression e in ρ to value v
• Update ρ with x v: {x → v} + ρ
• Update: ρ₁+ ρ₂ has all the bindings in ρ₁ and all those in ρ₂ that are not rebound in ρ₁

{x → 2, y → 3, a → “hi”} + {y → 100, b → 6} =

{x → 2, y → 3, a → “hi”, b → 6}

​

*

28

Evaluation

Evaluating declarations

• Evaluation uses an environment ρ
• To evaluate a (simple) declaration let x = e
• Evaluate expression e in ρ to value v
• Update ρ with x v: {x → v} + ρ
• Update: ρ₁+ ρ₂ has all the bindings in ρ₁ and all those in ρ₂ that are not rebound in ρ₁

{x → 2, y → 3, a → “hi”} + {y → 100, b → 6} =

{x → 2, y → 3, a → “hi”, b → 6}

​

*

29

Evaluation

Evaluating declarations

• Evaluation uses an environment ρ
• To evaluate a (simple) declaration let x = e
• Evaluate expression e in ρ to value v
• Update ρ with x v: {x → v} + ρ
• Update: ρ₁+ ρ₂ has all the bindings in ρ₁ and all those in ρ₂ that are not rebound in ρ₁

{x → 2, y → 3, a → “hi”} + {y → 100, b → 6} =

{x → 2, y → 3, a → “hi”, b → 6}

​

*

30

Evaluation

Evaluating expressions in OCaml

• Evaluation takes expression e and an environment ρ, and evaluates e in ρ to some value v:
• Eval (e , ρ) => v
• A constant c evaluates to itself, including primitive operators like + and =
• Eval (c , ρ) => Val c
• To evaluate a variable v, look it up in ρ:
• Eval (v, ρ) => Val (ρ(v))

*

31

Evaluation

Evaluating expressions in OCaml

• Evaluation takes expression e and an environment ρ, and evaluates e in ρ to some value v:
• Eval (e , ρ) => v
• A constant c evaluates to itself, including primitive operators like + and =
• Eval (c , ρ) => Val c
• To evaluate a variable v, look it up in ρ:
• Eval (v, ρ) => Val (ρ(v))

*

32

Evaluation

Evaluating expressions in OCaml

• Evaluation takes expression e and an environment ρ, and evaluates e in ρ to some value v:
• Eval (e , ρ) => v
• A constant c evaluates to itself, including primitive operators like + and =
• Eval (c , ρ) => Val c
• To evaluate a variable v, look it up in ρ:
• Eval (v, ρ) => Val (ρ(v))

*

33

Evaluation

Evaluating expressions in OCaml

• Evaluation takes expression e and an environment ρ, and evaluates e in ρ to some value v:
• Eval (e , ρ) => v
• A constant c evaluates to itself, including primitive operators like + and =
• Eval (c , ρ) => Val c
• To evaluate a variable v, look it up in ρ:
• Eval (v, ρ) => Val (ρ(v))

*

34

Evaluation

Evaluating expressions in OCaml

• Evaluation takes expression e and an environment ρ, and evaluates e in ρ to some value v:
• Eval (e , ρ) => v
• A constant c evaluates to itself, including primitive operators like + and =
• Eval (c , ρ) => Val c
• To evaluate a variable v, look it up in ρ:
• Eval (v, ρ) => Val (ρ(v))

*

35

Evaluation

36

​

​

​

Questions so far?

Evaluation

Evaluating expressions in OCaml

• Evaluation takes expression e and an environment ρ, and evaluates e in ρ to some value v:
• Eval (e , ρ) => v
• We define evaluation one small step at a time. So when evaluating an expression e requires recursively evaluating some subexpression, we may write something like:
• Eval (e , ρ) => Eval (e’ , ρ’)

for subexpression e’ and updated environment ρ’.

*

37

Evaluation

Evaluating expressions in OCaml

• Evaluation takes expression e and an environment ρ, and evaluates e in ρ to some value v:
• Eval (e , ρ) => v
• We define evaluation one small step at a time. So when evaluating an expression e requires recursively evaluating some subexpression, we may write something like:
• Eval (e , ρ) => Eval (e’ , ρ’)

for subexpression e’ and updated environment ρ’

​

*

38

Evaluation

Evaluating expressions in OCaml

• Evaluation takes expression e and an environment ρ, and evaluates e in ρ to some value v:
• Eval (e , ρ) => v
• We define evaluation one small step at a time. So when evaluating an expression e requires recursively evaluating some subexpression, we may write something like:
• Eval (e , ρ) => Eval (e’ , ρ’)

for subexpression e’ and updated environment ρ’

​

*

39

Evaluation

This gives us an algorithm to implement an interpreter!

Evaluating expressions in OCaml

• To evaluate a tuple (e₁ , … , e_n):
• Evaluate each e_i to v_i, right to left for OCaml
• Then make value (v₁ , … , v_n)
• Eval((e₁ , … , e_n), ρ) =>

Eval((e₁ , … , Eval (e_n, ρ)), ρ)

• Eval((e₁ , … , e_i, Val v_i+1 , … , Val v_n), ρ) =>

Eval((e₁ , … , Eval(e_i, ρ), Val v_i+1 , … , Val v_n), ρ)

• Eval((Val v₁ , … , Val v_n) , ρ) =>

Val (v₁ , … , v_n)

​

​

​

*

40

Evaluation

Evaluating expressions in OCaml

• To evaluate a tuple (e₁ , … , e_n):
• Evaluate each e_i to v_i, right to left for OCaml
• Then make value (v₁ , … , v_n)
• Eval((e₁ , … , e_n), ρ) =>

Eval((e₁ , … , Eval (e_n, ρ)), ρ)

• Eval((e₁ , … , e_i, Val v_i+1 , … , Val v_n), ρ) =>

Eval((e₁ , … , Eval(e_i, ρ), Val v_i+1 , … , Val v_n), ρ)

• Eval((Val v₁ , … , Val v_n) , ρ) =>

Val (v₁ , … , v_n)

​

​

​

*

41

Evaluation

Evaluating expressions in OCaml

• To evaluate a tuple (e₁ , … , e_n):
• Evaluate each e_i to v_i, right to left for OCaml
• Then make value (v₁ , … , v_n)
• Eval((e₁ , … , e_n), ρ) =>

Eval((e₁ , … , Eval (e_n, ρ)), ρ)

• Eval((e₁ , … , e_i, Val v_i+1 , … , Val v_n), ρ) =>

Eval((e₁ , … , Eval(e_i, ρ), Val v_i+1 , … , Val v_n), ρ)

• Eval((Val v₁ , … , Val v_n) , ρ) =>

Val (v₁ , … , v_n)

​

​

​

*

42

Evaluation

Evaluating expressions in OCaml

• To evaluate a tuple (e₁ , … , e_n):
• Evaluate each e_i to v_i, right to left for OCaml
• Then make value (v₁ , … , v_n)
• Eval((e₁ , … , e_n), ρ) =>

Eval((e₁ , … , Eval (e_n, ρ)), ρ)

• Eval((e₁ , … , e_i, Val v_i+1 , … , Val v_n), ρ) =>

Eval((e₁ , … , Eval(e_i, ρ), Val v_i+1 , … , Val v_n), ρ)

• Eval((Val v₁ , … , Val v_n) , ρ) =>

Val (v₁ , … , v_n)

​

​

​

*

43

Evaluation

Evaluating expressions in OCaml

• To evaluate a tuple (e₁ , … , e_n):
• Evaluate each e_i to v_i, right to left for OCaml
• Then make value (v₁ , … , v_n)
• Eval((e₁ , … , e_n), ρ) =>

Eval((e₁ , … , Eval (e_n, ρ)), ρ)

• Eval((e₁ , … , e_i, Val v_i+1 , … , Val v_n), ρ) =>

Eval((e₁ , … , Eval(e_i, ρ), Val v_i+1 , … , Val v_n), ρ)

• Eval((Val v₁ , … , Val v_n) , ρ) =>

Val (v₁ , … , v_n)

​

​

​

*

44

Evaluation

Evaluating expressions in OCaml

• To evaluate a tuple (e₁ , … , e_n):
• Evaluate each e_i to v_i, right to left for OCaml
• Then make value (v₁ , … , v_n)
• Eval((e₁ , … , e_n), ρ) =>

Eval((e₁ , … , Eval (e_n, ρ)), ρ)

• Eval((e₁ , … , e_i, Val v_i+1 , … , Val v_n), ρ) =>

Eval((e₁ , … , Eval(e_i, ρ), Val v_i+1 , … , Val v_n), ρ)

• Eval((Val v₁ , … , Val v_n) , ρ) =>

Val (v₁ , … , v_n)

​

​

​

*

45

Evaluation

46

​

​

​

Questions so far?

Evaluation

Evaluating expressions in OCaml

• To evaluate uses of +, - , etc., eval args, then do operation ⦿ (+, -, *, +., …):
• Eval(e₁⦿ e₂, ρ) =>

Eval(e₁⦿ Eval(e₂, ρ), ρ))

• Eval(e₁⦿ Val e₂, ρ) =>

Eval(Eval(e₁, ρ) ⦿ Val v₂, ρ))

• Eval(Val v₁⦿ Val v₂) =>

Val (v₁⦿ v₂)

• Function expression evaluates to its closure
• Eval (fun x -> e, ρ) => Val < x -> e, ρ>

*

47

Evaluation

Evaluating expressions in OCaml

• To evaluate uses of +, - , etc., eval args, then do operation ⦿ (+, -, *, +., …):
• Eval(e₁⦿ e₂, ρ) =>

Eval(e₁⦿ Eval(e₂, ρ), ρ))

• Eval(e₁⦿ Val e₂, ρ) =>

Eval(Eval(e₁, ρ) ⦿ Val v₂, ρ))

• Eval(Val v₁⦿ Val v₂) =>

Val (v₁⦿ v₂)

• Function expression evaluates to its closure
• Eval (fun x -> e, ρ) => Val < x -> e, ρ>

*

48

Evaluation

Evaluating expressions in OCaml

• To evaluate uses of +, - , etc., eval args, then do operation ⦿ (+, -, *, +., …):
• Eval(e₁⦿ e₂, ρ) =>

Eval(e₁⦿ Eval(e₂, ρ), ρ))

• Eval(e₁⦿ Val e₂, ρ) =>

Eval(Eval(e₁, ρ) ⦿ Val v₂, ρ))

• Eval(Val v₁⦿ Val v₂) =>

Val (v₁⦿ v₂)

• Function expression evaluates to its closure
• Eval (fun x -> e, ρ) => Val < x -> e, ρ>

*

49

Evaluation

Evaluating expressions in OCaml

• To evaluate uses of +, - , etc., eval args, then do operation ⦿ (+, -, *, +., …):
• Eval(e₁⦿ e₂, ρ) =>

Eval(e₁⦿ Eval(e₂, ρ), ρ))

• Eval(e₁⦿ Val e₂, ρ) =>

Eval(Eval(e₁, ρ) ⦿ Val v₂, ρ))

• Eval(Val v₁⦿ Val v_2, ρ) =>

Val (v₁⦿ v₂)

• Function expression evaluates to its closure
• Eval (fun x -> e, ρ) => Val < x -> e, ρ>

*

50

Evaluation

Evaluating expressions in OCaml

• To evaluate uses of +, - , etc., eval args, then do operation ⦿ (+, -, *, +., …):
• Eval(e₁⦿ e₂, ρ) =>

Eval(e₁⦿ Eval(e₂, ρ), ρ))

• Eval(e₁⦿ Val e₂, ρ) =>

Eval(Eval(e₁, ρ) ⦿ Val v₂, ρ))

• Eval(Val v₁⦿ Val v₂) =>

Val (v₁⦿ v₂)

• Function expression evaluates to its closure
• Eval (fun x -> e, ρ) => Val < x -> e, ρ>

*

51

Evaluation

Evaluating expressions in OCaml

• To evaluate a local declaration:

let x = e1 in e2

• Eval e1 to v, then eval e2 using {x → v} + ρ
• Eval(let x = e₁ in e₂, ρ) => Eval(let x = Eval(e₁, ρ) in e₂, ρ)
• Eval(let x = Val v in e₂, ρ) => Eval(e₂, {x → v} + ρ)

​

*

52

Evaluation

Evaluating expressions in OCaml

• To evaluate a local declaration:

let x = e1 in e2

• Eval e1 to v, then eval e2 using {x → v} + ρ
• Eval(let x = e₁ in e₂, ρ) => Eval(let x = Eval(e₁, ρ) in e₂, ρ)
• Eval(let x = Val v in e₂, ρ) => Eval(e₂, {x → v} + ρ)

​

*

53

Evaluation

Evaluating expressions in OCaml

• To evaluate a local declaration:

let x = e1 in e2

• Eval e1 to v, then eval e2 using {x → v} + ρ
• Eval(let x = e₁ in e₂, ρ) => Eval(let x = Eval(e₁, ρ) in e₂, ρ)
• Eval(let x = Val v in e₂, ρ) => Eval(e₂, {x → v} + ρ)

​

*

54

Evaluation

Evaluating expressions in OCaml

• To evaluate a conditional expression:

if b then e₁ else e₂

• Evaluate b to a value v
• If v is true, evaluate e₁
• If v is false, evaluate e₂
• Eval(if b then e₁ else e₂, ρ) => Eval(if Eval(b, ρ) then e₁ else e₂, ρ)
• Eval(if Val true then e₁ else e₂, ρ) => Eval(e₁, ρ)
• Eval(if Val false then e₁ else e₂, ρ) => Eval(e₂, ρ)

​

*

55

Evaluation

Evaluating expressions in OCaml

• To evaluate a conditional expression:

if b then e₁ else e₂

• Evaluate b to a value v
• If v is true, evaluate e₁
• If v is false, evaluate e₂
• Eval(if b then e₁ else e₂, ρ) => Eval(if Eval(b, ρ) then e₁ else e₂, ρ)
• Eval(if Val true then e₁ else e₂, ρ) => Eval(e₁, ρ)
• Eval(if Val false then e₁ else e₂, ρ) => Eval(e₂, ρ)

​

*

56

Evaluation

Evaluating expressions in OCaml

• To evaluate a conditional expression:

if b then e₁ else e₂

• Evaluate b to a value v
• If v is true, evaluate e₁
• If v is false, evaluate e₂
• Eval(if b then e₁ else e₂, ρ) => Eval(if Eval(b, ρ) then e₁ else e₂, ρ)
• Eval(if Val true then e₁ else e₂, ρ) => Eval(e₁, ρ)
• Eval(if Val false then e₁ else e₂, ρ) => Eval(e₂, ρ)

​

*

57

Evaluation

Evaluating expressions in OCaml

• To evaluate a conditional expression:

if b then e₁ else e₂

• Evaluate b to a value v
• If v is true, evaluate e₁
• If v is false, evaluate e₂
• Eval(if b then e₁ else e₂, ρ) => Eval(if Eval(b, ρ) then e₁ else e₂, ρ)
• Eval(if Val true then e₁ else e₂, ρ) => Eval(e₁, ρ)
• Eval(if Val false then e₁ else e₂, ρ) => Eval(e₂, ρ)

​

*

58

Evaluation

Evaluating expressions in OCaml

• To evaluate a conditional expression:

if b then e₁ else e₂

• Evaluate b to a value v
• If v is true, evaluate e₁
• If v is false, evaluate e₂
• Eval(if b then e₁ else e₂, ρ) => Eval(if Eval(b, ρ) then e₁ else e₂, ρ)
• Eval(if Val true then e₁ else e₂, ρ) => Eval(e₁, ρ)
• Eval(if Val false then e₁ else e₂, ρ) => Eval(e₂, ρ)

​

*

59

Evaluation

Evaluating expressions in OCaml

• To evaluate a conditional expression:

if b then e₁ else e₂

• Evaluate b to a value v
• If v is true, evaluate e₁
• If v is false, evaluate e₂
• Eval(if b then e₁ else e₂, ρ) => Eval(if Eval(b, ρ) then e₁ else e₂, ρ)
• Eval(if Val true then e₁ else e₂, ρ) => Eval(e₁, ρ)
• Eval(if Val false then e₁ else e₂, ρ) => Eval(e₂, ρ)

​

*

60

Evaluation

61

​

​

​

Questions so far?

Evaluation

Evaluation of Application with Closures

• Given application expression f e
• In OCaml, evaluate e to value v
• In environment ρ, evaluate f to <(x₁,…,x_n) → b, ρ’>
• Evaluate body b in {x₁ → v₁,…, x_n →v_n} + ρ’
• Eval(f e, ρ) => Eval(f (Eval(e, ρ)), ρ)
• Eval(f (Val v), ρ) => Eval((Eval(f, ρ)) (Val v), ρ)
• Eval((Val<(x₁ , … , x_n)→b, ρ’>)(Val(v₁ , … , v_n)), ρ) => Eval(b, {x₁→v₁ , … , x_n→v_n} + ρ’)

*

62

Evaluation

Evaluation of Application with Closures

• Given application expression f e
• In OCaml, evaluate e to value v
• In environment ρ, evaluate f to <(x₁,…,x_n) → b, ρ’>
• Evaluate body b in {x₁ → v₁,…, x_n →v_n} + ρ’
• Eval(f e, ρ) => Eval(f (Eval(e, ρ)), ρ)
• Eval(f (Val v), ρ) => Eval((Eval(f, ρ)) (Val v), ρ)
• Eval((Val<(x₁ , … , x_n)→b, ρ’>)(Val(v₁ , … , v_n)), ρ) => Eval(b, {x₁→v₁ , … , x_n→v_n} + ρ’)

*

63

Evaluation

Evaluation of Application with Closures

• Given application expression f e
• In OCaml, evaluate e to value v
• In environment ρ, evaluate f to <(x₁,…,x_n) → b, ρ’>
• Evaluate body b in {x₁ → v₁,…, x_n →v_n} + ρ’
• Eval(f e, ρ) => Eval(f (Eval(e, ρ)), ρ)
• Eval(f (Val v), ρ) => Eval((Eval(f, ρ)) (Val v), ρ)
• Eval((Val<(x₁ , … , x_n)→b, ρ’>)(Val(v₁ , … , v_n)), ρ) => Eval(b, {x₁→v₁ , … , x_n→v_n} + ρ’)

*

64

Evaluation

Evaluation of Application with Closures

• Given application expression f e
• In OCaml, evaluate e to value v
• In environment ρ, evaluate f to <(x₁,…,x_n) → b, ρ’>
• Evaluate body b in {x₁ → v₁,…, x_n →v_n} + ρ’
• Eval(f e, ρ) => Eval(f (Eval(e, ρ)), ρ)
• Eval(f (Val v), ρ) => Eval((Eval(f, ρ)) (Val v), ρ)
• Eval((Val<(x₁ , … , x_n)→b, ρ’>)(Val(v₁ , … , v_n)), ρ) => Eval(b, {x₁→v₁ , … , x_n→v_n} + ρ’)

*

65

Evaluation

Evaluation of Application with Closures

• Given application expression f e
• In OCaml, evaluate e to value v
• In environment ρ, evaluate f to <(x₁,…,x_n) → b, ρ’>
• Evaluate body b in {x₁ → v₁,…, x_n →v_n} + ρ’
• Eval(f e, ρ) => Eval(f (Eval(e, ρ)), ρ)
• Eval(f (Val v), ρ) => Eval((Eval(f, ρ)) (Val v), ρ)
• Eval((Val<(x₁ , … , x_n)→b, ρ’>)(Val(v₁ , … , v_n)), ρ) => Eval(b, {x₁→v₁ , … , x_n→v_n} + ρ’)

*

66

Evaluation

Evaluation of Application with Closures

• Given application expression f e
• In OCaml, evaluate e to value v
• In environment ρ, evaluate f to <(x₁,…,x_n) → b, ρ’>
• Evaluate body b in {x₁ → v₁,…, x_n →v_n} + ρ’
• Eval(f e, ρ) => Eval(f (Eval(e, ρ)), ρ)
• Eval(f (Val v), ρ) => Eval((Eval(f, ρ)) (Val v), ρ)
• Eval((Val<(x₁ , … , x_n)→b, ρ’>)(Val(v₁ , … , v_n)), ρ) => Eval(b, {x₁→v₁ , … , x_n→v_n} + ρ’)

*

67

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval (plus_x z, ρ) =>

Eval (plus_x (Eval(z, ρ))) =>

Eval (plus_x (Val 3), ρ) =>

Eval ((Eval (plus_x, ρ)) (Val 3), ρ) =>

Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) => …

​

*

68

Your turn!

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval (plus_x z, ρ) =>

Eval (plus_x (Eval(z, ρ))) =>

Eval (plus_x (Val 3), ρ) =>

Eval ((Eval (plus_x, ρ)) (Val 3), ρ) =>

Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) => …

​

*

69

Keep going!

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval (plus_x z, ρ) =>

Eval (plus_x (Eval(z, ρ))) =>

Eval (plus_x (Val ?), ρ) =>

Eval ((Eval (plus_x, ρ)) (Val 3), ρ) =>

Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) => …

​

*

70

Look it up!

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval (plus_x z, ρ) =>

Eval (plus_x (Eval(z, ρ))) =>

Eval (plus_x (Val ?), ρ) =>

Eval ((Eval (plus_x, ρ)) (Val 3), ρ) =>

Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) => …

​

*

71

Look it up!

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval (plus_x z, ρ) =>

Eval (plus_x (Eval(z, ρ))) =>

Eval (plus_x (Val 3), ρ) =>

Eval ((Eval (plus_x, ρ)) (Val 3), ρ) =>

Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) => …

​

*

72

Done with argument!

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval (plus_x z, ρ) =>

Eval (plus_x (Eval(z, ρ))) =>

Eval (plus_x (Val 3), ρ) =>

Eval ((Eval (plus_x, ρ)) (Val 3), ρ) =>

Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) => …

​

*

73

Now what?

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval (plus_x z, ρ) =>

Eval (plus_x (Eval(z, ρ))) =>

Eval (plus_x (Val 3), ρ) =>

Eval ((Eval (plus_x, ρ)) (Val 3), ρ) =>

Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) => …

​

*

74

Now what?

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval (plus_x z, ρ) =>

Eval (plus_x (Eval(z, ρ))) =>

Eval (plus_x (Val 3), ρ) =>

Eval ((Eval (plus_x, ρ)) (Val 3), ρ) =>

Eval ((Val ?)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) => …

​

*

75

Look it up!

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval (plus_x z, ρ) =>

Eval (plus_x (Eval(z, ρ))) =>

Eval (plus_x (Val 3), ρ) =>

Eval ((Eval (plus_x, ρ)) (Val 3), ρ) =>

Eval ((Val ?)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) => …

​

*

76

Look it up!

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval (plus_x z, ρ) =>

Eval (plus_x (Eval(z, ρ))) =>

Eval (plus_x (Val 3), ρ) =>

Eval ((Eval (plus_x, ρ)) (Val 3), ρ) =>

Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) => …

​

*

77

Closure!

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval (plus_x z, ρ) =>

Eval (plus_x (Eval(z, ρ))) =>

Eval (plus_x (Val 3), ρ) =>

Eval ((Eval (plus_x, ρ)) (Val 3), ρ) =>

Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) => …

​

*

78

What’s next?

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) => …

​

*

79

How to evaluate closure?

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, … ) =>

​

*

80

Evaluate its body …

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, ? + ρ_{plus_x} ) =>

​

*

81

Evaluate its body in an updated environment!

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) =>

​

*

82

Evaluate its body in an updated environment!

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) =>

​

*

83

How to evaluate applied operator?

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) =>

Eval (y + Eval(x, {y → 3} + ρ_{plus_x} ), {y → 3} + ρ_{plus_x} ) =>

​

*

84

RHS first!

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) =>

Eval (y + Eval(x, {y → 3} + ρ_{plus_x} ), {y → 3} + ρ_{plus_x} ) =>

​

*

85

Look it up!

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) =>

Eval (y + Eval(x, {y → 3} + ρ_{plus_x} ), {y → 3} + ρ_{plus_x} ) =>

Eval (y + Val 12), {y → 3} + ρ_{plus_x} ) =>

​

*

86

Now what?

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) =>

Eval (y + Eval(x, {y → 3} + ρ_{plus_x} ), {y → 3} + ρ_{plus_x} ) =>

Eval (y + Val 12), {y → 3} + ρ_{plus_x} ) =>

​

*

87

LHS next!

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) =>

Eval (y + Eval(x, {y → 3} + ρ_{plus_x} ), {y → 3} + ρ_{plus_x} ) =>

Eval (y + Val 12), {y → 3} + ρ_{plus_x} ) =>

Eval (Eval(y, {y → 3} + ρ_{plus_x} ) + Val 12, {y → 3} + ρ_{plus_x} ) =>

​

*

88

LHS next!

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) =>

Eval (y + Eval(x, {y → 3} + ρ_{plus_x} ), {y → 3} + ρ_{plus_x} ) =>

Eval (y + Val 12), {y → 3} + ρ_{plus_x} ) =>

Eval (Eval(y, {y → 3} + ρ_{plus_x} ) + Val 12, {y → 3} + ρ_{plus_x} ) =>

​

*

89

Look it up in which environment?

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) =>

Eval (y + Eval(x, {y → 3} + ρ_{plus_x} ), {y → 3} + ρ_{plus_x} ) =>

Eval (y + Val 12), {y → 3} + ρ_{plus_x} ) =>

Eval (Eval(y, {y → 3} + ρ_{plus_x} ) + Val 12, {y → 3} + ρ_{plus_x} ) =>

​

*

90

Look it up locally!

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) =>

Eval (y + Eval(x, {y → 3} + ρ_{plus_x} ), {y → 3} + ρ_{plus_x} ) =>

Eval (y + Val 12), {y → 3} + ρ_{plus_x} ) =>

Eval (Eval(y, {y → 3} + ρ_{plus_x} ) + Val 12, {y → 3} + ρ_{plus_x} ) =>

Eval (Val 3 + Val 12 , {y → 3} + ρ_{plus_x} ) =>

*

91

Look it up locally!

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) =>

Eval (y + Eval(x, {y → 3} + ρ_{plus_x} ), {y → 3} + ρ_{plus_x} ) =>

Eval (y + Val 12), {y → 3} + ρ_{plus_x} ) =>

Eval (Eval(y, {y → 3} + ρ_{plus_x} ) + Val 12, {y → 3} + ρ_{plus_x} ) =>

Eval (Val 3 + Val 12, {y → 3} + ρ_{plus_x} ) =>

*

92

Finally, the operator!

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) =>

Eval (y + Eval(x, {y → 3} + ρ_{plus_x} ), {y → 3} + ρ_{plus_x} ) =>

Eval (y + Val 12), {y → 3} + ρ_{plus_x} ) =>

Eval (Eval(y, {y → 3} + ρ_{plus_x} ) + Val 12, {y → 3} + ρ_{plus_x} ) =>

Eval (Val 3 + Val 12, {y → 3} + ρ_{plus_x} ) =>

Val (3 + 12) = Val 15

​

*

93

Evaluation

Evaluation of Application of plus_x;;

• Have environment:

ρ = { plus_x →<y → y + x, ρ_{plus_x} >, … ,

y → 19, x →17, z →3, … }

where: ρ_{plus_x} = {x → 12, … , y → 24, …}

• Eval ((Val <y → y + x, ρ_{plus_x} >)(Val 3), ρ) =>

Eval (y + x, {y → 3} + ρ_{plus_x} ) =>

Eval (y + Eval(x, {y → 3} + ρ_{plus_x} ), {y → 3} + ρ_{plus_x} ) =>

Eval (y + Val 12), {y → 3} + ρ_{plus_x} ) =>

Eval (Eval(y, {y → 3} + ρ_{plus_x} ) + Val 12, {y → 3} + ρ_{plus_x} ) =>

Eval (Val 3 + Val 12, {y → 3} + ρ_{plus_x} ) =>

Val (3 + 12) = Val 15

​

*

94

Evaluation

95

​

​

​

Questions so far?

Evaluation

Evaluation of Application of plus_pair

• Assume environment

ρ = {x → 3 , … , plus_pair →<(n, m) →n + m, ρ_{plus_pair}>}

+ ρ_{plus_pair}

​

• Eval (plus_pair (4, x), ρ) =>

Eval (plus_pair (Eval ((4, x), ρ)), ρ) =>

Eval (plus_pair (Eval ((4, Eval (x , ρ)), ρ)), ρ) =>

Eval (plus_pair (Eval ((4, Val 3), ρ)), ρ) =>

Eval (plus_pair (Eval ((Eval (4, ρ), Val 3), ρ)), ρ) =>

Eval (plus_pair (Eval ((Val 4, Val 3), ρ)), ρ) =>

​

*

96

Evaluation

Evaluation of Application of plus_pair

• Assume environment

ρ = {x → 3 , … , plus_pair →<(n, m) →n + m, ρ_{plus_pair}>}

+ ρ_{plus_pair}

​

• Eval (plus_pair (4, x), ρ) =>

Eval (plus_pair (Eval ((4, x), ρ)), ρ) =>

Eval (plus_pair (Eval ((4, Eval (x , ρ)), ρ)), ρ) =>

Eval (plus_pair (Eval ((4, Val 3), ρ)), ρ) =>

Eval (plus_pair (Eval ((Eval (4, ρ), Val 3), ρ)), ρ) =>

Eval (plus_pair (Eval ((Val 4, Val 3), ρ)), ρ) =>

​

*

97

Evaluation

Evaluation of Application of plus_pair

• Assume environment

ρ = {x → 3 , … , plus_pair →<(n, m) →n + m, ρ_{plus_pair}>}

+ ρ_{plus_pair}

​

• Eval (plus_pair (4, x), ρ) =>

Eval (plus_pair (Eval ((4, x), ρ)), ρ) =>

Eval (plus_pair (Eval ((4, Eval (x , ρ)), ρ)), ρ) =>

Eval (plus_pair (Eval ((4, Val 3), ρ)), ρ) =>

Eval (plus_pair (Eval ((Eval (4, ρ), Val 3), ρ)), ρ) =>

Eval (plus_pair (Eval ((Val 4, Val 3), ρ)), ρ) =>

​

*

98

Evaluation

Evaluation of Application of plus_pair

• Assume environment

ρ = {x → 3 , … , plus_pair →<(n, m) →n + m, ρ_{plus_pair}>}

+ ρ_{plus_pair}

​

• Eval (plus_pair (4, x), ρ) =>

Eval (plus_pair (Eval ((4, x), ρ)), ρ) =>

Eval (plus_pair (Eval ((4, Eval (x , ρ)), ρ)), ρ) =>

Eval (plus_pair (Eval ((4, Val 3), ρ)), ρ) =>

Eval (plus_pair (Eval ((Eval (4, ρ), Val 3), ρ)), ρ) =>

Eval (plus_pair (Eval ((Val 4, Val 3), ρ)), ρ) =>

​

*

99

Evaluation

Evaluation of Application of plus_pair

• Assume environment

ρ = {x → 3 , … , plus_pair →<(n, m) →n + m, ρ_{plus_pair}>}

+ ρ_{plus_pair}

​

• Eval (plus_pair (4, x), ρ) =>

Eval (plus_pair (Eval ((4, x), ρ)), ρ) =>

Eval (plus_pair (Eval ((4, Eval (x , ρ)), ρ)), ρ) =>

Eval (plus_pair (Eval ((4, Val 3), ρ)), ρ) =>

Eval (plus_pair (Eval ((Eval (4, ρ), Val 3), ρ)), ρ) =>

Eval (plus_pair (Eval ((Val 4, Val 3), ρ)), ρ) =>

​

*

100

Evaluation

Evaluation of Application of plus_pair

• Assume environment

ρ = {x → 3 , … , plus_pair →<(n, m) →n + m, ρ_{plus_pair}>}

+ ρ_{plus_pair}

​

• Eval (plus_pair (4, x), ρ) =>

Eval (plus_pair (Eval ((4, x), ρ)), ρ) =>

Eval (plus_pair (Eval ((4, Eval (x , ρ)), ρ)), ρ) =>

Eval (plus_pair (Eval ((4, Val 3), ρ)), ρ) =>

Eval (plus_pair (Eval ((Eval (4, ρ), Val 3), ρ)), ρ) =>

Eval (plus_pair (Eval ((Val 4, Val 3), ρ)), ρ) =>

​

*

101

Evaluation

Evaluation of Application of plus_pair

• Assume environment

ρ = {x → 3 , … , plus_pair →<(n, m) →n + m, ρ_{plus_pair}>}

+ ρ_{plus_pair}

​

• Eval (plus_pair (4, x), ρ) =>

Eval (plus_pair (Eval ((4, x), ρ)), ρ) =>

Eval (plus_pair (Eval ((4, Eval (x , ρ)), ρ)), ρ) =>

Eval (plus_pair (Eval ((4, Val 3), ρ)), ρ) =>

Eval (plus_pair (Eval ((Eval (4, ρ), Val 3), ρ)), ρ) =>

Eval (plus_pair (Eval ((Val 4, Val 3), ρ)), ρ) =>

​

*

102

Evaluation

Evaluation of Application of plus_pair

• Assume environment

ρ = {x → 3 , … , plus_pair →<(n, m) →n + m, ρ_{plus_pair}>}

+ ρ_{plus_pair}

​

• Eval (plus_pair (4, x), ρ) =>

Eval (plus_pair (Eval ((4, x), ρ)), ρ) =>

Eval (plus_pair (Eval ((4, Eval (x , ρ)), ρ)), ρ) =>

Eval (plus_pair (Eval ((4, Val 3), ρ)), ρ) =>

Eval (plus_pair (Eval ((Eval (4, ρ), Val 3), ρ)), ρ) =>

Eval (plus_pair (Eval ((Val 4, Val 3), ρ)), ρ) =>

​

*

103

Evaluation

Evaluation of Application of plus_pair

• Assume environment

ρ = {x → 3 , … , plus_pair →<(n, m) →n + m, ρ_{plus_pair}>}

+ ρ_{plus_pair}

• Eval (plus_pair (Eval ((Val 4, Val 3), ρ)), ρ) =>

Eval (plus_pair (Val (4, 3)), ρ) =>

Eval (Eval (plus_pair, ρ), Val (4, 3)), ρ) => …

Eval ((Val<(n,m)→n+m, ρ_{plus_pair}>)(Val(4,3)) , ρ)=>

Eval (Val (n + m), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Eval (Val (4 + 3), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Val 7

​

​

*

104

Evaluation

Evaluation of Application of plus_pair

• Assume environment

ρ = {x → 3 , … , plus_pair →<(n, m) →n + m, ρ_{plus_pair}>}

+ ρ_{plus_pair}

• Eval (plus_pair (Eval ((Val 4, Val 3), ρ)), ρ) =>

Eval (plus_pair (Val (4, 3)), ρ) =>

Eval (Eval (plus_pair, ρ), Val (4, 3)), ρ) => …

Eval ((Val<(n,m)→n+m, ρ_{plus_pair}>)(Val(4,3)) , ρ)=>

Eval (Val (n + m), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Eval (Val (4 + 3), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Val 7

​

​

*

105

Evaluation

Evaluation of Application of plus_pair

• Assume environment

ρ = {x → 3 , … , plus_pair →<(n, m) →n + m, ρ_{plus_pair}>}

+ ρ_{plus_pair}

• Eval (plus_pair (Eval ((Val 4, Val 3), ρ)), ρ) =>

Eval (plus_pair (Val (4, 3)), ρ) =>

Eval (Eval (plus_pair, ρ), Val (4, 3)), ρ) => …

Eval ((Val<(n,m)→n+m, ρ_{plus_pair}>)(Val(4,3)) , ρ)=>

Eval (Val (n + m), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Eval (Val (4 + 3), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Val 7

​

​

*

106

Evaluation

Evaluation of Application of plus_pair

• Assume environment

ρ = {x → 3 , … , plus_pair →<(n, m) →n + m, ρ_{plus_pair}>}

+ ρ_{plus_pair}

• Eval (plus_pair (Eval ((Val 4, Val 3), ρ)), ρ) =>

Eval (plus_pair (Val (4, 3)), ρ) =>

Eval (Eval (plus_pair, ρ), Val (4, 3)), ρ) =>

Eval ((Val<(n,m)→n+m, ρ_{plus_pair}>)(Val(4,3)) , ρ)=>

Eval (Val (n + m), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Eval (Val (4 + 3), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Val 7

​

​

*

107

Evaluation

Evaluation of Application of plus_pair

• Assume environment

ρ = {x → 3 , … , plus_pair →<(n, m) →n + m, ρ_{plus_pair}>}

+ ρ_{plus_pair}

• Eval (plus_pair (Eval ((Val 4, Val 3), ρ)), ρ) =>

Eval (plus_pair (Val (4, 3)), ρ) =>

Eval (Eval (plus_pair, ρ), Val (4, 3)), ρ) =>

Eval ((Val<(n,m)→n+m, ρ_{plus_pair}>)(Val (4 , 3)) , ρ)=>

Eval (Val (n + m), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Eval (Val (4 + 3), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Val 7

​

​

*

108

Evaluation

Evaluation of Application of plus_pair

• Assume environment

ρ = {x → 3 , … , plus_pair →<(n, m) →n + m, ρ_{plus_pair}>}

+ ρ_{plus_pair}

• Eval (plus_pair (Eval ((Val 4, Val 3), ρ)), ρ) =>

Eval (plus_pair (Val (4, 3)), ρ) =>

Eval (Eval (plus_pair, ρ), Val (4, 3)), ρ) =>

Eval ((Val<(n,m)→n+m, ρ_{plus_pair}>)(Val (4 , 3)) , ρ)=>

Eval (Val (n + m), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Eval (Val (4 + 3), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Val 7

​

​

*

109

Evaluation

Evaluation of Application of plus_pair

• Assume environment

ρ = {x → 3 , … , plus_pair →<(n, m) →n + m, ρ_{plus_pair}>}

+ ρ_{plus_pair}

• Eval (plus_pair (Eval ((Val 4, Val 3), ρ)), ρ) =>

Eval (plus_pair (Val (4, 3)), ρ) =>

Eval (Eval (plus_pair, ρ), Val (4, 3)), ρ) =>

Eval ((Val<(n,m)→n+m, ρ_{plus_pair}>)(Val (4 , 3)) , ρ)=>

Eval (Val (n + m), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Eval (Val (4 + 3), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Val 7

​

​

*

110

Evaluation

Evaluation of Application of plus_pair

• Assume environment

ρ = {x → 3 , … , plus_pair →<(n, m) →n + m, ρ_{plus_pair}>}

+ ρ_{plus_pair}

• Eval (plus_pair (Eval ((Val 4, Val 3), ρ)), ρ) =>

Eval (plus_pair (Val (4, 3)), ρ) =>

Eval (Eval (plus_pair, ρ), Val (4, 3)), ρ) =>

Eval ((Val<(n,m)→n+m, ρ_{plus_pair}>)(Val (4 , 3)) , ρ)=>

Eval (Val (n + m), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Eval (Val (4 + 3), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Val 7

​

​

*

111

Evaluation

Evaluation of Application of plus_pair

• Assume environment

ρ = {x → 3 , … , plus_pair →<(n, m) →n + m, ρ_{plus_pair}>}

+ ρ_{plus_pair}

• Eval (plus_pair (Eval ((Val 4, Val 3), ρ)), ρ) =>

Eval (plus_pair (Val (4, 3)), ρ) =>

Eval (Eval (plus_pair, ρ), Val (4, 3)), ρ) =>

Eval ((Val<(n,m)→n+m, ρ_{plus_pair}>)(Val (4 , 3)) , ρ)=>

Eval (Val (n + m), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Eval (Val (4 + 3), {n -> 4, m -> 3} + ρ_{plus_pair}) =>

Val 7

​

​

*

112

Evaluation

113

​

​

​

Questions?

• To use recursion in OCaml, you need the rec keyword
• Evaluation takes expression e and an environment ρ, and evaluates e in ρ to some value v:
• Eval (e , ρ) => v
• We define evaluation one small step at a time. So when evaluating an expression e requires recursively evaluating, we write:
• Eval (e , ρ) => Eval (e’ , ρ’)

for subexpression e’ and updated environment ρ’

• This gives an algorithm for an interpreter!

​

Takeaways

114

115

Next Class:

Lists, more recursion

​

• MP2 due Tuesday
• This is worth points!
• Please do this!
• WA2 due next Thursday
• All deadlines can be found on course website
• Use office hours and class forums for help

Reminder: Also Next Class

116

Next Class