Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #93765 > unrolled thread

Re: Possibly Pythonic Tail Call Optimization (TCO/TRE)

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Ethan Furman <ethan@stoneleaf.us> - 2015-07-13 10:38 -0700
    Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Marko Rauhamaa <marko@pacujo.net> - 2015-07-13 22:07 +0300
      Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Terry Reedy <tjreedy@udel.edu> - 2015-07-13 23:36 -0400

#93765 — Re: Possibly Pythonic Tail Call Optimization (TCO/TRE)

Antoon,

I think Chris is arguing in good faith; certainly asking for examples should be a reasonable request.

Even if he is not, we would have better discussions and other participants would learn more if you act like he is.  I would love to see good functional examples as it is definitely a weak spot for me.

--
~Ethan~

[toc] | [next] | [standalone]

#93766

Ethan Furman <ethan@stoneleaf.us>:

> I would love to see good functional examples as it is definitely a
> weak spot for me.

Oh, if you want to go functional, you should look at idiomatic Scheme
code:

========================================================================
(define (common-prefix-length bytes-a bytes-b)
  (let loop ((list-a (string->list bytes-a))
             (list-b (string->list bytes-b))
             (common-length 0))
    (cond
     ((null? list-a) common-length)
     ((null? list-b) common-length)
     ((= (car list-a) (car list-b))
      (loop (cdr list-a) (cdr list-b) (+ common-length 8)))
     (else
      (+ common-length
         (vector-ref bit-match
                     (- 8 (integer-length (logxor (car list-a)
                                                  (car list-b))))))))))
========================================================================

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)
========================================================================


Marko

[toc] | [prev] | [next] | [standalone]

#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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web