►A Data-Centric Introduction to Computing
►IV Programming With State
▼11 Programming with State (in Both Pyret and Python)
►11.4 Cyclic Data
On this page:
11.4.1 Creating Cyclic Data
11.4.2 Testing Cyclic Data
11.4.3 Cycles in Practice
    contents    up   

11.4 Cyclic Data🔗

    11.4.1 Creating Cyclic Data

    11.4.2 Testing Cyclic Data

    11.4.3 Cycles in Practice

11.4.1 Creating Cyclic Data🔗

Earlier [Aliasing], we introduced the idea of aliased bank accounts, where multiple customers can operate the same account. Sometimes, a bank wants to keep track of all the customers who have access to a given account. For instance, when the account balance runs low, it would want to notify all the customers who have access to it.

Therefore, each account needs to maintain a list of its customers. Because the set of owners can change over time, we make that field mutable in Pyret:

Python

Pyret

@dataclass
class Account:
    id: int
    balance: int
    owners: list # of Customer

@dataclass
class Customer:
    name: str
    acct: Account


data Account:
    account(id :: Number,
      ref balance :: Number,
      ref owners :: List<Customer>)
end

data Customer:
    cust(name :: String,
      acct :: Account)
end

If you look closely, you’ll see that Account refers to Customer (specifically, a list of them) and in turn Customer refers to Account. This could get interesting.

Previously, we could create an account with one customer as follows:

Python

elena = Customer("Elena", Account(8404, 500))

Pyret

elena = cust("Elena", account(8404, 500))

How do we do that now? Every Account requires a list of its Customers. We need to write

Python

elena = Customer("Elena", Account(8404, 500, [_____]))

Pyret

elena = cust("Elena", account(8404, 500, [list: _____]))

But what goes in _____? It needs to refer to the very customer account that we are presently creating.

Another way to think about writing this is:

Python

acct1 = Account(8404, 500, [_____])
elena = Customer("Elena", acct1)

Pyret

acct1 = account(8404, 500, [list: _____])
elena = cust("Elena", acct1)

This hasn’t solved our fundamental problem—we still need to fill in _____—but at least we now have names to refer to entities. We would like to be able to write

Python

acct1 = Account(8404, 500, [elena])
elena = Customer("Elena", acct1)

Pyret

acct1 = account(8404, 500, [list: elena])
elena = cust("Elena", acct1)

But when we try to run this, both Python and Pyret will give us an error. That is because they try to evaluate the right-hand-side of the first line to create an account, whose heap address will be bound in the directory to acct1. To do so, they must evaluate that account-creation expression. In doing so, they look up the name elena. However, elena has not yet been bound in the directory. Therefore, they produce an error.

Observe that we can’t just reverse the order of these two bindings. If we try that, we end up with the same problem: we try to create a customer that refers to acct1. But we haven’t yet defined acct1, producing the same error.

The problem is we are trying to create cyclic data. The two data refer to one another. We could already sense that this might happen from the data definitions, and now we must confront it. The problem is that we have to create some value first, and we can’t produce either one correctly since each one depends on the other.

As you might guess, we have to compromise. We have to construct one of the data first, and when we do so, it might not be entirely accurate. Then we create the other, and then modify the first one to have the correct contents.

In our case, the Pyret version makes clear what order to use in creating the data. Nothing in a Customer is mutable (nor needs to be), whereas the list of account owners is (and should be, because the set of customers can grow). Therefore, we can write:

Python

acct1 = Account(8404, 500, [])

Pyret

acct1 = account(8404, 500, empty)

Note that at this point, this is actually accurate! There are no owners of this account.

Now we create Elena’s account:

Python

elena = Customer("Elena", acct1)

Pyret

elena = cust("Elena", acct1)

At this point, our memory looks like this:For simplicity, we will show the list of owners inside the account instead of putting it in its own memory location(s).

Directory

  • acct1

     → 1001

  • elena

     → 1002

Heap

  • 1001: Account(8404, 500, [])

  • 1002: Customer("Elena", 1001)

Now things are slightly inaccurate: the account at 1001 does have an owner, which is not yet reflected. So we have to update it to reflect that:

Python

Pyret

acct1.owners = [elena]

acct1!{owners: [list: elena]}

We can legitimately do this now because elena is bound in the dictionary. Furthermore, it is bound to something useful: Elena’s customer information. So now the values are properly set up: Elena’s customer information refers to the account, and the account refers to Elena’s customer information:

Directory

  • acct1

     → 1001

  • elena

     → 1002

Heap

  • 1001: Account(8404, 500, [1002])

  • 1002: Customer("Elena", 1001)

This is the cycle in “cyclic”: 1001 depends on 1002 and 1002 depends on 1001.

Observe that if we introduce another customer, Jorge, who shares the same account, we can update the account to reflect that also:

Python

jorge = Customer("Jorge", acct1)

Pyret

jorge = cust("Jorge", acct1)

Again, the information in acct1 is inaccurate because it does not reflect the new owner. We can modify it in a similar way:

Python

acct1.owners = acct1.owners + [jorge]

Pyret

acct1!{owners: acct1!owners + [list: jorge]}

So now our memory would look like this:

Directory

  • acct1

     → 1001

  • elena

     → 1002

  • jorge

     → 1003

Heap

  • 1001: Account(8404, 500, [1002, 1003])

  • 1002: Customer("Elena", 1001)

  • 1003: Customer("Jorge", 1001)

Do Now!

We wrote slightly different code when adding Jorge’s account than when adding Elena’s account. Is one better than the other?

The code for Elena’s addition ignored whatever owners there previously were. That is, it would only work correctly in a setting where there were no other owners. The code for Jorge’s addition takes into account all the previous owners. Therefore, Elena’s code was perfectly fine for illustrating the simple first case, but Jorge’s code is more general in that it will work in all settings (including when the prior list of owners is empty).

Exercise

Write a function that takes care of adding a customer to an account.

11.4.2 Testing Cyclic Data🔗

When you want to write a test involving circular data, you can’t write out the circular data manually. For example, imagine that we wanted to write out acct1 from earlier:

Python

assert(acct1 = Account(8404, 500, [Customer("Elena", Account(8404, 500, …)]))

Pyret

check:
  acct1 is
    account(8404, 500, [list: cust("Elena", account(8404, 500, …))])
end

However, because of the circularity, we can’t finish writing down the data. We can’t just leave part of it unspecified with ….

This leaves us with two choices:

You have two options: write tests in terms of the names of data, or write tests on the components of the data.

Here’s an example that illustrates both. After setting up the account, we might want to check that the owner of the new account is the new customer:

assert(new_acct.owner is new_cust)

Here, rather than write out the Customer explicitly, we use the name of the existing item in the directory. This doesn’t require you to write ellipses. We also focused on just the owner component, as a part of the Account value that we expected to change.

11.4.3 Cycles in Practice🔗

Cyclic data show up in many settings in real programs. Whenever two data are interrelated, and we have good reason to want to get from either one to the other, they have the potential to have references to each other, which can lead to cycles. Sometimes the connection can be to provide updates, as above; other times it can simply be for navigational convenience.

Consider the Document Object Model (DOM), which is the data structure that represents every Web page in a Web browser. Programmers usually think of the DOM hierarchically, as a tree, because every note refers to all the nodes that constitute it: e.g., a page has references to each of its paragraphs, a list has references to each list item, and so forth. However, every one of these elements also has a reference to its parent. This way, a program can conveniently traverse “downward” or “upward”.

Programming with cyclic data introduces complications. If we traverse the data naïvely, we would go into an infinite loop. Rather, we have to keep track of the data we have previously visited, and make sure we don’t visit them again (see The Size of a DAG). Indeed, cyclic data are graphs [Graphs], so issues in processing graphs become relevant here.

One interesting question that programming languages face is, how do you print cyclic data? For instance, what happens if the programmer writes 

acct1

? To print the account we must print its owners; to print each owner, we must print their account; to print that account…

Do Now!

Try it out in both Python and Pyret!

Different programming languages handle this problem in different ways. Some languages will go into an infinite loop trying to print cyclic data. Both Python and Pyret handle this more intelligently. Determining even whether a datum is cyclic is an interesting question, which we take up in Detecting Cycles.

    contents    up