Квайн без циклов и рекурсии

Question

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

Такую программу можно на любом популярном языке программирования, это известно. Но все решения обычно прибегают к циклам или рекурсии, чтобы обойти ограничения на объём печати. Ведь первый вопрос который надо решить: как напечатать текста больше, чем задано в строках в программе?

Отсюда задача: написать квайн без использования циклов и рекурсии.

Дополнение. Очень желательно чтобы решение было переносимым между языками. В конкретных языках есть средства вроде printf(s, s), которые здорово упрощают задачу, в других их нет. Хочется обойтись без них, если это возможно.

Answer 1

Чем не устраивает классика?

#include <stdio.h>

int main(void) {
    char *s = "#include <stdio.h>%c%cint main(void) {%c    char *s = %c%s%c;%c    printf(s,10,10,10,34,s,34,10,10,10,10);%c    return 0;%c}%c";
    printf(s,10,10,10,34,s,34,10,10,10,10);
    return 0;
}

Ни циклов, ни рекурсии...

Answer 2

Но все решения обычно прибегают к циклам или рекурсии, чтобы обойти ограничения на объём печати.

IMHO, проблемы не с объёмом печати, проблемы с возможностями преобразования.

А насчёт, ограничения ответа @Harry кодировками Unicode/UTF-8/ASCII/KOI8-R/Windows-1251 или остальными белорусскими, западноевропейскими, казахскими, украинскими и др. Из нескольких мне известных, которые были несовместимы с его решением, осталась одна, EBCDIC. Но встретить её непросто (последний раз у нас с ней была проблема, лет 15 назад - ошибка при сборке Java пакетов на zOS).

Впрочем, на современном C++, его легко перелицевать, причём станет краше, чем было. Вот пара вариантов, первый в стиле C:

#include <cstdio>

int main(void) {
    auto s = R"a(#include <cstdio>

int main(void) {
    auto s = R"a(%s)%s";
    printf(s, s, "a");
}
)a";
    printf(s, s, "a");
}

Альтернатива, по заветам комитета C++:

#include <print>

int main(void) {
    constexpr auto s = R"a(#include <print>

int main(void) {0:.1}
    constexpr auto s = R"a({1}){2}";
    std::print(s, "{0}", s, "a", "{3}");
{3}
)a";
    std::print(s, "{0:.1}", s, "a", "}");
}

Answer 3

Сперва покажу квайн с циклами, потом его вариант без циклов.

Квайн с циклами

Обычно квайн ассоциируется с использованием каких-то хитрых языковых конструкций, я попробую решить задачу минимумом средств. А именно: строковый литерал, функции с параметрами, циклы. Печать будет посимвольная, сейчас это излишество, а когда будем избавляться от циклов, пригодится.

Программа состоит из трёх блоков:

часть до строкового литерала (три строки или 39 символов);
строковый литерал;
часть после строкового литерала.

Первая часть не интересная: директива include, объявление строковой константы.

Вторая часть повторяет код программы в виде строки. Там много строк, которые компилятор C склеивает вместе. Из этой строки, которая повторяет код программы, вырезана вторая часть.

Третья часть самая интересная.

Функция p(i) печатает символ из литерала.

Функция r(i) тоже, но так, чтобы символ стал частью строки в C. Специальная обработка требуется для перевода строки \n, двойной кавычки " и обратного слеша \. Где нужно вставляется оформление для строк: отступ и кавычки.

main печатает три части программы в трёх циклах. Циклы "знают" размеры первой и третьей частей программы внутри строки. Первый и третий циклы вызывают p, второй r.

#include <stdio.h>

const char *code =
    "#include <stdio.h>\n"
    "\n"
    "const char *code =\n"
    ";\n"
    "\n"
    "void p(int i) {\n"
    "    putchar(code[i]);\n"
    "}\n"
    "\n"
    "void r(int i) {\n"
    "    if (i == 0 || code[i - 1] == '\\n') {\n"
    "        putchar(' ');\n"
    "        putchar(' ');\n"
    "        putchar(' ');\n"
    "        putchar(' ');\n"
    "        putchar('\"');\n"
    "    }\n"
    "    switch (code[i]) {\n"
    "    case '\\n':\n"
    "        putchar('\\\\');\n"
    "        putchar('n');\n"
    "        putchar('\"');\n"
    "        putchar('\\n');\n"
    "        break;\n"
    "    case '\"':\n"
    "        putchar('\\\\');\n"
    "        putchar('\"');\n"
    "        break;\n"
    "    case '\\\\':\n"
    "        putchar('\\\\');\n"
    "        putchar('\\\\');\n"
    "        break;\n"
    "    default:\n"
    "        putchar(code[i]);\n"
    "        break;\n"
    "    }\n"
    "}\n"
    "\n"
    "int main() {\n"
    "    for (int i = 0; i < 39; ++i) {\n"
    "        p(i);\n"
    "    }\n"
    "    for (int i = 0; i < 795; ++i) {\n"
    "        r(i);\n"
    "    }\n"
    "    for (int i = 39; i < 795; ++i) {\n"
    "        p(i);\n"
    "    }\n"
    "}\n"
;

void p(int i) {
    putchar(code[i]);
}

void r(int i) {
    if (i == 0 || code[i - 1] == '\n') {
        putchar(' ');
        putchar(' ');
        putchar(' ');
        putchar(' ');
        putchar('"');
    }
    switch (code[i]) {
    case '\n':
        putchar('\\');
        putchar('n');
        putchar('"');
        putchar('\n');
        break;
    case '"':
        putchar('\\');
        putchar('"');
        break;
    case '\\':
        putchar('\\');
        putchar('\\');
        break;
    default:
        putchar(code[i]);
        break;
    }
}

int main() {
    for (int i = 0; i < 39; ++i) {
        p(i);
    }
    for (int i = 0; i < 795; ++i) {
        r(i);
    }
    for (int i = 39; i < 795; ++i) {
        p(i);
    }
}

Квайн без циклов

Из предыдущей программы можно убрать циклы и вызовы процедур с параметрами. Взамен будет одна глобальная переменная.

Вводим глобальную переменную i – текущее место в строке. Вызов p0() печатает символ code[i] и увеличивает i. Функция p1 вызывает p0 два раза, p2 вызывает p1 два раза и так далее до p10.

Чтобы напечатать в main первые 39 символов надо будет сделать так: i = 0; p5(); p2(); p1(); p0();. p5печатает 32 символа, p2 – четыре, p1 – два, p0 – один. Всего 39.

Аналогично набираются вызовы r* для печати второй части. Третья снова печатается вызовами p*. Какие надо делать вызовы, определяется длиной программы. С другой стороны, добавление/удаление вызова меняет длину программы. Получается цикл, который может сойтись, может не сойтись. Поэтому печать второй и третьей частей выровнена комментариями так, чтобы при подборе вызовов длина программы не менялась.

#include <stdio.h>

const char *code =
    "#include <stdio.h>\n"
    "\n"
    "const char *code =\n"
    ";\n"
    "\n"
    "int i;\n"
    "\n"
    "void p0() { putchar(code[i++]); }\n"
    "\n"
    "void p1() { p0(); p0(); }\n"
    "void p2() { p1(); p1(); }\n"
    "void p3() { p2(); p2(); }\n"
    "void p4() { p3(); p3(); }\n"
    "void p5() { p4(); p4(); }\n"
    "void p6() { p5(); p5(); }\n"
    "void p7() { p6(); p6(); }\n"
    "void p8() { p7(); p7(); }\n"
    "void p9() { p8(); p8(); }\n"
    "void p10() { p9(); p9(); }\n"
    "\n"
    "void r0() {\n"
    "    if (i == 0 || code[i - 1] == '\\n') {\n"
    "        putchar(' ');\n"
    "        putchar(' ');\n"
    "        putchar(' ');\n"
    "        putchar(' ');\n"
    "        putchar('\"');\n"
    "    }\n"
    "    switch (code[i]) {\n"
    "    case '\\n':\n"
    "        putchar('\\\\');\n"
    "        putchar('n');\n"
    "        putchar('\"');\n"
    "        putchar('\\n');\n"
    "        break;\n"
    "    case '\"':\n"
    "        putchar('\\\\');\n"
    "        putchar('\"');\n"
    "        break;\n"
    "    case '\\\\':\n"
    "        putchar('\\\\');\n"
    "        putchar('\\\\');\n"
    "        break;\n"
    "    default:\n"
    "        putchar(code[i]);\n"
    "        break;\n"
    "    }\n"
    "    ++i;\n"
    "}\n"
    "\n"
    "void r1() { r0(); r0(); }\n"
    "void r2() { r1(); r1(); }\n"
    "void r3() { r2(); r2(); }\n"
    "void r4() { r3(); r3(); }\n"
    "void r5() { r4(); r4(); }\n"
    "void r6() { r5(); r5(); }\n"
    "void r7() { r6(); r6(); }\n"
    "void r8() { r7(); r7(); }\n"
    "void r9() { r8(); r8(); }\n"
    "void r10() { r9(); r9(); }\n"
    "\n"
    "int main() {\n"
    "    i = 0;\n"
    "    p5(); p2(); p1(); p0();\n"
    "    i = 0;\n"
    "    r10(); /* */ r8(); /* */ r6(); /* */ r4(); /*       */ r1(); /* */\n"
    "    i = 39;\n"
    "    p10(); /* */ p8(); /*       */ p5(); /* */ p3(); /* */ p1(); p0();\n"
    "}\n"
;

int i;

void p0() { putchar(code[i++]); }

void p1() { p0(); p0(); }
void p2() { p1(); p1(); }
void p3() { p2(); p2(); }
void p4() { p3(); p3(); }
void p5() { p4(); p4(); }
void p6() { p5(); p5(); }
void p7() { p6(); p6(); }
void p8() { p7(); p7(); }
void p9() { p8(); p8(); }
void p10() { p9(); p9(); }

void r0() {
    if (i == 0 || code[i - 1] == '\n') {
        putchar(' ');
        putchar(' ');
        putchar(' ');
        putchar(' ');
        putchar('"');
    }
    switch (code[i]) {
    case '\n':
        putchar('\\');
        putchar('n');
        putchar('"');
        putchar('\n');
        break;
    case '"':
        putchar('\\');
        putchar('"');
        break;
    case '\\':
        putchar('\\');
        putchar('\\');
        break;
    default:
        putchar(code[i]);
        break;
    }
    ++i;
}

void r1() { r0(); r0(); }
void r2() { r1(); r1(); }
void r3() { r2(); r2(); }
void r4() { r3(); r3(); }
void r5() { r4(); r4(); }
void r6() { r5(); r5(); }
void r7() { r6(); r6(); }
void r8() { r7(); r7(); }
void r9() { r8(); r8(); }
void r10() { r9(); r9(); }

int main() {
    i = 0;
    p5(); p2(); p1(); p0();
    i = 0;
    r10(); /* */ r8(); /* */ r6(); /* */ r4(); /*       */ r1(); /* */
    i = 39;
    p10(); /* */ p8(); /*       */ p5(); /* */ p3(); /* */ p1(); p0();
}

Последний квайн использует строковый литерал, вызовы функций без параметров (кроме putchar), одну глобальную переменную. Это всё, ни рекурсии, ни циклов. Даже печать сделана посимвольно, что бы избежать потенциального цикла в стандартной библиотеке при печати.

Что дальше?

Дальше можно думать, как избавиться от строки. Всё-таки это массив. Можно ли без массивов?

Есть вызов функции putchar с меняющимся параметром. Можно ли обойтись только вызовами функций с константами?

Есть одна глобальная переменная. Можно ли её убрать?

БЛОГ НА HUSL

Квайн без циклов и рекурсии

Ответы (3 шт):

Квайн с циклами

Квайн без циклов

Что дальше?