expressions.py

class Expr(object):
    def __init__(self, *args):
        self.args = args

    def rewrite(self, fn):
        rewritten = map(fn, self.args)
        if any(a is not b for a, b in zip(self.args, rewritten)):
            return type(self)(*rewritten)
        return self

    def __call__(self, **kwargs):
        return self.rewrite(lambda x: x(**kwargs))

    def fmap(self, fn):
        func = type('Anonymous', (Function,), {'implementation': staticmethod(fn)})
        return func(self)

    def bind(self, fn):
        cofexpr = type('Anonymous', (Cofexpr,), {'implementation': staticmethod(fn)})
        return cofexpr(self)

    def evaluate(self):
        raise NotImplementedError('No evaluation')


class Atom(Expr):
    '''An Atom is an Expr that evaluates to itself'''
    def __init__(self, *args):
        self.args = args

    def __call__(self, **kwargs):
        return self

    def evaluate(self):
        return self

    def to_python(self):
        return self.args[0]

    def __str__(self):
        return str(self.args[0])


class Data(object):
    class List(Atom):
        def __str__(self):
            return '[{}]'.format(', '.join(str(x) for x in self.to_python()))


class Variable(Expr):
    '''A Variable is an Expr that can be substituted by name'''
    def __call__(self, **kwargs):
        key = self.args[0].to_python()
        if key in kwargs:
            return kwargs[key]
        return self


class Sexpr(Expr):
    '''A Sexpr applies an implementation to its arguments upon evaluation'''
    def implementation(self, *args):
        raise NotImplementedError('No implementation')


class Function(Sexpr):
    '''A Function has an implementation that accepts values and returns values'''
    def evaluate(self):
        return self.implementation(*[x.evaluate() for x in self.args])


class Macro(Sexpr):
    '''A Macro has an implementation that accepts syntax and returns syntax'''
    def evaluate(self):
        return self.implementation(*self.args).evaluate()


class Fexpr(Sexpr):
    '''A Fexpr has an implementation that accepts syntax and returns values'''
    def evaluate(self):
        return self.implementation(*self.args)


class Cofexpr(Sexpr):
    '''A Cofexpr has an implementation that accepts values and returns syntax'''
    def evaluate(self):
        return self.implementation(*[x.evaluate() for x in self.args]).evaluate()


class List(Function):
    def implementation(self, *args):
        return Data.List(args)


class Map(Macro):
    def implementation(self, xs, f):
        return xs.bind(lambda ls: List(*[
            f(_=x) for x in ls.to_python()
        ]))


print Map(List(Atom(1), Atom(2)), Variable(Atom('_'))).evaluate()