Semantics

Heaps (v2)

Example

x = 5;

y = 7;

z = x;

y = z;

5

7

c=1

c=1

x

y

z

None

c=1

c=2

c=4

c=3

c=2

c=3

c=0

Deallocate

This is how we presented heaps

Example

x = 5;

y = 7;

z = x;

y = z;

x

y

z

None

c=1

c=2

c=4

c=3

But you may have been thinking, why not this?

Example

x = 5;

y = 7;

z = x;

y = z;

5

7

c=1

c=1

x

y

z

None

c=1

c=2

c=4

c=3

c=0

Deallocate

5

c=1

c=2

c=1

5

c=1

c=2

c=1

That is right. so we we’d need to change our semantic rule to produce this heap. Note, however, that if you push the following heap changes all the way through the semantics (very carefully), the programs still compute the same outputs! As in my note on piazza, this is just a different representation choice. As long a as you get the right outputs, either will work. But, these two slides show that maybe you get a smaller heap with this alternative.

But you may have been thinking, why not this?

In this version, every time we assign a value to

a variable, we create a new object for it…because this is what are slides from the semantics do.

Frames and Heaps

x = 1;

y = 2;

z = 3;

Still the same as before!�(See slides in lecture 8)

Evaluation Relations (with heaps - before)

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

​

​

​

​

​

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

Evaluation Relations (with heaps, v2)

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

​

​

​

​

​

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

Now return an address to the computed value!

Expressions: Inference Rules

Allocate a new address for the value

Just return the address!

Expressions: Inference Rules

This rule below allocates a new address for the value

Note, we will end up with lots of allocations. 1 allocation for every operation. But, most will turn out to be garbage (like a here) as we only hold on to final result!

Expressions: Inference Rules

Note, have to thread the heap through�each expression. Expressions have side-effects on�the heap now, whereas before they were pure �meaning (no side effects)

Statements: Inference Rules

No allocation! See how we’ve moved allocations to the computations rather

than for them happening at the assignment.

Self-Exercise: Records

• Records are a little bit easier now
• The following slides are the original slides on records from the lecture. Think about/write new syntax and rules for
1. Creating records in expressions rather at an assignment or declaration. It’s easier now.
2. Assigning to a field in a record.

​

(note: you will have to update your heaps to store values rather than just integers!)

Add Records: Grammar

(update record)

(create record)

Records

• Record constructor
• Design decision: how to represent the record contents?

var a = { x : 1; y : 2};

var b = a;

b.x = 3;

print(a.x)

What’s the output?

Records

• Record constructor
• Design decision: how to represent the record contents?