James Tauber

journeyman of some

blog > 2008 > 11 > 22 >

First Success With Combinatory Python

In More Questions on the Path to Combinatory Python I wondered how to write an 'add' function such that not only 

(add)(2)(2) == 4

worked but also things like: 

(add)(add)(1)(2)(3) == 6
(add)(1)(add)(2)(3) == 6

If we throw in a unary function like 'neg' then things like this should work too: 

(neg)(5) == -5
(neg)(neg)(5) == 5
(add)(3)(neg)(2) == 1

Here's how I started to think about it. An expression such as (add)(2)(2) could be described as having the signature "200". It consists of subexpressions requiring, respectively 2, 0 and 0 arguments. Just (add)(2) would have a signature "20" which is equivalent to a signature of 1.

Using this notion:

It is easy to see that for an expression to be complete (i.e. not partial) it must have a signature ending in 0. But there is slightly more to it that than. Basically, start off with a score of 1 and work from left to write, every "2" you encounter increases the score by 1 and every "0" decreases it by 1. A "1" has no effect. When you hit a score of 0 you're complete.

Every complete signature has a particular bracketing of function application. For example, expressions of signature 112100 can be evaluated as follows: 

def eval112100(a, b, c, d, e, f):
    return a(b(c(d(e))(f)))

and each partial signature has a function that can dispatch evaluation to another function depending on the number of args the next arg takes (relying on a function like add being annotated with add.args = 2). 

def eval1121(a, b, c, d):
    return lambda e: (
        eval11210 if e.args == 0 else
        eval11211 if e.args == 1 else
        eval11212 if e.args == 2 else
        ...
    )(a, b, c, d, e)

I was still struggling to implement this in a recursive way that could handle unlimited depth and then I saw in a comment that Eric Wald came up with a solution: 

def combinatoric(n):
    def decorator(f):
        @wraps(f)
        def wrapper(x):
            if callable(x):
                return lambda y: combinatoric(n)(f)(x(y))
            elif n > 1:
                return combinatoric(n - 1)(wraps(f)(partial(f, x)))
            else:
                return f(x)
        return wrapper
    return decorator

and so you then say 

@combinatoric(1)
def neg(x):
    return -x



@combinatoric(2)
def add(x, y):
    return x + y

and it all works. The use of wraps is optional but including it means partial add will have the name add not wrapper.

As Eric points out in his comment, this still doesn't solve the (add)(M)(5) issue but I have some thoughts on that for a subsequent post.

Categories:
prev « python » next
prev « algorithms
prev « combinatory_python » next

Comments (5)

Adam Collard on Nov. 22, 2008:

inspect module can remove the need to manually specify the number of arguments the callable takes

import inspect
def auto_arity_combinatoric(f):
return combinatoric(len(inspect.getargspec(f)[0]))(f)

@auto_arity_combinatoric
def neg(x):
return -x

@auto_arity_combinatoric
def add(x, y):
return x + y

Of course, you can choose to tweak combinatoric instead of the extra decorator

James Tauber on Nov. 22, 2008:

Thanks Adam. I figured something like that was possible but hadn't investigated further.

Eric Wald on Nov. 22, 2008:

Good call, Adam. I had experimented with
n = f.func_code.co_argcount
but that felt too hackish. As an extra bonus, reading n directly also allows you to trim the decorator() layer out of combinatoric().

Unfortunately, combinatoric() functions tend to be a bit too greedy, particularly when encountering constructs like K and S that expect to operate on other operators instead of values. That problem really is best solved by Church encoding, but it might be possible to find workarounds.

James Tauber on Nov. 22, 2008:

Eric, I so far haven't found it greedy with regard to combinators like K and S. I've used B, W, V, C, M, S, K and I in combination with add and neg with no problem. Do you have an example that doesn't work as it should?

James Tauber on Nov. 25, 2008:

Eric, I think I worked out how you mean by your "greedy" comment.

You mean in the case of something like

(K)(add)(neg)(1)(1)

your concern is that, because add is callable, the rest of the expression is thunked and treated as the first argument to K?

I never accounted this because I don't use combinatoric to define K, I just define it as

K = lambda x: lambda y: x

and only use combinatoric to turn regular functions into combinators.

Created: Nov. 22, 2008
Last Modified: Nov. 22, 2008
Author: James Tauber