Yet another arithmetic simulator

arithmetic.py

# Tools
def typematcher(*objects):
    def inner(*types):
        assert(len(objects) == len(types))
        return all(isinstance(obj, typ) for obj, typ in zip(objects, types))
    return inner

def recursive_construct(f, base, n=0):
    yield base
    if n > 0:
        yield from recursive_construct(f, f(base), n-1)

# Expandable domain containing all objects
domain = {}

# (Memoizing) function to create exactly one instance of each object
def spawn(cons_func, *arguments):
    key = (cons_func, *arguments)
    if key not in domain:
        domain[key] = cons_func(*arguments)
    return domain[key]

# Decorator for all constructors
# Performs type checking and wraps memoization
def make_constructor(func, *types):
    def wrapper(*args):
        assert(typematcher(*args)(*types))
        return spawn(func, *args)
    return wrapper




# Any global operations go here
class UniversalObject:
    def __eq__(self, other):
        typematch = typematcher(self, other)
        if typematch(Natural, Natural):
            return self is other
        elif typematch(Integer, Integer):
            return self.neg + other.pos == self.pos + other.neg
        elif typematch(Rational, Rational):
            return self.numer * IntConstruct(Zero(), Succ(other.denom)) == \
                other.numer * IntConstruct(Zero(), Succ(self.denom))
        else:
            raise TypeError

    def __hash__(self):
        return hash(id(self))




# Natural numbers
# Zero : Natural
# Succ : Natural => Natural

class Natural(UniversalObject):
    def __add__(self, other):
        if isinstance(other, ZeroType):
            return self
        elif isinstance(other, SuccType):
            return Succ(self + other.prec)
        else:
            raise TypeError

    def __mul__(self, other):
        if isinstance(other, ZeroType):
            return other
        elif isinstance(other, SuccType):
            return self + self * other.prec
        else:
            raise TypeError(type(other))

class ZeroType(Natural):
    def __init__(self):
        self.numeric = 0

    def __repr__(self):
        return 'Zero()'

    def __str__(self):
        return '0'
Zero = make_constructor(ZeroType)

class SuccType(Natural):
    def __init__(self, prec):
        self.prec = prec
        self.numeric = prec.numeric + 1

    def __repr__(self):
        return 'Succ({})'.format(repr(self.prec))

    def __str__(self):
        return str(self.numeric)
Succ = make_constructor(SuccType, Natural)


# Integers
# Tuples of natural numbers
class Integer(UniversalObject):
    def __init__(self, neg, pos):
        self.neg = neg
        self.pos = pos
        self.numeric = self.pos.numeric - self.neg.numeric

    def __add__(self, other):
        if not isinstance(other, Integer):
            raise TypeError
        return IntConstruct(self.neg + other.neg, self.pos + other.pos)

    def __mul__(self, other):
        if not isinstance(other, Integer):
            raise TypeError
        a, b = self.neg, self.pos
        c, d = other.neg, other.pos
        # (b - a)*(d - c) = b*d + a*c - (a*d + b*c)
        return IntConstruct(a * d + b * c, b * d + a * c)

    def __repr__(self):
        return 'IntConstruct({}, {})'.format(repr(self.neg), repr(self.pos))

    def __str__(self):
        return str(self.numeric)
IntConstruct = make_constructor(Integer, Natural, Natural)


# Rationals
# Tuples of integer, natural number
# The denominator is incremented by one in all arithmetic processes
class Rational(UniversalObject):
    def __init__(self, numer, denom):
        self.numer = numer
        self.denom = denom

    def __add__(self, other):
        if not isinstance(other, Rational):
            raise TypeError
        a, b = self.numer, IntConstruct(Zero(), Succ(self.denom))
        c, d = other.numer, IntConstruct(Zero(), Succ(other.denom))
        return RatConstruct(a * d + b * c, (Succ(self.denom) * Succ(other.denom)).prec)

    def __repr__(self):
        return 'RatConstruct({}, {})'.format(
            repr(self.numer), repr(self.denom))

    def __str__(self):
        return '({})/({})'.format(
            str(self.numer.numeric), str(Succ(self.denom)))
RatConstruct = make_constructor(Rational, Integer, Natural)




# Construct some objects
nats = list(recursive_construct(Succ, Zero(), 100))
posints = list(IntConstruct(Zero(), n) for n in nats)
negints = list(IntConstruct(n, Zero()) for n in nats)
posrats = list(list(RatConstruct(k, n) for n in nats) for k in posints)
negrats = list(list(RatConstruct(k, n) for n in nats) for k in negints)



def tests():
    assert(nats[2] == Succ(Succ(Zero())))
    assert(repr(nats[2]) == 'Succ(Succ(Zero()))')
    assert(str(nats[5]) == '5')
    assert(posints[1] == IntConstruct(Zero(), Succ(Zero())))
    assert(negints[1] == IntConstruct(Succ(Zero()), Zero()))
    assert(negints[1] == IntConstruct(nats[6], nats[5]))
    assert(str(negrats[5][0]) == '(-5)/(1)')
    assert(nats[3] * nats[7] == nats[21])
    assert(posints[5] * negints[3] == negints[15])
    assert(negints[3] * negints[7] == posints[21])
    assert(posrats[1][2] + negrats[1][2] == negrats[0][0])
    assert(posrats[3][3] + negrats[5][2] == negrats[11][11])
    print("Passed all tests")

if __name__ == '__main__':
    tests()
    print("Created {} objects".format(len(domain)))