Possibly Pythonic Tail Call Optimization (TCO/TRE)

[Ian Burnette]

Hi there,

First, please forgive me if this is the wrong venue to be suggesting this
idea-- I'm just following the PEP workflow page
.

I've recently been playing around with Clojure, and I really like the way
they've overcome the JVM not supporting TRE. The way Clojure solves this
problem is to have a built in "recur" function that signals to the Clojure
compiler to convert the code to a loop in the JVM. In python we could do
something similar by having a *recur(*args, **kwargs)* function that
removes its parent from the stack and then runs the parent function again
with the given arguments. It would look something like this:

def factorial(n, acc=1):

if n == 0:

return acc

else:

return recur(n-1, acc=(acc*n)) #signals to the interpreter to trigger TRE


# Doesn't overflow the stack!

factorial(3)


I've also created a plugin
 that mocks
this behavior using the try/except looping method that others
 have utilized to implement
TCO into python. Of course, my plugin still requires a decorator and the
overhead of transmitting information through an exception. Implementing
recur with interpreter support should lead to much better performance.

I've read Guido's reasoning against dynamic TCO
,
but I believe many of his concerns can be boiled down to "I don't want the
interpreter doing things the user didn't expect, and I just don't think
this is important enough to affect everyone's experience". This recur
approach solves that by giving functional python users the ability to
explicitly tell the interpreter what they want without changing how other
users interact with the interpreter. Guido also notes that TRE removes
removes stack trace data. While a more subtle garbage collection scheme
would help alleviate this problem, there's really no avoiding this. My only
defense is that this solution is at least explicit, so users should know
that they're implementing code that might produce a completely unhelpful
stack trace.

Thank you for your time and consideration; I hope this was at least
interesting!

All the best,
Ian Burnette

*Ian Burnette*
Python/Django Developer
Cox Media Group
P: 843.478.5026
-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Jussi Piitulainen]

Ian Burnette writes:

> I've recently been playing around with Clojure, and I really like the
> way they've overcome the JVM not supporting TRE. The way Clojure
> solves this problem is to have a built in "recur" function that
> signals to the Clojure compiler to convert the code to a loop in the
> JVM. In python we could do something similar by having a recur(*args,
> **kwargs) function that removes its parent from the stack and then
> runs the parent function again with the given arguments. It would look
> something like this:

where I introduce some indentation:

>   def factorial(n, acc=1):
>  if n == 0:
> return acc
>  else:
> return recur(n-1, acc=(acc*n))
>#signals to the interpreter to trigger TRE

That's oddly restricted to self-calls. To get the real thing, "recur"
should replace "return" - I'm tempted to spell it "recurn" - so the
definition would look like this:

def factorial(n, acc=1):
   if n == 0:
  return acc
   else:
  recur factorial(n-1, acc=(acc*n))

Probably it would still be syntactically restricted to calls - just
guessing what it would and would not be like to have this in Python:

def factorial(n, acc=1):
   recur ( acc if n == 0 else factorial(n-1, acc=(acc*n)) ) #error?

Something similar could be done inside lambda forms, again probably
restricted to calls in value position:

factorial = ( lambda n, acc=1 : #horror?
( acc if n == 0 else rec factorial(n-1, acc=(acc*n)) ))

But I don't think it's a way that's missing, I think it's a will. I know
you know this, and I agree with your point (in a paragraph that I'm not
quoting) that an explicit syntax for "eliminable" tail calls would be,
well, explicit :) so a user of such syntax should at least know why they
are not getting in their stack traces material that they have
specifically requested to not have in their stacks.
-- 
https://mail.python.org/mailman/listinfo/python-list

Interactive, test-driven coding challenges (algorithms and data structures)

[donne . martin]

Repo:
https://github.com/donnemartin/interactive-coding-challenges

Shortlink:
https://bit.ly/git-code 

Hi Everyone,

I created a number of interactive, test-driven coding challenges. I will 
continue to add to the repo on a regular basis. I'm hoping you find it useful 
as a fun, hands-on way to learn or to sharpen your skills on algorithms and 
data structures, while helping yourself prep for coding interviews and coding 
challenges.

Let me know if you have any questions or comments. Contributions are welcome!

-Donne

-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Chris Angelico]

On Sun, Jul 12, 2015 at 8:20 AM, Ian Burnette  wrote:
>
> I've recently been playing around with Clojure, and I really like the way 
> they've overcome the JVM not supporting TRE. The way Clojure solves this 
> problem is to have a built in "recur" function that signals to the Clojure 
> compiler to convert the code to a loop in the JVM. In python we could do 
> something similar by having a recur(*args, **kwargs) function that removes 
> its parent from the stack and then runs the parent function again with the 
> given arguments. It would look something like this:
>
> def factorial(n, acc=1):
> if n == 0:
> return acc
> else:
> return recur(n-1, acc=(acc*n)) #signals to the interpreter to trigger 
> TRE
> # Doesn't overflow the stack!
>
> factorial(3)
>
>
> I've also created a plugin that mocks this behavior using the try/except 
> looping method that others have utilized to implement TCO into python. Of 
> course, my plugin still requires a decorator and the overhead of transmitting 
> information through an exception. Implementing recur with interpreter support 
> should lead to much better performance.
>

When a function is purely tail-recursive like this, it's trivial to
convert it at the source code level:

def factorial(n):
acc = 1
while n > 0:
acc *= n
n -= 1
return acc

The cases that _can't_ be converted this trivially are the ones that
usually can't be converted automatically either - the best case I can
think of is tree traversal, where one of the calls could be tail-call
optimized:

def traverse(node, func):
if node.left: traverse(node.left, func)
func(node)
if node.right: return recur(node.right, func)

(By the way, what happens if you call recur() without returning its result?)

It still needs stack space for all the left calls, so it's not really
benefiting that much from TCO. Where does the advantage show up? Why
is it worth writing your code recursively, only to have it be
implemented iteratively? Warping your code around a recursive solution
to make it into a perfect tail call usually means making it look a lot
less impressive; for instance, the 'acc' parameter in your above code
has no meaning outside of transforming the recursion into tail
recursion.

https://xkcd.com/1270/

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Chris Angelico]

On Mon, Jul 13, 2015 at 9:22 PM, Jussi Piitulainen
 wrote:
> That's oddly restricted to self-calls. To get the real thing, "recur"
> should replace "return" - I'm tempted to spell it "recurn" - so the
> definition would look like this:
>
> def factorial(n, acc=1):
>if n == 0:
>   return acc
>else:
>   recur factorial(n-1, acc=(acc*n))
>
> Probably it would still be syntactically restricted to calls

Huh. Now it looks like the 'exec' operation (the C function and shell
operation, not the Python keyword/function) - it's saying "replace the
current stack frame with _this_", which looks reasonable. It doesn't
have to be recursion. The thing is, you would have to use this ONLY
when you don't care about the current stack frame; so you could do a
logging decorator thus:

def log_calls(func):
@functools.wraps(func)
def wrapped(*a, **kw):
logging.debug("Calling %s(%r, %r)", func.__name__, a, kw)
recur func, a, kw
return wrapped

When an exception occurs inside the wrapped function, the wrapper
won't be visible - but that's not a problem, because it doesn't affect
anything. Like every other tool, it would be something that could
easily be abused, but this actually does justify the removal.

It would almost certainly need to be language syntax. I've done it up
as a keyword that takes "function, args, kwargs" rather than a prefix
on a function call, which emphasizes that the part after it is NOT an
expression. In a sense, it makes a counterpart to lambda - where
lambda takes an expression and turns it into a function, recur takes a
function and treats it as if its body were part of the current
function. Kinda.

Does that make sense to anyone else?

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Antoon Pardon]

On 07/13/2015 01:28 PM, Chris Angelico wrote:
> On Sun, Jul 12, 2015 at 8:20 AM, Ian Burnette  wrote:
>> [ About tail recursion ]
>>
> When a function is purely tail-recursive like this, it's trivial to
> convert it at the source code level:
>
> def factorial(n):
> acc = 1
> while n > 0:
> acc *= n
> n -= 1
> return acc
>
> The cases that _can't_ be converted this trivially are the ones that
> usually can't be converted automatically either - the best case I can
> think of is tree traversal, where one of the calls could be tail-call
> optimized:

This is not true. Tail recursion elimination can always converted
automatically. Otherwise other languages couldn't have implemted it.

> Why is it worth writing your code recursively, only to have it be
> implemented iteratively?

Because sometimes, it is easier to think about the problem recursively.

> Warping your code around a recursive solution
> to make it into a perfect tail call usually means making it look a lot
> less impressive; for instance, 

And sometimes your problem is very easily solved by a number of functions
that tail call each other but in python you will need to warp your code
around an iterative solution, in order to avoid the stack limit.

It seems warping your code is only seen as a problem when going in the
functional direction. Going into the iterative direction may take all
the warping that is needed, without comment.

-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Chris Angelico]

On Mon, Jul 13, 2015 at 10:00 PM, Antoon Pardon
 wrote:
> On 07/13/2015 01:28 PM, Chris Angelico wrote:
>> On Sun, Jul 12, 2015 at 8:20 AM, Ian Burnette  wrote:
>>> [ About tail recursion ]
>>>
>> When a function is purely tail-recursive like this, it's trivial to
>> convert it at the source code level:
>>
>> def factorial(n):
>> acc = 1
>> while n > 0:
>> acc *= n
>> n -= 1
>> return acc
>>
>> The cases that _can't_ be converted this trivially are the ones that
>> usually can't be converted automatically either - the best case I can
>> think of is tree traversal, where one of the calls could be tail-call
>> optimized:
>
> This is not true. Tail recursion elimination can always converted
> automatically. Otherwise other languages couldn't have implemted it.

Yes, when it's in the pure form of an actual tail call. Most recursion
isn't, so you have to warp your code until it is (like adding the
'acc' parameter, which is NOT logically a parameter to the factorial
function).

>> Why is it worth writing your code recursively, only to have it be
>> implemented iteratively?
>
> Because sometimes, it is easier to think about the problem recursively.

Can you give me an example that (a) makes a lot more sense recursively
than iteratively, and (b) involves just one tail call?

>> Warping your code around a recursive solution
>> to make it into a perfect tail call usually means making it look a lot
>> less impressive; for instance,
>
> And sometimes your problem is very easily solved by a number of functions
> that tail call each other but in python you will need to warp your code
> around an iterative solution, in order to avoid the stack limit.

Example, please? In all my Python programming, I've never hit the
stack limit outside of deliberate playing around (or accidental
infinite recursion, which means it's doing its job).

> It seems warping your code is only seen as a problem when going in the
> functional direction. Going into the iterative direction may take all
> the warping that is needed, without comment.

That's because I've never seen code that warps more for iteration than
it does for programming in general. Again, example please?

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Ian Kelly]

On Mon, Jul 13, 2015 at 6:34 AM, Chris Angelico  wrote:
> On Mon, Jul 13, 2015 at 10:00 PM, Antoon Pardon
>  wrote:
>> On 07/13/2015 01:28 PM, Chris Angelico wrote:
>>> Why is it worth writing your code recursively, only to have it be
>>> implemented iteratively?
>>
>> Because sometimes, it is easier to think about the problem recursively.
>
> Can you give me an example that (a) makes a lot more sense recursively
> than iteratively, and (b) involves just one tail call?

Why does (b) matter? If the function has more than one tail call, it
doesn't matter which one you hit -- either way it's a tail call and
the stack frame is no longer needed.
-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Antoon Pardon]

On 07/13/2015 02:34 PM, Chris Angelico wrote:
>
>>> Warping your code around a recursive solution
>>> to make it into a perfect tail call usually means making it look a lot
>>> less impressive; for instance,
>> And sometimes your problem is very easily solved by a number of functions
>> that tail call each other but in python you will need to warp your code
>> around an iterative solution, in order to avoid the stack limit.
> Example, please? In all my Python programming, I've never hit the
> stack limit outside of deliberate playing around (or accidental
> infinite recursion, which means it's doing its job).

I have had to process text coming from a network connection. The data
was mosly unstructered text with some lines that could be used as markers
to proceed through some kind of state machine that indicated how the
following lines needed to be processed. That was easiest written by having
a function for each "state" that would process the next lines until
a marker line was encountered and then call the function corresponding
with the next state. However since a connection could stay active for
days, sooner or later a stack limit would occur if done the natural
recursive way.

>> It seems warping your code is only seen as a problem when going in the
>> functional direction. Going into the iterative direction may take all
>> the warping that is needed, without comment.
> That's because I've never seen code that warps more for iteration than
> it does for programming in general. Again, example please?

And since when is your experience the measure stick for what other people
encounter as problems?

-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Chris Angelico]

On Mon, Jul 13, 2015 at 11:46 PM, Ian Kelly  wrote:
> On Mon, Jul 13, 2015 at 6:34 AM, Chris Angelico  wrote:
>> On Mon, Jul 13, 2015 at 10:00 PM, Antoon Pardon
>>  wrote:
>>> On 07/13/2015 01:28 PM, Chris Angelico wrote:
 Why is it worth writing your code recursively, only to have it be
 implemented iteratively?
>>>
>>> Because sometimes, it is easier to think about the problem recursively.
>>
>> Can you give me an example that (a) makes a lot more sense recursively
>> than iteratively, and (b) involves just one tail call?
>
> Why does (b) matter? If the function has more than one tail call, it
> doesn't matter which one you hit -- either way it's a tail call and
> the stack frame is no longer needed.

Oops. I meant "involves just one point of recursion". When you
traverse a tree, only one can be a tail call, because after the other,
you still have more processing to do. Most problems that I've found to
work recursively and not iteratively have involved multiple branches -
consider a simplistic solution to the Eight Queens problem that places
a queen, then calls itself to place another queen:

def eightqueens(positions=()):
for i in range(8):
if i not in positions:
# TODO: check for the diagonals
result = eightqueens(positions + (i,))
if result: return result
return None

While it can do the classic "call self, return result", it has to
conditionally _not_ do that and keep on going. While this algorithm
can be implemented iteratively, it's a reasonable show-case for
recursion; but not for tail recursion, because one call to
eightqueens() might result in more than one chained call, so I don't
think there's any way for TCO to kick in here.

What I'm asking for is an example of something that can have the tail
calls optimized away, and yet still looks cleaner - preferably,
*significantly* cleaner - in its recursive form than in its
corresponding iterative form. Considering that an iterative function
can maintain state that isn't in the parameters, I'm dubious that such
a thing exists outside of the deranged minds of functional
programmers. (Very much deranged. If you consider that a recursive
factorial just uses addition and subtraction, while an iterative one
can start with "for i in range(n):", you will agree that my
terminology is strictly correct. So there.)

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Chris Angelico]

On Mon, Jul 13, 2015 at 11:55 PM, Antoon Pardon
 wrote:
> On 07/13/2015 02:34 PM, Chris Angelico wrote:
>>
 Warping your code around a recursive solution
 to make it into a perfect tail call usually means making it look a lot
 less impressive; for instance,
>>> And sometimes your problem is very easily solved by a number of functions
>>> that tail call each other but in python you will need to warp your code
>>> around an iterative solution, in order to avoid the stack limit.
>> Example, please? In all my Python programming, I've never hit the
>> stack limit outside of deliberate playing around (or accidental
>> infinite recursion, which means it's doing its job).
>
> I have had to process text coming from a network connection. The data
> was mosly unstructered text with some lines that could be used as markers
> to proceed through some kind of state machine that indicated how the
> following lines needed to be processed. That was easiest written by having
> a function for each "state" that would process the next lines until
> a marker line was encountered and then call the function corresponding
> with the next state. However since a connection could stay active for
> days, sooner or later a stack limit would occur if done the natural
> recursive way.

I'm not sure why the transition to another state has to be recursive.
With most network protocols, you'll end up returning to some kind of
"base state" - maybe there's a header line that says that you're
entering some new mode, which strongly suggests a subroutine call, but
then at the end of that mode, you would return to the normal position
of looking for another header. Alternatively, if the only way you know
you're at the end of one mode is by discovering the beginning of the
next, it's common to be able to have a single primary loop that
dispatches lines appropriately - when it gets the next header, it
sends the entire previous block to its appropriate function, and then
carries on looking for lines of text.

Maybe this is something where previous experience makes you more
comfortable with a particular style, which will mean that functional
idioms will never feel more comfortable to me than iterative ones do,
and vice versa for you. If that's the case, then I'll stick with
Python and Pike, and you can happily use Lisp and Haskell, and neither
of us need be a problem to the other. But honestly, I'm not seeing
anything that requires infinite recursion in your description. And
I've worked with a lot of networking protocols in my time.

>>> It seems warping your code is only seen as a problem when going in the
>>> functional direction. Going into the iterative direction may take all
>>> the warping that is needed, without comment.
>> That's because I've never seen code that warps more for iteration than
>> it does for programming in general. Again, example please?
>
> And since when is your experience the measure stick for what other people
> encounter as problems?

That's why I said "example please?". My experience has not a single
time come across this. If you want to make an assertion that iterative
code requires equivalent warping to tail-recursive code, I want to see
an example of it. Is that difficult?

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Antoon Pardon]

On 07/13/2015 04:05 PM, Chris Angelico wrote:
> On Mon, Jul 13, 2015 at 11:55 PM, Antoon Pardon
>  wrote:
>> On 07/13/2015 02:34 PM, Chris Angelico wrote:
> Warping your code around a recursive solution
> to make it into a perfect tail call usually means making it look a lot
> less impressive; for instance,
 And sometimes your problem is very easily solved by a number of functions
 that tail call each other but in python you will need to warp your code
 around an iterative solution, in order to avoid the stack limit.
>>> Example, please? In all my Python programming, I've never hit the
>>> stack limit outside of deliberate playing around (or accidental
>>> infinite recursion, which means it's doing its job).
>> I have had to process text coming from a network connection. The data
>> was mosly unstructered text with some lines that could be used as markers
>> to proceed through some kind of state machine that indicated how the
>> following lines needed to be processed. That was easiest written by having
>> a function for each "state" that would process the next lines until
>> a marker line was encountered and then call the function corresponding
>> with the next state. However since a connection could stay active for
>> days, sooner or later a stack limit would occur if done the natural
>> recursive way.
> I'm not sure why the transition to another state has to be recursive.

Off course it doesn't has to be recursive. It was just easier/more
natural to do in a recursive way and needed warping to do in an interactive
way.

> Maybe this is something where previous experience makes you more
> comfortable with a particular style, which will mean that functional
> idioms will never feel more comfortable to me than iterative ones do,
> and vice versa for you.

Don't give me that. I have generally no problem solving things in
an iterative way. This problem however was most naturally solved
with a functional approach and I had to warp it in order to fit
an iterative approach.

>  If that's the case, then I'll stick with
> Python and Pike, and you can happily use Lisp and Haskell, and neither
> of us need be a problem to the other. But honestly, I'm not seeing
> anything that requires infinite recursion in your description. And
> I've worked with a lot of networking protocols in my time.

Your moving the goal posts. I only stated that sometimes the problem
is easily solved by a number of fuctions that tail call each other.
That you can warp this into an interative process and so don't
require infinite recursion doesn't contradict that.

 It seems warping your code is only seen as a problem when going in the
 functional direction. Going into the iterative direction may take all
 the warping that is needed, without comment.
>>> That's because I've never seen code that warps more for iteration than
>>> it does for programming in general. Again, example please?
>> And since when is your experience the measure stick for what other people
>> encounter as problems?
> That's why I said "example please?". My experience has not a single
> time come across this. If you want to make an assertion that iterative
> code requires equivalent warping to tail-recursive code, I want to see
> an example of it. Is that difficult?

Oh come on. It was rather obvious that your request for an example was
not meant to learn something new but was meant for you to have a target
to demolish and thus that you would try to mold that target into something
you were familiar with. Which is exactly what you did above.

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: beginners choice: wx or tk?

[Grant Edwards]

On 2015-07-11, Chris Angelico  wrote:
> On Sat, Jul 11, 2015 at 7:28 PM, Ulli Horlacher
> wrote:
>> I want to start a project with python.
>> The program must have a (simple) GUI and must run on Linux and Windows.
>> The last one as standalone executable, created with pyinstaller.
>
> Not sure what your advantage is with pyinstaller, it adds a level of
> complication that doesn't usually justify itself IMO.
>
>> I have already an implementation in perl/tk :
>> http://fex.rus.uni-stuttgart.de/fop/ZAcXSugp/schwuppdiwupp.png
>> http://fex.belwue.de/download/schwuppdiwupp.pl
>>
>> I am not really happy with tk, because it has some bugs, at least its
>> perl integration. I have never used wx.

IMO, tk is quite a bit easier to use than wx for simple apps.

>> What is the recommendation for a python beginner: wx or tk?
>
> Using wxPython means you need another library, while tkinter comes
> with Python.

Tkinter _usually_ comes with Python.  You may run into Linux/Unix
installs that have Python without tk.

> There are some limitations to tk, and I personally don't like its
> style, but if you're wanting to package it up into an EXE, every
> third-party library you add will increase the size of that EXE,
> potentially quite significantly (wxPython will drag in everything
> that it depends on, which IIRC is quite a bit).

Interesting.  My experience was opposite.  When I used to use py2exe,
wx bundles tended to be smaller installs that tkinter apps (at least
for small, simple apps).  It doesn't matter whether the library is
"third party" or not when bundling up a windows app.  All that matters
is the size of the library.  When I compared sizes of farily simple
apps, tkinter apps were quite a bit larger than wx apps.  Don't forget
that tkinter pulls in a complete TCL implementation. 

> There are other choices, too - pygtk/pygobject (GTK) and pyqt (Qt)
> come to mind - is there a particular reason you're limiting the
> question to just wx vs tk?

The last time I checked pygtk on Windows wasn't ready for the real
world, but that was a year or two back. That said, I think pygtk feels
like a much cleaner and more pythonesque API than wx.

> Personally, I quite like GTK, but I don't have much experience with
> either of the Python bindings. Never used wxPython or PyQt.

If it didn't have to run on Windows, I'd pick pygtk over wx.  I've
never tried qt.

-- 
Grant Edwards   grant.b.edwardsYow! Pardon me, but do you
  at   know what it means to be
  gmail.comTRULY ONE with your BOOTH!
-- 
https://mail.python.org/mailman/listinfo/python-list

A new module for performing tail-call elimination

[Th. Baruchel]

Hi, after having spent much time thinking about tail-call elimination
in Python (see for instance http://baruchel.github.io/blog/ ), I finally
decided to write a module for that. You may find it at:

  https://github.com/baruchel/tco

Tail-call elimination is done for tail-recursion as well as for
continuation-passing style (cps) in a consistent syntax for both usages.

Any tail-recursive function having the suitable format for being
embeddable in the Y combinator can be used here with no change at all
(with the main difference that tail-calls will be eliminated), but other
continuations can also be added

The module is available under two forms: traditional python code and cython
compilable code (pre-compiled binaries are also released for the cython
version). Of course the Cython version is quicker and should be preferred
for serious work.

I must admit I haven't browsed much in order to know if similar projects
already exist; I was happy to do it for myself, but I want to share it now
in case other people are interested by it also.

Best regards,

-- 
Thomas Baruchel
-- 
https://mail.python.org/mailman/listinfo/python-list

str.index() and str.find() versus only list.index()

[Roel Schroeven]

Hi,

Quick question: why does str have both index() and find(), while list 
only has index()? Is there a reason for that, or is it just an 
historical accident?



Best regards,
Roel

--
The saddest aspect of life right now is that science gathers knowledge
faster than society gathers wisdom.
  -- Isaac Asimov

Roel Schroeven

--
https://mail.python.org/mailman/listinfo/python-list

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

[Ethan Furman]

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~
--
https://mail.python.org/mailman/listinfo/python-list

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

[Marko Rauhamaa]

Ethan Furman :

> 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
-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Terry Reedy]

On 7/13/2015 7:22 AM, Jussi Piitulainen wrote:

Ian Burnette writes:


A post I did not receive, but want to comment on.


I've recently been playing around with Clojure, and I really like the
way they've overcome the JVM not supporting TRE. The way Clojure
solves this problem is to have a built in "recur" function that
signals to the Clojure compiler to convert the code to a loop in the
JVM.In python we could do something similar


Currently, the only means of affecting compilation of Python code are 
future imports and global and nonlocal declarations. (Coding cookie 
comments affect decoding of python code encoded as bytes, which happens 
before interpretation of the code.)  Functions are called while running, 
after normal compilation.  Python-coded functions are created during 
runtime by executing def statements (although code object are created 
during compilation).


A tre(code) function could be written today that converts a 
tail-recursive body to a while body. It would be used as an alternate 
'decorator' that works on the function text rather than the function 
object.  Example:


tre('''\
def dsum(n, a=0): return dsum(n-1, a+n) if n > 0 else a
'''

In pseudocode (minus error checks and raises) that would work for the 
simple (and normal) case of exactly one tail_recursive call:


def tre(tail_rec_code):
  split tail_rec_code into initial_part (header, docstring,
and initial comments and code before the alternation)
and recursive_alternation
  if recursive_alternation is if-else expression,
convert to if-else statement
  if tail-recursion is in else branch,
invert if condition and switch branch bodies
  replace 'if' with 'while'
  replace tail call with multiple assignment to parameters
(from signature)
  modified_code = inital_part + modified_body
  return exec(modified_code, globals())

In the replacement steps
if n > 1: return fac(n-1, acc*n)
would become
while n > 1: n, acc = n-1, acc*n

If the operations were done with strings, tre would work today and 
indefinitely with any interpreter with standard string operations, exec 
and globals (though in practice I would use re also).  If operations 
were done with ASTs, compile and the ast module (which is subject to 
change) would be required.


>> by having a recur(*args,

**kwargs) function that removes its parent from the stack and then
runs the parent function again with the given arguments.


Ian here somewhat confusingly half switches from loop conversion, which 
saves both space and time, to general tail call elimination, which saves 
space possibly at the cost of more time and less useful or even useless 
tracebacks.  Which is to say, he switches from a tre-only implementation 
to a general tco implementation but uses syntax limited to tre. As Jussi 
notes, a general method should not be so limited.


If one only wants tre, for which traceback compression is often a plus 
rather than a minus, then for automatic conversion, I think the time and 
space efficient loop-conversion should be used.


If the recursion iterates through a collection, which is nearly always 
the case, then a human might convert to a for loop instead of a while 
loop.  The idiomatic example below contains the input check usually left 
out of toy recursion examples.  (Doing the check just once would require 
nesting the recursion within an outer function.)


def fact(n):
if n < 0 or not isinstance(n, int):
raise ValueError('non-negative integer required')
val = 1
for i in range(2, n+1):
val *= i
return val

For loops separate iterating through a collection, which in this case is 
a range of integers, which has a known builtin solution, from processing 
the items produced by the iteration. Recursion and the equivalent while 
loops mix item processing with explicit next-item calculation, which is 
generally collection-class specific.  To write a generic function like 
sum(iterable, start) with recursion, one must explicitly do everything 
that for loop do, which is to call iter, next, and handle StopIteration.


Stack frames, and hence tre and tco, are implementation issues, not 
language issues.  Moreover, these are machine implementation issues, as 
an intelligent human executing Python code should do 'the right thing' 
anyway.


Guido himself has noted that it would be trivial for CPython to optimize 
all tail calls.  But he also noted the cost of sometimes useless 
trackbacks and distraction from using iterables with for loops.


Optimizing specific tail calls is tricker.  For one thing, calls to a 
recursion-replacement function, such as recur, add a stack frame that 
must also be popped. A CPython bytecode manimpuation solution was given 
years ago as a recipe on the ActiveState Python Cookbook site.  MacroPy 
at pypi.python.org "provides a mechanism for user-defined functions 
(macros) to perform transformations on the abstract syntax tree(AST) of 
Python code at module import time".  Among many inclu

A webpy Templetor question

[yongzhi . chen]

Hi all,

I want to display/update several metrics in a normal page (not in a webpy 
form). These metrics got updated every minute and were stored in a log file. I 
prepared a function to open that log file then analyze the last several lines 
to collect them. I want these metrics got updated in every page load/refresh.

The first method I considered is to utilize Templetor 
(http://webpy.org/docs/0.3/templetor).  I used $code block in the template but 
figured out soon that this solution won't work for the security reason. In my 
function I use open which is prohibited by webpy.

Then I thought of `Import functions into templates` 
(https://github.com/webpy/webpy.github.com/blob/master/cookbook/template_import.md).
 In my case, there is no argument for that function. I followed the instruction 
but got the following error.

checknow() takes no arguments (1 given)


#in my application.py:
def checknow():
...
return TN_str

render = web.template.render('templates/',globals={'stat':checknow})

#in the template:
$def with(checknow)
... ...
Test: $stat(checknow)

By the way, how to refer multiple values of the function checknow()? The 
function checknow() should return multiple values in the real case. Could you 
please help me out? Thanks a lot.

Best Regards,
-Yongzhi
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: A webpy Templetor question

[Chris Angelico]

On Tue, Jul 14, 2015 at 9:13 AM,   wrote:
> #in my application.py:
> def checknow():
> ...
> return TN_str
>
> render = web.template.render('templates/',globals={'stat':checknow})
>
> #in the template:
> $def with(checknow)
> ... ...
> Test: $stat(checknow)

You've effectively taken a reference to the checknow function and
given it the name 'stat'. So when you call $stat(), I would expect it
to call checknow() with exactly those arguments. I don't know what
"$def with(checknow)" means, but if you figure out what checknow is
inside there, then you'll know whether you want any argument at all. I
suspect just "$stat()" may well do what you want.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: beginners choice: wx or tk?

[Michael Torrie]

On 07/13/2015 08:42 AM, Grant Edwards wrote:
> If it didn't have to run on Windows, I'd pick pygtk over wx.  I've
> never tried qt.

PyQt is very nice to work with.  In some respects it's not as Pythonic
as PyGTK.  It feels a lot like transliterated C++ code, which it is.
But it's a powerful toolkit and looks great on all supported platforms.
 If the licensing terms of PyQt are not to your liking, PySide is fairly
close to PyQt (a few quirks that can be worked around), though I'm not
sure how much love it's receiving lately.  Like wx, or Gtk, you would
have to ship some extra dlls with your project for Windows and OS X.


-- 
https://mail.python.org/mailman/listinfo/python-list

Re: str.index() and str.find() versus only list.index()

[Ian Kelly]

On Mon, Jul 13, 2015 at 10:56 AM, Roel Schroeven  wrote:
> Hi,
>
> Quick question: why does str have both index() and find(), while list only
> has index()? Is there a reason for that, or is it just an historical
> accident?

Historical accident, I think. If it were to be redone, I doubt that
str.find would exist. The problem with it is that it returns -1 to
indicate that the argument was not found, but -1 is a valid index into
the string. This is a potential source of hard-to-find bugs.

There was a long thread from 2005 on python-dev proposing to remove
str.find in Python 3, but evidently it didn't make the cut:
https://mail.python.org/pipermail/python-dev/2005-August/055704.html
-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Steven D'Aprano]

On Tue, 14 Jul 2015 12:05 am, Chris Angelico wrote:

> If you want to make an assertion that iterative
> code requires equivalent warping to tail-recursive code, I want to see
> an example of it. Is that difficult?

Of course it is. If it wasn't difficult, people would post examples instead
of getting all defensive about being asked for examples.


-- 
Steven

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: str.index() and str.find() versus only list.index()

[Steven D'Aprano]

On Tue, 14 Jul 2015 01:12 pm, Ian Kelly wrote:

> On Mon, Jul 13, 2015 at 10:56 AM, Roel Schroeven 
> wrote:
>> Hi,
>>
>> Quick question: why does str have both index() and find(), while list
>> only has index()? Is there a reason for that, or is it just an historical
>> accident?
> 
> Historical accident, I think. If it were to be redone, I doubt that
> str.find would exist. The problem with it is that it returns -1 to
> indicate that the argument was not found, but -1 is a valid index into
> the string. This is a potential source of hard-to-find bugs.

Correct. But rather than removing it, it would be better to take a leaf out
of re.match's book and return None as the sentinel. That would eliminate
the "using -1 as a valid index" bug.


-- 
Steven

-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Terry Reedy]

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

--
https://mail.python.org/mailman/listinfo/python-list

Re: str.index() and str.find() versus only list.index()

[Ian Kelly]

On Mon, Jul 13, 2015 at 9:23 PM, Steven D'Aprano  wrote:
> On Tue, 14 Jul 2015 01:12 pm, Ian Kelly wrote:
>
>> On Mon, Jul 13, 2015 at 10:56 AM, Roel Schroeven 
>> wrote:
>>> Hi,
>>>
>>> Quick question: why does str have both index() and find(), while list
>>> only has index()? Is there a reason for that, or is it just an historical
>>> accident?
>>
>> Historical accident, I think. If it were to be redone, I doubt that
>> str.find would exist. The problem with it is that it returns -1 to
>> indicate that the argument was not found, but -1 is a valid index into
>> the string. This is a potential source of hard-to-find bugs.
>
> Correct. But rather than removing it, it would be better to take a leaf out
> of re.match's book and return None as the sentinel. That would eliminate
> the "using -1 as a valid index" bug.

I disagree on both counts.

>>> s = 'abc'
>>> s[None:None]
'abc'

Better IMO to just have the one non-redundant method that raises an
exception rather than returning anything that could possibly be
interpreted as a string index.
-- 
https://mail.python.org/mailman/listinfo/python-list

Foo.__new__ is what species of method?

[Ben Finney]

Howdy all,

The Python reference says of a class ‘__new__’ method::

object.__new__(cls[, ...])

Called to create a new instance of class cls. __new__() is a static
method (special-cased so you need not declare it as such) that takes
the class of which an instance was requested as its first argument.

https://docs.python.org/3/reference/datamodel.html#object.__new__>

But a “static method” is described, elsewhere in the documentation
https://docs.python.org/3/library/functions.html#staticmethod>, as
“A static method does not receive an implicit first argument”.

What the ‘__new__’ documentation describes would match a “class method”
https://docs.python.org/3/library/functions.html#classmethod>
“A class method receives the class as implicit first argument”.

I suspect this a bug in the reference documentation for ‘__new__’, and
it should instead say “__new__ is a class method …”. Am I wrong?

-- 
 \“Cooles & Heates: If you want just condition of warm in your |
  `\room, please control yourself.” —air conditioner instructions, |
_o__)Japan |
Ben Finney

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Foo.__new__ is what species of method?

[Steven D'Aprano]

On Tuesday 14 July 2015 14:45, Ben Finney wrote:

> Howdy all,
> 
> The Python reference says of a class ‘__new__’ method::
> 
> object.__new__(cls[, ...])
> 
> Called to create a new instance of class cls. __new__() is a static
> method (special-cased so you need not declare it as such) that takes
> the class of which an instance was requested as its first argument.

This is correct. __new__ is a static method and you need to explicitly 
provide the cls argument:


py> class Spam(object):
... def __new__(cls):
... print cls
... 
py> Spam.__new__()  # implicit first arg?
Traceback (most recent call last):
  File "", line 1, in 
TypeError: __new__() takes exactly 1 argument (0 given)


py> Spam.__new__(Spam)



Furthermore:

py> type(Spam.__dict__['__new__'])




> I suspect this a bug in the reference documentation for ‘__new__’, and
> it should instead say “__new__ is a class method …”. Am I wrong?

I've made that mistake in the past too :-)



-- 
Steve

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: str.index() and str.find() versus only list.index()

[Steven D'Aprano]

On Tuesday 14 July 2015 14:07, Ian Kelly wrote:

> On Mon, Jul 13, 2015 at 9:23 PM, Steven D'Aprano 
> wrote:
>> On Tue, 14 Jul 2015 01:12 pm, Ian Kelly wrote:
>>
>>> On Mon, Jul 13, 2015 at 10:56 AM, Roel Schroeven
>>>  wrote:
 Hi,

 Quick question: why does str have both index() and find(), while list
 only has index()? Is there a reason for that, or is it just an
 historical accident?
>>>
>>> Historical accident, I think. If it were to be redone, I doubt that
>>> str.find would exist. The problem with it is that it returns -1 to
>>> indicate that the argument was not found, but -1 is a valid index into
>>> the string. This is a potential source of hard-to-find bugs.
>>
>> Correct. But rather than removing it, it would be better to take a leaf
>> out of re.match's book and return None as the sentinel. That would
>> eliminate the "using -1 as a valid index" bug.
> 
> I disagree on both counts.
> 
 s = 'abc'
 s[None:None]
> 'abc'


Well wadda ya know, I just learned something new. I was thinking more along 
these lines:

py> 'abc'[None]
Traceback (most recent call last):
  File "", line 1, in 
TypeError: string indices must be integers, not NoneType



> Better IMO to just have the one non-redundant method that raises an
> exception rather than returning anything that could possibly be
> interpreted as a string index.


Well, maybe, but if you got rid of str.find, the first thing people would do 
is recreate it:

def find(*args):
try:
return str.index(*args)
except ValueError:
return -1


Having a version of str.index that returns a sentinel is just too damn 
handy.



-- 
Steve

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: str.index() and str.find() versus only list.index()

[Chris Angelico]

On Tue, Jul 14, 2015 at 2:58 PM, Steven D'Aprano
 wrote:
> On Tuesday 14 July 2015 14:07, Ian Kelly wrote:
>
>> On Mon, Jul 13, 2015 at 9:23 PM, Steven D'Aprano 
>> wrote:
>>> Correct. But rather than removing it, it would be better to take a leaf
>>> out of re.match's book and return None as the sentinel. That would
>>> eliminate the "using -1 as a valid index" bug.
>>
>> I disagree on both counts.
>>
> s = 'abc'
> s[None:None]
>> 'abc'
>
>
> Well wadda ya know, I just learned something new. I was thinking more along
> these lines:
>
> py> 'abc'[None]
> Traceback (most recent call last):
>   File "", line 1, in 
> TypeError: string indices must be integers, not NoneType

Which proves that None is not a valid index, but it is a valid slice
boundary. Given that the return value will often be used for slicing
as well as indexing, it'd be good to have something that's not valid
for either. How about -1.0? It's equal to -1 in case someone uses
(str.find(...) == -1), it's less than zero in case they do
(str.find(...) < 0), and it's invalid in both slices and string
subscripts. There's no way that can break anything, right?

... oh wait. XKCD 1172. And anyone who's adding 1 to the position and
using that as a slice boundary, which will smoothly and without error
work with the beginning of the string if something isn't found (eg
s[s.find("-"):] will be everything after the first hyphen, or the
whole string if there isn't one).

>> Better IMO to just have the one non-redundant method that raises an
>> exception rather than returning anything that could possibly be
>> interpreted as a string index.
>
>
> Well, maybe, but if you got rid of str.find, the first thing people would do
> is recreate it:
>
> def find(*args):
> try:
> return str.index(*args)
> except ValueError:
> return -1
>
>
> Having a version of str.index that returns a sentinel is just too damn
> handy.

Same as dictionaries have [] and .get(), although find doesn't allow
you to change the sentinel.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Foo.__new__ is what species of method?

[Ben Finney]

Steven D'Aprano  writes:

> py> class Spam(object):
> ... def __new__(cls):
> ... print cls
> ... 
> py> Spam.__new__()  # implicit first arg?
> Traceback (most recent call last):
>   File "", line 1, in 
> TypeError: __new__() takes exactly 1 argument (0 given)

Thanks, I'm glad I checked before filing a bug report.

Hopefully I'll remember that clear test, when I need to remember which
species it is :-)

-- 
 \   “Instead of having ‘answers’ on a math test, they should just |
  `\   call them ‘impressions’, and if you got a different |
_o__)   ‘impression’, so what, can't we all be brothers?” —Jack Handey |
Ben Finney

-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Paul Rubin]

Chris Angelico  writes:
> I'm not sure why the transition to another state has to be recursive.

It's not recursive: it's more like a goto with arguments, and a tail
call expresses it nicely.

> Maybe this is something where previous experience makes you more
> comfortable with a particular style, which will mean that functional
> idioms will never feel more comfortable to me than iterative ones do,
> and vice versa for you. If that's the case, then I'll stick with
> Python and Pike, and you can happily use Lisp and Haskell, and neither
> of us need be a problem to the other. 

Do you also use explicit loops instead of list comprehensions?  They are
another nice functional idiom adapted into Python.

> That's why I said "example please?". My experience has not a single
> time come across this. If you want to make an assertion that iterative
> code requires equivalent warping to tail-recursive code, I want to see
> an example of it. Is that difficult?

It's difficult given how subjective the concept of warping is.  What's
straightforward to someone else sounds likely to look warped to you and
vice versa.  But how does this look:

  def quicksort(array, start, end):
 midp = partition(array, start, end)
 if midp <= (start+end)//2:
quicksort(array, start, midp)
quicksort(array, midp+1, end)
 else:
quicksort(array, midp+1, end)
quicksort(array, start, midp)

I assume you know how quicksort and its partition step work.  The idea
is you partition the array around the pivot element (midp is the index
of that element), then recursively sort the two partitions, doing the
smaller partition as a recursive call and the larger one as a tail call,
so that you use O(log n) stack depth instead of potentially O(n).

So the idea is that the second quicksort call in each branch of the if
is a tail call.  Yes you could code that as a loop but from my
perspective the way I wrote it above looks more natural.

Of course it's also possible that I've totally derped this and the
example is no good for some reason I've missed so far ;-).
-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Chris Angelico]

On Tue, Jul 14, 2015 at 3:15 PM, Paul Rubin  wrote:
> It's difficult given how subjective the concept of warping is.  What's
> straightforward to someone else sounds likely to look warped to you and
> vice versa.  But how does this look:
>
>   def quicksort(array, start, end):
>  midp = partition(array, start, end)
>  if midp <= (start+end)//2:
> quicksort(array, start, midp)
> quicksort(array, midp+1, end)
>  else:
> quicksort(array, midp+1, end)
> quicksort(array, start, midp)
>
> I assume you know how quicksort and its partition step work.  The idea
> is you partition the array around the pivot element (midp is the index
> of that element), then recursively sort the two partitions, doing the
> smaller partition as a recursive call and the larger one as a tail call,
> so that you use O(log n) stack depth instead of potentially O(n).
>
> So the idea is that the second quicksort call in each branch of the if
> is a tail call.  Yes you could code that as a loop but from my
> perspective the way I wrote it above looks more natural.
>
> Of course it's also possible that I've totally derped this and the
> example is no good for some reason I've missed so far ;-).

That's a prime example of recursion... but not of recursion that can
be tail-call optimized into iteration. It's an example of forking
recursion, where one call can result in multiple calls (same with tree
traversal); it calls itself to sort the first part and the last part,
and while you might be able to turn the second call into a goto, you
still need stack space to maintain the first call. The claim that TCO
means you don't need stack space for all those levels of recursion
doesn't work if you still need stack space for all those levels of
recursion *before* you get to the tail call.

(Also, side point: Python can't actually optimize the above function,
because it actually means "call quicksort, then discard its return
value and return None". A true tail call has to return the result of
the recursive call, and Python lacks a way to say "this function will
always return None". But that's trivial.)

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Chris Angelico]

On Tue, Jul 14, 2015 at 3:15 PM, Paul Rubin  wrote:
> Chris Angelico  writes:
>> I'm not sure why the transition to another state has to be recursive.
>
> It's not recursive: it's more like a goto with arguments, and a tail
> call expresses it nicely.

Hmm, maybe, but I'm not sure that the transition to another state is a
goto with arguments. What triggers the transition? Is it a linear
protocol? Is it a nested protocol that completes some operation and
returns to a base state? How are these transitions recognized, and why
is that needing a "goto with arguments" to express it?

>> Maybe this is something where previous experience makes you more
>> comfortable with a particular style, which will mean that functional
>> idioms will never feel more comfortable to me than iterative ones do,
>> and vice versa for you. If that's the case, then I'll stick with
>> Python and Pike, and you can happily use Lisp and Haskell, and neither
>> of us need be a problem to the other.
>
> Do you also use explicit loops instead of list comprehensions?  They are
> another nice functional idiom adapted into Python.

I use list comprehensions, but that's not the same thing as using
functional programming. What that means is that there's nothing that
we can't learn from. I'm glad functional languages exist, where people
try to make everything have no side effects and be deterministic; it's
a good discipline, and worth being aware of even when your language
doesn't enforce it. But just because functional languages like to say
"take this array and multiply every element by 4" and I like using
that same feature, that doesn't mean that I want to do everything in a
functional style.

Here's an alternative way of expressing that thought.

Do you write code such that each line does one simple thing? That's a
nice assembly language practice that's been adapted into Python.

Assembly languages tend to enforce a "one line, one operation" rule.
Python programmers often adhere to that (you don't generally see a
bunch of stuff separated by semicolons, and even "for line in lines:
print(line)" is frowned upon - add a newline!), but that doesn't mean
we want all the other trappings of assembly languages.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Marko Rauhamaa]

Chris Angelico :

>>   def quicksort(array, start, end):
>>  midp = partition(array, start, end)
>>  if midp <= (start+end)//2:
>> quicksort(array, start, midp)
>> quicksort(array, midp+1, end)
>>  else:
>> quicksort(array, midp+1, end)
>> quicksort(array, start, midp)
> [...]
> That's a prime example of recursion... but not of recursion that can
> be tail-call optimized into iteration.

Of course it can. The 2nd and 4th calls to quicksort can be trivially
tail-call-optimized.

Tail-call optimization has nothing to do with converting algorithms into
iterations. It's a prosaic trick of dropping an unneeded stack frame
before making a function call.

> The claim that TCO means you don't need stack space for all those
> levels of recursion doesn't work if you still need stack space for all
> those levels of recursion *before* you get to the tail call.

Nobody is making that claim.

What you are questioning is what tail-call optimization would buy you in
practice. Not much. The few times you run into a stack overflow, you can
refactor your code pretty easily. However, when you have to do that, it
feels a bit silly.


Marko
-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Paul Rubin]

Chris Angelico  writes:
> That's a prime example of recursion... but not of recursion that can
> be tail-call optimized into iteration. It's an example of forking
> recursion, where one call can result in multiple calls (same with tree
> traversal); it calls itself to sort the first part and the last part,
> and while you might be able to turn the second call into a goto, you
> still need stack space to maintain the first call. The claim that TCO
> means you don't need stack space for all those levels of recursion
> doesn't work if you still need stack space for all those levels of
> recursion *before* you get to the tail call.

You partition the array into two parts, one of which has at most N/2
elements.  You push that smaller one onto the stack and recurse, so at
the next recursive level you push at most an N/4 part, then N/8 and so
on.  In that way the total recursion depth is O(log N).  If N=1e6 you
enter 20 levels of recursion which is no big deal.

If you also push the larger part on the stack, it can have size as high
as N-1, so you can end up pushing N-1, N-2, N-3, etc.  If N=1e6 you
overflow the stack when you've barely gotten started.

So it's important in that example that both of the recursive calls
involving the larger partition are both tail calls.  It's fine that the
first call pushes stuff on the stack.  It's vital that the second call
be turned into a goto.
-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Ian Kelly]

On Mon, Jul 13, 2015 at 11:25 PM, Chris Angelico  wrote:
> (Also, side point: Python can't actually optimize the above function,
> because it actually means "call quicksort, then discard its return
> value and return None". A true tail call has to return the result of
> the recursive call, and Python lacks a way to say "this function will
> always return None". But that's trivial.)

Another point in favor of an explicit tail-call keyword. Then one
couldn't make that mistake.
-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Marko Rauhamaa]

Ian Kelly :

> On Mon, Jul 13, 2015 at 11:25 PM, Chris Angelico  wrote:
>> (Also, side point: Python can't actually optimize the above function,
>> because it actually means "call quicksort, then discard its return
>> value and return None". A true tail call has to return the result of
>> the recursive call, and Python lacks a way to say "this function will
>> always return None". But that's trivial.)
>
> Another point in favor of an explicit tail-call keyword. Then one
> couldn't make that mistake.

How about "return"?


Marko
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: Foo.__new__ is what species of method?

[Stefan Behnel]

Steven D'Aprano schrieb am 14.07.2015 um 06:54:
> On Tuesday 14 July 2015 14:45, Ben Finney wrote:
>> The Python reference says of a class ‘__new__’ method::
>>
>> object.__new__(cls[, ...])
>>
>> Called to create a new instance of class cls. __new__() is a static
>> method (special-cased so you need not declare it as such) that takes
>> the class of which an instance was requested as its first argument.
> 
> This is correct. __new__ is a static method and you need to explicitly 
> provide the cls argument:

And it needs to be that way in order to allow superclass calls in a
subclass's __new__ method:

  class Super(object):
  def __new__(cls):
  return object.__new__(cls)

  class Sub(Super):
  def __new__(cls):
  return Super.__new__(cls)

If it was a classmethod, it would receive the class you call it on as first
argument (i.e. "Super" and "object" above), not the class you want to
instantiate (i.e. "Sub" or "Super").

Stefan


-- 
https://mail.python.org/mailman/listinfo/python-list

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

[Gregory Ewing]

Marko Rauhamaa wrote:

Ian Kelly :


Another point in favor of an explicit tail-call keyword. Then one
couldn't make that mistake.


How about "return"?


How about "goto"? :-)

That's not entirely an unserious suggestion -- if you
really believe that a "goto with arguments" is a good
feature for a language to have, you shouldn't be
afraid to spell it as such.

  def quicksort(array, start, end):
 midp = partition(array, start, end)
 if midp <= (start+end)//2:
quicksort(array, start, midp)
goto quicksort(array, midp+1, end)
 else:
quicksort(array, midp+1, end)
goto quicksort(array, start, midp)

--
Greg
--
https://mail.python.org/mailman/listinfo/python-list