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

It's been more than a decade since Typical Programmer Greg Jorgensen taught the word about Abject-Oriented Programming.

Much of what he said still applies, but other things have changed.
I haven't posted anything new in a couple years (partly because I attempted to move to a different blogging platform where I could write everything in markdown instead of HTML but got frustrated—which I may attempt again), but I've had a few private comments and emails on some of the old posts, so I
Looking before you leap

Python is a duck-typed language, and one where you usually trust EAFP ("Easier to Ask Forgiveness than Permission") over LBYL ("Look Before You Leap").
Background

Currently, CPython’s internal bytecode format stores instructions with no args as 1 byte, instructions with small args as 3 bytes, and instructions with large args as 6 bytes (actually, a 3-byte EXTENDED_ARG followed by a 3-byte real instruction).
If you want to skip all the tl;dr and cut to the chase, jump to Concrete Proposal.
Many people, when they first discover the heapq module, have two questions:

Why does it define a bunch of functions instead of a container type? Why don't those functions take a key or reverse parameter, like all the other sorting-related stuff in Python? Why not a type?

At the abstract level, it'
Currently, in CPython, if you want to process bytecode, either in C or in Python, it’s pretty complicated.

The built-in peephole optimizer has to do extra work fixing up jump targets and the line-number table, and just punts on many cases because they’re too hard to deal with.
One common "advanced question" on places like StackOverflow and python-list is "how do I dynamically create a function/method/class/whatever"? The standard answer is: first, some caveats about why you probably don't want to do that, and then an explanation of the various ways to do it when you reall
A few years ago, Cesare di Mauro created a project called WPython, a fork of CPython 2.6.4 that “brings many optimizations and refactorings”. The starting point of the project was replacing the bytecode with “wordcode”. However, there were a number of other changes on top of it.
Many languages have a for-each loop.
When the first betas for Swift came out, I was impressed by their collection design. In particular, the way it allows them to write map-style functions that are lazy (like Python 3), but still as full-featured as possible.
In a previous post, I explained in detail how lookup works in Python.
The documentation does a great job explaining how things normally get looked up, and how you can hook them.

But to understand how the hooking works, you need to go under the covers to see how that normal lookup actually happens.

When I say "Python" below, I'm mostly talking about CPython 3.5.
In Python (I'm mostly talking about CPython here, but other implementations do similar things), when you write the following:

def spam(x): return x+1 spam(3) What happens?

Really, it's not that complicated, but there's no documentation anywhere that puts it all together.
I've seen a number of people ask why, if you can have arbitrary-sized integers that do everything exactly, you can't do the same thing with floats, avoiding all the rounding problems that they keep running into.
In a recent thread on python-ideas, Stephan Sahm suggested, in effect, changing the method resolution order (MRO) from C3-linearization to a simple depth-first search a la old-school Python or C++.
Note: This post doesn't talk about Python that much, except as a point of comparison for JavaScript.

Most object-oriented languages out there, including Python, are class-based. But JavaScript is instead prototype-based.
About a year and a half ago, I wrote a blog post on the idea of adding pattern matching to Python.

I finally got around to playing with Scala semi-seriously, and I realized that they pretty much solved the same problem, in a pretty similar way to my straw man proposal, and it works great.
About a year ago, Jules Jacobs wrote a series (part 1 and part 2, with part 3 still forthcoming) on the best collections library design.
In three separate discussions on the Python mailing lists this month, people have objected to some design because it leaks something into the enclosing scope. But "leaks into the enclosing scope" isn't a real problem.
There's a lot of confusion about what the various kinds of things you can iterate over in Python. I'll attempt to collect definitions for all of the relevant terms, and provide examples, here, so I don't have to go over the same discussions in the same circles every time.
Python has a whole hierarchy of collection-related abstract types, described in the collections.abc module in the standard library. But there are two key, prototypical kinds. Iterators are one-shot, used for a single forward traversal, and usually lazy, generating each value on the fly as requested.
There are a lot of novice questions on optimizing NumPy code on StackOverflow, that make a lot of the same mistakes. I'll try to cover them all here.

What does NumPy speed up?

Let's look at some Python code that does some computation element-wise on two lists of lists.
When asyncio was first proposed, many people (not so much on python-ideas, where Guido first suggested it, but on external blogs) had the same reaction: Doing the core reactor loop in Python is going to be way too slow. Something based on libev, like gevent, is inherently going to be much faster.
Let's say you have a good idea for a change to Python.
There are hundreds of questions on StackOverflow that all ask variations of the same thing. Paraphrasing:

lst is a list of strings and numbers. I want to convert the numbers to int but leave the strings alone.
In Haskell, you can section infix operators. This is a simple form of partial evaluation. Using Python syntax, the following are equivalent:

(2*) lambda x: 2*x (*2) lambda x: x*2 (*) lambda x, y: x*y So, can we do the same in Python?

Grammar

The first form, (2*), is unambiguous.
Many people—especially people coming from Java—think that using try/except is "inelegant", or "inefficient". Or, slightly less meaninglessly, they think that "exceptions should only be for errors, not for normal flow control".

These people are not going to be happy with Python.
If you look at Python tutorials and sample code, proposals for new language features, blogs like this one, talks at PyCon, etc., you'll see spam, eggs, gouda, etc. all over the place.
Most control structures in most most programming languages, including Python, are subordinating conjunctions, like "if", "while", and "except", although "with" is a preposition, and "for" is a preposition used strangely (although not as strangely as in C…).
There are two ways that some Python programmers overuse lambda. Doing this almost always mkes your code less readable, and for no corresponding benefit.
Some languages have a very strong idiomatic style—in Python, Haskell, or Swift, the same code by two different programmers is likely to look a lot more similar than in Perl, Lisp, or C++.

There's an advantage to this—and, in particular, an advantage to you sticking to those idioms.
Python doesn't have a way to clone generators.

At least for a lot of simple cases, however, it's pretty obvious what cloning them should do, and being able to do so would be handy. But for a lot of other cases, it's not at all obvious.
Every time someone has a good idea, they believe it should be in the stdlib. After all, it's useful to many people, and what's the harm? But of course there is a harm.
This confuses every Python developer the first time they see it—even if they're pretty experienced by the time they see it:

>>> t = ([], []) >>> t[0] += [1] --------------------------------------------------------------------------- TypeError Traceback (most recent call last) <stdin> in <module>()
Blog Archive
About Me
About Me
Loading
Dynamic Views theme. Powered by Blogger. Report Abuse.