Python's "only one way to do it" philosophy isn't good?

[Anders J. Munch]

The usual compiler method is to translate the code into
continuation-passing style and thereby gain tail-recursion
optimization automagically.

There's no need to go into CPS just to optimise tail-recursion. After all,
compilers were optimising tail-calls decades before Appel's work on SML/NJ.

Converting tail-recursion to iteration is trivial, and perfectly reasonable for
a human to do by hand. You add an outer "while True"-loop, the recursive call
becomes a tuple assignment, and other code paths end with a break out of the
loop. Completely mechanical and the resulting code doesn't even look that bad.

Like Steven said, tail-call optimisation is not necessary as you can always
hand-optimise it yourself.

- Anders

 

[Alexander Schmolck]

Don't keep us in suspense. What do you believe is the true reason?

It's easier to spot that some rationalization is bogus than to unconver the
true underlying causes; I'm pretty sure it's more a Gestalt thing than a
compelling technical reason (I guess Guido's distaste for scheme also plays a
role). Not that I discount that out of hand -- maybe all that's great about
python is due to Guido being exceptionally good at making such judgements.

He's not the only one who gets to make these decisions.

This is news to me. Who else does?

But even if he uses his veto to prevent tail-recursion optimization from
being put into the main branch, there are other options.

That don't involve abducting his kids?

That's not the sort of arbitrary failure I was discussing, but for that
matter Python is one of those languages.

Apart from floating point arithmetic, simple arithmetic doesn't tend to fail
arbitrarily in python, as far as I'm aware. You can of course create your very
own classes specifically to get broken arithmetic but that doesn't strike me
as "simple" arithmetic anymore.

Perhaps Python is not the language for you?

Do you also happen to know what would be?

Correct me if I'm wrong, but surely it is C++ that can have arbitrary
behaviour for "a + b", not C?

``INT_MAX + 1`` can do precisely anything in C.

Sorry, how does that work? You're suggesting that there is an algorithm
which the compiler could follow to optimize away tail-recursion, but human
beings can't follow the same algorithm? Now I'm confused.

Does it also confuse you that if I give you a 500x500 matrix A you won't be
able to figure out a single element in A^-1 by doing mental arithmetic (or
using pen and paper), although my computer manages just fine and I'm happy to
give you the algorithm it uses?

'as

 

[Alexander Schmolck]

Like Steven said, tail-call optimisation is not necessary as you can always
hand-optimise it yourself.

Care to demonstrate on some code written in CPS (a compiler or parser, say)?

'as

 

[John Nagle]

It's easier to spot that some rationalization is bogus than to unconver the
true underlying causes; I'm pretty sure it's more a Gestalt thing than a
compelling technical reason.

There's a real reason. Remember, functions are dynamically
replaceable. The compiler would have to detect that the function
doesn't modify or replace itself while recursing for this optimization
to be valid. Worst case, another thread could replace the function
while it was recursing, invalidating the tail recursion optimization.

John Nagle

 

[Neil Cerutti]

There's no need to go into CPS just to optimise tail-recursion.
After all, compilers were optimising tail-calls decades before
Appel's work on SML/NJ.

Converting tail-recursion to iteration is trivial, and
perfectly reasonable for a human to do by hand.

For simple recursive tail calls, yeah, it can be. Translating a
tail-recursive Factorial function into a while loop is easy. But
tail-call optimization technically works for any tail-call,
including mutual recursion, and non-recursive tail-calls. You
can't reasonably hand-optimize away the stack frame for all
tail-calls.

def foo(x)
bar(x)

The only way to hand-optimize the call to bar is to inline it
yourself.

 

[Neil Cerutti]

You would just change the language definition to say that once
you enter f(), any call to f() from within f() behaves as if
the recursively called f() still points to the originally bound
version of f. To want any other behavior would be absurd,
anyhow.

There's a reason it's generally refered to as "tail-call"
optimization and not "tail-recursive" optimization. The former is
more general, and, I believe, easier to implement than the
latter.

 

[Anders J. Munch]

For simple recursive tail calls, yeah, it can be. Translating a
tail-recursive Factorial function into a while loop is easy. But
tail-call optimization technically works for any tail-call,
including mutual recursion, and non-recursive tail-calls. You
can't reasonably hand-optimize away the stack frame for all
tail-calls.

I may have misunderstood, I thought we were talking about tail recursion only.
The general tail-call optimisation, where all leaf calls become jumps and the
called function usurps the current stack frame, is a different ballgame
entirely. There's no pure-Python transformation for that, but that still
doesn't mean you need CPS.

General tail-call optimisation is of course completely out-of-bounds for Python,
because it ruins tracebacks. Unlike tail recursion, which could use recursion
counters.

- Anders

 

[Anders J. Munch]

Care to demonstrate on some code written in CPS (a compiler or parser, say)?

I meant tail recursion, not tail-call, sorry, that was just my fingers trying to
save typing.

- Anders

 

[Neil Cerutti]

General tail-call optimisation is of course completely
out-of-bounds for Python, because it ruins tracebacks. Unlike
tail recursion, which could use recursion counters.

Is it really ruined? To use a similar example:

def foo(x):
bar(x+1)

def bar(x):
if x > 10:
raise ValueError
else:
foo(x+2)

Today, when I call foo(4), I get something like:

C:\WINNT\system32\cmd.exe /c python temp.py
Traceback (most recent call last):
File "temp.py", line 529, in <module>
foo(4)
File "temp.py", line 521, in foo
bar(x+1)
File "temp.py", line 527, in bar
foo(x+2)
File "temp.py", line 521, in foo
bar(x+1)
File "temp.py", line 527, in bar
foo(x+2)
File "temp.py", line 521, in foo
bar(x+1)
File "temp.py", line 525, in bar
raise ValueError
ValueError
shell returned 1

With tail-call optimization you'd get something like:

C:\WINNT\system32\cmd.exe /c python temp.py
Traceback (most recent call last):
File "temp.py", line 529, in <module>
foo(4)
File "temp.py", line 525, in bar
raise ValueError
ValueError
shell returned 1

What makes the latter harder to work with?

 

[Carsten Haese]

Is it really ruined? To use a similar example:

def foo(x):
bar(x+1)

def bar(x):
if x > 10:
raise ValueError
else:
foo(x+2)

Today, when I call foo(4), I get something like:

C:\WINNT\system32\cmd.exe /c python temp.py
Traceback (most recent call last):
File "temp.py", line 529, in <module>
foo(4)
File "temp.py", line 521, in foo
bar(x+1)
File "temp.py", line 527, in bar
foo(x+2)
File "temp.py", line 521, in foo
bar(x+1)
File "temp.py", line 527, in bar
foo(x+2)
File "temp.py", line 521, in foo
bar(x+1)
File "temp.py", line 525, in bar
raise ValueError
ValueError
shell returned 1

With tail-call optimization you'd get something like:

C:\WINNT\system32\cmd.exe /c python temp.py
Traceback (most recent call last):
File "temp.py", line 529, in <module>
foo(4)
File "temp.py", line 525, in bar
raise ValueError
ValueError
shell returned 1

What makes the latter harder to work with?

The fact that you don't see how many call levels down your algorithm got
before throwing an exception. This may be an important clue in debugging
a recursive algorithm.

 

[Neil Cerutti]

Is it really ruined? To use a similar example:

I found some interesting notes by Alex Martelli pertaining to
tail-call optimisation, and my assumption that tail-call
optimization is easier to implement than tail-recursive
optimization may have been naive.

http://groups.google.com/group/comp.lang.python/msg/1a7cccc103c1bd70?hl=en&

Moreover, there are (or were) technical reasons that you can't do
tail-call optimization in Python, which can't even recognize
tail-calls at compile time. According to Tim Peters:

http://groups.google.com/group/comp.lang.python/msg/ea1de1e35aefb828?hl=en&

 

[Terry Reedy]

|
| You would just change the language definition to say
| that once you enter f(), any call to f() from within
| f() behaves as if the recursively called f() still
| points to the originally bound version of f.

I am pretty sure such a context-dependent rule cannot be written as a
context-free grammar rule. In any case, the function object does not exist
when code is being compiled to a code object. So this requires
implementation-dependent post-patching of the code object. R.
Hetchinger(sp?) posted a Cookbook recipe for doing this for CPython.
Anyone wanting the speedup (with CPython) can use it.

tjr

 

[Paul Rubin]

And if only the html-parsing is slow, you might consider creating an
extension for that. Using e.g. Pyrex.

I just tried using BeautifulSoup to pull some fields out of some html
files--about 2 million files, output of a web crawler. It parsed very
nicely at about 5 files per second. Of course Python being Python, I
wanted to run the program a whole lot of times, modifying it based on
what I found from previous runs, and at 5/sec each run was going to
take about 4 days (OK, I probably could have spread it across 5 or so
computers and gotten it to under 1 day, at the cost of more effort to
write the parallelizing code and to scare up extra machines). By
simply treating the html as a big string and using string.find to
locate the fields I wanted, I got it up to about 800 files/second,
which made each run about 1/2 hour. Simplest still would be if Python
just ran about 100x faster than it does, a speedup which is not
outlandish to hope for.

 

[John Nagle]

I just tried using BeautifulSoup to pull some fields out of some html
files--about 2 million files, output of a web crawler. It parsed very
nicely at about 5 files per second.

That's about what I'm seeing. And it's the bottleneck of
"sitetruth.com".

By
simply treating the html as a big string and using string.find to
locate the fields I wanted, I got it up to about 800 files/second,
which made each run about 1/2 hour.

For our application, we have to look at the HTML in some detail,
so we really need it in a tree form.

> Simplest still would be if Python
just ran about 100x faster than it does, a speedup which is not
outlandish to hope for.

Right. Looking forward to ShedSkin getting good enough to run
BeautifulSoup.

(Actually, the future of page parsing is probably to use some kind
of stripped-down browser that reads the page, builds the DOM,
runs the startup JavaScript, then lets you examine the DOM. There
are too many pages now that just come through as blank if you don't
run the OnLoad JavaScript.)

John Nagle

 

[Douglas Alan]

Try suggesting on a Lisp or Scheme group that having only one type
of syntax (prefix expressions) lacks something and that they should
add variety in the form of statement syntax ;-) Hint: some Lispers
have bragged here about the simplicity of 'one way to do it' and put
Python down for its mixed syntax. (Of course, this does not mean
that some dialects have not sneaked in lists of statements thru a
back door ;-).

Almost all Lisp dialects have an extremely powerful macro mechanism
that lets users and communities extend the syntax of the language in
very general ways. Consequently, dialects such a Scheme try to keep
the core language as simple as possible. Additional ways of doing
things can be loaded in as a library module.

So, a language such as Scheme may have no *obvious* way of something,
and yet may provide excellent means to extend the language so that
many obvious ways might be provided.

|>oug

 

[Douglas Alan]

My only point was that Sussman is an odd person to be criticizing
(somewhat mistakingly) Python for being minimalist.

I think that being a language minimalist is very different from
believing that there should be exactly one obvious way to do
everything.

For instance, I believe that Python is now too big, and that much of
what is in the language itself should be replaced with more general
Scheme-like features. Then a good macro mechanism should be
implemented so that all the conveniences features of the language can
be implemented via macro definitions in the standard library.

Macros, however, are typically claimed in these parts to violate the
"only one way" manifesto.

|>oug

 

[Douglas Alan]

Here's the situation. Python is making inroads at MIT, Scheme home turf.
The co-developer of Scheme, while writing about some other subject, tosses
in an off-the-wall slam against Python. Someone asks what we here think.
I think that the comment is a crock and the slam better directed, for
instance, at Scheme itself. Hence 'he should look in a mirror'.

You are ignoring the fact that Scheme has a powerful syntax extension
mechanism (i.e., hygenic macros), which means that anyone in the world
can basically extend Scheme to include practically any language
feature they might like it to have.

|>oug

 

[Kay Schluehr]

For instance, I believe that Python is now too big, and that much of
what is in the language itself should be replaced with more general
Scheme-like features.
Then a good macro mechanism should be
implemented so that all the conveniences features of the language can
be implemented via macro definitions in the standard library.

And why sould anyone reimplement the whole standard library using
macro reductions? Because this is the "one obvious way to do it" for
people who are addicted to Scheme?

 

[Douglas Alan]

And why sould anyone reimplement the whole standard library using
macro reductions? Because this is the "one obvious way to do it" for
people who are addicted to Scheme?

(1) By, "should be replaced", I meant in an ideal world. I'm not
proposing that this be done in the real world anytime soon.

(2) I didn't suggest that a single line of the standard library be
changed. What would need to be changed is the core Python language,
not the standard library. If this idea were implemented, the core
language could be made smaller, and the features that were thereby
removed from the language core could be moved into the standard
library instead.

(3) My reasons for wanting this have nothing to do with being
"addicted to Scheme", which I almost never use. It has to do more
with my language design and implementation aesthetics, and my desire
for a syntax extension mechanism so that I can add my own language
features to Python without having to hack on the CPython source code.

|>oug

 

[Steven D'Aprano]

You are ignoring the fact that Scheme has a powerful syntax extension
mechanism (i.e., hygenic macros), which means that anyone in the world
can basically extend Scheme to include practically any language
feature they might like it to have.

You say that like it is a good thing.