The latest instance of the course can be found at: O1: 2024
Luet oppimateriaalin englanninkielistä versiota. Mainitsit kuitenkin taustakyselyssä osaavasi suomea. Siksi suosittelemme, että käytät suomenkielistä versiota, joka on testatumpi ja hieman laajempi ja muutenkin mukava.
Suomenkielinen materiaali kyllä esittelee englanninkielisetkin termit. Myös suomenkielisessä materiaalissa käytetään ohjelmaprojektien koodissa englanninkielisiä nimiä kurssin alkupään johdantoesimerkkejä lukuunottamatta.
Voit vaihtaa kieltä A+:n valikon yläreunassa olevasta painikkeesta. Tai tästä: Vaihda suomeksi.
Chapter 8.3: Robots and Conditional Looping
About This Page
Questions Answered: How can I repeat sequence of a commands if I
can’t find a higher-order method that’s sufficiently convenient or
efficient for my needs? I’ve heard programmers talk about something
called a while
loop — what are they and does Scala have them?
How about creating different sorts of robots?
Topics: Classics from the imperative programmer’s toolkit: do
and while
loops. A class hierarchy for robots. We’ll say a bit
more about streams, too.
What Will I Do? First read, then program.
Rough Estimate of Workload:? This will take time. Reading the text and doing the next two parts of the Robots assignment could well take two hours or more. The last two parts of the assignment are harder and might take three or four hours more.
Points Available: A20 + B45 + C70.
Related Projects: Robots. Plus some mini-examples in DoWhile (new).
Introduction
Recap from 6.2 and 6.3: When solving a programming problem, you may be able to find a tool at a high level of abstraction that provides a simple solution for just what you need. If you don’t, you can build a solution using lower-level tools. Those lower-level tools may not be quite as convenient to use but they are applicable to a wider range of situations; any higher-level tools you have at your disposal havbe also been built from lower-level pieces. Occasionally, it makes sense to deliberately adopt lower-level tools in order to optimize efficiency.
An Example Program
Consider a toy example: We’re writing an interactive program that prompts the user for their name. We’d like the program to check that the user actually enters a string that contains at least one character; the program should keep re-prompting the user until it receives a non-empty string.
The program should work in the text console as illustrated below. In this example run,
the user first just hits Enter
twice, then actually inputs their name:
Enter your name (at least one character, please): The name is 0 characters long. Enter your name (at least one character, please): The name is 0 characters long. Enter your name (at least one character, please): Juha The name is 4 characters long. OK. Your name is Juha.
In Chapter 7.1, we approached problems like this by thinking about a stream of inputs and the operations that we applied to the elements in the stream. Alternatively, we may think of the program in imperative terms: as a sequence of commands that adjust the program’s state step by step. Let’s formulate such a solution, first as pseudocode:
var name = "" Do the following things: name = readLine("Enter your name (at least one character, please): ") println("The name is " + name.length + (if (name.length != 1) " characters" else " character") + " long.") Finish by checking whether name equals the empty string, and if so, do these same things again. Otherwise, advance to the code that follows. println("OK. Your name is " + name + ".")
Our pseudocode bears a resemblance to an if
statement in that it checks a condition —
is the name empty? — and uses the result to decide where to proceed in the program.
The main difference is that the code is potentially executed multiple times, as long as
the condition keeps being met.
On the other hand, this program resembles a for
loop in that it too involves repetition,
a loop. However, this loop isn’t tied to a collection like the for
loops you’ve seen:
it’s formed by repeatedly checking a particular condition.
The do
Loop
Here is a Scala implementation for our pseudocode. You can also find this program inside the DoWhile project.
var name = ""
do {
name = readLine("Enter your name (at least one character, please): ")
println("The name is " + name.length + (if (name.length != 1) " characters" else " character") + "long.")
} while (name.isEmpty)
println("OK. Your name is " + name + ".")
while
with round brackets that contain a condition,
just like we’d do in an if
. This Boolean
expression is evaluated
each time the commands above have been executed.true
. In this example, the loop jumps back
to the beginning each time name
is checked and holds an empty
string.false
.Such a do
–while
loop is commonly known simply as a do
loop. Here’s a generic
outline for writing one:
(Up here, you might have some commands that precede the loop and are executed just once.) do { One or more commands that are executed at least once and whose execution is followed by checking the condition below. In case that condition is true these commands are executed again from the beginning. } while (condition for continuing) (After the condition evaluates to false the program advances to any commands that follow the loop.)
Another example of a do
loop
Study the animation below and predict the program’s behavior when prompted.
What does “while” mean exactly?
Beginners are occasionally confused by how Scala and many other programming
languages use the English word while
. Consider the program above. Since “while”
means “as long as”, one might easily thing that as soon as number
reaches 13 —
which isn’t less than 10 — the loop exits and we proceed to the code that follows.
However, the condition is only checked after each complete execution of the loop body,
and so the program prints 13 twice.
For the same reason, our first program reports “The name is X characters long.” also after the user has entered the final, non-empty input.
The same while
keyword also appears in another, slightly different construct:
The while
Loop
The while
loop is an alternative for the do
loop. This type of loop uses only the
while
keyword, not do
.
Here’s a do
loop, and below it, a while
loop. As you see, the two are very similar.
(Up here, you might have some commands that precede the loop and are executed just once.) do { One or more commands that are executed at least once and whose execution is followed by checking the condition below. In case that condition is true these commands are executed again from the beginning. } while (condition) (After the condition evaluates to false the program advances to any commands that follow the loop.)
do
loop (above) the while
keyword and the condition appear
at the bottom. In a while
loop (below), they are at the top.do
loop checks the condition after each
iteration of the loop body. A while
loop instead checks the
condition before every iteration.do
loop’s body always executes at least once, before checking
the condition for the first time. A while
loop checks the
condition right off the bat, and if it evaluates to false
, the
loop body is not executed at all.(Up here, you might have some commands that precede the loop and are executed just once.) while (condition) { One or more commands that are executed zero or more times, checking the condition above before each iteration. If the condition is true these commands are executed. } (After the condition evaluates to false the program advances to any commands that follow the loop.)
In many cases, there is barely any difference between a do
loop and a while
loop.
For instance, the following while
-based code produces precisely the same interaction as
our earlier do
-based program:
var name = ""
while (name.isEmpty) { // The name is initially empty so we end up running the body at least once anyway.
name = readLine("Enter your name (at least one character, please): ")
println("The name is " + name.length + (if (name.length != 1) " characters" else " character") + " long.")
}
println("OK. Your name is " + name + ".")
These two types of loop are so much alike that it is simple to rewrite any do
loop
as a while
loop and vice versa. (Optional assignment: consider how to do that.) Whenever
you’ve decided you want to use these loops, you can just pick one based on whether you
intend the body to repeat once or more (in which case you might as well pick do
) or zero
or more times (hence while
).
Practice on while
and do
Some Loop-Writing Advice
When you write a loop, take care. If you break even one of the “golden rules of looping” listed below, you’ll have a buggy program on your hands.
val word = "llama"
var index = 0
while (index < word.length) {
println("Letter: " + word(index))
index += 1
}
var
s.What happens if you overlook one of these “rules” depends on the specific loop. A fairly typical outcome is a so-called infinite loop: the computer repeats the same commands “forever”, that is, until it runs out of resources or the program run is externally interrupted.
When does an “infinite” loop stop? How can one stop it?
The alternatives are more or less the same as those in a boxing match:
- Concession: The user can interrupt the
program. How they do that depends on the
environment where they run the program.
In Eclipse, you can click the red
Terminate button. Many
command-line environments use the
keyboard shortcut
Ctrl+C
. - Technical knockout: If the program keeps consuming more and more memory, it will eventually crash with an error once that resource is depleted.
- Disqualification: If you submit such a program in A+, the system will interrupt its execution after a while by externally terminating the process that executes your program.
- Knockout: Power off.
Of course, the main thing to do is to prevent such problems, not to react to them.
Programmer Jim was heading to the store to pick up groceries. As he was leaving the house his wife said: “While you are there, buy some milk.” Jim never came back.
—thanks to the O1 student who shared this cautionary tale
do
and while
vs. Higher-Level Tools
Comparing solutions
These two snippets do essentially the same thing: multiply some integers by two and find the first one that fulfills a particular condition:
val result = Stream.from(0).map( _ * 2 ).dropWhile( _ <= 20 ).head
val result = {
var number = 0
var doubled = 0
while (doubled <= 20) {
number += 1
doubled = number * 2
}
doubled
}
dropWhile
has the same purpose as the conditional expression in the
while
loop.Here’s a toy function that we’ll need for our next example:
def examine(number: Int): Boolean = { println("I’m examining the number " + number + ". Is it over 90?") number > 90 }
The next two snippets generate some random numbers until they happen upon a sufficiently large random number:
Stream.continually( Random.nextInt(100) ).map(examine).find( _ == true )
var isBig = false
do {
isBig = examine(Random.nextInt(100))
} while (!isBig)
find
has the same purpose
as the loop’s conditional. We keep generating and
processing elements in the stream and calling examine
until examine
returns true
on an element.Which tools should I choose?
It should be clear by now that the generic looping constructs do
and while
can be
used for the same purposes as the higher-order methods you’ve seen earlier. Oftentimes,
it isn’t the best idea, but sometimes it does pay off.
By using the higher-order methods on streams and other collections, you emphasize — in your thoughts and in your program code — the data that your program operates on and the operations that you wish to perform on that data. When you use these methods, you leave the details of step-by-step execution for library methods to deal with and focus on expressing the program’s purpose. Which is nice.
By using do
and while
, you instead emphasize the step-by-step execution of commands.
These looping commands bring you a little bit closer to the low-level sequential execution
that takes place within the computer system as it runs your programs. When you use these
loops, you assume direct control of the program’s flow of execution and specify the
sequential steps of your algorithm in detail.
For many purposes, do
and while
loops are unnecessarily detailed. Generally, if
you opt for higher-order methods instead, you’ll have less work to do, you’ll write code
that is more readable, and your program is less likely to contain errors. That being
said, there are reasons to use the loops sometimes. For instance:
- Perhaps you’re implementing an algorithm that relies on modifying the program’s state step by step. Due to the nature of the algorithm, it can be natural to write it down as a sequence of consecutive steps. For instance, some programs that engage the user in dialogue in the text console arguably fall in this category.
Or:
- Perhaps you’re working on an application that needs to be highly efficient (i.e., it needs to run fast). Perhaps you’ve studied your code carefully and identified one or more subprograms that require optimization. To that end, you may wish to painstakingly detail the exact operations in those subprograms rather than leaving those minutiae to library methods.
Conditional loops such as do
and while
are available in many programming languages
and they are used widely. As you continue studying programming, you will keep running
into these constructs. In fact, they are probably used too much by many programmers.
Sometimes, people use them because the programming language affords them no alternatives;
sometimes, people use them because of the surrounding programming culture or because
of historical inertia; sometimes, people use them because they are unaware of better
alternatives.
You should know these loops. But don’t think of them as the primary or only means to implement repetition in a program. Higher-order methods, for instance, are convenient, elegant, and efficient enough for most purposes, and there are other alternatives too.
Loops as first-class citizens
Chapter 5.5 mentioned the expression “first-class functions”, which refers to the notion that a programming language treats functions like it treats other values: functions can be assigned to variables, passed as parameters, returned by functions, etc.; they are first-class citizens of the language,
Chapter 7.1 brought up streams, which enabled us to create collections of
indeterminate length and repeat operations until a given condition was fulfilled.
That is, we could use streams for the same sorts of things that we’ve used loops
for in this chapter. On the other hand, a stream — unlike a loop — can be
treated as data: you can invoke methods such as map
on a stream to produce
a different stream, or you can call find
or exists
to iterate over a part
of a stream. This is why some people call streams “first-class loops”.
What about for
loops?
The code of a for
loop defines the loop’s “shape” simply and implicitly:
after each iteration of the loop body, the loop advances towards termination
by plucking the next element from the collection. The implicit condition for
continuing the loop is: “as long as there are more elements to process”.
for
loops thus operate on a higher level of abstraction than the more
explicit while
and do
loops. Scala’s for
loop is a flavor of
syntactic sugar, a different notation for a higher-order method call.
Robots that Change Location
You’ve done the first four parts of the Robots assignment; now’s the time for the remaining four. You’ll submit them in two batches: first Parts 5 and 6 (for points in Category B), then Parts 7 and 8 (for points in Category C).
Robots, Part 5 of 8: tools for movement
RobotBrain
needs more methods for controlling robot movements. Implement
locationInFront
, squareInFront
, robotInFront
, and moveCarefully
.
Robots, Part 6 of 8: Nosebot
- Implement mobile robots,
Nosebot
s. There are two methods missing from this class:moveBody
andattemptMove
. Start with the latter and use it as you implementmoveBody
.
A stream or a loop?
You could implement
moveBody
with a loop. Alternatively, you could use a stream. Can you come up with both solutions? (You don’t strictly need to, but do try.)A hint for the stream-based solution: you can, for example, use a combination of
map
andfind
akin to the one in the random-numbers example above.
- Try creating some nosebots in the app’s GUI. Notice how the design of the program made it very easy to add a new type of robot in the simulator. Basically, the only thing you needed to do was implement the algorithm that nosebots use for moving.
- Submit Parts 5 and 6.
A+ presents the exercise submission form here.
Robots, Part 7 of 8: collisions
Spinbot
s and Nosebot
s never collide with anything during their own turn but other
sorts of robots, such as the ones you’re about to implement in Part 8, may. Before
that, though, you’ll need to set up a few things so that Square
’s subtypes support
collisions.
- First, notice that
Wall
andFloor
are defined in the same file as their supertypeSquare
:Square.scala
. They could have been in separate files, too, but since there is little code and the classes are closely associated with each other, why not? - The the
Wall
singleton’saddRobot
method doesn’t do anything yet, apart from returning a value that indicates that the arriving robot did not fit into the same square with the wall. Edit this method so that it breaks any robot attempting to enter a wall square. - Also edit the
addRobot
method in classFloor
so that it meets the specification. The method should attend to collisions between robots.
Robots, Part 8 of 8: Staggerbot
, Lovebot
, and Psychobot
- Implement
Staggerbot
.- You’ll need a random-number generator (Chapter 3.5) and you’ll need to use it exactly as specified in the Scaladocs.
- You’re allowed to write private methods, and we recommend that you do. For instance, you could write a separate method for picking a random direction.
- You may find it helpful to add private methods in the next two robot classes too.
- Implement
Lovebot
. - Implement
Psychobot
.- You again have a choice between a loop and/or methods on streams. Can you implement the method in both ways?
- You may find the methods in
GridPos
useful; check the Scaladocs.
- Submit Parts 7 and 8.
A+ presents the exercise submission form here.
Chapter Summary
- Many programming languages have constructs known as
do
andwhile
loops; many, many programs contain such loops. These loops repeat a command or sequence of commands as long as a specific condition continues to be met.- The conditional expression is checked at the
beginning (
while
) or end (do
) of each iteration of the loop body. - When writing these loops, you must pay particular attention to initializing the loop, setting an appropriate condition for continuing, and advancing the program’s state so that the loop will eventually terminate.
- The conditional expression is checked at the
beginning (
for
loops and higher-order methods are often efficient enough and quite a bit more convenient thando
orwhile
loops.- Links to the glossary: loop,
do
loop,while
loop, iteration; stream; level of abstraction.
Hey, What About break
and continue
? And return
?
Some readers who have earlier exposure to other programming languages will be familiar with additional commands that sometimes appear in loops. If you’re one of those readers, you may be wondering if Scala also has those commands?
See below for answers, which are educational for complete beginners, too.
Loop-breaking commands
Various programming languages have commands for exiting a loop body either by
terminating the loop altogether (break
) or by jumping back to the top for a new
iteration (continue
).
When programming in Scala, such commands are seldom used. You can handle practically any
scenario more elegantly by choosing a different approach. However, there is a break
command of sorts available in the Scala API; see elsewhere for more
information. Scala doesn’t provide a continue
command since that command is so very
seldom useful in a well-designed Scala program.
Returning a value from a loop
Various programming languages have a command that explicitly instructs the computer
to immediately terminate the ongoing function call and return a value. This command
is usually named return
. Programmers may use it to interrupt a function call during
a loop, terminating the loop at once along with the rest of the function.
Scala, too, has the return
keyword, although it is rather rarely used. In most
cases, it’s possible to find a better solution without it, although this is to an
extent a matter of taste.
A simple example of return
is shown below. This function loops through a vector and
returns the first non-empty string:
def firstNonEmpty(vector: Vector[String]): Option[String] = {
for (element <- vector) {
if (element.length > 0) {
return Some(element) // Found it. Terminate the search without considering the remaining elements.
}
}
return None
}
return
keyword.return
.return
need an explicit return type
annotation.In this ebook, return
is very seldom used.
A bit more about return
Many Scala programmers look askance at return
and practically never
use it. The reasons have to do with writing clearer code and the fact
that return
isn’t strictly needed for anything.
return
may make it harder to follow the steps of a program (the
program’s “control flow”). This is a serious risk especially if the
code is composed of many nested and verbose constructs. Reliance on
return
may also lead a programmer to write such needlessly complicated
code.
It’s generally considered good programming practice to split a
program in small, cleanly delimited subprograms. If you do that,
there is usually little temptation to use return
. Moreover,
languages such as Scala have many elegant alternatives to the
“loop and return
” approach. These techniques include higher-order
methods that process only a part of a collection (such as find
)
as well as recursion (Chapter 11.2); they make return
largely
redundant. Higher-order methods and recursion are particularly common
in the functional programming style (Chapter 10.2) but they aren’t
unique to it.
But it’s not a mortal sin to put return
in your Scala program,
especially if your code is otherwise nicely written.
A tangent on StarCraft and return
In his blog post Whose bug is this anyway?!?, game developer Patrick Wyatt is kind enough to recount a past blunder: he didn’t initially notice a bug in the StarCraft game even though it was “trivial”. It’s a nice read.
The error involved a return
command that terminated the relevant subprogram
in case a particular condition was met. However, another section of code many
lines further down in the same subprogram was written without consideration of
the fact that the code won’t get executed at all in case the condition had already
triggered an early return
.
Something that’s particularly noteworthy about this cautionary tale is that
the conditional return
was followed by a long sequence of other commands
all within the same subprogram and all implicitly dependent on the return
way
above. return
is dangerous when a program isn’t split into functions that
are small enough.
A bit more about break
Even more Scala programmers frown at break
than at return
.
For the most part, break
has been criticized on similar grounds
as return
has. The additional complaint is: assuming you do wish
to break out of a loop for some reason, and further assuming your
code is appropriately divided in small functions, each with its
own cleanly delimited purpose, then you don’t need break
; you
can just return
your way out of the loop.
If you feel you need break
, you should first consider if you
might be able to place your loop in a function and use return
to
terminate it. (And then you can consider whether there might be
a better alternative to return
as well.)
More kinds of loops?
Some programming languages provide a different sort of for
loop that
has separate “slots” for initializer code, the loop-controlling
condition, and the code that advances the loop towards termination. In
a Java program, for instance, you can write:
// This is Java, not Scala.
for (index = 0; index < myString.length(); index += 1) {
// Do the loop’s actual job here.
}
Scala doesn’t have that sort of for
loop. On the other hand,
Scala’s for
expressions are capable of various other tricks,
which we’ll discuss later.
Feedback
Please note that this section must be completed individually. Even if you worked on this chapter with a pair, each of you should submit the form separately.
Credits
Thousands of students have given feedback that has contributed to this ebook’s design. Thank you!
Weeks 1 to 13 of the ebook, including the assignments and weekly bulletins, have been written in Finnish and translated into English by Juha Sorva.
Weeks 14 to 20 are by Otto Seppälä. That part of the ebook isn’t available during the fall term, but we’ll publish it when it’s time.
The appendices (glossary, Scala reference, FAQ, etc.) are by Juha Sorva unless otherwise specified on the page.
The automatic assessment of the assignments has been programmed by Riku Autio, Jaakko Kantojärvi, Teemu Lehtinen, Timi Seppälä, Teemu Sirkiä, and Aleksi Vartiainen.
The illustrations at the top of each chapter, and the similar drawings elsewhere in the ebook, are the work of Christina Lassheikki.
The animations that detail the execution Scala programs have been designed by Juha Sorva and Teemu Sirkiä. Teemu Sirkiä and Riku Autio have done the technical implementation, relying on Teemu’s Jsvee and Kelmu toolkits.
The other diagrams and interactive presentations in the ebook are by Juha Sorva.
The O1Library software has been developed by Aleksi Lukkarinen and Juha Sorva. Several of its key components are built upon Aleksi’s SMCL library.
The pedagogy of using tools from O1Library (such as Pic
) for simple graphical programming
is inspired by the textbooks How to Design Programs by Flatt, Felleisen, Findler, and
Krishnamurthi and Picturing Programs by Stephen Bloch.
The course platform A+ has been created by Aalto’s LeTech research group and is largely developed by students. The current lead developer is Jaakko Kantojärvi; many other students of computer science and information networks are also active on the project.
For O1’s current teaching staff, please see Chapter 1.1.
Additional credits appear at the ends of some chapters.
do
. Another keyword,while
, appears on the line that ends the loop. These are two of Scala’s reserved words (likeif
etc.), not methods on an object.