A computation is made up of one or more lines of execution.
How exactly execution proceeds within a line is known as control flow.
There are (at least) five major types of flow:
Do this THEN this THEN this, in the order actions appear in the program source code
Do this OR this OR this (chosen based on the evaluation of a condition)
Do this WHILE this is true, or UNTIL this is true, or for EACH item in a collection
Do this OR this OR this (chosen randomly among a number of alternatives)
Go some place else, abandon, or recover
The three big kinds of entities that contribute to control flow, and their three Es, are:
Some languages, notably Ada, keep these three kinds of entities syntactically separate. In others, such as C++, they are all mixed together as statements: you can have declaration statements and expression statements as well as other typical statements.
void f() { cout << "hello"; // expression int x = 10; // declaration if (x < 2) return; // statement }
Some languages don’t have statements at all—code is made up of entirely of expressions. These are called expression-oriented languages. They have while-expressions, not while-statements. Here’s an example in ML:
- val x = ref 5; > val x = ref 5 : int ref - val y = while !x > 0 do (print(Int.toString(!x)^"\n"); x := !x - 1); 5 4 3 2 1 > val y = () : unit
and in Ruby:
>> x = 5 => 5 >> y = (while x > 0; puts x; x -= 1; end) 5 4 3 2 1 => nil >> y => nil
and in Scala:
scala> var x = 5 x: Int = 5 scala> var y = (while (x > 0) {println(x); x -= 1;}) 5 4 3 2 1 y: Unit = ()
and in Algol68, where the following expression evaluates to 5:
BEGIN
a := IF b < c THEN d ELSE e;
a := BEGIN f(b); g(c) END;
g(d);
2 + 3
END
Rust is almost like the others. It has a let-statement, a macro invocation statement, a declaration statement, but every other thing you would think of as a statement (if, while, call, break, continue, match, loop, etc.) are all expressions.
In such languages, expressions perform actions in addition to producing values. The kind of value produced by ”statement-like” expressions is something like null
, nil
, None
, Unit
, unit
, ()
, void
, or some other indication of a value not really mattering.
Now, let’s look at the five major types of flow.
Sequencing is the most basic control flow. It refers to doing elaborations, evaluations, or executions one after another. Not in parallel. Just in the order things appear in the source code. Not out of order, either (unless a compiler can guarantee that such optimizations don’t change the meaning).
A simple example:
let x = 5 // This happens first, x is now 5 let y = 8 - x // This happens after x is initialized, y is now 3 let z = x + y // This happens after x and y are initialized console.log(z) // This reliably prints 8
C uses semi-colons for sequencing statements and declarations, but uses the comma operator for expressions:
x = 5; y = x + 3; /* x is assigned 5 THEN y is assigned 8 */ x = f(a), g(b), 3; /* f is called THEN g is called THEN x is assigned 3 */ x = 1,000; /* x is assigned 0 */
Standard ML doesn’t have statements, but it can sequence expression evaluation. It uses the semicolon for sequencing:
val x = 5; val y = x (* x and y now both 5 *) val x = (f(a); g(b); 3) (* x now 3 -- note parens required BTW *) (* However "and" does parallel binding, NOT sequential *) val x = y and y = x (* Yes, it’s a swap *)
You do not always need a sequencing operator; you can get sequencing by calling functions. Here’s some Haskell:
(\x -> (\y -> "x is " ++ show x ++ " and y is " ++ show y)(x + 3))(5)
That gets hard to read, so you’ll often see syntactic sugar such as:
let x = 5 in let y = x + 3 in "x is " ++ show x ++ " and y is " ++ show y
So, yes, let
-expressions sugar function calls. Who knew?
let
-expression for the function call (\x -> x + 3)(5)
? let x = 5 in x + 3
Conditional flow means we do one of several alternatives, each of which are guarded by their own condition. We normally evaluate the conditions in order and take the first condition that is true.
The syntactic variation on this simple conditional flow across many languages is huge. Sometimes the flow is captured at the expression level and sometimes at the statement level. Here’s the simple conditional operator expressed in several languages:
console.log(lat >= 0 ? "North" : "South")
print("North" if lat >= 0 else "South")
System.out.println(lat >= 0 ? "North" : "South")
println(if (lat >= 0) "North" else "South")
println!("{}", if lat >= 0 { "North" } else { "South" })
Put_Line(if lat >= 0 then "North" else "South");
(println (if (>= lat 0) "North" "South"))
print(lat >= 0 ? "North" : "South")
print_endline(if lat >= 0 then "North" else "South")
0 >= "North" "South" ? print
In general, multi-way conditions within expressions can be expressed by nesting conditional operators, for instance x < 0 ? "NEG" : x > 0 ? "POS" : "ZERO"
but, um, this can get messy. In the case that each alternative is controlled by a single value, many languages have a slick expression form that helps:
var action = switch (color) { case Color.RED -> "stop"; case Color.YELLOW -> "slow down"; case Color.GREEN -> "go"; }
let action = match color { Color::Red => "stop", Color::Yellow => "slow down", Color::Green => "go" }
val action = when (color) { Color.RED -> "stop" Color.YELLOW -> "slow down" Color.GREEN -> "go" }
let action = match color with | Red -> "stop" | Yellow -> "slow down" | Green -> "go"
let action = case color of Red -> "stop" Yellow -> "slow down" Green -> "go"
Action = case Color of red -> "stop"; yellow -> "slow down"; green -> "go" end.
Conditional flow can also be written at the statement level. The most well-known form of conditional flow (at the statement level) is probably the venerable if
-statement:
// Java, C, C++, C#, JavaScript, Go, Rust, Swift, Kotlin if (e1) { s1 } else if (e2) { s2 } else if (e3) { s3 } else if (e4) { s4 } else { s5 } /* For PHP, replace "else if" with "elseif" above */ /* For Perl, replace "else if" with "elsif" above */
# Ruby - terminal end if e1 then s1 elsif e2 then s2 elsif e3 then s3 elsif e4 then s4 else s5 end # For Lua, replace "elsif" with "elseif" # For Ada, you finish with "end if;" # For Fortran, replace "elsif" with "else if" and finish with "end if" # In Ruby, the "then" is optional unless you use a single-line form.
# Python, Mojo - indentation if e1: s1 elif e2: s2 elif e3: s3 elif e4: s4 else: s5
# Bash - a terminal end but it is called "fi" if e1; then s1 elif e2; then s2 elif e3; then s3 elif e4; then s4 else s5 fi
Here is a specific example in Python:
if not started: started = True yield n elif n == 1: raise StopIteration elif n % 2 == 0: n = n // 2 else: n = 3 * n + 1
In some languages, notably Go, Odin, Swift, and C++, you can declare a variable right before the condition and it will be local to the statement.
if v := f(); v > 0 { fmt.Println("v is positive:", v) } else { fmt.Println("v is non-positive:", v) } // v is not accessible here
if let v = f(), v > 0 { print("v is positive:", v) } else { print("v is non-positive:", v) } // v is not accessible here
if (int v = f(); v > 0) { cout << "v is positive: " << v << endl; } else { cout << "v is non-positive: " << v << endl; } // v is not accessible here
instanceof
in an if
condition. Research this feature and give a real-life example of it in use.
Some languages have a syntax that manages to avoid all those “else-ifs”:
% Erlang if expression, with guards if e1 -> s1; e2 -> s2; e3 -> s3; e4 -> s4; true -> s5; end.
; Common Lisp (cond ((e1) (s1)) ((e2) (s2)) ((e3) (s3)) ((e4) (s4)) (t (s5)))
-- Ada case e is when c1 => s1; when c2 => s2; when c3 => s3; when c4 => s4; when others => s5; end case;
match e: case c1: s1; case c2: s2; case c3: s3; case c4: s4; case _: s5;
switch (e) { c1 -> s1; c2 -> s2; c3 -> s3; c4 -> s4; default -> s5; }
when (e) { c1 -> s1 c2 -> s2 c3 -> s3 c4 -> s4 else -> s5 }
Ada even checks to make sure at compile time that the cases are exhaustive!
WARNING: Some languages bastardize the conditional so that once you found a truthy condition, you “fall through” and execute subsequent cases. This is horrifying. You will almost always need to put a break
or return
or something similar to prevent that from happening.
// Java, C, JavaScript, C++
switch (e) {
case c1 : s1; // These "fall through", so you
case c2 : s2; // ...will normally place a "break"
case c3 : s3; // ...or a "return" after each
case c4 : s4;
default : s5; // In Java you should always use "->", not ":"
}
In Go, you don’t fall through, but you can put in a fallthrough
statement:
switch prizeLevel { case 4: fmt.Println("Car") fallthrough case 3: fmt.Println("Tent") fallthrough case 2: fmt.Println("T-shirt") fallthrough case 1: fmt.Println("Bandana") }
Fallthrough?Seems like nuts, right? It was designed by people thinking about hardware and solving some systems-level implementation ideas like “jump tables” which you might enjoy researching.
In our modern era, readability is in and cleverness is out (and machines are really fast), so it might be good to follow this advice: Avoid switches in languages with implicit fall-through. Even when people tell you “oh it is so amazing in these particular cases,” remember that those cases are pretty esoteric and you will come across them so rarely that they aren’t even worth worrying about.
As an aside, it’s worthwhile to note that a condition switch need not be just a boolean expression. It is often allowed to be any kind of (possibly wild) pattern match. Here’s a Python example:
match e: case 2 | 3 | 5 | 7 | 11: print("Small prime") case int(n) if n % 5 == 0: print("Multiple of 5") case (_, x, _): print(f"A three-tuple with {x} in the middle") case {'id': y}: # Matches any dictionary that has an id key, binds value to y print(f"Your identifier is {y}") case _: print("What?")
switch
expression and switch
statement. We saw Python’s match
statement only. Does Python even have a match
expression?
Time for more conditional structures! Perl and Ruby have an unless
statement:
# Perl unless ($x >= 0) { # Braces required in Perl for compound statements die "must be non-negative"; }
Perl and Ruby allow if and unless to be used as modifiers for simple statements which read really nicely (at least in English):
# Perl die "must be non-negative" unless $x >= 0; die "must be non-negative" if $x < 0; # Same as above
Here’s something cool. Short-circuit operators can be used for selection too:
# Perl chdir $dir or die "Can’t change to $dir: $!"; open F, $file or die "Can’t open $file: $!"; @lines = <F> or die "$file may be empty"; close F or die "Can’t close $file: $!";
This is quite satisfying! One’s eye can scan the "normal" flow of control down the left margin.
cond
. Check it out. What is different about it?
To iterate means to do something repeatedly, allowing for slight differences in the thing at each iteration. An iteration could go on forever:
But typically it employs a test:
Iteration can be done either for each value in a range or collection (definite iteration), or while (or until) some condition holds (indefinite iteration). Iteration is typically modeled in four ways:
Let’s look at each of these.
There seem to be 5 kinds of loops:
Example time!
Ada, Fortran, and Go represent forever-loops directly:
loop Put_Line("HELP ME"); end loop;
do print *, "HELP ME" end do
for { fmt.Println("HELP ME") }
Most other languages get the effect of a forever loop with a logically-controlled loop, which we’ll get to in a minute, and write something like JavaScript’s:
while (true) { console.log("HELP ME") }
It is somewhat frustrating how rare this seems to be. Shoutout Ruby and Go!
5.times do puts "Hello is anyone there?" end
for range 5 { fmt.Println("Hello is anyone there?") }
There is quite a variety out there. Often, a language will have a way of saying do something while a condition is true, with the test happening before each iteration. That way, if the condition is initially false, the loop body will not execute at all.
Code | Languages | Notes |
---|---|---|
while (active) { run(); } | Java, C, C++, JavaScript, Perl | |
while active { run() } | Rust, Swift | |
while active do run() | ML, Pascal | |
WHILE active DO run() END | Modula-2, Modula-3 | |
while active do run() end | Lua | |
do while (active) call run() end do | Fortran | |
while Active loop Run(); end loop; | Ada | |
while active run() end | Julia, Ruby | |
for active run() end | Go | Go does not have a while keyword! |
run() while active | Perl, Ruby | Condition is still evaluated before the first iteration, even though it looks like it happens at the end |
As we saw earlier with the if
-statement, many languages allow a local variable to be declared right before the condition. This variable will be local to the loop condition and body. It is initialized just once, before the first condition evaluation.
TODO
Some languages offer an until
form for logically-controlled loops. It’s not as common, but it reads nicer when you are more interested in the stopping condition rather than the continuation condition.
repeat run() until exhausted | Pascal, Lua |
REPEAT run() UNTIL exhausted | Modula-2, Modula-3 |
until (exhausted) {run()} | Perl |
run() until exhausted | Perl, Ruby |
until exhausted; run(); end | Ruby |
Many languages provide loop constructs that loop through, or enumerate, items in a collection, such as an array, list, set, string, lines in a file, files in a folder, and so on. (How the language identifies what kids of things are iterable is another matter, for now, we’re just looking at the syntax for the iteration):
# Python pets = ["dog", "rabbit", "rat", "turtle"] for p in pets: print(p.upper())
// JavaScript -- not that it is for-OF, ****not**** for-IN const pets = ["dog", "rat", "fish", "rabbit"]; for (const p of pets) { console.log(p.toUpperCase()); }
# Julia pets = ["dog", "rat", "fish", "rabbit"] for p in pets println(uppercase(p)) end
# Perl my @pets = ("dog", "rat", "fish", "rabbit"); for my $p (@pets) { print uc($p); }
// Java var pets = List.of("dog", "rat", "fish", "rabbit"); for (var p: pets) { System.out.println(p.toUpperCase()); }
// C++ vector<string> pets = {"dog", "rat", "fish", "rabbit"}; for (auto p: pets) { cout << p << '\n'; }
-- Ada, assuming Ada.Characters.Handling.To_Upper was imported declare pets : array(1..4) of String := ["dog", "rat", "fish", "rabbit"]; begin for Pet of Pets loop Put_Line (To_Upper(Pet)); end loop; end;
// Swift let pets = ["dog", "rat", "fish", "rabbit"] for pet in pets { print(pet.uppercased()) }
Oh hey, there’s something cool in Perl. You don’t always need a loop variable—the special variable $_
takes on that role. And that variable can even be implicit. The following three Perl statements are the same:
for (1..10) {print $_;} for (1..10) {print} print for (1..10)
Hey what about Go and Lua?Interestingly, we don’t have good examples for iterating only through the elements of a sequential collection in Go or Lua. Why not? We’ll see very soon why not.
Sometimes you need the index, in addition to the value, within a collection. Some languages offer a function or method, when applied to a collection, to yield Index-Value pairs:
# Python pets = ["dog", "rabbit", "rat", "turtle"] for i, p in enumerate(pets): print(p, 'is at index', i)
// Swift let pets = ["dog", "rabbit", "rat", "turtle"] for (i, p) in pets.enumerated() { print("\(p) is at index \(i)") }
// JavaScript const pets = ["dog", "rabbit", "rat", "turtle"] for (let [i, p] of pets.entries()) { console.log(p, 'is at index', i) }
// Go func main() { pets := [...]string{"dog", "rat", "rabbit", "turtle"} for i, p := range pets { fmt.Println(p, "is at index", i) } }
-- Lua pets = {"dog", "rat", "rabbit", "turtle"} for i, p in ipairs(pets) do print(p .. " is at index " .. i) end
What’s interesting about Go and Lua is that there is no way to iterate only over the values. To get just the values, you need to explicitly ignore the index! It’s common to do this by naming the index variable _
and just not touching it.
By the way, there are languages, like C, in which you have to use the index only and then grab the value by subscripting. C is really low level.
# Python pets = {"Lisichka": "dog", "Clover": "rabbit", "Oreo": "rat"} for name, kind in pets.items(): print(name, 'is a', kind)
// Swift let pets = ["Lisichka": "dog", "Clover": "rabbit", "Oreo": "rat"] for (name, kind) in pets { print("\(name) is a \(kind)") }
// Go func main() { pets := map[string]string{"Lisichka": "dog", "Clover": "rabbit", "Oreo": "rat"} for name, kind := range pets { fmt.Println(name, "is a", kind) } }
-- Lua pets = {Lisichka = "dog", Clover = "rabbit", Oreo = "rat"} for name, kind in pairs(pets) do print(name .. " is a " .. kind) end
// JavaScript const pets = {Lisichka: "dog", Clover: "rabbit", Oreo: "rat"}; for (const [name, kind] of Object.entries(pets)) { console.log(`${name} is a ${kind}`); }
// Java var pets = Map.of("Lisichka", "dog", "Clover", "rabbit", "Oreo", "rat"); for (var e: pets.entrySet()) { System.out.println(e.getKey() + " is a " + e.getValue()); }
A typical iteration that shows up a lot is iteration over the lines of a file. Here’s a program that iterates over the lines of a file and writes them to standard output prefixed with a line number, padded at the beginning with zeros:
import sys if len(sys.argv) != 2: print(f'Usage: {sys.argv[0]}
') sys.exit(1) line_number = 0 with open(sys.argv[1], 'r', encoding='utf-8') as file: for line in file: line_number += 1 print(f'{line_number:08}: {line.rstrip()}')
import { open } from "fs/promises" if (process.argv.length !== 3) { console.log(`Usage: ${process.argv[1]}
`) process.exit(1) } let lineNumber = 0 const file = await open(process.argv[2], "r") for await (const line of file.readLines()) { lineNumber++ console.log(`${lineNumber.toString().padStart(8, "0")}: ${line}`) }
if #arg ~= 1 then print(string.format("Usage: %s
", arg[0])) os.exit(1) end line_number = 0 file = io.open(arg[1], 'r') if file == nil then error("No such file") end for line in file:lines() do line_number = line_number + 1 print(string.format("%08d: %s", line_number, line)) end file:close()
An aside on resource managementIn the JavaScript and Python examples above, we used constructs that automatically close the opened file. Lua required an explicit
close
call. Lua is a very simple languages without many features.
A numeric range is very much like a list, right? It’s just such a common kind of thing that many languages give you a construct for it, or a special syntax in the for
-loop:
for (i = 0; i < 10; i++) b | Many languages |
FOR i := 1 TO 10 DO b END | Modula-2, Modula-3 |
for I in 1..10 loop b end | Ada |
for i = 1, 10 do b end | Lua |
for i = 1:10 b end | Julia |
for i in range(1,11): b | Python |
for my $i (1..10) {b} | Perl |
for (i = 0; i < 10; i += 3) b | Many languages |
FOR i := 1 TO 10 BY 3 DO b END | Modula-2, Modula-3 |
for i in range(1,11,3): b | Python |
for i := 1,10,3 do b end | Lua |
Now, what if you are C or JavaScript? You don’t have a special form. You can go with a traditional while
loop:
int i = 1; while (i <= 10) { // do something with i i++; }
But just like you can move the initializer into a loop header, something like
(int i = 1; i <= 10)
looping through integer ranges is so common that we might as well move the end-of-the-loop piece into the header too:
(int i = 1; i <= 10; i++)
And that’s what C does, except C replaces while
with for
:
for (int i = 1; i <= 10; i++) { // do something with i }
This funky syntax has actually been adopted by quite a few languages, though you won’t need it often, unless your language does not give you any alternatives. Or, hey, you might just like it. It is so common that most programmers can just read it fine.
And by the way, it makes it easy to do the “step size” thing:
for (int i = 1; i <= 10; i += 3) { // do something with i }
The old-fashioned for-loop syntax in C, Java, C++, and JavaScript can be used to iterate through the nodes of a linked list:
/* C */ for (int* p = a; p; p = p ->next) ...
In Perl you can dispense with making an array to iterate over and just list the contents of your collection:
for my $count (10,9,8,7,6,5,4,3,2,1,"liftoff") {...} for my $count (reverse "liftoff", 1..10) {...}
But here’s something really cool. There’s this neat mix of definite and indefinite iteration in Algol 60, with this cool syntax:
for i := 1, i+2, while i<10 do ...
[Algol 60] is a language so far ahead of its time that it was not only an improvement on its predecessors but also on nearly all its successors. —Tony Hoare
In Swift and Ada, the for
statement has a where
clause:
for i in 1...10 where i % 2 == 0 { print(i) }
for I in 1 .. 10 when I mod 2 = 0 loop Put_Line(Integer'Image(I)); end loop;
And something else fancy! Julia can combine nested loops into a single loop:
for c = 1:40, b = 1:c-1, a = 1:b-1 if a * a + b * b == c * c println("$a, $b, $c") end end
Building your own language? Think, then, about:
goto
to jump inside an enumeration-controlled loop?
for (short i = 30000; i <= 32767; i++) {...}
This is a very popular alternative to for-loops:
# Ruby pets = ["dog", "rat", "fish", "rabbit"] pets.each {|p| puts p.upcase}
// JavaScript const pets = ["dog", "rat", "fish", "rabbit"]; pets.forEach(p => console.log(p.toUpperCase()));
// Java var pets = List.of("dog", "rat", "fish", "rabbit"); pets.forEach(p -> System.out.println(p.toUpperCase()));
// Swift let pets = ["dog", "rat", "fish", "rabbit"] pets.forEach {print($0.uppercased())}
Ruby and JavaScript use this technique to produce value and its index during iteration:
# Ruby pets = ["dog", "rat", "fish", "rabbit"] pets.each_with_index {|p, i| puts "#{p} is at index #{i}"}
// JavaScript const pets = ["dog", "rat", "fish", "rabbit"]; pets.forEach((p, i) => console.log("%s is as index %d", p, i));
Many languages have an each-function for dictionaries, too:
// Java var pets = Map.of("Lisichka", "dog", "Clover", "rabbit", "Oreo", "rat"); pets.forEach((name, kind) -> System.out.println(name + " is a " + kind));
// JavaScript const pets = {Lisichka: "dog", Clover: "rabbit", Oreo: "rat"}; Object.entries(pets).forEach(([name, kind]) => { console.log(`${name} is a ${kind}`); });
# Ruby pets = {Lisichka: "dog", Clover: "rabbit", Oreo: "rat"} pets.each {|name, kind| puts "#{name} is a #{kind}"}
Many languages use each
to build up dozens of methods that work on each item of a collection.
Examples include map
, filter
, every
, some
,
min
, and max
. The effect of all this is that you might find yourself writing
few, if any, loops when processing collections!
An iterator is an object that keeps track of where you are during an iteration. You don’t have to use them in a loop! You just call methods such as hasNext
and next
(or in some languages, begin
,
end
, and ++
).
// Java - variable types shown explicitly for emphasis List<String> pets = Arrays.asList("dog", "rat", "rabbit"); Iterator<String> it = pets.iterator(); System.out.println(it.hasNext()); // true System.out.println(it.next()); // dog System.out.println(it.hasNext()); // true System.out.println(it.next()); // rat System.out.println(it.hasNext()); // true System.out.println(it.next()); // rabbit System.out.println(it.hasNext()); // false System.out.println(it.next()); // raises NoSuchElementException
// C++ vector<string> pets = {"dog", "rat"}; vector<string>::iterator it = pets.begin(); cout << *it << '\n'; // dog it++; cout << *it << '\n'; // rat it++; cout << (it == pets.end()); // 1
*it
when it
is at the end? What if you try it++
?
# Python pets = ["dog", "rat"] it = iter(pets) next(it) # "dog" next(it) # "rat" next(it) # raises a StopIteration exception!
# Python def colors(): yield 'red' yield 'green' yield 'blue' it = colors() next(c) # "red" next(c) # "green" next(c) # "blue" next(c) # raises a StopIteration exception!
The use of explicit iterators opens the possibility that your underlying collection changes while your iterator is still active. In some languages, this may cause your program to just crash; in others, doing this will trigger a concurrent modification exception.
// Java var pets = new ArrayList<String>(){{add("dog");add("rat");}}; var it = pets.iterator(); System.out.println(it.next()); // dog pets.add("turtle"); System.out.println(it.next()); // raises ConcurrentModificationException
A recursive function is one that calls itself (either directly or indirectly). You can design recursive functions to carry out iterative control flow. Recursion is:
for
and while
constructsRecursive code is:
What could go wrong?
(* THIS IS A REALLY STUPID USE OF RECURSION *) fun fact n = if n < 0 then 1 else n * fact(n-1)
evaluates as
fact 4 = 4 * fact 3 = 4 * (3 * fact 2) = 4 * (3 * (2 * fact 1)) = 4 * (3 * (2 * (1 * fact 0))) = 4 * (3 * (2 * (1 * 1))) = 4 * (3 * (2 * 1)) = 4 * 3 * 2 = 4 * 6 = 24
Here, all these pieces of partially complete computations take up a lot of space, hurting performance. Fortunately, there is an alternative approach.
Tail recursive code, in which a function returns the result of a recursive call to itself, can always be implemented efficiently. Contrast that last factorial implementation with this one:
(* ML, Tail Recursive *) fun gcd x y = if y = 0 then x else gcd y (x mod y)
-- Haskell, Tail Recursive gcd x y = if y == 0 then x else gcd y (x `mod` y)
// JavaScript, Tail Recursive const gcd = (x, y) => y === 0 ? x : gcd(y, x % y);
This evaluation is much cleaner:
gcd 444 93 = gcd 93 72 = gcd 72 21 = gcd 21 9 = gcd 9 3 = gcd 3 0 = 3
A tail recursive function returns exactly the result of calling itself — no partial results need to be stored. A good compiler can recognize tail recursion and generate code that has no calls at all: just reload the parameters and jump back to the top. It’s as if you wrote:
# Ruby def gcd(x, y) while true return x if y == 0 x, y = y, x % y end end
though the tail-recursive code is cleaner, and better because it has no side effects!.
In functional programming, the programmer will sometimes have to turn a non-tail-recursive function into a tail recursive one. The idea is to pass along arguments (like a counter or partial result) into the next call. So factorial can be written like this:
(* ML *) fun fact n = let fun f i a = if i = n then a else f (i+1) ((i+1)*a) in f 0 1 end
which is evaluated like so:
fact 5 = f 0 1 = f 1 1 = f 2 2 = f 3 6 = f 4 24 = f 5 120 = 120
and Fibonacci like this:
(* ML *) fun fib n = let fun f i last current = if i = n then current else f (i+1) current (last+current) in f 0 0 1 end
This yields:
fib 7 = f 0 0 1 = f 1 1 1 = f 2 1 2 = f 3 2 3 = f 4 3 5 = f 5 5 8 = f 6 8 13 = f 7 13 21 = 21
This sure beats the naive implementation, which requires 535,821,591 calls to compute fib(40)
.
Nondeterministic control flow occurs when the next computation step is made randomly (not arbitrarily) from a set of alternatives. It is similar to conditional flow, but there is no explicit test. The runtime system makes a random choice as to how to continue the computation:
Some languages have a specific construct for nondeterministic choice:
select
x := 4;
or
y := 6;
or
print "Hello";
end;
Generally each of the arms are guarded. To execute a select statement, first the guards are evaluated, then a choice is made among the open alternatives (those with true guards). A missing guard is assumed to be true. Example:
select when x > y =>
y := x * x - 3;
or when not found =>
print x;
or
close(f);
or when x % y >= 25 || finished =>
crash();
end;
What if all guards are false? In Ada, this raises an exception. In other languages, the statement simply has no effect.
Nondeterministic control flow can hide some asymmetries in code. Some examples:
select when (a >= b) =>
max := a;
or when (a <= b) =>
max := b;
end;
loop
select when a > b =>
a := a - b;
or when b > a =>
b := b - a;
or when a = b =>
return a;
end;
end;
Sometimes, nondeterminism is more subtle, but it is there, and you have to be aware of it. Suppose that x
and y
are global variables and the functions f
and g
can write to them, and consider the expressions f(x) + g(y)
and h(f(x), g(y))
.
If a language does not require operands or even function arguments to be evaluated in any particular order(e.g., left-to-right or right-to-left) and truly allows the runtime to evaluate the operands in any particular order it wants, then we have nondeterminism.
How does this matter in practice? This says you should learn the evaluation order rules of a language. Or even better, try not to write expressions whose result depends on evaluation order.
Nondeterministic constructs turn out to be very useful in concurrent programming, because random execution paths sometimes help to avoid deadlock. We’ll see how when we study concurrency later on.
Conditional, Iterative, and Nondeterministic flow each modify the standard sequential flow but in a structured fashion. That is, every if
, while
, or select
statement is itself just another statement in a sequence of statements. In fact, the very term structured programming refers exactly to this notion.
However, it’s often convenient disrupt the control flow in a very unstructured way.
Here are some constructs that enable you to do something other than the next thing that a typical control flow would suggest:
While indispensible for low-level programming, the goto
statement is not used much, if at all, in high-level languages.
Read about goto at Wikipedia.
Sometimes something goes wrong and you need to abandon the rest of a block (or function or program), indicating exactly what happened. This is frequently done by throwing or raising an exception. (Sometimes exceptions are simply called errors.)
The syntax varies widely among languages, so here’s some JavaScript just to have at least one concrete example:
console.log('Welcome to my script') throw 'Ha ha ha' console.log('You will never see this message')
Here’s how to catch in JavaScript:
try { // This is a contrived example that just illustrates a point console.log('Welcome to my script') throw 'Ha ha ha' console.log('You will never see this message') } catch (e) { console.log(`Caught: ${e}`) }
In JavaScript, you can throw any value at all. In other languages, you can only throw objects of a certain type. To be fair, JavaScript does recommend you throw objects having the Error
type (or any of its subtypes):
throw new Error("Sorry, I don't accept words like that.")
There are a lot of built-in error types in JavaScript (and in other languages too):
> let a = [10, 20, 30]; > a.length = -5; RangeError: Invalid array length > a = null; > a[3] TypeError: Cannot read property '3' of null > @#@*($#*(; SyntaxError: Invalid or unexpected token
ArithmeticException
, ArrayIndexOutOfBoundsException
, ClassCastException
, IllegalArgumentException
, IllegalStateException
, NullPointerException
, NumberFormatException
, UnsupportedOperationException
.
Avoiding exceptions: Errors Are ValuesMany languages intentionally omit exceptions because they are complex and the language values simplicity. Sometimes a language leaves out exceptions because the language designers dislike them immensely. After all, exceptions are a disruptive control flow and can lead to very convoluted and ugly code.
Without exceptions, a language will encourage an errors as values approach. This approach is taken in Go, Zig, Rust, and many other languages.
Modern languages have a panic
construct which is loosely equivalent to a throw, but designed in such a way to discourage their overuse. That is, people sometimes use try/catch to build up normal looking programs instead of using them only as very last resort—to handle truly unexpected and very problematic cases.
The section in the Go FAQ on Go not having exceptions elaborates a bit.
Many languages give you opportunities to modify loop behavior. You can:
break
(C, Java, Ruby, JavaScript)
exit
(Ada, Modula)
last
(Perl)
continue
(C, Java, JavaScript)
next
(Perl, Ruby)
redo
(Perl, Ruby)
retry
(Ruby)
Perl has an interesting continue
construct, where you can put code that is to be done at the end of every iteration, regardless of how the iteration ended (either normally or through a next
). It saves you from writing some convoluted if
statements:
# Perl LINE: while (<STDIN>) { next LINE if /^#/; next LINE if /^$/; # ... process $_ .... } continue { count++; }
Python allows else
clauses on its for
and while
statements. This is where you can put code that is supposed to run only when the loop finishes normally, not when the loop is prematurely terminated via a break
, return
, or raise
.
for place in places: if good(place): print(f"Ah, a good place: {place}") break else: print("No good places for you")
tries, guess = 0, None while guess != answer: guess = input("What is your guess? ") if malformed(guess): print("You are not playing fair, game over") break else: print(f"You got it, it was: {guess}")
Here are some questions useful for your spaced repetition learning. Many of the answers are not found on this page. Some will have popped up in lecture. Others will require you to do your own research.
switch
statement, that fit nicely with the machine instruction set they were working with, but is hardly ever used in application programming. What was it? fallthrough
was added.if
statement? Integer
class called times
that takes a block and executes it the specified number of times. In C-like languages, you have to write a loop, and you have to remember to increment the loop variable.10.times {puts "Hello"}
for
statement.for
and while
constructs.else
clauses on Python’s for
and while
statements do? break
, return
, or raise
.We’ve covered: