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?
here you go:
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 .From the lambda-calculus standpoint, incrementing a number can be done with the following function:
Then,
one = succ(zero)
,two = succ(one)
, and so forth.