Posted at

フォースを使う

More than 1 year has passed since last update.

英語として、なぜ the が必要なのだろうと少しだけ考えた。良いフォースと悪いフォースがあるからだろうか?結論は見ればわかるのかもしれない。当分、映画には行けそうもないので、そのままそっとしておこう。なにしろ、私の中ではハン・ソロが凍ったままだ。あるいは、老体に鞭打ってアンドロイドを追っかけまわす姿を見るのも忍びない。

私が紹介する FORTH は retro の ver 11 だ。最新の retro は ver 12 で VM から作り直したらしい。retro は正確には FORTH ではないらしい。本格的に FPGA で FORTH をやるなら swapforth がよさそうだ。以前、Synthesijer で retro を移植したので今回も retro だ。


簡単な VM

まず最初に簡単な VM のソースを示そう。高位合成で VM を作るのはそう難しい話ではない。例えば Polyphony ではこんな感じで作れるだろう。


minivm.py

from polyphony import testbench

def minivm(start_addr):
LOAD0 = 0
LOAD1 = 1
ADD = 2
SUB = 3
MUL = 4
HALT = 0xFF
pc = start_addr
reg = [0]*8
program = [0x0001, 0x0102, 0x0200, 0x0103, 0x0200, 0xFF00, #1+2+3
0x0002, 0x0103, 0x0400, 0x0104, 0x0400, 0xFF00] #2*3*4

def get_op(inst):
return (inst & 0xFF00) >> 8

def get_v1(inst):
return (inst & 0x00FF)

while True:
inst = program[pc]
op = get_op(inst)
print(op)
v1 = get_v1(inst)
if op == LOAD0:
reg[0] = v1
elif op == LOAD1:
reg[1] = v1
elif op == ADD:
reg[0] = reg[0] + reg[1]
elif op == SUB:
reg[0] = reg[0] - reg[1]
elif op == MUL:
reg[0] = reg[0] * reg[1]
elif op == HALT:
break
pc += 1
return reg[0]

@testbench
def test():
assert minivm(0) == 6
assert minivm(6) == 24

test()


これは Polyphony の tests/app にある minivm.py のコードだ。その他に minivm2.py, mips.py がある。


retro

ちょっと長いが全ソースを掲げよう。といっても 350 行程度でif-elif が続くだけなのでプログラムとしてはそんなに難解ではない。


retro-skinless.py

#!/usr/bin/env python3

# Ngaro VM
# Copyright (c) 2010, Charles Childers
# Optimizations and process() rewrite by Greg Copeland
# Copyright (c) 2016, 2017, Ryos Suzuki
# -----------------------------------------------------------------------------
import os, sys, math, time
from polyphony import testbench

MEMORY_SIZE = 64 #16384
STACK_SIZE = 64 #2048
EXIT = 1
DEC = 2
INPUT_INC = 4

# -----------------------------------------------------------------------------
def abs(x):
if x < 0 :
return -x
return x

def handle_devices( ip, ports:list, stack:list, stack_pos, address:list, retro_program:list, retro_program_pos ):
rv = 0
ports[0] = 1
if ports[1] == 1:
#ports[1] = ord(sys.stdin.read(1))
if len(retro_program) == retro_program_pos :
rv = EXIT
else:
c = retro_program[retro_program_pos]
ports[1] = c
#ports[1] = ord(sys.stdin.read(1))
#print("ryos char %c", c)
#sys.stdout.write(chr(c))
rv = INPUT_INC

if ports[1] == 13:
ports[1] = 10
if ports[2] == 1:
c = stack[stack_pos-1]
if c > 0 and c < 128:
#sys.stdout.write(chr(c))
print(c)
stack_pos -= 1
rv |= DEC
ports[2] = 0
if ports[5] == -1: # memory size - zero based index
ports[5] = MEMORY_SIZE - 1
elif ports[5] == -2: # canvas exists?
ports[5] = 0
elif ports[5] == -3: # screen width
ports[5] = 0
elif ports[5] == -4: # screen height
ports[5] = 0
elif ports[5] == -5: # stack depth
ports[5] = len(stack)
elif ports[5] == -6: # address stack depth
ports[5] = len(address)
elif ports[5] == -7: # mouse exists?
ports[5] = 0
elif ports[5] == -8: # time
# ports[5] = int(time.time())
ports[5] = 0
elif ports[5] == -9: # exit vm
rv = EXIT
ports[5] = 0

return rv

#-----------------------------------------------------------------------------
#def print_stack(stack, stack_pos):
# pstack = []
# for i in range(0, stack_pos):
# pstack.append(stack[i])
# print(pstack)

#-----------------------------------------------------------------------------
def load(rom:list, rom_sz, memory:list):
for i in range(0, rom_sz):
memory[i] = rom[i]

# -----------------------------------------------------------------------------
def retro_main( rom:list, rom_sz, io:list, retro_program:list ):
ip = 0
ext = MEMORY_SIZE - 1
stack = [None]*2048
address = [None]*2048
ports = [0]*128
files = [0]*8
memory = [None]*16384

stack_pos = 0
address_pos = 0
stack_len_max = 0
retro_program_pos = 0

print("load start %5t", "$time")
load(rom, rom_sz, memory)
print("load END %5t", "$time")
debug_on = 0

while ip < ext:
opcode = memory[ip]

if stack_len_max < stack_pos:
stack_len_max = stack_pos
print("do opcode", opcode)

# If opcode is not one we know,
# jump past it. We have 30-opcodes.
if opcode <= 30:
if opcode == 0: # nop
#stack[stack_pos] = "here";
#print(stack)
#stack[stack_pos] = -1
pass

elif opcode == 1: # lit
ip += 1
stack[stack_pos] = memory[ip]
stack_pos += 1

elif opcode == 2: # dup
stack[stack_pos] = stack[stack_pos-1]
stack_pos += 1

elif opcode == 3: # drop
stack_pos -= 1
stack[stack_pos] = 0

elif opcode == 4: # swap
a = stack[stack_pos-2]
stack[stack_pos-2] = stack[stack_pos-1]
stack[stack_pos-1] = a

elif opcode == 5: # push
stack_pos -= 1
address[address_pos] = stack[stack_pos]
stack[stack_pos] = 0
address_pos += 1

elif opcode == 6: # pop
address_pos -= 1
stack[stack_pos] = address[address_pos]
address[address_pos] = 0
stack_pos += 1

elif opcode == 7: # loop
#print("loop n:%d" % stack[stack_pos-1])
stack[stack_pos-1] -= 1
if stack[stack_pos-1] != 0 and stack[stack_pos-1] > -1:
ip += 1
ip = memory[ip] - 1
else:
ip += 1
stack_pos -= 1

elif opcode == 8: # jump
ip += 1
ip = memory[ip] - 1
if memory[ip + 1] == 0:
ip += 1
if memory[ip + 1] == 0:
ip += 1

elif opcode == 9: # return
address_pos -= 1
ip = address[address_pos]
#print("return %d" % ip)

elif opcode == 10: # >= jump
ip += 1
stack_pos -= 1
a = stack[stack_pos]
stack_pos -= 1
b = stack[stack_pos]
if b > a:
ip = memory[ip] - 1

elif opcode == 11: # <= jump
ip += 1
stack_pos -= 1
a = stack[stack_pos]
stack_pos -= 1
b = stack[stack_pos]
if b < a:
ip = memory[ip] - 1

elif opcode == 12: # != jump
ip += 1
stack_pos -= 1
a = stack[stack_pos]
stack_pos -= 1
b = stack[stack_pos]
if b != a:
ip = memory[ip] - 1

elif opcode == 13: # == jump
ip += 1
stack_pos -= 1
a = stack[stack_pos]
stack_pos -= 1
b = stack[stack_pos]
if b == a:
ip = memory[ip] - 1

elif opcode == 14: # @
stack[stack_pos-1] = memory[stack[stack_pos-1]]

elif opcode == 15: # !
stack_pos -= 1
mi = stack[stack_pos]
stack_pos -= 1
memory[mi] = stack[stack_pos]

elif opcode == 16: # +
stack_pos -= 1
t = stack[stack_pos]
stack[stack_pos-1] += t

elif opcode == 17: # -
stack_pos -= 1
t = stack[stack_pos]
stack[stack_pos-1] -= t

elif opcode == 18: # *
stack_pos -= 1
t = stack[stack_pos]
stack[stack_pos-1] *= t

elif opcode == 19: # /mod
x = stack[stack_pos-2]
y = stack[stack_pos-1]

abs_x = abs(x)
abs_y = abs(y)

q = abs_x // abs_y
r = abs_x % abs_y

if x < 0 and y < 0:
r = -r
elif x > 0 and y < 0:
q = -q
elif x < 0 and y > 0:
q = -q
r = -r

stack[stack_pos-1] = q
stack[stack_pos-2] = r

elif opcode == 20: # and
stack_pos -= 1
t = stack[stack_pos]
stack[stack_pos-1] &= t

elif opcode == 21: # or
stack_pos -= 1
t = stack[stack_pos]
stack[stack_pos-1] |= t

elif opcode == 22: # xor
stack_pos -= 1
t = stack[stack_pos]
stack[stack_pos-1] ^= t

elif opcode == 23: # <<
stack_pos -= 1
t = stack[stack_pos]
stack[stack_pos-1] <<= t

elif opcode == 24: # >>
stack_pos -= 1
t = stack[stack_pos]
stack[stack_pos-1] >>= t

elif opcode == 25: # 0;
if stack[stack_pos-1] == 0:
stack_pos -= 1
address_pos -= 1
ip = address[address_pos]

elif opcode == 26: # inc
stack[stack_pos-1] += 1

elif opcode == 27: # dec
stack[stack_pos-1] -= 1

elif opcode == 28: # in
stack[stack_pos-1] = ports[stack[stack_pos-1]]

elif opcode == 29: # out
stack_pos -= 1
pi = stack[stack_pos]
stack_pos -= 1
ports[ pi ] = stack[stack_pos]

elif opcode == 30: # wait
# Only call if we have pending I/O
# print(ports)
if ports[0] == 0:
rv = handle_devices( ip, ports, stack, stack_pos, address, retro_program, retro_program_pos )
if (rv & EXIT) == EXIT :
ip = ext
if (rv & DEC) == DEC :
stack_pos -= 1
if (rv & INPUT_INC) ==INPUT_INC :
retro_program_pos += 1

else:
address[address_pos] = ip
address_pos += 1
ip = memory[ip] - 1
if memory[ip + 1] == 0:
ip += 1

ip += 1

return ip

# -----------------------------------------------------------------------------
def load_from_file(rom:list):
# fileName = 'retroImage'
# sz = os.path.getsize(fileName)
# f = open( fileName, 'rb' )
# data = f.read()
# f.close()
#
# for i in range(0, sz, 4):
# b1 = (data[i])
# b2 = (data[i+1])
# b3 = (data[i+2])
# b4 = (data[i+3])
# n = b1 + (b2<<8) + (b3<<16) + (b4<<24)
# if n > 2147483647:
# n = n - 4294967296
# rom[int(i/4)] = n
pass

# -----------------------------------------------------------------------------
@testbench
def test():
rom = [1, -9, 1, 5, 29, 30]
io = [0]*1

retro_program = [0x33, 10, 0x34, 10, 43, 10, 112, 117, 116, 110, 10]

load_from_file(rom)

retro_main(rom, len(rom), io, retro_program)

test()


retro は FORTH の亜種なので自己増殖する。通常は PC で動く自分自身あるいは他の FORTH から bootstrap を作りそれを種に自分を増殖させる。ここで掲げるコードは残念ながらその種のコードがついてない。uart にも対応した形でいずれ全ソースを公開したい。


おまけ

もし、これをみて FORTH を作ってみたいと思ったら、前出の swapforth のソースを読むとよい。Verilog-HDL のコードもある。memory やら io のアクセスを巧みに省略していてコンパクトなコードになっている。種は gforth からつくる。VM をつくって、そこから FORTH を組み立てられれば、どんな組み込みシステム環境でも FORTH を移植できるようになるに違いない。

May the FORTH be with you.