Церковные булевы
Церковь булева функция , которая возвращает x
для истинно и y
для ложных , где x
это первый аргумент функции и y
является вторым аргументом функции. Дополнительные функции могут быть составлены из этих функций, которые представляют and
not
or
xor
и implies
логические операции.
Вызов
Построить булеву Церковь и and
not
or
xor
и implies
церковные ворота на языке по вашему выбору. and
or
и xor
должен принимать две функции (представляющие логические значения Церкви) и возвращать функцию (представляющую другое логическое значение Церкви). Точно так же, not
следует инвертировать функцию, которую он выполняет, и implies
логический элемент должен выполнять логическую, подразумевающую логику, где первый аргумент implies
второй.
счет
Общая длина всего кода, необходимого для создания церковного true
и false
на вашем языке and
not
or
xor
и implies
церковных ворот, за исключением названия функции. (например, false=lambda x,y:y
в Python будет 13 байт). Вы можете использовать эти имена позже в своем коде, считая их на 1 байт до общего количества байтов в этих воротах.
Примеры псевдокода:
Функции, которые вы создаете, должны иметь возможность вызываться позже в вашем коде следующим образом.
true(x, y) -> x
false(x, y) -> y
and(true, true)(x, y) -> x
and(true, false)(x, y) -> y
# ... etc
источник
true([x, y])
,and([true, true])([x, y])
)?Ответы:
Двоичное лямбда-исчисление ,
13,875,12,875 байт (103 бита)Язык двоичного лямбда-исчисления (BLC) Джона Тромпа - это в основном эффективный формат сериализации для лямбда-исчисления. Он отлично подходит для этой задачи, поскольку нотация Церкви - это даже «идиоматический» способ работы с логическими значениями в BLC.
Я использовал следующие лямбда-функции для комбинаторов,
некоторые из которых я скопировал и сыграл в гольф из ответа Хаскелла:которые были найдены путем исчерпывающего поиска с доказательством ограничения в 20 β-сокращений для каждого случая. Есть большая вероятность, что они будут кратчайшими.Они переводят в следующие (двоичные) кодовые последовательности BLC:
Вышеуказанные функции имеют общую
длину 111 бит (13,875 байт),длину 103 бит (12,875 байт). Их не нужно выравнивать по границам байтов для использования внутри программы, поэтому имеет смысл считать дробные байты.Между комбинаторами нет повторного использования кода, поскольку в BLC нет переменных / ссылок / имен - все должно быть скопировано. Тем не менее, эффективность кодирования обеспечивает довольно сжатое представление.
источник
And: (\a \b a b a)
работать?\a \b a a b
. Это длиннее, чем тот, который я использовал в BLC.Haskell , 50 - 6 = 44 байта
-1 байт благодаря Khuldraeseth na'Barya, и -1 байт благодаря Кристиану Сиверсу.
Попробуйте онлайн!
источник
Show
экземпляры дляconst
иconst id
и печатать церковные булевы непосредственно. Попробуйте онлайн! ,a
можно сократитьf=n t
?t=pure
вместоt=const
.t=pure
приведет к ошибке при попытке применитьa
,o
,x
илиi
к нему. Объявление типаt
исправления стоит больше байтов, чем просто использованиеt=const
.Python 2 , (-3?)
10195 байтДэвид Бизли съест твое сердце!
-6 спасибо Часу Брауну (перенес повторение
:
в текст объединения>. <)Попробуйте онлайн!
Я думаю, что это может быть
95 - 3
потому, что я не использую функцииA
,X
илиI
, но я использую один=
для присваивания (передlambda
). Может быть, я не могу удалить любой; может я вообще получу удалить 3,5?источник
exec
имею в виду, что я не могу? Я вижу, что происходит в любом случае - я не использую A, X или I, но код не будет работать без них. (Может быть, я даже удаляю 3,5 ?!)JavaScript (Node.js) ,
928683 - 7 = 76 байтПопробуйте онлайн! Ссылка включает в себя основные тестовые случаи. Изменить: Сохранено
69 байт благодаря @tsh.источник
t
,f
,n
используются.t
,f
иn
в вашем случае).Python 2 ,
133 - 6 = 12794 байтаПопробуйте онлайн!
Бесстыдно крадет подлую идею ответа Джонатана Аллана ; байты не вычитаются.
источник
J 67 байт - 7 = 60
Попробуйте онлайн!
Стоит отметить:
Функции высшего порядка работают в J иначе, чем в функциональном языке. Чтобы создать новый глагол из 1 или 2 существующих глаголов, вам нужно использовать наречие (в случае 1) или соединение (в случае 2).
Синтаксически, наречия идут после глагола, и соединения происходят между ними. Таким образом, чтобы «не» глагол
f
вы делаетеf n
, а «и» глаголыf
иg
выf a g
.источник
Wolfram Language (Mathematica) , 61-7 = 54 байта
Попробуйте онлайн!
не в гольф: вдохновленный Википедией ,
источник
Недогрузки ,
5652 байтПопробуйте онлайн! (включает тестовый набор и текстовые части программы)
Это удивительно хорошо для esolang очень низкого уровня. (По этой причине в Underload очень часто используются церковные цифры, церковные логические значения и т. Д .; в языке нет встроенных чисел и логических значений, и это один из самых простых способов их симуляции. закодируйте логические числа как церковные цифры 0 и 1.)
Для тех, кто в замешательстве: недогрузка позволяет вам определять многократно используемые функции, но не позволяет вам называть их обычным способом, они просто как бы плавают в стеке аргументов (так что если вы определяете пять функций, а затем хотите вызвать первую Вы определили, что вам нужно написать новую функцию, которая принимает пять аргументов и вызывает пятый из них, а затем вызывает ее с недостаточным количеством аргументов, чтобы она могла искать свободные аргументы). Вызов их уничтожает их по умолчанию, но вы можете изменить вызов, чтобы сделать его неразрушающим (в простых случаях вам просто нужно добавить двоеточие к вызову, хотя сложные случаи встречаются чаще, потому что вам нужно убедиться, что копии в стеке, не мешайте), так что поддержка функций Underload имеет все требования, которые нам нужны из этого вопроса.
объяснение
правда
Это довольно просто; мы избавляемся от аргумента, который нам не нужен, и аргумента, который нам нужен, просто остается там, служа в качестве возвращаемого значения.
ложный
Это еще проще.
не
Это забавно: он
not
вообще не вызывает свой аргумент, он просто использует композицию функций. Это обычная уловка в Underload, в которой вы вообще не проверяете свои данные, вы просто меняете их функционирование, предварительно и после компоновки. В этом случае мы модифицируем функцию, чтобы поменять ее аргументы перед запуском, что явно отрицает церковную цифру.а также
Вопрос позволяет определять функции в терминах других функций. Мы определяем «и» далее, потому что чем позже было определено «нет», тем легче его использовать. (Это не вычитает из нашей оценки, потому что мы вообще не называем «не», но экономит байты при повторной записи определения. Это единственный раз, когда одна функция ссылается на другую, потому что ссылается на любую функцию но последнее определение будет стоить слишком много байтов.)
Определение здесь
and x y = (not x) false y
. Другими словами, еслиnot x
, тогда мы вернемсяfalse
; в противном случае мы вернемсяy
.или
@Nitrodon указал в комментариях, что
or x y = x x y
обычно корочеor x y = x true y
, и это оказывается правильным и в Underload. Наивная реализация этого была бы(:~^)
, но мы можем отыграть дополнительный байт, отметив, что не имеет значения, запускаем ли мы первый аргумент или его копию, результат одинаков в любом случае.Недостаточная нагрузка на самом деле не поддерживает карри в обычном смысле, но такие определения заставляют ее выглядеть так, как будто это происходит! (Хитрость заключается в том, что неиспользуемые аргументы просто остаются рядом, поэтому вызываемая вами функция будет интерпретировать их как свои собственные аргументы.)
подразумевает
Определение , используемое здесь
implies x y = not (y false x)
. Если у истинно, это упрощаетсяnot false
, то естьtrue
. Если у ложно, это упрощаетсяnot x
, давая нам таблицу истинности, которую мы хотим.В этом случае мы используем
not
снова, на этот раз переписывая его код, а не ссылаясь на него. Он просто написан напрямую,(~)~*
без скобок, поэтому вызывается, а не определяется.исключающее
На этот раз мы оцениваем только один из двух наших аргументов и используем его, чтобы определить, что нужно составить для второго аргумента. Недогрузка позволяет вам играть быстро и свободно с арностью, поэтому мы используем первый аргумент для выбора между двумя функциями с двумя аргументами и двумя возвращаемыми значениями; своп аргумента, который возвращает их обоих, но в обратном порядке, и функция тождества, которая возвращает их обоих в том же порядке.
Когда первый аргумент верно, поэтому мы производим отредактированную версию второго аргумента , что свопы аргументов перед запуском, то есть Precompose с «аргументами свопа», то есть
not
. Таким образом, истинный первый аргумент означает, что мы возвращаемnot
второй аргумент. С другой стороны, ложный первый аргумент означает, что мы сочиняем с функцией тождества, т.е. ничего не делаем. Результатом является реализацияxor
.источник
or x y = x x y
сохраняет несколько байтовor x y = x true y
.Рубин , 82 - 4 = 78 байт
Попробуйте онлайн!
источник
Java 8, оценка:
360358319271233 (240-7) байтЭто было сложнее, чем я думал, когда начинал. ОсобенноРЕДАКТИРОВАТЬ: Хорошо, не повторное использование функций, а просто дублирование одного и того же подхода намного дешевле с точки зрения подсчета байтов для Java. И я получаю полный бонус -7 за то, что не использовал ни одну из функций.implies
. Во всяком случае, это работает .. Возможно, можно немного поиграть в гольф здесь и там.Попробуйте онлайн.
Объяснение:
источник
C ++ 17,
207−49 = 158195 - 58 = 137 байтРазрывы строки не нужны (кроме первых двух).
Попробуйте онлайн!
Юнит-тестирование с утверждениями, такими как:
ОБНОВЛЕНО: раньше я имел
но ответ Романа указал путь к более короткой версии. Обратите внимание, что сейчас
not_(std::plus<>)
плохо сформирован, где раньше это было эквивалентноstd::plus<>
; но такstd::plus<>
как «не представляет собой булеву церковь», я думаю, что любое поведение в порядке по правилам.источник
Forth (gforth) ,
133байта - 7 =126122Попробуйте онлайн!
-4 байта благодаря Quuxplusone
Первоначально я значительно обдумал это, рассматривая такие вещи, как макросы и литералы, но потом я понял, что если я определяю вещи в терминах «истина» и «ложь» (как я должен был это сделать в первую очередь), все становится намного проще.
Объяснение кода
источник
execute
три раза. Определение сокращений: j execute ;
сэкономит вам 4 байта.SKI-исчисление + C комбинатор, 36 байт
На самом деле я не знаю ни одного интерпретатора, который позволял бы вам определять дополнительные комбинаторы в терминах предыдущих, поэтому мне пришлось проверить это с помощью http://ski.aditsu.net/ , вставив нужные комбинаторы, например,
CCKK(SK)pq
выходные данныеq
, показывая, чтоK
не подразумеваетSK
.источник
Юлия 1,0 , 36 байт
Я не знаю, имеет ли это значение, я просто перегружаю нативный
Bool
тип, чтобы его можно было вызывать, поэтому я получаю большинство логических элементов бесплатно. К сожалению, у Джулии нетimplies
ворот, поэтому мне пришлось написать свою собственную функцию.Попробуйте онлайн!
источник
Perl 6 ,
120106102101 байт-1 байт благодаря Джо Кингу
Попробуйте онлайн!
источник
C ++ 17,
202−49 = 153193 - 58 = 135 байтовВдохновленный комментарием-обсуждением того, что в любом случае считается 2-арной функцией, вот карри версия моего предыдущего решения C ++ 17. Это на самом деле короче, потому что мы можем использовать тот же макрос для определения,
not_
что и для определения всех других функций!Попробуйте онлайн!
Этот проверен с утверждениями как
Обратите внимание, что
or_
определяется как эффективноМы могли бы определить
or_
более "кратко" какно это будет стоить нам, потому что мы больше не будем использовать
D
макрос.источник
True
иFalse
вместоtrue_
иfalse_
? И похоже на других операторов. Это сэкономит 12 байтов.APL (dzaima / APL) , 47 байтов SBCS
Основано на J-решении Джоны .
true
иfalse
являются инфиксными функциями,not
являются суффиксными операторами, а остальные являются инфиксными операторами.В соответствии с OP, это подсчитывает все от и
←
до конца каждой строки, и считает каждый вызов предыдущим определением как один байт.Попробуйте онлайн!
true и false - это левая и правая функции идентичности.
not
просто меняет аргументы своей функции операнда.Остальные реализуют дерево решений:
and
использует правую функцию,⍹
чтобы выбрать результат левой функции,⍶
если истина, иначе результатfalse
функции.or
использует левую функцию,⍶
чтобы выбратьtrue
if true, иначе результат правой функции⍹
.xor
использует правую функцию,⍹
чтобы выбрать отрицательный результат левой функции,⍶not
если истина, иначе результат левой функции.implies
использует левую функцию,⍶
чтобы выбрать результат правой функции,⍹
если истина, иначе результатtrue
функции.источник
Stax , 34 байта
Запустите и отладьте его на staxlang.xyz!
Вставляет кучу блоков в стек. Каждый блок ожидает свой последний аргумент поверх стека, за которым следуют в обратном порядке остальные.
Распаковано (41 байт):
Каждая пара
{ }
представляет собой блок. Я использовал два регистра X и Y для хранения,true
иnot
я мог легко получить к ним доступ позже. К сожалению, этоfalse
не может быть просто невозможностью, так как это оставит стек загроможденным и испортит один случай XOR.Тестовый набор, прокомментирован
источник
Befunge-98 ,
1057765 байтПродолжаем играть с понятием «функция» в языках без функций… вот версия церковных логических выражений Befunge-98!
В этом ограниченном диалекте Befunge-98 программа состоит из серии «линий» или «функций», каждая из которых начинается с
>
инструкции («Вправо») в столбце x = 0. Каждую «функцию» можно идентифицировать по номеру строки (координата y). Функции могут принимать данные через стек Befunge , как обычно.Строка 0 является особенной, потому что (0,0) является начальным IP. Чтобы создать программу, которая выполняет строку L, просто поместите инструкции в строку 0, которые, при выполнении, передают указатель инструкции на (x = L, y = 0).
Волшебство происходит в строке 1. Строка 1, когда выполняется, извлекает число
L
из стека и переходит на номер строкиL
. (Эта строка ранее была такой> >>0{{2u2}2}$-073*-\x
, что может «абсолютный переход» к любой строке; но я только что понял, что, поскольку я знаю, что эта строка привязана к строке 1, мы можем «относительный переход»L-1
строк в чертовом количестве кода намного меньше.)Линия 2 представляет церковь
FALSE
. При запуске она появляется два числаt
иf
из стека , а затем летит к номеру строкиf
.Строка 3 представляет церковь
TRUE
. При запуске она появляется два числаt
иf
из стека , а затем летит к номеру строкиt
.Строка 6, представляющая Церковь
XOR
, является инновационной. При выполнении она появляется два числа ,a
иb
из стека, а затем летит в линииa
с вводом стекаNOT EXEC b
. Итак, еслиa
представляет ЦерковьTRUE
, результатa NOT EXEC b
будетNOT b
; и еслиa
представляет церковьFALSE
, результатa NOT EXEC b
будетEXEC b
.Вот версия без присмотра с тестовой оснасткой. В строке 0 установите стек со своими данными. Например,
338
значитIMPLIES TRUE TRUE
. Убедитесь, что закрытиеx
появляется точно (x, y) = (0,15), иначе ничего не будет работать! Также убедитесь, что установка стека начинается с тогоba
, что программа фактически завершится с некоторым выводом.Попробуйте онлайн!
Вот версия, байты которой я посчитал.
Обратите внимание, что для определения функции на этом диалекте вы вообще не упоминаете ее имя; его «имя» определяется его исходным местоположением. Чтобы вызвать функцию, вы должны упомянуть ее «имя»; например,
XOR
(6
) определяется в терминахNOT
иEXEC
(5
и1
). Но все мои «имена функций» уже занимают только один байт. Таким образом, это решение не получает корректировок оценки.источник