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

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

Tail recursion to while iteration in 2 easy steps

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

Contents

  Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-01 17:30 -0400
    Re: Tail recursion to while iteration in 2 easy steps rusi <rustompmody@gmail.com> - 2013-10-01 22:16 -0700
      Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-02 10:23 +0200
        Re: Tail recursion to while iteration in 2 easy steps rusi <rustompmody@gmail.com> - 2013-10-02 06:29 -0700
      Re: Tail recursion to while iteration in 2 easy steps Ravi Sahni <ganeshsahni07@gmail.com> - 2013-10-03 22:57 +0530
        Re: Tail recursion to while iteration in 2 easy steps rusi <rustompmody@gmail.com> - 2013-10-04 03:52 -0700
    Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-02 10:17 +0200
      Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-02 11:59 -0700
      Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-02 14:05 -0700
        Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-04 11:49 +0200
          Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-04 10:51 +0000
          Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-04 18:32 -0400
            Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-07 19:15 +0200
              Re: Tail recursion to while iteration in 2 easy steps Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-10-07 19:57 +0200
                Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-08 10:56 +0200
                  Re: Tail recursion to while iteration in 2 easy steps Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-10-08 12:49 +0300
              Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-07 16:42 -0400
              Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-07 17:19 -0400
                Re: Tail recursion to while iteration in 2 easy steps Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2013-10-08 10:41 +0200
              Re: Tail recursion to while iteration in 2 easy steps MRAB <python@mrabarnett.plus.com> - 2013-10-07 22:39 +0100
              Re: Tail recursion to while iteration in 2 easy steps Piet van Oostrum <piet@vanoostrum.org> - 2013-10-07 18:03 -0400
              Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 15:47 -0700
                Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-07 23:50 +0000
                  Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 17:24 -0700
                    Formal-ity and the Church-Turing thesis rusi <rustompmody@gmail.com> - 2013-10-07 20:17 -0700
                      Re: Formal-ity and the Church-Turing thesis Ravi Sahni <ganeshsahni07@gmail.com> - 2013-10-08 10:46 +0530
                        Re: Formal-ity and the Church-Turing thesis rusi <rustompmody@gmail.com> - 2013-10-07 22:44 -0700
                          Re: Formal-ity and the Church-Turing thesis Mark Lawrence <breamoreboy@yahoo.co.uk> - 2013-10-08 07:43 +0100
                          Re: Formal-ity and the Church-Turing thesis Ravi Sahni <ganeshsahni07@gmail.com> - 2013-10-08 18:31 +0530
                            Re: Formal-ity and the Church-Turing thesis rusi <rustompmody@gmail.com> - 2013-10-08 06:33 -0700
                        Re: Formal-ity and the Church-Turing thesis Steven D'Aprano <steve@pearwood.info> - 2013-10-08 07:50 +0000
                          Re: Formal-ity and the Church-Turing thesis Ravi Sahni <ganeshsahni07@gmail.com> - 2013-10-08 18:16 +0530
                            Re: Formal-ity and the Church-Turing thesis Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-08 13:11 +0000
                              Re: Formal-ity and the Church-Turing thesis Robert Day <robertkday@gmail.com> - 2013-10-08 14:25 +0100
                              Re: Formal-ity and the Church-Turing thesis Chris Angelico <rosuav@gmail.com> - 2013-10-09 08:36 +1100
                      Re: Formal-ity and the Church-Turing thesis Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 22:19 -0700
                        Re: Formal-ity and the Church-Turing thesis rusi <rustompmody@gmail.com> - 2013-10-07 23:01 -0700
                          Re: Formal-ity and the Church-Turing thesis Mark Janssen <dreamingforward@gmail.com> - 2013-10-08 10:39 -0700
                  Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 17:16 -0700
                    Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-08 02:36 +0000
                      Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 20:27 -0700
                        Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve@pearwood.info> - 2013-10-08 09:22 +0000
                          Re: Tail recursion to while iteration in 2 easy steps Charles Hixson <charleshixsn@earthlink.net> - 2013-10-09 15:45 -0700
                  Re: Tail recursion to while iteration in 2 easy steps Piet van Oostrum <piet@vanoostrum.org> - 2013-10-07 22:46 -0400
                  Re: Tail recursion to while iteration in 2 easy steps Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-10-08 10:25 +0300
                  Re: Tail recursion to while iteration in 2 easy steps Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-10-08 11:18 +0200
                Re: Tail recursion to while iteration in 2 easy steps Piet van Oostrum <piet@vanoostrum.org> - 2013-10-07 22:45 -0400
                  Re: Tail recursion to while iteration in 2 easy steps Mark Janssen <dreamingforward@gmail.com> - 2013-10-07 20:34 -0700
      Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-02 18:17 -0400
        Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-03 01:24 +0000
          Re: Tail recursion to while iteration in 2 easy steps Dave Angel <davea@davea.name> - 2013-10-03 01:39 +0000
          Re: Tail recursion to while iteration in 2 easy steps MRAB <python@mrabarnett.plus.com> - 2013-10-03 02:46 +0100
            Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-03 02:34 +0000
              Re: Tail recursion to while iteration in 2 easy steps Chris Angelico <rosuav@gmail.com> - 2013-10-03 14:14 +1000
              Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-03 10:16 -0400
              Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-03 15:04 -0400
          Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-02 22:41 -0400
            Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-04 01:30 +0000
          Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-02 23:06 -0400
          Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-03 10:14 -0400
          Literal syntax for frozenset, frozendict (was: Tail recursion to while iteration in 2 easy steps) Ben Finney <ben+python@benfinney.id.au> - 2013-10-04 10:18 +1000
          Re: Literal syntax for frozenset, frozendict Ethan Furman <ethan@stoneleaf.us> - 2013-10-03 18:31 -0700
      Re: Tail recursion to while iteration in 2 easy steps Duncan Booth <duncan.booth@invalid.invalid> - 2013-10-03 14:52 +0000
        Re: Tail recursion to while iteration in 2 easy steps Neil Cerutti <neilc@norwich.edu> - 2013-10-03 16:03 +0000
          Re: Tail recursion to while iteration in 2 easy steps Duncan Booth <duncan.booth@invalid.invalid> - 2013-10-04 10:16 +0000
            Re: Tail recursion to while iteration in 2 easy steps Ian Kelly <ian.g.kelly@gmail.com> - 2013-10-04 04:41 -0600
            Re: Tail recursion to while iteration in 2 easy steps Ian Kelly <ian.g.kelly@gmail.com> - 2013-10-04 04:46 -0600
              Re: Tail recursion to while iteration in 2 easy steps Duncan Booth <duncan.booth@invalid.invalid> - 2013-10-04 11:16 +0000
            Re: Tail recursion to while iteration in 2 easy steps Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-10-04 14:11 +0300
            Re: Tail recursion to while iteration in 2 easy steps Terry Reedy <tjreedy@udel.edu> - 2013-10-04 17:14 -0400
            Re: Tail recursion to while iteration in 2 easy steps Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-10-05 09:39 +0200
            Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-07 17:27 -0400
              Re: Tail recursion to while iteration in 2 easy steps Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-10-08 10:11 +0300
            Re: Tail recursion to while iteration in 2 easy steps Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-10-08 11:43 +0200

Page 1 of 4  [1] 2 3 4  Next page →

#55239 — Tail recursion to while iteration in 2 easy steps

Part of the reason that Python does not do tail call optimization is 
that turning tail recursion into while iteration is almost trivial, once 
you know the secret of the two easy steps. Here it is.

Assume that you have already done the work of turning a body recursive 
('not tail recursive') form like

def fact(n): return 1 if n <= 1 else n * fact(n-1)

into a tail recursion like

def fact(n, _fac=1):
   '''Return factorial for any count n.

   Users are not expected to override private parameter _fac.
   '''
   if n <= 1:
     return _fac
   else:  # optional
     return fact(n-1, n * _fac)

(This conversion nearly requires adding an accumulator parameter, as 
done here.

Turn this into while iteration with two easy steps.

1. If not already done, make if-else a statement, rather than an 
expression, with the recursive call in the if branch. If nothing else, 
just use 'not condition' to invert the condition.

def fact(n, _fac=1):
   if n > 1:  # not n <= 1
     return fact(n-1, n * _fac)
   else:  # optional
     return _fac

While contrary to what is often published, this order makes logical 
sense. The recursive call means 'go to the top of this function with new 
bindings for the parameters'. So put it closest to the top. The base 
case means 'we are done, time to leave'. So put it at the bottom.

2. This order also makes the follow substeps work:
2a. Replace 'if' with 'while'.
2b. Replace the recursive call with multiple assignment, using the 
parameters as targets and the arguments as source.
For our example:

def fact(n, _fac=1):
   while n > 1:
     n, _fac = n-1, n * _fac
   else:
     return _fac

The proof of correctness for this conversion might argue that the 
recursive form is equivalent to the following pseudo-Python:

def fact(n, _fac=1):
   label top
   if n > 1:
     n, _fac = n-1, n * _fac
     goto top
   else:
     return _fac

and that this is equivalent to the real Python with while.

At this point, you call pull the initialization of the private parameter 
into the body, remove the else, and even add a value check.

def fact(n):
   if n < 0 or n != int(n):
     raise ValueError('fact input {} is not a count'.format(n))
   fac = 1
   while n > 1:
     n, fac = n-1, n * fac
   return fac

With care, the multiple-assignment statement can usually be turned into 
multiple assignment statements for greater efficiency.

   fac *= n
   n -= 1

But note that the reverse order would be a bug. So I would not do this, 
especially in more complicated situations, without having tests first.

-- 
Terry Jan Reedy

[toc] | [next] | [standalone]

#55273

On Wednesday, October 2, 2013 3:00:41 AM UTC+5:30, Terry Reedy wrote:
> Part of the reason that Python does not do tail call optimization is 
> that turning tail recursion into while iteration is almost trivial, once 
> you know the secret of the two easy steps. Here it is.

What happens for mutual tail recursive code like this

def isodd(x) : return False if x==0 else iseven(x-1)
def iseven(x): return True if x==0 else isodd(x-1)

----------------
Notes:
1. I am not advocating writing odd/even like the above -- just giving a trivial example
2. General mutual structural (what you call 'body') recursion is more general than mutual tail recursion is more general than single tail recursion.
3. IOW tail recursion optimization is intermediate between the optimization you are showing and the maximally pessimistic implementation -- stack, activation record etc -- of programming languages
4. There is a whole spectrum of such optimizaitons -- 
4a eg a single-call structural recursion example, does not need to push return address on the stack. It only needs to store the recursion depth: 

If zero jump to outside return add; if > 0 jump to internal return address

4b An example like quicksort in which one call is a tail call can be optimized with your optimization and the other, inner one with 4a above

5. Programming language implementations dont do optimizations like TR because these analyses are in themselves hard but because inter-procedural analysis per se is a headache.  For python-like languages its a much bigger headache because the recursive name must be dynamically fetched for every call

6. [Personal pov] TR optimization is not really a big beef for me:
As you can see, it does not figure in the "All things every programmer should learn from FP" list of mine
http://blog.languager.org/2012/10/functional-programming-lost-booty.html

7. Pedagogically, understanding general recursion is far more important than exploiting tail recursion

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

#55287

rusi <rustompmody@gmail.com> writes:

> On Wednesday, October 2, 2013 3:00:41 AM UTC+5:30, Terry Reedy wrote:
>> Part of the reason that Python does not do tail call optimization is 
>> that turning tail recursion into while iteration is almost trivial, once 
>> you know the secret of the two easy steps. Here it is.
>
> What happens for mutual tail recursive code like this
>
> def isodd(x) : return False if x==0 else iseven(x-1)
> def iseven(x): return True if x==0 else isodd(x-1)

It takes one step of inlining to make Terry's technique applicable.

(Actually, out of curiosity, I tried this with gcc 4.6.3: the compiler
does 16 levels of inlining, plus tail call optimization. The final code
has no call.)

-- Alain.

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

#55332

On Wednesday, October 2, 2013 1:53:46 PM UTC+5:30, Alain Ketterlin wrote:
> rusi writes:
> 
> 
> 
> > On Wednesday, October 2, 2013 3:00:41 AM UTC+5:30, Terry Reedy wrote:
> >> Part of the reason that Python does not do tail call optimization is 
> >> that turning tail recursion into while iteration is almost trivial, once 
> >> you know the secret of the two easy steps. Here it is.
> 
> >
> > What happens for mutual tail recursive code like this
> >
> > def isodd(x) : return False if x==0 else iseven(x-1)
> > def iseven(x): return True if x==0 else isodd(x-1)
> 
> 
> It takes one step of inlining to make Terry's technique applicable.

Well I did say my example was trivial!
For a more nontrivial case consider the delta function of an FSM.

The cleanest way of doing it in C is to make one function with a goto label for each state and a goto for each transition

The same thing can be done in a TR optimized language like scheme by making each state into a function and each transition into a TR-call

> 
> 
> 
> (Actually, out of curiosity, I tried this with gcc 4.6.3: the compiler
> does 16 levels of inlining, plus tail call optimization. The final code
> has no call.)

Good to know. 

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

#55426

On Wed, Oct 2, 2013 at 10:46 AM, rusi wrote:
> 4. There is a whole spectrum of such optimizaitons --
> 4a eg a single-call structural recursion example, does not need to push return address on the stack. It only needs to store the recursion depth:
>
> If zero jump to outside return add; if > 0 jump to internal return address
>
> 4b An example like quicksort in which one call is a tail call can be optimized with your optimization and the other, inner one with 4a above

I am interested in studying more this 'whole spectrum of optimizations'
Any further pointers?

Thanks

-- 
Ravi

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

#55471

On Thursday, October 3, 2013 10:57:48 PM UTC+5:30, Ravi Sahni wrote:
> On Wed, Oct 2, 2013 at 10:46 AM, rusi wrote:
> > 4. There is a whole spectrum of such optimizaitons --
> > 4a eg a single-call structural recursion example, does not need to push return address on the stack. It only needs to store the recursion depth:
> >
> > If zero jump to outside return add; if > 0 jump to internal return address
> >
> > 4b An example like quicksort in which one call is a tail call can be optimized with your optimization and the other, inner one with 4a above
> 
> 
> I am interested in studying more this 'whole spectrum of optimizations'
> Any further pointers?

Mmm… Bummer…

There was a book having these -- at least 5-6 different optimizations of which tail-call was the most obvious. Maybe author was McGettrick dont remember for sure... Probably 20 years now!

I'll try and re-remember them and post.

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

#55286

Terry Reedy <tjreedy@udel.edu> writes:

> Part of the reason that Python does not do tail call optimization is
> that turning tail recursion into while iteration is almost trivial,
> once you know the secret of the two easy steps. Here it is.
>
> Assume that you have already done the work of turning a body recursive
> ('not tail recursive') form like
>
> def fact(n): return 1 if n <= 1 else n * fact(n-1)
>
> into a tail recursion like
[...]

How do know that either "<=" or "*" didn't rebind the name "fact" to
something else? I think that's the main reason why python cannot apply
any procedural optimization (even things like inlining are impossible,
or possible only under very conservative assumption, that make it
worthless).

-- Alain.

P/S: don't take me wrong; your explanation is excellent (and very useful
to python programmers). What I say is that it relies on assumptions that
do not apply to python.

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

#55375

>> def fact(n): return 1 if n <= 1 else n * fact(n-1)
>>
>> into a tail recursion like
> [...]
>
> How do know that either "<=" or "*" didn't rebind the name "fact" to
> something else? I think that's the main reason why python cannot apply
> any procedural optimization (even things like inlining are impossible,
> or possible only under very conservative assumption, that make it
> worthless).

It's called "operator precedence".

-- 
MarkJ
Tacoma, Washington

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

#55379

On Wed, Oct 2, 2013 at 1:23 PM, Alain Ketterlin <alain@unistra.fr> wrote:
> On 10/02/2013 08:59 PM, Mark Janssen wrote:
>>>>
>>>> def fact(n): return 1 if n <= 1 else n * fact(n-1)
>>>
>>> How do know that either "<=" or "*" didn't rebind the name "fact" to
>>> something else? I think that's the main reason why python cannot apply
>>> any procedural optimization
>>
>> It's called "operator precedence".
>
> Operator precedence is totally irrelevant here, you misunderstand what
> "bind" means.
>
> Imagine that you call fact(x) where x is an instance of the following class:
>
> class Strange:
>   ...
>   def __le__(dummy):
>     global fact
>     fact = someotherfun # this is "binding"
>     return false
>
> i.e., executing "n<=1" calls __le__, which rebinds the name "fact" to
> someting else. Then, there is no recursive call at all. At the time
> fact(x-1) is executed, "fact" is not the same function any more.
>
> You cannot prevent this in python.


No, but you can't prevent a lot of bad moves in python.  What you just
did there is a total bonehead ("strange"?) of an idea.

-- 
MarkJ
Tacoma, Washington

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

#55464

Mark Janssen <dreamingforward@gmail.com> writes:

>>>>> def fact(n): return 1 if n <= 1 else n * fact(n-1)

>> class Strange:
>>   ...
>>   def __le__(dummy):
>>     global fact
>>     fact = someotherfun # this is "binding"
>>     return false

>> You cannot prevent this in python.

> No, but you can't prevent a lot of bad moves in python.  What you just
> did there is a total bonehead ("strange"?) of an idea.

I think allowing rebinding of function names is extremely strange, even
though it's easier to implement. I tend to agree with you on the quality
of the idea, but optimization has to take this into account (and give
up, usually).

-- Alain.

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

#55469

On Fri, 04 Oct 2013 11:49:26 +0200, Alain Ketterlin wrote:

> I think allowing rebinding of function names is extremely strange,

It's not, it's quite common. Functions in Python are first-class values, 
and we can do things like this:

from somelibrary import somethingwithalonglongname as shortname

def inorder(tree, op=print):
    # Walk the tree in infix order, doing op to each node.
    process(tree.left, op)
    op(tree.payload)
    process(tree.right, op)

_len = len
def len(obj):
    do_something_first()
    return _len(obj)


Now, the first two aren't the same sort of function-rebinding that you're 
talking about, or that were shown in your post, but the third is. What is 
unusual though is rebinding a function from within itself:

def func(arg):
    global func
    do_this(arg)
    def func(arg):
        do_that(arg)


but it's legal and it sometimes can be useful, although it counts as 
"clever code", possibly "too clever".



-- 
Steven

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

#56164

On 10/4/2013 5:49 AM, Alain Ketterlin wrote:

> I think allowing rebinding of function names is extremely strange,

Steven already countered the 'is extremely strange' part by showing that 
such rebinding is common, generally useful, and only occasionally dodgy 
and a candidate for being blocked.

I want to consider here what it would mean to concretely implement the 
abstract notion 'disallow rebinding of function names' and show what 
would be behind calling the idea 'not feasible'.

1. A 'name' is not a 'function name' unless the name is bound, at 
runtime, to a 'function'.

2. A 'function' in Python is not just one class but any callable object 
-- with with a __call__ methods. That comprises an unbounded set.

3. Python does not mandate how namespaces are implemented. CPython uses 
both dicts and, for function local namespaces, internal C arrays. So 
'names' in code can become either string keys for dicts or integer 
indexes for arrays.

4. Rebinding can be explicit ('='), implicit ('import', 'class', 'def'), 
*or hidden* (globals('a') = 1; ob.__dict__('a') = 1). The 'hidden' 
methods are intentional as they are sometimes needed*.  In CPython, 
these forms remain different in the byte code, but it could be 
otherwise. The point is that is may or may not be possible for the 
interpreter to even recognize a 'rebinding' in order to apply any 
rebinding blocking rule.

* There is no trick (that I know of) for hidden rebinding of function 
locals and nonlocals (short of using ctypes), but I am not sure that 
this is a language guarantee. However, I an sure that the absence is 
intentional.

 > even though it's easier to implement.

No kidding.

-- 
Terry Jan Reedy

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

#56317

Terry Reedy <tjreedy@udel.edu> writes:

> On 10/4/2013 5:49 AM, Alain Ketterlin wrote:
>
>> I think allowing rebinding of function names is extremely strange,
>
> Steven already countered the 'is extremely strange' part by showing
> that such rebinding is common, generally useful, and only occasionally
> dodgy and a candidate for being blocked.

I was talking about rebinding a "function name", not about rebinding a
name to a function. Steve's message was pretty clear on this: iirc, his
first two cases were "binding a new name to an existing callable", the
last case (rebinding len) was in line with what I meant (except his code
"saved" the original function).

My example was: the code of "fact" contains a call to "fact", which is
not guaranteed to be bound to the function it appears in. And this
prevents any kind of optimization.

> I want to consider here what it would mean to concretely implement the
> abstract notion 'disallow rebinding of function names' and show what
> would be behind calling the idea 'not feasible'.

Again, I'm more concerned about the function than about the name.

And the fact that "disallow rebinding of function names" is not feasible
in Python is a design choice, not an essential characteristic of every
programming language.

That's fine. My point was: you can't at the same time have full
dynamicity *and* procedural optimizations (like tail call opt).
Everybody should be clear about the trade-off.

> 1. A 'name' is not a 'function name' unless the name is bound, at
> runtime, to a 'function'.
>
> 2. A 'function' in Python is not just one class but any callable
> object -- with with a __call__ methods. That comprises an unbounded
> set.

Right. Then when you do:

     def myfunc(...): ...

myfunc is bound to an callable object. In my example, I was doing the
equivalent to rebinding myfunc, losing the last reference to that piece
of code:

    myfunc = somethingelse

BTW, does the original callable object have a ref counter? Is it garbage
collected in that case? If not, would it be considered a bug?

> 3. Python does not mandate how namespaces are implemented. CPython
> uses both dicts and, for function local namespaces, internal C arrays.
> So 'names' in code can become either string keys for dicts or integer
> indexes for arrays.

Well, yes, but that's an implementation detail, no?

> 4. Rebinding can be explicit ('='), implicit ('import', 'class',
> def'), *or hidden* (globals('a') = 1; ob.__dict__('a') = 1). The
> hidden' methods are intentional as they are sometimes needed*.  In
> CPython, these forms remain different in the byte code, but it could
> be otherwise. The point is that is may or may not be possible for the
> interpreter to even recognize a 'rebinding' in order to apply any
> rebinding blocking rule.

Sure (that's exactly why I said it is easier to implement). If you were
to disallow rebinding of global function names, you would need a proper
notion of global scope and various categories of names, something almost
all compiled languages have.

> * There is no trick (that I know of) for hidden rebinding of function
> locals and nonlocals (short of using ctypes), but I am not sure that
> this is a language guarantee. However, I an sure that the absence is
> intentional.
>
>> even though it's easier to implement.
>
> No kidding.

(See above).

-- Alain.

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

#56325

Op 07-10-13 19:15, Alain Ketterlin schreef:
>> I want to consider here what it would mean to concretely implement the
>> abstract notion 'disallow rebinding of function names' and show what
>> would be behind calling the idea 'not feasible'.
>
> Again, I'm more concerned about the function than about the name.
>
> And the fact that "disallow rebinding of function names" is not feasible
> in Python is a design choice, not an essential characteristic of every
> programming language.
>
> That's fine. My point was: you can't at the same time have full
> dynamicity *and* procedural optimizations (like tail call opt).
> Everybody should be clear about the trade-off.

Your wrong. Full dynamics is not in contradiction with tail call
optimisation. Scheme has already done it for years. You can rebind
names to other functions in scheme and scheme still has working
tail call optimisatiosn.

-- 
Antoon Pardon

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

#56372

Antoon Pardon <antoon.pardon@rece.vub.ac.be> writes:

> Op 07-10-13 19:15, Alain Ketterlin schreef:

[...]
>> That's fine. My point was: you can't at the same time have full
>> dynamicity *and* procedural optimizations (like tail call opt).
>> Everybody should be clear about the trade-off.
>
> Your wrong. Full dynamics is not in contradiction with tail call
> optimisation. Scheme has already done it for years. You can rebind
> names to other functions in scheme and scheme still has working
> tail call optimisatiosn.

See
http://en.wikipedia.org/wiki/Scheme_%28programming_language%29#Lexical_scope

(first sentence, about variable bindings).

-- Alain.

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

#56379

Alain Ketterlin writes:
> Antoon Pardon writes:
> 
> > Op 07-10-13 19:15, Alain Ketterlin schreef:
> 
> [...]
> >> That's fine. My point was: you can't at the same time have full
> >> dynamicity *and* procedural optimizations (like tail call opt).
> >> Everybody should be clear about the trade-off.
> >
> > Your wrong. Full dynamics is not in contradiction with tail call
> > optimisation. Scheme has already done it for years. You can rebind
> > names to other functions in scheme and scheme still has working
> > tail call optimisatiosn.
> 
> See
> http://en.wikipedia.org/wiki/Scheme_%28programming_language%29#Lexical_scope
> 
> (first sentence, about variable bindings).

# ... Scheme is lexically scoped: all possible variable bindings in a
# program unit can be analyzed by reading the text of the program unit
# without consideration of the contexts in which it may be called ...

The actual procedure to be called is still not known at compile time,
in general. It can be a parameter. It needn't even be the value of any
explicit variable (needn't be "bound to a name").

def call(f, a):
   ...
   return f(a)  # tail call
   ...

def wev(...):
   ...
   return (fs if c(k) else gs)[k](a)  # tail call
   ...

In the Scheme reports, a variable is said to be bound to a location,
which is lexically apparent to the language processor; the value is
stored in that location, and assignment to the variable means storing
a new value in that location. It works like Python or Java; Python
just has a different way of talking about how it works - binding names
directly to values in a namespace, and rebinding to different values.

However, Scheme processors know that the local variables are not
accessible from anywhere else but the local code, so there are more
opportunities for compile-time analysis. They can optimize many of
those locations away, for example.

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

#56327

On 10/7/2013 1:15 PM, Alain Ketterlin wrote:
> Terry Reedy <tjreedy@udel.edu> writes:

>> 3. Python does not mandate how namespaces are implemented. CPython
>> uses both dicts and, for function local namespaces, internal C arrays.
>> So 'names' in code can become either string keys for dicts or integer
>> indexes for arrays.
>
> Well, yes, but that's an implementation detail, no?

That is why I switched from 'Python' to 'CPython'. But I note the 
following: in 2.x, 'from mod import *' in a function meant that the 
compile time mapping of name to index could not be used and that a 
fallback to dict was necessary. So another implementation might take the 
easier path and always use a dict for function locals. In 3.x, such 
import are limited to module scope so that functions can always use an 
array and indexes for function locals. So other implementations can take 
the hint and do the same without needing a dict fallback.

In other words, 3.x changed the language to facilitate the 
implementation detail.

-- 
Terry Jan Reedy

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

#56330

On Mon, Oct 7, 2013, at 13:15, Alain Ketterlin wrote:
> That's fine. My point was: you can't at the same time have full
> dynamicity *and* procedural optimizations (like tail call opt).
> Everybody should be clear about the trade-off.

Let's be clear about what optimizations we are talking about. Tail call
optimization, itself, doesn't care _what_ is being called. It can just
as easily mean "erase its own stack frame and replace it with that of
another function" as "reassign the arguments and jump to the top of this
function". Some people have introduced the idea of _further_
optimizations, transforming "near" tail recursion (i.e. return self()+1)
into tail recursion, and _that_ depends on knowing the identity of the
function (though arguably that could be accounted for at the cost of
including dead code for the path that assumes it may have been changed),
but tail call optimization itself does not.

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

#56371

random832@fastmail.us writes:

> On Mon, Oct 7, 2013, at 13:15, Alain Ketterlin wrote:
>> That's fine. My point was: you can't at the same time have full
>> dynamicity *and* procedural optimizations (like tail call opt).
>> Everybody should be clear about the trade-off.
>
> Let's be clear about what optimizations we are talking about. Tail call
> optimization, itself, doesn't care _what_ is being called. It can just
> as easily mean "erase its own stack frame and replace it with that of
> another function" as "reassign the arguments and jump to the top of this
> function". Some people have introduced the idea of _further_
> optimizations, transforming "near" tail recursion (i.e. return self()+1)
> into tail recursion, and _that_ depends on knowing the identity of the
> function (though arguably that could be accounted for at the cost of
> including dead code for the path that assumes it may have been changed),
> but tail call optimization itself does not.

You're right, thanks for the clarification.

-- Alain.

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

#56333

On 07/10/2013 18:57, Antoon Pardon wrote:
> Op 07-10-13 19:15, Alain Ketterlin schreef:
>>> I want to consider here what it would mean to concretely
>>> implement the abstract notion 'disallow rebinding of function
>>> names' and show what would be behind calling the idea 'not
>>> feasible'.
>>
>> Again, I'm more concerned about the function than about the name.
>>
>> And the fact that "disallow rebinding of function names" is not
>> feasible in Python is a design choice, not an essential
>> characteristic of every programming language.
>>
>> That's fine. My point was: you can't at the same time have full
>> dynamicity *and* procedural optimizations (like tail call opt).
>> Everybody should be clear about the trade-off.
>
> Your wrong. Full dynamics is not in contradiction with tail call
> optimisation. Scheme has already done it for years. You can rebind
> names to other functions in scheme and scheme still has working tail
> call optimisatiosn.
>
Consider this code:

def fact(n, acc=1):
    if n <= 1:
        return acc
    return fact(n-1, n*acc)

It compiles to this:

 >>> dis.dis(fact)
   2           0 LOAD_FAST                0 (n)
               3 LOAD_CONST               1 (1)
               6 COMPARE_OP               1 (<=)
               9 POP_JUMP_IF_FALSE       16

   3          12 LOAD_FAST                1 (acc)
              15 RETURN_VALUE

   4     >>   16 LOAD_GLOBAL              0 (fact)
              19 LOAD_FAST                0 (n)
              22 LOAD_CONST               1 (1)
              25 BINARY_SUBTRACT
              26 LOAD_FAST                0 (n)
              29 LOAD_FAST                1 (acc)
              32 BINARY_MULTIPLY
              33 CALL_FUNCTION            2 (2 positional, 0 keyword pair)
              36 RETURN_VALUE

I think that CALL_FUNCTION immediately followed by RETURN_VALUE could
be tail-call optimised by dropping the caller's stack frame provided
that (like in this case) the callee doesn't refer to any name in the
callers stack frame (nonlocal).

You could also consider replacing the caller's stack frame with a
smaller pseudo-frame, perhaps compressing multiple pseudo-frames or
repeated sequences of pseudo-frames into a single pseudo-frame, so that
it could still generate the same traceback as before (or an compressed
traceback like what was discussed on python-ideas in the threads
"Compressing excepthook output" and "Idea: Compressing the stack on the
fly").

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

Page 1 of 4  [1] 2 3 4  Next page →

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

csiph-web