[Tutor] function algebra, explained (was: Re: function algebra)

[Abel Daniel]

Daniel Ehrenberg writes:
> I'm sorry, but being a beginner, as many are on this
> list, I can't understand that. Would you mind
> explaining it or pointing me to a website explaining
> something similar?
Let's start from the first version:

class Fun:
    def __init__(self, func):
        self.func=func
    
    def __call__(self, *a, **kw):
        return self.func(*a, **kw)

    def __add__(self, other):
        def f(*a, **kw):
            return self.func(*a, **kw) + other(*a, **kw)
        return Fun(f)

The __call__ method will be called when a Fun instance is called, so
( after sin=Fun(math.sin) ) "sin(42)" is the same as "sin.__call__(42)".
The __add__ method will be called when two Fun instances are added, so
"sin + sin" is transformed into sin.__add__(sin). (There is other
magic going on, it might be transformed into something else. We'll see
more about this a bit later.)

So instances of Fun can be called, and they can be added. Now we'll
continue by adding other operations.
http://python.org/doc/current/ref/numeric-types.html contains a long
list of them.

To support "sin * sin" we need a __mul__ method. We could simply add
it by copying the __add__ method, like this:

    def __mul__(self, other):
        def f(*a, **kw):
            return self.func(*a, **kw) * other(*a, **kw)
        return Fun(f)

However, wwe would have to make almost the same method for every
similar "magic method". That's "comb code"
(see http://bigasterisk.com/wikis/essays/CombCode) and I wanted to avoid
it. (If for no better reasons then because it's unimaginative and not fun.)

Instead of writing that many similar methods, we will make a more
general solution. The 'template' which is the same in these methods is:

    def some-name(self, other):
        def f(*a, **kw):
            return self.func(*a, **kw) some-operator  other(*a, **kw) #(1)
        return Fun(f)

In each case we would substitute the appropriate thing in the place of
'some-name' and 'some-operator'. (Like __add__ and +, for example.)
This can be done by hand when writing the code, but we would like to
do it during runtime in the program. However, the line marked with (1)
would cause a error. Here, we would like to replace 'some-operator'
with the contents of a variable. We could do this by generating code
with something like exec() or eval(). (Making a string and passing
that to one of these.)

But such 'generating code from a string' is awfully dangerous when
done wrong, using some other alternative is usually much better. In
this case, there is a suitable alternative, so we'll use that
instead.[1]

The idea is to first replace
    self.func(*a, **kw) some-operator  other(*a, **kw)
with
    self.func(*a, **kw).some-name( other(*a, **kw) )
Then we can replace
    self.func(*a, **kw).some-name
with
    getattr(self.func(*a, **kw), some-name)
getting
   getattr(self.func(*a, **kw),  name)(other(*a, **kw))
which is just what we need.

Putting it together, we get a 'method generator' which will generate
the appropriate method from a name:

     def method_generator(self, name):
         def ff(other):
             def f(*a, **kw):
                 return getattr(self.func(*a, **kw),  name)(other(*a, **kw))
             return Fun(f)
         return ff

Okay, this three-times nested 'def' looks really intimidating. The
easy way of grokking it is to find out what the innermost def does
('creates a function which takes such and such arguments and returns
such and such') and then handle that part as a black box. Then go from
inside out: take the second-innermost def and so on. The idea is that
stepping 'outwards' means going to a higher abstraction level.  A
function in an inner level is just a variable in an outer level. Trying
to describe method_generator as 'a function that returns a function
that returns an object, which, when called returns a number' might be
precise, but it's not really useful. Calling it 'a function that
returns something we can pass on to get numerical operations
supported' might be more helpful. Ignorance is bliss. :)

Another complicating thing here is the use of variables. Normally the
body of a function only works with thing that are either 'global' (for
example they come from an imported module or such) or are passed in as
variables. Here, however, we have a function created with:

             def f(*a, **kw):
                 return getattr(self.func(*a, **kw),  name)(other(*a, **kw))

In this case, 'name', 'other' and 'self' are variables, that are
neither 'global', nor passed in as variables. They come from the scope
where f is defined. Here, we are using the lexically-scopedness of the
language. ( For more examples, see
http://mail.python.org/pipermail/tutor/2003-June/023187.html )

So now we can generate all these magic methods simply from the
name. But we don't want to generate them, we want to use them. Make
them the methods of the class and get them called when we want to
divide two Fun instances.

That can be achieved in different ways. I choose a getattr hack, for
no real reason. Simply that was the first idea I had. Now I think
different approach is better, see [3].

__getattr__ is a magic method too. It is used for attribute access,
just as __call__ is used for calling. A.B will be A.__getattr__(B).
(There are many details I ommit here. See
http://python.org/doc/current/ref/attribute-access.html)

So the idea is that "A + B" get transformed into "A.__add__(B)" which
becomes "A.__getattr__('__add__')(B)". ( As A.__add__ is turned into
A.__getattr__('__add__') .) All we have to do in __getattr__ is check
if the requested attribute is a numerical-operation-handling-magic-method
and return the result of method_generator:

    operators=['__add__', '__mul__', ...etc... ]
    def __getattr__(self, name):
        if name in operators:
            return self.method_generator(name)
        raise AttributeError # follow __getattr__'s docs

This will work fine for all the binary operators. But some operators
are unary (like __neg__ which handles negation) and some have an
optional third argument (actually only one, __pow__). method_generator
in it's current form can only handle the binary operators.

To support unary and ternary operators, we would have to add a new
method_generator, and extra checking in __getattr__. Following the
spirit of this posting, we should create a new method that creates
the necessary method_generator methods on-the-fly. We would call it
n_ary_method_generator_generator, and it would be a function, that
would return a function, that would return a function...
Oh well, I don't hate comb-code _that_ much.

So we'll rename method_generator to binary_operation and make the
methods unary_operation and ternary_operation which differ only in one
line. In the case of ternary_operation there is an extra trick in
that the third arg is optional, so we can't make ff take two args, it
needs to take arbitrary number of args (which in practice will be one
or two), hence the use of *args.

Now we have only two methods left to explain. (Which have not much to
do with the ones discussing sofar.) compose is pretty simple, if you
understood the first version of Fun, you'll understand compose, too.

As for __coerce__, it's for handling "f = Fun(math.sin) + 5". Adding a
number to a function usually doesn't make much sense, but we can say
that in this case we aren't adding a number, we are adding the
constant 5 function, in which case f(x) should be "math.sin(x)+5".

Doing numerical operations with different types is pretty every-day,
so there is a special mechanism to handle it. The idea is that
__coerce__ is called before doing the operation, thus giving the
programmer a chance to convert the object to something else. In our
case, we have to make something callable, so we simply bundle it up in
a lambda.

That's it.
Pretty simple, isn't it? :)

-- 
Abel Daniel

[1] As it turns out, this alternative isn't so 'suitable' after all.
Although "a+b" gets transformed into "a.__add__(b)", that doesn't mean
that the two are equivalent. For example:
    
    >>> 5 + 12j
    (5+12j)
    >>> (5).__add__(12j)
    NotImplemented

Here we get an error because complex numbers and ints can't be
added. The int must be turned into a complex number first. (Which
means converting 5 to (5+0j) in this case.) This is done during
coercion when doing "5 + 12j", but by calling __add__ we skip this
step.

This means that my (second) Fun() class will break when doing
operations on two functions that return different type of numbers.
For example:

    >>> (Fun(int) + Fun(math.sin))(1.0)
    NotImplemented

Adding to the breakage, the order of adding matters:

    >>> (Fun(math.sin) + Fun(int))(1.0)
    1.8414709848078965

(In this case, a float's __add__ method is called, which can handle
ints. In the previous case and int's __add__ method was called, which
can't handle floats.)

Generating code from a string looks really attractive now... (At least
I don't know how to do it in some other way.)

[3] In the version detailed above, __getattr__ creates a new method
for every numerical operation. That's not really what we had in mind
when we started by trying to avoid comb-code. A better method would be
the following:
(only for binary operations, putting ternary and unary back is trivial)

binary_operators  ['__add__', ...etc... ]
class Fun:
    def __init__(self, func):
        self.func=func

    def __call__(self, *a, **kw):
        return self.func(*a, **kw)

   # __coerce__ and compose don't change

def binary_operation( name ):
    def ff(self, other):
        def f(*a, **kw):
            return getattr(self.func(*a, **kw), name)(other(*a, **kw))
        return Fun(f)
    return ff

for i in  binary_operators:
    setattr(Fun, i, binary_operation(i)) # (2)

The changes: binary_operation is not a method of Fun any more, ff in
binary_operation is a bit different, __getattr__ is gone, and there is
a strange loop at the end.

The idea is that at the end of Fun's definition we have a class that's
missing all the magic __add__ and similar methods. We'll attach these
methods in that for loop. After that loop, there won't be any
tricks. No __getattr__, no method generation, nothing. The class will
behave as if we had written every magic method by hand, like in the
first version we wrote __add__ by hand.

Let's take a look at that loop. For every item in the list, it will
first create a function by calling binary_operation. This function
takes two args, self and other. Then it makes this function into an
attribute of the Fun class.

I have to note that the above might be wrong. All the examples I found
on the net that does such 'add a new method to an existing class at
runtime' trick uses new.instancemethod. I don't know why that would be
needed, as ommiting it works fine for me, but there might be a reason
for it. If it _is_ needed, the line marked with (2) above should be
replaced with:

    setattr(Fun, i, new.instancemethod(binary_operation(i), None, Fun))

(And an 'import new' should be added.)