# Algorithms as objects?

Discussion in 'Python' started by Kreso, Aug 28, 2009.

1. ### KresoGuest

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.
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.

Kreso, Aug 28, 2009

2. ### Chris RebertGuest

On Thu, Aug 27, 2009 at 4:05 PM,
Kreso<> wrote:
>
> 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.
> 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__
http://docs.python.org/reference/datamodel.html#object.__call__

Cheers,
Chris
--
http://blog.rebertia.com

Chris Rebert, Aug 28, 2009

3. ### BearophileGuest

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

Bearophile, Aug 28, 2009
4. ### Diez B. RoggischGuest

Kreso schrieb:
> 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.
> 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

Diez B. Roggisch, Aug 28, 2009
5. ### Bruno DesthuilliersGuest

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.
> 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 ?

Bruno Desthuilliers, Aug 28, 2009
6. ### Steven D'ApranoGuest

On Thu, 27 Aug 2009 23:05:41 +0000, Kreso wrote:

> 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
....
>>> def double(y):

.... return 2*y
....
>>> double_plus_one(3.5)

8.0

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

> 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:

>>> f1 = axbx2_factory(1, 2)
>>> f2 = axbx2_factory(1, 0)
>>> f1(2.5)

-10.0
>>> f1(3.5)

-21.0
>>> f2(2.5)

2.5
>>> f2(3.5)

3.5

Hope this helps.

--
Steven

Steven D'Aprano, Aug 28, 2009
7. ### KresoGuest

Bearophile <> wrote:
> 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.

Kreso, Sep 3, 2009