binfunc.py

import numpy
import itertools


class BinFunc:
    """Binary functions, represented as a truth table. This lets us
    compare binary functions, and build sets of binary functions. Normal
    Python functions don't let us do that.
    """
    def __init__(self, table):
        self.table = numpy.array(table, dtype=bool)

    def __repr__(self):
        # when you print a BinFunc, just print the truth table instead
        return repr(self.table)

    def __hash__(self):
        # this lets us build sets of BinFunc objects later
        return hash(tuple(self.table))

    def __eq__(self, other):
        # this lets us use == on BinFunc objects
        return all(self.table == other.table)

    def __call__(self, *args):
        """Make BinFunc objects callable like functions.

        binary_or = BinFunc(2, lambda a, b: a | b)
        assert binary_or(0, 1) == 1
        """
        width = len(args)
        coef = numpy.array([2 ** i for i in reversed(range(width))])
        return self.table[coef @ args]

    @property
    def width(self):
        """The number of inputs to this function."""
        # calculate this from our table size
        return int(numpy.log2(len(self.table)))

    @classmethod
    def from_func(cls, width, f):
        """Create a binary function from a python function. For example,

        binary_3or = BinFunc(3, lambda a, b, c: a | b | c)
        """
        # construct the truth table
        table = numpy.zeros((2 ** width,), dtype=bool)
        bits = [False, True]
        for i, inp in enumerate(itertools.product(bits, repeat=width)):
            table[i] = f(*inp)
        return BinFunc(table)

    @classmethod
    def all(cls, width):
        """Iterate over all binary functions with the given number of inputs.
        """
        bits = [False, True]
        for table in itertools.product(bits, repeat=2 ** width):
            yield BinFunc(table)

    def invert(self):
        """Invert ourselves. For example,

        binary_nor = BinFunc(2, lambda a, b: a | b).invert()
        """
        return BinFunc(~self.table)


def lathrop(width):
    """Iterator over Lathrop-style internal functions (without the xor)."""

    # Lathrop ignores functions that just repeat an input, or ~input
    # so lets build a set of functions to ignore
    ignores = set()
    for i in range(width):
        f = BinFunc.from_func(width, lambda *b: b[i])
        ignores.add(f)
        ignores.add(f.invert())

    # ok, now iterate through *all* binary functions and skip our ignores
    for f in BinFunc.all(width):
        if f in ignores:
            continue
        yield f


def xored(fs):
    """Transform a list of functions f into xor(u, f).

    (If f has N inputs, xor(u, f) has N + 1.)
    """
    for f in fs:
        yield BinFunc.from_func(f.width + 1, lambda a, *b: a ^ f(*b))


def hopfield(width, trials=10000):
    """Iterator over Hopfield-style weighted sum binary functions.

    This is a random process, so we just return a bunch of random instances.
    """
    for _ in range(trials):
        weights = numpy.random.normal(size=width)
        bias = numpy.random.normal()
        yield BinFunc.from_func(width, lambda *b: weights @ b + bias > 0.0)


if __name__ == '__main__':
    # get a set of all Lathrop functions on 3 inputs (2 internal + xor)
    ls = set(xored(lathrop(2)))
    # get a set of (probably) all Hopfield-style functions on 3 inputs
    hs = set(hopfield(3))

    # print out their sizes and intersection
    print("Lathrop functions", len(ls))
    print("Hopfield functions", len(hs))
    print("Intersection", len(ls.intersection(hs)))

    # debug: print out the truth tables for their intersection
    #print(ls.intersection(hs))