14
\$\begingroup\$

Having played Human Resource Machine for over a day, and wanting to improve my interpreting / tokenizer skills, I made a Human Resource Machine interpreter.


For those that do not know, so if you do you can skip this. Human Resource Machine is a game where you're an 'instruction follower' employee. You are given tasks to complete, things such as multiplying numbers, returning the smaller word, counting from a number to zero. To complete these task you create a program constructed from a fairly small list of functions, tiles on the floor and an input and output queue. To give an example the first level you are given two commands 'inbox' and 'outbox', and the task is to pass three boxes with data in them to the output. In the second level you are introduced to the 'jump' command which is the same as using labels and goto in languages that support it, allowing you to pass any number of input to the output. There are then:

  • 'copyfrom' and 'copyto' that copy to or from the tiles on the floor from/to your hand.
  • 'add' and 'sub' that apply the respective function on the box in you hand and the tile on the floor. If your hand is 5, and you sub a tile with the value 4, you'll result in having 1 in your hand.
  • 'bump+' and 'bump-' which increase and decrease the value in that space by one, and add the item to your hand. And,
  • 'jump if zero' and 'jump if negative' which only jump if the value in your hand is zero or negative.

Sometimes levels can also start with boxes already in tiles. All of this is how your average Joe would interact with the game, but this one heavily abused the copy ability in the game that gives you output such as:

-- HUMAN RESOURCE MACHINE PROGRAM --

a:
    INBOX   
    COPYTO   0
b:
c:
    OUTBOX  
    COPYFROM 0
    JUMPZ    a
    JUMPN    d
    BUMPDN   0
    JUMP     b
d:
    BUMPUP   0
    JUMP     c

This takes a number and adds or minuses one, outputs it, and loops until the number is zero. Before I bore you there's one other part of the language, if the argument is wrapped in [], say COPYTO [10] your instruction follower will COPYTO the index of what tile 10 has, so if it's 6 it's the equivalent to COPYTO 6.


Based of this language I created my own interpreter. With the following implementation:

HRM class:

  • HRM functions wrapped in hrm_fn are passed the type of input they take.
  • hrm_fn wraps the types, function and arguments to create an argument-less function.
  • hrm_fn also does additional type checks with the above information.

Tokenizer:

  • Passed a string that is split into the form command, *args.
  • Checks the command is one we've implemented, and does a rough check on the args.

HRMBox class:

  • Holds both characters and numbers.
  • Has some sugar to make it act like a number. It implements enough for what it's needed for, but wouldn't be enough for a proper number class.

HRMType family:

  • Specifies the type passed to the function, when passed to hrm_fn.
  • This also changes the input so when passed to the HRM class.
  • Pointer is a special one that wraps the normal types and allows you to use HRM's [] syntax.

I have unit tests that contain spoilers for some of the levels. And so, if you want a spoiler-free experience, stay away from the test_programs folder. My program should work correctly with most HRM programs. However, I haven't fully implemented the COMMENT command, so I'd steer clear of it. This means my program may not work with programs that put comments on the tiles, which I'm fine with.

import re
import string


class HRMException(Exception):
    pass


class TileError(HRMException):
    def __init__(self, data):
        super().__init__(
            "Bad tile address! "
            "Tile with address {} does not exist! "
            "Where do you think you're going?"
            .format(data))


class OutOfBoundsError(HRMException):
    def __init__(self):
        super().__init__(
            "Overflow! "
            "Each data unit is restricted to values between -999 and 999. "
            "That should be enough for anybody.")


class OperandsError(HRMException):
    def __init__(self, operator):
        super().__init__(
            "You can't {0} with mixed operands! "
            "{0}'ing between one letter and one number is invalid. "
            "Only nice respectable pairs of two letters or two numbers are allowed.! "
            .format(operator))


class HRMType:
    letters = set()
    def get(self, *_):
        return self.data


class Empty(HRMType):
    def __init__(self, data):
        self.data = data


class Number(HRMType):
    letters = set(string.digits)
    def __init__(self, data):
        self.data = int(data)


class Word(HRMType):
    letters = set(string.ascii_letters)
    def __init__(self, data):
        self.data = str(data)


class Pointer:
    letters = set('[]')
    def __init__(self, other):
        self.other = other
        self.letters |= other.letters
        self.pointer = False
        self.data = None

    def __call__(self, data):
        data = str(data)
        self.pointer = False
        if data[0] == '[':
            if data[-1] != ']':
                raise HRMException("Mismatched parenths")
            self.pointer = True
            data = data[1:-1]
        self.data = self.other(data).get()
        return self

    def get(self, hrm):
        if self.pointer:
            d = hrm[self.data]
            return d.data if isinstance(d, HRMBox) else d
        return self.data


class HRMBox:
    def __init__(self, data):
        if isinstance(data, HRMBox):
            self.word = data.word
            self.data = data.data
            return
        self.word = False
        data = str(data)
        if set(data) <= set(string.digits + '-'):
            data = int(data)
        elif not len(data):
            raise ValueError("HRMBox needs to be at least a size of one.")
        elif set(data) <= set(string.ascii_letters):
            self.word = True
            data = ord(data[0].upper()) - 64
        else:
            raise ValueError("HRMBox can only be numbers and digits.")
        self.data = data

    @property
    def data(self):
        return self._data

    @data.setter
    def data(self, value):
        if value >= 1000 or value <= -1000:
            raise OutOfBoundsError()
        self._data = value

    @property
    def item(self):
        if self.word:
            return chr(self.data + 64)
        return self.data

    def __int__(self):
        if self.word:
            pass
        return self.data

    def __index__(self):
        return self.__int__()

    def __repr__(self):
        return 'HRMBox({})'.format(self.item)

    def __sub__(self, other):
        if not isinstance(other, HRMBox):
            other = HRMBox(other)
        if self.word is not other.word:
            raise OperandsError('')
        return HRMBox(self.data - other.data)

    def __add__(self, other):
        if not isinstance(other, HRMBox):
            other = HRMBox(other)
        if self.word is not other.word:
            raise OperandsError('')
        return HRMBox(self.data + other.data)

    def __eq__(self, other):
        if not isinstance(other, HRMBox):
            other = HRMBox(other)
        return self.data == other.data

    def __lt__(self, other):
        if not isinstance(other, HRMBox):
            other = HRMBox(other)
        return self.data < other.data


COMMANDS = {}
def hrm_fn(*types):
    def wrap(fn):
        def call(self, *args):
            def data():
                fn(self, *[t(a).get(self) for t, a in zip(types, args)])
            return data
        call.letters = [t.letters for t in types]
        COMMANDS[fn.__name__.upper()[1:]] = call
        return call
    return wrap


class HRM:
    def __init__(self, program, tiles=0, tile_defaults=None):
        if tile_defaults is None:
            tile_defaults = {}
        self.tokens = list(remove_invalid_tokens(tokenise(program)))
        self.labels = {
            places[0]: i
            for i, (command, places) in enumerate(self.tokens)
            if command == 'LABEL'
        }
        self.tiles = [None for _ in range(tiles)]
        for tile, value in tile_defaults.items():
            self.tiles[tile] = HRMBox(value)
        self.hand = None

    @property
    def hand(self):
        return self._hand

    @hand.setter
    def hand(self, value):
        if value is None:
            self._hand = HRMBox(value)
        self._hand = value

    def __getitem__(self, index):
        try:
            return self.tiles[index]
        except IndexError:
            raise MemoryError(index)

    def __setitem__(self, index, value):
        try:
            self.tiles[index] = HRMBox(value)
        except IndexError:
            raise MemoryError(index)

    def __call__(self, input):
        self.input = iter(input)
        self.output = []
        self.command = 0
        self.hand = None
        commands = [
            COMMANDS[command](self, *value)
            for command, value in self.tokens
        ]
        while True:
            try:
                commands[self.command]()
            except IndexError: # No more commands
                break
            except StopIteration: # No more input
                break
            self.command += 1
        return self.output

    @hrm_fn(Empty)
    def _inbox(self):
        self.hand = HRMBox(next(self.input))

    @hrm_fn(Empty)
    def _outbox(self):
        self.output.append(self.hand.item)
        self.hand = None

    @hrm_fn(Pointer(Number))
    def _copyfrom(self, index):
        self.hand = self[index]

    @hrm_fn(Pointer(Number))
    def _copyto(self, index):
        self[index] = self.hand

    @hrm_fn(Pointer(Number))
    def _add(self, index):
        self.hand += self[index]

    @hrm_fn(Pointer(Number))
    def _sub(self, index):
        self.hand -= self[index]

    @hrm_fn(Pointer(Number))
    def _bumpup(self, index):
        self[index] += 1
        self.hand = self[index]

    @hrm_fn(Pointer(Number))
    def _bumpdn(self, index):
        self[index] -= 1
        self.hand = self[index]

    @hrm_fn(Word)
    def _jump(self, label):
        self.command = self.labels[label]

    @hrm_fn(Word)
    def _jumpz(self, label):
        if self.hand == 0:
            self.command = self.labels[label]

    @hrm_fn(Word)
    def _jumpn(self, label):
        if self.hand < 0:
            self.command = self.labels[label]

    @hrm_fn(Number)
    def _comment(self, comment):
        pass

    @hrm_fn(Word)
    def _label(self, label):
        pass


COMMAND_TYPES = {command: fn.letters for command, fn in COMMANDS.items()}
def tokenise(hrm_string):
    for line in hrm_string.split('\n'):
        line = line.strip()
        if re.match('--', line) is not None:
            continue
        label = re.match('(\w+):', line)
        if label is not None:
            yield 'LABEL', label.group(1)
            continue
        expression = line.split()
        if expression and all(re.match('\w+|\[\w+\]$', e) for e in expression):
            yield expression
            continue


def remove_invalid_tokens(tokens):
    for command, *values in tokens:
        command = command.upper()
        command_types = COMMAND_TYPES.get(command, None)
        if (command_types is not None and
            all(set(v) <= c for c, v in zip(command_types, values))):
            yield command, values

And an example of how to use this is:

import instruction_follower as hrm

program = """
loop:
    INBOX
    COPYTO 0
    INBOX
    ADD 0
    OUTBOX
    JUMP loop
"""

hrm_program = hrm.HRM(program, 1)
print(hrm_program([1, 2]))
print(hrm_program(['A', 'B']))

Which correctly outputs:

[3]
[3]

I'm fine with a review of anything, but I'm mostly concerned with more a design review, as I think the design is starting to become a little, wrong. I'm more than happy to be told changes to improve readability or to improve the code too.

And to note again, there are a few minor features missing, such as COMMENT may not work, and OperandsError doesn't display the operand.

\$\endgroup\$
7
+400
\$\begingroup\$

I agree with your feeling about the design. I wouldn't necessarily say it's wrong, but it feels a little heavy for the task at hand.

Firstly, you have quite a lot of code that's slightly tricky, or "strange" as SuperBiasedMan said. As his answer also said, we could benefit a lot from some comments explaining what your methods and classes do, especially in places where the intent of the code may not immediately obvious to somebody reading it for the first time.

With no disrespect intended, can I make a guess that you're coming to Python from a background in a statically-typed, strongly object-oriented language like Java? I really like Python as a language, and one reason is that you can get a lot done with a minimum of fuss and boilerplate. I think it's a good choice for this task, but personally, I probably wouldn't use so many classes. Plain old lists, dictionaries, ints and strings will take you a long way most cases.

The language you're interpreting seems to be a very simple assembly language. Your interpreter is essentially a mapper from textual commands and arguments to simple operations. Sounds like your input is guaranteed to be valid, since it's copy and pasted from the game UI. I understand you may be trying to make a more complete interpreter with strict checking as an exercise, but why not start more simply?

With that in mind, how about something like this as a starting point? I tested it on your simple example, but haven't run it on all your unit tests. I may be missing some aspects of the game or language, and it doesn't have detailed input checking, but it's a basic working interpreter using 100 lines of code rather than 300.

import sys

class Instruction:
  def __init__(self, instr, arg=None):
    self.instr = instr
    self.arg = arg


def parse(hr_program_lines):
  instructions = []    # list of instructions
  labels = {}          # map labels to instruction indexes
  for line in hr_program_lines:
    if line.startswith((' ', '\t')):
      split = line.strip().split()
      instr = Instruction(split[0], split[1] if len(split) > 1 else None)
      instructions.append(instr)
    else:
      label = line.strip().rstrip(':')
      # point the label at the next instruction to be parsed
      labels[label] = len(instructions)
  return instructions, labels


class Interpreter:
  def __init__(self, instructions, labels, output_fn=print):
    self.instructions = instructions
    self.labels = labels
    self.output_fn = output_fn

  def _eval_int(self, arg):
    if arg is None:
      return None
    try:    # Integer value
      return int(arg)
    except ValueError:
      try:  # Pointer
        ptr = int(arg.strip('[]'))
        return self.tiles[int(ptr)]
      except ValueError:
        # String to integer - A -> 1, B -> 2 etc
        return ord(arg[0].upper()) - 64

  def inbox(self, _arg):
    # Will throw StopIteration if all input is consumed
    self.hand = self._eval_int(next(self.input_iter))

  def outbox(self, _arg):
    self.output_fn(self.hand)

  def copyfrom(self, idx):
    self.hand = self.tiles[idx]

  def copyto(self, idx):
    self.tiles[idx] = self.hand

  def bumpdn(self, idx):
    self.tiles[idx] -= 1
    self.hand = self.tiles[idx]

  def add(self, n):
    self.hand += self.tiles[n]

  def jump(self, addr):
    self.ip = addr

  def jumpz(self, addr):
    if 0 == self.hand:
      self.ip = addr

  def jumpn(self, addr):
    if self.hand < 0:
      self.ip = addr

  def execute_step(self):
    instr = self.instructions[self.ip]
    # print("  IP: %d" % self.ip)
    # print("  hand:  %s" % str(self.hand))
    # print("  tiles: %s" % self.tiles)
    # print(" Executing %s" % instr.instr)
    method_name = instr.instr.lower()
    try:
      method = getattr(self, method_name)
    except AttributeError:
      raise(Exception('Unrecognized instruction %s' % instr.instr))
    if method_name.startswith('jump'):
      method(self.labels[instr.arg])
    else:
      method(self._eval_int(instr.arg))
      self.ip += 1

  def execute(self, inputs):
    # print('EXECUTING PROGRAM ON INPUT %s' % str(inputs))
    self.ip = 0     # instruction pointer
    self.tiles = {} # indexed by integer address
    self.hand = None
    self.input_iter = iter(inputs)
    try:
      while True:
        self.execute_step()
    except StopIteration:
      # print('EXECUTION COMPLETE')
      return # all input consumed

if '__main__' == __name__:
  instructions, labels = parse(sys.stdin.readlines())
  interpreter = Interpreter(instructions, labels)
  interpreter.execute([1, 2])
  interpreter.execute(['A', 'B'])

Having read your code again in more detail, here's a short list of things I liked and didn't like so much about it:

Liked:

  • Your idea to write the interpreter in the first place, and the fact that you put it up for review!
  • Methods named after instructions, logical use of metaprogramming
  • Natural use of iter() and StopIteration
  • Unit tests! +10 for this :)

Didn't like so much:

  • The complex way you dealt with data types.
  • Overloading of operators in the HRM class.
  • Use of properties and setters where simple attributes feel sufficient.
  • The way you built the COMMANDS dictionary.
  • The use of sets, which I still don't quite understand.

Essentially, parts which felt unnecessarily complex or verbose. I guess that part of your goal was to explore Python as a language, which is great, and may be why you used so many features. But in a program of this size, especially a Python script, I think that less is often more!

\$\endgroup\$
  • 1
    \$\begingroup\$ Tiles in the game are like memory adresses or registers. You can adress them by index or by label in copyfrom and copyto commands. Other commands (mostly infix operators and comparisons) between the current value (that the player avatar holds in its hand) and the value of the current tile. \$\endgroup\$ – Mathias Ettinger Jun 26 '16 at 15:00
  • 1
    \$\begingroup\$ Python is my main and first language, and you share my thought that it's not what Python should be like. I'll try following your advice, definitely the "start more simply", that's probably where I'm going wrong. Thanks, :) \$\endgroup\$ – Peilonrayz Jun 27 '16 at 13:57
4
\$\begingroup\$

I don't like your error messages a lot. Let's compare them to some of Python's builtins:

TypeError: 'NoneType' object has no attribute '__getitem__'
IndexError: list index out of range

These are short snappy and too the point. They tell you as precisely as they can what has happened.

TileError: Bad tile address! Tile with address {data} does not exist! Where do you think you're going?
OutOfBoundsError: Overflow! Each data unit is restricted to values between -999 and 999. That should be enough for anybody.

These are exceedingly long error messages, and in both cases you only need the middle message:

TileError: Tile with address {data} does not exist!
OutOfBoundsError: Each data unit is restricted to values between -999 and 999.

The HRMType was a bit confusing to follow. You should have docstrings to make it clear what it's for. I was just reading it before I moved on, and then realised it was for subclassing. Before that, the lack of the data attribute was strange to see. The other odd thing that should be documented, is why the get command has *_ to take an arbitrary list of arguments? Normally a get command doesn't take any arguments, and in this case you're not doing anything with them anyway.

The other confusing aspect is that it seems like these are purely just wrappers for simple int and str data. They have only the single data attribute, and no methods besides __init__. The letters constant is odd, since you could just have a NUMBER_CHARACTERS constant without needing the class.

You are making a strange set up, so it's entirely possible that it's all necessary. But documentation is import for clarity, and it becomes extra important when you're doing strange things that the user wouldn't expect it.

\$\endgroup\$
  • 3
    \$\begingroup\$ To be fair, the error messages are supposed to be fun, we're talking about a game here. Otherwise, nice review, and pointing out the confusing parts is always helpful. \$\endgroup\$ – Quentin Pradet Jun 27 '16 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.