Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!1.eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed8.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Terry Reedy <tjreedy@udel.edu>
Subject: Re: Possibly Pythonic Tail Call Optimization (TCO/TRE)
Date: Mon, 13 Jul 2015 23:36:44 -0400
References: <CAD+URuj-4e62-9hvpiLsrBP1M6kXRyZhZ6XyL01gWWnDoShvNg@mail.gmail.com> <CAPTjJmrnd2cdA75ROZUKsJfYMdYUXkxRbEN50UE_-r0Jg=c5nQ@mail.gmail.com> <55A3A853.4040006@rece.vub.ac.be> <CAPTjJmr92j+2DDPsZxynoHyZTTCpc-48cWCVrx_fT3dA0j_Osg@mail.gmail.com> <55A3C366.6060602@rece.vub.ac.be> <CAPTjJmqHaJy1jHJTATB+iqzwMNawXCqH28rFmYKC06vqvCquqQ@mail.gmail.com> <55A3CE62.6060304@rece.vub.ac.be> <mailman.471.1436809101.3674.python-list@python.org> <87r3obev0s.fsf@elektro.pacujo.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:38.0) Gecko/20100101 Thunderbird/38.1.0
In-Reply-To: <87r3obev0s.fsf@elektro.pacujo.net>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.476.1436845030.3674.python-list@python.org>
Lines: 56
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:93774

On 7/13/2015 3:07 PM, Marko Rauhamaa wrote:

> Or, translated into (non-idiomatic) Python code:
>
> ========================================================================
> def common_prefix_length(bytes_a, bytes_b):
>      def loop(list_a, list_b, common_length):
>          if not list_a:
>              return common_length
>          if not list_b:
>              return common_length
>          if list_a[0] == list_b[0]:
>              return loop(list_a[1:], list_b[1:], common_length + 8)
>          return common_length + \
>                 bit_match[8 - integer_length(list_a[0] ^ list_b[0])]
>      return loop(bytes_a, bytes_b, 0)
> ========================================================================

This is an interesting challenge for conversion.  The straightforward 
while loop conversion is (untested, obviously, without the auxiliary 
functions):

def common_prefix_length(bytes_a, bytes_b):
     length = 0
     while bytes_a and bytes_b and bytes_a[0] == bytes_b[0]:
         length += 8
         bytes_a, bytes_b = bytes_a[1:], bytes_b[1:]
     if not bytes_a or not bytes_b:
         return length
     else:
         return common_length + bit_match[
             8 - integer_length(bytes_a[0] ^ bytes_b[0])]

Using a for loop and zip to do the parallel iteration for us and avoid 
the list slicing, which is O(n) versus the O(1) lisp (cdr bytes), I 
believe the following is equivalent.

def common_prefix_length(bytes_a, bytes_b):
     length = 0
     for a, b in zip(bytes_a, bytes_b):
         if a == b:
             length += 8
         else:
             return length + bit_match[8 - integer_length(a ^ b)]
     else:
         # short bytes is prefix of longer bytes
         return length

I think this is much clearer than either recursion or while loop.  It is 
also more general, as the only requirement on bytes_a and bytes_b is 
that they be iterables of bytes with a finite common_prefix, and not 
necessarily sequences with slicing or even indexing.

-- 
Terry Jan Reedy