Control flow |
In computer science and in computer programming, statements in Pseudocode or in a computer program are normally obeyed (or executed ) one after the other in the order in which they are written (sequential flow of control). Most programming languages have control flow statements which allow variations in this sequential order:
The use of Subroutines does not normally cause any control flow problems, but see the discussions below on early return, error recovery, and labels as parameters.
At the Machine language/assembly language level, it is usually the case that the only instructions available for handling choice and/or loops are goto and conditional goto (often known as variations of jump and/or branch ). Compilers for high-level programming languages must translate all control-flow statements into these primitives.
= Primitives =
== Labels ==
In a few programming languages (e.g. Fortran, BASIC programming language), a label is just a whole number which appears at the beginning of a statement, e.g. 1234 X = 3
In many programming languages, a label is an identifier, which is attached to a statement by using a colon (:), e.g. Success:print( target has been found )
Historical note: Algol 60 allowed both whole numbers and identifiers as labels (both attached by colons to statements), but few if any implementations allowed whole numbers.
== Goto ==
The most common form for the unconditional transfer of control is just goto label Conditional transfer of control varies from language to language, e.g. IF test THEN label IF (test) GOTO label if test then goto label; if (test) goto label;
For a fuller discussion on the drawbacks of goto, see Goto.
In brief, undisciplined use of goto leads to below).
A number of authors have pointed out that using goto is often acceptable, provided that control is transferred to some later statement (forward jump) and that control is not transferred into the middle of some other structured statement.
Some of the control-flow statements available in high-level programming languages are effectively disguised gotos which comply with these conditions, e.g. break, continue, return as found in C/C++.
== Subroutines ==
The terminology for Subroutines varies; they may alternatively be known as routines, procedures, or sometimes methods. If they can be used in an expression and return a result, they may also be known as functions.
In the 1950 s, computer memories were very small by current standards so subroutines were used primarily to reduce program size; a piece of code was written once and then used many times from various other places in the program. Nowadays, subroutines are more frequently used to help make a program more structured, e.g. by isolating some particular algorithm or hiding some particular data access method. If many programmers are working on a single program, subroutines can be used to help split up the work.
Subroutines can be made much more useful by providing them with parameters, e.g. many programming languages have a built-in square root subroutine whose parameter is the number you wish to find the square root of.
Some programming languages allow Recursion, i.e. subroutines can call themselves directly or indirectly. Certain algorithms such as Quicksort and various tree-traversals are very much easier to express in recursive form than in non-recursive form.
The use of subroutines does slow a program down slightly, due to the overhead of passing parameters, calling the subroutine, entering the subroutine (may involve saving information on a stack), and returning. The actual overhead depends on both the hardware instructions available and on any software conventions which are used; excluding parameters, the overhead may range from 2 to 14 instructions, or worse. Some compilers may effectively insert the code of a subroutine inline expansion at the point of call to remove this overhead.
In some programming languages, the only way of returning from a subroutine is by reaching the physical end of the subroutine. Other languages have a return statement. This is equivalent to a forward jump to the physical end of the subroutine and so does not complicate the control flow situation. There may be several such statements within a subroutine if required.
In most cases, a call to a subroutine is only a temporary diversion to the sequential flow of control, and so causes no problems for control flow analysis. A few languages allow labels to be passed as parameters, in which case understanding the control flow becomes very much more complicated, since you may then need to understand the subroutine to figure out what might happen.
Here is an example illustrating the use of a subroutine which returns a value, written side-by-side in BASIC_programming_language and in PHP (a language similar to C).
BASIC PHP 10 X = 2 | $x = 2; 20 Y = DOUBLE(X) | $y = double($x); 30 PRINT Y | echo $y; | FUNCTION DOUBLE(NUM) | function double($num) { NUM = NUM * 2 | $num *= 2; RETURN NUM | return $num; | }
At execution time, the program defines a variable X and gives it a value of 2. In the next line, the program jumps down to the subroutine named DOUBLE, copying the value of X to a temporary variable called NUM (this is known as passing a variable). The instructions in the subroutine are then carried out (i.e. NUM is multiplied by 2), and the resulting value is returned to the point in the main program where the subroutine was called. Here another variable Y is set to that value (4) and, on the next line, output to the screen. The program will end execution after the third line without continuing into the function.
= Minimal structured control flow =
In May 1966, Böhm and Jacopini published an article in Communications of the ACM which showed that any program with gotos could be transformed into a goto-free form involving only choice (IF THEN ELSE) and loops (WHILE condition DO xxx), possibly with duplicated code and/or the addition of Boolean variables (true/false flags). Later authors have shown that choice can be replaced by loops (and yet more Boolean variables).
The fact that such minimalism is possible does not necessarily mean that it is desirable; after all, computers theoretically only need one machine instruction (subtract one number from another and branch if the result is negative), but practical computers have dozens or even hundreds of machine instructions.
What Böhm and Jacopini s article showed was that all programs could be goto-free. Other research showed that control structures with one entry and one exit were much easier to understand than any other form, primarily because they could be used anywhere as a statement without disrupting the control flow.
= Control structures in practice =
Most programming languages with control structures have an initial keyword which indicates the type of control structure involved (Smalltalk is an exception). Languages then divide as to whether or not control structures have a final keyword.
Languages which have a final keyword tend to have less debate regarding layout and indentation ( ). Languages whose final keyword is of the form: end + initial keyword (with or without space in the middle) tend to be easier to learn and read.
= Choice =
== Choice using arbitrary tests ==
These are usually known as if statements. Note that if the language has an endif, then it usually has elseif as well, in order to avoid a large number of endifs for multiple tests.
if test then statementTrue else statementFalse;
if (test) statementTrue else statementFalse;
if (test1) statementTrue1 else if (test2) statement2True else if (test3) statement3True else statementAllFalse;
IF (test1) THEN xxx1True ELSEIF (test2) THEN xxx2True ELSEIF (test3) THEN xxx3True ELSE xxxAllFalse ENDIF
== Choice based on specific constant values ==
These are usually known as case or switch statements. The effect is to compare a given value with specified constants and take action according to the first constant to match. If the constants form a compact range then this can be implemented very efficiently as if it were a choice based on whole numbers. This is often done by using a jump table. case someChar of switch (someChar) { a : actionOnA; case a : actionOnA; x : actionOnX; break; y , z :actionOnYandZ; case x : actionOnX; end; break; case y : case z : actionOnYandZ; break; default: actionOnNoMatch; }
In some languages and programming environments, a case or switch statement is considered easier to read and maintain than an equivalent series of if-else statements. One notable aspect of the switch statement is that of fall-through , especially as used in the C programming language.
Duff s device is a loop unwinding technique that makes use of a switch statement.
== Choice based on whole numbers 1..N ==
Relatively few programming languages have these constructions but it can be implemented very efficiently using a computed goto . GOTO (label1,label2,label3), I outOfRangeAction
case I in action1, action2, action3 out outOfRangeAction esac
== Arithmetic IF ==
Fortran 77 has an arithmetic if statement which is halfway between a computed IF and a case statement, based on the trichotomy x < 0, x = 0, x > 0:
IF (e) label1, label2, label3
Where e is any numerical expression (not necessarily an integer); this is equivalent to
IF (e < 0) GOTO label1 IF (e = 0) GOTO label2 IF (e > 0) GOTO label3
This specialized construct was included because the original implementation of Fortran (on the IBM 704) could implement it particularly efficiently with its compare-and-skip instruction.
= 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, or until some condition is met.
In some languages, such as Scheme programming language, loops are often expressed using tail recursion rather than explicit looping constructs.
== Count-controlled loops ==
Most programming languages have constructions for repeating a loop a certain number of times. Note that if N is less than 1 in these examples then the body is skipped completely. In most cases counting can go downwards instead of upwards and step sizes other than 1 can be used. FOR I = 1 TO N for I := 1 to N do begin xxx xxx NEXT I end;
DO I = 1,N for ( I=1; I|
|