Всем привет! Сегодня мы с вами сделаем реализацию LISP'а. Конечно же не полного.
Возможно, когда то я доведу этот лисп до ума и напишу новую статью... Но не обещаю.
История LISP'а вкратце
Перед тем как писать, давайте я введу вас в историю LISP'а.
Он был создан Джоном Маккарти в 1958 году (вроде бы).
И в 1960-ом он опубликовал работу по лиспу под названием "Рекурсивные функции символических выражений и их машинное вычисление" (английская версия: "Recursive Functions of Symbolic Expressions and Their Computation by Machine").
И пошло поехало... Там к примеру LISP в России ну и всё в таком роде.
Потом в 1976 ОПЯТЬ в MIT создают новый диалект LISP'а под названием "Scheme". Ну и так далее. Я не хочу объяснять историю в полной версии. Для этого нужна новая статья.
Схема реализации (опять какая-то схема...)
Во первых он будет не компилируемым ведь с компилятором для LISP'а нужно ещё дальше понимать LISP. А будет интерпретируемым.
Схема стандартная.
Лексер: просто превращает строку (к примеру (+ 3 2)) в " ( + 3 2 ) ")
Парсер: превращает токены в список (к примеру: ['+', '3', '2'])
Интерпретатор: ну, выполняет результат парсера (AST)
Также env станет впервые за все мои статьи (я их убрал) не словарём а классом.
Первые две стадии
Почитав прошлый заголовок вы поймёте что это очень легко.
Но, начнём мы не с лексера а с типов данных.
Они нужны для красоты, хоть это звучит как анти паттерн.
Их очень мало. Всего 3:
Symbol: символ, к примеру hello
Real: хотел назвать float, ну короче 3.14 к примеру
Number: просто цифра. К примеру: 55
Вот реализация этих типов данных:
Symbol = str #символ
Real = float #число с плавающей точкой
Number = int #просто число
Это ещё не всё. Также в лиспе есть атомы. Это либо число, либо число с плавающей точкой, либо символ.
Вот реализация этой функции:
def atom(val):
try:
return Number(val)
except:
try:
return Real(val)
except:
return Symbol(val)
Она простая.
Вот концепция функции:
-
Попробуй преобразовать значение в число.
-
Нет, не получилось, пробуй в float.
Тоже не получилось. Это символ.
-
Вот такая вот функция.
Перейдем к лексеру:
Он двухстрочный.
Вот реализация:
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 |
Объявить переменную (пример: (def x 5)) |
quote |
Вернуть то что идёт после quote. (пример: (quote hello, world!)) |
if |
Условие. Пример: (if (= 3 3) (1) (2)) То есть: (if (условие) (если истинно) (иначе)) |
lambda |
Процедура. Пример: (lambda x (* x x)) |
begin |
Вычисляет каждое выражение и возвращает результат последнего. Пример: (begin (def x 5) (+ x 5)) |
dict |
Делает словарь. Пример: (dict (a 1) (b 2)) |
t |
Истина (true или truth) |
nil |
Ложь или ничего |
; |
Комментарий. Пример: ;hello world |
(proc *args) |
Вызов функции если это не переменная. Пример: (square 5). Если же переменная: вернуть её значение. |
Вроде бы всё легко. Осталось реализовать:
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 который лучше этого и покажете как такой же сделать.
Но вообще, статья вроде бы нормальная.
Так что всем пока!
Так же спасибо Питеру Норвигу за идею такого простого лексера и парсера, вот ссылка:
Комментарии (14)
edyatl
08.07.2025 17:48Забавно. Существует ядро Clojure (современный диалект LISP) для Jupyter и можно в привычном блокноте писать на лиспе. И есть Babashka - интерпретатор Clojure для терминала для однострочников и скриптов - классная штука если нравится LISP.
vadimr
08.07.2025 17:48if name == 'if': return eval(ast[2] if eval(ast[1]) else eval(ast[3]))
Что-то у вас тут со вложенностью
eval
напутано.А посмотрел я туда, потому что у вас по синтаксису Лиспа лишние скобки в форме
if
:(if (= n 1) (1) (* n (fac (- n 1)))))
(1)
по кашруту должно быть без скобок, потому что это не вычислимая форма, а просто литерал1
, значение которого равно единице.Так как вы реализовали Лисп-1, то семантика формы
(1)
заключается в том, чтобы выполнить значение единицы, то есть число 1, как код. Что невозможно.SystemSoft Автор
08.07.2025 17:48Он и без скобок нормально вычисляет. Просто у меня боязнь что не заработает так.
vadimr
08.07.2025 17:48Я к тому, что со скобками не должно бы работать. Вы там перестраховались немножко на входе в
eval
сtry
.SystemSoft Автор
08.07.2025 17:48Ну, я так понял мне надо было убрать этот код:
if type(name) == int or type(name) == float: return name
FlyingDutchman2
08.07.2025 17:48Функция rem имеет побочный эффект, а именно удаляется элемент из списка lst. Это точно то, что вы хотели? В этом случае код функции можно сократить:
def rem(lst, el): lst.remove(el) return lst
sergey-gornostaev
08.07.2025 17:48Уже есть реализация Lisp на Python и довольно хорошая - Hy.
SystemSoft Автор
08.07.2025 17:48Да, диалект нормальной но он превращает код в Python AST и вроде дальше это AST выполняет Python. А у меня собственный интерпретатор.
SystemSoft Автор
извините за заголовок "интерпретатор", я там просто нечего не объяснил