Quine (obliczenia) - Quine (computing)

Dane wyjściowe quine są dokładnie takie same, jak ich kod źródłowy. (Zauważ, że podświetlanie składni pokazane przez edytor tekstu w górnej połowie obrazu nie wpływa na wyjście quine.)

Quine to program komputerowy, który nie bierze wejście i tworzy kopię własnego kodu źródłowego jako jedynego wyjścia. Standardowe terminy dla tych programów w teorii obliczalności i literaturze informatycznej to „programy samopowielające się”, „programy samoodtwarzające się” i „programy samokopiujące”.

Quine jest stałym punktem środowiska wykonawczego, gdy środowisko wykonawcze jest postrzegane jako funkcja przekształcająca programy w ich dane wyjściowe. Quines są możliwe w dowolnym języku programowania Turing-complete , jako bezpośrednia konsekwencja twierdzenia Kleene'a o rekurencji . Dla rozrywki programiści czasami próbują opracować jak najkrótszy quine w dowolnym języku programowania .

Nazwa „quine” została ukuta przez Douglasa Hofstadtera , w jego popularnonaukowej książce Gödel, Escher, Bach , na cześć filozofa Willarda Van Ormana Quine'a (1908-2000), który dokonał obszernych badań na temat pośredniego samoodniesienia , a w szczególności dla następującego wyrażenia wywołującego paradoks, znanego jako paradoks Quine'a :

„Wydaje fałsz, gdy jest poprzedzone jego cytatem” daje fałsz, gdy jest poprzedzone jego cytatem.

Historia

Pomysł samoreprodukujących się automatów pojawił się od zarania informatyki, jeśli nie wcześniej. John von Neumann teoretyzował na ich temat w latach 40. XX wieku. Później artykuł Paula Bratleya i Jeana Millo „Computer Recreations: Self-Reproducing Automata” omówił je w 1972 roku. Bratley po raz pierwszy zainteresował się programami do samodzielnego odtwarzania po obejrzeniu pierwszego znanego takiego programu napisanego w Atlas Autocode w Edynburgu w latach 60. przez uniwersytet wykładowcy i badacza Edynburga Hamisha Dewara .

Wymóg „źródła pobierania” licencji Affero General Public License opiera się na idei quine.

Przykłady

Konstruktywne quines

Ogólnie rzecz biorąc, metodą używaną do tworzenia quine w dowolnym języku programowania jest posiadanie w programie dwóch części: (a)  kodu używanego do faktycznego drukowania oraz (b)  danych reprezentujących tekstową formę kodu. Kod działa, wykorzystując dane do wydrukowania kodu (co ma sens, ponieważ dane reprezentują tekstową formę kodu), ale wykorzystuje również dane przetworzone w prosty sposób, aby wydrukować tekstową reprezentację samych danych.

Oto trzy małe przykłady w Python3: 

a='a=%s%s%s;print(a%%(chr(39),a,chr(39)))';print(a%(chr(39),a,chr(39)))
b='b={}{}{};print(b.format(chr(39),b,chr(39)))';print(b.format(chr(39),b,chr(39)))
c='c=%r;print(c%%c)';print(c%c)
#note that %r will quote automatically

W Pythonie 3.8: 

exec(s:='print("exec(s:=%r)"%s)')

Poniższy kod Java demonstruje podstawową strukturę quine. 

public class Quine
{
  public static void main(String[] args)
  {
    char q = 34;      // Quotation mark character
    String[] l = {    // Array of source code
    "public class Quine",
    "{",
    "  public static void main(String[] args)",
    "  {",
    "    char q = 34;      // Quotation mark character",
    "    String[] l = {    // Array of source code",
    "    ",
    "    };",
    "    for(int i = 0; i < 6; i++)           // Print opening code",
    "        System.out.println(l[i]);",
    "    for(int i = 0; i < l.length; i++)    // Print string array",
    "        System.out.println(l[6] + q + l[i] + q + ',');",
    "    for(int i = 7; i < l.length; i++)    // Print this code",
    "        System.out.println(l[i]);",
    "  }",
    "}",
    };
    for(int i = 0; i < 6; i++)           // Print opening code
        System.out.println(l[i]);
    for(int i = 0; i < l.length; i++)    // Print string array
        System.out.println(l[6] + q + l[i] + q + ',');
    for(int i = 7; i < l.length; i++)    // Print this code
        System.out.println(l[i]);
  }
}

Kod źródłowy zawiera własną tablicę ciągów, która jest wyprowadzana dwukrotnie, raz w cudzysłowie.

Ten kod został zaadaptowany z oryginalnego posta z c2.com, gdzie autor, Jason Wilson, opublikował go jako minimalistyczną wersję Quine'a, bez komentarzy Javy.

Dzięki nowej funkcji bloków tekstowych w Javie 15 (lub nowszej) możliwa jest bardziej czytelna i prostsza wersja: 

public class Quine {
	public static void main(String[] args) {
		String textBlockQuotes = new String(new char[]{'"', '"', '"'});
		char newLine = 10;
		String source = """
public class Quine {
	public static void main(String[] args) {
		String textBlockQuotes = new String(new char[]{'"', '"', '"'});
		char newLine = 10;
		String source = %s;
		System.out.print(source.formatted(textBlockQuotes + newLine + source + textBlockQuotes));
	}
}
""";
		System.out.print(source.formatted(textBlockQuotes + newLine + source + textBlockQuotes));
	}
}

Eval quines

Niektóre języki programowania mają możliwość oceny ciągu jako programu. Quines może skorzystać z tej funkcji. Na przykład ta chinka Ruby : 

eval s="print 'eval s=';p s"

Lua potrafi: 

s="print(string.format('s=%c%s%c; loadstring(s)()',34,s,34))"; loadstring(s)()

"Oszukujące" quines

Samoocena

W wielu językach funkcjonalnych, w tym Scheme i innych Lispach , a także w językach interaktywnych, takich jak APL , liczby oceniają się samoczynnie. W TI-BASIC , jeśli ostatni wiersz programu jest zwracaną wartością, zwracana wartość jest wyświetlana na ekranie. Dlatego w takich językach program zawierający pojedynczą cyfrę daje w wyniku 1-bajtową chinę. Ponieważ taki kod nie tworzy się sam, jest to często uważane za oszustwo. 

1

W niektórych językach, szczególnie w językach skryptowych, ale także C , pusty plik źródłowy jest stałym punktem języka, będąc prawidłowym programem, który nie generuje żadnych danych wyjściowych. Taki pusty program złożony jako „najmniejszej na świecie samodzielnego odtwarzania programu”, gdy wygrał „najgorszy nadużycie regulaminu” nagrody w International Obfuscated C Code Contest . Program nie został w rzeczywistości skompilowany, ale został użyty cpdo skopiowania pliku do innego pliku, który można było wykonać, aby nic nie wydrukować.

Inne wątpliwe techniki obejmują korzystanie z komunikatów kompilatora; na przykład w środowisku GW-BASIC wprowadzenie „Błąd składni” spowoduje, że interpreter odpowie „Błąd składni”.

Kontrola kodu źródłowego

Quine, z definicji, nie może otrzymywać żadnych danych wejściowych, w tym odczytywania pliku, co oznacza, że ​​quine jest uważane za „oszukujące”, jeśli patrzy na swój własny kod źródłowy. Poniższy skrypt powłoki nie jest quine: 

#!/bin/sh
# Invalid quine.
# Reading the executed file from disk is cheating.
cat $0

Programy Uroboros

Koncepcję quine można rozszerzyć na wiele poziomów rekurencji, tworząc "programy uroboros " lub przekaźniki quine. Nie należy tego mylić z multichinami .

Przykład

Ten program Java wyprowadza źródło programu C++, który wyprowadza oryginalny kod Java. 

#include <iostream>
#include <string>
using namespace std;

int main(int argc, char* argv[])
{
    char q = 34;
    string l[] = {
    "    ",
    "=============<<<<<<<< C++ Code >>>>>>>>=============",
    "#include <iostream>",
    "#include <string>",
    "using namespace std;",
    "",
    "int main(int argc, char* argv[])",
    "{",
    "    char q = 34;",
    "    string l[] = {",
    "    };",
    "    for(int i = 20; i <= 25; i++)",
    "        cout << l[i] << endl;",
    "    for(int i = 0; i <= 34; i++)",
    "        cout << l[0] + q + l[i] + q + ',' << endl;",
    "    for(int i = 26; i <= 34; i++)",
    "        cout << l[i] << endl;",
    "    return 0;",
    "}",
    "=============<<<<<<<< Java Code >>>>>>>>=============",
    "public class Quine",
    "{",
    "  public static void main(String[] args)",
    "  {",
    "    char q = 34;",
    "    String[] l = {",
    "    };",
    "    for(int i = 2; i <= 9; i++)",
    "        System.out.println( l[i] );",
    "    for(int i = 0; i < l.length; i++)",
    "        System.out.println(l[0] + q + l[i] + q + ',');",
    "    for(int i = 10; i <= 18; i++)",
    "        System.out.println(l[i]);",
    "  }",
    "}",
    };
    for(int i = 20; i <= 25; i++)
        cout << l[i] << endl;
    for(int i = 0; i <= 34; i++)
        cout << l[0] + q + l[i] + q + ',' << endl;
    for(int i = 26; i <= 34; i++)
        cout << l[i] << endl;
    return 0;
}

public class Quine
{
  public static void main(String[] args)
  {
    char q = 34;
    String[] l = {
    "    ",
    "=============<<<<<<<< C++ Code >>>>>>>>=============",
    "#include <iostream>",
    "#include <string>",
    "using namespace std;",
    "",
    "int main(int argc, char* argv[])",
    "{",
    "    char q = 34;",
    "    string l[] = {",
    "    };",
    "    for(int i = 20; i <= 25; i++)",
    "        cout << l[i] << endl;",
    "    for(int i = 0; i <= 34; i++)",
    "        cout << l[0] + q + l[i] + q + ',' << endl;",
    "    for(int i = 26; i <= 34; i++)",
    "        cout << l[i] << endl;",
    "    return 0;",
    "}",
    "=============<<<<<<<< Java Code >>>>>>>>==========",
    "public class Quine",
    "{",
    "  public static void main( String[] args )",
    "  {",
    "    char q = 34;",
    "    String[] l = {",
    "    };",
    "    for(int i = 2; i <= 9; i++)",
    "        System.out.println(l[i]);",
    "    for(int i = 0; i < l.length; i++)",
    "        System.out.println( l[0] + q + l[i] + q + ',' );",
    "    for(int i = 10; i <= 18; i++))",
    "        System.out.println(l[i]);",
    "  }",
    "}",
    };
    for(int i = 2; i <= 9; i++)
        System.out.println(l[i]);
    for(int i = 0; i < l.length; i++)
        System.out.println( l[0] + q + l[i] + q + ',' );
    for(int i = 10; i <= 18; i++)
        System.out.println(l[i]);

 }
}

Takie programy zostały wyprodukowane w różnych długościach cykli:

Multikiny

David Madore, twórca Unlambdy , opisuje multiquiny w następujący sposób:

„Multichin jest zbiorem r różnych programów (w r różnych językach – bez tego warunku moglibyśmy wziąć je wszystkie jako równe jednej chinie), z których każdy jest w stanie wydrukować dowolny z r programów (w tym siebie) zgodnie z argument wiersza poleceń jest przekazywany (pamiętaj, że oszustwo jest niedozwolone: ​​argumenty wiersza poleceń nie mogą być zbyt długie – przekazanie pełnego tekstu programu jest uważane za oszustwo)."

Multichin składający się z 2 języków (lub biquine) byłby programem, który:

  • Po uruchomieniu jest quine w języku X.
  • Po dostarczeniu argumentu wiersza poleceń zdefiniowanego przez użytkownika, wypisze drugi program w języku Y.
  • Biorąc pod uwagę drugi program w języku Y, gdy jest uruchamiany normalnie, byłby również quine w języku Y.
  • Biorąc pod uwagę drugi program w języku Y i dostarczony ze zdefiniowanym przez użytkownika argumentem wiersza poleceń, wytworzy oryginalny program w języku X.

Biquine może być wtedy postrzegany jako zestaw dwóch programów, z których oba są w stanie wydrukować jeden z nich, w zależności od dostarczonego argumentu wiersza poleceń.

Teoretycznie nie ma ograniczeń co do liczby języków w multichinach. 5-częściowy multichin (lub pentaquine) został wyprodukowany w Python , Perl , C , NewLISP i F# , a także 25-językowy multichin.

Utwardzone promieniowaniem

Szyna utwardzona promieniowaniem to chinka, z której można usunąć dowolny pojedynczy znak i nadal tworzy oryginalny program bez brakującego znaku. Z konieczności, takie quines są znacznie bardziej zawiłe niż zwykłe quines, jak widać na poniższym przykładzie w Ruby : 

eval='eval$q=%q(puts %q(10210/#{1 1 if 1==21}}/.i rescue##/

1 1"[13,213].max_by{|s|s.size}#"##").gsub(/\d/){["=\47eval$q=%q(#$q)#\47##\47

",:eval,:instance_,"||=9"][eval$&]}
exit)#'##'

instance_eval='eval$q=%q(puts %q(10210/#{1 1 if 1==21}}/.i rescue##/

1 1"[13,213].max_by{|s|s.size}#"##").gsub(/\d/){["=\47eval$q=%q(#$q)#\47##\47

",:eval,:instance_,"||=9"][eval$&]}
exit)#'##'

/#{eval eval if eval==instance_eval}}/.i rescue##/

eval eval"[eval||=9,instance_eval||=9].max_by{|s|s.size}#"##"

Zobacz też

Uwagi

Bibliografia

Dalsza lektura

Zewnętrzne linki