Пишем свой диалект LISP

Привет, Хабр и читатели!

Сегодня я попытаюсь сделать с вами диалект LISP.

Я думаю, что я достаточно хорошо понимаю как его сделать.

Мы реализуем там TCO, FEXPR функции и dynamic scoping.

Как он будет выглядеть и на чём?

Язык написания - Python.

Думаю, на нём проще всего понимать такие проекты.

Я думаю что нам достаточно вот столько спец форм:

Будут 3 этапа:

1. Лексер.

2. Парсер.

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()

Логика проста:

1. Делаем пробелы во круг скобок.

2. Заменяем переносы строк на пробелы.

3. В конце делаем 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 в мире.

1. add(name, value) - создать запись в env.

2. get(name) - попытаться найти переменную в env.

3. 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.