Инструмент для создания самореферентных программ?

Question

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

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

РЕДАКТИРОВАТЬ : Основываясь на предложении @Henning Makholm, я решил просто сесть и реализовать такую ​​программу. Результирующая программа (которую я назвал "kleene") принимает в качестве входных данных программу C ++ и создает новую программу C ++, которая может получить доступ к своему собственному исходному коду, вызвав функцию kleene::MySource(). Это означает, что вы можете преобразовать эту очень простую программу в Quine, используя программу kleene:

#include <iostream>

int main() {
    std::cout << kleene::MySource() << std::endl;
}

Если вам интересно проверить его, он доступен здесь, на моем сайте .

Answer 1

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

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

Answer 2

Наш набор инструментов для реинжиниринга программного обеспечения DMS - это система преобразования программ , которая будет принимать программы в произвольном синтаксисе (описывается DMS в явном параметре, называемом «описанием домена»), анализ Их можно преобразовать в AST, выполнить анализ и преобразование AST, а также восстановить рецензированный текст программы из модифицированной версии.

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

И да, ваше замечание о таком инструменте, обеспечивающем отражение для произвольных языков, шокирует. Большинство средств отражения, предоставляемых в языках, разрешают доступ только к тем вещам, которые люди языкового компилятора считали первостепенно важными для доступа во время выполнения, таким как «имена методов». Вещи , которых они не интересовали, конечно же, недоступны; когда-нибудь видел механизм отражения, который скажет вам, что в выражении? В комментарии?

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