Sunday, January 18, 2009

Post's Machine

An undergrad CompSci major, Shriphani Palakodety, posted an implementation of Post's Machine. Post's machine is a simple computer that has separate data and execution storage. Here's my implementation and my advice to Shriphani - Keep it simple! When working on hard problems post-graduation you'll find that code gets complicated of its own volition. The job of the writer is to fight it at every turn (the next guy to come along will appreciate the effort).

This version replaces the two custom containers with python dicts and moves all the complicated code to the pretty printer. A collections.defaultdict might be a slightly better choice for the 'infinite tape' that starts as all zeros. A nice thing about defaultdicts is that you can min() and max() even empty dicts.

I also did a python3.0 version which was nearly identical except for a 'with' on the file open and print-as-fucntion. Disappointingly I thought the advanced tuple unpack syntax would help in the case where a too-short tuple is padded and then the padding discarded.

# args might be a two or three tuple
a, b, c = (args + [0])[:3]

# python3 syntax
a, b, c, *ignore = args + [0]

The *ignore argument demands to be read as opposed to the [:3] trimmer on the end which keeps the low profile it deserves.

Here's the code for my Post Machine
def parse(lines):
program = {}
for line in lines:
pos, action, jump = [p.strip() for p in line.split(',') + ['0']][:3]
program[pos] = action, jump
return program

def execute(program):
tape = {}
tape_pos = 0
action = None
action_pos = '0'

while action != 'exit':
action, action_pos = program[action_pos]

pretty_tape(tape, tape_pos)

if action == '<':
tape_pos -= 1
elif action == '>':
tape_pos += 1
elif action == 'mark':
tape[tape_pos] = 1
elif action == 'unmark':
tape[tape_pos] = 0

return tape, tape_pos

def pretty_tape(tape, tape_pos):
if not tape:
tape = {0:0}
min_pos = min(tape_pos, min(tape), 0)
max_pos = max(tape_pos, max(tape), 4)

parts = []
for pos in range(min_pos, max_pos + 1):
val = tape.get(pos, 0)
if pos == tape_pos:
parts.append('[%d]' % val)
else:
parts.append('%d' % val)

print '.....', ', '.join(parts), '.....'

if __name__ == '__main__':
program = parse(open('post.txt'))
execute(program)

1 comment:

Anonymous said...

Hi,

Thanks a lot for your version and advice. The Py3k version looks weird. The Py2.5 version looks intuitive enough. Maybe the *ignore seems more "Explicit".