Johnicholas Hines

Long-haired programmer; loves cats and dogs but doesn't have any.

What is an interpreter? An interpreter is a computer program that obeys some data.

This is a skeleton of an interpreter:

program = [
  'command1',
  'command2'
]
for command in program:
  if command == 'command1':
    command1()
  elif command == 'command2':
    command2()

There are a lot of optional add-ons to this skeleton. For example, we might want a register. This holds a small amount of state.

program = [
  'inc',
  'print',
  'print',
  'inc',
  'print',
  'inc',
  'print'
  'inc',
  'inc',
  'print'
]
register = 0
for command in program:
  if command == 'inc':
    register = register + 1
  elif command == 'print':
    print(register)

Another thing that we might want is a ‘go to’ command, also called ‘jump’, which allows the interpreter’s control flow to move around the program in a nonlinear way. One way to add that is using a special register called the ‘program counter’.

program = [
  'print',
  'inc',
  'goto', '0'
]
register = 0
program_counter = 0
while program_counter >= 0 and program_counter < len(program):
  command = program[program_counter]
  if command == 'inc':
    register = register + 1
    program_counter = program_counter + 1
  elif command == 'print':
    print(register)
    program_counter = program_counter + 1
  elif command == 'goto':
    program_counter = int(program[program_counter+1])

This illustrates another phenomenon - variable length instructions. The interpreter uses the command directly at the program counter to dispatch to one of the (in this case) three clauses. But the clause can look at the program just beyond the command, in order to (in this case) decide where to go to.

Let’s do something a bit more interesting. Python has a turtle package - let’s write an interpreter that controls the turtle. Note that program_counter has been shortened to pc.

from turtle import *

program = [
  'color', 'red', 'yellow',
  'begin_fill',
  'forward', '200',
  'left', '270',
  'forward', '200',
  'left', '270',
  'forward', '200',
  'left', '270',
  'forward', '200',
  'left', '270',
  'end_fill'
  'done'
]
register = 0
pc = 0
while pc >= 0 and pc < len(program):
  command = program[pc]
  if command == 'goto':
    pc = int(program[pc+1])
  elif command == 'color':
    color(program[pc+1], program[pc+2])
    pc = pc + 3
  elif command == 'begin_fill':
    begin_fill()
    pc = pc + 1
  elif command == 'forward':
    forward(int(program[pc+1]))
    pc = pc + 2
  elif command == 'left':
    left(int(program[pc+1]))
    pc = pc + 2
  elif command == 'end_fill':
    end_fill()
    pc = pc + 1
  elif command == 'done':
    done()
    pc = pc + 1

Despite being a LITTLE bit more interesting, it’s still not VERY interesting. But people do write interpreters that produce graphics. For example, the SVG path element has commands like “moveto x, y”, ‘lineto x, y”, “closepath”, which work very analogously to this turtle-interpreter.

Another common addon to a basic interpreter is a stack. That is, just a linear sequence that we push things onto or pop things off of, in some of the commands. It is a really simple mechanism, that produces remarkably flexible effects.

from turtle import *

program = [
  'goto', '37',
  'forward', '10',
  'forward', '-10',
  'return',
  'forward', '14',
  'left', '24',
  'call', '2',
  'left', '312',
  'call', '2',
  'left', '24',
  'forward', '-14',
  'return',
  'forward', '20',
  'left', '24',
  'call', '7',
  'left', '312',
  'call', '7',
  'left', '24',
  'forward', '-20',
  'return',
  'left', '90',
  'color', 'green', 'yellow',
  'begin_fill',
  'forward', '28',
  'left', '24',
  'call', '22',
  'left', '312',
  'call', '22',
  'left', '24',
  'forward', '-28',
  'end_fill',
  'done'
]
stack = []
register = 0
pc = 0
while pc >= 0 and pc < len(program):
  command = program[pc]
  if command == 'call':
    stack.append(pc+2)
    pc = int(program[pc+1])
  elif command == 'return':
    return_to = stack.pop()
    pc = int(return_to)
  elif command == 'goto':
    pc = int(program[pc+1])
  elif command == 'color':
    color(program[pc+1], program[pc+2])
    pc = pc + 3
  elif command == 'begin_fill':
    begin_fill()
    pc = pc + 1
  elif command == 'forward':
    forward(int(program[pc+1]))
    pc = pc + 2
  elif command == 'left':
    left(int(program[pc+1]))
    pc = pc + 2
  elif command == 'end_fill':
    end_fill()
    pc = pc + 1
  elif command == 'done':
    done()
    pc = pc + 1

I’m not certain that this blog has actually demonstrated that little interpreters, either like these or disguised versions of these, are valuable and useful in software development - but I claim they are? Sigh.

Opinions expressed are solely my own and do not express the views or opinions of my employer.