Создаём свою легкую реализацию LISP’а на Python

Всем привет! Сегодня мы с вами сделаем реализацию 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