Привет, Хабр и читатели!
Сегодня я попытаюсь сделать с вами диалект LISP.
Я думаю, что я достаточно хорошо понимаю как его сделать.
Мы реализуем там TCO, FEXPR функции и dynamic scoping.
Как он будет выглядеть и на чём?
Язык написания - Python.
Думаю, на нём проще всего понимать такие проекты.
Я думаю что нам достаточно вот столько спец форм:
Команда | Аргументы | Значение |
if | test, a, b | Если test = t - выполнить a, если test = nil - выполнить b. |
quote | x | Вернуть x не вычисляя - для макросов самое то. |
macro | name, args, body | Создать макрос с именем name, аргументами args и с body. |
setq | name, val | Создать переменную с именем name и значением val. |
expand | expr | expr[0] = имя, expr[1:] = аргументы. По имени находим макрос и передаём ему аргументы |
foreach | name, obj, body | Пройтись по obj (iterable) и записывать каждую итерацию переменную name (значение которое взяли) и выполнять body |
loop | cond, body | Изначально loop в LISP немного по другому работает, но для простоты это будет просто while cond - eval body |
lambda | args, body | Возвращает анонимную функцию которая выполняет body с аргументами args. |
Будут 3 этапа:
Лексер.
Парсер.
Эвалуатор.
Наш TCO (tail-call optimization) будет лишь для хвостовых вызовов, так что вот такие рекурсивные вызов:
(* n (fact (- n 1)))
Будут ломать стек.
Валидный вызов для TCO будет:
(fact (- n 1) (* n acc))
Не правда ли что это ограничение?
Да, но для начала я думаю пойдёт.
Что за FEXPR, да?
Это такая функция которой передают невычисленные аргументы и она из этого всего строит какие то данные которые в последствие выполнит интерпретатор.
Вот пример:
(macro defun (name args . body) (list (quote setq) name (list (quote lambda) args (cons (quote begin) body)))))
И когда мы запустим:
(defun square (x) (princ x) (* x x))
... то интерпретатор вызовет макрос и получит в результат вот такой код:
(setq square (lambda (x) (begin (princ x) (* x x))))
Он его выполнит и мы получим функцию square.
Сразу скажу, квазиквот и всякой прочей дряни не будет.
Почему dynamic scoping?
Проще реализовать я думаю.
Конечно же это будет огромным минусом, потому что FEXPR может сожрать переменные функции, но lexical scoping можете добавить по своему желанию, это достаточно просто.
Реализуем парсер и лексер.
Сразу скажу - лексер это пряма копия из lis.py - это интерпретатор LISP от Питера Норвига, которым я вдохновлялся и вдохновляюсь.
Кстати вот его код:
def read(s): return s.replace('(',' ( ').replace(')',' ) ').replace('\n', ' ').split()
Логика проста:
Делаем пробелы во круг скобок.
Заменяем переносы строк на пробелы.
В конце делаем split и превращаем это чудо в список который прочитает парсер.
Тест (копировал из REPL):
>>> test = """(defun square (x) (* x x)""" >>> read(test) ['(', 'defun', 'square', '(', 'x', ')', '(', '*', 'x', 'x', ')'] >>>
Как видим логика верна.
Теперь парсер.
Вот его код:
def parse(tokens): stack = [[]] for token in tokens: if token == '(': stack.append([]) elif token == ')': completed = stack.pop() if stack: stack[-1].append(completed) else: return completed else: stack[-1].append(atom(token)) if len(stack) == 1 and len(stack[0]) == 1: return stack[0][0] return stack[0] def atom(token): try: return int(token) except: try: return float(token) except: return token
На самом деле это один из самых костыльных строчек кода, но проще говоря - я сделал TCO реализацию парсера который делал Питер Норвиг.
atom работает таким способом:
Попытка преобразовать в int и вернуть -> попытка преобразовать в float и вернуть -> вернуть как есть.
Попытка объяснить парсер:
1. Сначала создаём пустой список в котором само выражение итоговое.
2. Начинаем перебирать токены (слова, скобки, числа, символы) по порядку.
3. Если текущий токен это '(':
Мы начинаем новый внутренний список.
Кладём этот новый пустой список в стек.
4. Если текущий токен это ')':
Заканчиваем текущий внутренний список.
Достаём его из стека.
Добавляем этот готовый список в предыдущий список.
5. Если текущий токен не скобка - превращаем его в атом.
6. Когда все токены закончились:
Смотрим, что осталось в хранилище.
Если там ровно один список и в нём ровно один элемент — возвращаем этот элемент (не список).
Иначе возвращаем главный список как есть.
Извините что эта попытка объяснить наполовину от ИИ, но я тоже редактировал это объяснение.
Окружение нашего интерпретатора.
Эта одна из самый главных часть, без которой бы мы не могли хранить переменные.
Давайте я предоставлю вам код для реализации класса Env:
class Env: def __init__(self): self.env = {} self.macros = [] def add(self, name, value): self.env[name] = value def get(self, name): if name in self.env: return self.env[name] raise Exception(f'what? (i dont know it: "{name}")') def delete(self, name): if not name in self.env: raise Exception(f'what? (i dont know it: "{name}")') elif name in self.macros: self.macros.remove(name) del self.env[name]
Это самый обычный Env в мире.
add(name, value) - создать запись в env.
get(name) - попытаться найти переменную в env.
delete(name) - удалить запись в env и в макросах (если есть).
Думаю здесь нужен GC, но его можете добавить сами.
Я думаю для статьи тут больше нечего описать.
Трамплин для TCO.
Мы реализуем для нашего интерпретатора TCO на трамплинах.
Думаю, это не чем не примечательная реализация TCO как TCO в виде самодельного стека.
class Thunk: def __init__(self, func, *args): self.func = func self.args = args def bounce(self): return self.func(*self.args) #... скоро посреди этих двух элементах будет интерпретатор. def trampoline(ast, env): result = eval(ast, env) while type(result) is Thunk: result = result.bounce() return result
Вот как оно работает.
Thunk - это та самая часть которая спасает стек.
Туда мы будем передавать либо lambda: res, либо eval, body, env.
init просит любое количество аргументов и просит функцию.
bounce вызывает функцию которую мы ранее передавали, а после возвращает её результат.
trampoline просит наше AST и любой env, после в начале выполняет eval (наш будущий интерпретатор) и крутит в цикле пока тип данных у result = Thunk.
После цикла соответственно возвращает результат.
Сам интерпретатор.
Вот щас пойдёт самое мясо ;)
Каждый результат кроме вызова функции мы должны возвращать как Thunk.
"Но почему же кроме вызова функции?" - вы спросите скорее всего.
Ответ таков - когда мы создаем функцию то она возвращает Thunk(eval, body, env).
Того даже вызов функции возвращает Thunk теоретически.
Нечего больше не могу сказать, код в студию:
def eval(ast, env): if type(ast) is str: return env.get(ast) elif type(ast) is not list: return ast if ast == []: return -1 op, *args = ast if op == 'quote': return Thunk(lambda: args[0]) elif op == 'setq': var, val_expr = args val = trampoline(val_expr, env) env.add(var, val) return val elif op == 'if': test, a, b = args test = trampoline(test, env) return Thunk(eval, a if test else b, env) elif op == 'foreach': name, obj, body = args res = False obj = trampoline(obj, env) for i in obj: env.add(name, i) res = trampoline(body, env) return Thunk(lambda: res) elif op == 'loop': cond, body = args res = False while trampoline(cond, env): res = trampoline(body, env) return Thunk(lambda: res) elif op == 'begin': res = False for i in args: res = trampoline(i, env) return Thunk(lambda: res) elif op == 'lambda': args_names, body = args def closure(*a): for i in range(len(args_names)): env.add(args_names[i], a[i]) return Thunk(eval, body, env) return closure elif op == 'macro': name = args[0] if '.' in args[1]: fixed = [] rest = None for a in args[1]: if a == '.': rest = True continue if rest is True: rest = a break fixed.append(a) args_names = fixed rest_name = rest body = args[2] else: args_names = args[1] rest_name = None body = args[2] def macro(*a): for i, arg_name in enumerate(args_names): env.add(arg_name, a[i]) if rest_name: env.add(rest_name, list(a[len(args_names):])) return trampoline(body, env) env.add(name, macro) if not name in env.macros: env.macros.append(name) return macro elif op == 'expand': cmd = args[0] name = cmd[0] return trampoline(name, env)(*cmd[1:]) proc = trampoline(op, env) if op in env.macros: return trampoline(proc(*args), env) vals = [trampoline(arg, env) for arg in args] return proc(*vals)
Как можно заметить setq не возвращает Thunk.
Но... Сам val то Thunk возвращает - короче говоря такая же ситуация как с вызовом функции.
Когда мы вызываем функцию то первым делом интерпретатор выполняет op потому что op может быть (lambda (x) (* x x)) и мы получаем лямбду.
После проверяем - нету ли op в макросах?
Если он есть - тупо запускаем код из результата proc(*args) (где *args - те невычисленные аргументы).
Если его нету в макросах - вычисляем аргументы и вызываем proc с этими аргументами.
Вот почему это не полный TCO:
Посмотрите на эту строку:
[trampoline(arg, env) for arg in args]
К примеру вызов такой:
(* n (fact (- n 1)))
Чтобы вычислить * ему нужно в начале найти переменную n. Это окей.
Но чтобы вычислить второй аргумент - ему нужно вычислить себя самого который будет вычислять * и который тоже будет вычислять самого себя ...
Хвостовой вызов же в начале вычислит (- n 1), после вычислит (* n acc) и только потом уже вызовет себя, что можно оптимизировать.
Макросы - самая болезненная часть в начале.
Короче как то находим все эти аргументы нужные, и как то оборачиваем их в функцию macro.
expand легко понять надеюсь.
setq и другие тоже легко понять.
Интерпретатор сам легкий, если что-то не понятно - пишите в комментарии. ...Но нам не хватает одной части.
Встроенные функции.
Вот они вместе с основном env:
def rem(lst, el): new_lst = [] for i in lst: if i != el: new_lst.append(i) return new_lst def apply_binop(op, *args): if len(args) == 1: return args[0] result = args[0] for arg in args[1:]: result = op(result, arg) return result def apply_relop(op, *args): if len(args) <= 1: return True prev = args[0] for curr in args[1:]: if not op(prev, curr): return False prev = curr return True evalenv = Env() evalenv.env.update({ 'list': lambda *x: list(x), 'nth': lambda ind, lst: lst[ind], '+': lambda *args: apply_binop(lambda a, b: a + b, *args), '-': lambda *args: apply_binop(lambda a, b: a - b, *args), '*': lambda *args: apply_binop(lambda a, b: a * b, *args), '/': lambda *args: apply_binop(lambda a, b: a / b, *args), '=': lambda *args: apply_relop(lambda a,b: a == b, *args), '/=': lambda *args: not apply_relop(lambda a,b: a == b, *args) if len(args) > 1 else True, '<': lambda *args: apply_relop(lambda a,b: a < b, *args), '>': lambda *args: apply_relop(lambda a,b: a > b, *args), '<=': lambda *args: apply_relop(lambda a,b: a <= b, *args), '>=': lambda *args: apply_relop(lambda a,b: a >= b, *args), '//': lambda *args: apply_binop(lambda a, b: a // b, *args), '%': lambda *args: apply_binop(lambda a, b: a % b, *args), 'append': lambda lst, el: lst + el, 'snoc': lambda lst, el: lst + [el], 'remove': lambda lst, el: rem(lst, el), 'car': lambda lst: lst[0], 'cdr': lambda lst: lst[1:], 'cons': lambda el, lst: [el] + lst, "princ": lambda val: print(val), 't': True, 'nil': False, 'null': [], 'null?': lambda val: val is False or val == [], 'list?': lambda val: type(val) is list, 'int?': lambda val: type(val) is int, 'str?': lambda val: type(val) is str, 'type-of': lambda val: type(val).__name__, 'length': lambda val: len(val), 'str-type': str, 'int-type': int, 'list-type': list, 'apply': lambda func, args: func(*args) })
Это самые обычные стандартные функции.
Думаю, половина них есть в спецификациях и которых нет - они понятны.
Время теста!
Время теста нашего диалекта.
Соберём всё в один код
def read(s): return s.replace('(',' ( ').replace(')',' ) ').replace('\n', ' ').split() def parse(tokens): stack = [[]] for token in tokens: if token == '(': stack.append([]) elif token == ')': completed = stack.pop() if stack: stack[-1].append(completed) else: return completed else: stack[-1].append(atom(token)) if len(stack) == 1 and len(stack[0]) == 1: return stack[0][0] return stack[0] def atom(token): try: return int(token) except: try: return float(token) except: return token class Env: def __init__(self): self.env = {} self.macros = [] def add(self, name, value): self.env[name] = value def get(self, name): if name in self.env: return self.env[name] raise Exception(f'what? (i dont know it: "{name}")') def delete(self, name): if not name in self.env: raise Exception(f'what? (i dont know it: "{name}")') elif name in self.macros: self.macros.remove(name) del self.env[name] class Thunk: def __init__(self, func, *args): self.func = func self.args = args def bounce(self): return self.func(*self.args) def eval(ast, env): if type(ast) is str: return env.get(ast) elif type(ast) is not list: return ast if ast == []: return -1 op, *args = ast if op == 'quote': return Thunk(lambda: args[0]) elif op == 'setq': var, val_expr = args val = trampoline(val_expr, env) env.add(var, val) return val elif op == 'if': test, a, b = args test = trampoline(test, env) return Thunk(eval, a if test else b, env) elif op == 'foreach': name, obj, body = args res = False obj = trampoline(obj, env) for i in obj: env.add(name, i) res = trampoline(body, env) return Thunk(lambda: res) elif op == 'loop': cond, body = args res = False while trampoline(cond, env): res = trampoline(body, env) return Thunk(lambda: res) elif op == 'begin': res = False for i in args: res = trampoline(i, env) return Thunk(lambda: res) elif op == 'lambda': args_names, body = args def closure(*a): for i in range(len(args_names)): env.add(args_names[i], a[i]) return Thunk(eval, body, env) return closure elif op == 'macro': name = args[0] if '.' in args[1]: fixed = [] rest = None for a in args[1]: if a == '.': rest = True continue if rest is True: rest = a break fixed.append(a) args_names = fixed rest_name = rest body = args[2] else: args_names = args[1] rest_name = None body = args[2] def macro(*a): for i, arg_name in enumerate(args_names): env.add(arg_name, a[i]) if rest_name: env.add(rest_name, list(a[len(args_names):])) return trampoline(body, env) env.add(name, macro) if not name in env.macros: env.macros.append(name) return macro elif op == 'expand': cmd = args[0] name = cmd[0] return trampoline(name, env)(*cmd[1:]) proc = trampoline(op, env) if op in env.macros: return trampoline(proc(*args), env) vals = [trampoline(arg, env) for arg in args] return proc(*vals) def trampoline(ast, env): result = eval(ast, env) while type(result) is Thunk: result = result.bounce() return result def rem(lst, el): new_lst = [] for i in lst: if i != el: new_lst.append(i) return new_lst def apply_binop(op, *args): if len(args) == 1: return args[0] result = args[0] for arg in args[1:]: result = op(result, arg) return result def apply_relop(op, *args): if len(args) <= 1: return True prev = args[0] for curr in args[1:]: if not op(prev, curr): return False prev = curr return True evalenv = Env() evalenv.env.update({ 'list': lambda *x: list(x), 'nth': lambda ind, lst: lst[ind], '+': lambda *args: apply_binop(lambda a, b: a + b, *args), '-': lambda *args: apply_binop(lambda a, b: a - b, *args), '*': lambda *args: apply_binop(lambda a, b: a * b, *args), '/': lambda *args: apply_binop(lambda a, b: a / b, *args), '=': lambda *args: apply_relop(lambda a,b: a == b, *args), '/=': lambda *args: not apply_relop(lambda a,b: a == b, *args) if len(args) > 1 else True, '<': lambda *args: apply_relop(lambda a,b: a < b, *args), '>': lambda *args: apply_relop(lambda a,b: a > b, *args), '<=': lambda *args: apply_relop(lambda a,b: a <= b, *args), '>=': lambda *args: apply_relop(lambda a,b: a >= b, *args), '//': lambda *args: apply_binop(lambda a, b: a // b, *args), '%': lambda *args: apply_binop(lambda a, b: a % b, *args), 'append': lambda lst, el: lst + el, 'snoc': lambda lst, el: lst + [el], 'remove': lambda lst, el: rem(lst, el), 'car': lambda lst: lst[0], 'cdr': lambda lst: lst[1:], 'cons': lambda el, lst: [el] + lst, "princ": lambda val: print(val), 't': True, 'nil': False, 'null': [], 'null?': lambda val: val is False or val == [], 'list?': lambda val: type(val) is list, 'int?': lambda val: type(val) is int, 'str?': lambda val: type(val) is str, 'type-of': lambda val: type(val).__name__, 'length': lambda val: len(val), 'str-type': str, 'int-type': int, 'list-type': list, 'apply': lambda func, args: func(*args) })
Вот такой код ;)
Напишем небольшой REPL:
def repl(): print('lisp') while True: prompt = input('> ') print(trampoline(parse(read(prompt)), evalenv)) if __name__ == '__main__': repl()
В итоге я написал пару тестов на нём. Вот:
lisp > (setq fact (lambda (n acc) (if (= n 0) acc (fact (- n 1) (* n acc))))) <function eval.<locals>.closure at 0x0000012084363A60> > (fact 5 1) 120 > (macro define (lst body) (if (list? lst) (list (quote setq) (car lst) (list (quote lambda) (cdr lst) body)) (list (quote setq) lst body))) <function eval.<locals>.macro at 0x0000012084363CE0> > (define x 5) 5 > x 5 > (define (square x) (* x x)) <function eval.<locals>.closure at 0x0000012084363B00> > (square 5) 25 > (define (add x y) (+ x y)) <function eval.<locals>.closure at 0x0000012084375760> > (add 5 6) 11 >
Итог.
Я думаю мы написали с вами замечательный диалект LISP.
Я старался писать без багов и без орфографических ошибок. Если заметите - пожалуйста сообщите об этом.
P.S: На некоторых версиях float(".") может быть как 0.0, так что советую сделать проверку if token == ".": return token в функции atom.
