Сейчас пишу компилятор для маленького лиспа, все работает так, как нужно, но хочется узнать, как это реализовать правильнее. На данный момент, такой вот код:
(defun (fact n)
(if-else (> n 1)
(* n (fact (- n 1)))
1))
(print (fact 5))
компилируется в такой "ассемблерный" код (комментарии исполнитель не пропускает):
fact:
check_args 1
set_arg n; изначально, в функцию приходит массив аргументов, их нужно распаковать и дать имена
load_name n
push_int 1
gt; берет два верхних объекта на стеке, возвращает True, если второй больше первого
jf 7; пропускает заданное количество команд, если верхний элемент стека - False
load_name n
load_name n
push_int 1
sub
call fact 1; вызывает заданную функцию с указанным количеством аргументов
mult 2
jmp 1; безусловно пропускает заданное количество команд
push_int 1
ret
push_int 5
call fact 1
print 1
Исполнением занимается такая простыня кода:
from time import time
class Type:
(Int, Str, Func, List, Bool) = range(5)
Name = ('Int', 'Strs', 'Func', 'List', 'Bool')
class Var:
def __init__(self, t, value):
self.type = t
self.value = value
def __add__(self, other):
addable = [Type.Int, Type.Str, Type.List]
if not self.type in addable or not other.type in addable:
raise TypeError('Error: (+ <{}> <{}>)'.format(Type.Name(self.type), Type.Name(other.type)))
return Var(Type.Int, self.value + other.value)
def __sub__(self, other):
if self.type != Type.Int or other.type != Type.Int:
raise TypeError('Error: (- <{}> <{}>)'.format(Type.Name(self.type), Type.Name(other.type)))
return Var(Type.Int, self.value - other.value)
def __mul__(self, other):
if self.type != Type.Int or other.type != Type.Int:
raise TypeError('Error: (* <{}> <{}>)'.format(Type.Name(self.type), Type.Name(other.type)))
return Var(Type.Int, self.value * other.value)
def __truediv__(self, other):
if self.type != Type.Int or other.type != Type.Int:
raise TypeError('Error: (/ <{}> <{}>)'.format(Type.Name(self.type), Type.Name(other.type)))
return Var(Type.Int, self.value / other.value)
def __repr__(self):
return 'V[{}, {}]'.format(self.type, self.value)
def __str__(self):
if self.type == Type.Func:
return '<Func at {}>'.format(self.value)
return str(self.value)
def __gt__(self, other):
if self.type != Type.Int or other.type != Type.Int:
raise TypeError('Error: (> <{}> <{}>)'.format(Type.Name(self.type), Type.Name(other.type)))
return Var(Type.Bool, self.value > other.value)
def __bool__(self):
return bool(self.value)
class Scope:
def __init__(self, parent):
self.parent = parent
self.scope = {}
def __getitem__(self, key):
if not key in self.scope.keys():
if self.parent != {}:
return self.parent[key]
else:
raise KeyError(key)
return self.scope[key]
def __setitem__(self, key, value):
self.scope[key] = value
def __repr__(self):
return repr(self.scope)
def __contains__(self, key):
if not key in self.scope.keys():
if key in self.parent:
return True
return False
return True
def keys(self):
ret = set(self.scope.keys())
for i in self.parent.keys():
ret.add(i)
return ret
f_name = input() or 'code.code'
f = open(f_name, 'r').readlines()
f = [i.replace('\n', '') for i in f]
inFunc = False
stack = []
args = []
var = [Scope({})]
call_level = 0
call_stack = []
pos = 0
start = time()
while pos<len(f):
i = f[pos]
if i.endswith(':'):
var[0][i.replace(':', '')] = Var(Type.Func, pos)
inFunc = True
if inFunc and i == 'ret':
inFunc = False
pos+=1
continue
if not inFunc:
a = i.split(' ') # a for args
if a[0] == 'push_int':
stack.append(Var(Type.Int, int(a[1])))
elif a[0] == 'call':
if not a[1] in var[-1].keys():
raise NameError('{} is not defined! Pos: {}'.format(a[1], pos))
for i in range(int(a[2])):
args.append(stack.pop())
args.reverse()
call_stack.append(pos)
call_level+=1
var.append(Scope(var[-1]))
if var[-1][a[1]].type == Type.Func:
pos = var[-1][a[1]].value
elif a[0] == 'check_args':
if not len(args) == int(a[1]):
raise TypeError('Expected {} arguments, got {}! Pos: {}'.format(int(a[1]), len(args), pos))
elif a[0] == 'set_arg':
var[call_level][a[1]] = args.pop()
elif a[0] == 'load_name':
stack.append(var[call_level][a[1]])
elif a[0] == 'gt':
r = stack.pop()
l = stack.pop()
stack.append(l>r)
elif a[0] == 'add':
r = stack.pop()
l = stack.pop()
stack.append(l+r)
elif a[0] == 'sub':
r = stack.pop()
l = stack.pop()
stack.append(l-r)
elif a[0] == 'mult':
r = stack.pop()
l = stack.pop()
stack.append(l*r)
elif a[0] == 'div':
r = stack.pop()
l = stack.pop()
stack.append(l/r)
elif a[0] == 'jmp':
pos += int(a[1])
elif a[0] == 'jf':
if bool(stack.pop()) == False:
pos += int(a[1])
elif a[0] == 'ret':
pos = call_stack.pop()
call_level-=1
var.pop()
elif a[0] == 'print':
args = [stack.pop() for i in range(int(a[1]))]
args.reverse()
print(*args)
args = []
elif a[0] == 'list':
args = [stack.pop() for i in range(int(a[1]))]
args.reverse()
stack.append(Var(Type.List, args))
args = []
elif a[0] == 'get':
it = stack.pop()
arr = stack.pop()
stack.append(arr[it])
elif a[0] == 'len':
arr = stack.pop()
stack.append(len(arr))
pos+=1
print('finnished in {}s'.format(time()-start))
В общем, все работает, но есть несколько вопросов:
Как сделать так, что бы встроенные функции были "полноправными" (функциями первого класса)? Пока смог придумать только такой вариант:
(defun (+ a b) (bif-add a b)) # bif-add
- встроенная функция, + - оберткаКак правильнее реализовать области видимости?
Как ввести замыкания?
Буду благодарен, если кто-нибудь расскажет, как можно улучшить имеющийся код.