A new module for performing tail-call elimination

Terry Reedy tjreedy at udel.edu
Thu Jul 16 21:45:45 CEST 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