Программисты Лисп хвастаются, что Лисп - это мощный язык, который может быть создан из очень небольшого набора примитивных операций . Давайте воплотим эту идею в жизнь, играя в гольф переводчиком для диалекта под названием tinylisp.

Спецификация языка

В этой спецификации любое условие, результат которого описан как «неопределенный», может делать что-либо в вашем интерпретаторе: аварийно завершать работу, молча терпеть неудачу, генерировать случайный gobbldegook или работать как ожидалось. Ссылочная реализация в Python 3 доступна здесь .

Синтаксис

Лексемы в tinylisp являются (, )или любая строка из одного или нескольких печатаемых ASCII символов , кроме скобок или пространства. (Т.е. следующее регулярное выражение:. [()]|[^() ]+) Любой токен, состоящий полностью из цифр, является целочисленным литералом. (Нули в порядке.) Любой маркер , который содержит нецифровой символ, даже числовые выглядящие примерам нравятся 123abc, 3.14и -10. Все пробелы (включая, как минимум, символы ASCII 32 и 10) игнорируются, кроме случаев, когда они разделяют токены.

Программа tinylisp состоит из серии выражений. Каждое выражение представляет собой целое число, символ или s-выражение (список). Списки состоят из нуля или более выражений, заключенных в скобки. Разделитель между элементами не используется. Вот примеры выражений:

4
tinylisp!!
()
(c b a)
(q ((1 2)(3 4)))

Выражения, которые не являются правильно сформированными (в частности, имеют несопоставимые скобки), дают неопределенное поведение. (Референтная реализация автоматически закрывает открытые парены и прекращает анализ на непревзойденных закрытых паренах.)

Типы данных

Типы данных tinylisp - это целые числа, символы и списки. Встроенные функции и макросы также можно рассматривать как тип, хотя их формат вывода не определен. Список может содержать любое количество значений любого типа и может быть вложен произвольно глубоко. Целые числа должны поддерживаться как минимум от -2 ^ 31 до 2 ^ 31-1.

Пустой список - ()также называемый nil - и целое число 0- единственные значения, которые считаются логически ложными; все остальные целые числа, непустые списки, встроенные и все символы логически верны.

оценка

Выражения в программе оцениваются по порядку, и результаты каждого из них отправляются на стандартный вывод (подробнее о форматировании вывода позже).

• Целочисленный литерал оценивает сам по себе.
• Пустой список ()оценивает сам по себе.
• Список из одного или нескольких элементов оценивает его первый элемент и обрабатывает его как функцию или макрос, вызывая его с остальными элементами в качестве аргументов. Если элемент не является функцией / макросом, поведение не определено.
• Символ оценивается как имя, давая значение, связанное с этим именем в текущей функции. Если имя не определено в текущей функции, оно оценивается как значение, привязанное к нему в глобальной области видимости. Если имя не определено в текущей или глобальной области видимости, результат не определен (эталонная реализация выдает сообщение об ошибке и возвращает nil).

Встроенные функции и макросы

В тинилиспе есть семь встроенных функций. Функция оценивает каждый из своих аргументов, прежде чем применить к ним какую-либо операцию и вернуть результат.

• c- минусы [список правил]. Принимает два аргумента, значение и список, и возвращает новый список, полученный путем добавления значения в начале списка.
• h- голова ( машина , в терминологии Лисп). Принимает список и возвращает первый элемент в нем, или ноль, если задан ноль.
• t- tail ( cdr , в терминологии Lisp). Принимает список и возвращает новый список, содержащий все элементы, кроме первого, или ноль, если задано ноль.
• s- вычесть. Берет два целых числа и возвращает первое минус второе.
• l- меньше, чем. Занимает два целых числа; возвращает 1, если первое меньше второго, 0 в противном случае.
• e- равный. Принимает два значения одного типа (оба целых числа, оба списка или оба символа); возвращает 1, если два равны (или идентичны в каждом элементе), 0 в противном случае. Тестирование встроенных функций на равенство не определено (эталонная реализация работает как положено).
• v- Эвал. Берет один список, целое число или символ, представляющий выражение, и оценивает его. Например, делать (v (q (c a b)))то же самое, что делать (c a b); (v 1)дает 1.

«Значение» здесь включает любой список, целое число, символ или встроенную функцию, если не указано иное. Если функция указана как принимающая определенные типы, передача ее другим типам является неопределенным поведением, как и передача неверного числа аргументов (ссылочная реализация обычно дает сбой).

В tinylisp есть три встроенных макроса. Макрос, в отличие от функции, не оценивает свои аргументы перед применением к ним операций.

• q- цитата. Принимает одно выражение и возвращает его без оценки. Например, оценка (1 2 3)дает ошибку, потому что она пытается вызвать 1функцию или макрос, но (q (1 2 3))возвращает список (1 2 3). Оценка aдает значение, связанное с именем a, но (q a)дает само имя.
• i- если. Принимает три выражения: условие, выражение iftrue и выражение iffalse. Сначала оценивает состояние. Если результатом является ложь ( 0или ноль), вычисляется и возвращается выражение iffalse. В противном случае вычисляет и возвращает выражение iftrue. Обратите внимание, что выражение, которое не возвращается, никогда не оценивается.
• d- определ. Принимает символ и выражение. Оценивает выражение и связывает его с данным символом, рассматриваемым как имя в глобальной области видимости , а затем возвращает символ. Попытка переопределить имя должна потерпеть неудачу (молча, с сообщением или сбоем; эталонная реализация отображает сообщение об ошибке). Примечание: нет необходимости цитировать имя , прежде чем передать его d, хотя необходимо процитировать выражение , если это список или символ вы не хотите оценили: например, (d x (q (1 2 3))).

Передача неправильного количества аргументов в макрос является неопределенным поведением (сбой ссылочной реализации). Передача чего-то, что не является символом, в качестве первого аргумента dявляется неопределенным поведением (ссылочная реализация не выдает ошибку, но впоследствии на значение нельзя ссылаться).

Пользовательские функции и макросы

Начиная с этих десяти встроенных функций, язык можно расширять, создавая новые функции и макросы. У них нет выделенного типа данных; это просто списки с определенной структурой:

• Функция представляет собой список из двух элементов. Первый - это либо список из одного или нескольких имен параметров, либо одно имя, которое получит список любых аргументов, переданных функции (таким образом, учитывая функции переменной арности). Второе - это выражение, которое является телом функции.
• Макрос такой же, как функция, за исключением того, что он содержит nil перед именами параметров, что делает его списком из трех элементов. (Попытка вызвать трехэлементные списки, которые не начинаются с nil, является неопределенным поведением; эталонная реализация игнорирует первый аргумент и обрабатывает их как макросы.)

Например, следующее выражение - это функция, которая добавляет два целых числа:

(q               List must be quoted to prevent evaluation
 (
  (x y)          Parameter names
  (s x (s 0 y))  Expression (in infix, x - (0 - y))
 )   
)

И макрос, который принимает любое количество аргументов, вычисляет и возвращает первый:

(q
 (
  ()
  args
  (v (h args))
 )
)

Функции и макросы можно вызывать напрямую, привязывать к именам с помощью dи передавать другим функциям или макросам.

Поскольку тела функций не выполняются во время определения, рекурсивные функции легко определить:

(d len
 (q (
  (list)
  (i list                      If list is nonempty
   (s 1 (s 0 (len (t list))))  1 - (0 - len(tail(list)))
   0                           else 0
  )
 ))
)

Обратите внимание, однако, что вышеприведенное не является хорошим способом определения функции длины, потому что она не использует ...

Хвостовая рекурсия

Хвостовая рекурсия является важной концепцией в Лиспе. Он реализует определенные виды рекурсии в виде циклов, таким образом сохраняя стек вызовов небольшим. Ваш интерпретатор tinylisp должен реализовать правильную рекурсию хвостового вызова!

• Если возвращаемое выражение пользовательской функции или макроса является вызовом другой пользовательской функции или макроса, ваш интерпретатор не должен использовать рекурсию для оценки этого вызова. Вместо этого он должен заменить текущую функцию и аргументы новой функцией и аргументами и выполнить цикл, пока цепочка вызовов не будет разрешена.
• Если возвращаемое выражение пользовательской функции или макроса является вызовом i, не следует сразу оценивать выбранную ветвь. Вместо этого проверьте, является ли это вызовом другой пользовательской функции или макроса. Если это так, поменяйте местами функцию и аргументы, как указано выше. Это относится к сколь угодно глубоко вложенным вхождениям i.

Хвостовая рекурсия должна работать как для прямой рекурсии (функция вызывает себя), так и для косвенной рекурсии (функция aвызывает функцию, bкоторая вызывает [и т. Д.], Которая вызывает функцию a).

Хвостово-рекурсивная функция длины (с вспомогательной функцией len*):

(d len*
 (q (
  (list accum)
  (i list
   (len*
    (t list)
    (s 1 (s 0 accum))
   )
   accum
  )
 ))
)
(d len
 (q (
  (list)
  (len* list 0)
 ))
)

Эта реализация работает для произвольно больших списков, ограниченных только максимальным целочисленным размером.

Объем

Параметры функции - это локальные переменные (на самом деле это константы, так как они не могут быть изменены). Они находятся в области видимости, пока выполняется тело этого вызова этой функции, и выходят из области видимости во время любых более глубоких вызовов и после возврата функции. Они могут «скрывать» глобально определенные имена, делая глобальное имя временно недоступным. Например, следующий код возвращает 5, а не 41:

(d x 42)
(d f
 (q (
  (x)
  (s x 1)
 ))
)
(f 6)

Однако следующий код возвращает 41, потому что xна уровне вызова 1 недоступен с уровня вызова 2:

(d x 42)
(d f
 (q (
  (x)
  (g 15)
 ))
)
(d g
 (q (
  (y)
  (s x 1)
 ))
)
(f 6)

Единственными именами в области действия в любой момент времени являются: 1) локальные имена выполняемой в настоящее время функции, если таковые имеются, и 2) глобальные имена.

Требования к подаче

Вход и выход

Ваш интерпретатор может читать программу из стандартного ввода или из файла, указанного с помощью стандартного ввода или аргумента командной строки. После оценки каждого выражения он должен вывести результат этого выражения в стандартный вывод с завершающим переводом строки.

• Целые числа должны быть выведены в наиболее естественном представлении вашего языка реализации. Могут быть выведены отрицательные целые числа с ведущими знаками минус.
• Символы должны выводиться в виде строк без окружающих кавычек или экранированных символов .
• Списки должны выводиться со всеми элементами, разделенными пробелами и заключенными в скобки. Пространство внутри скобок является необязательным: (1 2 3)и ( 1 2 3 )оба приемлемые форматы.
• Вывод встроенных функций и макросов - неопределенное поведение. (Ссылочная интерпретация отображает их как <built-in function>.)

Другие

Справочный интерпретатор включает среду REPL и возможность загружать модули tinylisp из других файлов; они предоставляются для удобства и не требуются для этой задачи.

Контрольные примеры

Тестовые случаи разделены на несколько групп, так что вы можете тестировать более простые, прежде чем переходить к более сложным. Тем не менее, они также будут отлично работать, если вы свалите их все в один файл вместе. Только не забудьте удалить заголовки и ожидаемый результат перед запуском.

Если вы правильно реализовали рекурсию хвостового вызова, последний (многокомпонентный) контрольный пример вернется без переполнения стека. Эталонная реализация вычисляет его примерно за шесть секунд на моем ноутбуке.

Python 2, 685 675 660 657 646 642 640 байт

import sys,re
E=[]
G=zip("chtsle",[eval("lambda x,y=0:"+f)for f
in"[x]+y (x+[E])[0] x[1:] x-y +(x<y) +(x==y)".split()])
def V(e,L=E):
 while 1:
    try:return e and int("0%s"%e)
    except:A=e[1:]
    if""<e:return dict(G+L).get(e,e)
    f=V(e[0],L)
    if""<f:
     if f in"iv":t=V(A[0],L);e=(e[~bool(t)],t)[f>"u"];continue
     if"e">f:G[:]+=(A[0],V(A[1],L)),
     return A[0]
    if[]>f or f[0]:A=[V(a,L)for a in A]
    if[]>f:return f(*A)
    P,e=f[-2:];L=([(P,A)],zip(P,A))[P<""]
F=lambda x:V<x<""and"(%s)"%" ".join(map(F,x))or"%s"%x
for t in re.sub("([()])"," \\1 ",sys.stdin.read()).split():
 if")"==t:t=E.pop()
 if"("==t:E+=[],
 elif E:E[-1]+=t,
 else:print F(V(t))

Считывает ввод из STDIN и записывает вывод в STDOUT.

Хотя это и не обязательно, интерпретатор поддерживает нулевые функции и макросы и оптимизирует хвостовые вызовы, выполняемые через v.

объяснение

анализ

Для того, чтобы разобрать вход, мы сначала окружаем каждое вхождение (и )с пробелами, и разделить полученную строку на слова; это дает нам список токенов. Мы поддерживаем стек выражений E, который изначально пуст. Сканируем токены по порядку:

• если мы сталкиваемся с a (, мы помещаем пустой список в начало стека выражений;
• если мы сталкиваемся с a ), мы выталкиваем значение в верхнюю часть стека выражений и добавляем его в список, который ранее был ниже его в стеке;
• в противном случае мы добавляем текущий токен в виде строки в список в верхней части стека выражений (на этом этапе мы сохраняем целые числа в виде строк и анализируем их во время оценки.)

Если при обработке обычного токена или после извлечения выражения из стека из-за того ), что стек выражений пуст, мы находимся на выражении верхнего уровня и оцениваем значение, которое мы иначе добавили бы, используя V()и выведите результат, отформатированный соответствующим образом F().

оценка

Мы поддерживаем глобальную область видимости Gв виде списка пар ключ / значение. Изначально он содержит только встроенные функции (но не макросы и не v, которые мы рассматриваем как макрос), которые реализованы как лямбды.

Оценка происходит внутри V(), который принимает выражение для оценки, eи локальная область, L, который тоже, список пар ключ / значение (при оценке выражения верхнего уровня, локальная область пуст.) Внутренности V()живой внутри бесконечного цикла, как мы выполняем оптимизацию хвостового вызова (TCO), как будет объяснено позже.

Мы обрабатываем в eсоответствии с его типом:

• если это пустой список или строка, конвертируемая в int, мы возвращаем его немедленно (возможно, после преобразования в int); иначе,

• если это строка, мы ищем ее в словаре, построенном на основе объединения глобальной и локальной областей. Если мы находим ассоциированное значение, мы его возвращаем; в противном случае, eдолжно быть имя встроено макрос (т.е. q, i, dили v), и мы возвращаем его без изменений. В противном случае, если eэто не строка,

• eявляется (непустым) списком, то есть вызовом функции. Мы оцениваем первый элемент списка, то есть выражение функции, вызывая V()рекурсивно (используя текущую локальную область видимости); мы называем результат f. Остальная часть списка A, это список аргументов. fможет быть только строкой, в этом случае это встроенный макрос (или функция v), лямбда, в этом случае это встроенная функция или список, и в этом случае это пользовательская функция или макрос.

  Если fэто строка, т. Е. Встроенный макрос, мы обрабатываем ее на месте. Если это макрос iилиv , мы оцениваем его первый операнд и выбираем второй или третий операнд соответственно, в случае i, или используем результат первого операнда, в случае v; вместо рекурсивной оценки выбранного выражения, что приведет к победе над TCO, мы просто заменим eуказанное выражение и перейдем к началу цикла. Если fэто макрос d, мы добавляем пару, первый элемент которой является первым операндом, а второй элемент является результатом вычисления второго операнда, в глобальную область Gи возвращаем первый операнд. В противном случае fэто макрос q, и в этом случае мы просто возвращаем его операнд напрямую.

  Иначе, если fэто лямбда или список, первым элементом которого не является (), то это ненулевая функция, а не макрос, и в этом случае мы оцениваем ее аргументы, т. Е. Элементы A, и заменяем Aна результат.

  Если fэто лямбда, мы называем его, передавая ему распакованные аргументы A, и возвращаем результат.

  В противном случае, fэто список, то есть пользовательская функция или макрос; его список параметров является вторым по последнему элементу, а его тело - последним элементом. Как и в случае с макросами, iи vдля выполнения TCO мы не рекурсивно оцениваем тело, а заменяем eего телом и переходим к следующей итерации. В отличие от iи v, однако, мы также заменяем локальную область действия Lновой локальной областью действия функции. Если список параметров,P , по сути, является списком, новая локальная область создается путем сжатия списка параметров со списком Pаргументов A; в противном случае мы имеем дело с функцией с переменным значением, и в этом случае новая локальная область имеет только один элемент - пару (P, A).

РЕПЛ

Если вы хотите поиграть с ним, вот версия REPL переводчика. Он поддерживает переопределение символов и импорт файлов с помощью аргументов командной строки или (import <filename>)макроса. Чтобы выйти из интерпретатора, завершите ввод (обычно это Ctrl + D или Ctrl + Z).

try:import sys,re,readline
except:0
E=[];G=zip("chtsle",[eval("lambda x,y=0:"+f)for f
in"[x]+y (x+[E])[0] x[1:] x-y +(x<y) +(x==y)".split()])
def V(e,L=E):
 while 1:
    try:return e and int("0%s"%e)
    except:A=e[1:]
    if""<e:return dict(G+L).get(e,e)
    f=V(e[0],L)
    if""<f:
     if f in"iv":t=V(A[0],L);e=(e[~bool(t)],t)[f>"u"];continue
     if"e">f:G[:]+=(A[0],V(A[1],L)),
     elif"j">f:X(open(str(A[0])).read())
     return A[0]
    if[]>f or f[0]:A=[V(a,L)for a in A]
    if[]>f:return f(*A)
    P,e=f[-2:];L=([(P,A)],zip(P,A))[P<""]
F=lambda x:V<x<""and"(%s)"%" ".join(map(F,x))or"%s"%x
def X(s,v=0):
 for t in re.sub("([()])"," \\1 ",s).split():
    if")"==t:t=E.pop()
    if"("==t:E[:]+=[],
    elif E:E[-1]+=t,
    else:
     x=V(t)
     if v:print F(x)
for f in sys.argv[1:]:X("(g %s)"%f)
while 1:
 try:X(raw_input(">."[[]<E]*3+" "),1)
 except EOFError:break
 except KeyboardInterrupt:E=[];print
 except Exception as e:print"Error: "+e.message

А вот пример сеанса, реализующего сортировку слиянием:

>>> (d let d) (d if i) (d head h) (d tail t) (d prepend c) (d less l)
let
if
head
tail
prepend
less
>>>
>>> (let list (q (x... x...)))
list
>>> (let lambda (q (() (params body) (list params body))))
lambda
>>> (let def (q (() (name params body) (
...     v (list (q let) name (list (q lambda) params body))
... ))))
def
>>>
>>> (def else(body) body)
else
>>> (def or(x y) ( if x x y ))
or
>>> (def and(x y) ( if x y x ))
and
>>>
>>> (def front-half(L) ( front-half/impl L L ))
front-half
>>> (def front-half/impl(L M) (
...     if M (
...         prepend (head L)
...                 (front-half/impl (tail L) (tail (tail M)))
...     ) (else
...         ()
...     )
... ))
front-half/impl
>>>
>>> (def back-half(L) ( back-half/impl L L ))
back-half
>>> (def back-half/impl(L M) (
...     if M (
...         back-half/impl (tail L) (tail (tail M))
...     ) (else
...         L
...     )
... ))
back-half/impl
>>>
>>> (def merge(L M comp) (
...     if (and L M) (
...         if (comp (head M) (head L)) (
...             prepend (head M) (merge L (tail M) comp)
...         ) (else (
...             prepend (head L) (merge (tail L) M comp)
...         ))
...     ) (else (
...         or L M
...     ))
... ))
merge
>>>
>>> (def sort(L comp) (
...     if (and L (tail L)) (
...         merge (sort (front-half L) comp)
...               (sort (back-half L) comp)
...               comp
...     ) (else
...         L
...     )
... ))
sort
>>>
>>>
>>> (let my-list (list 4 7 2 5 9 1 6 10 8 3))
my-list
>>> my-list
(4 7 2 5 9 1 6 10 8 3)
>>> (sort my-list less)
(1 2 3 4 5 6 7 8 9 10)
>>> (sort my-list (lambda(x y) ( less y x )))
(10 9 8 7 6 5 4 3 2 1)

C (GNU), 1095 байтов

Большая часть действия происходит в гигантской vфункции. Вместо явной реализации хвостовой рекурсии, vона структурирована так, что многие вызовы изv доv будет обрабатываться путем оптимизации хвостовой рекурсии ССЗА. Там нет сборки мусора.

Это интенсивно использует расширения GCC, поэтому его можно скомпилировать только с помощью gcc (используйте команду gcc -w -Os tl.c). Он также использует некоторые scanfрасширения, которые не были доступны в Windows, которые я обычно использую. Перспектива написания парсера со стандартом scanfбыла настолько ужасна, что я вместо этого использовал виртуальную машину Linux, чтобы протестировать программу. Разбор безscanf классов символов, вероятно, добавил бы более 100 байтов.

#define O(...)({o*_=malloc(32);*_=(o){__VA_ARGS__};_;})
#define P printf
#define F(I,B)({for(I;x->c;x=x->l)B;})
#define Z return
typedef struct o{struct o*n,*l,*c;int i,t;}o;E(o a,o b){Z
a.n?!strcmp(a.n,b.n):a.c?b.c&&E(*a.c,*b.c)&E(*a.l,*b.l):!b.c&a.i==b.i;}p(o*x){x->t?P("%d ",x->i):x->n?P("%s ",x->n):F(P("("),p(x->c);P(")"));}o*x,G,N;*C(o*h,o*t){Z
O(c:h,l:t);}o*v(o*x,o*e){o*W(o*l,o*e){Z
l->c?C(v(l->c,e),W(l->l,e)):&N;}o*y,*a,*f;int t;Z
x->c?y=v(x->c,e),x=x->l,t=y->i,t?9/t?a=v(x->c,e),t>7?(t>8?a->c:a->l)?:a:t>6?v(a,e):t<6?x=v(x->l->c,e),t>4?C(a,x):O(t:1,i:t>3?E(*a,*x):t>2?a->i<x->i:a->i-x->i):v((a-&N&&!a->t|a->i?x:x->l)->l->c,e):(t&1&&d(x->c->n,v(x->l->c,e)),x->c):(y->l->l->l?y=y->l:(x=W(x,e)),a=y->c,v(y->l->c,a->n?O(n:a->n,c:x,l:&G):F(f=&G,(f=O(n:a->c->n,c:x->c,l:f),a=a->l);f))):x->n?e->n?strcmp(x->n,e->n)?v(x,e->l):e->c:e:x;}d(o*n,o*x){*v(O(n:""),&G)=(o){n:n,c:x,l:O()};}*R(h){char*z,*q;Z
scanf(" %m[^ \n()]",&q)>0?h=strtoul(q,&z,10),C(*z?O(n:q):O(t:1,i:h),R()):~getchar()&1?q=R(),C(q,R()):&N;}main(i){for(;++i<12;)d(strndup("slecivthqd"+i-2,1),O(i:i));F(x=R(),p(v(x->c,&G)));}

Semi-ungolfed

typedef struct o o;
struct o {
    char* n;
    o* l, //next in this list
     * c; 
    int i,
        t;
} ;



#define O(...)({o*_=malloc(32);*_=(o){__VA_ARGS__};_;})

E(o a, o b) { //tests equality 
    return
        a.n ? !strcmp(a.n,b.n) :
        a.t ? a.i==b.i :
        a.c ? b.c && E(*a.c,*b.c)&E(*a.l,*b.l) :
        !b.c
    ;
}

#define P printf


p(o*x){
    x->t?P("%d ",x->i):x->n?P("%s ",x->n):({for(P("(");x->c;x=x->l)p(x->c);P(")");});
}


o*_,G,N; //N = nil



o*C(o*h,o*t){return O(c:h,l:t);}


/*
        2 3 4 5 6 7 8 9 10 11
        s l e c i v t h d  q
    */


o* v(o* x, o* e) { //takes list, int, or name
    o*W(o* l, o* e) { //eval each item in list
        return l->c ? C(v(l->c ,e), W(l->l, e)) : &N;
    }

    o*y,*a,*f;int t;
    return x->c ? //nonempty list = function/macro call
        y = v(x->c,e), //evals to function/macro
        x = x->l,   //list position of first arg (if it exists)
        (t=y->t)?   //builtin no., if any
             t>9 ?
              t&1 ? x->c // 11 = q
                : //10 = d
                (d(x->c,v(x->l->c,e)),x->c)
           : (a = v(x->c,e), //eval'd first arg
             t)>7 ? // t/h
                (t > 8 ? a->c : a->l) ?: a
           : t>6 ? //v
                v(a,e)
           : (x = x->l, //position of 2nd arg in list
             t)>5 ? //i
                v( (a->n||a->l||a->i|a->t>1 ? x : x->l)->c, e)
           : (x = v(x->c,e), //evaluated 2nd arg
             t)>4 ? // c
                C(a,x)
           : O(t:1,i:
                t>3 ? E(*a,*x) :  //e
                t>2 ? a->i<x->i : //l
                      a->i-x->i   //s
              )
        :
        (
            y->l->l->l ? //whether this is macro
                y = y->l :
                (x = W(x,e)),  //eval args
            a = y->c,  //a = arg list
            //a = a->n ? x=C(x, &N), C(a, &N) : a, //transform variadic style to normal
            v(y->l->c,
               a->n ? //variadic
                O(n:a->n,c:x,l:&G)
              : ({
                   for(f=&G; a->c; a=a->l,x=x->l)
                      f=O(n:a->c->n, c: x->c, l:f);
                   f;
                })
            )
        )
    :
    x->n ? // name
        e->n ?
            strcmp(x->n,e->n) ?
                v(x,e->l)
            : e->c
        : e
     : x; //int or nil
}

d(o*n,o*x){
    * v(O(n:""),&G) =
        (o){n:n->n,c:x,l:O()};
}


;
o*R(){
    char*z,*q;int h;
return scanf(" %m[^ \n()]",&q)>0?
    h=strtoul(q,&z,10),
    C(*z ? O(n:q) : O(t:1,i:h), R())
: getchar()&1?&N:(q=R(),C(q,R()));
}
main(i) {

    for(;++i<12;) d(O(n:strndup("slecivthdq"+i-2,1)),O(t:i));

    o *q;
    for(q=R(); q->c; q=q->l) p(v(q->c,&G));

}

Цейлон, 2422 байта

(Я думаю, что это моя самая длинная гольф-программа.)

import ceylon.language{sh=shared,va=variable,fo=formal,O=Object}import ceylon.language.meta.model{F=Function}interface X{sh fo V v(S t);sh fo G g;}class G(va Map<S,V>m)satisfies X{v(S t)=>m[t]else nV;g=>this;sh S d(S s,V v){assert(!s in m);m=map{s->v,*m};return s;}}V nV=>nothing;class LC(G c,Map<S,V>m)satisfies X{g=>c;v(S t)=>m[t]else g.v(t);}alias C=>V|Co;interface Co{sh fo C st();}interface V{sh fo C l(X c,V[]a);sh default Boolean b=>0<1;sh fo C vO(X c);sh default V vF(X c){va C v=vO(c);while(is Co n=v){v=n.st();}assert(is V r=v);return r;}}class L(sh V*i)satisfies V{vO(X c)=>if(nonempty i)then i[0].vF(c).l(c,i.rest)else this;equals(O o)=>if(is L o)then i==o.i else 1<0;b=>!i.empty;string=>"(``" ".join(i)``)";hash=>i.hash;sh actual C l(X c,V[]p){value[h,ns,x]=i.size<3then[f,i[0],i[1]]else[m,i[1],i[2]];value n=if(is L ns)then[*ns.i.narrow<S>()]else ns;assert(is S|S[]n,is V x);V[]a=h(c,p);LC lC=if(is S n)then LC(c.g,map{n->L(*a)})else LC(c.g,map(zipEntries(n,a)));return object satisfies Co{st()=>x.vO(lC);};}}class S(String n)satisfies V{vO(X c)=>c.v(this);l(X c,V[]a)=>nV;equals(O o)=>if(is S o)then n==o.n else 1<0;hash=>n.hash;string=>n;}class I(sh Integer i)satisfies V{vO(X c)=>this;l(X c,V[]a)=>nV;equals(O o)=>if(is I o)then i==o.i else 1<0;hash=>i;b=>!i.zero;string=>i.string;}V[]f(X c,V[]a)=>[for(v in a)v.vF(c)];V[]m(X c,V[]a)=>a;L c(X c,V h,L t)=>L(h,*t.i);V h(X c,L l)=>l.i[0]else L();V t(X c,L l)=>L(*l.i.rest);I s(X c,I f,I s)=>I(f.i-s.i);I l(X c,I f,I s)=>I(f.i<s.i then 1else 0);I e(X c,V v1,V v2)=>I(v1==v2then 1else 0);C v(X c,V v)=>v.vO(c);V q(X c,V a)=>a;C i(X c,V d,V t,V f)=>d.vF(c).b then t.vO(c)else f.vO(c);S d(X c,S s,V x)=>c.g.d(s,x.vF(c));class B<A>(F<C,A>nat,V[](X,V[])h=f)satisfies V given A satisfies[X,V+]{vO(X c)=>nV;string=>nat.declaration.name;l(X c,V[]a)=>nat.apply(c,*h(c,a));}{<S->V>*}b=>{S("c")->B(`c`),S("h")->B(`h`),S("t")->B(`t`),S("s")->B(`s`),S("l")->B(`l`),S("e")->B(`e`),S("v")->B(`v`),S("q")->B(`q`,m),S("i")->B(`i`,m),S("d")->B(`d`,m)};[V*]p(String inp){value ts=inp.split(" \n()".contains,1<0,1<0);va[[V*]*]s=[];va[V*]l=[];for(t in ts){if(t in" \n"){}else if(t=="("){s=[l,*s];l=[];}else if(t==")"){l=[L(*l.reversed),*(s[0]else[])];s=s.rest;}else if(exists i=parseInteger(t),i>=0){l=[I(i),*l];}else{l=[S(t),*l];}}return l.reversed;}sh void run(){va value u="";while(exists l=process.readLine()){u=u+l+"\n";}V[]e=p(u);X c=G(map(b));for(v in e){print(v.vF(c));}}

Я мог бы сыграть еще несколько байт, так как в некоторых местах я использовал двухбуквенные идентификаторы, но у меня кончились несколько значащих одиночных букв для них. Хотя даже так это не очень похоже на Цейлон ...

Это объектно-ориентированный реализация.

У нас есть интерфейс значений Vс реализующими классами L(список - просто обертка вокруг последовательности Цейлона V), S(символ - обертка вокруг строки), I(целое число - обертка вокруг целого числа Цейлона) и B(встроенная функция или макрос, обертка вокруг Цейлонская функция).

Я использую стандартную нотацию равенства Цейлона, реализуя equalsметод (а также hashатрибут, который действительно нужен только для символов), а также стандартstring атрибут для вывода.

У нас есть логический атрибут b(который по умолчанию имеет значение true, переопределяется Iи Lвозвращает false для пустых списков) и два метода l(вызов, т.е. использование этого объекта в качестве функции) и vO(оценка одного шага). Оба возвращают либо значение, либо объект продолжения, который позволяет затем выполнить оценку для еще одного шага иvF (полностью оценить) циклы, пока результат больше не будет продолжением.

Контекстный интерфейс позволяет получить доступ к переменным. Существует две реализации Gдля глобального контекста (который позволяет добавлять переменные с помощью dвстроенного) иLC для локального контекста, который активен при оценке выражения пользовательской функции (он возвращается к глобальному контексту).

Оценка символов обращается к контексту, списки (если не пустые) оценивают, сначала оценивая их первый элемент, а затем вызывая его метод вызова. Вызов реализуется только списками и встроенными функциями - он сначала оценивает аргумент (если функция, а не макрос), а затем выполняет действительно интересные вещи - для встроенных функций только то, что жестко закодировано, для списков он создает новый локальный контекст и возвращает продолжение с этим.

Для встроенных функций я использовал трюк, аналогичный тому, который я использовал в интерпретаторе Shift , который позволяет мне определять их с нужными им типами аргументов, но вызывать их с общей последовательностью, используя отражение (типы будут проверяться во время вызова). Это позволяет избежать проблем с преобразованием типов / утверждениями внутри функций / макросов, но требует функций верхнего уровня, чтобы я мог получить их Functionобъекты метамодели .

p (parse) разбивает строку на пробелы, символы новой строки и круглые скобки, затем перебирает токены и строит списки, используя стек и текущий список.

Интерпретатор (в runметоде, который является точкой входа) затем берет этот список выражений (которые являются просто значениями), оценивает каждое из них и печатает результат.

Ниже приведена версия с комментариями и прогоном через форматтер.

Более ранняя версия до того, как я начал играть в гольф (и все еще с некоторыми недоразумениями относительно оценки списка), найдена в моем репозитории Github , я скоро добавлю ее (так что обязательно посмотрите на первую версию, если вы хотите оригинал).

//  Tiny Lisp, tiny interpreter
//
// An interpreter for a tiny subset of Lisp, from which most of the
// rest of the language can be bootstrapped.
//
// Question:   https://codegolf.stackexchange.com/q/62886/2338
// My answer:  https://codegolf.stackexchange.com/a/63352/2338
//
import ceylon.language {
    sh=shared,
    va=variable,
    fo=formal,
    O=Object
}
import ceylon.language.meta.model {
    F=Function
}

// context

interface X {
    sh fo V v(S t);
    sh fo G g;
}
// global (mutable) context, with the buildins 
class G(va Map<S,V> m) satisfies X {
    // get entry throws error on undefined variables. 
    v(S t) => m[t] else nV;
    g => this;
    sh S d(S s, V v) {
        // error when already defined
        assert (!s in m);
        // building a new map is cheaper (code-golf wise) than having a mutable one.
        m = map { s->v, *m };
        return s;
    }
}

// This is simply a shorter way of writing "this is not an allowed operation".
// It will throw an exception when trying to access it.
// nV stands for "no value".
V nV => nothing;

// local context
class LC(G c, Map<S,V> m) satisfies X {
    g => c;
    v(S t) => m[t] else g.v(t);
    // sh actual String string => "[local: ``m``, global: ``g``]";
}

// continuation or value
alias C => V|Co;

// continuation
interface Co {
    sh fo C st();
}

// value
interface V {
    // use this as a function and call with arguments.
    // will not work for all types of stuff.
    sh fo C l(X c, V[] a);
    // check the truthiness. Defaults to true, as
    // only lists and integers can be falsy.
    sh default Boolean b => 0 < 1;
    // evaluate once (return either a value or a continuation).
    // will not work for all kinds of expression.
    sh fo C vO(X c);
    /// evaluate fully
    sh default V vF(X c) {
        va C v = vO(c);
        while (is Co n = v) {
            v = n.st();
        }
        assert (is V r = v);
        return r;
    }
}
class L(sh V* i) satisfies V {

    vO(X c) => if (nonempty i) then i[0].vF(c).l(c, i.rest) else this;
    equals(O o) => if (is L o) then i == o.i else 1 < 0;
    b => !i.empty;
    string => "(``" ".join(i)``)";
    hash => i.hash;

    sh actual C l(X c, V[] p) {
        value [h, ns, x] =
                i.size < 3
                then [f, i[0], i[1]]
                else [m, i[1], i[2]];
        // parameter names – either a single symbol, or a list of symbols.
        // If it is a list, we filter it to throw out any non-symbols.
        // Should throw an error if there are any, but this is harder.
        value n = if (is L ns) then [*ns.i.narrow<S>()] else ns;
        assert (is S|S[] n, is V x);
        V[] a = h(c, p);

        // local context
        LC lC = if (is S n) then
            LC(c.g, map { n -> L(*a) })
        else
            LC(c.g, map(zipEntries(n, a)));
        // return a continuation instead of actually
        // calling it here, to allow stack unwinding.
        return object satisfies Co {
            st() => x.vO(lC);
        };
    }
}

// symbol
class S(String n) satisfies V {
    // evaluate: resolve
    vO(X c) => c.v(this);
    // call is not allowed
    l(X c, V[] a) => nV;
    // equal if name is equal
    equals(O o) => if (is S o) then n == o.n else 1 < 0;
    hash => n.hash;
    string => n;
}

// integer
class I(sh Integer i) satisfies V {

    vO(X c) => this;
    l(X c, V[] a) => nV;
    equals(O o) => if (is I o) then i == o.i else 1 < 0;
    hash => i;
    b => !i.zero;
    string => i.string;
}

// argument handlers for functions or macros
V[] f(X c, V[] a) => [for (v in a) v.vF(c)];
V[] m(X c, V[] a) => a;

// build-in functions
// construct
L c(X c, V h, L t) => L(h, *t.i);
// head
V h(X c, L l) => l.i[0] else L();
// tail
V t(X c, L l) => L(*l.i.rest);
// subtract
I s(X c, I f, I s) => I(f.i - s.i);
// lessThan
I l(X c, I f, I s) => I(f.i < s.i then 1 else 0);
// equal
I e(X c, V v1, V v2) => I(v1 == v2 then 1 else 0);
// eval (returns potentially a continuation)
C v(X c, V v) => v.vO(c);

// build-in macros
// quote
V q(X c, V a) => a;
// if (also returns potentially a continuation)
C i(X c, V d, V t, V f) => d.vF(c).b then t.vO(c) else f.vO(c);
// define symbol in global context
S d(X c, S s, V x) => c.g.d(s, x.vF(c));

// buildin function or macro, made from a native function and an argument handler
class B<A>(F<C,A> nat, V[](X, V[]) h = f)
        satisfies V
        given A satisfies [X, V+] {
    vO(X c) => nV;
    string => nat.declaration.name;
    // this "apply" is a hack which breaks type safety ...
    // but it will be checked at runtime.
    l(X c, V[] a) => nat.apply(c, *h(c, a));
}

// define buildins
{<S->V>*} b => {
    S("c") -> B(`c`),
    S("h") -> B(`h`),
    S("t") -> B(`t`),
    S("s") -> B(`s`),
    S("l") -> B(`l`),
    S("e") -> B(`e`),
    S("v") -> B(`v`),
    S("q") -> B(`q`, m),
    S("i") -> B(`i`, m),
    S("d") -> B(`d`, m)
};

// parses a string into a list of expressions.
[V*] p(String inp) {
    // split string into tokens (retain separators, don't group them –
    // whitespace and empty strings will be sorted out later in the loop)
    value ts = inp.split(" \n()".contains, 1 < 0, 1 < 0);
    // stack of not yet finished nested lists, outer most at bottom
    va [[V*]*] s = [];
    // current list, in reverse order (because appending at the start is shorter)
    va [V*] l = [];
    for (t in ts) {
        if (t in " \n") {
            // do nothing for empty tokens
        } else if (t == "(") {
            // push the current list onto the stack, open a new list.
            s = [l, *s];
            l = [];
        } else if (t == ")") {
            // build a lisp list from the current list,
            // pop the latest list from the stack, append the created lisp list. 
            l = [L(*l.reversed), *(s[0] else [])];
            s = s.rest;
        } else if (exists i = parseInteger(t), i >= 0) {
            // append an integer to the current list.
            l = [I(i), *l];
        } else {
            // append a symbol to the current list.
            l = [S(t), *l];
        }
    }
    return l.reversed;
}

// Runs the interpreter.
// This handles input and output, calls the parser and evaluates the expressions.
sh void run() {
    va value u = "";
    while (exists l = process.readLine()) {
        u = u + l + "\n";
    }
    V[] e = p(u);
    // create global context
    X c = G(map(b));
    // iterate over the expressions, ...
    for (v in e) {
        // print("  '``v``' → ...");
        // ... evaluate each (fully) and print the result.
        print(v.vF(c));
    }
}