An idea for fast function composition

Discussion in 'Python' started by Arnaud Delobelle, Feb 16, 2008.

  1. Hi all,

    Recently there was a thread about function composition in Python (and
    this was probably not the first). The fast way to create a
    (anonymous) composite function

    f1 o f2 o ... o fn

    in Python is via

    lambda x: f1(f2(...fn(x)...)),

    but according to some this is neither the most compact nor the most
    readable. Below I define a 'compose' function such that the above can
    be written

    compose(f1, f2, ...., fn),

    the resulting function being as fast as the lambda version (or maybe
    faster?). 'getcomposer' is a helper function (which in most cases
    will amount to a dictionary lookup).

    ----------------------------------
    def getcomposer(nfunc, _cache={}):
    "getcomposer(n) -> lambda f1, ..., fn:(lambda x: f1(...fn(x)...))"
    try:
    return _cache[nfunc]
    except KeyError:
    fnames = ['f%s' % i for i in range(nfunc)]
    call = ''.join('%s(' % f for f in fnames)
    args = ','.join(fnames)
    cstr = 'lambda %s:(lambda x:%sx%s)' % (args, call, ')'*nfunc)
    composer = _cache[nfunc] = eval(cstr)
    return composer

    def compose(*functions):
    "compose(f1, ..., fn) -> lambda x: f1(f2(...fn(x)...))"
    return getcomposer(len(functions))(*functions)


    # Test

    def double(x): return 2*x
    def square(x): return x**2
    def succ(x): return x+1

    f1 = compose(double, square, succ, float)
    f2 = lambda x: double(square(succ(float(x))))

    def benchmark(f, n=1000000):
    from time import time
    from itertools import imap
    t0 = time()
    for _ in imap(f1, xrange(n)): pass
    t1 = time()
    return t1-t0

    print 'compose', benchmark(f1)
    print 'lambda ', benchmark(f2)
    ----------------------------------

    marigold:python arno$ python -i simple_compose.py
    compose 1.84630298615
    lambda 1.86365509033
    >>> import dis
    >>> dis.dis(f1)

    1 0 LOAD_DEREF 0 (f0)
    3 LOAD_DEREF 3 (f1)
    6 LOAD_DEREF 1 (f2)
    9 LOAD_DEREF 2 (f3)
    12 LOAD_FAST 0 (x)
    15 CALL_FUNCTION 1
    18 CALL_FUNCTION 1
    21 CALL_FUNCTION 1
    24 CALL_FUNCTION 1
    27 RETURN_VALUE
    >>> dis.dis(f2)

    23 0 LOAD_GLOBAL 0 (double)
    3 LOAD_GLOBAL 1 (square)
    6 LOAD_GLOBAL 2 (succ)
    9 LOAD_GLOBAL 3 (float)
    12 LOAD_FAST 0 (x)
    15 CALL_FUNCTION 1
    18 CALL_FUNCTION 1
    21 CALL_FUNCTION 1
    24 CALL_FUNCTION 1
    27 RETURN_VALUE

    f1 and f2 are almost exaclty the same but array lookups (LOAD_DEREFs)
    in f1 replace dictionary lookups (LOAD_GLOBALs) in f2. A C version of
    'compose' could easily be written that doesn't require the use of a
    python lambda-function (as created by 'getcomposer').

    --
    Arnaud
    Arnaud Delobelle, Feb 16, 2008
    #1
    1. Advertising

  2. Arnaud Delobelle

    Guest

    On Feb 16, 3:47 pm, Arnaud Delobelle <> wrote:
    > Hi all,
    >
    > Recently there was a thread about function composition in Python (and
    > this was probably not the first).  The fast way to create a
    > (anonymous) composite function
    >
    >      f1 o f2 o ... o fn
    >
    > in Python is via
    >
    >      lambda x: f1(f2(...fn(x)...)),
    >
    > but according to some this is neither the most compact nor the most
    > readable.  Below I define a 'compose' function such that the above can
    > be written
    >
    >      compose(f1, f2, ...., fn),
    >
    > the resulting function being as fast as the lambda version (or maybe
    > faster?).  'getcomposer' is a helper function (which in most cases
    > will amount to a dictionary lookup).
    >
    > ----------------------------------
    > def getcomposer(nfunc, _cache={}):
    >      "getcomposer(n) -> lambda f1, ..., fn:(lambda x: f1(...fn(x)...))"
    >      try:
    >          return _cache[nfunc]
    >      except KeyError:
    >          fnames = ['f%s' % i for i in range(nfunc)]
    >          call = ''.join('%s(' % f for f in fnames)
    >          args = ','.join(fnames)
    >          cstr = 'lambda %s:(lambda x:%sx%s)' % (args, call, ')'*nfunc)
    >          composer = _cache[nfunc] = eval(cstr)
    >          return composer
    >
    > def compose(*functions):
    >      "compose(f1, ..., fn) -> lambda x: f1(f2(...fn(x)...))"
    >      return getcomposer(len(functions))(*functions)
    >
    > # Test
    >
    > def double(x): return 2*x
    > def square(x): return x**2
    > def succ(x): return x+1
    >
    > f1 = compose(double, square, succ, float)
    > f2 = lambda x: double(square(succ(float(x))))
    >
    > def benchmark(f, n=1000000):
    >      from time import time
    >      from itertools import imap
    >      t0 = time()
    >      for _ in imap(f1, xrange(n)): pass
    >      t1 = time()
    >      return t1-t0
    >
    > print 'compose', benchmark(f1)
    > print 'lambda ', benchmark(f2)
    > ----------------------------------
    >
    > marigold:python arno$ python -i simple_compose.py
    > compose 1.84630298615
    > lambda  1.86365509033
    >  >>> import dis
    >  >>> dis.dis(f1)
    >    1           0 LOAD_DEREF               0 (f0)
    >                3 LOAD_DEREF               3 (f1)
    >                6 LOAD_DEREF               1 (f2)
    >                9 LOAD_DEREF               2 (f3)
    >               12 LOAD_FAST                0 (x)
    >               15 CALL_FUNCTION            1
    >               18 CALL_FUNCTION            1
    >               21 CALL_FUNCTION            1
    >               24 CALL_FUNCTION            1
    >               27 RETURN_VALUE
    >  >>> dis.dis(f2)
    >   23           0 LOAD_GLOBAL              0 (double)
    >                3 LOAD_GLOBAL              1 (square)
    >                6 LOAD_GLOBAL              2 (succ)
    >                9 LOAD_GLOBAL              3 (float)
    >               12 LOAD_FAST                0 (x)
    >               15 CALL_FUNCTION            1
    >               18 CALL_FUNCTION            1
    >               21 CALL_FUNCTION            1
    >               24 CALL_FUNCTION            1
    >               27 RETURN_VALUE
    >
    > f1 and f2 are almost exaclty the same but array lookups (LOAD_DEREFs)
    > in f1 replace dictionary lookups (LOAD_GLOBALs) in f2.  A C version of
    > 'compose' could easily be written that doesn't require the use of a
    > python lambda-function (as created by 'getcomposer').
    >
    > --
    > Arnaud


    def compose( funcs ):
    def reccompose( *args ):
    return compose( funcs[:-1] )( funcs[-1]( *args ) ) if funcs else
    funcs[0]( *args )
    return reccompose
    , Feb 16, 2008
    #2
    1. Advertising

  3. Arnaud Delobelle

    Guest

    > def compose( funcs ):
    >    def reccompose( *args ):
    >       return compose( funcs[:-1] )( funcs[-1]( *args ) ) if funcs else
    > funcs[0]( *args )
    >    return reccompose- Hide quoted text -


    Which was, if funcs> 1, which is len( funcs )> 1.
    >>> [1]>0

    Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    TypeError: unorderable types: list() > int()
    , Feb 16, 2008
    #3
  4. Arnaud Delobelle

    Boris Borcic Guest

    wrote:
    > On Feb 16, 3:47 pm, Arnaud Delobelle <> wrote:
    >> Hi all,
    >>
    >> Recently there was a thread about function composition in Python (and
    >> this was probably not the first). The fast way to create a
    >> (anonymous) composite function
    >>
    >> f1 o f2 o ... o fn
    >>
    >> in Python is via
    >>
    >> lambda x: f1(f2(...fn(x)...)),
    >>
    >> but according to some this is neither the most compact nor the most
    >> readable. Below I define a 'compose' function such that the above can
    >> be written
    >>
    >> compose(f1, f2, ...., fn),
    >>
    >> the resulting function being as fast as the lambda version (or maybe
    >> faster?). 'getcomposer' is a helper function (which in most cases
    >> will amount to a dictionary lookup).
    >>
    >> ----------------------------------
    >> def getcomposer(nfunc, _cache={}):
    >> "getcomposer(n) -> lambda f1, ..., fn:(lambda x: f1(...fn(x)...))"
    >> try:
    >> return _cache[nfunc]
    >> except KeyError:
    >> fnames = ['f%s' % i for i in range(nfunc)]
    >> call = ''.join('%s(' % f for f in fnames)
    >> args = ','.join(fnames)
    >> cstr = 'lambda %s:(lambda x:%sx%s)' % (args, call, ')'*nfunc)
    >> composer = _cache[nfunc] = eval(cstr)
    >> return composer
    >>
    >> def compose(*functions):
    >> "compose(f1, ..., fn) -> lambda x: f1(f2(...fn(x)...))"
    >> return getcomposer(len(functions))(*functions)
    >>
    >> # Test
    >>
    >> def double(x): return 2*x
    >> def square(x): return x**2
    >> def succ(x): return x+1
    >>
    >> f1 = compose(double, square, succ, float)
    >> f2 = lambda x: double(square(succ(float(x))))
    >>
    >> def benchmark(f, n=1000000):
    >> from time import time
    >> from itertools import imap
    >> t0 = time()
    >> for _ in imap(f1, xrange(n)): pass
    >> t1 = time()
    >> return t1-t0
    >>
    >> print 'compose', benchmark(f1)
    >> print 'lambda ', benchmark(f2)
    >> ----------------------------------
    >>
    >> marigold:python arno$ python -i simple_compose.py
    >> compose 1.84630298615
    >> lambda 1.86365509033
    >> >>> import dis
    >> >>> dis.dis(f1)

    >> 1 0 LOAD_DEREF 0 (f0)
    >> 3 LOAD_DEREF 3 (f1)
    >> 6 LOAD_DEREF 1 (f2)
    >> 9 LOAD_DEREF 2 (f3)
    >> 12 LOAD_FAST 0 (x)
    >> 15 CALL_FUNCTION 1
    >> 18 CALL_FUNCTION 1
    >> 21 CALL_FUNCTION 1
    >> 24 CALL_FUNCTION 1
    >> 27 RETURN_VALUE
    >> >>> dis.dis(f2)

    >> 23 0 LOAD_GLOBAL 0 (double)
    >> 3 LOAD_GLOBAL 1 (square)
    >> 6 LOAD_GLOBAL 2 (succ)
    >> 9 LOAD_GLOBAL 3 (float)
    >> 12 LOAD_FAST 0 (x)
    >> 15 CALL_FUNCTION 1
    >> 18 CALL_FUNCTION 1
    >> 21 CALL_FUNCTION 1
    >> 24 CALL_FUNCTION 1
    >> 27 RETURN_VALUE
    >>
    >> f1 and f2 are almost exaclty the same but array lookups (LOAD_DEREFs)
    >> in f1 replace dictionary lookups (LOAD_GLOBALs) in f2. A C version of
    >> 'compose' could easily be written that doesn't require the use of a
    >> python lambda-function (as created by 'getcomposer').
    >>
    >> --
    >> Arnaud

    >
    > def compose( funcs ):
    > def reccompose( *args ):
    > return compose( funcs[:-1] )( funcs[-1]( *args ) ) if funcs else
    > funcs[0]( *args )
    > return reccompose



    >>> def compose( *funcs ):

    def reccompose( *args ):
    return compose( funcs[:-1] )( funcs[-1]( *args ) ) if funcs else funcs[0]( *args )
    return reccompose

    >>> f3 = compose(double, square, succ, float)
    >>> import dis
    >>> dis.dis(f3)

    3 0 LOAD_DEREF 0 (funcs)
    3 JUMP_IF_FALSE 33 (to 39)
    6 POP_TOP
    7 LOAD_GLOBAL 0 (compose)
    10 LOAD_DEREF 0 (funcs)
    13 LOAD_CONST 1 (-1)
    16 SLICE+2
    17 CALL_FUNCTION 1
    20 LOAD_DEREF 0 (funcs)
    23 LOAD_CONST 1 (-1)
    26 BINARY_SUBSCR
    27 LOAD_FAST 0 (args)
    30 CALL_FUNCTION_VAR 0
    33 CALL_FUNCTION 1
    36 JUMP_FORWARD 14 (to 53)
    >> 39 POP_TOP

    40 LOAD_DEREF 0 (funcs)
    43 LOAD_CONST 2 (0)
    46 BINARY_SUBSCR
    47 LOAD_FAST 0 (args)
    50 CALL_FUNCTION_VAR 0
    >> 53 RETURN_VALUE



    Mmmhhh...
    Boris Borcic, Feb 16, 2008
    #4
  5. Arnaud Delobelle

    Guest

    On Feb 16, 5:57 pm, Boris Borcic <> wrote:
    > wrote:
    > > On Feb 16, 3:47 pm, Arnaud Delobelle <> wrote:
    > >> Hi all,

    >
    > >> Recently there was a thread about function composition in Python (and
    > >> this was probably not the first).  The fast way to create a
    > >> (anonymous) composite function

    >
    > >>      f1 o f2 o ... o fn

    >
    > >> in Python is via

    >
    > >>      lambda x: f1(f2(...fn(x)...)),

    >
    > >> but according to some this is neither the most compact nor the most
    > >> readable.  Below I define a 'compose' function such that the above can
    > >> be written

    >
    > >>      compose(f1, f2, ...., fn),

    >
    > >> the resulting function being as fast as the lambda version (or maybe
    > >> faster?).  'getcomposer' is a helper function (which in most cases
    > >> will amount to a dictionary lookup).

    >
    > >> ----------------------------------
    > >> def getcomposer(nfunc, _cache={}):
    > >>      "getcomposer(n) -> lambda f1, ..., fn:(lambda x: f1(...fn(x)....))"
    > >>      try:
    > >>          return _cache[nfunc]
    > >>      except KeyError:
    > >>          fnames = ['f%s' % i for i in range(nfunc)]
    > >>          call = ''.join('%s(' % f for f in fnames)
    > >>          args = ','.join(fnames)
    > >>          cstr = 'lambda %s:(lambda x:%sx%s)' % (args, call, ')'*nfunc)
    > >>          composer = _cache[nfunc] = eval(cstr)
    > >>          return composer

    >
    > >> def compose(*functions):
    > >>      "compose(f1, ..., fn) -> lambda x: f1(f2(...fn(x)...))"
    > >>      return getcomposer(len(functions))(*functions)

    >
    > >> # Test

    >
    > >> def double(x): return 2*x
    > >> def square(x): return x**2
    > >> def succ(x): return x+1

    >
    > >> f1 = compose(double, square, succ, float)
    > >> f2 = lambda x: double(square(succ(float(x))))

    >
    > >> def benchmark(f, n=1000000):
    > >>      from time import time
    > >>      from itertools import imap
    > >>      t0 = time()
    > >>      for _ in imap(f1, xrange(n)): pass
    > >>      t1 = time()
    > >>      return t1-t0

    >
    > >> print 'compose', benchmark(f1)
    > >> print 'lambda ', benchmark(f2)
    > >> ----------------------------------

    >
    > >> marigold:python arno$ python -i simple_compose.py
    > >> compose 1.84630298615
    > >> lambda  1.86365509033
    > >>  >>> import dis
    > >>  >>> dis.dis(f1)
    > >>    1           0 LOAD_DEREF               0 (f0)
    > >>                3 LOAD_DEREF               3 (f1)
    > >>                6 LOAD_DEREF               1 (f2)
    > >>                9 LOAD_DEREF               2 (f3)
    > >>               12 LOAD_FAST                0 (x)
    > >>               15 CALL_FUNCTION            1
    > >>               18 CALL_FUNCTION            1
    > >>               21 CALL_FUNCTION            1
    > >>               24 CALL_FUNCTION            1
    > >>               27 RETURN_VALUE
    > >>  >>> dis.dis(f2)
    > >>   23           0 LOAD_GLOBAL              0 (double)
    > >>                3 LOAD_GLOBAL              1 (square)
    > >>                6 LOAD_GLOBAL              2 (succ)
    > >>                9 LOAD_GLOBAL              3 (float)
    > >>               12 LOAD_FAST                0 (x)
    > >>               15 CALL_FUNCTION            1
    > >>               18 CALL_FUNCTION            1
    > >>               21 CALL_FUNCTION            1
    > >>               24 CALL_FUNCTION            1
    > >>               27 RETURN_VALUE

    >
    > >> f1 and f2 are almost exaclty the same but array lookups (LOAD_DEREFs)
    > >> in f1 replace dictionary lookups (LOAD_GLOBALs) in f2.  A C version of
    > >> 'compose' could easily be written that doesn't require the use of a
    > >> python lambda-function (as created by 'getcomposer').

    >
    > >> --
    > >> Arnaud

    >
    > > def compose( funcs ):
    > >    def reccompose( *args ):
    > >       return compose( funcs[:-1] )( funcs[-1]( *args ) ) if funcs else
    > > funcs[0]( *args )
    > >    return reccompose

    >
    >  >>> def compose( *funcs ):
    >         def reccompose( *args ):
    >                 return compose( funcs[:-1] )( funcs[-1]( *args ) ) if funcs else funcs[0]( *args )
    >         return reccompose
    >
    >  >>> f3 = compose(double, square, succ, float)
    >  >>> import dis
    >  >>> dis.dis(f3)
    >    3           0 LOAD_DEREF               0 (funcs)
    >                3 JUMP_IF_FALSE           33 (to 39)
    >                6 POP_TOP
    >                7 LOAD_GLOBAL              0 (compose)
    >               10 LOAD_DEREF               0 (funcs)
    >               13 LOAD_CONST               1 (-1)
    >               16 SLICE+2
    >               17 CALL_FUNCTION            1
    >               20 LOAD_DEREF               0 (funcs)
    >               23 LOAD_CONST               1 (-1)
    >               26 BINARY_SUBSCR
    >               27 LOAD_FAST                0 (args)
    >               30 CALL_FUNCTION_VAR        0
    >               33 CALL_FUNCTION            1
    >               36 JUMP_FORWARD            14 (to 53)
    >          >>   39 POP_TOP
    >               40 LOAD_DEREF               0 (funcs)
    >               43 LOAD_CONST               2 (0)
    >               46 BINARY_SUBSCR
    >               47 LOAD_FAST                0 (args)
    >               50 CALL_FUNCTION_VAR        0
    >          >>   53 RETURN_VALUE
    >
    > Mmmhhh...- Hide quoted text -
    >
    > - Show quoted text -


    OOOOOOwwwwwwww! <Sulks off to lick wounds.>
    , Feb 17, 2008
    #5
    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. Alan G Isaac

    Pythonic function composition

    Alan G Isaac, Oct 25, 2004, in forum: Python
    Replies:
    6
    Views:
    424
    Lonnie Princehouse
    Oct 25, 2004
  2. Replies:
    10
    Views:
    1,220
    Big K
    Feb 2, 2005
  3. Kay Schluehr
    Replies:
    10
    Views:
    541
    Kay Schluehr
    Feb 4, 2008
  4. Dr Mephesto

    App idea, Any idea on implementation?

    Dr Mephesto, Feb 4, 2008, in forum: Python
    Replies:
    3
    Views:
    702
    Dennis Lee Bieber
    Feb 5, 2008
  5. Replies:
    0
    Views:
    623
Loading...

Share This Page