Due at 11:59pm on 04/08/2015.
Download lab10.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.
By the end of this lab, you should have submitted the lab with
python3 ok --submit
. You may submit more than once before the
deadline; only the final submission will be graded.
Today, we will build a text-based adventure game. This involves writing a program that accepts text commands, interprets those commands, acts upon them, and reports the results back to the player. For example, the game will look like:
$ python3 adventure.py
Welcome to the micro-world of CS 61A! You have a midterm tomorrow,
and in hopes of doing well, you quest to seek Werdna, a mythical
TA who is rumoured to hold the key to besting the test.
You arrive in 271 Soda. The room is bright
and miserable as always. A few 61A students
are scattered among the lab computers, working
on the latest project.
Exits:
out - Hearst Ave.
adventure> help
There are 7 possible operators
look
go
take
give
examine
ask
help
adventure> look
You look around. You see
A rubber ducky
adventure> take rubber ducky
You take the rubber ducky
adventure> examine rubber ducky
Hm. It's yellow and it's rubber and it squeaks. Fascinating.
adventure> go out
You leave 2nd floor Soda though the exit all the cool kids use
You find yourself on the sidewalk of Hearst Ave.
Exits:
north - 271 Soda
west - Euclid Ave.
south - Campus
At a high level, this is exactly what an interpeter does.
Why are we doing this? Because traditionally, all the interpreter based exercises in 61A have either been "write a calculator" OR "write an programming language interpreter." Hopefully this livens things up.
See this article for more information about text based adventure games. Kn0w y0ur r00ts, y0.
An interpreter is a program that allows you to interact with the computer in a certain language. It understands the expressions that you type in through that language, and perform the corresponding actions in some way, usually using an underlying language.
For example, you saw a simple calculator language in lecture that is written in Python. In Project 4, you will write a Scheme interpreter in Python as well. Python itself is written in the C programming language. The computer itself uses hardware to interpret machine code, a series of ones and zeros that represent basic operations like adding numbers, loading information from memory, etc.
When you talk about an interpreter, there are two languages that are at work:
Note that the underlying language need not be different from the implemented language. In the previous incarnation of 61A, students were introduced to a Scheme interpreter written in Scheme. CS61A in Summer 2012 covered a Python interpreter written in Python! This idea is called Metacircular Evaluation.
Each interpreter has five parts:
adv_parse
in the line
tokens = line.split()
.Here's how all the pieces fit together:
____________________________________________
| |
|_____ _________ __________ ______|
User Input -->|Lexer|--> | Parser |--> |Evaluator|-->|Print|--> Output
|_____| |________| |_________| |_____|
| __^_v____ |
^ |Apply | v
^ REPL |_________| v
|____________________________________________|
Now let's explore how these parts work together in an adventure game!
We can implement our adventure language in Python3 by completing
the interpreter(/game engine) in adventure.py
.
First, here's an explanation of the the two files we were given:
adventure.py
: This file includes the skeleton code of the game
engine that you will complete. There are also classes (Person, Place,
Thing) that model objects in the game. Your engine and the game data
uses these.cs61a_world.py
: All the game data that makes things interesting is
in this file. It creates Persons, Places, and Things that make up
the adventure world.Now, let's look at the base code in adventure.py
. There's a lot of
code to take in at once, but don't freeze up! We'll walk through and
implement everything, function by function.
adventure
: our REPL. This function reads player input, calls
adv_parse
to get an expression out (represented as a tuple), and
then calls adv_eval
to perform the actions. It prints the results
accordingly. Then it makes a recursive call to itself in order to
take in the next command.The player is represented as a Person
object. The interpreter will
allow the player to move the Person
through the game and interact
with the various aspects of the world.
You can try to run it by doing
>>> python3 adventure.py
However it's missing functionality, so nothing will really work.
Let's fix that, shall we?
Note: When you want to test manually, make sure you're in Python. Here's how:
$ python3 -i adventure.py adventure> # Type ctrl-D >>> adv_parse('look') # Now you can call adv_parse
Remember that when you run
adventure.py
, you are talking to the adventure program, which will evaluate your input in terms of the adventure code. In order to talk to Python again, you kill the adventure program by doing Ctrl-d.If the above didn't work (Ctrl-d takes you out of the entire interpreter), try
$ python3 >>> from adventure import * >>> from cs61a_world import * >>> adv_parse('look')
OK tests can still be run the same way
$ python3 ok -q adv_parse
Let's start things off by implementing parsing. We do this in
adv_parse
— our Parser. Since our game language is simple, we're
going to do the lexical (turn line into tokens) and syntactic analyses
(turn tokens into expression) all in one function. Our expression
representation is a tuple (No ADT here). Here is the basic syntax of a
command:
[operator] [operand]
When we encounter a command that matches this syntax, return:
([operator], [operand])
Another common syntax is:
[operator]
The corresponding expression is:
([operator], '')
For example,
adv_parse('take cookie')
returns ('take', 'cookie')
'take'
is the operator'cookie'
is the operandadv_parse('look')
returns ('look', '')
'look'
is the operator''
is the operandadv_parse('take rubber ducky')
returns ('take', 'rubber ducky')
'take'
is the operator'rubber ducky'
is the operandMost of our operators follow this syntax. There are two commands that require a different handling:
ask
: when you encounter a line like 'ask Leonard for sushi', return
('ask', 'Leonard', 'sushi')
give
: when you encounter a line like 'give a cookie to Andrew',
return ('give', 'a cookie', 'Andrew')
Use OK to test your solution to adv_parse
:
python3 ok -q adv_parse
Hint: consider the following example:
>>> x = 'take rubber ducky'
>>> y = x.split()
>>> y
['take', 'rubber', 'ducky']
>>> y.pop(0)
'take'
>>> y
['rubber', 'ducky']
>>> ' '.join(y[0:]) # Google 'python3 string join'
'rubber ducky'
>>> # You may also find list slicing helpful
Note: This lab is heavy on the concepts, so the big picture is important.
We therefore tried to make the code simpler to write to help with that.
We suggest that you actively discuss the interpretation process and how Scheme's
additional features (e.g. define
) might change the way we write certain parts of the
interpreter.
adv_eval
: our Evaluator. We want to handle all kinds of expressions.
The rules are:
adventure.py
can we use to evaluate them?
Then, apply the operator to the operand by calling adv_apply
.give
function (line
109). You may just call the give
function directly in this case.
What is give
's domain?ask
function (line
122). What is ask
's domain?For example:
>>> from adventure import *
>>> from cs61a_world import *
>>> adv_parse('look')
>>> Place.current = SodaHall
>>> adv_eval(adv_parse('take rubber ducky'))
'Player 1 takes the rubber ducky'
>>> Place.current = WerdnasHouse
>>> adv_eval(adv_parse('give rubber ducky to Werdna'))
'Werdna takes the rubber ducky'
Note: You won't be able to test this until you finish Question 3.
adv_eval
is truly where the action is. It takes the expression
that is passed in and performs the correct action based on the rules
of our game language.
Hint: Use recursion and also the functions defined right under adv_eval
(adv_apply
, look
, give
, take
, etc.).
ask
and give
are Special Forms, because they do not follow the
[operator] [operand]
pattern. As you can see, we write separate rules for
them in adv_eval
to account for this difference. When evaluating Scheme
expressions, you will also have to handle if
, define
, and other forms
differently because not all operands are evaluated in those expressions.
adv_apply
: our apply. Handles the application of the normal commands
Since our commands are simple, adv_apply
just needs to apply the
operator to the operand. There are no calls to adv_eval
in Adventure.
The point of apply becomes more apparent with more complicated languages. (Why? Which features of programming languages are missing in this adventure game language?) However the princple holds—apply takes care of the function calls that are evaluated without any special rules.
Hint: adv_apply
is really straightfoward. Don't overthink it.
Use OK to test your solution to adv_eval
and adv_apply
:
python3 ok -q adv_eval
AT THIS POINT YOU CAN PLAY THE GAME! :D
One thing that would be useful is to figure out what's in our inventory. For example:
adventure> take rubber ducky
Player 1 takes the rubber ducky
adventure> stuff
You look through your stuff... you see
rubber ducky - Hm. It's yellow and it's rubber and it squeaks. Fascinating.
-- End of stuff --
Add code to take care of this. What needs to be modified?
Do adv_eval
and/or adv_apply
need to be modified at all?
Hint: You will find it helpful to use examine
(line 133).
Now that you've implemented this interpreter, you can play the game!
python3 adventure.py
Happy Questing!
Hope this lab was fun. :)
Since the game is simple, some parts of the lab are toy-ish. However, the game is still strong and robust enough to be extended; feel free to add more places, people and things! :P This also speaks to how powerful Python is as a language, to allow us to create a full game in relatively short time! (The original TA might have hacked this game together in a night...) You are also encouraged to create your own world and tell your own story.
Lab 10 Takeaways:
adv_eval
and adv_apply
: our simple game
language doesn't need it. However, think about what why mutual recursion
is necessary in Scheme.In Project 4, you will implement a Scheme interpreter in Python.