Mailing List Archive

On 11/7/23 18:26, Julieta Shem via Python-list wrote:
> For the first time I'm trying to write a tail-recursive
> square-and-multiply and, even though it /seems/ to work, I'm not happy
> with what I wrote and I don't seem to understand it so well.
>
> --8<---------------cut here---------------start------------->8---
> def sam(b, e, m, acc = 1):
> if e == 0:
> return acc
> if is_even(e):
> return sam(remainder(b * b, m), e//2, m, acc)
> else:
> return sam(b, e - 1, m, remainder(b * acc, m))
> --8<---------------cut here---------------end--------------->8---

I don't see any definition of "remainder()" When you post to the list,
please provide short but complete code, including a demonstration of
using the code provided. That will help others understand what you are
trying to do, and perhaps comment on your concerns.

> You see, I tried to use an accumulator, but I'm only accumulating when
> the exponent is odd. When it's even, I feel I'm forced to change the
> base into b * b mod m and leave the accumulator alone. This feels so
> unnatural to me. I feel I broke some symmetry there. I'm having to
> think of two cases --- when I change the accumulator and when I change
> the base. That seems too much for my small head. Can you help?

I don't really understand the code either, so I cannot help much.

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

On 8/11/23 2:26 pm, Julieta Shem wrote:
> For the first time I'm trying to write a tail-recursive
> square-and-multiply and, even though it /seems/ to work, I'm not happy
> with what I wrote and I don't seem to understand it so well.

Stepping back a bit, why do you feel the need to write this
tail-recursively? Is it just an exercise?

Note that Python doesn't optimise tail calls, so anything that
can be done tail-recursively is probably better done iteratively.

>
> --8<---------------cut here---------------start------------->8---
> def sam(b, e, m, acc = 1):
> if e == 0:
> return acc
> if is_even(e):
> return sam(remainder(b * b, m), e//2, m, acc)
> else:
> return sam(b, e - 1, m, remainder(b * acc, m))
> --8<---------------cut here---------------end--------------->8---
>
> You see, I tried to use an accumulator, but I'm only accumulating when
> the exponent is odd. When it's even, I feel I'm forced to change the
> base into b * b mod m and leave the accumulator alone. This feels so
> unnatural to me. I feel I broke some symmetry there. I'm having to
> think of two cases --- when I change the accumulator and when I change
> the base. That seems too much for my small head. Can you help?

Well, there are inherently two cases, and they're different, so
I don't think you're doing anything wrong here. It was asymmetrical
to begin with. If you were doing it iteratively you would also be
leaving the accumulator alone when the exponent is even.

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

Greg Ewing <greg.ewing@canterbury.ac.nz> writes:

> On 8/11/23 2:26 pm, Julieta Shem wrote:
>> For the first time I'm trying to write a tail-recursive
>> square-and-multiply and, even though it /seems/ to work, I'm not happy
>> with what I wrote and I don't seem to understand it so well.
>
> Stepping back a bit, why do you feel the need to write this
> tail-recursively? Is it just an exercise?

Yes --- an exercise. (It would be relevant if I were in a language that
gives me tail-call optimization. I'm preparing myself for when that
happens.)

> Note that Python doesn't optimise tail calls, so anything that
> can be done tail-recursively is probably better done iteratively.

I agree. By the way, I once read or watched an interview with Guido van
Rossum and and he was asked why not to tail-call optimize Python and the
answer he gave --- IIRC --- was that tail-call optimization makes it
harder for a beginner to understand a stack trace. I'm now interested
in discovering whether that was his sole reason. Do you (or does
anyone) know of any reference that I could look into? Thank you.

>> --8<---------------cut here---------------start------------->8---
>> def sam(b, e, m, acc = 1):
>> if e == 0:
>> return acc
>> if is_even(e):
>> return sam(remainder(b * b, m), e//2, m, acc)
>> else:
>> return sam(b, e - 1, m, remainder(b * acc, m))
>> --8<---------------cut here---------------end--------------->8---
>> You see, I tried to use an accumulator, but I'm only accumulating
>> when
>> the exponent is odd. When it's even, I feel I'm forced to change the
>> base into b * b mod m and leave the accumulator alone. This feels so
>> unnatural to me. I feel I broke some symmetry there. I'm having to
>> think of two cases --- when I change the accumulator and when I change
>> the base. That seems too much for my small head. Can you help?
>
> Well, there are inherently two cases, and they're different, so
> I don't think you're doing anything wrong here. It was asymmetrical
> to begin with. If you were doing it iteratively you would also be
> leaving the accumulator alone when the exponent is even.

I think you're quite right and that was not clear until now. Here's my
iterative version of the procedure:

--8<---------------cut here---------------start------------->8---
def isam(b, e, m):
r = 1
while e > 0:
if is_even(e):
b = remainder(b * b, m)
e = e // 2
else:
r = remainder(r * b, m)
e = e - 1
return remainder(r, m)
--8<---------------cut here---------------end--------------->8---

So, indeed, it is asymmetric. When it's even, I change the base. When
it's odd, I change the /r/eturning value. Thank you so much.

(*) The remainder function

--8<---------------cut here---------------start------------->8---
def is_even(n):
return remainder(n, 2) == 0

def remainder(a, b):
return a % b
--8<---------------cut here---------------end--------------->8---
--
https://mail.python.org/mailman/listinfo/python-list

Julieta Shem <jshem@yaxenu.org> writes:

[...]

> I agree. By the way, I once read or watched an interview with Guido van
> Rossum and and he was asked why not to tail-call optimize Python and the
> answer he gave --- IIRC --- was that tail-call optimization makes it
> harder for a beginner to understand a stack trace. I'm now interested
> in discovering whether that was his sole reason. Do you (or does
> anyone) know of any reference that I could look into? Thank you.

It seems everyone refers Guido van Rossum's post at

https://neopythonic.blogspot.com/2009/04/final-words-on-tail-calls.html

From the page, confuse-users is /not/ the only reason. After mentioning
it first, he begins a second paragraph saying ``[t]he main issue here
[...]'' and I wonder if by ``main issue'' he means something like ---
the main /problem/ with tail-call optimization (for me) is [...].

--8<---------------cut here---------------start------------->8---
Personally, I think it is a fine feature for some languages, but I
don't think it fits Python: The elimination of stack traces for some
calls but not others would certainly confuse many users, who have not
been raised with tail call religion but might have learned about call
semantics by tracing through a few calls in a debugger.

The main issue here is that I expect that in many cases tail calls are
not of a recursive nature (neither direct nor indirect), so the
elimination of stack frames doesn't do anything for the algorithmic
complexity of the code, but it does make debugging harder. For
example, if your have a function ending in something like this:

if x > y:
return some_call(z)
else:
return 42

and you end up in the debugger inside some_call() whereas you expected
to have taken the other branch, with TCO as a feature your debugger
can't tell you the value of x and y, because the stack frame has been
eliminated.
--8<---------------cut here---------------end--------------->8---
--
https://mail.python.org/mailman/listinfo/python-list