Задача состоит в том, чтобы написать интерпретатор для нетипизированного лямбда-исчисления, используя как можно меньше символов. Мы определяем нетипизированное лямбда-исчисление следующим образом:
Синтаксис
Существуют следующие три вида выражений:
Лямбда-выражение имеет форму,
(λ x. e)
гдеx
может быть любое допустимое имя переменной иe
любое допустимое выражение. Здесьx
называется параметром иe
называется телом функции.Для простоты мы добавим еще одно ограничение: не должно быть переменной с тем же именем, что и в
x
настоящее время в области видимости. Переменная начинает находиться в области видимости, когда ее имя появляется между(λ
и.
и перестает быть в области видимости соответствующей области)
.- Функция приложения имеет вид
(f a)
гдеf
иa
являются юридическими выражениями. Здесьf
называется функция иa
называется аргументом. - Переменная имеет вид
x
гдеx
допустимое имя переменной.
Семантика
Функция применяется путем замены каждого вхождения параметра в теле функции своим аргументом. Более формально выражение формы ((λ x. e) a)
, где x
это имя переменной и e
и a
являются выражениями, оценивает (или уменьшает) к выражению e'
где e'
является результатом замены каждого вхождения x
в e
с a
.
Нормальная форма - это выражение, которое не может быть оценено в дальнейшем.
Соревнование
Ваша миссия, если вы решите принять ее, - написать интерпретатор, который принимает в качестве входных данных выражение нетипизированного лямбда-исчисления, не содержащее свободных переменных, и выдает в качестве выходных данных нормальную форму выражения (или выражение, альфа-конгруэнтное ему) , Если выражение не имеет нормальной формы или не является допустимым выражением, поведение не определено.
Решение с наименьшим количеством символов выигрывает.
Пара заметок:
- Входные данные могут быть либо прочитаны из стандартного ввода, либо из имени файла, заданного в качестве аргумента командной строки (вам нужно только реализовать одно или другое, а не оба). Вывод идет в стандартный вывод.
- В качестве альтернативы вы можете определить функцию, которая принимает входные данные в виде строки и возвращает выходные данные в виде строки.
- Если символы не ASCII для вас проблематичны, вы можете использовать
\
символ обратной косой черты ( ) вместо λ. - Мы считаем количество символов, а не байтов, поэтому даже если ваш исходный файл в кодировке Unicode λ считается одним символом.
- Допустимые имена переменных состоят из одной или нескольких строчных букв, то есть символов между a и z (нет необходимости поддерживать буквенно-цифровые имена, прописные буквы или нелатинские буквы - хотя это, конечно, не сделает ваше решение недействительным).
- Что касается этой проблемы, то круглые скобки не являются обязательными. Каждое лямбда-выражение и каждое приложение функции будут заключены ровно в одну пару скобок. Имя переменной не будет заключено в круглые скобки.
- Синтаксический сахар, такой как запись
(λ x y. e)
для(λ x. (λ y. e))
, не нуждается в поддержке. - Если для оценки функции требуется глубина рекурсии более 100, поведение не определено. Это должно быть более чем достаточно, чтобы быть реализованным без оптимизации на всех языках, и все же достаточно большим, чтобы можно было выполнять большинство выражений.
- Вы также можете предположить, что интервал будет таким же, как в примерах, то есть без пробелов в начале и конце ввода или перед
λ
или или.
и ровно через один пробел после a.
и между функцией и ее аргументом и после aλ
.
Пример ввода и вывода
Входные данные:
((λ x. x) (λ y. (λ z. z)))
Выход:
(λ y. (λ z. z))
Входные данные:
(λ x. ((λ y. y) x))
Выход:
(λ x. x)
Входные данные:
((λ x. (λ y. x)) (λ a. a))
Выход:
(λ y. (λ a. a))
Входные данные:
(((λ x. (λ y. x)) (λ a. a)) (λ b. b))
Выход:
(λ a. a)
Входные данные:
((λ x. (λ y. y)) (λ a. a))
Выход:
(λ y. y)
Входные данные:
(((λ x. (λ y. y)) (λ a. a)) (λ b. b))
Выход:
(λ b. b)
Входные данные:
((λx. (x x)) (λx. (x x)))
Вывод: что угодно (это пример выражения, которое не имеет нормальной формы)
Входные данные:
(((λ x. (λ y. x)) (λ a. a)) ((λx. (x x)) (λx. (x x))))
Вывод:
(λ a. a)
(Это пример выражения, которое не нормализуется, если вы оцениваете аргументы перед вызовом функции, и, к сожалению, пример, для которого моя попытка решения не удалась)Входные данные:
((λ a. (λ b. (a (a (a b))))) (λ c. (λ d. (c (c d)))))
Вывод:
`(λ a. (λ b. (a (a (a (a (a (a (a (a b))))))))))
это вычисляет 2 ^ 3 в церковных цифрах.
(\y. a)
.Ответы:
Новые:
Я сократил его до 644 символов , я разложил части cEll на cOpy и Par; кэшировал вызовы cell и cdr во временные локальные переменные и перемещал эти локальные переменные в глобальные переменные в «терминальных» (то есть нерекурсивных) функциях. Кроме того, десятичные константы короче литералов символов и это неприятное дело ...
... правильно определяет строчные буквы (при условии ASCII), но также принимает любую из `{|} ~. (То же самое наблюдение об ASCII сделано в этом превосходном видео о UTF-8 .)
Эт альт: |
Ранее:
Могу ли я получить несколько голосов за усилия? Я работаю в этот день и ночь в течение недели. Я выкопал оригинальную статью Маккарти, и меня мучила ошибка в самой газете, пока я не прочитал приложение к Полу Грэму « Корни Лиспа» . Я так отвлекся, что заперся в своем доме, а затем совершенно забыл, пока не вернулся домой в ту ночь в 12:30 (немного поздно, чтобы позвонить управляющему, живущему в округе), и мне пришлось потратить ночь у моей бабушки (взлома, пока батарея моего ноутбука не высохла).
И после всего этого, это даже не близко к победной записи!
Я не уверен, как сделать это немного короче; и я использовал все грязные уловки, которые я могу придумать! Может быть, это не может быть сделано в C.
С некоторой щедростью в подсчете (первый кусок берет строку и распечатывает результат), это
778770709694 символа. Но чтобы сделать его автономным, он должен иметь этотsbrk
призыв. И для обработки более сложных выражений ему также нуженsignal
обработчик. И, конечно, его нельзя превратить в модуль с любым кодом, который пытается использоватьmalloc
.Итак, увы, вот оно:
Вот блок перед окончательными сокращениями. Трюки здесь - это целочисленные курсоры вместо указателей (использующие поведение «implicit int») и использование «нуля памяти»: это
char*n
указатель «new» или «next» в свободное пространство. Но иногда я записываю строку в память, затем вызываю strlen и увеличиваю n; эффективно используя память, а затем выделяя ее, после того как размер будет легче вычислить. Вы можете видеть, что это в значительной степени прямо из статьи Маккарти, за исключением того,cell()
какие интерфейсы между функциями и строковым представлением данных.источник
sprintf(n,...);n+=strlen(n)+1;
Это лучше, посколькуn+=sprintf(n,...)+1;
инвертирование синтаксиса массиваx[m]
вместо того,m[x]
чтобы позволить мне заменить все косвенные переменные макросом «postfix»#define M [m]
...,x M
который сохраняет 1 символ и дает «свободный» разрыв строки, поскольку для разделения токенов необходим пробел.// um ...
перебирает строку и считает скобки, пока не найдет подходящую близкую точку на правильном уровне вложенности.Двоичное лямбда-исчисление 186
Программа показанная в шестнадцатеричном дампе ниже
не совсем подходит формат, который вы предлагаете. Скорее, он ожидает лямбда-член в формате двоичного лямбда-исчисления (blc). Тем не менее, он показывает каждый шаг в обычном сокращении формы, используя минимальные скобки.
Пример: вычисление 2 ^ 3 в церковных цифрах
Сохраните вышеуказанный шестнадцатеричный дамп с помощью xxd -r> symbolic.Blc
Возьмите переводчика blc с http://tromp.github.io/cl/uni.c
Поскольку hexdump довольно нечитаем, вот «разобранная» версия
замена 00 (лямбда) на \ и 01 (приложение) на @ Теперь это почти так же читабельно, как brainfuck :-)
Также см. Http://www.ioccc.org/2012/tromp/hint.html.
источник
Haskell,
342323317305 символовНа момент написания статьи это единственное решение, которое оценивает ((λ f. (Λ x. (Fx))) (λ y. (Λ x. Y))) правильный результат (λ x. (Λ z. х)) а не (Х х. (Х х. х)). Корректная реализация лямбда-исчисления требует замены , избегающей захвата , даже при упрощенной гарантии этой задачи, что никакая переменная не затеняет другую переменную в своей области видимости. (Моя программа работает даже без этой гарантии.)
Заметки:
Неуправляемая версия с документацией.
источник
Python -
321320Вот моя (исправленная) попытка:
источник
Руби 254 персонажа
Может использоваться как
Решение еще не полностью закончено, но уже почти нечитаемо.
источник
Изменить: проверьте мой ответ ниже для 250 под чистым JavaScript.
2852243 символа, использующих LiveScript (без регулярных выражений! Не полностью в гольф - можно улучшить)Тест:
Что
3^2=9
, как указано на ОП.Если кому-то интересно, вот расширенная версия с некоторыми комментариями:
источник
Уотерхаус Арк - 140 персонажей
источник
C 1039 байт
Переменные допускают в качестве входных данных, используя строчные буквы [из a..z], sys может генерировать переменные, используя заглавные буквы [из A..Z], если это необходимо в выводе ... Предположим, конфигурация символов ascii.
источник
Haskell 456 C
Это может быть намного короче, если функция отложенной оценки Haskell полностью используется. К сожалению, я не знаю, как это сделать.
Кроме того, многие символы теряются на этапе анализа.
Неуправляемая версия
источник
Получил 231 с JavaScript / без регулярных выражений
Получает 2-элементные массивы.
1
обозначает,λ
а 2 обозначает переменную индекса Брейна.Тест:
источник
Python: 1266 символов (измеряется с помощью wc)
Не самый короткий по дальности, но он правильно обрабатывает альфа-переименование и все примеры, перечисленные в постах ОП.
источник
except NameError
простоexcept
? (3) Двухсимвольные имена функций могут быть переименованы в односимвольные имена. (4) Есть несколько мест, где у вас есть задания, в которых есть пробелы=
. (5)if t[0]=='c'
можно заменить наif'c'==t[0]
.C ++ (gcc) ,
+782+766+758731 байтПопробуйте онлайн!
Основная идея здесь заключается в том, что в коде используется внутреннее представление, основанное на идее индексов де Брюйна, за исключением того, что я обращаюсь к индексам в обратном порядке, чтобы указать лямбда-глубину привязки указанной переменной. В коде:
E::t
представляет тип узла - 0 для листового узла переменной, 1 для лямбда-узла и 2 для узла приложения функции. (Выбранный таким образом, чтобы он совпадал с арностью узла, что просто возможно). ТогдаE::l
иE::r
являются подходящими дочерними элементами (толькоE::l
для лямбда-узла), иE::i
это индекс лямбда-глубины для переменного конечного узла.E::E(E&o,int d,int e)
клонирует подвыражение, которое изначально было на лямбда-глубине,d
для вставки в новое место на лямбда-глубинеd+e
. Это предполагает сохранение переменных на лямбда-глубине меньше, чемd
при увеличении переменных на лямбда-глубине хотя быd
наe
.E::s
делает замену подвыраженияv
в переменное числоd
в*this
то время как декремент переменного числа большеd
(иe
внутренняя деталь отслеживания лямбды-приращения глубины для того, когда она должна вызоваE::c
).E::R
выполняет поиск одного бета-сокращения, предпочитая самые верхние или самые левые экземпляры в соответствии с предварительным поиском через AST. Он возвращает ненулевое значение, если он нашел сокращение для выполнения, или ноль, если он не нашел ни одного.E::u
являетсяto_string
операцией типа, которая восстанавливает «читаемую человеком» строку, используя синтетические имена для переменных. (Обратите внимание, что из-за небольшого влиянияV
вспомогательной функции он будет генерировать только имена, содержащиеa
доi
.)E::E(int d, std::map<std::string, int> m, char*&s)
выполняет синтаксический анализ входной строкиs
в выражении AST, основываясь на отображенииm
имен связанных в настоящее время переменных в индексы глубины лямбды.f
является основной функцией ответа на вопрос.(Как вы можете видеть по ссылке TIO, код обрабатывает имена переменных с несколькими символами, и он также получает правильный ответ
(\ a. (\ b. a))
для((\ f. (\ x. (f x))) (\ y. (\ x. y)))
. Также случается, что код синтаксического анализа может обрабатывать затенение переменных без дополнительных затрат.)-16 байтов, частично из-за идеи потолочной кошки (которую я также придумал независимо), и частично из-за изменения
E*a=new E;
вE&a=*new E;
и затем измененияa->
вa.
-8 больше байтов из-за другого комментария потолочного кота (исключить назначение
a.t
из троичного)-27 байт от преобразования парсера и клона в конструкторы
E
источник
C 637 байт
В этой версии не используются вспомогательные переменные (поэтому это не соответствует 100% тому, что говорит лямбда-исчисление ... как и многие другие здесь ...). Каждая переменная должна быть длиной 1 символ (как и некоторые другие здесь). Тестовый код:
полученные результаты:
это полу-негольф один:
источник