Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Python: nested lambdas -- `s_push: parser stack overflow Memory Error`

I recently stumbled across this article which describes how to code FizzBuzz using only Procs in Ruby, and since I was bored, thought it would be neat to try and implement the same thing in Python using lambdas.

I got to the section where you create numbers using nested functions, and wrote the following Python script:

#!/usr/bin/env python

zero  = lambda p : (lambda x: x)
one   = lambda p : (lambda x: p(x))
two   = lambda p : (lambda x: p(p(x)))
three = lambda p : (lambda x: p(p(p(x))))
five  = lambda p: (lambda x: p(p(p(p(p(x))))))

fifteen = lambda p : (lambda x: p(p(p(p(p( \
                                p(p(p(p(p( \
                                p(p(p(p(p(x))))))))))))))))


hundred = lambda p: (lambda x: p(p(p(p(p(p(p(p(p(p( \
                               p(p(p(p(p(p(p(p(p(p( \
                               p(p(p(p(p(p(p(p(p(p( \
                               p(p(p(p(p(p(p(p(p(p( \
                               p(p(p(p(p(p(p(p(p(p( \
                               p(p(p(p(p(p(p(p(p(p( \
                               p(p(p(p(p(p(p(p(p(p( \
                               p(p(p(p(p(p(p(p(p(p( \
                               p(p(p(p(p(p(p(p(p(p( \
                               p(p(p(p(p(p(p(p(p(p(x)))))))))))))))))))))))))))) \
                                                     ))))))))))))))))))))))))))) \
                                                     ))))))))))))))))))))))))))) \
                                                     )))))))))))))))))))

def to_int(func):
    return func(lambda n: n + 1)(0)

print to_int(zero)
print to_int(one)
print to_int(two)
print to_int(three)
print to_int(five)
print to_int(fifteen)
print to_int(hundred)

Numbers zero through fifteen works fine, but if I try creating the number 100, the file won't run due to the following error:

s_push: parser stack overflow
MemoryError

I have to comment it out in order for the file to run at all.

This sort of sucks -- is there any way around this limitation so that I can arbitrarily nest lambdas and function calls without Python falling over and running out of memory?

Or alternatively, is there some kind of lambda-calculus trick I can use to express the number 100 without having so many nested functions?

like image 745
Michael0x2a Avatar asked Oct 22 '12 06:10

Michael0x2a


2 Answers

express the number 100 without having so many nested functions?

here you go:

>>> test = lambda f: f(lambda x: x + 1)(0)
>>> z = lambda f: lambda x: x
>>> test(z)
0
>>> succ = lambda n: lambda f: lambda x: f(n(f)(x))
>>> _1 = succ(z)
>>> test(_1)
1
>>> _2 = succ(_1)
>>> test(_2)
2
>>> plus = lambda m: lambda n: lambda f: lambda x: m(f)(n(f)(x))
>>> _3 = plus(_1)(_2)
>>> test(_3)
3
>>> mult = lambda m: lambda n: lambda f: lambda x: m(n(f))(x)
>>> _6 = mult(_2)(_3)
>>> test(_6)
6
>>> _5 = plus(_2)(_3)
>>> _25 = mult(_5)(_5)
>>> _4 = plus(_2)(_2)
>>> _100 = mult(_25)(_4)
>>> test(_100)
100
>>> 
like image 148
georg Avatar answered Nov 14 '22 13:11

georg


It looks like it's not possible without recompiling Python. The parser stack size is set with the constant MAXSTACK in parser.h. You could increase this value and recompile to increase the limit. See http://bugs.python.org/issue3971 and http://mail.python.org/pipermail/python-list/2012-March/621555.html .

like image 7
BrenBarn Avatar answered Nov 14 '22 13:11

BrenBarn