Для академических целей хочу использовать задачу по написанию интерпретатора LISP. Достаточно распространённая практика. Однако для моих целей LISP всё же слишком сложен, поэтому хочу его упростить. И так как не являюсь профессионалом этого языка, решил посоветоваться, не выкину ли я что-то необходимое.
Итак, я хочу сделать следующее:
1) из атомов оставить только целые десятичные числа и идентификаторы (состоящие из букв и символа подчёркивания);
2) убрать точечные пары вообще (их можно заменить списками из двух элементов);
3) оставить только эти функции: cons, car, cdr, if, defun, quote и ещё арифметические.
Останется ли данный язык полным по Тьюрингу? Не выкинул ли я что-то необходимое? Или наоборот, может оставил что-то избыточное?
Моя цель - сохранить дух LISP, максимально сократив синтаксис.
Насколько я могу судить, минимальный набор для лиспа следующий: undefined (McCarthy, 1960), true, false (McCarthy, 1960), if, atom, eq, cons, car, cdr, nil (McCarthy, 1960), quote, lambda (рекурсия через Y combinator) и множество атомов (без чисел).
(cons 1 2) => '(1 . 2)
А список из двух элементов это (cons 1 (cons 2 nil))
Так что, боюсь, без точечных пар вам не обойтись. Они имеют отношение не именно к "парам элементов", а к конструированию списковых ячейкеек. Попробуйте выполнить (cons 1 (cons 2 3)) и убедитесь.
Кстати, упомянутый nil (ну и соответственно T) вам тоже понадобится.
Обязательна возможность сравнения. Не исключаю, что вы её присовокупили к арифметическим функциям, но сравнение логических значений тоже дело совершенно необходимое.
Ну и наконец необходима возможность отличать список от атома. Насколько помню, atomp либо consp обязательно включается в ядро лисп. Это вроде как не влияет на тьюринг-полноту, но реализовать это вне ядра, в виде функции с помощью примитивов не получится.
> (cons 1 2) => '(1 . 2)
Я знаю это. И что список определяется именно через точечные пары: список = NIL | "(", S-выражение, ".", список, ")".
Я же как раз хочу заменить точечные пары на список из двух элементов, и тогда (cons 1 2) => `(1 2), а список будет определяться как NIL | "(", S-выражение, {" ", S-выражение}, ")".
Вроде бы это ничего существенно не изменит с точки зрения использования языка. А парсинг существенно упростится.
> Обязательна возможность сравнения.
Верно, я включил функции сравнения в арифметические. И есть идея полностью отказаться от логического типа, а сделать как в C: 0 - это ложь, а 1 - истина. Ну и пустой список тоже ложь.
> Ну и наконец необходима возможность отличать список от атома.
А зачем? Я, честно говоря, не совсем понимаю области применения этой функции. Наверное в написании макросов она полезна, но у меня их не будет.
Не понял вашего совета. Clojure - мощный современный диалект LISP, расширяющий его в сравнении с классической версией. А мне нужно напротив, упростить язык.
По тьюрингу Лисп останется полным даже если в нём оставить одну lambda.
И сам по себе Лисп является очень простым языком. Не хотите реализовывать самостоятельно всякие плавающие точки и строки — пишите интерпретатор на самом же Лиспе.
з.ы. сам в л\испоподобных языках пока полный чайник, поэтому не знаю, насколько этот диалект, что я дал ссыль подходит под задачу) но раз микро, значит там оставлено тока самое необходимое - по идее)
Простой
