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

Starter Files

Download lab12.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.

To receive credit for this lab, you must complete questions 1, 2, 3, and 4 in interpreter.py

Introduction

Today, we will build an interpreter for tic-tac-toe. This involves writing a program that accepts text commands, interprets those commands, and places pieces based on those commands.

For example, the game might look like:

$ python3 interpreter.py

Welcome to TicTacToe. Player0 is 'X', Player1 is 'O'. Please use Capitals.
Player0> X 1
   | X |  
-----------
   |   |  
-----------
   |   |  
O must place a piece.
Player1> O 3
   | X |  
-----------
 O |   |  
-----------
   |   |  
X must place a piece.
Player0> X 7
   | X |  
-----------
 O |   |  
-----------
   | X |  
O must place a piece.

Note: Our implementation of tic-tac-toe enumerates the spaces from 0 to 8, starting in the top left corner and moving right until we hit the end of the row, at which point we repeat the same process at the next row.

At a high level, this is exactly what an interpeter does.

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.

When you talk about an interpreter, there are two languages that are at work:

1. The language being interpreted, or the language being implemented.
2. The underlying implementation language, or the language used to implement the language being interpreted.

For example, the language being interpreted in our Scheme interpreter is Scheme, while the underlying implementation language is Python.

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:

• Read-Eval-Print-Loop (REPL for short) - the loop that waits for user input, passes it to the parser and then the evaluator, and then prints out the result.
• Lexer - first operation called by REPL. The lexer turns the user input string into atomic pieces (tokens) that are like "words" of the implemented language. In tic-tac-toe, this part is combined with the parser in in_game_parse and end_game_parse in the line tokens = line.split().
• Parser - takes the tokens and organizes them in a data structure that the underlying language understands. For our adventure game, holding the tokens in a list is enough. For Scheme, we use deep linked lists (linked lists whose elements can also be linked lists) to represent hierarchy and recursion.
• Evaluator - takes in the aforementioned sequence and interprets it accordingly to the rules of the language. The evaluator may call apply to apply an evaluated operator to its evaluated operands.
• Apply - applies the operator to the argument values. Apply may call the evaluator to do more work... this is possibly the most important example of Mutual Recursion. Ever.

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 our tic-tac-toe game!

Tic-Tac-Toe

We can implement our game interpreter in Python3 by completing the interpreter(/game engine) in interpreter.py.

First, here's an explanation of the the two files we were given:

• interpreter.py: This file includes the skeleton code of the interpreter that we are going to build.
• tictactoe.py: All of the implementation of the tic-tac-toe game itself is in this file. It has already been completely implemented so you don't need to worry about that! However, it is important for you to understand how the game runs.

Now, let's look at the base code in interpreter.py. We'll walk through and implement everything, function by function.

• new_game: our REPL. This function reads player input, calls our two parse functions (in_game_parse and end_game_parse) to get an expression out (represented as a tuple), and then calls ttc_eval to perform the actions. It prints the results accordingly. Then it loops and waits for a new command. This has already been implemented for you.

You can try to run it by doing

$ python3 interpreter.py

However it's missing functionality, so nothing will really work.

Let's fix that, shall we?

Question 1: Placing pieces

Note: When you want to test manually, make sure you're in Python. Here's how:

$ python3 -i interpreter.py
Player0>                 # Press ctrl-D
>>> in_game_parse('X 7')      # Now you can call in_game_parse

Remember that when you run interpreter.py, you are talking to the tic-tac-toe program, which will evaluate your input in terms of the tic-tac-toe code. In order to talk to Python again, you kill the game by doing Ctrl-d.

If the above didn't work (Ctrl-d takes you out of the entire interpreter), try

$ python3
>>> from interpreter import *
>>> in_game_parse('X 7')

OK tests can still be run the same way

$ python3 ok -q in_game_parse

Let's start things off by implementing parsing. We do this using two functions, the first of which is:

• in_game_parse: We call this function on input we received while the game is ongoing. The commands received in the game can correspond to either placing a new piece or resetting the current game.

Since our game language is simple, we're going to do the lexical (turn line into tokens by using line.split) and syntactic analyses (turn tokens into an expression) all in one function. Our expression representation is a list (No ADT here). All expressions in our interpreter take the form of

[[operator], [operand]]

or

[[operator]]

Both of our parsers take in a line of text and return a expression of one of the above forms. There are two possible expressions that in_game_parse could return:

['Place', [piece, space]]

and

['Reset']

In these expressions, 'Place' and 'Reset' are the operators and the list [piece,space] is the operand for 'Place'.

Implement in_game_parse according to the rules given in the doctest.

def in_game_parse(line):
    """ Parse takes in a command from the user and returns an expression.
    If the first word of the command is 'Reset', the returned expression
    should be the 'Reset' command. Otherwise, the line corresponds to a
    'Place' expression.  In 'Place' expressions, the first symbol (X or O)
    encountered is the piece placed.  The first number 0 to 8 after finding
    the piece is the space where it is to be placed.

    Be sure to change the space number from a string to an integer.

    >>> in_game_parse('Reset the board, please')
    ['Reset']
    >>> in_game_parse('Reset the board X 1')
    ['Reset']
    >>> in_game_parse('Place X on 1')
    ['Place', ['X', 1]]
    >>> in_game_parse('I want O to be placed on 6')
    ['Place', ['O', 6]]
    >>> in_game_parse('Please put X on 8')
    ['Place', ['X', 8]]
    >>> in_game_parse('Would you put O on 2')
    ['Place', ['O', 2]]
    >>> in_game_parse('7 X 5')
    ['Place', ['X', 5]]
    >>> in_game_parse('X O 3')
    ['Place', ['X', 3]]
    >>> in_game_parse('O 4 3')
    ['Place', ['O', 4]]
    >>> in_game_parse('This is random gibberish')
    Traceback (most recent call last):
    SyntaxError: Symbol or Place is missing
    """
    tokens = line.split()
    if not tokens:
        raise SyntaxError('No Command Given')
    "*** YOUR CODE HERE ***"
    if tokens[0] == 'Reset':
        return ['Reset']
    exp = ['Place', ['Put piece here', 'Put space here']]
    symbols = ['X', 'O']
    places = [str(i) for i in range(9)]

    while tokens:
        token = tokens.pop(0)
        "*** YOUR CODE HERE ***"
        if token in symbols and exp[1][0] not in symbols:
            exp[1][0] = token
        elif token in places and exp[1][0] in symbols:
            exp[1][1] = int(token)
            return exp
    raise SyntaxError("Symbol or Place is missing")

Toggle Solution

Use OK to test your code:

python3 ok -q in_game_parse

Question 2: Starting a new game

The other parsing function that we use is:

• end_game_parse: This function is called on input we received after the game is over, specifically in response to the question "Would you like to play another game?". We use this function to determine whether or not the player answered yes or no.

This parsing function can return two commands:

['New']

and

['End']

It can also return None if it reads through the line and doesn't find a command.

Implement end_game_parse according to the rules given in the doctest.

def end_game_parse(line):
    """ Takes in input from a user after the game has ended.
    The line is a response to the question "Would you like to play another game?"
    This input can correspond to a 'New' expression, an 'End' expression, or 
    None if no expression was found.

    To determine the expression, we look at the first letter of each word in the line.
    If the first letter of a word is 'y' or 'Y', the command is 'New'.
    If the first letter of a word is 'n' or 'N', the command is 'End'.
    If both 'y' and 'n' appear in the first letters of words in the input, we use whichever letter came first.

    >>> end_game_parse("yes")
    ['New']
    >>> end_game_parse("no")
    ['End']
    >>> end_game_parse("I do not like this game.") # 'not' begins with 'n'
    ['End']
    >>> end_game_parse("I could play against you all day") # 'you' begins with 'y'
    ['New']
    >>> end_game_parse("Purple snacks never yaks")
    ['End']
    >>> end_game_parse("There are zero valid commands in this line")
    """
    tokens = line.split()
    while tokens:
        token = tokens.pop(0)
        "*** YOUR CODE HERE ***"
        if 'y' == token[0]:
            return ['New']
        elif 'n' == token[0]:
            return ['End']
    return None

Toggle Solution

Use OK to test your code:

python3 ok -q end_game_parse

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 3: Applying operators

ttc_apply: Handles the application of the normal commands Since our commands are simple, ttc_apply just needs to apply the operator to the operand.

The point of apply becomes more apparent with more complicated languages. (Why? Which features of programming languages are missing in this tic-tac-toe game language?) However the princple holds—apply takes care of the function calls that are evaluated without any special rules.

Hint: ttc_apply is really straightfoward. Don't overthink it.

def ttc_apply(operator, operand):
    """Applies the operator on the given operand.

    (This is a very simple function.)

    >>> ttc_apply(lambda x: x*x, 7)
    49
    >>> ttc_apply(lambda y: True, False)
    True
    """
    "*** YOUR CODE HERE ***"
    return operator(operand)

Toggle Solution

Use OK to test your code:

python3 ok -q ttc_apply

Question 4: Evaluating commands

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

The rule is:

• Determine the operator that corresponds to each expression. Then, apply the operator to the operand by calling ttc_apply.

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

def ttc_eval(board, exp):
    """ Takes in the game board and the expression returned from a parse function
    and evaluates the expression given.

    Be sure to call ttc_apply whenever you want to call a function.

    If the command is 'Reset' or 'New', we begin a new game.  Remember that new_game
    takes in an intro message.  (We have no restrictions on what the message can be.)
    If the command is 'Place', we want to place a piece on the given board.
    (Look at the tictactoe.py file to figure out how to do this)
    If the command is 'End', we do nothing.

    >>> b = Board(False) # Create a board that doesn't print unnecessarily
    >>> line = "Place X at 7"
    >>> exp = in_game_parse(line)
    >>> ttc_eval(b, exp)
    'X has been placed in space 7'
    >>> ttc_eval(b, in_game_parse("O in for 6"))
    'O has been placed in space 6'
    """
    if exp[0] == 'Reset':
        return ttc_apply(new_game, "The game has been reset!")
    elif exp[0] == 'Place':
        return ttc_apply(board.place_piece,exp[1])
    elif exp[0] == 'New':
        return ttc_apply(new_game, "New game!")
    elif exp[0] == 'End':
        return None

Toggle Solution

Use OK to test your code:

python3 ok -q ttc_eval

AT THIS POINT YOU CAN PLAY THE GAME! :D

Conclusion

Hope this lab was fun. :)

Lab Takeaways:

• Interpreters allow us to directly interact with the computer through a language.
• Interpreters are made of a REPL, a parser, an evaluator, and an apply'er. They interact with each other in specific ways.
• There are two languages when talking about an interpreter: the underlying language vs language being implemented.
• Special forms have their own rules for being evaluted. They don't get handled in apply.
• In interpreter.py, the tic-tac-toe game language is interpreted by the Python program. You talk to the computer in tic-tac-toe talk which gets translated to actions in the underlying Python language.
• No tree recursion between 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.

There are no extra questions this lab. Study for the midterm!