Python: nested lambdas - `s_push: parser stack overflow memory error`

Question

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

I ended up in 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) 

A number from zero to fifteen works fine, but if I try to create the number 100, the file will not be launched due to the following error:

s_push: parser stack overflow
Memoryerror

I need to comment on this so that the file generally runs.

So sucks - is there any way to limit this so that I can arbitrarily insert lambdas and function calls without losing Python and running out of memory?

Or, alternatively, is there any trick of lambda calculus that I can use to express the number 100 without having a lot of nested functions?

Answer 1

express the number 100 without having 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 >>> 

Answer 2

This seems to be impossible without recompiling Python. The parser stack size is set with the MAXSTACK constant in parser.h . You can 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 .

Answer 3

From the point of view of lambda calculus, incrementing a number can be done using the following function:

 succ = lambda n: lambda p: lambda x: p(n(p)(x)) 

Then one = succ(zero) , two = succ(one) , etc.