Closures

Today: Linked Stacks

Where are we now?

• IMP
• Heaps
• Types
• Closures
• Scopes (Stacks)
• Long-lived scopes (Linked Stacks)
• Functions

​

​

What is a Closure?

​

​

​

​

​

​

• A function and a scope (in which to run the function)
• First-class: a closure is a value
• Higher-Order: functions may take closures as arguments

​

var f = fun(x) {

print(x);

};

f(1);

var x = 1;

var f = fun() {

print(x);

};

f();

Output: 1

var x = 1;

var f = fun() {

x = 2;

};

print(x)

var g = fun(h) {

h();

}

print(x)

g(f);

print(x);

Output: 1

Outputs: �1�1�2

Challenge: Managing Scopes

A closure may refer to the value of variable from a scope that has been popped from the stack

​

Scope’s frame may live longer than the the single execution of the scope’s code

​

What do we do?

var f = 0;

{

var x = 1;

f = fun() {

print(x);

x = x + 1;

};

}

f();

f();

f();

Output:

1

2

3

Statements: Inference Rules

Expressions: Inference Rules

Integer

Constant

Variable

Reference

Unary

Minus

Statements: Inference Rules

{

var x = 1;

var x = 2;

}

Statements: Inference Rules

Update

Challenge: Managing Scopes

A closure may refer to the value of variable from a scope that has been popped from the stack

​

Scope’s frame may live longer than the the single execution of the scope’s code

​

What do we do?

var f = 0;

{

var x = 1;

f = fun() {

print(x);

x = x + 1;

};

}

f();

f();

f();

Output:

1

2

3

Closures versus “Functions”

void f() {

int x = 1;

printf(“%d\n”, x);

x = x + 1;

}

void f() {

static int x = 1;

printf(“%d\n”, x);

x = x + 1;

}

int x = 1;

void f() {

printf(“%d\n”, x);

x = x + 1;

}

void main(...) {

f(); f(); f();

}

var f = 0;

{

var x = 1;

f = fun() {

print(x);

x = x + 1;

};

}

f();

f();

f();

Output:

1

1

3

Closures versus “Functions” (C++ Attempt)

void f() {

int x = 1;

printf(“%d\n”, x);

x = x + 1;

}

void f() {

static int x = 1;

printf(“%d\n”, x);

x = x + 1;

}

int f_x = 1;

void f() {

printf(“%d\n”, f_x);

f_x = f_x + 1;

}

void main(...) {

f(); f(); f();

}

Output:

1

1

1

Output:

1

2

3

Output:

1

2

3

Challenge: Managing Scopes

var f = 0;

{

var x = 1;

f = fun() {

print(x);

x = x + 1;

};

}

f();

f();

f();

Output:

1

2

3

var g = fun() {

var x = 1;

var f = fun() {

print(x);

x = x + 1;

};

return f;

};

g()();

g()();

g()();

Output:

1

1

1

Challenge: Managing Scopes

A closure may refer to the value of variable from a scope that has been popped from the stack

​

Scope’s frame may live longer than the the single execution of the scope’s code

​

What do we do?

var f = 0;

{

var x = 1;

f = fun() {

print(x);

x = x + 1;

};

}

f();

f();

f();

Output:

1

2

3

Allocate frames in the heap!

Closures versus “Functions”

struct FClosure {

int x;

FClosure() : x() { }

int f() {

printf(“%d\n”, this.x);

this.x = this.x + 1;

}

};

​

FClosure* g() { return new FClosure();}

​

int main(...)

{

g()->f(); g()->f(); g()->f();

}

var g = fun() {

var x = 1;

var f = fun() {

print(x);

x = x + 1;

};

return f;

};

g()();

g()();

g()();

These are Automation (plus more)

f = lambda x, y : x + y

var f = function(x, y) {

return x + y;

}

var f = (x, y) => {

return x + y;

}

auto f = [](int x, int y) {

return x + y;

};

BinaryOperator<int> f = (int x, int y) -> {

return x + y;

};

Python

C++

Java

Javascript

Extending IMP with Closures

• Syntax: create and call closures

​

• Representation: closures are values and frames are long-lived

​

• Semantics: creating and calling closures

Extending IMP with Closures

• Syntax: create and call closures

​

• Representation: closures are values and frames are long-lived

​

• Semantics: creating and calling closures

Add Closures: Grammar

(call closure)

Extending IMP with Closures

• Syntax: create and call closures

​

• Representation: closures are values and frames are long-lived

​

• Semantics: creating and calling closures

Linked Stacks

1: var x = 1;

2: var y = 2;

3: {

4: var x = 3;

5: y = 4;

6: }

Linked Stacks

1: var x = 1;

2: var y = 2;

3: {

4: var x = 3;

5: y = 4;

6: }

Linked Stacks

1: var x = 1;

2: var y = 2;

3: {

4: var x = 3;

5: y = 4;

6: }

Linked Stacks

1: var x = 1;

2: var y = 2;

3: {

4: var x = 3;

5: y = 4;

6: }

Linked Stacks

1: var x = 1;

2: var y = 2;

3: {

4: var x = 3;

5: y = 4;

6: }

Linked Stacks

1: var x = 1;

2: var y = 2;

3: {

4: var x = 3;

5: y = 4;

6: }

Linked Stacks

1: var x = 1;

2: var y = 2;

3: {

4: var x = 3;

5: y = 4;

6: }

Frames, Heaps, Linked Stacks, and Closures

Evaluation Relations (with heaps and stacks)

• Define the semantics of each term in our language (E, B, and S) with an evaluation relation:

​

​

​

​

​

• Meaning: given a stack, and heap, the term evaluates to a result

Evaluation Relations (with linked stacks)

• Define the semantics of each term in our language (E, B, and S) with an evaluation relation:

​

​

​

​

​

• Meaning: given a frame pointer, and heap, the term evaluates to a result

Expressions: Inference Rules

Integer

Constant

Variable

Reference

Unary

Minus

Lookup

Expressions: Inference Rules

Integer

Constant

Variable

Reference

Unary

Minus

Inference Rules: Declaration

In-place update

Inference Rules: Assignment

Update

Inference Rules: Block Scope

Extending IMP with Closures

• Syntax: create and call closures

​

• Representation: closures are values and frames a long-lived

​

• Semantics: creating and calling closures

Inference Rules: Closure Creation (Declaration)

Inference Rules: Closure Creation

​

​

​

​

​

​

​

• Execution: capture frame pointer

​

​

​

​

​

Managing Scope (Revisited)

1: var f = 0;

2: {

3: var x = 1;

4: f = fun(y) {

5: print(x);

6: x = x + 1;

7: };

8: }

9: f(1);

10: f(2);

Managing Scope (Revisited)

1: var f = 0;

2: {

3: var x = 1;

4: f = fun(y) {

5: print(x);

6: x = x + 1;

7: };

8: }

9: f(1);

10: f(2);

Managing Scope (Revisited)

1: var f = 0;

2: {

3: var x = 1;

4: f = fun(y) {

5: print(x);

6: x = x + 1;

7: };

8: }

9: f(1);

10: f(2);

Managing Scope (Revisited)

1: var f = 0;

2: {

3: var x = 1;

4: f = fun(y) {

5: print(x);

6: x = x + 1;

7: };

8: }

9: f(1);

10: f(2);

Managing Scope (Revisited)

1: var f = 0;

2: {

3: var x = 1;

4: f = fun(y) {

5: print(x);

6: x = x + 1;

7: };

8: }

9: f(1);

10: f(2);

Managing Scope (Revisited)

1: var f = 0;

2: {

3: var x = 1;

4: f = fun(y) {

5: print(x);

6: x = x + 1;

7: };

8: }

9: f(1);

10: f(2);

Managing Scope (Revisited)

1: var f = 0;

2: {

3: var x = 1;

4: f = fun(y) {

5: print(x);

6: x = x + 1;

7: };

8: }

9: f(1);

10: f(2);

Inference Rules: Closure Execution

x Evaluates to a closure

E evaluates to a value

Create a new frame

Evaluate body of closure

Managing Scope (Revisited)

1: var f = 0;

2: {

3: var x = 1;

4: f = fun() {

5: print(x);

6: x = x + y;

7: };

8: var y = 2;

9: }

10: f(1);

11: f(2);