This example in Python is taken from the excellent video: “A Talk Near the Future of Python” by David Beazley.
Part 1: Most Simple Machine
Create the Machine with a Stack
class Machine:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def execute(self, instructions):
for args in instructions:
op = args[0]
args = args[1:]
print(op, args, self.items)
if op == 'const':
self.push(args[0])
elif op == 'add':
right = self.pop()
left = self.pop()
self.push(left+right)
elif op == 'mul':
right = self.pop()
left = self.pop()
self.push(left*right)
else:
raise RuntimeError('Bad op {}'.format(op))
Simple instructions for the machine
# Compute 2 + 3 * 0.1
code = [
('const', 2),
('const', 3),
('const', 0.1),
('mul',),
('add',),
]
m = Machine()
m.execute(code)
print('Result:', m.pop())
Putting it all together for Part 1
class Machine:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def execute(self, instructions):
for args in instructions:
op = args[0]
args = args[1:]
print(op, args, self.items)
if op == 'const':
self.push(args[0])
elif op == 'add':
right = self.pop()
left = self.pop()
self.push(left+right)
elif op == 'mul':
right = self.pop()
left = self.pop()
self.push(left*right)
else:
raise RuntimeError('Bad op {}'.format(op))
# Compute 2 + 3 * 0.1
code = [
('const', 2),
('const', 3),
('const', 0.1),
('mul',),
('add',),
]
m = Machine()
m.execute(code)
print('Result:', m.pop())
const (2,) []
const (3,) [2]
const (0.1,) [2, 3]
mul () [2, 3, 0.1]
add () [2, 0.30000000000000004]
Result: 2.3
Get the file here: Machine Pt.1 in Python.
Part 2: Adding memory and variables
Amend the Machine to add memory
import struct
class Machine:
def __init__(self, memsize=65536): # Choose a memory size
self.items = []
self.memory = bytearray(memsize)
def load(self, addr): # Add function to load from memory
return struct.unpack('<d', self.memory[addr:addr+8])[0]
def store(self, addr, val): # Add function to store in memory
self.memory[addr:addr+8] = struct.pack('<d', val)
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def execute(self, instructions):
for args in instructions:
op = args[0]
args = args[1:]
print(op, args, self.items)
if op == 'const':
self.push(args[0])
elif op == 'add':
right = self.pop()
left = self.pop()
self.push(left+right)
elif op == 'mul':
right = self.pop()
left = self.pop()
self.push(left*right)
elif op == 'load': # Add operation for load
addr = self.pop()
self.push(self.load(addr))
elif op == 'store': # Add operation for store
val = self.pop()
addr = self.pop()
self.store(addr, val)
else:
raise RuntimeError('Bad op {}'.format(op))
Example instructions for the machine
# Now we can have variables, instead of hardcoded values
# We can now express "Compute 2 + 3 * 0.1"
# as "x = x * v * 0.1" where x = 2 and v = 3
# Pick addresses for the memory
x_addr = 22
v_addr = 42
code = [
('const', x_addr),
('const', x_addr),
('load',),
('const', v_addr),
('load',),
('const', 0.1),
('mul',),
('add',),
('store',),
]
m = Machine() # Create the machine
# Store our variables
m.store(x_addr, 2.0)
m.store(v_addr, 3.0)
m.execute(code)
print('Result:', m.load(x_addr)) # load from x, where we stored the result.
Putting it all together for Part 2
import struct
class Machine:
def __init__(self, memsize=65536): # Choose a memory size
self.items = []
self.memory = bytearray(memsize)
def load(self, addr): # Add function to load from memory
return struct.unpack('<d', self.memory[addr:addr+8])[0]
def store(self, addr, val): # Add function to store in memory
self.memory[addr:addr+8] = struct.pack('<d', val)
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def execute(self, instructions):
for args in instructions:
op = args[0]
args = args[1:]
print(op, args, self.items)
if op == 'const':
self.push(args[0])
elif op == 'add':
right = self.pop()
left = self.pop()
self.push(left+right)
elif op == 'mul':
right = self.pop()
left = self.pop()
self.push(left*right)
elif op == 'load': # Add operation for load
addr = self.pop()
self.push(self.load(addr))
elif op == 'store': # Add operation for store
val = self.pop()
addr = self.pop()
self.store(addr, val)
else:
raise RuntimeError('Bad op {}'.format(op))
# Now we can have variables, instead of hardcoded values
# We can now express "Compute 2 + 3 * 0.1"
# as "x = x * v * 0.1" where x = 2 and v = 3
# Pick addresses for the memory
x_addr = 22
v_addr = 42
code = [
('const', x_addr),
('const', x_addr),
('load',),
('const', v_addr),
('load',),
('const', 0.1),
('mul',),
('add',),
('store',),
]
m = Machine() # Create the machine
# Store our variables
m.store(x_addr, 2.0)
m.store(v_addr, 3.0)
m.execute(code)
print('Result:', m.load(x_addr)) # load from x, where we stored the result.
const (22,) []
const (22,) [22]
load () [22, 22]
const (42,) [22, 2.0]
load () [22, 2.0, 42]
const (0.1,) [22, 2.0, 3.0]
mul () [22, 2.0, 3.0, 0.1]
add () [22, 2.0, 0.30000000000000004]
store () [22, 2.3]
Result: 2.3
Get the file here: Machine Pt.2 in Python.
Part 3: Adding ability to run functions
Amend the code to add a Function type
class Function:
def __init__(self, nparams, returns, code): # Choose a memory size
self.nparams = nparams
self.returns = returns
self.code = code
Update the machine to run functions
import struct
class Machine:
def __init__(self, functions, memsize=65536): # Choose a memory size
self.functions = functions
self.items = []
self.memory = bytearray(memsize)
def load(self, addr):
return struct.unpack('<d', self.memory[addr:addr+8])[0]
def store(self, addr, val):
self.memory[addr:addr+8] = struct.pack('<d', val)
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def call(self, func, *args): # New way to call functions
locals = dict(enumerate(args)) # {0: args[0], 1: args[1], 2: args[2]}
self.execute(func.code, locals)
if func.returns:
return self.pop()
def execute(self, instructions, locals):
for args in instructions:
op = args[0]
args = args[1:]
print(op, args, self.items)
if op == 'const':
self.push(args[0])
elif op == 'add':
right = self.pop()
left = self.pop()
self.push(left+right)
elif op == 'mul':
right = self.pop()
left = self.pop()
self.push(left*right)
elif op == 'load':
addr = self.pop()
self.push(self.load(addr))
elif op == 'store':
val = self.pop()
addr = self.pop()
self.store(addr, val)
elif op == 'local.get':
self.push(locals[args[0]])
elif op == 'local.set':
locals[args[0]] = self.pop()
elif op == 'call':
func = self.functions[args[0]]
fargs = reversed([self.pop() for _ in range(func.nparams)])
result = self.call(func, *fargs)
if func.returns:
self.push(result)
else:
raise RuntimeError('Bad op {}'.format(op))
Example instructions for the machine
# We can now express "Compute 2 + 3 * 0.1"
# as a function:
update_position = Function(nparams=3, returns=True, code=[
('local.get', 0), # x
('local.get', 1), # v
('local.get', 2), # dt
('mul',),
('add',)
])
functions = [update_position]
# Pick addresses for the memory
x_addr = 22
v_addr = 42
code = [
('const', x_addr),
('const', x_addr),
('load',),
('const', v_addr),
('load',),
('const', 0.1),
('call', 0), # Function 0: update_position
('store',),
]
m = Machine(functions) # Create the machine
# Store our variables
m.store(x_addr, 2.0)
m.store(v_addr, 3.0)
m.execute(code, None)
print('Result:', m.load(x_addr)) # load from x, where we stored the result.
Putting it all together for Part 3
class Function:
def __init__(self, nparams, returns, code): # Choose a memory size
self.nparams = nparams
self.returns = returns
self.code = code
import struct
class Machine:
def __init__(self, functions, memsize=65536): # Choose a memory size
self.functions = functions
self.items = []
self.memory = bytearray(memsize)
def load(self, addr):
return struct.unpack('<d', self.memory[addr:addr+8])[0]
def store(self, addr, val):
self.memory[addr:addr+8] = struct.pack('<d', val)
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def call(self, func, *args): # New way to call functions
locals = dict(enumerate(args)) # {0: args[0], 1: args[1], 2: args[2]}
self.execute(func.code, locals)
if func.returns:
return self.pop()
def execute(self, instructions, locals):
for args in instructions:
op = args[0]
args = args[1:]
print(op, args, self.items)
if op == 'const':
self.push(args[0])
elif op == 'add':
right = self.pop()
left = self.pop()
self.push(left+right)
elif op == 'mul':
right = self.pop()
left = self.pop()
self.push(left*right)
elif op == 'load':
addr = self.pop()
self.push(self.load(addr))
elif op == 'store':
val = self.pop()
addr = self.pop()
self.store(addr, val)
elif op == 'local.get':
self.push(locals[args[0]])
elif op == 'local.set':
locals[args[0]] = self.pop()
elif op == 'call':
func = self.functions[args[0]]
fargs = reversed([self.pop() for _ in range(func.nparams)])
result = self.call(func, *fargs)
if func.returns:
self.push(result)
else:
raise RuntimeError('Bad op {}'.format(op))
# We can now express "Compute 2 + 3 * 0.1"
# as a function:
update_position = Function(nparams=3, returns=True, code=[
('local.get', 0), # x
('local.get', 1), # v
('local.get', 2), # dt
('mul',),
('add',)
])
functions = [update_position]
# Pick addresses for the memory
x_addr = 22
v_addr = 42
code = [
('const', x_addr),
('const', x_addr),
('load',),
('const', v_addr),
('load',),
('const', 0.1),
('call', 0), # Function 0: update_position
('store',),
]
m = Machine(functions) # Create the machine
# Store our variables
m.store(x_addr, 2.0)
m.store(v_addr, 3.0)
m.execute(code, None)
print('Result:', m.load(x_addr)) # load from x, where we stored the result.
const (22,) []
const (22,) [22]
load () [22, 22]
const (42,) [22, 2.0]
load () [22, 2.0, 42]
const (0.1,) [22, 2.0, 3.0]
call (0,) [22, 2.0, 3.0, 0.1]
local.get (0,) [22]
local.get (1,) [22, 2.0]
local.get (2,) [22, 2.0, 3.0]
mul () [22, 2.0, 3.0, 0.1]
add () [22, 2.0, 0.30000000000000004]
store () [22, 2.3]
Result: 2.3
Get the file here: Machine Pt.3 in Python.
Part 4: Adding ability to control flow
Add Exceptions to break flow of control
class Break(Exception):
def __init__(self, level):
self.level = level
class Return(Exception):
pass
Update the machine to run functions
import struct
class Machine:
def __init__(self, functions, memsize=65536): # Choose a memory size
self.functions = functions
self.items = []
self.memory = bytearray(memsize)
def load(self, addr):
return struct.unpack('<d', self.memory[addr:addr+8])[0]
def store(self, addr, val):
self.memory[addr:addr+8] = struct.pack('<d', val)
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def call(self, func, *args): # New way to call functions
locals = dict(enumerate(args)) # {0: args[0], 1: args[1], 2: args[2]}
try:
self.execute(func.code, locals)
except Return:
pass
if func.returns:
return self.pop()
def execute(self, instructions, locals):
for args in instructions:
op = args[0]
args = args[1:]
print(op, args, self.items)
if op == 'const':
self.push(args[0])
elif op == 'add':
right = self.pop()
left = self.pop()
self.push(left+right)
elif op == 'mul':
right = self.pop()
left = self.pop()
self.push(left*right)
elif op == 'sub':
right = self.pop()
left = self.pop()
self.push(left-right)
elif op == 'le':
right = self.pop()
left = self.pop()
self.push(left<=right)
elif op == 'ge':
right = self.pop()
left = self.pop()
self.push(left>=right)
elif op == 'load':
addr = self.pop()
self.push(self.load(addr))
elif op == 'store':
val = self.pop()
addr = self.pop()
self.store(addr, val)
elif op == 'local.get':
self.push(locals[args[0]])
elif op == 'local.set':
locals[args[0]] = self.pop()
elif op == 'call':
func = self.functions[args[0]]
fargs = reversed([self.pop() for _ in range(func.nparams)])
result = self.call(func, *fargs)
if func.returns:
self.push(result)
elif op == 'br':
raise Break(args[0])
elif op == 'br_if':
if self.pop():
raise Break(args[0])
# if (test) { consequence } else { alternative }
# ('block', [
# ('block', [
# test
# ('br_if', 0), # Goto 0
# alternative,
# ('br', 1) # Goto 1
# ]
# ), # Label: 0
# consequence,
# ]
# ) # Label: 1
elif op == 'block': # ('block', [instructions])
try:
self.execute(args[0], locals)
except Break as b:
if b.level > 0:
b.level -= 1
raise
# ('block', [
# ('loop', [ # Label 0
# not test
# ('br_if', 1), # Goto 1: (break)
# body,
# ('br', 0) # Goto 0: (continue)
# ]
# ), # Label: 0
# ]
# ) # Label: 1
elif op == 'loop':
while True:
try:
self.execute(args[0], locals)
break
except Break as b:
if b.level > 0:
b.level -= 1
raise
elif op == 'return':
raise Return()
else:
raise RuntimeError('Bad op {}'.format(op))
Example instructions for the machine
# We can now express "Compute 2 + 3 * 0.1"
# as a function:
update_position = Function(nparams=3, returns=True, code=[
('local.get', 0), # x
('local.get', 1), # v
('local.get', 2), # dt
('mul',),
('add',)
])
functions = [update_position]
# Pick addresses for the memory
x_addr = 22
v_addr = 42
# while x > 0{
# x = update_position(x, v, 0.1)
# if x >= 70 {
# v = -v;
# }
# }
code = [
('block', [
('loop',[
('const', x_addr),
('load',),
('const', 0.0),
('le',),
('br_if', 1),
('const', x_addr),
('const', x_addr),
('load',),
('const', v_addr),
('load',),
('const', 0.1),
('call', 0),
('store',),
('block', [
('const', x_addr),
('load',),
('const', 70.0),
('ge',),
('block', [
('br_if', 0),
('br', 1),
]),
('const', v_addr),
('const', 0.0),
('const', v_addr),
('load',),
('sub',),
('store',),
]
),
('br', 0),
]
)
], None),
]
m = Machine(functions) # Create the machine
# Store our variables
m.store(x_addr, 2.0)
m.store(v_addr, 3.0)
m.execute(code, None)
print('Result:', m.load(x_addr)) # load from x, where we stored the result.
Putting it all together for Part 4
class Function:
def __init__(self, nparams, returns, code): # Choose a memory size
self.nparams = nparams
self.returns = returns
self.code = code
class Break(Exception):
def __init__(self, level):
self.level = level
class Return(Exception):
pass
import struct
class Machine:
def __init__(self, functions, memsize=65536): # Choose a memory size
self.functions = functions
self.items = []
self.memory = bytearray(memsize)
def load(self, addr):
return struct.unpack('<d', self.memory[addr:addr+8])[0]
def store(self, addr, val):
self.memory[addr:addr+8] = struct.pack('<d', val)
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def call(self, func, *args): # New way to call functions
locals = dict(enumerate(args)) # {0: args[0], 1: args[1], 2: args[2]}
try:
self.execute(func.code, locals)
except Return:
pass
if func.returns:
return self.pop()
def execute(self, instructions, locals):
for args in instructions:
op = args[0]
args = args[1:]
print(op, args, self.items)
if op == 'const':
self.push(args[0])
elif op == 'add':
right = self.pop()
left = self.pop()
self.push(left+right)
elif op == 'mul':
right = self.pop()
left = self.pop()
self.push(left*right)
elif op == 'sub':
right = self.pop()
left = self.pop()
self.push(left-right)
elif op == 'le':
right = self.pop()
left = self.pop()
self.push(left<=right)
elif op == 'ge':
right = self.pop()
left = self.pop()
self.push(left>=right)
elif op == 'load':
addr = self.pop()
self.push(self.load(addr))
elif op == 'store':
val = self.pop()
addr = self.pop()
self.store(addr, val)
elif op == 'local.get':
self.push(locals[args[0]])
elif op == 'local.set':
locals[args[0]] = self.pop()
elif op == 'call':
func = self.functions[args[0]]
fargs = reversed([self.pop() for _ in range(func.nparams)])
result = self.call(func, *fargs)
if func.returns:
self.push(result)
elif op == 'br':
raise Break(args[0])
elif op == 'br_if':
if self.pop():
raise Break(args[0])
# if (test) { consequence } else { alternative }
# ('block', [
# ('block', [
# test
# ('br_if', 0), # Goto 0
# alternative,
# ('br', 1) # Goto 1
# ]
# ), # Label: 0
# consequence,
# ]
# ) # Label: 1
elif op == 'block': # ('block', [instructions])
try:
self.execute(args[0], locals)
except Break as b:
if b.level > 0:
b.level -= 1
raise
# ('block', [
# ('loop', [ # Label 0
# not test
# ('br_if', 1), # Goto 1: (break)
# body,
# ('br', 0) # Goto 0: (continue)
# ]
# ), # Label: 0
# ]
# ) # Label: 1
elif op == 'loop':
while True:
try:
self.execute(args[0], locals)
break
except Break as b:
if b.level > 0:
b.level -= 1
raise
elif op == 'return':
raise Return()
else:
raise RuntimeError('Bad op {}'.format(op))
# We can now express "Compute 2 + 3 * 0.1"
# as a function:
update_position = Function(nparams=3, returns=True, code=[
('local.get', 0), # x
('local.get', 1), # v
('local.get', 2), # dt
('mul',),
('add',)
])
functions = [update_position]
# Pick addresses for the memory
x_addr = 22
v_addr = 42
# while x > 0{
# x = update_position(x, v, 0.1)
# if x >= 70 {
# v = -v;
# }
# }
code = [
('block', [
('loop',[
('const', x_addr),
('load',),
('const', 0.0),
('le',),
('br_if', 1),
('const', x_addr),
('const', x_addr),
('load',),
('const', v_addr),
('load',),
('const', 0.1),
('call', 0),
('store',),
('block', [
('const', x_addr),
('load',),
('const', 70.0),
('ge',),
('block', [
('br_if', 0),
('br', 1),
]),
('const', v_addr),
('const', 0.0),
('const', v_addr),
('load',),
('sub',),
('store',),
]
),
('br', 0),
]
)
], None),
]
m = Machine(functions) # Create the machine
# Store our variables
m.store(x_addr, 2.0)
m.store(v_addr, 3.0)
m.execute(code, None)
print('Result:', m.load(x_addr)) # load from x, where we stored the result.
Get the file here: Machine Pt.4 in Python.
Part 5: Importing external functions to run
28:00 min in to video