Quining Нетронутый мир

16

Эта задача основана на вопросе Хельки Хомбы « Программирование первозданного мира» . Исходя из этого вопроса, определение нетронутой программы:

Давайте определим нетронутую программу как программу, которая сама по себе не имеет никаких ошибок, но выдаст ошибку, если вы измените ее, удалив любую смежную подстроку из N символов, где 1 <= N < program length.

Например, трехсимвольная программа Python 2

`8`

является нетронутой программой ( спасибо, Sp ), потому что все программы, возникающие в результате удаления подстрок длины 1, вызывают ошибки (на самом деле синтаксические ошибки, но любой тип ошибок будет делать):

8`
``
`8

а также все программы, возникающие в результате удаления подстрок длины 2, вызывают ошибки:

`
`

Например, `8если бы программа была без ошибок, `8`она не была бы нетронутой, поскольку все результаты удаления подстроки должны содержать ошибки.

Примечания:

  • Предупреждения компилятора не считаются ошибками.
  • Подпрограммы с ошибками могут принимать входные данные или выдавать выходные данные или делать что-либо еще, если они дают ошибку независимо от того, что в итоге.

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

Кратчайший ответ в байтах для каждого языка выигрывает.

Shelvacu
источник
Я предполагаю, что языки без ошибок не могут конкурировать?
ATaco
@ATaco К сожалению, да. Другие языки, такие как lisp, имеют синтаксис, структурированный таким образом, что создание полезной нетронутой программы невозможно.
Шелваку
RIP На самом деле / ​​Серьезно
ATaco
«Кратчайший ответ в байтах для каждого языка выигрывает». Я не уверен, что короткая позиция - лучшая мера для нетронутой программы.
P.
@ P.Siehr Что бы вы порекомендовали вместо этого?
Шелваку

Ответы:

6

Haskell , 132 байта

q x=if length x==132then putStr x else fail[];main=q$(++)<*>show$"q x=if length x==132then putStr x else fail[];main=q$(++)<*>show$"

Попробуйте онлайн!

Это продолжение квайн

main=putStr$(++)<*>show$"main=putStr$(++)<*>show$"

который работает, объединяя строку данных с цитируемой версией (используя show) себя и печатая результат. Однако это не является нетронутым, поскольку любые символы в строке данных можно удалить без сбоев, а также можно удалить часть $(++)<*>show$или (++)<*>часть без прерывания программы.

Чтобы исправить это, определяется пользовательская функция печати, qкоторая проверяет длину заданной строки и вызывает ее, failесли она короче 132. Это отслеживает удаление любой последовательности из строки данных, а также удаление $(++)<*>show$или (++)<*>, как в обоих случаях строка передается qкороче.

В qчисло 132можно сократить до 1, 13, 32или 2, но в каждом случае снова failвызывается.

Насколько я могу судить, удаление любой другой подстроки вызывает ошибку синтаксиса или типа, поэтому программа даже не компилируется в первую очередь. (Строгая система типов Haskell пригодится здесь.)

Редактировать: Спасибо Орджану Йохансену и Шелваку за указание на недостатки!

Laikoni
источник
Я боюсь, что fail[]|length x/=122могут быть удалены. fail[]:[putStr x|length x==122]может работать лучше
Орджан Йохансен
Ага, нет, тогда |length x==122можно было бы удалить. if length x==122 then putStr x else fail[]возможно?
Эрджан Йохансен
@ ØrjanJohansen Хороший улов, у меня был if then elseраньше, но думал, что могу сократить его.
Лайкони
2
putStr xможет стать p x, что, когда я пытался на моей системе работать очень долго, прежде чем я убил его, я подозреваю, что рекурсия хвостового вызова была оптимизирована, так что это бесконечный цикл. Я не знаю достаточно Haskell, чтобы дать какие-либо предложения о том, как это исправить.
Шелваку
@Shelvacu Упс. Переименование , pчтобы qследует исправить.
Орджан Йохансен
4

Python 3 , 113 байт

for[]in{113:[]}[open(1,"w").write((lambda s:s%s)('for[]in{113:[]}[open(1,"w").write((lambda s:s%%s)(%r))]:a'))]:a

Попробуйте онлайн!

Как это устроено

Мы не можем легко использовать несколько операторов, так как второй может быть удален, поэтому мы начнем с одного выражения quine:

print((lambda s:s%s)('print((lambda s:s%%s)(%r))'))

Чтобы защитить его от удаления подстрок, мы используем open(1,"w").writeвместо print. В Python 3 writeвозвращает количество написанных символов, которое мы проверим, 113чтобы убедиться, что ни одна часть строки не была удалена. Мы делаем это, просматривая возвращаемое значение в словаре {113:[]}и циклически перебирая результат с for[]in…:a, что завершится ошибкой, если мы не получили пустую итерацию или forоператор был удален.

Андерс Касеорг
источник
1
Не могли бы вы объяснить, как работает ваш код?
Шелваку
@Shelvacu Да, добавил.
Андерс Касеорг
3

Рубин, 78 байт

eval(*[($>.write((s=%{eval(*[($>.write((s=%%{%s})%%s)-78).chr])})%s)-78).chr])

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

Объяснение:

  • eval(*[ выраж ])

    Это оценивает любой код, возвращаемый как программа ruby. Это эффективно проверяет, что строка, которую возвращает код, является допустимой программой ruby. Удобно, что программы ruby ​​могут быть пустыми или состоять только из пробелов.

    Оператор «splat» *позволяет использовать массив в качестве аргументов функции. Это также означает, что если evalудалить, результирующая программа является (*[ expr ]) , который не является допустимым ruby.

  • ($>.write( ул )-78).chr

    $> короткая переменная для STDOUT.

    $>.write(foo) записывает foo в STDOUT и, что важно для этого кода, возвращает количество записанных байтов.

    $>.write(foo)-78: Здесь 78указана длина программы, поэтому, если программа не искажена, будет также число записанных байтов. Таким образом, в нераскрытом случае это вернет ноль.

    num.chrвозвращает num как символ, например 0.chr, вернет строку, содержащую один нулевой байт. В неуправляемой программе это даст строку с единственным нулевым байтом eval, который является допустимой программой ruby, которая является неоперативной.

    Кроме того, программа может удалить подстроку так, чтобы она была равна просто eval(*[(78).chr])или eval(*[(8).chr]), что означает, что числовая константа не может заканчиваться каким-либо из чисел (0, 4, 9, 10, 11, 12, 13, 26, 32, 35, 48 , 49, 50, 51, 52, 53, 54, 55, 56, 57, 59, 64, 95), поскольку они являются кодами ascii для допустимых односимвольных программ ruby.

  • %{ ул }

    Это менее известный синтаксис для строковых литералов в ruby. Причина, по которой он здесь используется, заключается {}в том, что в строке могут использоваться сбалансированные пары , что означает, что этот синтаксис может содержать сам себя. Например, так %{foo{bar}}же, как "foo{bar}".

  • (s=%{ данные })%s

    Это определяет переменную, sкоторая является данными этого quine, как строку printf.

    Назначения в ruby ​​возвращают то, что было назначено, так что это то же самое, что сначала присвоение, sа затем запускs%s

    %на строке синтетический сахар для рубинового эквивалента sprintf. В %sЗначит , где в данных сами данные должны быть встроены.

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

Shelvacu
источник
3

Стандартный ML (MLton) , 204 182 189 байт

val()=hd[(fn s=>let val$ =s^"\""^String.toString s^"\"]"val(189,%)=(size$,$)in print%end)"val()=hd[(fn s=>let val$ =s^\"\\\"\"^String.toString s^\"\\\")\"val(189,%)=(size$,$)in print%end)"]

Попробуйте онлайн!

Для MLton, полные программы SML являются либо выражения с разделителями и заканчивали ;(например print"Hello";print"World";) или заявление с varи funключевыми словами (например var _=print"Hello"var _=print"World") , где _дикая карта , которая также может быть заменена любым именем переменным.

Первый вариант бесполезен для нетронутого программирования, потому что сам ;по себе является допустимой программой (которая ничего не делает, но и не выдает ошибку). Проблема со вторым подходом заключается в том, что объявления вроде var _=print"Hello"могут быть сокращены до просто var _="Hello"(или дажеvar _=print ), потому что объявление with varработает до тех пор, пока правая часть является допустимым выражением или значением SML (SML является функциональным языком, поэтому функции могут быть используется в качестве значения тоже).

В этот момент я был готов объявить невозможным программирование на SML, когда случайно наткнулся на сопоставление с образцом в val-declarations. Оказывается, что синтаксис для объявлений не является, val <variable_name> = <expression>но val <pattern> = <expression>, где шаблон может состоять из имен переменных, констант и конструкторов. Поскольку printфункция имеет тип string -> unit, мы можем использовать сопоставление с образцом на unit-value ()для обеспечения , что функция печати фактически применяется к строке: val()=print"Hey". При таком подходе, удаление либо printили "Hey"результатов в Pattern and expression disagree-ошибка.

С этим способом первичной печати под рукой, следующий шаг должен написать quine прежде, чем наконец будет добавлено еще какое-то сохранение защиты. Ранее я использовал простую технику SML quine (см. Историю изменений ), но Андерс Касорг указал на другой подход, который может сэкономить несколько байтов в его случае. Он использует встроенную String.toStringфункцию для обработки экранирования строки и имеет общий вид <code>"<data>", где "<data>"экранированная строка из codebefore:

val()=(fn s=>print(s^"\""^String.toString s^"\""))"val()=(fn s=>print(s^\"\\\"\"^String.toString s^\"\\\"\"))"

Это рабочая хама, но еще нетронутая. Прежде всего, Андерс Касорг обнаружил, что MLton принимает одинарную кавычку "как код без ошибок, что означает, что у нас не может быть кода, заканчивающегося кавычкой, как указано выше. Кратчайший способ предотвратить это - заключить в val()=скобки все после , но затем код можно сократить до val()=(). Второй самый короткий способ, который я нашел, это использоватьval()=hd[ ... ] , то есть мы заключаем все в список и возвращаем его первый элемент, чтобы радовать проверку типов.

Чтобы убедиться, что ни одна часть строки данных не может быть удалена без valзамечаний, сопоставление с образцом в -declarations снова пригодится: длина конечной строки для печати (и, следовательно, длина программы) должна быть равна 195, поэтому мы можем написать let val t=... val 195=size t in print t endв теле fnабстракции вместо print(...). Удаление части строки приводит к длине меньше 189, что вызывает Bindисключение.

Осталась еще проблема: весь val 195=size tчек можно было просто отбросить. Мы можем предотвратить это, расширив проверку на соответствие в кортеже:, val t=... val(216,u)=(n+size t,t)in print u endтак что удаление проверки приведет к появлению несвязанной переменной u.

В целом это дает следующее 195-байтовое решение:

val()=hd[(fn s=>let val t=s^"\""^String.toString s^"\")"val(195,u)=(size t,t)in print u end)"val()=hd[(fn s=>let val t=s^\"\\\"\"^String.toString s^\"\\\")\"val(195,u)=(size t,t)in print u end)"]

Применение игры в гольф трюк с использованием имен переменных оператор , как !, $и %вместо того n, tи uдля того , чтобы сэкономить немного белого пространства (см этот отзыв ) приводит к окончательной версии 182 байт.

Все другие удаления-подстроки, которые явно не указаны в объяснении, должны приводить к синтаксической ошибке или ошибке типа.

Редактировать 1: length(explode t) просто size t.
Редактировать 2: Спасибо Anders Kaseorg за другой подход к квине и указание на «уязвимость».

Laikoni
источник
-2 байта , записывая "\""напрямую и используя String.toStringдля экранирования.
Андерс Касеорг
Подождите, это ужасно: MLton, кажется, принимает программу ", выдающую пустой вывод ( TIO ).
Андерс Касеорг
@AndersKaseorg Да, это странно. Однако должна быть возможность исправить эту проблему с помощью другого let ... in ... end.
Лайкони
@AndersKaseorg Я исправил проблему, надеюсь, не вводя новых «уязвимостей».
Лайкони
На самом деле я рассматривал принятие MLton "в качестве программы, и похоже, что ошибка была исправлена ​​в этом коммите , поэтому, возможно, ваш 182 или мой 180 в порядке, если вы укажете невыпущенную версию MLton для Git.
Андерс Касеорг