I will do the same!

Great idea! I'll make sure to try that as well

@leycec

Python 3.12.4 (main, Jun  6 2024, 18:26:44) [Clang 15.0.0 (clang-1500.1.0.2.5)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import beartype
>>> beartype.__version__
'0.19.0rc0'
>>> from beartype.door import infer_hint
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ImportError: cannot import name 'infer_hint' from 'beartype.door' (/usr/local/lib/python3.12/site-packages/beartype/door/__init__.py)
>>> quit()

Oh, I just reread the whole thing, my bad.

...heh. Yup. Still a work-in-progress, technically. I could ship it as is under the proviso that it only "works" if you squint at it, but that wouldn't be so great. Instead, I'll hammer out a few implementation details over the coming days like:

• Dictionary inference (e.g., inferring type hints like dict[str: int] from dictionaries like {'Dis iz': 0x31337}).
• Literal inference (e.g., inferring type hints like typing.Literal["MuhString!"] from string literals like "MuhString!").

Much to do – yet no time in which to do. Still the spirit is strong. Arise, spirit! Don't fail us now. 👻

This is genuinely very cool, and I can definitely see myself having use for it!

Adding a way to get | instead of typing.Union with a flag would be nice

Because I live in an isolated air-gapped man-cave in the woods, this OceanGate meme had me rolling back and forth. It's so true!

Then I googled this "CrowdStrike" thing. Now, I'm wildly rolling my eyes back and forth after learning that a closed-source prophylactic against Windows-based cyberattack rootkits accidentally mutated into (...waitforit) a Windows-based cyberattack rootkit. Wikipedia's "2024 CrowdStrike incident" article is legitimately ridiculous and the clearest signal that closed-source is insecure by design. Microsoft, I 😻 many things you do – but it's clear that it's time for a family intervention:

On 19 July 2024, American cybersecurity company CrowdStrike distributed a faulty update to its security software that caused widespread problems with computers running Microsoft Windows. As a result, roughly 8.5 million systems crashed and were unable to properly restart[1] in what has been called the largest outage in the history of information technology[2] and "historic in scale".

The outage disrupted daily life, businesses, and governments around the world. Many industries were affected—airlines, airports, banks, hotels, hospitals, manufacturing, stock markets, broadcasting, gas stations, retail stores, and more—as were governmental services, such as emergency services and websites.[4][5] The worldwide financial damage has been estimated to be at least US$10 billion.

As this process must be done locally on each individual machine, it was "expected to take days" for affected businesses to restore all systems.[33] Further, technical staff will have to reboot the affected computers individually with manual intervention on each system, which could be a "monumental task".

On devices with Windows' BitLocker disk encryption enabled, as corporations often do to increase security, fixing the problem was exacerbated because a recovery key could be required that was stored on a server that itself had crashed.

Some Microsoft Azure customers discovered that they could fix the problem by rebooting affected virtual machines up to 15 times, ideally while connected to Ethernet.

Windows is destroying even hospitals now, huh? Encrypted recovery keys only stored on boot-bluescreened servers, huh? Rebooting boot-bluescreened servers 15 times while incanting a magical chant against gremlins that resemble bald men living in the woods, huh?

So. This is what our sordid timeline has finally come to. 😮‍💨

Thanks for the read and the ping!

I have a weird question now. If you succeded (and apparently you did) in implementing both something that tells you the type AND some import hook that adds a decorator to every thing in a package, then can it be imagined to created a hook that adds a decorator to all functions and declaration and instead of typechecking, just records all the type that go through the decorators during normal functionning (meaning the user just uses the script as usual) then infer each type and patch the type hints to all the code?

That seems like a terrible idea in a lot of cases but a great idea in some, i'm thinking specifically that it would make scientists (ie non professional coders) have cleaner code. And that would ease my life (i'm a medical student/researcher)

Or maybe I'm a dumbdumb and it already exists?

Thanks for beartype anyway, i'm doing way cleaner code thanks to you :)

The Eagle has landed!!

That's really amazing dude! Now it's time for you to take a long deserved break and play those video games (do you play D&D?).

No but seriously this is insanity. What on God's green earth is this insanity?
What is its...dare I ask... time complexity?

Dear heavens I love this so much. Doesn't this pretty much completely re-write the book as far as pattern matching, dispatch, etc? We have an "infer_type" now... so we can dynamically dispatch on runtime, deeply nested types without the insane is_bearable hacks I've been using (which iirc is how Plum works rn too?)

I have no clue how this devilry works, and honestly I... I desperately want to 0_o.

You realize the closest thing to this kind of tensor type-checking (albeit not at "compile time" the way they do it) is... what, this experimental hmatrix api?? And maybe some dynamically typed languages like idris2 and Agda and stuff... but dang.

Okay this one is seeming pretty stable for my use-case so far!

Been thinking about your insights all week, @wesselb. On the cusp of @beartype 0.19.0rc2, we give thanks to @wesselb and Plum for all the mind food they have given us. We eatin' good tonight, fam.

This directed graph contains no cycles, so a topological ordering exists and can be found in O(|E| + |V|) = O(|V|^2) time.

Ho, ho, ho. Because I have thought about this for a week while digging garden ditches covered in filth, I'm pretty sure (but not sure) that this might be considerably faster than worst-case quadratic complexity. Hear me out before you gut me.

By the graph construction you've given, each node n has out-degree out(n) bounded by 0 <= |out(n)| <= 1. That is, each node has at most one edge directed out of itself. Moreover, at least one node n_leaf must be a leaf node (i.e., have out-degree that is exactly |out(m_leaf)| == 0). This case is illustrated by a chain of k methods, each of which has a signature that is more specific than its predecessor: e.g.,

@dispatch
def hell_is(a_function: numbers.Number, in_python: collections.abc.Container) -> None: ...
@dispatch
def hell_is(a_function: numbers.Complex, in_python: collections.abc.Sequence) -> None: ...
@dispatch
def hell_is(a_function: numbers.Real, in_python: collections.abc.MutableSequence) -> None: ...
@dispatch
def hell_is(a_function: numbers.Rational, in_python: list) -> None: ...

...and so on. Hell is deeper than even Doom Guy knew. The above gives a linear chain of connected nodes resembling:

n1 -> n2 -> n3 -> n4

That's the "maximally connected" graph produced by this sort of graph construction. ^{i think. no quotes please. oh noes! somebody is already quoting and laughing at me on MathOverflow!!} From this, we can infer that in fact the maximum number of edges is given by max(|E|) = |V| - 1. This then trivially yields:

O(|E| + |V|) = O(|V| - 1 + |V|) = O(2|V| - 1) = O(|V|)

So, only worst-case linear complexity? Maybe? In other words, topologically sorting this sort of graph construction should actually be super-fast... which is good, because Plum will be doing it a lot. Like, seriously, seriously a lot. Specifically:

1. For the first @dispatch-decorated variant, Plum obviously doesn't sort anything. Just cache something in a thread-safe data structure somewhere and go running free.
2. For the second @dispatch-decorated variant, Plum again doesn't sort anything. Sure, Plum could – or Plum could just optimize this common case by manually sorting. Only two @dispatch-decorated callables are involved at this point. So manually sorting is trivial. Take that, vile topological sort.
3. For every @dispatch-decorated variant thereafter, however, Plum now needs to topologically sort the newest @dispatch-decorated variant into the previously sorted thread-safe data structure. If I haven't just vaped a giant bowl of CBD, each such topological sort should be O(|V|). But it might be even faster. Since you're only inserting a single new unsorted node into a previously sorted graph, there might be clever ways of doing this that exceed even linear complexity. Who caaaaaaaaares? Probably nobody. Yet still @leycec is typing.

This implies that the total worst-case time complexity over k total number of @dispatch-decorated variants for a single callable is:

• For k == 1 and k == 2, O(1). 🥳
• For k >= 3, O(k |V|). 😞

I'm down with some O(k |V|) up in here. Beat that, multipledispatch!

Actually, There Might Be a Way of Beating That

If you can lazily defer the creation of your Plum-dispatched callable until the first call to that callable, then you only need to perform a single topological sort rather than k topological sorts. Maybe Plum already does this? Maybe Plum is the miracle we've all been searching for. If so, you're straight back to O(|V|). 🥳

Which leads me to... multipledispatch. Woah! What an open-source find there. I didn't know Plum had reasonable competition in this space. Of course, multipledispatch is no longer actively maintained and has a billion open issues and PRs. Basically, Plum still has no reasonable competition in this space. Yes! 😸

Still, that topological sort is multipledispatch is fascinating. It's leveraging the obsolete collections.OrderedDict class, which is no longer required. There are other micro-optimizations that would yield joy, too. Rather than re-looking up the S.popitem() and L.append() methods each iteration, you instead do something resembling:

    S_popitem = S.popitem
    L_append = L.append

    while S:
        n, _ = S_popitem()
        L_append(n)

Definitely worth doing, considering how frequently Plum will be topologically sorting. In fact, you could probably even globally cache the L list and just clear that list before reusing that list during each topological sort.

Blegh! Boring stuff intensifies.

I Must Confess That I Am Dumb

Specifically:

you really need to be sure that is_bearable(x, t) == is_subhint(infer_type(x), t)

Do you, though? Given the above multiple-dispatch approach based only on infer_type() and is_bearable(), the is_subhint() function is only called in the initial topological sort to order the key-value pairs of your dispatch dictionary in descending order of specificity. In that case, does the is_bearable(x, t) == is_subhint(infer_type(x), t) constraint still need to hold for Plum?

Let's consider that worst-case user-defined ListOfThreeItems container. If the metaclass of that container defines the __instancecheck__() dunder method, it should probably also define the __subclasscheck__() dunder method. In that case, ListOfThreeItems should declare itself to be a "virtual" subclass of list such that issubclass(ListOfThreeItems, list) == True. Given that, is_subhint(ListOfThreeItems[str], list[str]) == True should also be the case. Maybe? Is is_subhint() dumber than we all would hope? Probably.

Kinda feels like I'm missing something. I get that feeling a lot, though. 😮‍💨

Thanks so much for the exciting foray into Graph Theoretic Land™! Now, let's excrete @beartype 0.19.0rc2 while I still have a pulse.

Hear me out before you gut me.

Ahhh, yes, of course you're right. Down the graph-theoretic rabbit hole we go!!

n1 -> n2 -> n3 -> n4

Given just n1, n2, n3, and n4, would you be able to efficiently (1) detect whether they form a chain or not and (2) organise them into that chain?

The general DAG that you can form has an edge from ni to nj if the one is a subsignature of the other, which in the above example would also imply edges from n1 to n3 and n4 and an edge from n2 to n4. I guess you could come up with some edge-elimination algorithm to find the chain. This, however, seems hard to do in less than O(|E|^2) time, because the starting graph already has O(|E|^2) edges! Hence, you'll need to do something more clever.

If we know that all nodes are comparable, I guess this is exactly just the standard sorting problem, which we can do in O(|V| log |V|) time. Where it becomes complicated is that not all nodes might be comparable, even in the one-argument case.

(Where it becomes even more complicated is variable arguments. I think that two signatures with variable arguments cannot be compared in isolation, but it's been a while since I've been down this rabbit hole.)

All in all, I guess the question is this: given a collection of nodes, can you efficiently find a list of O(|V|) edges such that the resulting topological sorting would also be valid for the graph with O(|V|^2) edges?

If you can lazily defer the creation of your Plum-dispatched callable until the first call to that callable, then you only need to perform a single topological sort rather than k topological sorts. Maybe Plum already does this?

Plum certainly does this. :)

There are other micro-optimizations that would yield joy, too.

Haha, give anything to @leycec and he shall find optimisations!!

Definitely worth doing, considering how frequently Plum will be topologically sorting.

Plum currently uses a silly and inefficient algorithm which runs in quadratically in the number of methods that match the given arguments. This cost currently has to be paid at every function call, but caching can effectively reduce this to the first call only (especially with infer_hint!).

We should probably really change this algorithm to an approach based on topological sorting. Figuring this out is going to list of high priority TODOs!

Do you, though?

Hmm, my reasoning is the following.

Suppose that you have some algorithm (efficient or inefficient) to find the appropriate method for a given argument x, and suppose that this algorithm uses only uses x through is_bearable(x, t) for various t. Assume that is_bearable(x, t) == is_subhint(infer_type(x), t) for all t. Then, if infer_type(x) is the same, the output of the algorithm to choose the method must be the same. Why? If infer_type(x) is the same, then is_bearable(x, t) == is_subhint(infer_type(x), t) for all t means that is_bearable(x, t) for all t is the same, which is the only way the algorithm depends on x. Therefore, infer_type(x) "determines" the output of the method resolution algorithm, meaning that it is valid to cache the output of the algorithm based on infer_hint(x).

Admittedly, this argues that is_bearable(x, t) == is_subhint(infer_type(x), t) for all t is sufficient, not necessary.

Ho, ho, ho. I see that one of us is a skilled academic and one of us not so much. I also see that Plum is in ingenious hands. I mean, I always knew Plum was in ingenious hands – but now I really see that.

Please codify everything you just invented into an introductory paper on Plum. If Plum successfully mutates into a topological sorting engine fuelled by a perfidious combination of infer_hint(), is_bearable(), and/or is_subhint(), Plum will then probably exhibit best-in-class amortized worst-case time complexity for the "dynamic JIT multiple dispatch at runtime" decision problem across relevant languages. Scooooooore! ⚽ 🥅

I will read that paper. Then I will read that paper again. Until then, I accept that you're right about everything. My frankly uneducated intuition of an O(|V|) topological sort assumed something painful yet clever that I failed to document or discuss. Something like:

While topologically sorting, we prune excess edges between nodes. Any edge e1 between two nodes n1 and n2 is excessive if there exists a longer path e2, ..., ek transitively connecting node n1 to n2.

Pruning excess edges preserves the DAG chain invariant, which I just made up. The "DAG chain invariant" states that "If there exists a path from node n1 to n2, there exists one and only one such path and that path is the longest possible path." There's probably a graph-theoretic term for this. Path-uniqueness? Path-singleness? Path-determinacy? No idea. This is why I am not Erdos.

Can you prune excess edges efficiently, though? Probably not... without some sort of super-cool data structure, anyway! The space complexity would probably blossom out-of-control, but you might be able to cache a nested dictionary structure like:

super_cool_data_structure = {
    n1: {
         n2: (e1, e2, e3,),
    },
    n2: {
         n1: (e1, e2, e3,),
    },
}

Given any two nodes n1 and n2, super_cool_data_structure then gives you the longest path between n1 and n2. You avoid adding any edges to the graph that would create a shorter path between n1 and n2. If you find an even longer path, you panic and hit <Ctrl-C>. The algorithm has blown up. 🤣

So much fun! Unrelatedly, let's push this @beartype 0.19.0 thing out. Python has suffered for too long under @beartype 0.18.5. Tonight, we QA Python... for reals.

First of all, huge congrats with the 0.19.0 release! That's huge!! So many exciting new features. Thank you for your incredible work, @leycec! :)

If Plum successfully mutates into a topological sorting engine

Alright, let's actually take this seriously! There is one issue I've not been able to figure out. It's pretty simple. Consider the signatures (int, *A) and (int, *B), where A and B are unrelated classes. If there is only one argument given, the signatures are considered equal. If there is more than one argument given, the signatures should be considered incomparable. Hence, we cannot define a partial order that compares (int, *A) and (int, *B) without violating at least one of the two cases.

To be able to do a topological sorting, I believe we do really need a partial order (to define the graph which we are going to sort). (Note the correspondence between partial orders and DAGs.) However, by the above, we cannot define a partial order which is right for every number of arguments! Any ideas on how to resolve this? I suppose one possibility would be to do a separate topological sorting for every possible number of arguments.

So much fun!

Very interesting. I'm going to think about whether there is a way to do the topological sorting in less than O(|V|^2) time. It feels like there must be.

@leycec, after rereading, the issue which I outline above does not fully make sense. Please ignore it! I'll let the message stand as a future reminder for myself. Let me actually think about this more carefully and then get back to you.

Yeah you can 100% listen to me and my niche use-cases for beartype :P

Ho, ho. Manual strongly-overtuned C-based Python argument parsing and unpacking, huh? Indeed, this is in our wheelhouse. Well, sorta in our wheelhouse.

@beartype is intentionally pure-Python. This means that we can't leverage most of the super-amazing insights of this article, which avoids high-level pure-Python in favour of low-level C extensions. Personally, my optimistic opinion is...

Pure-Python Is the Future of Python

Authoring Python in anything other than Python will make incrementally less sense with each passing year. With the advent of CPython 3.13, we now have an official JIT and official GIL-free multithreading in pure-Python. The official JIT currently yields efficiency increases of ~5% on average workloads without breaking backward compatibility, which is more than PyPy ever accomplished. With each new stable CPython iteration, JIT efficiency and stability will presumably improve; likewise for GIL-free multithreading. Python should eventually enjoy performance on par with Chrome's "crazy-fast" V8 JavaScript engine.

Given what's on the immediate horizon, does implementing Python in lower-level languages that are significantly more cumbersome, failure-prone, undebuggable, unmaintainable, and type-checking-free like C, C++, or Fortran make sense for new projects? Probably not – unless you're doing something sufficiently low-level that does genuinely require that hellish systems-level approach (e.g., Single Instruction/Multiple Data (SIMD)). Even Python-adjacent languages like Cython and PyPy don't particularly make sense for new projects anymore. Just use CPython ≥ 3.13 itself with --disable-gil + --enable-experimental-jit and you'll now get everything "for free" that you used to have to shed copious buckets of blood and salty tears for.

The only non-Python language that makes sense for new projects is Rust. That's it, really. Just Rust. Unlike every other systems-level language, Rust isn't hellish. That's nice. Even then, though, it's kinda hard to see the "value add" for most projects. If you think you need to leave the walled garden of pure-Python for more gruelling pastures, it's probably best to think again. You're already in the panic zone.

Pydantic is an apropos example. Did Pydantic need to reimplement its core as a Rust extension? Defly not. The "value add" just isn't there. Instead, @beartype shows the way. There is a subset of Python that is crazy-fast. When you need speed, just confine yourself to that subset. I dub thee Bearython, the Subset of Python That Is Fast:

• Avoid string munging. String munging is slower than a vicious game of late-night Canadian curling between elderly retirees. Munge strings only when you must. Even then, don't munge strings.
• Avoid exception handling. Raising exceptions is fine. Even the try: portion of exception handling is reasonably fast. But the except: portion? Yeah. That's slower than our elderly Maine Coon cat chasing after a stray piece of kibble rolling down the hill. Avoid doing anything in except: blocks.
• Avoid Easier To Ask for Permission than Forgiveness (EAFP). For exactly the prior reason, EAFP-style code suuuuuuuuucks. Nothing destroys performance more than EAFP.
• Prefer while loops to for loops. Internally, Python implements for loops by raising StopIteration exceptions on loop termination. Frankly, this is insane. As mentioned, exception handling is slow. But for loops are implemented in terms of exception handling, which means for loops are slow, too. Woops.
• Avoid object-oriented programming (OOP). If something can be done with a simple functional approach, prefer the simple functional approach. Almost everything be done with a simple functional approach. When you use classes, prefer simple dataclasses that just encapsulate related objects that you pass around to standard functions. Avoid methods, overriding, abstract base classes, and method-resolution order (MRO). Really, just avoid the whole object-oriented works. It's slower than the wood peeling off the side of our dilapidated cabin in the woods.

Uhh... Wasn't I Supposed to Release @beartype 0.19.0rc2 Tonight!?

Woops. 😜

Thanks a lot, I've always wondered what were your tips to make python so far. If I may, I think those tips deserve a prominent place in the docs.

You're most welcome. I adore this sort of madness. Optimizing Python may be painting lipstick on a wallowing pig, but it's an adorable pot-bellied pig that I've come to love.

I think those tips deserve a prominent place in the docs.

In other words: "Let's spread the madness." I agree. Sounds great. I've opened up a new issue tracking this docos request. The brain worm of Premature pythOn Optimization (POO) shall grow! 🪱 -> 🧠

Thanks a lot I read it and it's awesome. And this reply from you must be the sortest I've ever read from you :-)

(Btw when I said prominent I really meant an actual doc page with links to it in the main doc page. Like it's really cool)

I really meant an actual doc page with links to it in the main doc page.

Totally. You're too kind. That's why I've opened up a new issue tracking your superb docos request. Because I'll inevitably forget that somebody who is nice wanted this, I remind myself with issues that inevitably stay open for literally years until the userbase assembles burning torches and storms my castle. 🕯️ 🏰 🧛

Please ping me on that issue if I haven't done this in literally years. This is the likeliest outcome.