Day 28 - Mutable Data Structures and the Heap

Skills: 7

Pre-reading: 12.5

Intro (15 mins)

Today we look at how mutable data structures work in both Pyret and Python, and how the "heap" model helps us understand mutation and aliasing.

In Pyret, mutable fields in data must be marked with ref, are accessed with !, and updated using !{field: new_value}. Immutable fields use . and cannot be changed.

data LibraryBook:
  library-book(id :: Number, title :: String, ref copies :: Number)
end
book1 = library-book(101, "The Curious Incident", 5)
book2 = book1
book1!{copies: book1!copies - 1}
# book2!copies is now 4, because book2 is an alias for book1

In Python, all fields in structured values (like those created with @dataclass) are mutable by default. Assignment with = both creates and updates variables and fields. There is no syntactic difference between changing variables and fields inside data in Python, as both use =, but these have significant semantic different.
```
from dataclasses import dataclass

@dataclass
class LibraryBook:
    id: int
    title: str
    copies: int

book1 = LibraryBook(101, "The Curious Incident", 5)
book2 = book1
book1.copies = book1.copies - 1
# book2.copies is now 4, because book2 is an alias for book1
```
The program directory maps names to addresses in the heap, where the actual data lives. If two names refer to the same address, mutating through one changes the value for both.
In Python == checks for structural equality (same contents), while is checks for reference equality (same address in the heap). In Pyret, == (and the is in tests) checks that two values are always the same, which, for immutable values, means they are equal as values. For mutable values, it means they are the same object in memory. This is a safer default (if two values are == in Pyret, you won't be surprised by one changing to be different from the other), but it is not how Python works, so be careful!

In Python:

book3 = LibraryBook(101, "The Curious Incident", 5)
print(book1 == book3)  # True if contents are the same
print(book1 is book3)  # False, different objects
print(book1 is book2)  # True, same object (alias)

In Pyret:

book3 = library-book(101, "The Curious Incident", 5)
print(book1 == book3)  # false, since they are different objects and number of copies is mutable
print(book1 == book1)  # true, same object

Class Exercises (40 mins)

Analyze this Python code. What gets printed and why?

list1 = [1, 2, 3]
list2 = list1
list1.append(4)
print(list2)

Analyze this Pyret code. What gets printed and why?

data Box: box(ref value :: Number) end
box1 = box(10)
box2 = box1
box1!{value: 20}
box2!value

Draw the program directory and heap for this scenario:

obj1 = {"name": "Alice", "age": 25}
obj2 = {"name": "Alice", "age": 25}
obj3 = obj1
obj1["age"] = 26

Show which variables are affected and why.

Analyze this Python code. What do the comparisons return?

list1 = [1, 2, 3]
list2 = [1, 2, 3]
list3 = list1
print(list1 == list2)
print(list1 is list2)
print(list1 is list3)

Analyze this Pyret code. What does the comparison return?

data Point: point(x :: Number, y :: Number) end
p1 = point(5, 10)
p2 = point(5, 10)
p1 == p2

Trace through this Python function. What happens after each call?

def add_item(my_list, item):
    my_list.append(item)
    return my_list

original = [1, 2]
result1 = add_item(original, 3)
result2 = add_item(original, 4)
print(original)
print(result1)
print(result2)

Trace through this Pyret function with aliased records:

data Counter: counter(ref count :: Number) end
fun increment(c):
  c!{count: c!count + 1}
end

c1 = counter(0)
c2 = c1
increment(c1)
c2!count

Analyze this Python code. What gets printed?

list1 = [10, 20, 30]
list2 = list1
list1[1] = 99
print(list1)
print(list2)

Trace this Python function through multiple calls:

def make_list():
    new_list = [1, 2, 3]
    new_list.append(4)
    return new_list

result1 = make_list()
result2 = make_list()
print(result1 is result2)

Trace this Pyret function through multiple calls:

fun make-counter():
  var count = 0
  count := count + 1
  count
end

result1 = make-counter()
result2 = make-counter()
result1 == result2

Analyze this Python dataclass example:

from dataclasses import dataclass

@dataclass
class Person:
    name: str

person1 = Person("Alice")
person2 = Person("Bob")
person3 = person1
person1.name = "Charlie"
print(person2.name)
print(person3.name)

Wrap-up (5 mins)

In both Pyret and Python, mutable data structures live in the heap and can be aliased.
Mutating through one alias affects all.
Structural equality checks contents; reference equality checks identity.
Understanding these concepts is key to writing correct code and avoiding bugs related to aliasing and mutation.

Skills: 7​

Pre-reading: 12.5​

Intro (15 mins)​

Class Exercises (40 mins)​

Wrap-up (5 mins)​

Skills: 7

Pre-reading: 12.5

Intro (15 mins)

Class Exercises (40 mins)

Wrap-up (5 mins)