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 11.3: Robots That Compete
About This Page
Questions Answered: How can a program operate on other programs? How could groups of 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? There actually isn’t all that much code to write, but it will take time to understand the program.
Points Available: C95.
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:
1 2 3
move # Moves the robot forward by one square. spin # Turns the robot clockwise. goto 1 # Returns to line 1 of this program.
The Scala app in project 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. As a consequence, 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.
This chapter revolves around the RobotTribes project. Once again, we’re going to give you a version of the project 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.
About the Robots project
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.tribalexpands on what’s in
o1.robotsby adding tribes and tribal bots.
o1.robots.guidefines an application that is much like the original
RobotAppbut 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
||A subclass of the Robots project’s
||partial implementation given|
||Represents tribes of robots. Each
||Represents individual commands in a RoboSpeak program.
Each of these objects has an
||Represents call stacks. Each robot that runs a RoboSpeak program uses such a stack to track active subprogram calls. (You’ll need this class only near the end of the assignment. It’s not included in the diagram below.)||almost completely missing|
||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
Tribeclass. 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.
Part 2 of 9: Tribes on the Move
- Study the documentation and Scala code of the
TribalBotclass and the docs of the
- Implement the
- Use the
nextInstructionvariable defined in the same class.
Instructionobjects returns a value. Make sure to use that value.
hack. Include that method call in your implementation already, even though it doesn’t actually do anything yet, since
hack’s implementation is empty.
- Use the
Part 3 of 9: Let’s Experiment
Now’s a good time to try out some RoboSpeak programs.
TribalAppand 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
- Notice how the robots move but don’t yet attack other tribes. (The Patrolman tribe doesn’t move because it needs subprogram calls to work right.)
- 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
- Try writing a short RoboSpeak program of your own:
- Create a new file with the
tribesuffix in the
tribesfolder. Enter some RoboSpeak instructions (such as move, spin, uturn, or goto) in that file and save it.
- If you want a custom picture for the tribe, put
a PNG image file in the same folder; name it after
your tribe. The subfolder
extra_picshas some sample images, but you’re not limited them.
- Create a new file with the
Part 4 of 9: More Functionality
- Return to class
Tribe’s Scaladocs of class
Tribeand read the sections Using Memory Slots, Radar Commands, and Hacking and Talking.
TribalBot. The class’s other methods need this method in order to tell friend from foe.
- Notice that the parameter may refer to any
RobotBrainbut not all
RobotBrains have the
- One way to implement this method is to use
matchfor making a decision based on the parameter’s dynamic type; see Chapter 7.2._.
- Notice that the parameter may refer to any sort of
determineTribeand other ingredients from the
- 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.
- If you call other methods from
talk, the method is quite simple to implement.
- If you first ask the robot world to list all the robots in it, one of the collection methods from Chapter 6.2 will give you a very simple implementation for
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
hack. Use the methods in
TribalBotto help you.
TribalAppagain. See the tribes tussle it out. Try the different scenarios in the menu. Set up a few duels between Tigers and Guardians, for instance.
Part 6 of 9: Preparing for Subprograms
The RoboSpeak instructions callsub and return don’t work yet, but you’ll soon fix
that. First, though, 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 projects comes with a
Frame class, which represents very 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
Part 7 of 9: The
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 two main operations of a stack are:
- push: add a new element to the top of the stack; and
- pop: remove the topmost element — the one that was added most recently.
The Scaladocs in RobotTribes describe a
Stack class with these methods; read the
specification. There’s little in the way of
implementation yet, though; see
Stack. Use a private variable that refers to an auxiliary collection that
stores the stack’s contents. That auxiliary collection could be a buffer or a vector,
if you prefer, but we recommend that you consider the
List type described below.
List is a widely used class that works well for this purpose and is a good addition
to your arsenal of collections in general.
A short introduction to
A list (lista) is an immutable collection and, in that, resembles a vector. Because of how they are implemented, lists are efficient if you need to manipulate only the head of the collection or if you need to traverse the elements only in order from first to last. On the other hand, a list is probably a poor choice if you intend to access arbitrary elements anywhere in the collection (by their index, for instance).
In the Scala API, lists are available as
Lists work much like other collections. Here’s one way to create a new list:
val emptyList = List[Int]()emptyList: List[Int] = List() var wordList = List("first", "second", "third")wordList: List[String] = List(first, second, third)
The familiar methods are available:
wordList.sizeres0: Int = 3 wordList.tailres1: List[String] = List(second, third) wordList.map( _.length )res2: List[Int] = List(3, 4, 6)
:: operator is specific to lists. It forms a new list that has
one additional element and is thus equivalent to the stream operator
#:: (Chapter 7.1) and the generic collection operator
+: (Chapter 4.1).
wordList = "first-er" :: wordListwordList: List[String] = List(first-er, first, second, third)
wordListvariable’s old value with a reference to a new, longer list. You may find this notion useful as you implement
It’s easy to implement a stack using a list: we’ll place the top element at the head of the list and the bottom element at the rear end. All additions and removals then affect the top of the stack, which is at the front of the list.
Lists are especially common in functional programming. Many Scala programmers use them a lot. They will also play a significant part in Programming 2.
Part 8 of 9: Adding a Call Stack
TribalBot already has a
callStack variable with the type
stack that contains frame objects. The class doesn’t use the variable for anything,
Implement the methods
returnFromSubprogram. Use the
variable for manipulating the stack.
You can then test your solution on the Patrolman tribe or a RoboSpeak program of your own.
Part 9 of 9: The End
- Consider what the RobotTribes project has in common with virtual machines (Chapter 5.2). 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 to the entire assignment.
A+ presents the exercise submission form here.
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
shout uses a method named
collect. Look up
collect in the
Scala API and work out its purpose in
Challenge: extend RoboSpeak
- Study the code in
Tribe.scala. Find out how it parses lines of RoboSpeak and how there’s a hierarchy of subtypes below
Instruction. As an aid, you may want to use the book Programming in Scala, Third Edition, which is introduced on the Books and Other Resources page. Chapter 33 of the book, Combinator Parsing, is particularly relevant.
- Come up with a new command for RoboSpeak and implement it.
Add it to RoboSpeak’s grammar and write a corresponding subtype
- Add local variables to the
Frameobjects on tribal bots’ call stacks. Enable the bots to access these variables.
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.
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 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 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.