Mailing List Archive

On Fri, Aug 7, 2020 at 1:16 AM Christian Seberino <cseberino@gmail.com> wrote:
>
> Python is my favorite language and the easiest to use in my opinion.
>
> Lisp has a far simpler grammar and syntax. A beginner I think could
> learn Lisp much faster than Python.
>
> Therefore, it seems like Lisp *should* be easier to work with and more readable. I don't feel like it is easier to use but I can't see *why* that is.
>
> My best guess.....
>
> Lisp pros: simpler syntax
> Lisp cons: prefix notation, lots more parentheses
>
> My hypothesis is that the cons slightly outweigh the pros of Lisp
> which is why Python is easier to work with and is more readable in the end?

Ook has an even simpler syntax. It has just three syntactic elements:
"Ook." "Ook?" "Ook!"

The purpose of code is to represent a programmer's intentions in a way
that can be understood by other programmers, and by the
interpreter/compiler. Simpler syntax allows a simpler parser, but it
doesn't create expressiveness.

If your definition is based entirely on how quickly a beginner would
be able to learn the details of how a language is run, then that's
missing a lot of the point of readability. The point of learning a
language isn't that you can take a piece of pre-existing code and
figure out what it'll do, step by step; the point is to be able to
encode your intentions in that language, and to read the code and
understand the other programmer's intentions. That's why we have
comments - the language would be (slightly) simpler without them, but
we would lose an important aspect of that programmer-to-programmer
communication.

Ook is one of the least expressive and most simple languages there is.
Python is far more expressive, far more detailed... and far FAR more
useful.

Lisp is elegant and simple, but it's also less expressive than Python
is. That's why Python is (often) easier to work with.

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

On Thursday, August 6, 2020 at 10:52:00 AM UTC-5, Chris Angelico wrote:
> The point of learning a
> language isn't that you can take a piece of pre-existing code and
> figure out what it'll do, step by step; the point is to be able to
> encode your intentions in that language, and to read the code and
> understand the other programmer's intentions.

Thanks for sharing your thoughts. How do you define "expressiveness"?
Also, why is Python syntax able to more clearly communicate intentions?
Both Python and Lisp have comments so that isn't it.

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

On Fri, Aug 7, 2020 at 2:36 AM Christian Seberino <cseberino@gmail.com> wrote:
>
> On Thursday, August 6, 2020 at 10:52:00 AM UTC-5, Chris Angelico wrote:
> > The point of learning a
> > language isn't that you can take a piece of pre-existing code and
> > figure out what it'll do, step by step; the point is to be able to
> > encode your intentions in that language, and to read the code and
> > understand the other programmer's intentions.
>
> Thanks for sharing your thoughts. How do you define "expressiveness"?
> Also, why is Python syntax able to more clearly communicate intentions?
> Both Python and Lisp have comments so that isn't it.
>

Expressiveness is about how well you can translate your ideas into
code, and how well someone else can interpret your ideas by reading
your code. It's hard to quantify, but it's in a way the most important
thing about any language.

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

Christian Seberino writes:
> Python is my favorite language and the easiest to use in my opinion.
>
> Lisp has a far simpler grammar and syntax. A beginner I think could
> learn Lisp much faster than Python.
>
> Therefore, it seems like Lisp *should* be easier to work with and more readable. I don't feel like it is easier to use but I can't see *why* that is.

First, everybody's brain is different so be cautious of sweeping
statements. What's true for one person isn't necessarily true for another.

That said, for me, Lisp's simpler syntax arises from the fact that
there's basically one data structure: a list. To do anything in
Lisp, you have to think in lists, map everything to lists (including
the program's own structure), build up list-based data structures in
your head. It's also functional and recursive, which means that as
you're programming, you have to maintain a stack (which is also a
list) in your head of all the lists that aren't yet closed. Of
course, you can use tricks like let and setq to hold intermediate
variables and mitigate that a little, but that isn't really Lispish.

Trying to maintain that recursive list of unclosed lists in your
brain is fun. It stretches the brain in interesting ways. I was
way into Lisp at one point, including writing several Lisp
interpreters (that simple structure makes Lisp very easy to
implement). But I never found Lisp code very maintainable, because
any time you read a program, you have to build up that list in your
head every time just to follow the logic structure and figure out
what the return value will be. I suspect most people find that more
difficult than reading an inherently procedural language like
Python. I know I do.

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

On 2020-08-07 at 04:00:34 +1000,
Regarding "Re: How explain why Python is easier/nicer than Lisp which has a simpler grammar/syntax?,"
Chris Angelico <rosuav@gmail.com> wrote:

> On Fri, Aug 7, 2020 at 2:36 AM Christian Seberino <cseberino@gmail.com> wrote:
> >
> > On Thursday, August 6, 2020 at 10:52:00 AM UTC-5, Chris Angelico wrote:
> > > The point of learning a
> > > language isn't that you can take a piece of pre-existing code and
> > > figure out what it'll do, step by step; the point is to be able to
> > > encode your intentions in that language, and to read the code and
> > > understand the other programmer's intentions.
> >
> > Thanks for sharing your thoughts. How do you define "expressiveness"?
> > Also, why is Python syntax able to more clearly communicate intentions?
> > Both Python and Lisp have comments so that isn't it.
> >
>
> Expressiveness is about how well you can translate your ideas into
> code, and how well someone else can interpret your ideas by reading
> your code. It's hard to quantify, but it's in a way the most important
> thing about any language.

I would say that expressiveness is how *directly* you can translate your
ideas into code, and how *directly* some one else can see your original
idea by reading your code.

So when I say something like "create a new list in which each value is
double the value in the current list," that translates to relatively
idiomatic Python like so:

new_list = []
for value in current_list:
new_list.append(2 * value) # or maybe value + value; YMMV

Or even:

[ 2 * value for value in current_list ]

In Lisp, it might look like this:

(mapcar #'(lambda (value) (* 2 value)) current_list)

Unless you're familiar with Lisp (or Lisp-like languages), and
comfortable with high order functions (which many/most beginners aren't,
although most Lispers are), it's a lot harder to see the idea in the
code.

Having written my share of both Python and Lisp, I appreciate the
benefits of Lisp's syntax, but I also know that it still takes me a
little longer to read and understand a big block of straightforward Lisp
vs. a big block of straightforward Python. (Between dunders,
properties, and other bits of magic that takes place far away from its
invocation, Python code and the logic behind it can be *very* confusing
to unravel. Lisp macros present the same problem.)
--
https://mail.python.org/mailman/listinfo/python-list

On Fri, Aug 7, 2020 at 5:10 AM <2QdxY4RzWzUUiLuE@potatochowder.com> wrote:
>
> I would say that expressiveness is how *directly* you can translate your
> ideas into code, and how *directly* some one else can see your original
> idea by reading your code.

Yep, how directly or how accurately.

> So when I say something like "create a new list in which each value is
> double the value in the current list," that translates to relatively
> idiomatic Python like so:
>
> new_list = []
> for value in current_list:
> new_list.append(2 * value) # or maybe value + value; YMMV
>
> Or even:
>
> [ 2 * value for value in current_list ]
>
> In Lisp, it might look like this:
>
> (mapcar #'(lambda (value) (* 2 value)) current_list)
>
> Unless you're familiar with Lisp (or Lisp-like languages), and
> comfortable with high order functions (which many/most beginners aren't,
> although most Lispers are), it's a lot harder to see the idea in the
> code.

One thing worth noting is that your mental pseudo-code is affected by
the languages you're comfortable with. You said:

> create a new list in which each value is double the value in the current list

which clearly and obviously translates into a list comprehension. But
what if you instead thought of it as:

> double every value in this list

? That would translate far more obviously into an imperative construct
that doesn't really work in Python, but imagine that we had reference
variables:

for &value in list: value *= 2

So the expressiveness of a language isn't a fixed quantity, but it
depends on the programmer. And it can change as you learn and adjust,
too.

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

On 2020-08-07 at 05:22:53 +1000,
Chris Angelico <rosuav@gmail.com> wrote:

> On Fri, Aug 7, 2020 at 5:10 AM <2QdxY4RzWzUUiLuE@potatochowder.com> wrote:

> One thing worth noting is that your mental pseudo-code is affected by
> the languages you're comfortable with. You said:
>
> > create a new list in which each value is double the value in the current list
>
> which clearly and obviously translates into a list comprehension. But
> what if you instead thought of it as:
>
> > double every value in this list
>
> ? That would translate far more obviously into an imperative construct
> that doesn't really work in Python ...

for (index, value) in enumerate(this_list):
this_list[index] = 2 * value

Or:

for index in range(len(this_list)):
this_list[index] *= 2

(But I tend to avoid that, though, because I can never remember exactly
which mutations work inside a loop and which ones don't (or does
enumerate remove some or all of those restrictions?). Which feeds right
into what you said about being comfortable with certain languages or
programming styles.)

[Shared] Mutable Data will be the death of us all! ;-)

> So the expressiveness of a language isn't a fixed quantity, but it
> depends on the programmer. And it can change as you learn and adjust,
> too.

I think the expressiveness of the language remains fairly constant, new
features notwithstanding. Unless you mean that a given programmer's
usage of that expressiveness changes, in which case I absolutely agree.
--
https://mail.python.org/mailman/listinfo/python-list

On 8/6/20 4:07 PM, 2QdxY4RzWzUUiLuE@potatochowder.com wrote:
> for (index, value) in enumerate(this_list):
> this_list[index] = 2 * value
>
> Or:
>
> for index in range(len(this_list)):
> this_list[index] *= 2
>
> (But I tend to avoid that, though, because I can never remember exactly
> which mutations work inside a loop and which ones don't (or does
> enumerate remove some or all of those restrictions?). Which feeds right
> into what you said about being comfortable with certain languages or
> programming styles.)

Since you are not using an iterator of the list, changing it shouldn't
cause any problems. You loop (for its control) looks at the loop once,
before it starts, so as long as you don't delete any elements (which
would cause the index to go to high) you can't have an issue mutating
the list.

--
Richard Damon

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

> Trying to maintain that recursive list of unclosed lists in your
> brain is fun. It stretches the brain in interesting ways. I was
> way into Lisp at one point, including writing several Lisp
> interpreters (that simple structure makes Lisp very easy to
> implement). But I never found Lisp code very maintainable, because
> any time you read a program, you have to build up that list in your
> head every time just to follow the logic structure and figure out
> what the return value will be.

So basically while recursion is easy to write it isn't so easy for other
people to understand compared to iterative code. So maybe that is a
big part of it....recursion is just harder on the brain than iteration.

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

On Thu, Aug 06, 2020 at 04:08:29PM -0700, Christian Seberino wrote:
> > Trying to maintain that recursive list of unclosed lists in your
> > brain is fun. It stretches the brain in interesting ways. I was
> > way into Lisp at one point, including writing several Lisp
> > interpreters (that simple structure makes Lisp very easy to
> > implement). But I never found Lisp code very maintainable, because
> > any time you read a program, you have to build up that list in your
> > head every time just to follow the logic structure and figure out
> > what the return value will be.
>
> So basically while recursion is easy to write it isn't so easy for other
> people to understand compared to iterative code. So maybe that is a
> big part of it....recursion is just harder on the brain than iteration.

Not necessarily. Some problems very naturally lend themselves to
recursive solutions. Fibonacci's sequence is one.

#!/usr/bin/python

def fib(x):
if x < 1:
raise "arg must be >= 1"
if x == 1:
return 0
elif x == 2:
return 1
else:
return fib(x - 1) + fib(x - 2)

Pretty straightforward. Now try yourself to write the iterative
version. If you haven't done this recently, there's a pretty good
chance you'll get it wrong on your first try. The recursive version
is a bit simpler and more straightforward to understand, requiring
less state to be preserved (and mentally retained, if you're trying to
work through the algorithm mentally or on paper).

It's also probably significantly slower, so you'd likely still want to
use the iterative version, unless you're trying to illustrate how
recursion works or care more about writing easily understood code than
performance..

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

On 2020-08-06 at 16:08:29 -0700,
Christian Seberino <cseberino@gmail.com> wrote:

> > Trying to maintain that recursive list of unclosed lists in your
> > brain is fun. It stretches the brain in interesting ways. I was
> > way into Lisp at one point, including writing several Lisp
> > interpreters (that simple structure makes Lisp very easy to
> > implement). But I never found Lisp code very maintainable, because
> > any time you read a program, you have to build up that list in your
> > head every time just to follow the logic structure and figure out
> > what the return value will be.

"[R]ecursive list of unclosed lists"? Can you (whoever you are) expand
on that? Yes, if you eschew helper functions and local variables, then
you can end up with depply nested code, but that's true in any language.

Because of Lisp's simple syntax, text editors can nearly completely
relieve the programmer from the tedium of indenting and formatting, and
even closing parenthesis, which also highlights missing/extra/unbalanced
parentheses pretty quickly.

> So basically while recursion is easy to write it isn't so easy for other
> people to understand compared to iterative code. So maybe that is a
> big part of it....recursion is just harder on the brain than iteration.

I don't know about that. Have you ever seen an iterative or imperative
version of quicksort (or any divide-and-conquer algorithm, for that
matter)? Yes, it's doable, but explicitly managing your own stack of
unsorted data ranges can really obscure the idea(s) of quicksort.

And it's hard to imagine any language being more straightforward than
Haskell's recursive factorial function:

factorial 0 = 1
factorial n = n * factorial (n - 1)

(Yes, it fails for n < 0, but that's outside the scope of whether or not
recursion is harder on the brain than iteration. Pattern matching is a
beautiful thing, too.)
--
https://mail.python.org/mailman/listinfo/python-list

Some problems are well suited to recursion but perhaps //most// problems are better suited to iteration?

Maybe the spread is 10% vs 90%?

Therefore in general more often the Python way seems simpler than Lisp?
--
https://mail.python.org/mailman/listinfo/python-list

On 2020-08-06 at 20:07:05 -0700,
Christian Seberino <cseberino@gmail.com> wrote:

> Some problems are well suited to recursion but perhaps //most//
> problems are better suited to iteration?

> Maybe the spread is 10% vs 90%?

Citation needed?

> Therefore in general more often the Python way seems simpler than Lisp?

In general, the right tool is simpler than the wrong tool, regardless of
the problems and tools. Both Python and Lisp supoprt recursion,
iteration, and a number of other mindsets, paradigms, patterns, and
styles. If "the Python way" seems simpler to you than "the Lisp way,"
or iteration seems simpler to you than recursion, then so be it. Other
languages and other programmers are different.

Consider focusing less on the language and more on solving problems.
You, the problems you solve, and your solutions, will all grow over
time, and you'll discover what you like, what you don't like, what
you're good at, what you're not so good at, what works, and what
doesn't. And things will change. Solve the same problem in a different
language, preferably idiomatically rather than by transliteration. Go
back and look at code you wrote a few months or a year ago, laugh at
yourself for being so immature, and apply what you've learned since
then. Sometimes, it takes me only hours to realize how much better I
could have written a piece of code.
--
https://mail.python.org/mailman/listinfo/python-list

On 8/6/2020 11:13 AM, Christian Seberino wrote:
> Python is my favorite language and the easiest to use in my opinion.
>
> Lisp has a far simpler grammar and syntax. A beginner I think could
> learn Lisp much faster than Python.
>
> Therefore, it seems like Lisp *should* be easier to work with and more readable. I don't feel like it is easier to use but I can't see *why* that is.
>
> My best guess.....
>
> Lisp pros: simpler syntax
> Lisp cons: prefix notation, lots more parentheses
>
> My hypothesis is that the cons slightly outweigh the pros of Lisp
> which is why Python is easier to work with and is more readable in the end?

Here is why *I* prefer Python.

1. Python mostly separates computation of values (expressions) from flow
control and name binding (statements). When the latter are mixed with
the former, most people restrict the mixing to a line or two.

2. Lisp code is one dimensional (though I presume there are now
formatting conventions). Python makes direct use of two dimensional
structuring.

3. Forcing everything into linked lists is 'cute', but it introduces
irrelevant asymmetries, differential nesting, and boilerplate that
obscures the problem relevant structure.

A list of equal status items:
(1,2,3) versus (1 (2 (3 NIL)))

A complete binary tree of depth 2:
((LL, LR), (RL, RR))
Left and right branches have same form.
versus
# ((LL, (LR, NIL)), ((RL, (RR, NIL)), NIL))
((LL (LR NIL)) ((RL (RR NIL)) NIL))
Left and right branches have different forms.
I think I got the Lisp version right, but I had to initially include
commas to do so. Anyway, the Python version was much easier to write
and is much easier to read.




--
Terry Jan Reedy

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

On Fri, Aug 7, 2020 at 11:11 AM Python <python@bladeshadow.org> wrote:
> Not necessarily. Some problems very naturally lend themselves to
> recursive solutions. Fibonacci's sequence is one.
>
> #!/usr/bin/python
>
> def fib(x):
> if x < 1:
> raise "arg must be >= 1"
> if x == 1:
> return 0
> elif x == 2:
> return 1
> else:
> return fib(x - 1) + fib(x - 2)
>
> Pretty straightforward. Now try yourself to write the iterative
> version.

It might look slightly better to a mathematician, but it's so
abysmally inefficient (unless you add extra layers of indirection)
that it's not really a good example. The iterative version seeds the
algorithm and lets it run:

def fib(x):
if x < 1: raise ValueError
last, cur = 0, 1
for _ in range(1, x):
last, cur = cur, last + cur
return cur

It needs a way of remembering the previous as well as the current,
whereas the recursive one needs to ask to calculate the previous and
previous-by-two. I'll leave it to you whether that's better or worse.

But if you want something that is massively more elegant when done
recursively, the best place to look is an inherently recursive data
structure. How do you process all files in a directory tree?

def process(dir):
for thing in dir:
if is_file_we_want(thing): use_thing(thing)
if is_dir(thing) process(thing)

Now THAT is recursion at its best. Of course it's possible to do it
iteratively, but it won't be anything like this clean. There's a
reason that directory tree operations are usually called "recursive"
(eg "rm -r" means "remove directories and their contents recursively",
per the man page).

Similarly, quick sort and merge sort are beautiful when written recursively:

def mergesort(list):
if len(list) < 2: return list
mid = len(list) // 2
left = mergesort(list[:mid])
right = mergesort(right[mid:])
return merge(left, right)

I think recursion looks best when it's doing multiple levels at once
(eg "sort the left, sort the right"), rather than just a single one
(factorial being "n * factorial(n - 1)"), since it's a lot harder to
create an elegant iterative version of multiple recursion. The
Fibonacci example is a bit of an outlier, as the recursive one is just
*so bad* in performance that it loses some elegance points, but the
other examples don't suffer from that, and they're still very clean.

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

On 8/6/2020 2:39 PM, Akkana Peck wrote:
> Christian Seberino writes:
>> Python is my favorite language and the easiest to use in my opinion.
>>
>> Lisp has a far simpler grammar and syntax. A beginner I think could
>> learn Lisp much faster than Python.
>>
>> Therefore, it seems like Lisp *should* be easier to work with and more readable. I don't feel like it is easier to use but I can't see *why* that is.
>
> First, everybody's brain is different so be cautious of sweeping
> statements. What's true for one person isn't necessarily true for another.
>
> That said, for me, Lisp's simpler syntax arises from the fact that
> there's basically one data structure: a list.

In general, the one data structure is a tree*, skewed by being smashed
into a linked list. Replaced 'list' with 'skewed tree' in what you say
below, and I think you explain well the problem many have with thinking
in Lisp.

* One can think of a flat list of n items as being a one level n-ary
tree with a head node and n leafs. A linked list is a skewed binary tree.

> To do anything in
> Lisp, you have to think in lists, map everything to lists (including
> the program's own structure), build up list-based data structures in
> your head. It's also functional and recursive, which means that as
> you're programming, you have to maintain a stack (which is also a
> list) in your head of all the lists that aren't yet closed. Of
> course, you can use tricks like let and setq to hold intermediate
> variables and mitigate that a little, but that isn't really Lispish.
>
> Trying to maintain that recursive list of unclosed lists in your
> brain is fun. It stretches the brain in interesting ways. I was
> way into Lisp at one point, including writing several Lisp
> interpreters (that simple structure makes Lisp very easy to
> implement). But I never found Lisp code very maintainable, because
> any time you read a program, you have to build up that list in your
> head every time just to follow the logic structure and figure out
> what the return value will be. I suspect most people find that more
> difficult than reading an inherently procedural language like
> Python. I know I do.

Stephen Wolfram's Mathematica is also based on the idea that 'everything
is a symbolic expression'. With a somewhat more standard syntax, it
found a sufficiently substantial audience to be a commercial success.
It obviously fit *his* brain well enough that he was able to do a hugh
number of different computations for his 2002 book A New Kind of
Science. It fits me less well.

--
Terry Jan Reedy

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

> If "the Python way" seems simpler to you than "the Lisp way,"
> or iteration seems simpler to you than recursion, then so be it. Other
> languages and other programmers are different.

I think this is so true. I've had similar conversations with Lisp fans
and it has confused me at times why they don't see the wonderfulness
of Python like I do. As you said, everyone's brain isn't the same.
Just have to remember that and accept it.

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

> ChrisA

You're definitely an expert programmer.

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

> 1. Python mostly separates computation of values (expressions) from flow
> control and name binding (statements). When the latter are mixed with
> the former, most people restrict the mixing to a line or two.

This is an interesting observation. I've heard people say the fact that
Python has both expressions and statements is a negative. (Lisp only
has expressions.)

It isn't clear to me what special Python syntax or forms you are referring to that separates expressions from flow control and assignments.
--
https://mail.python.org/mailman/listinfo/python-list

On Sat, Aug 8, 2020 at 1:06 AM Christian Seberino <cseberino@gmail.com> wrote:
>
>
> > ChrisA
>
> You're definitely an expert programmer.
>

Uhh.... thank you? I think? I'm not sure if you're complimenting me or
making some sort of joke relating to the code I posted, or if it's
actually nothing to do with me at all. All you quoted - the only
context we have - is my scribbled signature at the bottom of the post.

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

On Fri, Aug 07, 2020 at 04:23:42PM +1000, Chris Angelico wrote:
> On Fri, Aug 7, 2020 at 11:11 AM Python <python@bladeshadow.org> wrote:
> > Pretty straightforward. Now try yourself to write the iterative
> > version.
>
> It might look slightly better to a mathematician, but it's so
> abysmally inefficient (unless you add extra layers of indirection)
> that it's not really a good example.

Yes, I did say more or less that... but efficiency was not the point.
Understanding was the point.

> The iterative version seeds the algorithm and lets it run:

Sure Chris, I fully expected YOU to get this on the first try, but the
average programmer tends not to. My team uses it as an interview
question fairly often, and I'd venture a guess that upward of 80% of
candidates get it wrong on their first try. The recursive version
is typically much easier to understand intuitively, not just for
mathemeticians, because it more or less restates in simple,
straightforward code what the natural language definition of the
Fibonacci sequence is, rather efficiently (not efficiency of
execution, efficiency of converting natural language to code).

The iterative version requires a bit more thought to make sure you're
seeding the state poperly, and maintaining it properly as the loop
executes. I'd imagine most folks who hang around in this forum would
consider that you are not an average programmer.

Your example was also a fine example.

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

On Sat, Aug 8, 2020 at 1:38 AM Python <python@bladeshadow.org> wrote:
>
> On Fri, Aug 07, 2020 at 04:23:42PM +1000, Chris Angelico wrote:
> > On Fri, Aug 7, 2020 at 11:11 AM Python <python@bladeshadow.org> wrote:
> > > Pretty straightforward. Now try yourself to write the iterative
> > > version.
> >
> > It might look slightly better to a mathematician, but it's so
> > abysmally inefficient (unless you add extra layers of indirection)
> > that it's not really a good example.
>
> Yes, I did say more or less that... but efficiency was not the point.
> Understanding was the point.
>
> > The iterative version seeds the algorithm and lets it run:
>
> Sure Chris, I fully expected YOU to get this on the first try, but the
> average programmer tends not to. My team uses it as an interview
> question fairly often, and I'd venture a guess that upward of 80% of
> candidates get it wrong on their first try. The recursive version
> is typically much easier to understand intuitively, not just for
> mathemeticians, because it more or less restates in simple,
> straightforward code what the natural language definition of the
> Fibonacci sequence is, rather efficiently (not efficiency of
> execution, efficiency of converting natural language to code).
>

My point is that doing Fibonacci recursively is arguably more elegant
while being materially worse at performance, but there are other
examples that are fundamentally recursive, are just as elegant (merge
sort: "fracture the array in half, sort each half, then merge them"),
and can't be done better iteratively. So IMO Fibonacci is a flawed
demonstration of what is a very valid point ("recursion can be really
elegant"), and other examples would serve the purpose better.

TBH most people won't get the recursive version right the first time
either. And that's not a problem. I actually didn't get the iterative
version perfect right away (had an off-by-one on the loop counter),
and tested it before posting. Every student I've worked with has had
the same thing - something doesn't work the first time, even with the
most brilliant students - so they test, they debug, and then they
refine their code. I'm not some sort of coding deity that gets things
right the first time; the medium of email lets me hide the
testing/debugging step and just post working code :)

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

On Fri, 7 Aug 2020 at 17:14, Christian Seberino <cseberino@gmail.com> wrote:
> This is an interesting observation. I've heard people say the fact that
> Python has both expressions and statements is a negative. (Lisp only
> has expressions.)

Commonly, in imperative languages like C, you can write

if (a = b) {...}

This is allowed in C, even if a = b is not an expression, but an
assignment statement. 99% of times you simply wrong and wanted:

if (a == b)

Python separates statements and expressions, so where you expect an
expression, you can't write a statement.

Maybe Lisp does not separate expressions and statements because it
supports both functional and imperative programming, while Python is
mainly an imperative language with some functional features. Not sure
about this, since I never used any Lisp dialect and I've not yet used
function programming in the real world.

PS: Recently there's an exception: if you *really* want an assignment
when an expression is expected, you can use the "walrus" := operator.
IMO it renders the code less readable and I'm not sure about it's
usefulness.

@Chris: note that "real" recursion in Python is not possible, since
there's no support for tail recursion. Maybe something similar can be
done using async functions.
--
https://mail.python.org/mailman/listinfo/python-list

Am 06.08.20 um 17:13 schrieb Christian Seberino:
> Python is my favorite language and the easiest to use in my opinion.
>
> Lisp has a far simpler grammar and syntax. A beginner I think could
> learn Lisp much faster than Python.
>
> Therefore, it seems like Lisp *should* be easier to work with and more readable. I don't feel like it is easier to use but I can't see *why* that is.
>
> My best guess.....
>
> Lisp pros: simpler syntax
> Lisp cons: prefix notation, lots more parentheses
>
> My hypothesis is that the cons slightly outweigh the pros of Lisp
> which is why Python is easier to work with and is more readable in the end?

I concur with Chris Angelico there. The word "simple" is ambiguous.
"Simpler" for the human is not the same as "simpler" for the computer

In Lisp, the grammar is "simpler", meaining that the definition of the
grammar is shorter; this makes it simpler for the compiler to parse, and
to write a compiler for Lisp.

In Python, the grammar is very complicated, writing a compiler for
Python is a big task - still it is "simpler" to translate your ideas
into Python

It is related to the old saying "if all you have is hammer, then
everything looks like a nail". In Lisp, your hammer is the list. So you
are forced to map your problems onto list processing. For some things
that works well, for others not so well (infix math....) .

In, say, Java, your tool is classes and inheritance. There are big books
on "design patterns" that teach you how to map your problem onto
inheritance. For some things, that works well, for others not so well
("abstract factory", "visitor pattern", ....)

In Python, you have an awfully complex of syntax, so your toolset
includes list processing, lambda, inheritance, string interpolation,
decorators....
This makes it possible to use the tool which best matches the language
of your problem. Many problem domains have their own language, e.g.
matrix math for linear algebra, pipes for sequential stream processing
etc. The easier it is to translate the algorithm on paper into the
runnable version, the

Lisp is still impressive, because it is very good at metaprogramming. It
shows how far you can get with so little syntax.

Another point to consider is the ecosystem of your language. If you
install Python, then you get basic math, I/O, a GUI toolkit, network
libraries, ... In more "traditional" languages like C or Lisp, you get
math and I/O, period. For everything else you need to hunt down a
library. Therefore, solve the task "download the gimp installer from
github via https" requires 2,3 lines in Python and installing a
(possibly complex) library for the same task in Lisp or C.

Christian

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

I wrote:
> > > Trying to maintain that recursive list of unclosed lists in your
> > > brain is fun. It stretches the brain in interesting ways.
> > > [ ... ] But I never found Lisp code very maintainable, [ ... ]

2QdxY4RzWzUUiLuE@potatochowder.com writes:
> "[R]ecursive list of unclosed lists"? Can you (whoever you are) expand
> on that? Yes, if you eschew helper functions and local variables, then
> you can end up with depply nested code, but that's true in any language.

To pick a function that I know is readily available in lots
of languages, let's look at a couple implementations of the
Haversine function (from http://rosettacode.org/wiki/Haversine_formula).
Comments to illustrate language differences are mine.

Here's the Common Lisp version.

(defparameter *earth-radius* 6372.8)
(defparameter *rad-conv* (/ pi 180))
;; Minor complication right off: assignment of variables or constants
;; is completely different depending on whether you're
;; defining something in general, like here, or only for
;; a subsequent clause, like the let* functions later on.

(defun deg->rad (x)
(* x *rad-conv*))
;; Prefix notation for arithmatic is unfamiliar to most people
;; since that's not what we learn in school, so that's a first
;; hurdle for readability.

(defun haversine (x)
(expt (sin (/ x 2)) 2))
;; To grok this function you need to have four levels of
;; parentheses simultaneously open in your head.

(defun dist-rad (lat1 lng1 lat2 lng2)
(let* ((hlat (haversine (- lat2 lat1)))
;; Then there's the let vs. let* issue,
;; no big deal for experienced programmers
;; but not entirely easy to explain to a beginner.
;; On the other hand, Python has its own confusing points on
;; that issue, like when you need to specify "global".
(hlng (haversine (- lng2 lng1)))
(root (sqrt (+ hlat (* (cos lat1) (cos lat2) hlng)))))
;; for that expression you need 7 levels of mental parens open
(* 2 *earth-radius* (asin root))))

(defun dist-deg (lat1 lng1 lat2 lng2)
(dist-rad (deg->rad lat1)
(deg->rad lng1)
(deg->rad lat2)
(deg->rad lng2)))

;; End Lisp example

Seven levels of unclosed lists that you need to keep in your head
in order to read and understand the program at its deepest point.

Here's the same thing in Python:

from math import radians, sin, cos, sqrt, asin

def haversine(lat1, lon1, lat2, lon2):
R = 6372.8 # Earth radius in kilometers

dLat = radians(lat2 - lat1)
dLon = radians(lon2 - lon1)
lat1 = radians(lat1)
lat2 = radians(lat2)

a = sin(dLat / 2)**2 + cos(lat1) * cos(lat2) * sin(dLon / 2)**2
c = 2 * asin(sqrt(a))

return R * c

# end Python example

The equation is still the same equation, but it looks a lot more
like the equation you'd see in a math textbook, or write on a
homework assignment, modulo notational issues like ** instead of
superscripts. The deepest level of parentheses you ever need to
keep in your head is two, but the second level is just a very
simple function call, sqrt(a). The indentation level (the program
structure) never gets beyond one.

On the other hand, your brain does need to keep track of more
intermediate variables (dLat, dLon etc.) Perhaps some people might
find that harder.

And yes, you could write the Lisp to look more like the Python or
vice versa. You're welcome to try that, but I predict you'll find that
even if you use the same number of intermediate variables, Lisp will
always require you to keep that larger mental stack of open parens.

> Because of Lisp's simple syntax, text editors can nearly completely
> relieve the programmer from the tedium of indenting and formatting, and
> even closing parenthesis, which also highlights missing/extra/unbalanced
> parentheses pretty quickly.

I find that emacs mostly does a pretty good job of figuring out
indentation, closing parentheses, highlighting syntax errors and
similar boilerplate in Python. Maybe you need a smarter text editor?

But my comment about levels of parens had nothing to do with editors.
To understand the code, you need to build up that list/tree
structure in your head, because that's what defines the program logic.

Again, my point isn't that Python is a better or simpler language
than Lisp. It's that it stretches the brain in different ways, and that
I would guess (but it's just a guess) that most beginners will find
the Python approach more intuitive and easier to learn, since it
emphasizes things they've done before (simple declarative statements,
equations written out in a familiar way) rather than new and unfamiliar
concepts (prefix notation, deeply nested parentheses, tree structures).

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

On 2020-08-07 at 17:55:45 +0200,
Marco Sulla <Marco.Sulla.Python@gmail.com> wrote:

> On Fri, 7 Aug 2020 at 17:14, Christian Seberino <cseberino@gmail.com> wrote:

> Commonly, in imperative languages like C, you can write
>
> if (a = b) {...}
>
> This is allowed in C, even if a = b is not an expression ...

In C, a = b *is* an expression. An assignment expression that uses the
assignment operator. See
<https://en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B>.

> ... 99% of times you simply wrong and wanted:

> if (a == b)

Where did 99% come from?

> Python separates statements and expressions, so where you expect an
> expression, you can't write a statement.

Yes.

> Maybe Lisp does not separate expressions and statements because it
> supports both functional and imperative programming ...

It's not a matter of separating expressions from statements. Lisp
doesn't have statements. It only has expressions. If you choose to
write imperative code in Lisp, all you're really doing is using the
expressions for their side effects rather than their values.

> PS: Recently there's an exception: if you *really* want an assignment
> when an expression is expected, you can use the "walrus" := operator.
> IMO it renders the code less readable and I'm not sure about it's
> usefulness.

It makes some code more concise. Readability is in the eye of the
beholder.

> @Chris: note that "real" recursion in Python is not possible, since
> there's no support for tail recursion. Maybe something similar can be
> done using async functions.

Python has real recursion. Whether or not there's tail recursion on the
inside is an implementation detail.
--
https://mail.python.org/mailman/listinfo/python-list

On 8/7/20 11:55 AM, Marco Sulla wrote:
> Commonly, in imperative languages like C, you can write
>
> if (a = b) {...}
>
> This is allowed in C, even if a = b is not an expression, but an
> assignment statement. 99% of times you simply wrong and wanted:

But in C (and related languages) it IS an expression, and C doesn't have
an 'assignment statement' but an 'expression statement', which is the
source of the issue. = is just another operator, which happens to modify
the value of its left operand.

Python makes assignment a full top level type of statement, so = can't
be misused in an expression thinking it means an equality test (and then
added recently the := operator, so that for the cases you actually want
to do assignments in the middle of an expression you can).

--
Richard Damon

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

On 8/7/20 11:46 AM, Chris Angelico wrote:
> My point is that doing Fibonacci recursively is arguably more elegant
> while being materially worse at performance, but there are other
> examples that are fundamentally recursive, are just as elegant (merge
> sort: "fracture the array in half, sort each half, then merge them"),
> and can't be done better iteratively. So IMO Fibonacci is a flawed
> demonstration of what is a very valid point ("recursion can be really
> elegant"), and other examples would serve the purpose better.

I would say that doing the recursive Fibonacci version can be an
important step (near the end) of the recursion unit as a learning
experience on some of the dangers of recursion (like turning an O(N)
problem into O(2**N). It perhaps can lead to discussions on optimization
techniques (like caching results) that can alleviate some of the issues
(at other costs).

--
Richard Damon

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

On Sat, Aug 8, 2020 at 2:21 AM <2QdxY4RzWzUUiLuE@potatochowder.com> wrote:
>
> On 2020-08-07 at 17:55:45 +0200,
> Marco Sulla <Marco.Sulla.Python@gmail.com> wrote:
> > @Chris: note that "real" recursion in Python is not possible, since
> > there's no support for tail recursion. Maybe something similar can be
> > done using async functions.
>
> Python has real recursion. Whether or not there's tail recursion on the
> inside is an implementation detail.

More specifically: Python has real recursion. Whether or not tail
recursion is optimized away is an implementation detail.

Tail call optimization (there's no reason to restrict it to recursion
alone) is something a Python implementation could choose to do, but
the trouble is that full optimization tends to destroy traceback
information, so it's often not worth doing. And the cases where
partial optimization is of value just aren't compelling enough for
anyone to implement it into CPython, nor any other major
implementation (to my knowledge). The biggest uses for TCO tend to be
the situations where recursion is the wrong solution to the problem.

But recursion? Recursion is definitely possible.

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

On Sat, Aug 8, 2020 at 2:44 AM Richard Damon <Richard@damon-family.org> wrote:
>
> On 8/7/20 11:46 AM, Chris Angelico wrote:
> > My point is that doing Fibonacci recursively is arguably more elegant
> > while being materially worse at performance, but there are other
> > examples that are fundamentally recursive, are just as elegant (merge
> > sort: "fracture the array in half, sort each half, then merge them"),
> > and can't be done better iteratively. So IMO Fibonacci is a flawed
> > demonstration of what is a very valid point ("recursion can be really
> > elegant"), and other examples would serve the purpose better.
>
> I would say that doing the recursive Fibonacci version can be an
> important step (near the end) of the recursion unit as a learning
> experience on some of the dangers of recursion (like turning an O(N)
> problem into O(2**N). It perhaps can lead to discussions on optimization
> techniques (like caching results) that can alleviate some of the issues
> (at other costs).

Yes, I'd definitely agree. It's great to have some demonstrations of
the advantages and disadvantages of recursion, and Fibonacci offers
both in one tidy package :)

Here's another really great example: triangle numbers.

def tri(n):
if n < 1: return 0
return n + tri(n - 1)

def tri(n):
tot = n
for i in range(n):
tot += i
return tot

def tri(n):
return functools.reduce(operator.add, range(n + 1))

def tri(n):
return n * (n + 1) // 2

A great demo of different ways to think about the same problem, with a
nice O(1) reference at the end that you can validate them against :)

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

About statement vs expression: maybe you, Richard and
2QdxY4RzWzUUiLuE, are right, maybe not. This is hard to say, since the
official C documentation is not public and you have to pay a small fee
to obtain it.

Anyway, I said "in C, the assignment is a statement that can be used
in expression". You're saying "No, in C the assignment IS an
expression".
I don't see the difference. If the assignment is a statement that can
be used as an expression, Python simply forbids that. If in C the
assignment is an expression, Python on the contrary treats it as a
statement.

The only real difference is that Python not only clearly separated the
concepts of statement and expression, but also _where_ you can use
them, for practical reasons.
--
https://mail.python.org/mailman/listinfo/python-list

On Fri, 7 Aug 2020 at 18:48, Chris Angelico <rosuav@gmail.com> wrote:
> Tail call optimization (there's no reason to restrict it to recursion
> alone) is something a Python implementation could choose to do, but
> the trouble is that full optimization tends to destroy traceback
> information

Indeed this is implemented in asyncio.
--
https://mail.python.org/mailman/listinfo/python-list

Your iterative fib(x) code and comment was quite nice.
--
https://mail.python.org/mailman/listinfo/python-list

> Another point to consider is the ecosystem of your language. If you
> install Python, then you get basic math, I/O, a GUI toolkit, network
> libraries, ... In more "traditional" languages like C or Lisp, you get
> math and I/O, period. For everything else you need to hunt down a
> library. Therefore, solve the task "download the gimp installer from
> github via https" requires 2,3 lines in Python and installing a
> (possibly complex) library for the same task in Lisp or C.
>
> Christian

I like this post so much I printed it. It seems you're saying
Python has lots of syntax forms or "mini-languages" in it and *that* is a big
reason why you can typically find syntax that makes an arbitrary
problem more readable in Python. On the other hand, Lisp tries
to everything with less syntax forms (paradigms) and hence it is less readable.

A Lisp person would probably say that they can create domain specific
languages (DSLs) for whatever they wish. However, many people like
that Python has so many standardized "DSLs" ready to go for you from
the start.

I think this is really significant point why more syntax does necessarily mean less readability.

I would just add that Clojure finally solved the ecosystem problem with
Lisp by giving it access to the Java libraries.

cs

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

On 8/7/20 12:52 PM, Marco Sulla wrote:
> About statement vs expression: maybe you, Richard and
> 2QdxY4RzWzUUiLuE, are right, maybe not. This is hard to say, since the
> official C documentation is not public and you have to pay a small fee
> to obtain it.
>
> Anyway, I said "in C, the assignment is a statement that can be used
> in expression". You're saying "No, in C the assignment IS an
> expression".
> I don't see the difference. If the assignment is a statement that can
> be used as an expression, Python simply forbids that. If in C the
> assignment is an expression, Python on the contrary treats it as a
> statement.
>
> The only real difference is that Python not only clearly separated the
> concepts of statement and expression, but also _where_ you can use
> them, for practical reasons.

The difference is that the two languages define 'expression' differently.

In Python, the = operation is not part of the general expression syntax,
but is specifically allowed only in specific locations.

In C, the = operator is exactly like all the other operators in how it
is parsed, it just has some restrictions on the type that can be on the
left side, and that it changes that value (but then, so do a few other
operators like ++)

In C, there is NO 'statement' called an assignment statement, because
assignments are just parts of expressions, so the statement type
'expression statement' handles both.

In Python, because assignment is NOT just part of an expression, it
needs a separate statement type to handle assignments, to allow them.


(BTW, while the official C Standards are only available at a price, the
draft standards prepared during the development of the final are all
available for free and the last published draft standard is almost
always virtually identical to the final released standard, so most
people will just use those. People who really need the official versions
can pay the price for it, and for them, that price isn't that high to
them). I keep the free downloads of all the major version of the C and
C++ language available on my computer.

--
Richard Damon

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

On 2020-08-07 at 10:00:25 -0600,
Akkana Peck <akkana@shallowsky.com> wrote:

> I wrote:
> > > > Trying to maintain that recursive list of unclosed lists in your
> > > > brain is fun. It stretches the brain in interesting ways.
> > > > [ ... ] But I never found Lisp code very maintainable, [ ... ]
>
> 2QdxY4RzWzUUiLuE@potatochowder.com writes:
> > "[R]ecursive list of unclosed lists"? Can you (whoever you are) expand
> > on that? Yes, if you eschew helper functions and local variables, then
> > you can end up with depply nested code, but that's true in any language.
>
> To pick a function that I know is readily available in lots
> of languages, let's look at a couple implementations of the
> Haversine function (from http://rosettacode.org/wiki/Haversine_formula).
> Comments to illustrate language differences are mine.
>
> Here's the Common Lisp version.
>
> (defparameter *earth-radius* 6372.8)
> (defparameter *rad-conv* (/ pi 180))
> ;; Minor complication right off: assignment of variables or constants
> ;; is completely different depending on whether you're
> ;; defining something in general, like here, or only for
> ;; a subsequent clause, like the let* functions later on.
>
> (defun deg->rad (x)
> (* x *rad-conv*))
> ;; Prefix notation for arithmatic is unfamiliar to most people
> ;; since that's not what we learn in school, so that's a first
> ;; hurdle for readability.

My first calculator was RPN, so prefix wasn't really a hurdle. ;-)

> (defun haversine (x)
> (expt (sin (/ x 2)) 2))
> ;; To grok this function you need to have four levels of
> ;; parentheses simultaneously open in your head.
>
> (defun dist-rad (lat1 lng1 lat2 lng2)
> (let* ((hlat (haversine (- lat2 lat1)))
> ;; Then there's the let vs. let* issue,
> ;; no big deal for experienced programmers
> ;; but not entirely easy to explain to a beginner.
> ;; On the other hand, Python has its own confusing points on
> ;; that issue, like when you need to specify "global".
> (hlng (haversine (- lng2 lng1)))
> (root (sqrt (+ hlat (* (cos lat1) (cos lat2) hlng)))))
> ;; for that expression you need 7 levels of mental parens open
> (* 2 *earth-radius* (asin root))))
>
> (defun dist-deg (lat1 lng1 lat2 lng2)
> (dist-rad (deg->rad lat1)
> (deg->rad lng1)
> (deg->rad lat2)
> (deg->rad lng2)))
>
> ;; End Lisp example
>
> Seven levels of unclosed lists that you need to keep in your head
> in order to read and understand the program at its deepest point.

Seven? Oh, there it is, inside the calculation of root in dist-rad.

> Here's the same thing in Python:

It's equivalent. It's not the same. (For example, in Lisp, the
parameters are clearly marked as such by the form defparameter, but in
Python, the parameters and the temporary variables are created with the
same syntax. When I read the Python code, how can I tell that R is a
parameter rather than a temporary variable? But that's not related to
the question of open parentheses. Also, the Lisp example separates the
conversion to radians into a helper function, but the Python version
doesn't.)

> from math import radians, sin, cos, sqrt, asin
>
> def haversine(lat1, lon1, lat2, lon2):
> R = 6372.8 # Earth radius in kilometers
>
> dLat = radians(lat2 - lat1)
> dLon = radians(lon2 - lon1)
> lat1 = radians(lat1)
> lat2 = radians(lat2)
>
> a = sin(dLat / 2)**2 + cos(lat1) * cos(lat2) * sin(dLon / 2)**2
> c = 2 * asin(sqrt(a))
>
> return R * c
>
> # end Python example
>
> The equation is still the same equation, but it looks a lot more
> like the equation you'd see in a math textbook, or write on a
> homework assignment, modulo notational issues like ** instead of
> superscripts. The deepest level of parentheses you ever need to
> keep in your head is two, but the second level is just a very
> simple function call, sqrt(a). The indentation level (the program
> structure) never gets beyond one.
>
> On the other hand, your brain does need to keep track of more
> intermediate variables (dLat, dLon etc.) Perhaps some people might
> find that harder.

On the other other hand, there's no confusing operator precedence rules
in Lisp. We know the basic arithmetic operators from grade school, but
who can remember whether & or and bind more tightly than or and | (sic)?
Instead of memory, some programmers use *parentheses* to *clarify*. ;-)

> And yes, you could write the Lisp to look more like the Python or
> vice versa. You're welcome to try that, but I predict you'll find that
> even if you use the same number of intermediate variables, Lisp will
> always require you to keep that larger mental stack of open parens.

A larger stack of *parentheses*, yes, but I don't think a larger stack.

Python: def f(x):
y = b + m * x
return y

Lisp: (defun f (x)
(let ((y (+ b (* m x))))
y))

A function definition, a temporary variable, the familiar "point slope"
artithmetic, and the result of the calculation/function. Now that I've
seen enough Lisp, the parentheses disappear into the whitespace.

> > Because of Lisp's simple syntax, text editors can nearly completely
> > relieve the programmer from the tedium of indenting and formatting, and
> > even closing parenthesis, which also highlights missing/extra/unbalanced
> > parentheses pretty quickly.
>
> I find that emacs mostly does a pretty good job of figuring out
> indentation, closing parentheses, highlighting syntax errors and
> similar boilerplate in Python. Maybe you need a smarter text editor?

Emacs... emacs... emacs... Oh, yeah! Emacs! I used to edit my own
config.h file, before the great emacs/xemacs schism (and I'm using a
more modern version to compose this email). ;-)

> But my comment about levels of parens had nothing to do with editors.
> To understand the code, you need to build up that list/tree
> structure in your head, because that's what defines the program logic.
>
> Again, my point isn't that Python is a better or simpler language
> than Lisp. It's that it stretches the brain in different ways, and that
> I would guess (but it's just a guess) that most beginners will find
> the Python approach more intuitive and easier to learn, since it
> emphasizes things they've done before (simple declarative statements,
> equations written out in a familiar way) rather than new and unfamiliar
> concepts (prefix notation, deeply nested parentheses, tree structures).

Aha. I think.

In Python, different levels of logical nesting use different physical
representations. Indentation, parentheses, operators (and operator
precedence), keywords, colons. But in Lisp, the only tool you have is
parentheses (humans use whitespace sometimes, but the compiler ignores
it). The differences are likely real, and perhaps moreso to beginners,
but if the nesting is too deep, in either case, refactor, and everyone
has their own definition of "too deep."

For completeness, let's not forget Greenspun's Tenth (which really isn't
about the syntax) and Lisp's loop macro (which *is* entirely all about
the syntax). ;-)
--
https://mail.python.org/mailman/listinfo/python-list

> In Lisp, your hammer is the list.

> In, say, Java, your tool is classes and inheritance.

And yet if Lisp or Java programmers were here they would say their
languages //are// multi-paradigm too. For example, Lisp has the
Common Lisp Object System (CLOS) and Java has the Vector class and so on.

Maybe Python somehow gives more paradigms //better// syntax support
whereas in Lisp and Java they are somewhat "bolted on" and not done
as well?

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

> It's also probably significantly slower, so you'd likely still want to
> use the iterative version

Generalizing this to the majority of recursive functions/methods, are their
iterative counterparts more efficient? (I say "majority of" because I've
personally encountered one or two recursive functions/methods that were
either very difficult for me to translate to iteration or just not possible
with my skill level at the time)

> It is related to the old saying "If all you have is a hammer, then
> everything looks like a nail".

Using this saying in the context of programming languages is extremely
accurate! Because Python can be object oriented or data oriented, it is a
large toolbox capable of tackling an even larger set of problems quite
simply.

I've never personally used Lisp, but I have used Java a bit. Even just the
strict object-oriented nature of Java was fairly cumbersome. The freedom,
fluidity, and the dynamic nature of Python are the reasons it's my
preferred language.

For just a moment, allow me to abstract this argument to include languages
other than Lisp I'm better versed in. Older languages, like Java and C,
required explicit typing for their variables, explicit output types for
their methods, and semicolons and brackets instead of utilized whitespace.
Please correct me if I'm wrong, but this system was primarily for saving
memory because computers were far less powerful when these languages were
born. Python, being a relatively young language, is free from these
shackles and was built to run on more modern computers where bits and bytes
are not a common constraint.

That said, if I were to ever design a software I planned on sharing, I
would write it in one of the more space-friendly languages.

Thank y'all for the great reading about Lisp vs Python and letting me get
very off-topic.

Best,
Wyatt Biggs
--
https://mail.python.org/mailman/listinfo/python-list

On Fri, 7 Aug 2020 at 19:48, Richard Damon <Richard@damon-family.org> wrote:
> The difference is that the two languages define 'expression' differently. [...]

I don't know if this is interesting or pertinent to the topic.

Christian Seberino just expressed a doubt about how a clear separation
between a statement and an expression is quite desiderable in the
"real" programming world. And I tried to explain it with the
assignment operation, since a ton of programmers feel very frustrated
about reading code of other programmers with assignment in an if
statement. I'm quite sure that they thought, as I thought: "What do
this?"
Worse when their program failed and they discovered that they wrote
`if (a=b)` instead of `if (a==b)`.

I'm just more curious about why Lisp programmers think that it's
better to not make a hard distinction between statements and
expressions.
--
https://mail.python.org/mailman/listinfo/python-list

On 2020-08-07 at 11:02:50 -0700,
Christian Seberino <cseberino@gmail.com> wrote:

> > In Lisp, your hammer is the list.
>
> > In, say, Java, your tool is classes and inheritance.
>
> And yet if Lisp or Java programmers were here they would say their
> languages //are// multi-paradigm too. For example, Lisp has the
> Common Lisp Object System (CLOS) and Java has the Vector class and so on.

Of what is "Java has the Vector class" an example? That the tools in
Java are classes and inheritance?
--
https://mail.python.org/mailman/listinfo/python-list

On 8/7/2020 11:46 AM, Chris Angelico wrote:

> My point is that doing Fibonacci recursively is arguably more elegant
> while being materially worse at performance.

This is a common misconception. Linear iteration and tail recursion are
equivalent. The issue is calculating values once versus multiple times.
Here is the fast recursion equivalent to the fast iteration.

def fib(n, pair=(1,0)):
previous, current = pair
if n:
return fib(n-1, (current, previous + current))
else:
return current

for i in range(10): print(fib(i), end=' ')
# 0 1 1 2 3 5 8 13 21 34

One can also do the slow algorithm, with wasteful duplication,
iteratively with one or two stacks of values instead of the hidden stack
of execution frames. I don't remember the details right now without
checking a text.

--
Terry Jan Reedy

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

On 2020-08-07 at 21:54:35 +0200,
Marco Sulla <Marco.Sulla.Python@gmail.com> wrote:

> On Fri, 7 Aug 2020 at 19:48, Richard Damon <Richard@damon-family.org> wrote:

> Christian Seberino just expressed a doubt about how a clear separation
> between a statement and an expression is quite desiderable in the
> "real" programming world. And I tried to explain it with the
> assignment operation, since a ton of programmers feel very frustrated
> about reading code of other programmers with assignment in an if
> statement. I'm quite sure that they thought, as I thought: "What do
> this?"
> Worse when their program failed and they discovered that they wrote
> `if (a=b)` instead of `if (a==b)`.

Don't conflate the concept with the syntax. The fact that Python now
has "the walrus operator" says that assignment expressions are useful.
The issue with the C version is that the assignment and comparison
operators look too much alike and using the wrong one can cause *silent*
catastrophes (although modern C compilers can and do emit appropriate
warnings or errors, if you ask them nicely).

> I'm just more curious about why Lisp programmers think that it's
> better to not make a hard distinction between statements and
> expressions.

Simplicity of syntax. Very few languages have a simpler syntax than
Lisp (Ook, et al, notwithstanding).
--
https://mail.python.org/mailman/listinfo/python-list

On 2020-08-07 at 13:43:06 -0500,
Wyatt Biggs <wyatt.biggs@gmail.com> wrote:

> > It's also probably significantly slower, so you'd likely still want to
> > use the iterative version
>
> Generalizing this to the majority of recursive functions/methods, are
> their iterative counterparts more efficient? (I say "majority of"
> because I've personally encountered one or two recursive
> functions/methods that were either very difficult for me to translate
> to iteration or just not possible with my skill level at the time)

As usual, it depends. :-)

Often, a recursive algorithn in the *source* code is rewritten/optimized
by a compiler into an iterative algorithm in the *object* code. And
sometimes, iterative code is rewritten into straight line imperative
code (i.e., loop unrolling, constant folding, etc.). At runtime, that
stack of pending items has to be somewhere, and the hardware stack
(where the CPU-level return addresses are stored) can be as good a place
as any, which means that the recursive version *might* be as fast or
faster than the iterative version, under certain circunstances.

> For just a moment, allow me to abstract this argument to include
> languages other than Lisp I'm better versed in. Older languages, like
> Java and C, required explicit typing for their variables, explicit
> output types for their methods, and semicolons and brackets instead of
> utilized whitespace. Please correct me if I'm wrong, but this system
> was primarily for saving memory because computers were far less
> powerful when these languages were born. Python, being a relatively
> young language, is free from these shackles and was built to run on
> more modern computers where bits and bytes are not a common
> constraint.

Lisp is older than both C and Java (by decades), and there's still no
explicit typing for variables. In Lisp, the data has a type, and the
"variables" are just names for it (just like Python, or rather Python is
just like Lisp).

> That said, if I were to ever design a software I planned on sharing, I
> would write it in one of the more space-friendly languages.

Space-friendly?
--
https://mail.python.org/mailman/listinfo/python-list

On Fri, 7 Aug 2020 at 19:41, Christian Seberino <cseberino@gmail.com> wrote:
> I think this is really significant point why more syntax does necessarily mean less readability.

I don't think so. Readability of programming languages was measured
using an objective method, and Python was one of the most readable.

The fact that a grammar is simpler does not mean it's more readable
for human beings. It's surely most simple to optimize for compilers.
For example, RISC instructions in CPUs were simpler than CISC. Even if
Intel tried to defend CISC, modern Intel CPUs have reduced their set
of instructions a lot. Furthermore, the majority of smartphone CPUs
are ARM, that have RISC instructions.
Think also about NAND. You can express the whole boolean logic using
only NAND or NOR. In the beginning, only the Military and NASA
constructed electrical circuits only with NAND or NOR gates. Now there
are electronic circuits made for common people, using only or mainly
NAND gates: they are, for example, pen cards and SSD drives.

But they are not simpler to understand. For example, in math you
*could* think a*b as a+a done b times. But what if a and b are
imaginary numbers?

There are many programmers that just feel Python much more simple to
read and use. Google can tell you a lot about this. Also Rosetta code
can show it to you clearly:
http://www.rosettacode.org/wiki/Rosetta_Code

It seems to me that you want to convince your colleagues that Python
is better than Lisp. I think that:

1. there's not a "best". The "best" depends heavily on what you need.
2. the people you have to convince is only yourselves
3. to convince yourselves, you have to try. "Refuse the temptation to guess" :)
--
https://mail.python.org/mailman/listinfo/python-list

On Fri, 7 Aug 2020 at 22:35, Terry Reedy <tjreedy@udel.edu> wrote:
> This is a common misconception. Linear iteration and tail recursion are
> equivalent. The issue is calculating values once versus multiple times.
> Here is the fast recursion equivalent to the fast iteration.
>
> def fib(n, pair=(1,0)):
> previous, current = pair
> if n:
> return fib(n-1, (current, previous + current))
> else:
> return current
>
> for i in range(10): print(fib(i), end=' ')
> # 0 1 1 2 3 5 8 13 21 34

It seems to me a sort of not persistent caching. If you do:

fib(very_large_number)

without calculating any previous Fibonacci number before, it will be
very slow and you could have a stack overflow.

A language with tail call optimization will execute it faster and with
less memory. Otherwise why asyncio de-facto implemented tail
optimization?

PS: it seems there's a module that implement tail call:
https://github.com/baruchel/tco
--
https://mail.python.org/mailman/listinfo/python-list

On Sat, Aug 8, 2020 at 6:34 AM Terry Reedy <tjreedy@udel.edu> wrote:
>
> On 8/7/2020 11:46 AM, Chris Angelico wrote:
>
> > My point is that doing Fibonacci recursively is arguably more elegant
> > while being materially worse at performance.
>
> This is a common misconception. Linear iteration and tail recursion are
> equivalent. The issue is calculating values once versus multiple times.
> Here is the fast recursion equivalent to the fast iteration.
>
> def fib(n, pair=(1,0)):
> previous, current = pair
> if n:
> return fib(n-1, (current, previous + current))
> else:
> return current
>
> for i in range(10): print(fib(i), end=' ')
> # 0 1 1 2 3 5 8 13 21 34
>
> One can also do the slow algorithm, with wasteful duplication,
> iteratively with one or two stacks of values instead of the hidden stack
> of execution frames. I don't remember the details right now without
> checking a text.

I'm aware you can do recursion iteratively and iteration recursively,
but why WOULD you ever do this? The version you've shown here isn't
any more elegant than the purely iterative version, and all it's doing
is implementing a for loop using recursive calls. (Also, it has one
thing that rankles with me, and that's a function signature that is
intentionally different for the recursive calls as for the main call.
You should *never* pass the 'pair' parameter on the initial call, and
it will *always* be passed on the recursive calls.) The idiomatic
recursive version is not tail recursive. Same with the idiomatic
recursive merge sort, which does forking recursion and then tail-calls
the merge operation. (Or you can implement the merge inline, but
whenever I'm explaining it, I prefer to write merge() as a separate
function.)

Knowing how to translate recursion into iteration and vice versa is a
useful skill (picture this: you're trying to build some actual coded
logic into an alias expansion system, where the only conditional you
have is "execute this file" with text substitution in the file name,
and the only looping you have is to re-execute the same file), but
it's not the way to show off the beauty of recursion.

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

On 8/7/20 4:08 PM, Terry Reedy wrote:
> On 8/7/2020 11:46 AM, Chris Angelico wrote:
>
>> My point is that doing Fibonacci recursively is arguably more elegant
>> while being materially worse at performance.
>
> This is a common misconception.  Linear iteration and tail recursion
> are equivalent.  The issue is calculating values once versus multiple
> times.  Here is the fast recursion equivalent to the fast iteration.
>
> def fib(n, pair=(1,0)):
>    previous, current = pair
>    if n:
>       return fib(n-1, (current, previous + current))
>    else:
>       return current
>
> for i in range(10): print(fib(i), end=' ')
> # 0 1 1 2 3 5 8 13 21 34
>
> One can also do the slow algorithm, with wasteful duplication,
> iteratively with one or two stacks of values instead of the hidden
> stack of execution frames.  I don't remember the details right now
> without checking a text.
>
But your example breaks the 'problem' in the recursion that Fibonacci,
when expressed 'naturally', the current value is based on two different
earlier values. You have morphed the definition, using basically the
iterative solution, so that the recursive call to fir(0, ...) doesn't
actually calculate the fib(0) value, but fib(n).

Yes, this shows that you can convert an iterative solution into a
recursive solution with a bit of hand waving, but you still end up with
a program based on the iterative algorithm, not the possibly natural
recursive one.

--
Richard Damon

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

On Sat, Aug 08, 2020 at 01:46:28AM +1000, Chris Angelico wrote:
> On Sat, Aug 8, 2020 at 1:38 AM Python <python@bladeshadow.org> wrote:
> TBH most people won't get the recursive version right the first time
> either.

So FWIW, I/my team don't find this to be true. I was originally going
to mention this in my previous post but decided to leave it out
for brevity (and in part because I assumed anyone familiar with the
problem already expected it was so).

In fact my team frequently uses Fibonacci as an interview question.
We've been doing so for at least a decade, so we do have a
not-insubstantial sample size. We find that candidates can much more
easily implement the recursive version correctly, and do so on the
first try roughly 70-80% of the time. Nearly all candidates choose to
implement the recursive version for that reason. Those that don't are
pretty familiar with the problem, and choose the iterative version so
they can "show off" their knowledge of the performance benefits. They
typically also implement the recursive version immediately after,
because it's pretty trivial to do it in most programming languages,
and because they assume the point of the question is to ascertain
whether they grok recursion. Which is partly true, but only
partly--we use it because it is a short problem that can be quickly
implemented, and demonstrates a few different interesting concepts,
one of which is recursion.

When we do use it, we always follow up with "Can you implement this
iteratively?" (assuming they didn't already). A small percentage
insist that it is impossible. Most who try (again, roughly 70-80%)
fail on the first try. Figuring out how to correctly prime the state
is pretty much invariably the sticking point.

These are not students, they are experienced programmers. This may
explain why they usually can easily implement the recursive version,
but it does not really address why most of them have trouble with the
iterative version. :)

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

On 8/7/2020 11:55 AM, Marco Sulla wrote:

> @Chris: note that "real" recursion in Python is not possible,

This is backwards. Python only does real recursion when one writes
recursive calls.

> since there's no support for tail recursion.

I am pretty sure that what you mean by 'support' is to turn tail
recursive syntax into iteration, making it fake recursion.


--
Terry Jan Reedy

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

On 8/7/20 3:54 PM, Marco Sulla wrote:
> On Fri, 7 Aug 2020 at 19:48, Richard Damon <Richard@damon-family.org> wrote:
>> The difference is that the two languages define 'expression' differently. [...]
> I don't know if this is interesting or pertinent to the topic.
>
> Christian Seberino just expressed a doubt about how a clear separation
> between a statement and an expression is quite desiderable in the
> "real" programming world. And I tried to explain it with the
> assignment operation, since a ton of programmers feel very frustrated
> about reading code of other programmers with assignment in an if
> statement. I'm quite sure that they thought, as I thought: "What do
> this?"
> Worse when their program failed and they discovered that they wrote
> `if (a=b)` instead of `if (a==b)`.
>
> I'm just more curious about why Lisp programmers think that it's
> better to not make a hard distinction between statements and
> expressions.

Actually, they might put a fairly hard distinction between statements
and expressions, a statement is a list that begins with a programmatic
atom, while an expression is a list that begins with an operator atom.

The fact that EVERYTHING is a list, makes those not used to the idea see
it as all the same (which I suppose in a way it is).

One side effect of this is that a program isn't just a bunch of
statements in sequence, but is actually a LIST of those statements, so
the whole program becomes effectively a single list.

The really interesting part is that since Lisp programs manipulate lists
as data, and the program is just a list, Lisp programs have the
theoretical ability to edit themselves (assuming the implementation give
access to the list of the program to the program).

Now for the general separation of expression from statement, which isn't
really as applicable to Lisp, since (if I remember right) assignment
doesn't use the = token, so you are less apt to make the mistake, there
are several arguments.

The confusion of assignment for equality comparison is likely on of the
big issues.

Some languages solve the problem by making assignments a special type of
statement, so you can't make the mistake, some of these even make = be
both, so the have to make the distinction.

Some languages (like C) make assignment just a 'normal' operator,  and
either just trust the programmer or use conventions to help generate
warnings (either at compile time or a separate Lint phase). People using
these languages will either like the additional power it give, or curse
the language for the additional opportunities to make mistakes (or
both). Some langagues make the mistake harder to make by using some
symbol other than = for assignment, like Pythons new := symbol.

One advantage of blurring the line between statements and expressions is
power, putting assignments in the middle of an expression, can allow
code to be more compact. Some extensions to C are even trying to take
this farther, and letting the programmer embed a { } block into a
statement as an expression, which is perhaps taking that idea to an extreme.

--
Richard Damon

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

On Sat, 8 Aug 2020 at 00:28, Richard Damon <Richard@damon-family.org> wrote:
> The really interesting part is that since Lisp programs manipulate lists
> as data, and the program is just a list, Lisp programs have the
> theoretical ability to edit themselves (assuming the implementation give
> access to the list of the program to the program).

This is a bit hard to understand for me.
I know that code can be translated to an AST, that is a tree. It's
quite difficult for me to imagine the code organized as a list. Do you
have some links about it?

On Sat, 8 Aug 2020 at 00:28, Richard Damon <Richard@damon-family.org> wrote:
> One advantage of blurring the line between statements and expressions is
> power, putting assignments in the middle of an expression, can allow
> code to be more compact.

I agree with you. I experimented a little with CPython code and I saw
assignments inside if statements. The code without them was less
readable. I also found this example:
https://stackoverflow.com/a/151920/1763602
My only fear is the abuse. How many people really use the walrus
operator to render the code more readable? My fear is that the
majority of programmer will use it for laziness and because it's
"cool" ^^
--
https://mail.python.org/mailman/listinfo/python-list

On 8/7/20 6:55 PM, Marco Sulla wrote:
> On Sat, 8 Aug 2020 at 00:28, Richard Damon <Richard@damon-family.org> wrote:
>> The really interesting part is that since Lisp programs manipulate lists
>> as data, and the program is just a list, Lisp programs have the
>> theoretical ability to edit themselves (assuming the implementation give
>> access to the list of the program to the program).
> This is a bit hard to understand for me.
> I know that code can be translated to an AST, that is a tree. It's
> quite difficult for me to imagine the code organized as a list. Do you
> have some links about it?

Lisp is built on Nested list, Lists were some (many) of the nodes are
other list. (Somewhat like you might build the AST in Python)

Generally the first element of the list defines what the list is, type
of statement or operation, and the rest are the parameters for it. Many
of these will be lists for sub expressions or dependent statements.

Perhaps the best option would be to search for the Lisp Language, and
see how you write programs.

>
> On Sat, 8 Aug 2020 at 00:28, Richard Damon <Richard@damon-family.org> wrote:
>> One advantage of blurring the line between statements and expressions is
>> power, putting assignments in the middle of an expression, can allow
>> code to be more compact.
> I agree with you. I experimented a little with CPython code and I saw
> assignments inside if statements. The code without them was less
> readable. I also found this example:
> https://stackoverflow.com/a/151920/1763602
> My only fear is the abuse. How many people really use the walrus
> operator to render the code more readable? My fear is that the
> majority of programmer will use it for laziness and because it's
> "cool" ^^

There is always the danger, that as you give the programmer more
expressive power, they can use it for 'good', or they can miss-use it to
make code harder to read. The question comes how much are you willing to
trust the programmer, or are you just going to give them enough rope so
that can do themselves in. 

--
Richard Damon

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

>> Readability of programming languages was measured
>> using an objective method, and Python was one of
>> the most readable.

Do you have a source for this?
--
https://mail.python.org/mailman/listinfo/python-list

On Sat, 8 Aug 2020 at 03:46, Christian Seberino <cseberino@gmail.com> wrote:
> >> Readability of programming languages was measured
> >> using an objective method, and Python was one of
> >> the most readable.
>
> Do you have a source for this?

This question means you have not read at all my suggestions :-D
Anyway, this is one: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3933420/

I do not agree with the entire work, but generally speaking it seems
to me they used a good approach. What really surprises me is the
absence of languages like JS and PHP.
--
https://mail.python.org/mailman/listinfo/python-list

Terry Reedy schreef op 7/08/2020 om 22:08:
> On 8/7/2020 11:46 AM, Chris Angelico wrote:
>
>> My point is that doing Fibonacci recursively is arguably more elegant
>> while being materially worse at performance.
>
> This is a common misconception. Linear iteration and tail recursion are
> equivalent. The issue is calculating values once versus multiple times.
> Here is the fast recursion equivalent to the fast iteration.
>
> def fib(n, pair=(1,0)):
> previous, current = pair
> if n:
> return fib(n-1, (current, previous + current))
> else:
> return current

Of course, but now you've lost the elegance of the recursive version
being near-literal translation of the mathematical definition.

It's a gripe I have with many introductory texts to functional
programming. Recursion is super cool, they say, it lets you decompose
problems in smaller problems in an elegant natural way. But then show
examples like Fibonacci where the elegant natural way is a bad solution,
so they introduce accumulators and stuff, and then Fibonacci does work
much better indeed. But they fail to notice that the new solution is not
elegant and natural at all anymore. It has just become iteration in a
recursive disguise.

I'm not saying there is nothing useful in functional programming and the
use of recursion; there most certainly is. But the way many texts
introduce it IMO doesn't help at all to understand the elegance that can
be achieved.

--
"Honest criticism is hard to take, particularly from a relative, a
friend, an acquaintance, or a stranger."
-- Franklin P. Jones

Roel Schroeven

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

On Tue, Aug 11, 2020 at 5:48 AM Roel Schroeven <roel@roelschroeven.net> wrote:
> I'm not saying there is nothing useful in functional programming and the
> use of recursion; there most certainly is. But the way many texts
> introduce it IMO doesn't help at all to understand the elegance that can
> be achieved.

Indeed. When I'm talking to students about recursion, often the
question "why bother" comes up... but when they finally 'get it', it's
usually because of an example far more elegant than Fibonacci numbers.
One of my favourites is: Given a binary tree, calculate its height.

def height(tree):
if not tree: return 0
return max(height(tree.left), height(tree.right)) + 1

THIS is the sort of thing that shows off the beauty of recursion.
Convoluted code with accumulator parameters just shows off that you
can write bad code in any style.

(Though the accumulator parameter form does have its place. Ever
written callback-based asynchronous code that needs to iterate over
something? Such fun.)

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

Christian Seberino wrote:
> A beginner I think could learn Lisp much faster than Python.

For talented beginners, Lisp rocks much like Python, in that easy assignments are easy enough to implement. On the high end, Lisp rocks again: Lisp masters are astonishingly productive. In between, beyond pedagogical exercises but short of our Turing Award masterwork, Lisp's extreme flexibility has a significant down-side in violating the middle third of Python Zen (PEP 20) guiding principle: "There should be one -- and preferably only one -- obvious way to do it."

Flexibility is good. In a programming language it's great, and Python is super flexible. Lisp is beyond. There are many Lisps, the big two of which are Common Lisp (CL) and Scheme. Common Lisp has been more industrially important, but Scheme out-Lisps CL. As we deal with Python's recent additions, such as "enum", the walrus operator, type hints, and async/await, I remain in awe of [call with current current continuation](https://en.wikipedia.org/wiki/Call-with-current-continuation), which in Scheme is abbreviated "call/cc".
--
https://mail.python.org/mailman/listinfo/python-list

Op 7/08/20 om 18:45 schreef Chris Angelico:
> On Sat, Aug 8, 2020 at 2:21 AM <2QdxY4RzWzUUiLuE@potatochowder.com> wrote:
>>
>> On 2020-08-07 at 17:55:45 +0200,
>> Marco Sulla <Marco.Sulla.Python@gmail.com> wrote:
>>> @Chris: note that "real" recursion in Python is not possible, since
>>> there's no support for tail recursion. Maybe something similar can be
>>> done using async functions.
>>
>> Python has real recursion. Whether or not there's tail recursion on the
>> inside is an implementation detail.
>
> More specifically: Python has real recursion. Whether or not tail
> recursion is optimized away is an implementation detail.
>
> Tail call optimization (there's no reason to restrict it to recursion
> alone) is something a Python implementation could choose to do, but
> the trouble is that full optimization tends to destroy traceback
> information, so it's often not worth doing.

I don't understand this argument. The trace back information that is
destroyed with this optimization, is information that isn't available
anyway if you write the code in an iterative fashion.

So people are advised to rewrite tail recursive code in an iterative
fashion, which results in less trace back information and the reason
for not doing tail call optimization is, that it destroy the trace back
information they don't have anyway by transforming the code to an iterative
version.

And the cases where
> partial optimization is of value just aren't compelling enough for
> anyone to implement it into CPython, nor any other major
> implementation (to my knowledge). The biggest uses for TCO tend to be
> the situations where recursion is the wrong solution to the problem.

I think writing code that is at heart a state machine would be a lot more
easy if python would have TCO. Then each state could be implemented by
a function and transitioning from one state to the next would be just
calling the next function.

Sure you can resolve this by writing your state function trampoline style
but it forces you into writing some boiler plate that otherwise wouldn't
be necessary.

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

On Sat, Aug 15, 2020 at 10:45 PM Antoon Pardon
<antoon.pardon@rece.vub.ac.be> wrote:
>
> Op 7/08/20 om 18:45 schreef Chris Angelico:
> > On Sat, Aug 8, 2020 at 2:21 AM <2QdxY4RzWzUUiLuE@potatochowder.com> wrote:
> >>
> >> On 2020-08-07 at 17:55:45 +0200,
> >> Marco Sulla <Marco.Sulla.Python@gmail.com> wrote:
> >>> @Chris: note that "real" recursion in Python is not possible, since
> >>> there's no support for tail recursion. Maybe something similar can be
> >>> done using async functions.
> >>
> >> Python has real recursion. Whether or not there's tail recursion on the
> >> inside is an implementation detail.
> >
> > More specifically: Python has real recursion. Whether or not tail
> > recursion is optimized away is an implementation detail.
> >
> > Tail call optimization (there's no reason to restrict it to recursion
> > alone) is something a Python implementation could choose to do, but
> > the trouble is that full optimization tends to destroy traceback
> > information, so it's often not worth doing.
>
> I don't understand this argument. The trace back information that is
> destroyed with this optimization, is information that isn't available
> anyway if you write the code in an iterative fashion.

Your counter-argument applies only to recursion, but TCO applies to
*any* tail call. Consider this:

@some_deco
def spam(n):
...
return spam(n // 2)

Not a recursive tail call and cannot be rewritten as a loop, unless
you know for sure that some_deco returns the original function. But
TCO can still optimize this - by collapsing the stack frames. Which
loses traceback info, unless you deliberately preserve it.

> And the cases where
> > partial optimization is of value just aren't compelling enough for
> > anyone to implement it into CPython, nor any other major
> > implementation (to my knowledge). The biggest uses for TCO tend to be
> > the situations where recursion is the wrong solution to the problem.
>
> I think writing code that is at heart a state machine would be a lot more
> easy if python would have TCO. Then each state could be implemented by
> a function and transitioning from one state to the next would be just
> calling the next function.

I'm honestly not sure how much you'd gain by writing the transitions
as additional calls. But then, I don't tend to write pure state
machines in Python. If anything, they're "state machines with
resumption" or something, and the additional wrinkles mean it's best
to maintain state in a data structure and maintain code in a function,
instead of trying to do both on the call stack.

ISTM that everyone who begs for tail recursion optimization is trying
to write loops as recursion. Maybe that's why Python has never
bothered - because it's an optimization for an inferior way to write
the same logic. Prove me wrong. Show me something where it actually
couldn't be better written iteratively, yet it still benefits from the
optimization.

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

@Chris: you're very right, but, I repeat, you can't have a real TCO
(asyncio apart):

(venv_3_10) marco@buzz:~$ python
Python 3.10.0a0 (heads/master-dirty:ba18c0b13b, Aug 14 2020, 17:52:45)
[GCC 10.1.1 20200718] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> def factorial(n):
... if n in (1, 2):
... return n
... return n * factorial(n-1)
...
>>> factorial(6)
720
>>> factorial(1000)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 4, in factorial
File "<stdin>", line 4, in factorial
File "<stdin>", line 4, in factorial
[Previous line repeated 995 more times]
File "<stdin>", line 2, in factorial
RecursionError: maximum recursion depth exceeded in comparison

Anyway, tail call is introduced in Python, but only for asyncio:

"If a Future.set_exception() is called but the Future object is never
awaited on, the exception would never be propagated to the user code.
Enable the debug mode to get the traceback where the task was created"
https://docs.python.org/3.10/library/asyncio-dev.html#detect-never-retrieved-exceptions

So, in theory, nothing prevents Python from having a Tail Call
Optimization... because it already has it! The only problem is that
it's applied to asyncio only. IMHO it's not a big problem to support
generic TCO, and disable it for debugging purposes enabling the Python
dev mode.
--
https://mail.python.org/mailman/listinfo/python-list

Op 15/08/20 om 15:02 schreef Chris Angelico:
> On Sat, Aug 15, 2020 at 10:45 PM Antoon Pardon
> <antoon.pardon@rece.vub.ac.be> wrote:
>>
>>
>> I don't understand this argument. The trace back information that is
>> destroyed with this optimization, is information that isn't available
>> anyway if you write the code in an iterative fashion.
>
> Your counter-argument applies only to recursion, but TCO applies to
> *any* tail call. Consider this:
>
> @some_deco
> def spam(n):
> ...
> return spam(n // 2)
>
> Not a recursive tail call and cannot be rewritten as a loop, unless
> you know for sure that some_deco returns the original function. But
> TCO can still optimize this - by collapsing the stack frames. Which
> loses traceback info, unless you deliberately preserve it.

And how often does this kind of situation come up and destroy important
trace back information? Sure you can come up with artificial examples
like the above, but if the above code gets into trouble because you
run into the recursion limit, you still will have to transform it into
a loop somehow.

>> I think writing code that is at heart a state machine would be a lot more
>> easy if python would have TCO. Then each state could be implemented by
>> a function and transitioning from one state to the next would be just
>> calling the next function.
>
> I'm honestly not sure how much you'd gain by writing the transitions
> as additional calls. But then, I don't tend to write pure state
> machines in Python. If anything, they're "state machines with
> resumption" or something, and the additional wrinkles mean it's best
> to maintain state in a data structure and maintain code in a function,
> instead of trying to do both on the call stack.

Why are you talking about a stack?

I don't know what best suits your code but my code often enough doesn't
have enough wrinkles to bother with extra data structures.

>
> ISTM that everyone who begs for tail recursion optimization is trying
> to write loops as recursion. Maybe that's why Python has never
> bothered - because it's an optimization for an inferior way to write
> the same logic. Prove me wrong. Show me something where it actually
> couldn't be better written iteratively, yet it still benefits from the
> optimization.

What standard do you use to measure what is inferior of superior? Sometimes
a state machines is easiest defined as a number of mutual recursive functions
that just tail call each other. So with TCO I could just write it like the
following.

def state1(...):
...
if ready_for_2:
return state2(...)
elif ready_for_7:
return state7(...)
elif finished:
return result

def state2(...):
...

and you just call it like:

result = state1(...)

Without TCO I am forced to write it as follow:

def state1(...):
...
if ready_for_2:
return state2, (...) # notice the comma between function and args.
elif ready_for_7:
return state7, (...)
elif finished:
return None, result

def state2(...):
...

and then call it like:

state = state0
args = ...
while state is not None:
state, args = state(*args)
result = args

I realy don't see what I gain by having this loop or what I could gain by some extra
data structure.

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

A few comments come to mind about this discussion about TCO.

First, TCO, Tail Call Optimization, is talking about something that is
an optimization.

Optimizations, are generally some OPTIONAL improvement in the method of
executing the code that doesn't alter its DEFINED meaning.

First big point, they are optional. Yes, some languages may define
certain circumstances where where there is a promise that a given
optimization will be done, but this is unusual. Some things that might
seem like optimizations, really aren't but are defined behaviors, like
the short cutting operators 'and' and 'or' where the fact that the
second operand isn't always evaluated could be though of as an optimization.

Second, optimizations are generally only allow to be performed if it
doesn't change any defined behavior of the program. I am not so sure
that is possible for TCO to be done in python based on that.

for example, given:

def foo(x):

    if x == 0: return 1

    else return foo(x-1)

def bar(x)

    if x == 0: return 2

    else return bar(x-1)

t = foo

foo = bar

bar = t

foo(1)


By the twiddling done at the end, we have changed the self
tail-recursive functions into mutually tail-recursive functions. The
fact we can do this says that when compiling foo and bar into byte-code,
the recursive call to foo can't just automatically go to the beginning
of the current function, but needs to look up the name and enter with a
possibly need operation, something like a tail-call which becomes more
of a jump as it doesn't create a new stack frame but somehow replaces
the current frame with what will be the new frame while binding the 'new
x' with the old 'x-1'

Second, because Python has defined things like traceback, the presence
of TCO is observable, and thus violates one of the basic guidelines of
an optimization, that it shouldn't change defined behavior.

In my mid, this says that for Python to proper support TCO, it may need
to do something to make it an explicit request, or at least defined
specifically when it will do it and when not.

Perhaps it could be defined that a return statement whose top level of
the expression is a function call, becomes an optimized tail call,
ALWAYS (at least with that version of Python), or maybe some sort of
flag needs to also be on the statement to avoid making it a backwards
breaking change.

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