An idea for fast function composition

[Boris Borcic]

castironpi at gmail.com wrote:
> On Feb 16, 3:47 pm, Arnaud Delobelle <arno... at googlemail.com> 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...