Beyond Values

Lots of us probably have some gut feeling for what a value is in Python: for example, 3, or "hello!", or [1,2,3,4,5].

In this note, I want to write about some ideas about values that I picked up in the functional programming world, and how things are not as simple as they seem. For motivation, I'll talk about a couple of features in projects I've worked on: Parsl and Globus Compute.

I'm going to talk about this implication:

$$x = y \implies f(x) = f(y) \qquad \forall x,y,f$$

This looks like some weird logic formula... but it's capturing something that when you're think about mathematical values and functions, you assume is true without thinking about it much.

A simple example

Here's an example, which I'll write in Python:

>>> def f(v):
...  return v+1

>>> x = 3
>>> f(x)
4

What is this going to evaluate to?

>>> y = 3
>>> f(y)

It's (obviously?) going to return 4 - but there's two ways we can reason about this: we can type that into the Python interpreter and look at the result of computing f(y)...

... or we can say well, f(x) must be the same as f(y) because x=y and I already know that f(x) is 4, so f(y) must also be 4.

@functools.cache

In essence that's what's happening when you use the @cache decorator from the functools package like this:

>>> @functools.cache
... def g(v):
...   print(f"Calculating for {v}")
...   return v+1

>>> g(x)
Calculating for 3
4

>>> g(y)
4

The second time we invoke g, the decorator sees that it's already been invoked with an equal parameter, and doesn't run the underlying body, instead relying on the return value it cached.

In Parsl, at a high level, this is also what happens when you turn on memoization and checkpointing to avoid re-executing Parsl task invocations.

Pure functions and equality

When you are doing this in a language like Python, rather than in the abstract maths world, it relies on the function (in the Python sense) behaving (mostly) like a function (in the maths sense) - it has to be pure, and not have effects.

But, it also relies on equality working correctly - something that we usually don't think about. For example, here are some "obviously True (or False)" Python relations: 3 == 3, 3 != 4, [1,2] == [1,2], [1,2] != [5,6,7], and so on.

In the rest of this note I want to dig into some specific cases where this doesn't work.

Functions with effects

First, functions can have effects (sometimes called side-effects). There's already one of those in the example I pasted above: I put a debugging print statement into the definition of g so that we could tell if it ran or not.

In this case, it was deliberate, and we can say it's ok to have debugging prints, because they don't affect the essential functionality: to return an incremented number. But this behaviour would be wrong if the effect was part of the essential behaviour.

For example, a function h(count) that operate hardware to dispense a given number of cat treats and return True if that worked ok: it would be incorrect to return True without dispensing anything. In this case, it's ok to describe h as a Python function, but it's not a function in the mathematical sense.

Effects don't have to change the world to make a Python function not be a mathematical function any more: for example, a Python function that observes the time (via time.time()) might return different values depending on when it is invoked - and so the output wouldn't be entirely defined by the input argument.

Other easy examples that I run into in this space are computing random numbers (random.random()) and inspecting the runtime environment (platform.node()).

Object structure as effect

Another effect is when Python code looks not at the "value" (whatever that is) of an object, but at the nature of the Python object itself. Most brazenly, there is the id function, which returns:

Return the “identity” of an object. This is an integer which is guaranteed to be unique and constant for this object during its lifetime. (python.org)

For example, with objects that represent large numbers, the values of two objects compare the same (with ==) but the id function returns different values:

>>> x = 1000000

>>> y = 1000000
>>> x == y
True
>>> id(x) == id(y)
False
>>> id(x)
139863203106896
>>> id(y)
139863203107280

Object identity with is

This leads to a second notion of equality in Python: in addition to the == value comparison operator, there is is, an operator that checks if two objects are the same object.

This operator looks at object identities, not at values, but it is still in some sense an equality (or equivalence) operator. We can think about the original referential transparency implication using `is` as a different equality on one side:

    x is y => f(x) == f(y)

Different equalities (or equivalences - I'm being deliberately vague about the difference here) can be related to each other: for example, an equivalance can be finer than another equivalence.

For example, we might expect that: a is b => a == b.

That's a way of saying that an object is always ==-equal to itself. This is reflexivity and it's another "obvious" thing that we don't always think about but sometimes rely on.

There's at least one counterexample built into Python (and you can create your own in your own __eq__ implementations) - it's an ongoing "controversy" with IEEE754, the standard for floating point arithmetic.

>>> x = math.nan
>>> x is x
True
>>> x == x
False

Where would you run into this in practice? If you were looking for a float in a data structure using ==: you would never find nan. Luckily people are culturally scared of using floats as keys, so actually not so much in practice.

Differing representations of equal values

Another place where the notion of value becomes a bit fuzzy is when there are different representations of the ==-same value: such as with dictionaries.

Here are two ==-equal dictionaries: the keys and values are all well behaved objects (str), they have the same keys and each key maps to the same value in both x, y.

>>> x = {"a":"one", "b":"two"}
>>> y = {"b":"two", "a":"one"}
>>> x == y
True

They're different according to is, because they are different objects, which shouldn't be too surprising:

>>> x is y
False

>>> x['a'] == y['a']
True
>>> len(x) == len(y)
True

>>> list(x.keys()) == list(y.keys())
False

Where would you run into this? Perhaps we're iterating over the entries in a dictionary - Parsl does this when computing the checkpoint hash of a dict object. You won't necessarily encounter the entries in the same order (so the parsl code normalises the list of keys by sorting - which restores the equality-behaviour [TODO code sample?]).

Another related problem could be using UUIDs: UUIDs usually have multiple string representations (because the hex values a-f can each be written as a lower-case or upper-case letter) so the equality of UUIDs-rendered-as-strings is not the same equality as equality-of-UUIDs:

>>> import uuid
>>> s1 = "af240119-eaa7-4d3d-b5ee-0a1d9064e3bd"
>>> s2 = "aF240119-eAa7-4D3d-B5eE-0a1D9064e3Bd"
>>> s1 == s2
False
>>> uuid.UUID(s1) == uuid.UUID(s2)
True

Subclasses

Another equality awkwardness arises with subclasses: in Python, bool is a subclass of int (for, I think, historical reasons) and the two elements of that type, False and True are ==-equal to 0 and 1:

>>> False == 0
True
>>> True == 1
True

>>> d = {}
>>> d[1] = str(1)
>>> d[True] = str(True)
>>> d
{1: 'True'}

This sort of behaviour can arise with user defined enums too -- although in Python 3.11, for user defined IntEnum in this specific str case, that code now returns the underlying integer to make this less surprising - a change that has caused some different surprise in Parsl log file output.

Rules of equality

I've talked about two different kinds of equality/equivalence that we care about, == and is, but there are more!

First, let's briefly go through the rules we would like to hold, both for equalities for how equalities interact with functions:

I mentioned above reflexivity. We would like: x = x for every value x.

There are a couple of others that usually come bundled with that:

Transitivity: If x == y and y == z, then x == z

A counter example to that might be if we define an equality for real numbers where x == y if x and y are within 0.1 of each other: this doesn't satisfy transitivity, because 0.0 = 0.07 and 0.07 = 0.14 but 0.0 != 0.14

The other property that equivalence relations should have symmetry: if x = y then y = x - so that it doesn't matter which way round we compare things. Where that can have practical effect in Python is in choosing which __eq__ gets to run first, x.__eq__ or y.__eq__. Nothing forces those two implementations to return consistent results.

And finally, the referential transparency equation I started with, about how equality and functions should interact: If x = y, then f(x) = f(y).

There are two other kinds of equality I'd like to talk about: hash based equality, and a slightly weirder serialisation based equality.

Hash equality

Some objects can be hashed, and we can hope that that hash is a function of their value. Depending on the characteristics of the hash, there are a couple of ways we can use this:

For any hash, we can assume that: x = y => hash(x) = hash(y) and so we can do things like put stuff in hash buckets: if we're looking for y, we know that if some x exists already where x = y, it will be in hash bucket hash(y) (aka. hash(x)) - we can forget about all the other hash buckets entirely.

This works (slowly) even if the hash function is poor: for example, the constant hash(x) = 7 - where it's quite easy to see that this relationship holds: x = y => 7 = 7. (There was a bug in the Globus Toolkit string hash function sometime around 2004, where it only hashed a prefix of strings, and that prefix was often the same - globus_ - so the hash function effectively became a constant)

With stronger hash functions, we can hope that the relationship goes the other way too: x = y <=> hash(x) = hash(y). With that we can do parsl style checkpointing, which makes a hash of the parameters to a function, and uses that as a cache key in an external database. This is only safe because of the stronger relationship between = and our checkpoint hash: we need to be sure that x != y => hash(x) != hash(y). In some sense, we need the ==-equality and the hash equality to be "the same" equality.

In the Parsl checkpointing code, one of the biggest complications is computing such a hash for complex objects, using the parsl id_for_memo function: we need a hash value that is consistent in the face of different representations of the same object (see the discussion about dict above) and we need a hash that is consistent between Python processes, so that when a Parsl workflow is re-run, function invocations with the "same" parameters will be found in the checkpoint database.

Serialization: equality by construction

I put "same" in quotes there, because here's a new, more abstract kind of equality. The kinds I've talked about before, ==, is and hashing are all equalities that you can compute inside a single Python process (by evaluating the Python expression x == y in your Python process, for example).

But what does it mean for values to be equal when they are kept inside different Python processes? At the code level, there's no longer a way to compute whether two objects represent the same value by passing into some comparison operator or function (like == or is).

We've got serialisation, and what we care about in Parsl is something involving serialization and equality: if in my first process I have a function and a value, and I send the function and the value to another process, and in that second process apply the function to the value, and then send the result back, then I end up with a value that is equal to if I applied the function to the value locally. (like with checkpointing, we're describing a computation and then instead of performing that computation, doing something that we believe to be equivalent)

TODO: looping diagram of (f,v) -> r, -> (f',v') -> r' -> r

So there's a notion of equality-by-serialisation: if I take an value in one process and deserialise it so that it behaves the same, in the above sense, then that value in one process is equal to the value on the other process. This is by construction, not by comparison - you can construct an equal object on the remote system, but not test an existing distant object for equality directly.

Getting serialisation right (in this value equality sense) can be quite complicated. In the Parsl and Globus Compute world, the most complexity comes from getting functions and classes from one place to the other, with three different ways in use: if a function or class seems likely to be installed remotely (based on some not-always-right heuristics in dill) then it will be referenced by name; otherwise dill can attempt to send Python's internal representation (which does not work well when each end is a different version of Python) and finally a Globus Compute specific method will try to send the source code for a function (which doesn't work when a function doesn't have source code).

This latter method has echoes of Python's repr method:

For many types, this function makes an attempt to return a string that would yield an object with the same value when passed to eval();

Mutability

One final awkwardness comes with the passage of time, or mutability: objects in Python are often mutable, which means their value can be changed. Mutability means that the equality behaviour between two objects can change. For example, with the pretty strong is equality relation, we usually have x is x => str(x) == str(x). But that doesn't work over time - for example if we make a function memoization cache keyed by a reference to the object x, then change the value of object x, the memoization will break: object identity over time doesn't imply value identity over time.

TODO: example from parsl here: open bug on returning a mutable object from @cache to a user, where the user can then perform arbitrary mutations - https://github.com/Parsl/parsl/issues/2555. For two identical bytestrings x == y, deserialise(x) == deserialise(y) ... but that doesn't hold over time if the object returned by deserialise(x) is mutable.

Conclusion

So, in summary - while we often get told to be careful about functions having side effects (and so not being true mathematical functions) - we don't get told so much to be careful about how *values* behave: what does it mean for two values to be the same (which of several choices of equality do we mean?), and how do they interact with functions. Often we don't have to think about it - but sometimes we do, and I've tried in this note to highlight some of the places that this has caused trouble while working on the parsl and globus compute codebase.