Friday Finking: Contorted loops

[dn]

Why does Python not have a repeat-until loop construct?
(or should that be 'modern programming languages'?)

This is a perennial question (one contributor calling it "immemorial"),
but there seem to be reasons why the Python Interpreter would find such
a construct awkward, or is otherwise unable to comply. If so, what does
one need to understand, in order to comprehend the (apparent) omission?

NB I'm not asking 'how to do this with while?'.


TLDR;
- wherein the historical background is explored, a possible 'gap in
knowledge' exposed, alternative implementations discussed, PEP-proposals
critiqued, and related-questions (re-)asked at the end...


If the question itself doesn't appeal to you, perhaps some of the
discussion and web.refs (below) will. Happy Friday. Happy thinking!


The term "Structured Programming" was coined by Edsger W Dijkstra. It
proposed a number of "control structures" (which were largely
unavailable in the programming languages of that time):

- sequence: a series of statements/routines to be executed in sequence
- selection: if...then, if...then...else..., case
- iteration: while, repeat (do...until), for
- recursion: a routine 'calling itself' as a cascade

The 'content' or 'process' of each structure was a block (or in Python
terminology: a "suite") consisting of any/all of the above (thus
"nesting"). Python's indentation practice, today likely descended from
this concept.


Much of the development of the ideas behind Structured Programming that
followed the crystallisation of this list of constructs, were attempts
to mathematically (logically) 'prove' code as "correct".

One of the ideas to (help?) make things more prove-able, was that each
block and construct have only one way in (entry), and one way out
(exit), eg (from Wikipedia) "The conditional statement should have at
least one true condition and each condition should have one exit point
at max ... Often it is recommended that each loop should only have one
entry point (and in the original structural programming, also only one
exit point, and a few languages enforce this)" which as they say, was an
idea later dropped/felt to be somewhat impracticable (but to which theme
I shall return...)

Even in fairly modest Python constructs, we quickly repeal the one-in,
one-out philosophy because try...except operates by providing another
exit-path.


The 'structures' (or "constructs") of Structured Programming were
fore-runners of the Software Patterns and SOLID Principles
commonly-practised today. These ideas still hold the same goal of
trading a degree of abstraction for programming simplicity, possibly
testability, and improved quality.

Today, Python offers almost all of the SP constructs. A form of
case/select is expected in v3.10. The continuing omission is repeat-until.


If you have not met such a code-component before, the idea of a
repeat...until (or do...until) might look like this:

    repeat:
        code-suite
        until condition

Thus, the code-suite will be executed as many times as necessary, until
the condition is met.


In Python, we are used to while-loops, which can be expressed in the
same style as:

    while condition:
        code-suite

What's the difference?

The answer is that the repeat's code-block MUST be executed at least
once. Whereas a while's code-suite could be totally ignored and not
executed at all!

An analogy is to RegEx and its * and + repetitions:

* means zero, one, or more matches
+ means (at least) one, or more matches


During the last weeks 'here', writing a while-loop was a topic of
conversation. A solution offered to the OP, can be described as:

    loop-init-code
    while True:        #in other words, loop forever
        code-suite
        if condition:
            break

Note three things:

1 the while condition has been bastardised - there is no meaningful
condition, it is designed to loop without thought or control*

2 the control condition within and ending the loop's suite exactly
replaces the until-condition of a repeat-until construct

3 the cyclomatic-complexity of the multi-faceted construct is much
higher than of a 'pure' while-loop (or for-loop)

NB "cyclomatic complexity" is an attempt to measure a program's
complexity based on the number of distinct paths or branches in the code
(please recall earlier comment about 'entry and exit').

* in one of the web.ref discussions, our own @Chris suggests taking
advantage of the 'truthiness' of data, and inserting some documentation:

    while 'there is data to process':

Which is a considerable improvement over the bland 'loop forever' or
'loop until I tell you otherwise, according to criteria I won't reveal
until later' (an operating mode every?no teenager would accept,
on-principle! - including this one...)


This form is a regularly recommended as a 'solution' (see first Answer
to SO question). However, it is likely to require some set-up (which is
technically preceding, and therefore outside of the construct, yet the
construct is highly-dependent upon it. (this may be unavoidable, regardless)

Most importantly (regretfully), another construct has been added at the
(middle or) end of the loop to perform work which has been displaced
from the while-condition.

So, whereas a repeat...until is a single construct encapsulating its
code-suite, the while+True...if+condition-break, forms two constructs
'around' the code-suite - and in some circumstances the code-suite may
be effectively split into two by the positioning of the added if+condition.

None of this is calculated to lead to 'the simple life' and soothe minds
into the Zen of Python!


Whereas most of this discussion is at the theoretical level, I have
spent several 'happy hours' hacking-away in the hope of finding a
practical solution to, or work-around for, this issue. Mostly
disappearing down the ast-and-exec rabbit-hole.

In a sub-set of possible-solutions "the time has come [for] the walrus
[operator]" ('improving' a line from a Lewis Carroll poem).

However, most solutions will require some retention of 'state'.
Accordingly, generators - which will also work in simpler cases.

They in-turn led me all the way to a class. I'm still playing with that
progression...

Sadly, am of the feeling that the 'cure' may be (as much criticised and)
more painful than 'the disease'...


Returning to an earlier point: for the 'pure' while-loop there is
exactly one way 'in' (entry), and one way 'out' (exit). The above,
loop-forever idea complicates matters, because when reading the code,
one's first understanding is that the while will control the indented
code-suite beneath - be its (single) exit. However, further reading
reveals that there is a second way 'out'. I should say, "theoretically",
because while True offers no escape - that implies it is no "exit" (the
"Hotel California" clause). So, reading the "while" creates an
expectation, but that must be immediately discarded when our eyes reach
the True-condition!


In the military, we were taught to always have a (current and
applicable) Escape Plan. If you've travelled by airplane/aeroplane you
will remember the crew giving a Safety Drill, and asking you to be aware
of your nearest exit should it be necessary to rapidly depart the plane
- and that "the closest may be behind you". These plans have virtue,
because in the chaos of an emergency, the time it takes to work-it-out
on-the-fly (hah!) may cost your life (no joke!).

To be sure, the extra time and effort required to read a bastardised
Python while-loop is hardly likely to be a matter of life or death (I
sincerely hope!), but it is grounds for complaint or 'muttering'.

When introducing trainees to recursion, I repeat over-and-over (and
-over) that the very first thing to do, is to code the termination
condition (the Escape Plan)! If you've ever coded recursive constructs,
you've almost certainly seen someone who hasn't followed this (simple)
plan - in your bath-room mirror...

The same principle applies to any while+True construct. Left alone, it
will not stop. In this situation, having to prepare by thinking about an
escape-route is a fundamental flaw. When you start coding the loop, your
mind is more interested in the code-suite - the business of the loop!
Once that is coded we will (in the normal course) be ready to
think-about 'what happens next'.

Sure, if one forgets the termination-clause, Python will save your life
- and it is likely that no-one else will notice. Does that make it
'right'? Doesn't it indicate that there's a 'smell' of something wrong?

In programming, consideration of "cognitive load" very much applies. We
are unlikely to ever need to escape from a smoke-filled development
environment, but we do have (more than) enough to think-about when
coding. Indeed the essential virtue of Structured Programming, SOLID,
software patterns, etc, is to reduce cognitive load by offering
tried-and-tested solutions, templates/abstractions, re-usable code, etc.


Am I the first to query the omission of repeat-until? No - not by a
long-shot! Raymond Hettinger and Isaac Carroll proposed PEP 315 back in
2003. The BDFL said: «Please reject the PEP. More variations along these
lines won't make the language more elegant or easier to learn. They'd
just save a few hasty folks some typing while making others who have to
read/maintain their code wonder what it means.» It was rejected.

Reading it now, the proposed syntax seems more than a little clumsy; but
makes me wonder why a more 'usual' repeat-until format wasn't, or
perhaps couldn't, be used (see Parser question).


@Raymond had (at least one) another 'go' in 2009. His comments included:
«The challenge has been finding a syntax that fits well with the
patterns in the rest of the language. It seems that every approach has
it's own strengths and weaknesses...These seem syntactically weird to me
and feel more like typos than real python code. I'm sure there are many
ways to spell the last line, but in the two years since I first worked
on the PEP, I haven't found any condition-at-the-end syntax that
FeelsRight(tm).»

Curiously, the last approach illustrated therein was to open the loop
with do: and terminate it with while+condition. I'd certainly concur
that the idea of using "while" at the 'head' of a while-loop and also at
the 'foot' of a repeat-until construct, seems "weird" (also (Tm)?). Am
not sure, perhaps didn't research far-enough, to see why another
construct-name, eg "until" was not considered. Can you point-out where
that is discussed, or give a reason 'why'?


As recently as 2017, David Murray addressed this issue with PEP 548
"More Flexible Loop Control". Again, with all the benefits conferred by
hind-sight, the idea seems clumsy: replacing the if+condition-break with
break-if+condition (in similar fashion to ternary conditional operators,
list-comprehensions, etc). It comes across as syntactic-sugar. It does
not address the 'bastardisation' and extra-construct's
cyclomatic-complexity rise.

Many points raised 'here' appear in another post at about that time (see
web.refs FYI).


In many cases, another common recommendation follows the lines of:

    do-something
    while the-something-is-ok:
        do-more
        do-something

This deserves criticism due to its code-repetition and thus
contravention of the DRY principle (Do not Repeat Yourself) - the
cyclomatic-complexity of the 'bastardisation' has been removed, but I'm
still discomforted. Are you?

As mentioned earlier, a major criticism is that something that is only
being done to establish the looping mechanism (is "closely-coupled") is
separate from, not (initially at least) an integral-part of the
construct. That said, please recall earlier allowance, that some
'initialisation' may be necessary.


Perhaps I missed it as life unfolded: has there been a paper/line of
research which discounted the need for repeat-until, assuming a while
construct was available?

Is a repeat-until construct missing from other
modern-languages, or is that a particular choice made in Python's design?


A paper from Duke (University) makes reference to a "Loop and a Half"
structure, with the particular example of completing an action until
some "sentinel-value" is reached. They presage my comments (below) about
"priming" the loop, the "sentinel" text as an additional construct,
and/or duplicate code - and how all that adds-up to making "the loop
body harder to understand since it turns a read-and-process loop into a
process-and-read loop." With sundry further admissions, they rewrite
into the bastardised form which has become Python's accepted-solution.


Perhaps it was not possible before, but will it become feasible under
Python's new (v3.9+) PEG parser?



Web.Refs:
https://en.wikipedia.org/wiki/Structured_programming
Dijkstra "Notes on Structured Programming"
https://dl.acm.org/doi/pdf/10.5555/1243380
Single-Entry, Single-Exit
https://web.archive.org/web/20121114195652/http://msmvps.com/blogs/peterritchie/archive/2008/03/07/single-entry-single-exit-should-it-still-be-applicable-in-object-oriented-languages.aspx
https://en.wikipedia.org/wiki/Cyclomatic_complexity
Ned Batchelder's McCabe plug-in https://pypi.org/project/mccabe/
The Walrus and the Carpenter by Lewis Carroll
https://poets.org/poem/walrus-and-carpenter
Python's Parser https://www.python.org/dev/peps/pep-0617/
PEP 315 https://www.python.org/dev/peps/pep-0315/
BDFL Rejection
https://mail.python.org/pipermail/python-ideas/2013-June/021610.html
Later discussion
https://mail.python.org/pipermail/python-ideas/2009-April/004306.html
and
https://mail.python.org/archives/list/python-ideas@python.org/thread/2VUZ3J6C4GSHGBZJW62AY4HPEEBMXAT6/#2VUZ3J6C4GSHGBZJW62AY4HPEEBMXAT6
PEP 548 https://www.python.org/dev/peps/pep-0548/
BDFL Rejection
https://mail.python.org/pipermail/python-dev/2017-September/149232.html
Python-Ideas post
https://mail.python.org/archives/list/python-ideas@python.org/thread/EDNARFL2RGOE53SLWPTD5ZLJQOYSVDCR/#EDNARFL2RGOE53SLWPTD5ZLJQOYSVDCR
Duke Paper
https://users.cs.duke.edu/~ola/patterns/plopd/loops.html#loop-and-a-half
RegEx in Python https://docs.python.org/3/library/re.html
and https://docs.python.org/3/howto/regex.html
"bastardise" (meaning 1) https://www.dictionary.com/browse/bastardize
https://stackoverflow.com/questions/743164/how-to-emulate-a-do-while-loop
DRY
https://code.tutsplus.com/tutorials/3-key-software-principles-you-must-understand--net-25161

-- 
Regards,
=dn