Search
Write a publication
Pull to refresh

Comments 6

Спасибо за положительный отзыв! Значит, всё было не зря))

Возможность написания квайнов на некотором языке программирования считается доказательством тьюринг-полноты этого языка.

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

Например, на старинном бейсике из 1980-х годов мы можем написать такую программу:

10 LIST

Сама по себе она ничего не говорит о полноте языка.

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

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

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

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

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

Да, всегда есть место для подобных оговорок) Но все такие приёмы, вроде "ручного" чтения исходников из файла, или автоматическая предзагрузка исходников в память, как в интерпретируемом бейсике - это всё очевидное читерство, не имеющее отношение к проблеме квайнов. 

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

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

В чистом лиспе первого типа это будет, соответственно:

(let ((f (lambda (x) x))) (f f))

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

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

Если вы реализуете стек в куче, он не перестаёт от этого логически быть стеком. На мейнфреймах IBM вот вообще нет стека, как такового, адреса возвратов там принято сохранять в куче (для рекурсивных вызовов).

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

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

"Чистый" лисп нетипизирован, как и "чистое" лямбда-исчисление, рассморенное в статье. Это позволяет без костылей реализовать Y-комбинатор, потому что каждый терм там типа имеет "нечестный" тип `F = F => F`. Тема же данной статьи - конструктивные рекурсивыные типы в языке со статической типизацией (позволяющей проверять корректность алгоритма до его исполнения). Такие рекурсивные типы можно нормализовать, и их значения можно использовать.

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

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

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

Sign up to leave a comment.

Articles