Path: csiph.com!optima2.xanadu-bbs.net!xanadu-bbs.net!2.eu.feeder.erje.net!feeder.erje.net!1.eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed7.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.000 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'else:': 0.03; 'elif': 0.04; '(even': 0.05; 'none:': 0.05; 'true)': 0.07; 'ugly': 0.07; '(none,': 0.09; 'false)': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'subject:module': 0.09; 'jan': 0.11; 'syntax': 0.13; 'def': 0.13; 'fn)': 0.16; 'looping': 0.16; 'loops': 0.16; 'received:80.91.229.3': 0.16; 'received:plane.gmane.org': 0.16; 'reedy': 0.16; 'sense,': 0.16; 'syntactical': 0.16; 'wrote:': 0.16; 'example.': 0.18; '%s"': 0.22; 'am,': 0.23; 'needed.': 0.23; 'header:In-Reply-To:1': 0.24; 'header:User-Agent:1': 0.26; 'example': 0.26; 'header:X -Complaints-To:1': 0.26; 'opposed': 0.27; 'raise': 0.29; 'another': 0.32; 'core': 0.32; 'to:addr:python-list': 0.36; 'pm,': 0.36; 'subject:: ': 0.37; 'received:org': 0.37; 'enough': 0.39; 'subject:-': 0.39; 'to:addr:python.org': 0.40; 'easy': 0.60; 'here': 0.66; '2:02': 0.84; 'odd,': 0.84; 'pardon': 0.84; 'wow': 0.84; 'ethan': 0.91; 'furman': 0.91; 'received:fios.verizon.net': 0.91 X-Injected-Via-Gmane: http://gmane.org/ To: python-list@python.org From: Terry Reedy Subject: Re: A new module for performing tail-call elimination Date: Thu, 16 Jul 2015 15:45:45 -0400 References: <55a3dcd9$0$3024$426a34cc@news.free.fr> <55a76628$0$2846$c3e8da3$76491128@news.astraweb.com> <55A78A42.4090506@rece.vub.ac.be> <55A7B309.8080903@rece.vub.ac.be> <55A7F1A7.9000203@stoneleaf.us> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Gmane-NNTP-Posting-Host: pool-98-114-97-173.phlapa.fios.verizon.net User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:38.0) Gecko/20100101 Thunderbird/38.1.0 In-Reply-To: <55A7F1A7.9000203@stoneleaf.us> X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.20+ Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 33 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1437075969 news.xs4all.nl 2874 [2001:888:2000:d::a6]:53475 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:93957 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