How do I dynamically create functions without lambda?

[Kay Schluehr]

Steven D'Aprano wrote:
> On Fri, 27 Jan 2006 11:41:56 -0800, Kay Schluehr wrote:
>
> >
> > Russell wrote:
> >> I want my code to be Python 3000 compliant, and hear
> >> that lambda is being eliminated. The problem is that I
> >> want to partially bind an existing function with a value
> >> "foo" that isn't known until run-time:
> >>
> >>    someobject.newfunc = lambda x: f(foo, x)
> >>
> >> The reason a nested function doesn't work for this is
> >> that it is, well, dynamic. I don't know how many times
> >> or with what foo's this will be done.
> >>
> >> Now, I am sure there are a half-dozen ways to do this.
> >> I just want the one, new and shiny, Pythonic way. ;-)
> >
> > If you want to code partial application without lambda I recommend
> > using the code presented in the accepted PEP 309 that will be
> > implemented in the functional module in Python 2.5.
> >
> > http://www.python.org/peps/pep-0309.html
>
>
> Fascinating. A couple of thoughts:
>
> - I really wish that people would make up their minds about what currying
> is, and how it differs from partials and closures. If the people who
> do know can't agree, how do they expect the rest of us to understand?

If they can't agree they probably don't know ;)

Concepts like "closure" and "currying" are well defined in lambda
calculus and hence in functional programming.

> - What, if anything, is the difference between a closure and an iterator?
> Is an iterator just a closure wrapped up with an API?

I would expect a closure to be a function with free/unbound variables
that are bound by an enclosing context. In FP slang a function without
any free variables is called a "combinator". An iterator is a function
related to an abstract data type equipped with a partial order. The
iterator abstracts from the particular ordering scheme and makes the
ADT look like a list. In Python we have a nice correspondence between
generators as implicit defined sequences of yielded values, iterators
that enable uniform access to the values produced by generators and
lists that make the sequence explicit ( if finite ).

Fun with combinators
======================
There are quite interesting relationships deep down in the theory of
computation. For instance understanding recursion in lambda calculus is
not that easy because you cannot simply reintroduce an anonymous
function by the name into its own body. The idea is to create a
fixpoint of a higher order curried function instead. See for example
this curried extension of a factorial:

F = lambda h: lambda n : n<2 and 1 or n*h(n-1)

Now imagine you have a fixpoint fix(F) of F which is again a function
and pass it into F then you will get:

fix(F) = F(fix(F)) = lambda n : n<2 and 1 or n*fix(F)(n-1)

That is fix(F) is actually the searched factorial ! There is a generic
way to create fixpoints of higher order curried functions such as F.
The most popular one is the so called Y-combinator ( not to confuse
with Paul Grahams company ;).

In Python you can write:

Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda
arg: f(f)(arg)))

This serves the purpose. Try Y(F) and see.

Kay