A new module for performing tail-call elimination
Terry Reedy
tjreedy at udel.edu
Thu Jul 16 15:45:45 EDT 2015
On 7/16/2015 2:02 PM, Ethan Furman wrote:
> On 07/16/2015 06:35 AM, Antoon Pardon wrote:
>> Here is one way to do the odd, even example.
>>
>> def even(n):
>> return odd_even('even', n)
>>
>> def odd(n):
>> return odd_even('odd', n)
>>
>> def odd_even(fn, n):
>> while fn is not None:
>> if fn == 'even':
>> fn, n = (None, True) if n == 0 else ('odd', n - 1)
>> elif fn == 'odd':
>> fn, n = (None, False) if n == 0 else ('even', n - 1)
>> else:
>> raise ValueError("Unknown state: %s" % fn)
>> return n
>
> Wow -- definitely uglier and less easy to understand than the original
> (even if the original had had the error-checking).
What you call ugly is an example of the core of the proof that
alternation and indefinite while looping are enough for turing
completeness, and that no recursive syntax is needed. Another way to
put it is that while loops perform recursion in the operational sense,
as opposed to the syntactical sense.
--
Terry Jan Reedy
More information about the Python-list
mailing list