Всем привет! Сегодня мы с вами сделаем реализацию LISP'а. Конечно же не полного.

Возможно, когда то я доведу этот лисп до ума и напишу новую статью... Но не обещаю.

История LISP'а вкратце

Перед тем как писать, давайте я введу вас в историю LISP'а.

Он был создан Джоном Маккарти в 1958 году (вроде бы).

И в 1960-ом он опубликовал работу по лиспу под названием "Рекурсивные функции символических выражений и их машинное вычисление" (английская версия: "Recursive Functions of Symbolic Expressions and Their Computation by Machine").

И пошло поехало... Там к примеру LISP в России ну и всё в таком роде.

Потом в 1976 ОПЯТЬ в MIT создают новый диалект LISP'а под названием "Scheme". Ну и так далее. Я не хочу объяснять историю в полной версии. Для этого нужна новая статья.

Схема реализации (опять какая-то схема...)

Во первых он будет не компилируемым ведь с компилятором для LISP'а нужно ещё дальше понимать LISP. А будет интерпретируемым.

Схема стандартная.

1. Лексер: просто превращает строку (к примеру (+ 3 2)) в " ( + 3 2 ) ")

2. Парсер: превращает токены в список (к примеру: ['+', '3', '2'])

3. Интерпретатор: ну, выполняет результат парсера (AST)

Также env станет впервые за все мои статьи (я их убрал) не словарём а классом.

Первые две стадии

Почитав прошлый заголовок вы поймёте что это очень легко.

Но, начнём мы не с лексера а с типов данных.

Они нужны для красоты, хоть это звучит как анти паттерн.

Их очень мало. Всего 3:

1. Symbol: символ, к примеру hello

2. Real: хотел назвать float, ну короче 3.14 к примеру

3. Number: просто цифра. К примеру: 55

Вот реализация этих типов данных:

Symbol = str #символ
Real = float #число с плавающей точкой
Number = int #просто число

Это ещё не всё. Также в лиспе есть атомы. Это либо число, либо число с плавающей точкой, либо символ.

Вот реализация этой функции:

def atom(val):
    try:
        return Number(val)
    except:
        try:
            return Real(val)
        except:
            return Symbol(val)

Она простая.

Вот концепция функции:

1. Попробуй преобразовать значение в число.

   1. Нет, не получилось, пробуй в float.

      1. Тоже не получилось. Это символ.

Вот такая вот функция.

Перейдем к лексеру:

Он двухстрочный.

Вот реализация:

def lexer(string):
    return string.replace('(', ' ( ').replace(')', ' ) ').replace('\n', '\n').split()

Не хочу объяснять этот код. Он понятен.

Перейдём к парсеру.

Вот его код:

def parse(tokens):
    if len(tokens) == 0:
        raise SyntaxError('unexpected EOF while reading')
    token = tokens.pop(0)
    if token == '(':
        l = []
        while tokens[0] != ')':
            l.append(parse(tokens))
        tokens.pop(0)
        return l
    elif token == ')':
        raise SyntaxError('unexpected )')
    else:
        return atom(token)

Объясняю код:

Если токенов нет - ошибка.

Получаем токен. Если это ")" - тоже ошибка.

Если же "(" - то вычисляем это S-выражение и возвращаем результат.

Иначе - возвращаем атом токена.

Достаточно легко.

Переменные

Я говорил что на этот раз это не просто словарь. А класс.

Вот реализация:

class Env:
    def __init__(self):
        self.env = {}

    def add(self, name, value):
        self.env[name] = value

    def get(self, name):
        return self.env[name] if name in self.env else 0

add - добавить переменную.

get - получить переменную.

Почему я реализовал класс? Для нормально контроля а не для побочных эффектов.

Также реализуем класс для процедуры.

class Proc:
    def __init__(self, lambda_, args):
        self.args, self.lambda_ = args, lambda_

    def __repr__(self):
        return f'#<lambda {self.args}>'

Вы спросите почему я сделал именно класс? Потому что тут реализованы словари (пока как команда).

Первый аргумент - сама функция (лямбда).

Второй аргументы - аргументы функции (builtins если нужно).

А теперь - самый момент для функций и глобальных переменных.

Вот они:

old_eval = eval

def rem(lst, el):
    new_lst = []
    for i in lst:
        if i != el:
            new_lst.append(i)
    return new_lst

genv = Env()
genv.env = {
    'princ': Proc(lambda *x: print(*x), 'builtins'),
    'list': Proc(lambda *x: [*x], 'builtins'),
    'nth': Proc(lambda lst, ind: lst[ind], ['lst', 'ind']),
    '+': Proc(lambda first, sec: first + sec, ['first', 'sec']),
    '-': Proc(lambda first, sec: first - sec, ['first', 'sec']),
    '*': Proc(lambda first, sec: first * sec, ['first', 'sec']),
    '/': Proc(lambda first, sec: first / sec, ['first', 'sec']),
    '>': Proc(lambda first, sec: first > sec, ['first', 'sec']),
    '<': Proc(lambda first, sec: first < sec, ['first', 'sec']),
    '=': Proc(lambda first, sec: first == sec, ['first', 'sec']),
    '/=': Proc(lambda first, sec: first != sec, ['first', 'sec']),
    'py': Proc(lambda exp: old_eval(exp, globals() | genv.env), ['exp']),
    'getk': Proc(lambda dct, name: dct[name], ['dct', 'name']),
    'append': Proc(lambda lst, el: lst + [el], ['lst', 'el']),
    'remove': Proc(lambda lst, el: rem(lst, el), ['lst', 'el']),
    'car': Proc(lambda lst: lst[0], ['lst']),
    'cdr': Proc(lambda lst: rem(lst, lst[0]), ['lst']),
    'cons': Proc(lambda el, lst: [el] + lst, ['el', 'lst'])
}

Зачем функция rem? Потому что обычный lst.remove удаляет элемент навсегда а в лиспе возвращается список lst где нету этого элемента.

Зачем переменная old_eval? Потому что для интерпретатора нужна функция eval. А у нас есть поддержка пайтона.

/= это != если что.

genv - это сами глобальные переменные.

Функций тут много по этому закончим на этом.

Интерпретатор

Давайте с начало обсудим команды. Вот их таблица:

Вроде бы всё легко. Осталось реализовать:

def eval(ast):
    try:
        name = ast[0] if type(ast) != str else ast
    except:
        return ast
    if name == 'if':
        return eval(ast[2] if eval(ast[1]) else eval(ast[3]))
    elif name == 'def':
        name = ast[1]
        val = eval(ast[2])
        genv.add(name, val)
    elif name == 'lambda':
        args = ast[1]
        if type(args) != list:
            args = [args]
        return Proc(lambda *args: eval(ast[2]), args)
    elif name == 'quote':
        res = ''
        for i in ast[1:]:
            res += to_lisp(i) + ' '
        return res[0:-1]
    elif name == 'begin':
        res = 'NIL'
        for i in ast[1:]:
            res = eval(i)
        return res
    elif name == 'dict':
        res = {}
        for i in ast[1:]:
            name = i[0]
            val = eval(i[1])
            res[name] = val
        return res
    elif name == 'nil':
        return False
    elif name == 't':
        return True
    elif name == ';':
        pass
    else:
        fn = genv.get(name)
        if type(fn) != Proc:
            return fn
        args = [eval(i) for i in ast[1:]]
        if fn.args == 'builtins':
            return fn.lambda_(*args)
        cur = 0
        for i in fn.args:
            eval(parse(lexer(f'(def {i} {args[cur]})')))
            cur += 1
        return fn.lambda_(*args)

Конечно не самый лучший код, но он работает.

Сильно нету ничего такого сверхъестественного чего надо объяснять.

Попробуем наш код:

#где то в REPL
>>> eval(parse(lexer('(def square (lambda x (* x x)))')))
None
>>> eval(parse(lexer('(square 5)')))
25
>>> 

Чего то не хватает. Согласны? Не хватает строки которая похожа на LISP. Давайте реализуем эту функцию.

Вот её код:

def to_lisp(val):
    if isinstance(val, list):
        cur = 0
        for i in val:
            val[cur] = to_lisp(i)
            cur += 1
        return '(' + ' '.join(val) + ')'
    elif isinstance(val, bool) or val == None:
        if val == True:
            return 'T'
        return 'NIL'
    elif isinstance(val, dict):
        cur = 0
        res = '('
        for i in val.values():
            val[list(val.keys())[cur]] = to_lisp(i)
            res += list(val.keys())[cur] + ':' + to_lisp(i) + ' '
            cur += 1
        res = res[0:-1]
        return res + ')'
    return str(val)

Если список то это сделать, если это t или nil то это сделать... Ну в принципе функция понятна за исключением словарей.

Теперь пробуем но с другим кодом:

#где то в REPL
>>> to_lisp(eval(parse(lexer('(list 1 2 3)'))))
(1 2 3)
>>> (= 3 2)
NIL
>>> 

Теперь осталось сделать командную строку.

def repl():
    print('MyLISP 1.0')
    while True:
        try:
            print(eval(parse(lexer(input('> ')))))
        except:
            print('Error!')

Конечно же я реализовал более нормальный REPL но это тогда ещё больше кода.

Ну, момент истинны:

#где то в REPL
>>> repl()
MyLISP 1.0
> (list 1 2 3)
(1 2 3)
> (dict (a 1) (b 2))
(a:1 b:2)
> (def fac (lambda n (if (= n 1) 1 (* n (fac (- n 1))))))
NIL
> (fac 5)
120
> 

Готово.

Заключение

Я создал свой LISP и показал как сделать его. Вы создадите свой LISP который лучше этого и покажете как такой же сделать.

Но вообще, статья вроде бы нормальная.

Так что всем пока!

Так же спасибо Питеру Норвигу за идею такого простого лексера и парсера, вот ссылка:

https://norvig.com/lispy.html