Пишем квайн-полиглот-палиндромы в честь дня программиста
Поздравляю всех трансляторов человеческого языка в машинный с их профессиональным днем, желаю вам меньше багов и больше-либо-равно классных идей! А в качестве идейного подарка со своей стороны предлагаю решение одной красивой задачи — написание кода, который на выходе выдаёт свой собственный текст, является валидным для интерпретаторов и компиляторов разных языков, и при этом правильно исполняется при реверсе исходников.
Не так давно я узнал о коде, который может одновременно интерпретироваться в PHP и компилироваться в Java: PhpJava.java. Как оказалось, эта идея не нова: код, валидный сразу для нескольких компиляторов или интерпретаторов, называется полиглотом (polyglot). Такой код возможно писать из-за особенностей обработки строк и комментариев в различных интерпретаторах или компиляторах.
Например, в Java можно описывать символы как в обычном виде, например символ '/', так и в виде юникод-записи: 'u002F'. В компиляторе C# такие записи не будут валидными. Однако если их «спрятать» в комментарий, то, с одной стороны, они не будут мешать при компиляции C# кода, с другой — будут валидными в Java-коде. Например, если нужно, чтобы код A компилировался только в языке C#, но не компилировался в Java, а код B компилировался только в Java, но не компилировался в C#, нужно использовать следующий фрагмент:
//\u000A\u002F\u002A
A//\u002A\u002FB
C#-компилятор будет «воспринимать» этот код следующим образом:
//Comment
A//Comment
А Java так:
//
/*A*/B
Комбинируя общие для обоих языков инструкции, а также разделяя различные, можно написать любую программу.
Однако такими юникод-записями трюки не ограничиваются. Например, в C-подобных языках существуют директивы препроцессора, которые могут определять, какой код должен компилироваться, а какой нет. В некомпилируемый код можно помещать код совсем другого языка. Например, ниже приведен код-полиглот на C++ и Python (отсюда), в котором в секции #if false
как раз и помещен код Python. А последовательности '''
начинают и заканчивают комментарий в коде Python.
#include
#if false
print "Hello world"
'''
#endif
int main() {
printf("Hello world");
return 0;
}
#if false
'''
#endif
В HTML, например, комментарии начинаются с последовательности символов
I'm a page
~
Квайн-полиглот
Для того чтобы написать квайн-полиглот на языках C# и Java, необходимо совместить принципы разработки квайна и полиглота. Как оказалось, и такая тема не нова: на сайте codegolf пользователи соревнуются, у кого квайн-полиглот или поликвайн получится короче: Write a Polyquine. Однако в этом вопросе не было вариантов с более многословными языками C# и Java, что мне и захотелось исправить.
Для написания такого квайна-полиглота нужно экранировать символы, запрещенные в строках обоих языков и встречающиеся в строках самой программы. Такими символами являются кавычки », перенос строки \n и обратный слеш \. А чтобы еще уменьшить размер кода, повторяющиеся последовательности символов, такие как \u000A, \u002F и \u002A, также были заменены на одиночные символы в самой кодирующей строке. Вот пример получившегося квайна-полиглота, валидного для компиляторов C# и Java:
PolyglotQuine.cs.java, 757 символов:
//\u000A\u002F\u002A
using System;//\u002A\u002F
class Program{public static void//\u000A\u002F\u002A
Main//\u002A\u002Fmain
(String[]z){String s="//@#'^using System;//'#^class Program{public static void//@#'^Main//'#main^(String[]z){String s=!$!,t=s;int[]a=new int[]{33,94,38,64,35,39,36};String[]b=new String[]{!&!!,!&n!,!&&!,!&@!,!!,!&'!,s};for(int i=0;i<7;i++)t=t.//@#'^Replace//'#replace^(!!+(char)a[i],b[i]);//@#'^Console.Write//'#System.out.printf^(t);}}",t=s;int[]a=new int[]{33,94,38,64,35,39,36};String[]b=new String[]{"\"","\n","\\","\\u000A","\\u002F","\\u002A",s};for(int i=0;i<7;i++)t=t.//\u000A\u002F\u002A
Replace//\u002A\u002Freplace
(""+(char)a[i],b[i]);//\u000A\u002F\u002A
Console.Write//\u002A\u002FSystem.out.printf
(t);}}
Квайн-полиглот-палиндром
Еще больше усложним задачу: попробуем написать квайн-полиглот-палиндром. Напомню, что палиндром — это число или текст, одинаково читающиеся в обоих направлениях. Принцип разработки квайнов-палиндромов я описывал в статье 3 года назад, тоже в день программиста. Принцип кода-палиндрома заключается в том, что зеркальная часть программы помещается в однострочный или многострочный комментарий, что не мешает при компиляции. Простейший код-палиндром в C# выглядит следующим образом:
/**/class P{static void Main(){}};/*/;}}{)(niaM diov citats{P ssalc/**/
Как видим, многострочный комментарий /*
начинается с середины и продолжается до конца, где и закрывается последовательностью */
. Пустой комментарий в начале нужен для того, чтобы строка полностью стала симметричной.
Итак, объединяя принципы создания палиндрома, полиглота и квайна, я написал следующий код:
PalidromePolyglotQuine.cs.java, 1747 символов:
/**///\u000A\u002F\u002A
using System;//\u002A\u002F
class Program{public static void//\u000A\u002F\u002A
Main//\u002A\u002Fmain
(String[]z){String s="`**?`@#_^using System;?_#^class Program{public static void?@#_^Main?_#main^(String[]z){String s=!$!,t=s;int i;int[]a=new int[]{33,94,38,64,35,95,96,63,36};String[]b=new String[]{!&!!,!&n!,!&&!,!&@!,!!,!&_!,!`!,!?!,s};for(i=0;i<9;i++)t=t.?@#_^Replace?_#replace^(!!+(char)a[i],b[i]);t+='*';for(i=872;i>=0;i--)t=t+t?@#_^[i];Console.Write?_#.charAt(i);System.out.printf^(t);}}/",t=s;int i;int[]a=new int[]{33,94,38,64,35,95,96,63,36};String[]b=new String[]{"\"","\n","\\","\\u000A","\\u002F","\\u002A","/","//",s};for(i=0;i<9;i++)t=t.//\u000A\u002F\u002A
Replace//\u002A\u002Freplace
(""+(char)a[i],b[i]);t+='*';for(i=872;i>=0;i--)t=t+t//\u000A\u002F\u002A
[i];Console.Write//\u002A\u002F.charAt(i);System.out.printf
(t);}}/*/}};)t(
ftnirp.tuo.metsyS;)i(tArahc.F200u\A200u\//etirW.elosnoC;]i[
A200u\F200u\A000u\//t+t=t)--i;0=>i;278=i(rof;'*'=+t;)]i[b,]i[a)rahc(+""(
ecalperF200u\A200u\//ecalpeR
A200u\F200u\A000u\//.t=t)++i;9i;278=i(rof;'*'=+t;)]i[b,]i[a)rahc(+!!(^ecalper#_?ecalpeR^_#@?.t=t)++i;9
К сожалению, монстр получился слишком большим (1747 символов), однако это объясняется длинными цепочками юникод-символов и многословностью языков C# и Java. Уверен, что на других языках можно будет написать квайн-палиндром-полиглот гораздо меньшего размера.
Теперь проверим, как эта программа исполняется. Для начала избавимся от всех комментариев и правильно отформатируем код:
using System;
class Program
{
public static void Main(String[] z)
{
String s = "`**?`@#_^using System;?_#^class Program{public static void?@#_^Main?_#main^(String[]z){String s=!$!,t=s;int i;int[]a=new int[]{33,94,38,64,35,95,96,63,36};String[]b=new String[]{!&!!,!&n!,!&&!,!&@!,!!,!&_!,!`!,!?!,s};for(i=0;i<9;i++)t=t.?@#_^Replace?_#replace^(!!+(char)a[i],b[i]);t+='*';for(i=872;i>=0;i--)t=t+t?@#_^[i];Console.Write?_#.charAt(i);System.out.printf^(t);}}/",
t = s;
int i;
int[] a = new int[] { 33, 94, 38, 64, 35, 95, 96, 63, 36 };
String[] b = new String[] { "\"", "\n", "\\", "\\u000A", "\\u002F", "\\u002A", "/", "//", s };
for (i = 0; i < 9; i++)
t = t.Replace("" + (char)a[i], b[i]);
t += '*';
for (i = 872; i >= 0; i--)
t = t + t[i];
Console.Write(t);
}
}
Из листинга становится понятно, что переменная s
содержит код программы, в котором экранированы запрещенные в строках символы и сжаты повторяющиеся последовательности. Ниже представлена таблица символов в формате код — символ — замена, которая используется для формирования выводимой строки t
.
код | символ | замена |
---|---|---|
33 | ! | » |
94 | ^ | \n |
38 | & | \ |
64 | @ | \u000A |
35 | # | \u002F |
95 | _ | \u002A |
96 | ` | / |
63 | ? | // |
36 | $ | s |
На следующем этапе происходит конкатенация строки t
с ней же, инвертированной для того, чтобы на выходе получился палиндром. Стоит отметить, что число 872 (длина строки t
) необходимо просчитывать после того, как квайн уже был написан. А для этого необходимо запускать уже написанный код, что также представляет определенные сложности.
Главным критерием при написании такого кода было достижение наименьшего размера в текстовом виде, а не его чистота. Поэтому, понятное дело, выглядит он несколько странно.
Как видим, ничего сложного в написании таких квайнов нет. Для тех, кто не верит, что это все действительно работает, были написаны тесты в репозитории Freaky-Sources (для запуска требуется, чтобы Java была установлена).
Кидайте в комментарии ваши квайнды-палиндромы-полиглоты на других языках и другие интересные кодофричные вещи, с удовольствием их изучу.
Еще раз поздравляю всех программистов и сочувствующих!
Комментарии (3)
12 сентября 2016 в 14:10
–1↑
↓
Зачем все это…12 сентября 2016 в 14:16
0↑
↓
Но 2^2^2 ведь равно 16…Но это все мелочи, работа проделана впечатляющая! Очень круто.
12 сентября 2016 в 14:19
0↑
↓
Спасибо, уже исправил! К сожалению, заметил это уже после публикации.