Recently, as an aside to the proposal for static type annotations in Python, Guido offhandedly noted another suggested improvement to Python, adding ADTs (Algebraic Data Types). This has also come up in discussions about pattern matching, and about existing run-time and compile-time static-typing libraries.

What is an ADT?

Instead of trying to fully define an ADT in formal terms (see Wikipedia, or, better, work through a Haskell tutorial, for that), I'll try to define it in terms of values as you might use them in Python.

Basically, an ADT is either a simple type, a product of ADTs, or a sum of ADTs. That's what makes it "algebraic".

Product types

What is a product of types? It's a tuple: (42, "spam") is of type int * str, or, written more simply, (int, str).*

Often you want to add names to the values, like (answer: 42, manna: "spam"), which is of type (answer: int) * (manna: str), or (answer: int, manna: str). Note the equivalency to the "implicit namedtuple literals" that people suggest for Python every few months.

And often you want to add a name to the tuple itself, making this a full "record" type, like ImportantStuff(answer: 42, manna: "spam"), which is of type ImportantStuff:((answer: int) * (manna: str)) or ImportantStuff(answer: int, manna: str). This is exactly like the namedtuple that Python has today. It's also like a C struct (or Python ctypes.Structure).

Note that none of these is like an OO class, especially Python's rendition of that concept. Besides the fact that classes have methods, they have an arbitrary bag of attributes, not an ordered sequence of them. They may have private attributes that are part of the structure but not part of the interface, and computed attributes that are part of the interface but not part of the structure. And so on. (The classes in weaker OO languages like C++ and Java are closer to record types—which is why C++ just defines "class" and "struct" to mean the same thing, except for the default visibility of their members.)

* Notice that, since a tuple type is just a product of types, a single-element tuple is the exact same thing as its one value. And an empty tuple is a singleton value of some unit type that's the result of not multiplying anything (equivalent to 0 when multiplying integers). Python of course distinguishes single-element tuples from their values: (spam,) != (spam). And Python's closest thing to a unit type is NoneType, whose value, None, is often used inside tuples. So, Python's tuple isn't quite a purist version of an untagged product type. But I think we can ignore that difference here.

Sum types

A sum type is a union of two types. This is the part Python doesn't really have today.

Consider a URL-fetching function, which can return either a successful download, an error download, or a failure to even get an error. (Ignore for now the fact that Python would use an exception for the third case.) So, it might return something like:

    ((headers: Sequence[str], body: Iterable[str])
     | (code: int, description: str, headers: Sequence[str], body: Iterable[str])
     | (errno: int,))

On its own, this isn't very usable; to know which of the three you've gotten, you need to either LBYL the members of the returned record with getattr, or EAFP it by using a try:/except AttributeError:. And consider that, at least with HTTP, successful downloads actually have a code and description, just like failed downloads, meaning the two record types are identical, giving you no way to distinguish them! So often, you will want to tag the values:

    (success: (headers: Sequence[str], body: Iterable[str])
     | failure: (code: int, description: str, headers: Sequence[str], body: Iterable[str])
     | error: (errno: int,))

But notice that a tagged union of plain (named) tuples is exactly equivalent to an untagged union of records. You could just as well write that type as:

    (Success(headers: Sequence[str], body: Iterable[str])
     | Failure(code: int, description: str, headers: Sequence[str], body: Iterable[str])
     | Error(errno: int,))

Either way, a language could allow you to dissect unions with the same member syntax used by records. But the latter allows you to dissect them by pattern matching, or sometimes just by comparison, which is often much simpler.

In practice

Most languages that make heavy use of ADTs go with a sort of hybrid: the tags are part of the named record type, but named record types can only be defined inside sum types, and therefore it doesn't really matter.

For example, here's how cons lists are generally defined:

    List(Cons(head: T, tail: List[T]) | Nil())

Here Cons and Nil are called constructors for List. Whichever way you interpret this, Nil() is an instance of type Nil (or of the Nil kind of type List), and also an instance of type List.* Cons(1, Nil()) is an instance of type Cons[int] (or the Cons kind of type List[int]), and also an instance of type List[int].

However, this does raise a question of namespacing: is the name Cons available in the same scope as List, or do you have to write Cons.List? (It's not a coincidence that this same question that comes up with enum in many languages, which I'll get to later.)

* It's worth noting that in most ADT-based languages, this Nil() can have a type, like List[int]; the fact that it isn't always inferable just means that sometimes you have to specify it explicitly.

Optional/Maybe

One special case that people often propose for Python isn't really special at all.

A value that can be either an int or None is just int | NoneType.

A value that can be either an int or None, with the type tagged by a name, is (Just(int) | Nothing(NoneType)).*

In languages that make sum types very concise, like Haskell,** it's perfectly reasonable to write Maybe int as a type, and Just 42 or Nothing as values of that type, and to pattern match the value as Just n | Nothing.

Many other languages add syntactic sugar: int? means Maybe[int], n! means the value of n or raise an exception if it's Nothing, n? means nil-chaining (an expression with n? has the value of the expression with the Just value if n is not Nothing, or it has the value Nothing if n is Nothing), there may be shortcut values to extract a value (e.g., Swift's "if let n: int = m {} else {}", and so on. But under the covers, these are all doing things that can be expressed directly in terms of the sum type.

* Note that the direct mapping of Haskell's Maybe to Python would be (Just(int,) | Nothing()). But because Python's unions aren't mathematical product types, and NoneType isn't a real unit type, as described earlier, it's more convenient to tag non-record-typed values in the Maybe, and there's really no theoretical reason you can't do that, it just means either treating the tags are part of the union rather than part of a record constructor, or a bit of extra syntactic sugar.

** In Haskell, tags are available in the outer namespace, and type parameters and constructors, like functions, don't need parentheses around their arguments.

Fitting ADTs into Python

Product types

As noted above, Python already has tuples and named record types, but not anonymous record types. How do we add those?

namedtuple

The existing namedtuple works fine for named record types.

The proposals for implicit namedtuple literals have, as far as I know, been coherent (at least Christian Tismer's worked out all of the tricky details and showed that they weren't so tricky after all); the only reason they haven't gone anywhere is that no one could explain a real need for them. So let's just add that, and use it for our anonymous tagged records:

    (answer: 42, manna: "spam")

The type of that is:

    (answer: int, manna: str)

Alternative: typed __slots__

A class with __slots__ is also pretty close to a named record type, and in some ways seems like a better fit, assuming we had a syntax to type the slots, which seems pretty easy.

However, the fact that, unlike a namedtuple, it's not a tuple is at least a theoretical problem, if not a practical one. The fact that there is nothing requiring the constructor arguments to map to the slots is a bigger problem. And it's hard to imagine a way to write these anonymously and inline (short of some kind of horrible expression using the type class's constructor).

Sum types

Python doesn't have sum types at all, except implicitly. And explicit sum types, especially either tagged sums of anonymous products or sums of named products, are exactly what people are missing when they ask for ADTs in Python.

So, how could we add them?

MyPy Union

MyPy adds a Union type: Union[int, NoneType] (or, more compactly, int | str) is a value that can be either an int or a str.

While this only gives us untagged unions, as noted above, tagged unions are equivalent to untagged unions of record types. So, if we wanted to define a Haskell-like Maybe, we could do this:

    Just = namedtuple('Just', (('value', T,)))
    Nothing = namedtuple('Nothing', ())
    Maybe = Just | Nothing

Also, without pattern matching, the only way to actually use this is with isinstance checks (or EAFP try/except):

    def spam(eggs: Maybe[int]):
        if isinstance(n, Just[int]):
            print('Spam with {} eggs'.format(eggs.value))
        else:
            print('The spam stands alone')

There's nothing theoretically wrong here, but it certainly is ugly.

Swift-style Enum

Consider that a sum type of tagged parameterless type constructors is equivalent to a Python-style Enum, with the constructors mapping to enumeration members:

    Color = (Red | Blue | Green)

    Color = Enum('Color', 'Red Blue Green')

You can do the same things with each (although with slightly different syntax). The question of whether Red, Blue, and Green leak into the parent scope or are attributes of Color arises in exactly the same way for the two cases, and has the same pro and con arguments.

So, what if Enum were extended to allow values to be attached to each member? This is exactly what Swift enumerations are, and this is how Swift handles sum types.

I'm going to assume some extension to the language that allows statically typing variables and attributes, rather than doing it in comments a la MyPy, and I'm going to assume that tuples of types are specified as tuples of types rather than some other syntax, but feel free to translate.

    class Barcode(Enum):
        UPCA: (int, int, int, int) = 1
        QRCode: str = 2

So now, you can do this:

    >>> barcode = Barcode.UPCA(8, 85909, 51226, 3)
    >>> barcode
    <Barcode.UPCA(8, 85909, 51226, 3): 1>
    >>> barcode.value
    (8, 85909, 51226, 3)

Or, if you wanted to name the parts of the UPC-A:

    class Barcode(Enum):
        UPCA: (LL: int, L: int, R: int, RR: int) = 1
        QRCode: str = 2

    >>> barcode = Barcode.UPCA(8, 85909, 51226, 3)
    >>> barcode
    <Barcode.UPCA(LL: 8, L: 85909, R: 51226, RR: 3): 1>
    >>> barcode.LL
    8

Of course you still need isinstance, pattern matching, or EAFP code to distinguish whether you've got a UPCA or a QRCode:

    >>> barcode = Barcode.QRCode('ABCDEFGHIJKLMNOP')
    >>> barcode.LL
    AttributeError: 'Barcode.QRCode' object has no attribute 'LL'
    >>> barcode

But still, it looks a lot prettier than using Union.

What about recursion?

One of the important features of ADTs is that they can be recursive. See the List example above: the second element of a Cons is a List.

In Python, this means we either need some kind of explicit forward reference (as used by MyPy), or a way to define sum types and record types in such a way that they can automatically use the type being defined.

Notice that it's relatively easy to write an "auto-numbered" Enum class that doesn't require you to specify a value; referencing an unknown name just gives it the next number in sequence and binds it. With a slightly smarter/hackier metaclass, I believe you could also write an "auto-recursive" Enum that assumes any unknown name is the class itself, and then checks at construction time that the only unknown name seen was the class name. I haven't actually tried to do this, but I'm going to just naively assume it's possible; if not, something like MyPy's forward references may be necessary.

So ADTs are just a subset of classes?

Each namedtuple type is a class, and each Enum type is a class, and I've defined ADTs in terms of (implicit) namedtuples and Enums. This seems at first to go against the spirit of ADTs, which are a completely alternative form of typing to OO classes.

But note that in Python, tuple is a class, int is a class, NonteType is a class, every type is a class.

More importantly, ADTs are a strict subset of classes. The "strict subset" part is what makes them useful: they have a static structure, they have 

Does Python really need this?

The big question is: under what circumstances would you want to use an ADT (whether implemented as an Enum with anonymous nanedtuple values, or otherwise) instead of a class?

If the language had pattern matching that only worked on ADTs, the answer might well be "quite often".

But without pattern matching, or with pattern matching that worked on classes that chose to opt in (as described in my previous blog post), I think it wouldn't be that often.

A paradigm case: JSON

JSON is (quite accidentally) an ADT. You can define it as:

    class JSON(Enum):
        null: NoneType = 0
        boolean: bool = 1
        number: numbers.Number = 2
        string: str = 3
        array: Sequence[JSON] = 4
        obj: Mapping[str, JSON] = 5

So, what would your code look like if json.loads returned one of these, instead of just returning a dict?

For the quick&dirty case, it would obviously be a whole lot more inconvenient to parse out a JSON than a plain dict. Today, you can already write:

    j = json.loads(s)
    j['aliases'][0]['first']

But if you want to specify a schema, map it to objects in your hierarchy, and validate it, that would be a huge pain with dynamically walking the structure, but comparatively easy treating JSON as an ADT:

    class Name((first: str, last: str)):
        def tojson(self):
            return JSON.object({'first': self.first, 'last': self.last})
        @classmethod
        def fromjson(cls, j):
            case j:
                of JSON.object as o:
                    return cls(o['first'], o['last'])
            raise ValueError('{} is not a name'.format(j))

    class Person((aliases: Sequence[Name], age: float)):
        def tojson(self):
            return JSON.object({'aliases': JSON.array(map(Name.tojson, self.aliases)), 'age': age})
        @classmethod
        def fromjson(cls, j):
            case j:
                of JSON.object as o:
                    case o['aliases']:
                        of JSON.array as a:
                            return cls([Name.fromjson(name) for name in a], o['age'])
            raise ValueError('{} is not a person'.format(j))

(Of course there's no reason Name and Person couldn't be "pure" ADTs, with free functions instead of methods, but it seems more Pythonic this way.)

This pattern matching syntax is nowhere near as simple as the ML or Haskell equivalent, which implies that maybe I didn't do as good a job with my straw-man syntax as I'd hoped. But note that a JSON parsing framework could automate all of that pattern matching based on the attributes and types of the class. Assuming I'd written such a thing, or found it on PyPI, or inherited it from the web framework I'm using, I could write the above as:

    class Name(JSONable[(first: str, last: str)]):
        pass

    class Person(JSONable[(aliases: Sequence[Name], age: float]):
        pass

So:

    person = Person.fromjson(json.loads(s))
    person['aliases'][0]['first']

This looks almost as simple as the non-validating case, but it will raise an exception if s doesn't actually specify a Person.

So, is that a good enough use case to include ADTs in Python?

5

View comments

  1. Oh my god please do it. I'm looking for just the F# Option type to work as a start , with pattern matching ie Some(d)= opt. And all the related methods that just naturally combine functions with the result ie bind, iter, map. Very hard to avoid writing spaghetti code without it.

    ReplyDelete
    Replies
    1. I think this comment gets to the crux of the issue: ADTs aren't very useful without pattern matching (unless, maybe, you have something like fmap). But adding pattern matching in general to Python is complicated (see http://stupidpythonideas.blogspot.com/2014/08/a-pattern-matching-case-statement-for.html). And adding ADTs and pattern matching just for ADTs seems like it would lead to two very different-feeling language subsets sutured into one.

      Meanwhile, if you're just trying to translate idiomatic F# code directly to Python, you're bound to get bad code, just as when you try to translate idiomatic Java to Python—or Python to Java. (There are plenty of blog posts out there explaining why you get bad results, and why it's unavoidable.) If you're going to program effectively in Python, you need to think Pythonically. Type-driven pattern-matching programming is far from the only way to avoid writing spaghetti code—but if it's the only way you know of, then you're going to write spaghetti code in any language that isn't designed to make your style easy.

      Also, Python _does_ have map, and other higher-order functions (not to mention comprehensions, which often make them unnecessary). They're the traditional Lisp-style HOFs that take a function and some arguments and generate some results (map(f: A->B, Iterable[A]) -> Iterator[B])), not the Haskell-style HOFs that take a function and return a new function that takes some arguments and generates some results (map(f: A->B) -> (Iterable[A] -> Iterator[B])). But that's just because Python—like Lisp and most other functional languages—doesn't auto-curry functions. And, while auto-currying has advantages, it also has disadvantages—for example, making it work with variable-argument functions is very tricky. And the reason it doesn't have the full set of monad/functor-related HOFs is that most of them are either not useful without auto-currying, or not useful without type-driven programming, so they wouldn't be useful in Python. Some of them are sometimes useful, but generally they're the ones that are so easy to write yourself that the stdlib doesn't really need them. (For example, if you need an identity function, lambda x: x, or, if you need it more than once, def identity(x): return x and then pass identity around just as you'd pass id around in Haskell.)

      Delete
    2. Well this is a start: https://gist.github.com/tuomas56/b86c7d7e7cc593ddf782

      Delete
    3. This comment has been removed by the author.

      Delete
  2. I know it's ugly as hell, but I get by by encoding my sum type values in terms of their catamorphism. Then, at least, "pattern matching" on them is just a function call. Here's an example:

    def duration_period(end_date, duration):
    return lambda if_duration, if_date: if_duration(end_date, duration)

    def date_period(end_date, start_date):
    return lambda if_duration, if_date: if_date(end_date, start_date)

    # Period -> String
    def print_period(period):
    return period(
    if_duration = lambda end_date, nPeriods: "end_date: {0}, nPeriods: {1}".format(str(end_date), str(nPeriods)),
    if_date = lambda end_date, start_date: "end_date: {0}, start_date: {1}".format(str(end_date), str(start_date)))

    ReplyDelete
Hybrid Programming
Hybrid Programming
5
Greenlets vs. explicit coroutines
Greenlets vs. explicit coroutines
6
ABCs: What are they good for?
ABCs: What are they good for?
1
A standard assembly format for Python bytecode
A standard assembly format for Python bytecode
6
Unified call syntax
Unified call syntax
8
Why heapq isn't a type
Why heapq isn't a type
1
Unpacked Bytecode
Unpacked Bytecode
3
Everything is dynamic
Everything is dynamic
1
Wordcode
Wordcode
1
For-each loops should define a new variable
For-each loops should define a new variable
4
Views instead of iterators
Views instead of iterators
2
How lookup _could_ work
How lookup _could_ work
2
How lookup works
How lookup works
7
How functions work
How functions work
2
Why you can't have exact decimal math
Why you can't have exact decimal math
2
Can you customize method resolution order?
Can you customize method resolution order?
1
Prototype inheritance is inheritance
Prototype inheritance is inheritance
1
Pattern matching again
Pattern matching again
The best collections library design?
The best collections library design?
1
Leaks into the Enclosing Scope
Leaks into the Enclosing Scope
2
Iterable Terminology
Iterable Terminology
8
Creating a new sequence type is easy
Creating a new sequence type is easy
2
Going faster with NumPy
Going faster with NumPy
2
Why isn't asyncio too slow?
Why isn't asyncio too slow?
Hacking Python without hacking Python
Hacking Python without hacking Python
1
How to detect a valid integer literal
How to detect a valid integer literal
2
Operator sectioning for Python
Operator sectioning for Python
1
If you don't like exceptions, you don't like Python
If you don't like exceptions, you don't like Python
2
Spam, spam, spam, gouda, spam, and tulips
Spam, spam, spam, gouda, spam, and tulips
And now for something completely stupid…
And now for something completely stupid…
How not to overuse lambda
How not to overuse lambda
1
Why following idioms matters
Why following idioms matters
1
Cloning generators
Cloning generators
5
What belongs in the stdlib?
What belongs in the stdlib?
3
Augmented Assignments (a += b)
Augmented Assignments (a += b)
11
Statements and Expressions
Statements and Expressions
3
An Abbreviated Table of binary64 Values
An Abbreviated Table of binary64 Values
1
IEEE Floats and Python
IEEE Floats and Python
Subtyping and Ducks
Subtyping and Ducks
1
Greenlets, threads, and processes
Greenlets, threads, and processes
6
Why don't you want getters and setters?
Why don't you want getters and setters?
8
The (Updated) Truth About Unicode in Python
The (Updated) Truth About Unicode in Python
1
How do I make a recursive function iterative?
How do I make a recursive function iterative?
1
Sockets and multiprocessing
Sockets and multiprocessing
Micro-optimization and Python
Micro-optimization and Python
3
Why does my 100MB file take 1GB of memory?
Why does my 100MB file take 1GB of memory?
1
How to edit a file in-place
How to edit a file in-place
ADTs for Python
ADTs for Python
5
A pattern-matching case statement for Python
A pattern-matching case statement for Python
2
How strongly typed is Python?
How strongly typed is Python?
How do comprehensions work?
How do comprehensions work?
1
Reverse dictionary lookup and more, on beyond z
Reverse dictionary lookup and more, on beyond z
2
How to handle exceptions
How to handle exceptions
2
Three ways to read files
Three ways to read files
2
Lazy Python lists
Lazy Python lists
2
Lazy cons lists
Lazy cons lists
1
Lazy tuple unpacking
Lazy tuple unpacking
3
Getting atomic writes right
Getting atomic writes right
Suites, scopes, and lifetimes
Suites, scopes, and lifetimes
1
Swift-style map and filter views
Swift-style map and filter views
1
Inline (bytecode) assembly
Inline (bytecode) assembly
Why Python (or any decent language) doesn't need blocks
Why Python (or any decent language) doesn't need blocks
18
SortedContainers
SortedContainers
1
Fixing lambda
Fixing lambda
2
Arguments and parameters, under the covers
Arguments and parameters, under the covers
pip, extension modules, and distro packages
pip, extension modules, and distro packages
Python doesn't have encapsulation?
Python doesn't have encapsulation?
3
Grouping into runs of adjacent values
Grouping into runs of adjacent values
dbm: not just for Unix
dbm: not just for Unix
How to use your self
How to use your self
1
Tkinter validation
Tkinter validation
7
What's the deal with ttk.Frame.__init__(self, parent)
What's the deal with ttk.Frame.__init__(self, parent)
1
Does Python pass by value, or by reference?
Does Python pass by value, or by reference?
9
"if not exists" definitions
"if not exists" definitions
repr + eval = bad idea
repr + eval = bad idea
1
Solving callbacks for Python GUIs
Solving callbacks for Python GUIs
Why your GUI app freezes
Why your GUI app freezes
21
Using python.org binary installations with Xcode 5
Using python.org binary installations with Xcode 5
defaultdict vs. setdefault
defaultdict vs. setdefault
1
Lazy restartable iteration
Lazy restartable iteration
2
Arguments and parameters
Arguments and parameters
3
How grouper works
How grouper works
1
Comprehensions vs. map
Comprehensions vs. map
2
Basic thread pools
Basic thread pools
Sorted collections in the stdlib
Sorted collections in the stdlib
4
Mac environment variables
Mac environment variables
Syntactic takewhile?
Syntactic takewhile?
4
Can you optimize list(genexp)
Can you optimize list(genexp)
MISRA-C and Python
MISRA-C and Python
1
How to split your program in two
How to split your program in two
How methods work
How methods work
3
readlines considered silly
readlines considered silly
6
Comprehensions for dummies
Comprehensions for dummies
Sockets are byte streams, not message streams
Sockets are byte streams, not message streams
9
Why you don't want to dynamically create variables
Why you don't want to dynamically create variables
7
Why eval/exec is bad
Why eval/exec is bad
Iterator Pipelines
Iterator Pipelines
2
Why are non-mutating algorithms simpler to write in Python?
Why are non-mutating algorithms simpler to write in Python?
2
Sticking with Apple's Python 2.7
Sticking with Apple's Python 2.7
Blog Archive
About Me
About Me
Loading
Dynamic Views theme. Powered by Blogger. Report Abuse.