Content deleted Content added
→Proposed control structures: Wording, loop and a half Tags: Mobile edit Mobile app edit Android app edit App section source |
|||
| (25 intermediate revisions by 8 users not shown) | |||
Line 10:
[[Interrupt]]s and [[Signal (computing)|signals]] are low-level mechanisms that can alter the flow of control in a way similar to a [[subroutine]], but usually occur as a response to some external stimulus or event (that can occur [[Asynchronous systems|asynchronously]]), rather than execution of an ''in-line'' control flow statement.
At the level of [[machine language]] or [[assembly language]], control flow instructions usually work by altering the [[program counter]]. For some [[central processing unit]]s (CPUs), the only control flow instructions available are conditional or unconditional [[Branch (computer science)|branch]] instructions, also termed jumps. However there is also [[Predication_(computer_architecture)|predication]] which conditionally enables or disables instructions ''without'' branching: as an alternative technique it can have both [[Predication_(computer_architecture)#Advantages|advantages]] and disadvantages over branching.
== Categories ==
Line 234:
== Loops ==
[[File:Programmingloops.svg|thumb|basic types of program loops]]
A loop is a sequence of statements which is specified once but which may be carried out several times in succession. The code "inside" the loop (the ''body'' of the loop, shown below as ''xxx'') is obeyed a specified number of times, or once for each of a collection of items (both cases of ''definite iteration''), or until some condition is met (''indefinite iteration''), or [[Infinite loop|infinitely]]. When one of those items is itself also a loop, it is called a "nested loop".<ref>{{Cite web |date=2019-11-25 |title=Nested Loops in C with Examples |url=https://www.geeksforgeeks.org/nested-loops-in-c-with-examples/ |access-date=2024-03-14 |website=GeeksforGeeks |language=en-US}}</ref><ref>{{Cite web |title=Python Nested Loops |url=https://www.w3schools.com/python/gloss_python_for_nested.asp |access-date=2024-03-14 |website=www.w3schools.com |language=en-US}}</ref><ref>{{Cite web |last=Dean |first=Jenna |date=2019-11-22 |title=Nested Loops |url=https://medium.com/swlh/nested-loops-ee1dbb9fc8ab |access-date=2024-03-14 |website=The Startup |language=en}}</ref>
Some common situations are not well-handled by these basic control structures, and are generally addressed by early exit from the loop, in the form of a ''break'' from the loop, a ''return'' from the function, or an exception being raised.<ref>{{cite journal
|last=Knuth |first=Donald E.
|author-link=Donald Knuth
|year=1974
|title=Structured Programming with <code>go to</code> Statements
|journal=[[ACM Computing Surveys|Computing Surveys]]
|volume=6
|issue=4
|pages=261–301
|doi=10.1145/356635.356640
|citeseerx=10.1.1.103.6084
|s2cid=207630080
}}</ref><ref name="roberts"/>
In [[functional programming]] languages, such as [[Haskell]] and [[Scheme (programming language)|Scheme]], both [[Recursion (computer science)|recursive]] and [[Fixed point combinator|iterative]] processes are expressed with [[Tail recursion|tail recursive]] procedures instead of looping constructs that are syntactic.
Line 243 ⟶ 258:
In most cases counting can go downwards instead of upwards and step sizes other than 1 can be used.
{|
| {{sxhl|2=basic|1=<nowiki/>
FOR I = 1 TO N
xxx
NEXT I}}
|
'''for''' I := 1 '''to''' N '''do''' '''begin'''
Line 253 ⟶ 268:
'''end''';
|-
| {{sxhl|2=fortran|1=<nowiki/>
DO I = 1,N
xxx
END DO}}
|
'''for''' ( I=1; I<=N; ++I ) {
Line 265 ⟶ 280:
In these examples, if N < 1 then the body of loop may execute once (with I having value 1) or not at all, depending on the programming language.
In many programming languages, only integers can be reliably used in a count-controlled loop. Floating-point numbers are represented imprecisely due to hardware constraints, so a loop such as
'''for''' X := 0.1 '''step''' 0.1 '''to''' 1.0 '''do'''
Line 311 ⟶ 327:
Several programming languages (e.g., [[Ada (programming language)|Ada]], [[APL (programming language)|APL]], [[D (programming language)|D]], [[C++11]], [[Smalltalk]], [[PHP]], [[Perl]], [[Object Pascal]], [[Java (programming language)|Java]], [[C Sharp (programming language)|C#]], [[MATLAB]], [[Visual Basic]], [[Ruby (programming language)|Ruby]], [[Python (programming language)|Python]], [[JavaScript]], [[Fortran 95]] and later) have special constructs which allow implicit looping through all elements of an array, or all members of a set or collection.
someCollection '''do''': {{codett|2=smalltalk|[:eachElement
'''for''' Item '''in''' Collection '''do''' '''begin''' xxx '''end''';
Line 319 ⟶ 335:
'''foreach''' someArray { xxx }
'''foreach''' {{codett|2=php|1=($someArray as $k => $v) { xxx } # PHP}}
Collection<String> coll; '''for''' (String s : coll) {}
Line 325 ⟶ 341:
'''foreach''' ('''string''' s '''in''' myStringCollection) { xxx }
{{codett|2=ps1|someCollection
'''forall''' ( index = first:last:step... )
[[Scala (programming language)|Scala]] has [[Scala (programming language)#For-expressions|for-expressions]], which generalise collection-controlled loops, and also support other uses, such as [[asynchronous programming]]. [[Haskell]] has do-expressions and comprehensions, which together provide similar function to for-expressions in Scala.
Line 349 ⟶ 366:
=== Restart loop ===
Ruby has a <code>retry</code> statement that restarts the entire loop from the initial iteration.<ref>{{cite web|title=control_expressions - Documentation for Ruby 2.3.0|url=https://docs.ruby-lang.org/en/2.3.0/syntax/control_expressions_rdoc.html|access-date=2020-09-25|website=docs.ruby-lang.org}}</ref>
=== Loop-and-a-half ===
Common loop structures sometimes result in duplicated code, either repeated statements or repeated conditions. This arises for various reasons and has various proposed solutions to eliminate or minimize code duplication.<ref name="c2messy">{{cite web |url=https://wiki.c2.com/?MessyLoopConditions |title=Messy Loop Conditions |work=WikiWikiWeb |date=2014-11-03}}</ref> Other than the traditional unstructured solution of a ''goto'' statement,{{sfn|Knuth|1974|p=278|loc=Simple Iterations}} general structured solutions include having a conditional (''if'' statement) inside the loop (possibly duplicating the condition but not the statements) or wrapping repeated logic in a function (so there is a duplicated function call, but the statements are not duplicated).<ref name="c2messy" />
A common case is where the start of the loop is always executed, but the end may be skipped on the last iteration.{{sfn|Knuth|1974|p=278|loc=Simple Iterations}} This was dubbed by Dijkstra a loop which is performed "''n'' and a half times",<ref>[[Edsger W. Dijkstra]], personal communication to [[Donald Knuth]] on 1974-01-03, cited in {{harvtxt|Knuth|1974|p=278|loc=Simple Iterations}}</ref> and is now called the '''''loop-and-a-half''' problem''.<ref name="roberts"/> Common cases include reading data in the first part, checking for end of data, and then processing the data in the second part; or processing, checking for end, and then preparing for the next iteration.{{sfn|Knuth|1974|p=278|loc=Simple Iterations}}<ref name="roberts"/> In these cases, the first part of the loop is executed {{tmath|n}} times, but the second part is only executed {{tmath|n - 1}} times.
This problem has been recognized at least since 1967 by Knuth, with Wirth suggesting solving it via early loop exit.{{sfn|Knuth|1974|p=279}} Since the 1990s this has been the most commonly taught solution, using a ''break'' statement, as in:<ref name="roberts"/>
'''loop'''
''statements''
'''if''' ''condition'' '''break'''
''statements''
'''repeat'''
A subtlety of this solution is that the condition is the ''opposite'' of a usual ''while'' condition: rewriting '''while''' ''condition'' ... '''repeat''' with an exit in the middle requires reversing the condition: '''loop''' ... '''if not''' ''condition'' '''exit''' ... '''repeat'''. The [[#Loop with test in the middle|loop with test in the middle]] control structure explicitly supports the loop-an-a-half use case, without reversing the condition.{{sfn|Knuth|1974|p=279}}
=== Early exit from loops ===
It is sometimes desirable to stop executing a loop before the end of the body; for example, when using a count-controlled loop to search through a table, one can stop as soon as the required item is found. Early exit is the most common way to solve the [[loop-and-a-half]] problem.<ref name="roberts"/>
Some programming languages provide a statement such as <code>break</code> (most languages), <code>Exit</code> (Visual Basic), or <code>last</code> (Perl), which effect is to terminate the current loop immediately, and transfer control to the statement immediately after that loop.
Other mechanisms for early exit include a <code>return</code> out of a subroutine executing the looped statements, breaking out of both the loop and the subroutine; and raising an exception. There are other [[#Proposed control structures|proposed control structures]], but they are not commonly implemented. This section treats early exit from only the loop ("break").
Most commonly, this is used by combining a conditional ('''if''' statement) with an unconditional break, as in Ada:
<syntaxhighlight lang="ada">
loop
Get(X);
if X = 0 then
exit;
end if;
-- Do something with X.
end loop;
</syntaxhighlight>
In this form, the condition is interpreted as '''until'''. Some languages, such as Ada, have syntax for a conditional break, here an '''exit when''' clause (not to be confused with the '''exitwhen''' statement in {{slink||Proposed control structures}}); if available, this is more idiomatic:
<syntaxhighlight lang="ada">
loop
exit
-- Do something with X.
end loop;
</syntaxhighlight>
This functions similarly to a [[#Loop with test in the middle|loop with test in the middle]], but in that case the test is part of the structure of the loop, dividing the body of the loop in half (visually indented at the same level as the start/end of loop), while early exit is unstructured: simply a statement that can appear anywhere in the body of the loop, and in fact multiple break statements are possible.
[[Python (programming language)|Python]] supports conditional execution of code depending on whether a loop was exited early (with a <code>break</code> statement) or not by using an else-clause with the loop. For example,
Line 384 ⟶ 429:
The <code>else</code> clause in the above example is linked to the <code>for</code> statement, and not the inner <code>if</code> statement. Both Python's <code>for</code> and <code>while</code> loops support such an else clause, which is executed only if early exit of the loop has not occurred.
==== Multi-level breaks ====
Some languages support breaking out of nested loops; in theory circles, these are called '''multi-level breaks'''. One common use example is searching a multi-dimensional table. This can be done either via multilevel breaks (break out of ''N'' levels), as in bash<ref>Advanced Bash Scripting Guide: [http://tldp.org/LDP/abs/html/loopcontrol.html 11.3. Loop Control]</ref> and PHP,<ref>PHP Manual: "[http://php.net/manual/en/control-structures.break.php break]"</ref> or via labeled breaks (break out and continue at given label), as in Ada. Go, Java and Perl.<ref>perldoc: [http://perldoc.perl.org/functions/last.html last]</ref> Alternatives to multilevel breaks include single breaks, together with a state variable which is tested to break out another level; exceptions, which are caught at the level being broken out to; placing the nested loops in a function and using return to effect termination of the entire nested loop; or using a label and a goto statement. C does not include a multilevel break, and the usual alternative is to use a goto to implement a labeled break.<ref>comp.lang.c FAQ list · "[http://c-faq.com/misc/multibreak.html Question 20.20b]"</ref> Python does not have a multilevel break or continue – this was proposed in [https://www.python.org/dev/peps/pep-3136/ PEP 3136], and rejected on the basis that the added complexity was not worth the rare legitimate use.<ref>[http://mail.python.org/pipermail/python-3000/2007-July/008663.html <nowiki>[</nowiki>Python-3000<nowiki>]</nowiki> Announcing PEP 3136], Guido van Rossum</ref>
The notion of multi-level breaks is of some interest in [[theoretical computer science]], because it gives rise to what is today called the ''Kosaraju hierarchy''.<ref name=kozen>{{cite book |first=Dexter |last=Kozen |date=2008 |chapter=The Böhm–Jacopini Theorem is False, Propositionally |title=Mathematics of Program Construction |series=Lecture Notes in Computer Science |doi=10.1007/978-3-540-70594-9_11 |volume=5133 |pages=177–192 |isbn=978-3-540-70593-2 |url=
Theory of Computing, (May 1973), 240-252; also in J. Computer and System Sciences, 9,
3 (December 1974), cited by {{harvtxt|Knuth|1974}}.</ref> Furthermore, Kosaraju proved that a strict hierarchy of programs exists: for every integer ''n'', there exists a program containing a multi-level break of depth ''n'' that cannot be rewritten as a program with multi-level breaks of depth less than ''n'' without introducing added variables.<ref name="kozen"/>
In his 2004 textbook, [[David Watt (computer scientist)|David Watt]] uses Tennent's notion of [[S-algol|sequencer]] to explain the similarity between multi-level breaks and return statements. Watt notes that a class of sequencers known as ''escape sequencers'', defined as "sequencer that terminates execution of a textually enclosing command or procedure", encompasses both breaks from loops (including multi-level breaks) and return statements. As commonly implemented, however, return sequencers may also carry a (return) value, whereas the break sequencer as implemented in contemporary languages usually cannot.<ref name="WattFindlay2004b">{{cite book|author1=David Anthony Watt|author2=William Findlay| title=Programming language design concepts| year=2004| publisher=John Wiley & Sons|isbn=978-0-470-85320-7|pages=215–221}}</ref>
=== Loop with test in the middle ===
The following structure was proposed by [[Ole-Johan Dahl|Dahl]] in 1972:<ref>Dahl & Dijkstra & Hoare, "Structured Programming" Academic Press, 1972.</ref>
'''loop''' '''loop'''
xxx1 read(char);
'''while''' test; '''while''' '''not''' atEndOfFile;
xxx2 write(char);
'''repeat'''; '''repeat''';
The construction here can be thought of as a '''do''' loop with the '''while''' check in the middle, which allows clear [[#Loop-and-a-half|loop-and-a-half]] logic. Further, by omitting individual components, this single construction can replace several constructions in most programming languages. If ''xxx1'' is omitted, we get a loop with the test at the top (a traditional '''while''' loop). If ''xxx2'' is omitted, we get a loop with the test at the bottom, equivalent to a '''do while''' loop in many languages. If '''while''' is omitted, we get an infinite loop. This construction also allows keeping the same polarity of the condition even when in the middle, unlike early exit, which requires reversing the polarity (adding a '''not'''),{{sfn|Knuth|1974|p=279}} functioning as '''until''' instead of '''while'''.
This structure is not widely supported, with most languages instead using '''if''' ... '''break''' for conditional early exit.
This is supported by some languages, such as [[Forth (programming language)|Forth]], where the syntax is BEGIN ... WHILE ... REPEAT,<ref>{{Cite web|url=https://www.forth.com/starting-forth/6-forth-do-loops/|title=6. Throw It For a Loop}}</ref> and the [[shell script]] languages [[Bourne shell]] (<code>sh</code>) and [[Bash (Unix shell)|bash]], where the syntax is '''while''' ... '''do''' ... '''done''' or '''until''' ... '''do''' ... '''done''', as:<ref>{{citation |url=https://www.gnu.org/software/bash/manual/bash.html |title=The GNU Bash Reference Manual |section=3.2.5.1 Looping Constructs |section-url=https://www.gnu.org/software/bash/manual/bash.html#Looping-Constructs-1 |date=2025-05-18}}</ref><ref>{{cite web |url=https://langdev.stackexchange.com/questions/1815/how-could-a-language-make-the-loop-and-a-half-less-error-prone/1868#1868 |title=How could a language make the loop-and-a-half less error-prone? |work=Stack Exchange: Programming Language Design and Implementation}}</ref>
<syntaxhighlight lang="bash">
while
statement-1
statement-2
...
condition
do
statement-a
statement-b
...
done
</syntaxhighlight>
The shell syntax works because the '''while''' (or '''until''') loop accepts a list of commands as a condition,<ref>{{citation |url=https://www.gnu.org/software/bash/manual/bash.html |title=The GNU Bash Reference Manual |section=3.2.4 Lists of Commands |section-url=https://www.gnu.org/software/bash/manual/bash.html#Lists |date=2025-05-18}}</ref> formally:
'''while''' ''test-commands''; '''do''' ''consequent-commands''; '''done'''
The value (exit status) of the list of ''test-commands'' is the value of the ''last'' command, and these can be separated by newlines, resulting in the idiomatic form above.
Similar constructions are possible in C and C++ with the [[comma operator]], and [[Comma_operator#Other_languages|other languages with similar constructs]], which allow shoehorning a list of statements into the while condition:
<syntaxhighlight lang="c">
while (
statement_1,
statement_2,
condition
) {
statement_a;
statement_b;
}
</syntaxhighlight>
While legal, this is marginal, and it is primarily used, if at all, only for short modify-then-test cases, as in:<ref>{{cite web |url=https://stackoverflow.com/questions/52550/what-does-the-comma-operator-do/52615#52615 |title=What does the comma operator , do? |work=[[Stack Overflow]]}}</ref>
<syntaxhighlight lang="c">
while (read_string(s), strlen(s) > 0) {
// ...
}
</syntaxhighlight>
=== Loop variants and invariants ===
Line 852 ⟶ 939:
# {{note_label|while|7|a}} There is no special construct, since the <code>while</code> function can be used for this.
# {{note_label|user|8|a}} There is no special construct, but users can define general loop functions.
# {{note_label|loop_foreach|9|a}} The [[C++11]] standard introduced the [[C++11#Range-based for loop|range-based for]]. In the [[Standard Template Library|STL]], there is a <code>std::for_each</code> [[template (programming)|template]] function which can iterate on STL [[Container (data structure)|containers]] and call a [[unary function]] for each element.<ref>[http://www.sgi.com/tech/stl/for_each.html for_each]. Sgi.com. Retrieved on 2010-11-09.</ref> The functionality also can be constructed as [[C preprocessor#Macro definition and expansion|macro]] on these containers.<ref>[
# {{note_label|count_loop_eiffel|10|a}} Count-controlled looping is effected by iteration across an integer interval; early exit by including an additional condition for exit.
# {{note_label|retry_in_eiffel|11|a}} Eiffel supports a reserved word <code>retry</code>, however it is used in [[Exception handling#Exception handling based on design by contract|exception handling]], not loop control.
# {{note_label|requires_JML|12|a}} Requires [[Java Modeling Language]] (JML) behavioral interface specification language.
# {{note_label|integer_variant|13|a}} Requires loop variants to be integers; transfinite variants are not supported. [http://archive.eiffel.com/doc/faq/variant.html Eiffel: Why loop variants are integers]
# {{note_label|DInfinite|13|a}} D supports infinite collections, and the ability to iterate over those collections. This does not require any special construct.
# {{note_label|cobol_deep_exit|14|a}} Deep breaks can be achieved using <code>GO TO</code> and procedures.
Line 1,075 ⟶ 1,162:
| {{yes}}
| {{yes}}
| {{yes}}<ref>{{
|-
| [[Rebol]]
Line 1,092 ⟶ 1,179:
| {{no}}
| {{yes}}
| {{yes|experimental}} <ref>{{
| {{yes}}<ref>{{
|-
| [[Scala (programming language)|Scala]]
Line 1,121 ⟶ 1,208:
== Proposed control structures ==
=== COMEFROM ===
{{main|COMEFROM}}
In a spoof [[Datamation]] article<ref>[http://www.fortran.com/fortran/come_from.html We don't know where to GOTO if we don't know where we've COME FROM. This (spoof) linguistic innovation lives up to all expectations.] {{Webarchive|url=https://web.archive.org/web/20180716171336/http://www.fortran.com/fortran/come_from.html |date=2018-07-16 }} By R. Lawrence Clark* From Datamation, December, 1973</ref> in 1973, R. Lawrence Clark suggested that the GOTO statement could be replaced by the [[COMEFROM]] statement, and provides some entertaining examples. COMEFROM was implemented in one [[esoteric programming language]] named [[INTERCAL]].
=== Event-based early exit from nested loops ===
[[Zahn's construct|This construct]] was proposed by [[Zahn's construct|Zahn]] in 1974,<ref>Zahn, C. T. "A control statement for natural top-down structured programming" presented at Symposium on Programming Languages, Paris, 1974.</ref> and discussed in {{harvtxt|Knuth|1974}}. A modified version is presented here.
'''exitwhen''' EventA '''or''' EventB '''or''' EventC;
xxx
Line 1,211 ⟶ 1,256:
* [[Jeroo]], helps learn control structures
* [[Main loop]]
* [[Predication_(computer_architecture)|predication]]
* [[Recursion]]
* [[Scheduling (computing)]]
| |||
