Lab 10: Interpreters

Due at 11:59pm on 04/08/2015.

Starter Files

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.

Submission

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.

Table of Contents

Introduction

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.

Interpreters

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:

  1. The language being interpreted. We also call this the language being implemented. We use Python to implement calc and Scheme. The main Python distribution (known as CPython) is implemented in C.
  2. The underlying implementation language. From above, Python, Python, and C respectively.

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:

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!

Adventure

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:

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.

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?

Question 1

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,

Most of our operators follow this syntax. There are two commands that require a different handling:

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.

Question 2

adv_eval: our Evaluator. We want to handle all kinds of expressions.

The rules are:

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.

Question 3

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

Question 4

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).

Question 5

Now that you've implemented this interpreter, you can play the game!

python3 adventure.py

Happy Questing!

Conclusion

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:

In Project 4, you will implement a Scheme interpreter in Python.