maybe.py

#!/usr/bin/env python3

import functools
import inspect
import itertools

@functools.total_ordering
class Maybe:
    """Extension of the boolean logic.

    & (“*”), | (“+”):
      - commutative
      - associative
      - behave normally on 0, 1
      - 0 | x = x
      - 1 & x = x
      - M | x = {1 if x = 1, M otherwise}
      - M & x = {0 if x = 0, M otherwise}
      - ~(x & y) = ~x | ~y
      - ~(x | y) = ~x & ~y
      - (x & y) | c = (x | c) & (y & c)
      - (x | y) & c = (x & c) | (y & c)
    """
    MAYBE_TAG = -1

    def __init__(self, value):
        self.value = value

    def __or__(self, other):
        if not isinstance(other, Maybe):
            return NotImplemented

        if self.value == self.MAYBE_TAG:
            if other.value == 1:
                return Maybe(1)
            return Maybe(self.MAYBE_TAG)
        elif other.value == self.MAYBE_TAG:
            return other | self
        else:
            return Maybe(self.value | other.value)

    def __and__(self, other):
        if not isinstance(other, Maybe):
            return NotImplemented

        if self.value == self.MAYBE_TAG:
            if other.value == 0:
                return Maybe(0)
            return Maybe(self.MAYBE_TAG)
        elif other.value == self.MAYBE_TAG:
            return other & self
        else:
            return Maybe(self.value & other.value)

    def __invert__(self):
        if self.value == 0:
            return Maybe(1)
        elif self.value == 1:
            return Maybe(0)
        else:
            return Maybe(self.MAYBE_TAG)

    def __eq__(self, other):
        if not isinstance(other, Maybe):
            return NotImplemented
        return self.value == other.value

    def __lt__(self, other):
        if not isinstance(other, Maybe):
            return NotImplemented
        if self.value == 1:
            return False
        elif self.value == self.MAYBE_TAG:
            return other.value == 1
        else:
            return other.value in (0, self.MAYBE_TAG)

    def __str__(self):
        if self.value == 0:
            return '0'
        elif self.value == 1:
            return '1'
        elif self.value == self.MAYBE_TAG:
            return 'M'
        else:
            return 'INVALID'


class Printer:
    """A wrapper that prints operator expressions.
    """
    def __init__(self, value):
        self.value = str(value)

    def __str__(self):
        return self.value

    def __invert__(self):
        if len(self.value) == 1:
            return '~' + self.value
        else:
            return '~({})'.format(self.value)

    def __and__(self, other):
        if not isinstance(other, Printer):
            other = Printer(other)
        return Printer('({} & {})'.format(self.value, other.value))

    def __or__(self, other):
        if not isinstance(other, Printer):
            other = Printer(other)
        return Printer('({} | {})'.format(self.value, other.value))

    def __eq__(self, other):
        if not isinstance(other, Printer):
            other = Printer(other)
        return Printer('{} == {}'.format(self.value, other.value))

    def __ne__(self, other):
        if not isinstance(other, Printer):
            other = Printer(other)
        return Printer('{} != {}'.format(self.value, other.value))

    def __lt__(self, other):
        if not isinstance(other, Printer):
            other = Printer(other)
        return Printer('{} < {}'.format(self.value, other.value))

    def __le__(self, other):
        if not isinstance(other, Printer):
            other = Printer(other)
        return Printer('{} <= {}'.format(self.value, other.value))

    def __gt__(self, other):
        if not isinstance(other, Printer):
            other = Printer(other)
        return Printer('{} > {}'.format(self.value, other.value))

    def __ge__(self, other):
        if not isinstance(other, Printer):
            other = Printer(other)
        return Printer('{} >= {}'.format(self.value, other.value))



_1 = Maybe(1)
_0 = Maybe(0)
_M = Maybe(Maybe.MAYBE_TAG)


def num_args(func):
    """Given a function, returns its number of positional arguments.
    """
    sig = inspect.signature(func)
    return sum(
        1
        for param in sig.parameters.values()
        if param.kind in [
            inspect.Parameter.POSITIONAL_ONLY,
            inspect.Parameter.POSITIONAL_OR_KEYWORD
        ]
    )


def validate(func):
    """Validates a function that computes one operator expression.

    Example: validate(lambda x, y: return x | y == y | x)
    """
    domain = [_0, _M, _1]
    n = num_args(func)
    for combination in itertools.product(domain, repeat=n):
        if not func(*combination):
            msg = 'Expected: {}'.format(func(*map(Printer, combination)))
            raise Exception(msg)


def parse_args():
    from argparse import ArgumentParser
    parser = ArgumentParser()
    parser.add_argument('--test-fail', action='store_true')
    return parser.parse_args()


def main():
    # use the --test-fail key to check that validation can fail :)
    args = parse_args()
    if args.test_fail:
        validate(lambda x: x | ~x == _1)

    # simple equalities
    validate(lambda x: ~(~x) == x)
    validate(lambda x: x | _1 == _1)
    validate(lambda x: x & _0 == _0)
    validate(lambda x: x | _0 == x)
    validate(lambda x: x & _1 == x)

    # maybe inequalities
    validate(lambda x: x & _M <= _M)
    validate(lambda x: x & _M <= x)
    validate(lambda x: x | _M >= _M)
    validate(lambda x: x | _M >= x)

    # commutativity & associativity
    validate(lambda x, y: x | y == y | x)
    validate(lambda x, y: x & y == y & x)
    validate(lambda x, y, z: (x | y) | z == x | (y | z))
    validate(lambda x, y, z: (x & y) & z == x & (y & z))

    # DeMorgan laws and distributivity
    validate(lambda x, y: ~(x & y) == ~x | ~y)
    validate(lambda x, y: ~(x | y) == ~x & ~y)
    validate(lambda x, y, c: (x | y) & c == (x & c) | (y & c))
    validate(lambda x, y, c: (x & y) | c == (x | c) & (y | c))

    print('All good!')


if __name__ == '__main__':
    main()