Algorithms as objects?

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

  1. Kreso

    Kreso Guest

    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.
    Kreso, Aug 28, 2009
    #1
    1. Advertising

  2. Kreso

    Chris Rebert Guest

    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.
    >  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
    --
    http://blog.rebertia.com
    Chris Rebert, Aug 28, 2009
    #2
    1. Advertising

  3. Kreso

    Bearophile Guest

    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
    #3
  4. 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.
    > 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
    Diez B. Roggisch, Aug 28, 2009
    #4
  5. 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 ?
    Bruno Desthuilliers, Aug 28, 2009
    #5
  6. 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:

    >>> def add1(x):

    .... return x+1
    ....
    >>> def double(y):

    .... return 2*y
    ....
    >>> double_plus_one = compose(add1, double)
    >>> 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.




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

    >>> 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
    #6
  7. Kreso

    Kreso Guest

    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
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Andreas
    Replies:
    0
    Views:
    503
    Andreas
    Dec 2, 2003
  2. abhinav

    encryption algorithms

    abhinav, Dec 26, 2004, in forum: VHDL
    Replies:
    2
    Views:
    642
  3. Melanie Nasic
    Replies:
    19
    Views:
    3,030
    Thomas Rudloff
    Jan 1, 2006
  4. Barak
    Replies:
    0
    Views:
    806
    Barak
    Aug 7, 2003
  5. 7stud
    Replies:
    11
    Views:
    684
    Dennis Lee Bieber
    Mar 20, 2007
Loading...

Share This Page