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.
Kieli vaihtuu A+:n sivujen yläreunan painikkeesta. Tai tästä: Vaihda suomeksi.
Chapter 10.3: Robots That Compete
About This Page
Questions Answered: How can a program operate on other programs? How might we make virtual robots act in collaboration?
Topics: Another programming language as part of a computer program; “virtual machines”. The stack collection type; implementing a simple call stack. Additional practice on earlier topics.
What Will I Do? Study and extend a given program.
Rough Estimate of Workload:? Four hours? Five? Six? There actually isn’t all that much code to write, but it will take time to understand the program.
Points Available: C5 — there’s just a handful of points available for some multiple-choice questions that introduce the theme of the actual programming assignment. (For most O1 students, this chapter’s contents and assignments are completely optional. However, if you are taking Programming Studio 1 in parallel with O1, do note that these assignments are an official part of that course.)
Related Modules: RobotTribes (new), which depends on Robots.
Introduction
In this chapter, we’ll again pick up the theme of virtual robots and design some “robot tribes” that do battle with each other.
Each robot tribe has its own program code, which specifies how the tribe’s members behave. Each tribe’s code is written in a separate text file, which is not in Scala but in a custom programming language called RoboSpeak. A RoboSpeak program consists of simple commands that instruct the robots. For instance, the short RoboSpeak program below orders robots to keep walking clockwise in a square pattern:
1move # Moves the robot forward by one square.
2spin # Turns the robot clockwise.
3goto 1 # Returns to line 1 of this program.
The Scala app in module RobotTribes reads in RoboSpeak programs from text files, interprets the RoboSpeak instructions therein, stores the instructions in memory as Scala objects, and directs tribal robots accordingly. You can define new tribes simply by writing new files of RoboSpeak; you don’t need to touch the Scala code for that.
In addition to following their tribe’s RoboSpeak program, tribal robots are always looking to “hack” the members of other tribes, causing those competitors to join their tribe. If you put two tribes in the same robot world, they’ll end up fighting for survival as each tribe attempts to gain more members by converting the other. Once a tribe gets the upper hand, the weaker tribe is often eliminated completely, as even its final members defect to the winning side. You’ll see some examples of such tribal duels later.
Chapter structure
This chapter revolves around the RobotTribes module. Once again, we’re going to give you a program that almost works but is missing some crucial pieces. The chapter comprises a programming assignment in several parts, in which you’ll add those pieces.
Let’s start with an overview.
Module RobotTribes
About the Robots module
The RobotTribes module depends on the Robots module from Chapters 8.3, 8.4, and 9.1. If that’s unfamiliar, please go back there and read up on the module. You’ll need it here.
If you didn’t do the earlier assignments on Robots, do them now or use the example solutions.
RobotTribes consists of two packages:
o1.robots.tribal
expands on what’s ino1.robots
by adding tribes and tribal bots.o1.robots.gui
defines an application that is much like the originalRobotApp
but has a number of additional features that involve tribes. The app and its GUI are ready as given and we won’t discuss them in more detail here.
The table below lists the main contents of o1.robots.tribal
.
Component |
Description |
Status |
---|---|---|
class |
A subtype of the |
partial implementation given |
class |
Represents tribes of robots. Each |
ready |
trait
|
Represents individual commands in a RoboSpeak program.
Each of these objects has an |
ready |
class |
Represents a frame in a robot’s call stack. (You’ll need this class only near the end of the assignment. It’s not included in the diagram below.) |
ready |
Part 1 of 9: Getting Started with RoboSpeak
There is an introduction to the RoboSpeak language at the top of the Scaladocs for the
Tribe
class. Read the first seven sections: RoboSpeak, Action Instructions, An Introductory Example, Basic Logic, Labels, Comments and Whitespace, and Pacifist Tribes. You can ignore the rest for now.Answer the questions below. In each question, tick the all the options that correctly describe how the given RoboSpeak program makes a tribe behave. Pick the answers that describe the behavior of the given code; ignore the possibility that the acting robot itself might get “hacked” and switch tribes as a result.
Part 2 of 9: Tribes on the Move
Study the documentation and Scala code of the
TribalBot
class and the docs of theInstruction
trait.Implement the
moveBody
method inTribalBot
.Use the
nextInstruction
variable defined in the same class.The
execute
method onInstruction
objects returns a value. Make sure to use that value.moveBody
should callhack
. Include that method call in your implementation already, even though it doesn’t actually do anything yet, sincehack
’s implementation is empty.
Part 3 of 9: Let’s Experiment
Now’s a good time to try out some RoboSpeak programs.
Launch
TribalApp
and create some robots of the predefined tribes.As you experiment with the robots, also take a look at the RoboSpeak programs that define their behavior. You’ll find the code in the
tribes
folder.Notice how the robots move but don’t yet attack other tribes. (The Patroller tribe doesn’t move because it needs subprogram calls to work right.)
Try writing a short RoboSpeak program of your own:
Create a new file named
mytribe.tribe
in thetribes
folder. Enter some RoboSpeak instructions (such as move, spin, uturn, or goto) in that file.If you want a custom picture for the tribe, put a PNG image file in the same folder; name it
mytribe.png
. The subfolderextra_pics
has some sample images, but you’re not limited to them.
Submit your work, then continue to the remaining steps.
A+ presents the exercise submission form here.
Part 4 of 9: More Functionality
Return to class
Tribe
’s Scaladocs of classTribe
and read the sections Memory Slots, Radar Commands, and Hacking and Talking.Implement
determineTribe
in classTribalBot
. The class’s other methods need this method in order to tell friend from foe.Note that the parameter may refer to any sort of
RobotBrain
but not allRobotBrain
s have thetribe
variable.One approach is to use
match
to decide what to do based on the parameter’s dynamic type; see Chapter 7.2.
Implement
isFriend
.Use
determineTribe
and other ingredients from theTribalBot
class.Once you’ve implemented this method, the robots should stop when they see an enemy but they still don’t do anything to the other robot.
Implement
talk
.There is a simple implementation for it if you call other methods from
TribalBot
.
Implement
longRadar
If you first ask the robot world to list all the robots in it, one of the collection methods from Chapter 6.3 will give you a simple implementation.
Implement
directedRadar
.One approach is to call
shortRadar
andfilter
the results.
You can now try talk, enemiesnear, friendsnear, foddernear, fodderleft, score, friendsdir, and enemiesdir in your RoboSpeak programs. These commands depend on the implementations that you just wrote.
Part 5 of 9: Hacking
Implement
hack
. Use the methods inTribalBot
to help you.Try
TribalApp
again. See the tribes tussle it out. Try the different scenarios in the menu. Set up a few duels between Tigers and Guardians, for instance.Submit your work, then continue to the remaining steps.
A+ presents the exercise submission form here.
Part 6 of 9: Prepare for Subprograms
The RoboSpeak instructions callsub and return don’t work yet, but you’ll soon fix
that. But first, you should read the Subprograms section in Tribe
’s Scaladocs and answer the questions below.
In order to implement these methods, you’ll need to give each tribal bot its own call stack. The bot can use the stack to track which subprogram calls are active and where it should resume the program after a subprogram returns.
The TribalBots module comes with a Frame
class, which represents simple call-stack
frames. Take a look.
In principle, you could represent the call stack as, say, a Buffer[Frame]
. However,
we’ll instead go for a collection type that is specifically designed for representing
stack-like structures.
Part 7 of 9: Get to Know Stack
A call stack is a special case of the more generic concept of a stack (pino). A stack is a collection that follows the LIFO principle: last in, first out. The main operations of a stack are these two:
push: add a new element to the top of the stack; and
pop: remove the topmost element — the one that was added most recently.
Read the example below, which introduces you to Scala’s Stack
class. Of course, you can
also experiment with it on your own in the REPL.
import scala.collection.mutable.Stackval wordStack = Stack[String]()wordStack: Stack[String] = Stack() wordStack.push("first")res0: Stack[String] = Stack(first) wordStack.push("second")res1: Stack[String] = Stack(second, first) wordStack.push("third")res2: Stack[String] = Stack(third, second, first) wordStack.pop()res3: String = third wordStack.pop()res4: String = second wordStack.push("fourth")res5: Stack[String] = Stack(fourth, first) wordStack.pop()res6: String = fourth wordStack.pop()res7: String = first wordStack.pop()java.util.NoSuchElementException: empty collection ... wordStack.isEmptyres8: Boolean = true
Part 8 of 9: Adding a Call Stack
Class TribalBot
already has a callStack
variable with the type Stack[Frame]
:
a stack that contains frame objects. The class doesn’t use the variable for anything,
though.
Implement the methods callSubprogram
and returnFromSubprogram
. Use the callStack
variable for manipulating the stack.
You can then test your solution on the Patroller tribe or a RoboSpeak program of your own.
Part 9 of 9: The End
Consider what the RobotTribes program has in common with virtual machines (Chapter 5.4). You may also observe some similarities between RoboSpeak and machine code: look up some machine languages online and see how they handle jumps to different parts of a program.
Submit your solution.
A+ presents the exercise submission form here.
Optional Activities
Further reading: domain-specific languages
RoboSpeak can be called a domain-specific language or DSL
(täsmäkieli). Look up the term. What are DSLs used for? Is RoboSpeak
an internal DSL or an external DSL? Could we say that the musical
strings that we pass to o1.play
form a DSL?
Further reading: the collect
method
shout
uses a method named collect
. Look up collect
in the
Scala API and work out its purpose in shout
.
Challenge: Expand on RoboSpeak
Study the code in
Tribe.scala
. Notice how there is a hierarchy of subtypes belowInstruction
.Study the code in
RoboSpeakGrammar.scala
. Find out how it parses lines of RoboSpeak. As an aid, you may want to use the documentation for the Scala Parser Combinators library (alhough the examples there are unfortunately still in Scala 2).Come up with a new command for RoboSpeak and implement it. Add it to RoboSpeak’s grammar and write a corresponding subtype for
Instruction
.Add local variables to the
Frame
objects on tribal bots’ call stacks. Enable the bots to access these variables.
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 and so contributed to this ebook’s design. Thank you!
The ebook’s chapters, programming assignments, and weekly bulletins have been written in Finnish and translated into English by Juha Sorva.
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 developed by: (in alphabetical order) Riku Autio, Nikolas Drosdek, Kaisa Ek, Joonatan Honkamaa, Antti Immonen, Jaakko Kantojärvi, Niklas Kröger, Kalle Laitinen, Teemu Lehtinen, Mikael Lenander, Ilona Ma, Jaakko Nakaza, Strasdosky Otewa, Timi Seppälä, Teemu Sirkiä, Anna Valldeoriola Cardó, 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 did 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 O1Library for simple graphical programming (such as Pic
) 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+ was originally created at Aalto’s LeTech research group as a student project. The open-source project is now shepherded by the Computer Science department’s edu-tech team and hosted by the department’s IT services. Markku Riekkinen is the current lead developer; dozens of Aalto students and others have also contributed.
The A+ Courses plugin, which supports A+ and O1 in IntelliJ IDEA, is another open-source project. It has been designed and implemented by various students in collaboration with O1’s teachers.
For O1’s current teaching staff, please see Chapter 1.1.
Additional credits for this page
The notion of programmable “tribes” or “species” that fight each other on a grid comes from a programming assignment by Nick Parlante.
Onni Miettinen, Niklas Koskela, Viljami Nurminen, and Rune Pönni contributed additional commands to the RoboSpeak language and other improvements. Their work was inspired by student feedback.