More Questions on the Path to Combinatory Python
I was just thinking yesterday that I need to get back to the posts I was intending to make after my initial post of the month, Two Fun(ctional) Questions. Then tonight Eric Florenzano made an excellent post on Lambda Calculus which is related to my topic of interest.
So let me take one of his examples and raise again the issue from my first post.
First of all, consider the following Python function taking two arguments:
>>> add_ = lambda x, y: x + y
This function works as expected:
>>> add_(5, 4) 9
Eric shows a curried version defined in Python:
>>> add = lambda x: lambda y: x + y
and shows how, when given one number, this returns a function that takes a second number and adds it to the first:
>>> add(5)(4) 9
To emphasize my desire to blur the distinction between functions and constants, I'd like to point out the following works too:
>>> (add)(5)(4) 9
But imagine we want to add three numbers. With our two-argument version, we could say:
>>> add_(5, add_(2, 2)) 9
How would we do that with our curried version? I'm NOT talking about defining a new 'add', I'm talking about using multiple applications of the original 'add' just like we did with 'add_' above.
The following works:
>>> (add)(5)((add)(2)(2)) 9
but note the additional parentheses we had to add. If we wanted to instead defer the application of the final argument we'd have to rewrite it as:
>>> (add)((add)(5)(2)) <function <lambda> at 0x755f0> >>> (add)((add)(5)(2))(2) 9
So the question is: is there a way to modify add (hopefully with just a wrapper that could be applied to any unary function) such that the following work:
(add)(5)(add)(2) (add)(5)(add)(2)(2)
where the former is equivalent to (add)(7) and the latter returns 9?
And is this pretty much the same question I asked in my original post with the very same solution(s)?
By the way, here is another example that should work in any true solution...
If I define
>>> M = lambda x: (x)(x)
then we should be able to get
(add)(M)(1)
to return 2.
Or is this whole hybrid approach destined to failure and the only real way to use combinators is with Church-encoded numerals?
Comments (11)
Marty Alchin on Nov. 20, 2008:
Okay, I'll bite. I commented on Eric's post that I don't yet understand the value of diving into lambda calculus, and I'm not sure what advantage there is to what you're asking for, but after spending so long on Pro Django, I'm actually intrigued about such an abstract problem. I'll do some digging and see what I can come up with. Maybe I'll find some point to all of this while I'm at it. :)
Dethe Elza on Nov. 20, 2008:
(add)(add)(5)(2)(2) is going to give you a syntax error because of parens context overloading. The first pair are meaningless (operator precedence of one argument) and are thrown away, giving this:
add(add)(5)(2)(2)
Which is a function call with the argument:
add)(5)(2)(2
This is why the extra parens were required. I don't see a way around that using parens, although you could possibly overload other syntax. I have seen binary OR overloaded in such a way that you could possibly make
|add| |add| |5| |2| |2|
work the way you're asking. Not sure if that is helpful to you or not. Personally, I'd prefer to use functools.partial, and the itertools and operator libraries to operate on lists (or other iterables) for this sort of thing.
James Tauber on Nov. 20, 2008:
Dethe, there is no syntax error. For example, if you define
>>> add = lambda x: lambda y: lambda z: x + y + z
you can successfully say
>>> add(1)(2)(3)
6
without the argument being treated as 1)(2)(3
Eric Florenzano on Nov. 20, 2008:
Very thought-provoking post! The concept is interesting because it begs for a sort of referential transparency where each expression is simultaneously a function and a value. I can't think of a trivial way to do this without defining numeric values in terms of functions...which you alluded to with your reference to Church numbers. I'll have to think about it more, but I'm guessing it's not going to be simple.
James Tauber on Nov. 20, 2008:
Eric, my previous post (Two Functional Questions) and the many comments there might provide the solution to the function/value problem, possibly in conjunction with converting all integer constants to constant functions (e.g. 5 => lambda: 5)
Eric Wald on Nov. 20, 2008:
A working example of the (add) part is available at http://pastebin.com/f66572824
Unfortunately, that approach probably wouldn't work for the definition of M as given.
Zachary Voase on Nov. 20, 2008:
I think what you'll end up finding is that Lisp is the solution to this problem. Seriously.
I'm not just saying that because I'm a lispophile.
Alex on Nov. 20, 2008:
Well having an object act as both a function and an int(sorta) is trivial in python, just subclass int and give it an __call__ method.
Carl on Nov. 21, 2008:
Just break down and use classes to make a decorator. See if the thing you're passed in is an object of the same type and if so defer the calc, if not, pass it as an argument to your function.
James Tauber on Nov. 22, 2008:
Eric Wald, your solution looks to be exactly what I want -- I'm doing another post about it.
Last Modified: Nov. 20, 2008
Author: James Tauber
Foo on Nov. 20, 2008:
"(add)(5)((add)(2)(2))" this reminds me of lisp somehow. is this really usefully in practice?