Пишем квайн-полиглот-палиндромы в честь дня 2^2^3

в 11:05, , рубрики: C#, java, palinndrome, polyglot, quine, Блог компании Positive Technologies, день программиста, квайн, ненормальное программирование, палиндром, полиглот

PalidromePolyglotQuine

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

Не так давно я узнал о коде, который может одновременно интерпретироваться в PHP и компилироваться в Java: PhpJava.java. Как оказалось, эта идея не нова: код, валидный сразу для нескольких компиляторов или интерпретаторов, называется полиглотом (polyglot). Такой код возможно писать из-за особенностей обработки строк и комментариев в различных интерпретаторах или компиляторах.

Например, в Java можно описывать символы как в обычном виде, например символ '/', так и в виде юникод-записи: 'u002F'. В компиляторе C# такие записи не будут валидными. Однако если их "спрятать" в комментарий, то, с одной стороны, они не будут мешать при компиляции C# кода, с другой — будут валидными в Java-коде. Например, если нужно, чтобы код A компилировался только в языке C#, но не компилировался в Java, а код B компилировался только в Java, но не компилировался в C#, нужно использовать следующий фрагмент:

//u000Au002Fu002A
A//u002Au002FB

C#-компилятор будет "воспринимать" этот код следующим образом:

//Comment
A//Comment

А Java так:

//
/*A*/B

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

Однако такими юникод-записями трюки не ограничиваются. Например, в C-подобных языках существуют директивы препроцессора, которые могут определять, какой код должен компилироваться, а какой нет. В некомпилируемый код можно помещать код совсем другого языка. Например, ниже приведен код-полиглот на C++ и Python (отсюда), в котором в секции #if false как раз и помещен код Python. А последовательности ''' начинают и заканчивают комментарий в коде Python.

#include <stdio.h>
#if false
print "Hello world"
'''
#endif
int main() {
printf("Hello world");
return 0;
}
#if false
'''
#endif

В HTML, например, комментарии начинаются с последовательности символов <!--, что также можно использовать. Есть и более сложные полиглоты, работающие одновременно на 6 и на 16 языках. Первый выводит сообщение "hitforum" для всех языков, а второй работает интересней: выводит название языка, на котором происходит его компиляция или интерпретация.

Код-полиглот на C, Shell, Perl, Brainfuck, Befunge, Whitespace

# define x u    /*            v
#    :::::::::::::::::::>>>>>>>$$$a"muroftih"#[>:#,_@]
eval 'echo "hitforum";exit';sub echo { print    "@_n"}               
__END__>++++++++++>++++++++++[>+++++++++++>++++++++++    
+<<-]>------.+.>++++++.<---.+++++++++.>--.+++                        
.<--.<<.    */
main() { printf ("hitforumn"); }

Код-полиглот на 16 язках

# /* [  <!-- */ include <stdio.h> /*    
    #`{{coding=utf-8
"true" if 0 != 0 and    q != """0"  ;   `   
    
if [ -n "$ZSH_VERSION" ]; then                  
    
    echo exec   echo I'm a zsh script.; 
    
elif [ -n "$BASH_VERSION" ]; then               
    
    echo exec   echo I'm a bash script.; 
else    
    echo exec   echo    I'm    a sh    script.;        
fi`;    #!;#
BEGIN{print"I'm a ", 0 ? "Ruby" :"Perl",    " program.n";  exit; }  
    #
%q~                     

set =dummy 0; puts [list "I'm"  "a" "tcl"   "script."]; exit      

all: ; @echo "I'm a Makefile."              
    #*/
/*: */ enum {a, b};                     
    
static int c99(void) {                  

 #ifndef __cplusplus /* bah */              

unused1: if ((enum {b, a})0)                
    (void)0;
 #endif                 

unused2:    return a;        
}   
static int trigraphs(void) {                
    
    return sizeof   "??!"   ==  2;       
}   
char X;                         
    
int main(void) {                    
    
    struct X    {            
    
        char    a[2];       
    };
    if (sizeof(X)   !=  1) {            
    
printf("I'm a C++ program (trigraphs %sabled).n",               
    
     trigraphs()    ? "en"  : "dis");
    
}else if (1//**/2

)unused3 : { ; 
        printf("I'm a C program (C%s, trigraphs %sabled).n", 
               c99() ? "89 with // comments" : "99", 
               trigraphs() ? "en" : "dis"); 
    } else { 
        printf("I'm a C program (C89, trigraphs %sabled).n", 
               trigraphs() ? "en" : "dis"); 
    } 
    return 0; 
} /*
 # 
begin{code}
import Prelude hiding ((:)); import Data.List (intercalate); import Language.Haskell.TH; import Data.String; default (S, String, Integer, Double); data S = S; instance Eq S where { _ == _ = False }; instance IsString S where { fromString = const S }; ifThenElse c t e = case c of True -> t; False -> e
cPP = False; {-
#define cPP True
-} main :: IO ()
main = putStr ("I'm a Literate Haskell program" ++ bonus ++ ".n") where
  _ = (); bonus | null details = "" | otherwise = " (" ++ details ++ ")"
  details = intercalate ", " [ name | (True, name) <- extensions ] :: String
  extensions =
    (bangPatterns,              "BangPatterns"             ) :
    (templateHaskell,           "TemplateHaskell"          ) :
    (rebindableSyntax,          "RebindableSyntax"         ) :
    (magicHash,                 "MagicHash"                ) :
    (overloadedStrings,         "OverloadedStrings"        ) :
    (noMonomorphismRestriction, "NoMonomorphismRestriction") :
    (scopedTypeVariables,       "ScopedTypeVariables"      ) :
    (cPP,                       "CPP"                      ) :
    (unicodeSyntax,             "UnicodeSyntax"            ) :
    (negativeLiterals,          "NegativeLiterals"         ) :
    (binaryLiterals,            "BinaryLiterals"           ) :
    (numDecimals,               "NumDecimals"              ) : []
  (!) = (!!)
  bangPatterns = [True] ! 0 where foo !bar = False
  templateHaskell = thc $(return (TupE []) :: ExpQ)
  rebindableSyntax = null (do { [()]; [()] })
    where _ >> _ = [] :: [()]
  magicHash = foo# () where
    foo = ['.']; "." # _  = False; foo# _ = True
  overloadedStrings = "" /= ""
  noMonomorphismRestriction = show foo == "0" where
    foo = 0
    bar = foo :: Double
  unicodeSyntax = let (★) = True in (*) where
    (*) = False
  negativeLiterals = -1 == NNa
  binaryLiterals = let b1 = 1 in 0b1 == 1
  numDecimals = show 0e0 == "0"
  scopedTypeVariables = stv (0 :: Double) == "0.0"
data{- = -} NN = NNa | NNb deriving Eq; instance Num NN where { fromInteger _ = NNa; negate _ = NNb; _ + _ = NNa; _ * _ = NNa; abs _ = NNa; signum _ = NNa }
instance{- = -} (Num a) => Num (e -> a) where { fromInteger = const . fromInteger; negate = (.) negate; abs = (.) abs; signum = (.) signum; x + y = e -> x e + y e; x * y = e -> x e * y e }
class THC a where { thc :: a -> Bool }; instance THC () where { thc _ = True }; instance THC (Q a) where { thc _ = False }; class (Show a, Num a) => STV a where
  stv :: a -> String
  stv = const $ show (f 0) where
    f = id :: a -> a
instance STV Double -- : 
end{code}

 # 
]>++++++++[<+++++++++>-]<+.>>++++[<++++++++++>-]<-.[-]>++++++++++ 
[<+++++++++++>-]<-.>>++++[<++++++++>-]<.>>++++++++++[<++++++++++> 
-]<- - -.<.>+.->>++++++++++[<+++++++++++>-]<++++.<.>>>++++++++++[ 
<++++++++++>-]<+++++.<<<<+.->>>>- - -.<+++.- - -<++.- ->>>>>+++++ 
+++++[<+++++++++++>-]<- - -.<<<<<.<+++.>>>.<<<-.- ->>>>+.<.<.<<.> 
++++++++++++++.[-]++++++++++""" else 0
 # 
from platform import * # 
print("I'm a Python program (%s %s)." % # [-][ 
(python_implementation(), python_version())); """--><html><head>
<!--:--><title>I'm a HTML page</title></head><body>
<!--:--><h1>I'm a <marquee><blink>horrible HTML</blink></marquee> page</h1>
<!--:--><script language="JavaScript">
<!--: # 
setTimeout( // 
   function () { // 
      document.body.innerHTML = "<h1>I'm a javascript-generated HTML page</h1>"; // 
   }, 10000); // 
//-->
</script><!--: 
</body></html><!-- }} # 
say "I'm a Perl6 program."; # """ # */
 #define FOO ]-->~

Квайн-полиглот

Для того чтобы написать квайн-полиглот на языках C# и Java, необходимо совместить принципы разработки квайна и полиглота. Как оказалось, и такая тема не нова: на сайте codegolf пользователи соревнуются, у кого квайн-полиглот или поликвайн получится короче: Write a Polyquine. Однако в этом вопросе не было вариантов с более многословными языками C# и Java, что мне и захотелось исправить.

Для написания такого квайна-полиглота нужно экранировать символы, запрещенные в строках обоих языков и встречающиеся в строках самой программы. Такими символами являются кавычки ", перенос строки n и обратный слеш . А чтобы еще уменьшить размер кода, повторяющиеся последовательности символов, такие как u000A, u002F и u002A, также были заменены на одиночные символы в самой кодирующей строке. Вот пример получившегося квайна-полиглота, валидного для компиляторов C# и Java:

PolyglotQuine.cs.java, 757 символов:

//u000Au002Fu002A
using System;//u002Au002F
class Program{public static void//u000Au002Fu002A
Main//u002Au002Fmain
(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.//u000Au002Fu002A
Replace//u002Au002Freplace
(""+(char)a[i],b[i]);//u000Au002Fu002A
Console.Write//u002Au002FSystem.out.printf
(t);}}

Квайн-полиглот-палиндром

Еще больше усложним задачу: попробуем написать квайн-полиглот-палиндром. Напомню, что палиндром — это число или текст, одинаково читающиеся в обоих направлениях. Принцип разработки квайнов-палиндромов я описывал в статье 3 года назад, тоже в день программиста. Принцип кода-палиндрома заключается в том, что зеркальная часть программы помещается в однострочный или многострочный комментарий, что не мешает при компиляции. Простейший код-палиндром в C# выглядит следующим образом:

/**/class P{static void Main(){}};/*/;}}{)(niaM diov citats{P ssalc/**/

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

Итак, объединяя принципы создания палиндрома, полиглота и квайна, я написал следующий код:

PalidromePolyglotQuine.cs.java, 1747 символов:

/**///u000Au002Fu002A
using System;//u002Au002F
class Program{public static void//u000Au002Fu002A
Main//u002Au002Fmain
(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.//u000Au002Fu002A
Replace//u002Au002Freplace
(""+(char)a[i],b[i]);t+='*';for(i=872;i>=0;i--)t=t+t//u000Au002Fu002A
[i];Console.Write//u002Au002F.charAt(i);System.out.printf
(t);}}/*/}};)t(
ftnirp.tuo.metsyS;)i(tArahc.F200uA200u//etirW.elosnoC;]i[
A200uF200uA000u//t+t=t)--i;0=>i;278=i(rof;'*'=+t;)]i[b,]i[a)rahc(+""(
ecalperF200uA200u//ecalpeR
A200uF200uA000u//.t=t)++i;9<i;0=i(rof;}s,"//","/","A200u\","F200u\","A000u\","\","n","""{][gnirtS wen=b][gnirtS;}63,36,69,59,53,46,83,49,33{][tni wen=a][tni;i tni;s=t,"/}};)t(^ftnirp.tuo.metsyS;)i(tArahc.#_?etirW.elosnoC;]i[^_#@?t+t=t)--i;0=>i;278=i(rof;'*'=+t;)]i[b,]i[a)rahc(+!!(^ecalper#_?ecalpeR^_#@?.t=t)++i;9<i;0=i(rof;}s,!?!,!`!,!_&!,!#&!,!@&!,!&&!,!n&!,!!&!{][gnirtS wen=b][gnirtS;}63,36,69,59,53,46,83,49,33{][tni wen=a][tni;i tni;s=t,!$!=s gnirtS{)z][gnirtS(^niam#_?niaM^_#@?diov citats cilbup{margorP ssalc^#_?;metsyS gnisu^_#@`?**`"=s gnirtS{)z][gnirtS(
niamF200uA200u//niaM
A200uF200uA000u//diov citats cilbup{margorP ssalc
F200uA200u//;metsyS gnisu
A200uF200uA000u///**/

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

Теперь проверим, как эта программа исполняется. Для начала избавимся от всех комментариев и правильно отформатируем код:

Отформатированный и очищенный код PalidromePolyglotQuine.cs.java под C#

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 была установлена).

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

Еще раз поздравляю всех программистов и сочувствующих!

Автор: Positive Technologies

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js