Day 28 - Mutable Data Structures and the Heap

Skills: 7

Pre-reading: DRAFT:11.5

Intro (10 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 objects (like those created with @dataclass) are mutable by default. Assignment with = both creates and updates variables and fields.

  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 object). 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.
• 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 (35 mins)

• In Python, create two variables that refer to the same list or object. Mutate the object using one variable. What happens to the other? Why?
• In Pyret, create two variables that refer to the same mutable record. Mutate a field using one variable. What happens to the other? Why?
• Draw the program directory and heap for a scenario where you create two objects with the same contents, make a third variable an alias for one of them, and mutate a field. Show which variables are affected and why.
• In Python, create two objects with the same contents and compare them with == and with is. What do you observe?
• In Pyret, create two records with the same contents and compare them with ==.
• Write a Python function that takes a list as input and appends a value to it. What happens if you call this function multiple times on the same list? On different lists?
• Write a Pyret function that mutates a field in a record. What happens if you call this function on two aliases?
• In Python, create two variables that refer to the same list. Change one element of the list using one variable (you can mutate lists in Python with l[n] = ...). What happens to the other variable? Why?
• In Pyret, you can create what is essentially a mutable list with [array: 1, 2, 3]. Create two variables that refer to the same array. Change the array using one variable (you can mutate an array a with a.set-now(index, value)). What happens to the other variable? Why?
• Write a Python function that creates a list inside the function, modifies it, and returns it. What happens if you call the function multiple times? Does each call return a new list or the same list? Why?
• Write a Pyret function that creates a mutable variable inside the function, modifies it, and returns it. What happens if you call the function multiple times? Does each call return a new value or the same value? Why?
• In Python, create a class with a mutable field. Create two instances of the class, make one an alias for the other, and mutate the field in one instance. What happens to the other instance? Why?

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.