Написать пост

Куайны (бесполезная программа в программе)

Аватар Типичный программист

Куайн (от анг. quine) — программа, результатом работы которой является собственный исходный код. Сразу оговоримся: программы, которые обращаются к файлам или производят считывание с клавиатуры куайнами не являются. Более серьезное ограничение: программы, которые могут напрямую получить доступ к своему исходному коду (средствами языка), также не являются куайнами.

Пример на Бейсике:

			10 LIST
		

Пример на Форте:

			SOURCE TYPE
		

А существуют ли они?

Несмотря на простую формулировку задания, потратив немного времени на ее решение, возникает вопрос: существуют ли вообще такие программы? Ответ: Да!

Более того, куайн существует в любом языке, способном выводить произвольную вычисляемую строку! Впервые эта идея была описана Полом Братли и Жаном Милло. А первым куайном считается программа, написанная на языке Atlas Autocode Хэмишем Дюаром.

А на современных языках?

Да пожалуйста:

JavaScript:

			function f(){alert(f.toString()+"f();");}f();
		

Pascal:

			program autobiografija (output);
  var c : array[1..14] of string[60];
      i : integer;
begin
  c[ 1]:='program autobiografija (output); ';
  c[ 2]:=' var c : array[1..14] of string[60]; ';
  c[ 3]:=' i : integer; ';
  c[ 4]:='begin ';
  c[ 5]:='for i := 1 to 4 do writeln(c[i]); ';
  c[ 6]:='for i := 1 to 13 do writeln(c[14,1],c[14,2],i:2,c[14,5], ';
  c[ 7]:=' c[14,6],c[14,7],c[14,8],c[i],c[14,8],c[14,9]); ';
  c[ 8]:='for i := 1 to 8 do write(c[14,i]); ';
  c[ 9]:='for i := 1 to 8 do write(c[14,i]); ';
  c[10]:='for i := 8 to 60 do write(c[14,i]); ';
  c[11]:='writeln(c[14,8],c[14,9]); ';
  c[12]:='for i := 5 to 13 do writeln(c[i]); ';
  c[13]:='end. ';
  c[14]:='c[14]:=''; ';
  for i := 1 to 4 do writeln(c[i]);
  for i := 1 to 13 do writeln(c[14,1],c[14,2],i:2,c[14,5],
             c[14,6],c[14,7],c[14,8],c[i],c[14,8],c[14,9]);
  for i := 1 to 8 do write(c[14,i]);
  for i := 1 to 8 do write(c[14,i]);
  for i := 8 to 60 do write(c[14,i]);
  writeln(c[14,8],c[14,9]);
  for i := 5 to 13 do writeln(c[i]);
end.
		

Итак. Мы убедились, что такие программы существуют, а теперь немного теории о том, как их сделать.

Грабли

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

Чтобы исправить положение, вообще не будем вносить в переменную сам факт присваивания. То есть:

			char c[]="char c[]=;";
		

После, во время вывода подставим значение с в её же определение.
Хорошо, но возникает проблема с кавычками. Языки, в которых определены одинарные и двойные кавычки, справляются с проблемой хорошо (мы говорим о том, что можно создать переменную q=” ‘ “, а потом вывести ее значение в ее определение), но что делать, например, с языком С? Экранирование, очевидно, не поможет, так как его тоже надо экранировать… В этом случае, можно задать кавычки кодом символа и вывести его.

Теперь остается проблема вставки строки в выходную строку с. Здесь вспомним про printf и всю его мощь.

			printf("%.2s", с+1);
		

Чаще всего методы взятия подстроки умеют брать её до конца:

			printf("%s", с+1);
		

Практика

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

PHP

			<?php $a="$"; $e='printf(\'<?php %sa="$"; %se=%s; eval(%se);\', $a, $a, var_export($e, 1), $a);'; eval($e);
		

SQL

			SELECT REPLACE(REPLACE('SELECT REPLACE(REPLACE("$",CHAR(34),CHAR(39)),CHAR(36),"$") AS Quine',CHAR(34),CHAR(39)),CHAR(36),'SELECT REPLACE(REPLACE("$",CHAR(34),CHAR(39)),CHAR(36),"$") AS Quine') AS Quine
		

Python

			q="'";s='q="";s=;print(s[:3]+q+s[3:7]+q+s+q+s[7:])';print(s[:3]+q+s[3:7]+q+s+q+s[7:])
		

Perl

			$_=q{$_=q{x};s/x/$_/;print};s/x/$_/;print
		

Высший пилотаж

Куайн, выводящий собственный код, это, конечно, хорошо. Но как вам идея куайна, который пишет другой код, являющийся куайном. Причем результатом работы последнего является первоначальный куайн! Заманчиво, не так ли?

Такого рода программы называются цепные куайны, и на сегодняшний день, самый большой цепной куайн (длина цепи уже достигла 100 языков) написан японцем Юсукэ Эндо.

Для того, чтобы работало:

			$ sudo apt-get install afnix algol68g aplus-fsf asymptote \
  ats-lang-anairiats bash bc bf boo bsdgames cduce clisp clojure1.4 \
  cmake coffeescript dc ecere-sdk emacs23 erlang f2c falconpl \
  fp-compiler fsharp g++ gambas3-script gap gauche gawk gcc gdc genius \
  gforth gfortran ghc ghostscript gnat gnu-smalltalk gnuplot gobjc \
  golang gpt gri groff groovy haxe icont iconx intercal iverilog \
  jasmin-sable julia kaya libgd2-xpm-dev libpng12-dev lisaac llvm lua5.2 \
  make maxima mlton mono-devel mono-mcs mono-vbnc nasm neko nickle ocaml \
  octave open-cobol openjdk-6-jdk pari-gp parrot perl php5-cli pike7.8 \
  python r-base ratfor regina-rexx rhino ruby2.0 scala scilab slsh \
  spl-core swi-prolog tcl ucblogo valac xsltproc yorick zoem
		

Ну и, соответственно, результат каждой программы нужно запускать самим:

			$ ruby QR.rb > QR.scala
$ scalac QR.scala && scala QR > QR.scm
$ gosh QR.scm > QR.sci
$ scilab -nw -nb -f QR.sci > QR.bash
$ bash QR.bash > QR.sl
$ slsh QR.sl > QR.st
$ gst QR.st > QR.spl
$ splrun QR.spl > QR.sml
$ mlton @MLton fixed-heap 200M -- QR.sml && ./QR > QR.sq
$ ruby vendor/subleq.rb QR.sq > QR.tcl
$ tclsh QR.tcl > QR.t
$ ruby vendor/thue.rb QR.t > QR.unl
$ ruby vendor/unlambda.rb QR.unl > QR.vala
$ valac QR.vala && ./QR > QR.v
$ iverilog -o QR QR.v && ./QR -vcd-none > QR.vb
$ vbnc QR.vb && mono ./QR.exe > QR.ws
$ ruby vendor/whitespace.rb QR.ws > QR.xslt
$ xsltproc QR.xslt > QR.yorick
$ yorick -batch QR.yorick > QR.azm
$ zoem -i QR.azm > QR.+
$ a+ QR.+ > qr.adb
$ gnatmake qr.adb && ./qr > QR.als
$ axi QR.als > QR.a68
$ a68g QR.a68 > QR.ante
$ ruby vendor/ante.rb QR.ante > QR.asy
$ asy QR.asy > QR.dats
$ atscc -o QR QR.dats && ./QR > QR.awk
$ awk -f QR.awk > QR.bc
$ BC_LINE_LENGTH=4000000 bc -q QR.bc > QR.bef
$ cfunge QR.bef > QR.Blc
$ ruby vendor/blc.rb < QR.Blc > QR.boo
$ booi QR.boo > QR.bf
$ bf QR.bf > QR.c
$ gcc -o QR QR.c && ./QR > QR.cpp
$ g++ -o QR QR.cpp && ./QR > QR.cs
$ mcs QR.cs && mono QR.exe > QR.cd
$ cduce QR.cd > QR.chef
$ PERL5LIB=vendor/local/lib/perl5 compilechef QR.chef QR.chef.pl &&
  perl QR.chef.pl > QR.clj
$ clojure QR.clj > QR.cob
$ cobc -O2 -x QR.cob && ./QR > QR.coffee
$ coffee QR.coffee > QR.lisp
$ clisp QR.lisp > QR.d
$ gdc -o QR QR.d && ./QR > QR.dc
$ dc QR.dc > QR.ec
$ ecp -c QR.ec -o QR.sym && ecc -c QR.ec -o QR.c && ecs -console QR.sym QR.imp -o QR.main.ec &&
  ecp -c QR.main.ec -o QR.main.sym && ecc -c QR.main.ec -o QR.main.c &&
  gcc -o QR QR.c QR.main.c -lecereCOM && ./QR > QR.el
$ emacs -Q --script QR.el > QR.erl
$ escript QR.erl > QR.fsx
$ fsharpc QR.fsx -o QR.exe && mono QR.exe > QR.fal
$ falcon QR.fal > QR.false
$ ruby vendor/false.rb QR.false > QR.fs
$ gforth QR.fs > QR.f
$ f2c QR.f && gcc -o QR QR.c -L/usr/lib -lf2c -lm && ./QR > QR.f90
$ gfortran -o QR QR.f90 && ./QR > QR.gbs
$ gbs3 QR.gbs > QR.g
$ gap -q QR.g > QR.gel
$ genius QR.gel > QR.plt
$ gnuplot QR.plt > QR.go
$ go run QR.go > QR.gpt
$ gpt -o QR QR.gpt && ./QR > QR.gri
$ gri QR.gri > QR.groovy
$ groovy QR.groovy > QR.hs
$ ghc QR.hs && ./QR > QR.hx
$ haxe -main QR -neko QR.n && neko QR.n > QR.icn
$ icont -s QR.icn && ./QR > QR.i
$ ick -bfO QR.i && ./QR > QR.j
$ jasmin QR.j && java QR > QR.java
$ javac QR.java && java QR > QR.js
$ rhino QR.js > QR.jl
$ julia QR.jl > QR.k
$ kayac QR.k && ./QR > QR.lazy
$ lazyk QR.lazy > qr.li
$ lisaac qr.li && ./qr > QR.ll
$ llvm-as QR.ll && lli QR.bc > QR.logo
$ logo QR.logo > QR.lol
$ lci QR.lol > QR.lua
$ lua QR.lua > QR.mk
$ make -f QR.mk > QR.mac
$ maxima -q --init-mac=QR.mac > QR.il
$ ilasm QR.il && mono QR.exe > QR.asm
$ nasm -felf QR.asm && ld -m elf_i386 -o QR QR.o && ./QR > QR.neko
$ nekoc QR.neko && neko QR.n > QR.5c
$ nickle QR.5c > QR.m
$ gcc -o QR QR.m && ./QR > QR.ml
$ ocaml QR.ml > QR.octave
$ octave -qf QR.octave > QR.ook
$ ruby vendor/ook-to-bf.rb QR.ook QR.ook.bf && bf QR.ook.bf > QR.gp
$ gp -f -q QR.gp > QR.pasm
$ parrot QR.pasm > QR.pas
$ fpc QR.pas && ./QR > QR.pl
$ perl QR.pl > QR.php
$ php QR.php > QR.png
$ npiet QR.png > QR.pike
$ pike QR.pike > QR.ps
$ gs -dNODISPLAY -q QR.ps > QR.ppt
$ ppt -d < QR.ppt > QR.prolog
$ swipl -q -t qr -f QR.prolog > QR.py
$ python QR.py > QR.R
$ R --slave -f QR.R > QR.r
$ ratfor -o QR.r.f QR.r && gfortran -o QR QR.r.f && ./QR > QR.rexx
$ rexx ./QR.rexx > QR2.rb
		

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

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

Куайны (бесполезная программа в программе) 1

По мотивам данных из интернета: один, два, три, WiKi, Habr.

Следите за новыми постами
Следите за новыми постами по любимым темам
10К открытий10К показов