# -*- coding: utf-8 -*- """A simple variant of nondeterministic evaluation for Python. This is essentially a toy that has no more power than list comprehensions or nested for loops. An important feature of McCarthy's amb operator is its nonlocality - being able to jump back to a choice point, even after the dynamic extent of the function where it resides. (Sounds a lot like ``call/cc``; which is how ``amb`` is usually implemented in Scheme.) Instead, what we have here is essentially a tuple comprehension that: - Can have multiple body expressions (side effects welcome!), by simply listing them (and making sure each returns exactly one output). - Presents the source code in the same order as it actually runs. The implementation is based on the list monad. This is a hack with the bare minimum of components to make it work, complete with a semi-usable syntax. If you use `mcpyrate`: - For a friendlier syntax for this, see ``unpythonic.syntax.forall``. - If you need the full(-ish) power of ``call/cc``, see ``unpythonic.syntax.continuations`` (which can implement ``amb``). If you need more monads, look into the ``OSlash`` library. If you want to roll your own monads, the parts for this module come from: https://github.com/Technologicat/python-3-scicomp-intro/blob/master/examples/monads.py """ __all__ = ["forall", "choice", "insist", "deny"] from collections import namedtuple from collections.abc import Callable, Iterable from typing import Any from .arity import arity_includes, UnknownArity from .monads.list import List Choice = namedtuple("Choice", "k v") def choice(**binding: Iterable) -> Choice: """Make a nondeterministic choice. Example:: forall(choice(x=range(5)), lambda e: e.x) """ if len(binding) != 1: raise ValueError(f"Expected exactly one name=iterable pair, got {len(binding)} with values {binding}") for k, v in binding.items(): # just one but we don't know its name return Choice(k, v) # Hacky code generator, because Python has ``eval`` but no syntactic macros. # For a cleaner solution based on AST transformation with macros, # see unpythonic.syntax.forall. def forall(*lines: Choice | Callable) -> tuple: """Nondeterministically evaluate lines. This is essentially a bastardized variant of Haskell's do-notation, specialized for the list monad. Examples:: out = forall(choice(y=range(3)), choice(x=range(3)), lambda e: insist(e.x % 2 == 0), lambda e: (e.x, e.y)) assert out == ((0, 0), (2, 0), (0, 1), (2, 1), (0, 2), (2, 2)) # pythagorean triples pt = forall(choice(z=range(1, 21)), # hypotenuse choice(x=lambda e: range(1, e.z+1)), # shorter leg choice(y=lambda e: range(e.x, e.z+1)), # longer leg lambda e: insist(e.x*e.x + e.y*e.y == e.z*e.z), lambda e: (e.x, e.y, e.z)) assert tuple(sorted(pt)) == ((3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15), (12, 16, 20)) Notes: - All choices are evaluated, depth first, and set of results is returned as a tuple. - If a line returns an iterable, it is implicitly converted into a list monad containing the same items. - This applies also to the RHS of a ``choice``. - As the only exception, the last line describes one item of the return value; there the implicit conversion is skipped. This allows easily returning a tuple (as one result item) from the computation, as in the above pythagorean triples example. - If a line returns a single item, it is wrapped into a singleton list monad (a MonadicList containing that one item). - The final result (containing all the results) is converted from the list monad to tuple for output. - The values currently picked by the choices are bound to names in the environment. To access it, use a ``lambda e: ...`` like in ``unpythonic.letrec``. Quick vocabulary for haskellers: - ``forall(...)`` = ``do ...`` - ``choice(x=foo)`` = ``x <- foo``, where ``foo`` is an iterable - ``insist x`` = ``guard x`` - ``deny x`` = ``guard (not x)`` """ # Notation used by the monad implementation for the bind and sequence # operators, with any relevant whitespace. bind = " >> " seq = ".then" class Scope: def __init__(self) -> None: self.names: set[str] = set() def assign(self, k: str, v: Any) -> None: """Assign value ``v`` to name ``k`` in this ``Scope``.""" self.names.add(k) setattr(self, k, v) def close_over(self, freevars: set[str]) -> None: """Simulate lexical closure property for scope attrs. ``freevars``: set of names that "fall in" from a surrounding scope. """ names_to_clear = {k for k in self.names if k not in freevars} for k in names_to_clear: delattr(self, k) self.names = freevars.copy() # stuff used inside the eval e = Scope() def begin(*exprs: Any) -> Any: # args eagerly evaluated by Python """begin(e1, e2, ..., en): perform side effects e1, e2, ..., e[n-1], return the value of en.""" return exprs[-1] allcode = "" names = set() # names seen so far (working line by line, so textually!) bodys = [] begin_is_open = False for j, item in enumerate(lines): is_first = (j == 0) is_last = (j == len(lines) - 1) if isinstance(item, Choice): name, body = item else: name, body = None, item if name and not name.isidentifier(): raise ValueError(f"name must be valid identifier, got {repr(name)}") bodys.append(body) freevars = names.copy() # names from the surrounding scopes if name: names.add(name) # on the last line, don't auto-unpack iterables, # to allow easily returning a tuple from the computation unpack_flag = "True" if not is_last else "False" if callable(body): try: if not arity_includes(body, 1): raise TypeError("Arity mismatch; callable body must allow arity 1, to take in the environment.") except UnknownArity: # pragma: no cover pass code = f"monadify(bodys[{j}](e), {unpack_flag})" else: # doesn't need the environment code = f"monadify(bodys[{j}], {unpack_flag})" if begin_is_open: code += ")" begin_is_open = False # monadic-bind or sequence to the next item, leaving only the appropriate # names defined in the scope (so that we get proper lexical scoping # even though we use an imperative stateful object to implement it) if not is_last: if name: code += f"{bind}(lambda {name}:\nbegin(e.close_over({freevars}), e.assign('{name}', {name}), " begin_is_open = True else: if is_first: code += f"{bind}(lambda _:\nbegin(e.close_over(set()), " begin_is_open = True else: code += f"{seq}(\n" allcode += code allcode += ")" * (len(lines) - 1) # print(allcode) # DEBUG # The eval'd code doesn't close over the current lexical scope at the site # of the eval call, but runs in its own initially blank environment, # so provide the necessary names as its globals. mlst = eval(allcode, {"e": e, "bodys": bodys, "begin": begin, "monadify": monadify}) return tuple(mlst) # -------------------------------------------------------------------------------- # This low-level machinery is shared with the macro version, `unpythonic.syntax.forall`. def monadify(value: Any, unpack: bool = True) -> "MonadicList": """Pack ``value`` into a monadic list if it is not already. If ``unpack=True``, an iterable ``value`` is unpacked into the created monadic list instance; if ``False``, the whole iterable is packed as one item. """ if isinstance(value, MonadicList): return value elif unpack: try: return MonadicList.from_iterable(value) except TypeError: pass # fall through return MonadicList(value) # unit: varargs form — singleton list containing value # TODO(3.0.0): remove this deprecated alias. Users should import `List` # directly from `unpythonic.monads`. MonadicList = List insist = MonadicList.guard # retroactively require expr to be True def deny(v: Any) -> Any: """Opposite of `insist`. End a branch of the computation if `v` is truthy.""" return insist(not v) # TODO: export these or not? insist and deny already cover the interesting usage. # anything with one item (except nil), actual value is not used ok = ("ok",) # let the computation proceed (usually alternative to fail) fail = () # end a branch of the computation