Prolog does sunshine like this, no? You give it rules and then make a statement with a blank in it and it'll fill in the blank given the rules you've described.
The cool stuff here is the simplicity of the interface to it and its integration thanks to high order functional constructs (decorator).
My implementation of AMB is purposefully small (70 LOC, not counting docstrings and tests and system definition), so that it can fit on a page of paper and be easily understood.
Making this further relevant is that perhaps the most well known example of monadic programming of lists is: Python's list comprehensions. Which makes a bit surprised to see that not more explored/exploited in this library.
Interesting nonetheless!
This authors use of 'non-determinsistic' doesn't match the meaning of a Nondeterministic Turing machine used to define the complexity class NP.
There are many types of non-deterministic Turing machines, like a probabilistic Turing machine which flips a coin at each step.
But the 'maximally lucky guesser' or 'run all possibilities in one step' version of NTM's that defines NP is physically unrealizable.
The code isn't magically solving NP vs P but it does simulate non deterministic run through a potentially exponential exploration.
Also, surely NTMs are only physically unrealizable if P!=NP, and so whether or not NTMs could exist is an open question.
There are pretty formal contexts in which it also means things like that! It's not about formalism, it's just about context.
In the context of a deterministic vs nondeterministic finite automata, a DFA has a linear computation path from the root to an accept/reject state and a NFA branches on epsilon transitions, continuing each potential computation (the "guesses") in so called "parallel universes" until one branch hits an accept state.
This definition follows with Introduction to the Theory of Computation 3rd edition by Sipser (would recommend)
