Algorithms as objects?

[Kreso]

I am writing an application that essentially calculates set of numbers,
say N1, N2, ..., where they can be calculated by several different
algorithms. (One should be able to choose the algorithm at run time.)
In each algorithm one starts from a set of functions, say f1, f2, ...,
which are then transformed into some other functions g1(f1, f2, ..),
g2(f1, f2, ...), ... , then maybe transformed once more and result is
obtained by evaluating final functions.
I can naturally think about this as a collection of transformation
blocks, which have functions as input and output, and which can be
put together to get the final results. However, I am not sure
how to program this, especially since one cannot subclass function
type. To be clear let me give simplified example of what is needed:

f(x) has unknown shape, so one would like to try, say

f1(x) = ax - b x**2 or f2(x) = a sin(b*x),

where a and b are variable parameters.

Then, one would like to create, with known k(x,y), function g(x)
in one of two ways:

g1(x) = k(x, x)*f(x) or g2(x) = integrate(k(x, y) * f(y), y=0..1),

and finally evaluate N=g(1) as result. In this simple example
there are 4 different algorithms for f(x) -> g(x) -> N, and one
should be able to simply choose between them, e.g. by calling
N(g1, f2, (a,b)).

In practice algorithm is not necessary so linear, but is
generally tree-lika:

(a,b) -> f1(x) --->g1(x)---+
|--> h(x) --> N
(c,d) ---+--> g2(x)--------+
|
f2(x) --+


It would be nice to have some class of function-objects,
that f1(x), .., g1(x), ... could be members/instances of so that common
operations on these functions could be possible (checking
that they satisfy some necessary properties, plotting them, ...),
and then second "class" of transformations/methods operating on
these objects.
I seem to be confused by the fact that I would like to somehow treat
algorithms as objects (so that one can experiment with different
algorithm systems) but I don't have clear picture how to do it.
I am just brainstorming for ideas. Any advice is welcome.

 

[Chris Rebert]

I am writing an application that essentially calculates set of numbers,
say N1, N2, ..., where they can be calculated by several different
algorithms. (One should be able to choose the algorithm at run time.)
In each algorithm one starts from a set of functions, say f1, f2, ...,
which are then transformed into some other functions g1(f1, f2, ..),
g2(f1, f2, ...), ... , then maybe transformed once more and result is
obtained by evaluating final functions.
 I can naturally think about this as a collection of transformation
blocks, which have functions as input and output, and which can be
put together to get the final results. However, I am not sure
how to program this, especially since one cannot subclass function
type. To be clear let me give simplified example of what is needed:

f(x) has unknown shape, so one would like to try, say

f1(x) = ax - b x**2   or    f2(x) = a sin(b*x),

where a and b are variable parameters.

Then, one would like to create, with known k(x,y), function g(x)
in one of two ways:

g1(x) = k(x, x)*f(x)  or   g2(x) = integrate(k(x, y) * f(y), y=0..1),

and finally evaluate N=g(1) as result. In this simple example
there are 4 different algorithms  for f(x) -> g(x) -> N, and one
should be able to simply choose between them, e.g. by calling
N(g1, f2, (a,b)).

In practice algorithm is not necessary so linear,  but is
generally tree-lika:

(a,b) -> f1(x) --->g1(x)---+
                          |--> h(x) --> N
(c,d) ---+--> g2(x)--------+
        |
 f2(x) --+


It would be nice to have some class of function-objects,
that f1(x), .., g1(x), ... could be members/instances of so that common
operations on these functions could be possible (checking
that they satisfy some necessary properties, plotting them, ...),
and then second "class" of transformations/methods operating on
these objects.
I seem to be confused by the fact that I would like to somehow treat
algorithms as objects (so that one can experiment with different
algorithm systems) but I don't have clear picture how to do it.
I am just brainstorming for ideas. Any advice is welcome.

It sounds like you're describing the Strategy Pattern
(http://en.wikipedia.org/wiki/Strategy_pattern).

To have objects callable like functions, just implement the __call__
special method in your class(es):
http://docs.python.org/reference/datamodel.html#object.__call__

Cheers,
Chris

 

[Bearophile]

Chris Rebert:

It sounds like you're describing the Strategy Pattern
(http://en.wikipedia.org/wiki/Strategy_pattern).

To have objects callable like functions, just implement the  __call__
special method in your class(es):

Please, can't you just use a bit of functional-style programming? Like
creating nested functions on the fly, etc.

Bye,
bearophile

 

[Diez B. Roggisch]

I am writing an application that essentially calculates set of numbers,
say N1, N2, ..., where they can be calculated by several different
algorithms. (One should be able to choose the algorithm at run time.)
In each algorithm one starts from a set of functions, say f1, f2, ...,
which are then transformed into some other functions g1(f1, f2, ..),
g2(f1, f2, ...), ... , then maybe transformed once more and result is
obtained by evaluating final functions.
I can naturally think about this as a collection of transformation
blocks, which have functions as input and output, and which can be
put together to get the final results. However, I am not sure
how to program this, especially since one cannot subclass function
type. To be clear let me give simplified example of what is needed:

f(x) has unknown shape, so one would like to try, say

f1(x) = ax - b x**2 or f2(x) = a sin(b*x),

where a and b are variable parameters.

Then, one would like to create, with known k(x,y), function g(x)
in one of two ways:

g1(x) = k(x, x)*f(x) or g2(x) = integrate(k(x, y) * f(y), y=0..1),

and finally evaluate N=g(1) as result. In this simple example
there are 4 different algorithms for f(x) -> g(x) -> N, and one
should be able to simply choose between them, e.g. by calling
N(g1, f2, (a,b)).

In practice algorithm is not necessary so linear, but is
generally tree-lika:

(a,b) -> f1(x) --->g1(x)---+
|--> h(x) --> N
(c,d) ---+--> g2(x)--------+
|
f2(x) --+


It would be nice to have some class of function-objects,
that f1(x), .., g1(x), ... could be members/instances of so that common
operations on these functions could be possible (checking
that they satisfy some necessary properties, plotting them, ...),
and then second "class" of transformations/methods operating on
these objects.
I seem to be confused by the fact that I would like to somehow treat
algorithms as objects (so that one can experiment with different
algorithm systems) but I don't have clear picture how to do it.
I am just brainstorming for ideas. Any advice is welcome.

Sound like simple function combinators to me. Like this:

import inspect


def combine(f, g):
if len(inspect.getargspec(g)[0]) > 1:
def h(*args):
return g(*f(*args))
return h
else:
def h(*args):
return g(f(*args))
return h


def a(x):
return 10 + x

def b(x):
return x ** 2



print combine(a, b)(20)


def c(x):
return x, x * 2


def d(x, y):
return x + y


print combine(c, d)(10)

But to be honest - I don't think you win much with this whole thing.
Spelling out the function-calls the way they are made is in the end as
efficient and clear as it can get. And for *real* algorithms, you need
non-strict constructs, control-structures and the like, and in the end
of the day, you create a programming language on top of a programming
language.

Diez

 

[Bruno Desthuilliers]

Kreso a écrit :

I am writing an application that essentially calculates set of numbers,
say N1, N2, ..., where they can be calculated by several different
algorithms. (One should be able to choose the algorithm at run time.)
In each algorithm one starts from a set of functions, say f1, f2, ...,
which are then transformed into some other functions g1(f1, f2, ..),
g2(f1, f2, ...), ... , then maybe transformed once more and result is
obtained by evaluating final functions.
I can naturally think about this as a collection of transformation
blocks, which have functions as input and output, and which can be
put together to get the final results. However, I am not sure
how to program this, especially since one cannot subclass function
type.

Nope, but you can write your own callable types:


class functor(object):
def __call__(self):
print "%s called" % self

(snip)

I seem to be confused by the fact that I would like to somehow treat
algorithms as objects

Strategy pattern anyone ?

 

[Steven D'Aprano]

I am writing an application that essentially calculates set of numbers,
say N1, N2, ..., where they can be calculated by several different
algorithms. (One should be able to choose the algorithm at run time.) In
each algorithm one starts from a set of functions, say f1, f2, ...,
which are then transformed into some other functions g1(f1, f2, ..),
g2(f1, f2, ...), ... , then maybe transformed once more and result is
obtained by evaluating final functions.

Sounds like you're doing functional programming. There's a rich set of
functional tools in languages like Haskell, but in Python there's only a
few, such as partial(). (See the functools module.)

However, you can make your own, using the following general technique.
Suppose you want to compose two functions, f and g. Then with a helper
function:

def compose(f, g):
def composed_function(*args):
return f(g(*args))
return composed_function

you can do this:
.... return x+1
........ return 2*y
....8.0


Unfortunately, about the only thing you can't do is check the return type
of functions without actually calling them.

I can naturally think about this as a collection of transformation
blocks, which have functions as input and output, and which can be put
together to get the final results. However, I am not sure how to program
this, especially since one cannot subclass function type. To be clear
let me give simplified example of what is needed:

f(x) has unknown shape, so one would like to try, say

f1(x) = ax - b x**2 or f2(x) = a sin(b*x),

where a and b are variable parameters.

You need factory functions!

def axbx2_factory(a, b):
# Return a function that returns a*x-b*x**2
def inner(x):
return a*x -b*x**2
return inner

And in use:
3.5



Hope this helps.

 

[Kreso]

Please, can't you just use a bit of functional-style programming? Like
creating nested functions on the fly, etc.

I thought about it but I believe that in the future some parts of the
code will be reimplemented in C/C++, so I try to keep it simple.

In the end the hint to learn about "strategy pattern" led me to
construct the program in the way I liked.

Thanks.