Intro to Parsy

I need to explain a few things about Parsy.

In Parsy, you build up Parser objects via a set of primitives and combinators. Each Parser object has a parse method that accepts strings [1] and returns some object – which might be a string for your lowest building blocks, but quickly you build more complex parsers that return different types of objects. A lot of code is written in “fluent” style where you chain methods together.

Here are some basics:

The primitive string just matches and returns the input:

import parsy as P

hello = P.string("hello")
assert hello.parse("hello") == "hello"

But we can change the result to some other type of object:

true_parser = P.string("true").result(True)
assert true_parser.parse("true") == True

We can map the parse result using a callable. This time I’m starting with a regex primitive, which returns strings, but converting to ints:

int_parser = P.regex(r"-?\d+").map(int)
assert int_parser.parse("123") == 123

We can discard things we don’t care about in a number of ways, such as with these “pointy” operators that point to the important bit:

whitespace = P.regex(r"\s*")
assert (whitespace >> int_parser << whitespace).parse(" 123    ") == 123

We can have a sequence of items, here with some separator we don’t care about collecting:

three_ints = P.seq(
  int_parser << P.string("-"),
  int_parser << P.string("-"),
  int_parser
)
assert three_ints.parse("123-45-67") == [123, 45, 67]

If we want something better than a list to store different components in (usually we do), we can use a keyword argument form of seq to give names for the components and collect them in a dict instead of a list, and instead of .map we can do .combine_dict to convert the result into some other object:

from dataclasses import dataclass

@dataclass
class Date:
    year: int
    month: int
    day: int

date_parser = P.seq(
  year=P.regex(r"\d{4}").map(int) << P.string("-"),
  month=P.regex(r"\d{2}").map(int) << P.string("-"),
  day=P.regex(r"\d{2}").map(int)
).combine_dict(Date)

assert date_parser.parse("2022-11-19") == Date(year=2022, month=11, day=19)

We can have alternatives using the | operator:

bool_parser = P.string("true").result(True) | P.string("false").result(False)
assert bool_parser.parse("false") == False

That’s enough to understand the rest of this post, let’s have a look at my 4 different approaches to improving the static type checking story for Parsy.

Simple types

The most obvious thing to do is to add Parser as the return value for a bunch of methods and operators, and other type hints wherever we can for the input arguments. For example, .map is:

def map(self, map_function: Callable) -> Parser:
   ...

What type of object does the parse method return? We don’t know, so we have to do:

def parse(self, input: str) -> Any:
    ...

And this is our first hint that the static type checking isn’t very useful. For example, this faulty code will now type check:

x: str = int_parser.parse("123")

We can see the return value is not going to be the right type, but our static type checker sees the Any and allows it.

The type checker is also not catching TypeError exceptions for .map() that it definitely ought to be able to. For example, suppose we have this faulty parser which is going to attempt to construct a timedelta from strings like "7 days ago":

from datetime import timedelta
days_ago_parser = (P.regex(r"\d+") << P.string(" days ago")).map(timedelta)

This is going to fail every time with:

TypeError: unsupported type for timedelta days component: str

That’s because we forgot a .map(int) after the P.regex parser.

This kind of type error is caught for you by mypy and pyright if you try to pass a string to the timedelta constructor, but here, we’ve got no constraints on the callable that would enable the type checker to pick it up. When we put a bare Callable in a signature, as we did above for the map method, we are really writing Callable[..., Any], so all proper type checking effectively gets disabled.

If you want static type checking, this is not what you expect or want! It’s especially important for Parsy, because almost all the mistakes you are likely to make will be of this nature. Most Parsy code consists of parsers defined at a module level, which means that as soon as you import the module, you’ll know whether you have attempted to use combinator methods that don’t exist, for example, so there is little usefulness in a type checker being able to tell you this. What you want to know is whether you are going to get TypeError or similar when you call the parse method at runtime.

Can we achieve that?

Generics

The answer is to make the Parser type aware of what kind of object it is going to output. This can be achieved by parameterising the type of Parser with a generic type, and is the second main approach.

Very often generics are used for homogeneous containers, to capture the type of the object they contain. Here, we don’t have a container as such. We are instead capturing the type of the object that the parser instance is going to produce when you call .parse() (assuming it succeeds, I’m ignoring all failure cases).

Some of the key type signatures in our Parser code now look like this (lots of details elided):

from typing import TypeVar, Generic

OUT = TypeVar("OUT")
OUT1 = TypeVar("OUT1")
OUT2 = TypeVar("OUT2")


@dataclass
class Result(Generic[OUT]):
    value: OUT
    ...


class Parser(Generic[OUT]):

    def parse(self, stream: str) -> OUT:
        ...

    def map(self: Parser[OUT1], map_function: Callable[[OUT1], OUT2]) -> Parser[OUT2]:
        ...

The main point is that we are capturing the type of output using a type parameter that our static type checker can track, which means that we can indeed catch the type errors that were ignored by the previous approach. I got this to work, and you can see my results in this PR (not merged).

The reason it isn’t merged is that this approach breaks down as soon as you have things like *args or **kwargs where the arguments need to be of different types. We have exactly that, multiple times, once you care about generics. For example, the seq combinator takes sequence of parsers as input, and runs them in order, collecting their results. All of them are Parser instances, so that would work fine with the previous approach, but they could all have different output types. There is no way to specify a type signature for this, as well as for alt, combine and combine_dict.

The best you can do is specify that they return Parser[Any]. This means you are downgrading to no type checking. This problem is going to apply to all but the most trivial cases – it’s difficult to come up with many real world examples where you don’t need sequencing.

Some people would say “well, it works sometimes, so it is better than nothing”. The problem is that you when you start writing your parser, you may well really benefit from the type checking and start to lean on it. Then, as soon as you get beyond the level of your simple (single part) objects and are creating parsers for more complex (multiple part) objects in your language, the type checking silently disappears. Or, if you have strictness turned up high, your type checker will complain about the introduction of Any, but you won’t be able to do anything about it.

Both of these are really bad developer UX in my opinion. If the type checker is going to give up and go home at 2pm on the second day of work, it would be better for it not to show up, which would push developers to lean on other, more reliable methods, like writing tests.

Typed Parsy fork

So we come to my third option, which builds on the second. Can we redesign Parsy so that it doesn’t have any Any? This would be a backwards incompatible fork that removes any API that is impossible to fully type, and attempts to provide some good enough replacements.

This was my most ambitious foray into static type checking in Python, and below are my notes from two perspectives – first implementation, which is important for any potential future contributors and maintainers, and secondly, usage, for the people who actually might want to use this fork.

class Operator(enum.Enum):
    EQ = "="
    LT = "<"
    GT = ">"
    LTE = "<="
    GTE = ">="

@dataclass
class Comparison:
    left: ColumnExpression
    operator: Operator
    right: ColumnExpression

# dataclass for Select etc

comparison = P.seq(
    left=column_expr << padding,
    operator=P.from_enum(Operator),
    right=padding >> column_expr,
).combine_dict(Comparison)

SELECT = P.string("SELECT")
FROM = P.string("FROM")
WHERE = P.string("WHERE")

select = P.seq(
    _select=SELECT + space,
    columns=column_expr.sep_by(padding + P.string(",") + padding, min=1),
    _from=space + FROM + space,
    table=table,
    where=(space >> WHERE >> space >> comparison).optional(),
    _end=padding + P.string(";"),
).combine_dict(Select)

comparison = (
    (column_expr << padding) & P.from_enum(Operator) & (padding >> column_expr)
).map(lambda t: Comparison(left=t[0][0], operator=t[0][1], right=t[1]))

SELECT = string("SELECT")
FROM = string("FROM")
WHERE = string("WHERE")

select = (
    (
        (SELECT + space)
        >> (column_expr.sep_by(padding + string(",") + padding, min=1))
        << (space + FROM + space)
    )
    & table
    & ((space >> WHERE >> space >> comparison).optional() << (padding + string(";")))
).map(lambda t: Select(columns=t[0][0], table=t[0][1], where=t[1]))

(map_fn: (tuple[tuple[list[Field | String | Number], Table], Comparison | None]) -> OUT2@map) -> Parser[OUT2@map]",

Argument 1 to "map" of "Parser" has incompatible type
"Callable[[List[List[T]]], List[T]]"; expected
"Callable[[List[Tuple[Tuple[str, int], str]]], List[T]]"

Argument 1 to "map" of "Parser" has incompatible type
"Callable[[Tuple[List[List[Tuple[List[List[OUT]], List[OUT]]]],
List[Tuple[List[List[OUT]], List[OUT]]]]], List[List[Tuple[List[List[OUT]],
List[OUT]]]]]";
expected "Callable[[Tuple[List[List[Tuple[List[List[OUT]],
List[OUT]]]], List[Tuple[List[List[OUT]], List[OUT]]]]], List[OUT]]"

Types for documentation

At some point along the way, I noticed that for the original version of parsy, with no type hints at all, my language server (pyright) was able to correctly infer return types of all the methods that returned Parser instances. The types it was inferring were the same as I would have added in the very first section, simple Parser objects, and that meant it could reliably give help with chained method calls, which is pretty nice.

The biggest problems were that the docstrings weren’t helpful (in most cases missing), and that for many parameters it wasn’t entirely obvious what type of object you should be passing in.

So, using a small amount of effort, we could improve usability a lot. We can add those dosctrings, and add type hints that are about the same level of types that pyright was inferring anyway, just a bit more complete.

The one thing I don’t want to do is imply that these types bring Parsy code up to the level of being “type checked”, but there is a simple way I can do that – by not including a py.typed marker file to my package.

So, I’m back at the beginning, but with a different aim. Now, it’s not about helping automated static type checkers – without a py.typed marker in the module they basically ignore the types – it’s about improving usability for developers as they write. I’ve done this work in the master branch now, and will hopefully release it soon.

There is another interesting advantage to this: because I’ve given up on static type checks and I’m not using static type checking for internal use in Parsy at all, I can be a bit looser with the type hints, allowing for greater readability. For example, I can annotate an optional string argument as arg: str = None, even though that’s not strictly compliant with PEP 484. In other places I can use slightly simplified type hints for the sake of having something that doesn’t make your eyes glaze over, even if it doesn’t show all the possibilities – such as saying that input types can be str | bytes | list, when technically I should be writing something much more abstract and complicated using Sequence.

Conclusion

In the end, type hints didn’t work out for use by a static type checker. But as clear and concise documentation for humans that pop up in a code editor, they worked well. Unless or until there are some big improvements in what it is possible to express with static types in Python, this seems to be the best solution for Parsy.

I learnt a lot about the limitations of typing in Python along the way, and hope you found this helpful too!

Links

• Discussion of this posts on Lobsters

Footnotes