Semana 11 — Autorreferencia
Objetivos
- Explicar cómo un programa puede obtener su propio código, y escribir un quine.
- Enunciar el teorema de recursión y usarlo para volver a demostrar que es indecidible.
- Explicar qué dice el primer teorema de incompletitud de Gödel y cómo se sigue de la indecidibilidad.
- Definir la complejidad de Kolmogorov y demostrar que hay cadenas incompresibles.
Sesión A — Autorreferencia: el teorema de recursión y los quines
Lectura: Apuntes, semana 11.
Apoyo: Sipser, sec. 6.1 (The Recursion Theorem).
Temas:
- La objeción a la semana 9: la máquina se aplicaba a su propia descripción. ¿Puede una máquina tener su descripción?
- Un programa que imprime su propio código. El intento ingenuo crece sin fin: el programa tendría que contenerse.
- La solución en dos partes: imprime una descripción de , y , a partir de lo que dejó, reconstruye a . La frase en español que hace lo mismo.
- Un quine en C++ leído línea por línea.
- Teorema de recursión: toda máquina se puede escribir de modo que empiece obteniendo su propia descripción .
- Usos: es indecidible, en cuatro líneas. No existe un algoritmo que diga si una máquina es la más pequeña para su lenguaje.
- Los virus: un programa que se copia a sí mismo es un quine con algo más.
- Error común: creer que un quine “hace trampa” leyendo su archivo. No lee nada: el código está construido para reproducirse.
Sesión B — Incompletitud de Gödel · ✂️ Complejidad de Kolmogorov
Lectura: Apuntes, semana 11.
Apoyo: Sipser, sec. 6.2 (Decidability of Logical Theories) y 6.4 (A Definition of Information). Barak, capítulo 11 (Is every theorem provable?).
Temas:
- El programa de Hilbert: un procedimiento que decida toda afirmación matemática.
- Sistema formal: axiomas, reglas, y demostraciones que una máquina puede comprobar. Demostrable no es lo mismo que verdadero.
- ” no se detiene con ” se puede escribir como una afirmación de la aritmética. Se da la idea, sin los detalles de la codificación.
- Primer teorema de incompletitud: en todo sistema correcto que exprese la aritmética hay afirmaciones verdaderas sin demostración. Si no, enumerar demostraciones decidiría el problema de la parada.
- La afirmación de Gödel, “esta afirmación no tiene demostración”, construida con el teorema de recursión.
- Lo que el teorema no dice: no habla de la mente humana ni dice que “nada se puede demostrar”.
- ✂️ Complejidad de Kolmogorov: es la longitud de la descripción más corta de . No depende mucho del lenguaje elegido.
- ✂️ Hay cadenas incompresibles de toda longitud, por conteo. no es computable: la paradoja de “el menor número que no se puede describir con menos de veinte palabras”.
- Error común: usar “incompleto” como si quisiera decir “contradictorio”. Son propiedades distintas, y el teorema las enfrenta.
Laboratorio — Práctica 3 · Opcional: un quine en C++
La sesión es para la Práctica 3 (semanas 6, 7, 9 y 10). Como ejercicio opcional:
- Escribir un programa en C++ que imprima exactamente su propio código fuente, sin abrir ningún archivo.
- Comprobarlo con
make test, que compila el programa, lo ejecuta y compara la salida con el fuente. - Modificarlo para que imprima su código y, además, cuántos caracteres tiene.
Preguntas de repaso
- ¿Por qué el intento ingenuo de escribir un quine no termina nunca? ¿Qué idea lo destraba?
- Demuestren con el teorema de recursión que es indecidible.
- ¿Por qué el conjunto de las afirmaciones demostrables es reconocible? ¿Qué pasaría si además toda afirmación verdadera fuera demostrable?
- Demuestren que para todo existe una cadena de longitud con .
- Si fuera computable, ¿qué programa corto imprimiría una cadena de complejidad enorme? ¿Dónde está la contradicción?
Código de la semana
Compilar y probar dentro del contenedor del curso con make y make test.
Ejemplos (11)Errores (2)Pruebas (2)Laboratorio (4)Compilación (1)
Ejemplos
Los programas que usan los apuntes y la clase.
#!/bin/sh
# Comprime tres cadenas binarias de la misma longitud con tres compresores y muestra cuánto
# ocupa cada resultado. El tamaño comprimido es una cota superior de lo que cuesta describir
# la cadena con ese compresor: no es la complejidad de Kolmogorov, que no se puede calcular.
# Se corre desde code/week-11, después de make: ./compress.sh [n]
set -e
n=${1:-1000000}
tmp=build/compress
mkdir -p "$tmp"
echo "cadenas de $n símbolos (0 y 1); tamaños comprimidos en bits"
printf '%-8s %12s %12s %12s\n' cadena gzip bzip2 xz
for kind in pattern count prng; do
build/gen_string "$kind" "$n" > "$tmp/$kind.txt"
g=$(gzip -9 -c "$tmp/$kind.txt" | wc -c)
b=$(bzip2 -9 -c "$tmp/$kind.txt" | wc -c)
x=$(xz -9 -c "$tmp/$kind.txt" | wc -c)
printf '%-8s %12d %12d %12d\n' "$kind" $((g * 8)) $((b * 8)) $((x * 8))
done
echo "el programa que las genera: $(($(wc -c < gen_string.cpp) * 8)) bits de código fuente"// Escribe en la salida estándar una cadena de n bytes de uno de tres tipos. Las tres salen de
// este programa corto, así que las tres tienen una descripción corta: el programa y n.
//
// build/gen_string pattern n 0101010101...
// build/gen_string count n 11011100101110111... (1, 10, 11, 100, 101... en binario, pegados)
// build/gen_string prng n los bits de un generador seudoaleatorio con semilla fija
#include <cstddef>
#include <iostream>
#include <random>
#include <string>
int main(int argc, char** argv) {
if (argc != 3) {
std::cerr << "uso: gen_string pattern|count|prng n\n";
return 1;
}
const std::string kind = argv[1];
const std::size_t n = std::stoul(argv[2]);
std::string out;
out.reserve(n + 32);
if (kind == "pattern") {
while (out.size() < n) {
out += "01";
}
} else if (kind == "count") {
for (std::size_t i = 1; out.size() < n; i++) {
std::string digits;
for (std::size_t rest = i; rest > 0; rest /= 2) {
digits += static_cast<char>('0' + rest % 2);
}
out.append(digits.rbegin(), digits.rend());
}
} else if (kind == "prng") {
// std::mt19937_64 da la misma secuencia en toda computadora: el estándar fija el algoritmo.
std::mt19937_64 rng(2025);
while (out.size() < n) {
std::mt19937_64::result_type word = rng();
for (int bit = 0; bit < 64; bit++) {
out += static_cast<char>('0' + ((word >> bit) & 1));
}
}
} else {
std::cerr << "gen_string: tipo desconocido: " << kind << "\n";
return 1;
}
out.resize(n);
std::cout << out;
return 0;
}// Completa un molde con una copia de sí mismo: lee de la entrada estándar el texto de un
// programa con una arroba, y escribe el programa en el que la arroba es un literal con ese
// mismo texto. Así se construyeron quine.cpp, quine_payload.cpp y self_check.cpp.
//
// build/make_self < templates/quine.tpl > quine.cpp
#include <exception>
#include <iostream>
#include <iterator>
#include <string>
#include "self.h"
int main() {
const std::string tpl{std::istreambuf_iterator<char>(std::cin), std::istreambuf_iterator<char>()};
try {
std::cout << fill_hole(tpl);
} catch (const std::exception& e) {
std::cerr << "make_self: " << e.what() << "\n";
return 1;
}
return 0;
}// El intento ingenuo de escribir un quine: un programa que imprime un texto fijo. Si el texto
// es un programa P, el que lo imprime es otro programa, más largo que P. Este ejemplo arma la
// cadena P0, P1, P2... donde cada uno imprime al anterior, y muestra cómo crecen.
//
// build/naive_growth la tabla de tamaños
// build/naive_growth --emit k el código de Pk
#include <cstddef>
#include <iostream>
#include <string>
#include "self.h"
int main(int argc, char** argv) {
const std::string p0 = "int main() {}\n";
if (argc == 3 && std::string(argv[1]) == "--emit") {
std::string p = p0;
for (int k = std::stoi(argv[2]); k > 0; k--) {
p = printer_of(p);
}
std::cout << p;
return 0;
}
std::cout << " k bytes de Pk lo que imprime Pk\n";
std::string p = p0;
std::size_t printed = 0;
for (int k = 0; k <= 8; k++) {
std::cout.width(2);
std::cout << k;
std::cout.width(14);
std::cout << p.size();
if (k == 0) {
std::cout << " nada\n";
} else {
std::cout << " P" << k - 1 << ", de " << printed << " bytes\n";
}
printed = p.size();
p = printer_of(p);
}
return 0;
}// Un quine con payload: escribe su código en la salida estándar y, además, hace otra cosa.
// Un virus tiene la misma forma: la parte que se copia y la parte que actúa. Aquí la segunda
// parte es inofensiva: cuenta sus propias líneas y lo dice por la salida de errores.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>
// Devuelve el código de este programa. Es la construcción del quine, sin imprimir.
std::string own_source() {
const std::string text = R"~(// Un quine con payload: escribe su código en la salida estándar y, además, hace otra cosa.
// Un virus tiene la misma forma: la parte que se copia y la parte que actúa. Aquí la segunda
// parte es inofensiva: cuenta sus propias líneas y lo dice por la salida de errores.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>
// Devuelve el código de este programa. Es la construcción del quine, sin imprimir.
std::string own_source() {
const std::string text = @;
const std::size_t hole = text.find('@');
return text.substr(0, hole) + "R\"~(" + text + ")~\"" + text.substr(hole + 1);
}
int main() {
const std::string self = own_source();
// La copia.
std::cout << self;
// El payload.
const std::ptrdiff_t lines = std::count(self.begin(), self.end(), '\n');
std::cerr << "payload: me copié completo, " << lines << " líneas y " << self.size() << " bytes\n";
return 0;
}
)~";
const std::size_t hole = text.find('@');
return text.substr(0, hole) + "R\"~(" + text + ")~\"" + text.substr(hole + 1);
}
int main() {
const std::string self = own_source();
// La copia.
std::cout << self;
// El payload.
const std::ptrdiff_t lines = std::count(self.begin(), self.end(), '\n');
std::cerr << "payload: me copié completo, " << lines << " líneas y " << self.size() << " bytes\n";
return 0;
}// Un quine: imprime exactamente su propio código fuente, sin abrir ningún archivo.
#include <cstddef>
#include <iostream>
#include <string>
int main() {
// Parte A: los datos. Es el texto de todo el programa, con una arroba en el lugar
// donde va este mismo literal.
const std::string text = R"~(// Un quine: imprime exactamente su propio código fuente, sin abrir ningún archivo.
#include <cstddef>
#include <iostream>
#include <string>
int main() {
// Parte A: los datos. Es el texto de todo el programa, con una arroba en el lugar
// donde va este mismo literal.
const std::string text = @;
// Parte B: el código. Imprime lo que hay antes de la arroba, después el texto otra
// vez, ahora escrito como literal, y al final lo que hay después de la arroba.
const std::size_t hole = text.find('@');
std::cout << text.substr(0, hole);
std::cout << "R\"~(" << text << ")~\"";
std::cout << text.substr(hole + 1);
return 0;
}
)~";
// Parte B: el código. Imprime lo que hay antes de la arroba, después el texto otra
// vez, ahora escrito como literal, y al final lo que hay después de la arroba.
const std::size_t hole = text.find('@');
std::cout << text.substr(0, hole);
std::cout << "R\"~(" << text << ")~\"";
std::cout << text.substr(hole + 1);
return 0;
}// El teorema de recursión en pequeño: el programa obtiene su propio código y después sigue
// calculando con él. Este lee la entrada estándar y dice si es su propio código.
#include <cstddef>
#include <iostream>
#include <iterator>
#include <string>
// Devuelve el código de este programa. Es la construcción del quine, sin imprimir.
std::string own_source() {
const std::string text = R"~(// El teorema de recursión en pequeño: el programa obtiene su propio código y después sigue
// calculando con él. Este lee la entrada estándar y dice si es su propio código.
#include <cstddef>
#include <iostream>
#include <iterator>
#include <string>
// Devuelve el código de este programa. Es la construcción del quine, sin imprimir.
std::string own_source() {
const std::string text = @;
const std::size_t hole = text.find('@');
return text.substr(0, hole) + "R\"~(" + text + ")~\"" + text.substr(hole + 1);
}
int main() {
const std::string self = own_source();
const std::string input{std::istreambuf_iterator<char>(std::cin), std::istreambuf_iterator<char>()};
if (input == self) {
std::cout << "es mi código: " << self.size() << " bytes\n";
} else {
std::cout << "no es mi código: yo tengo " << self.size() << " bytes y la entrada " << input.size() << "\n";
}
return 0;
}
)~";
const std::size_t hole = text.find('@');
return text.substr(0, hole) + "R\"~(" + text + ")~\"" + text.substr(hole + 1);
}
int main() {
const std::string self = own_source();
const std::string input{std::istreambuf_iterator<char>(std::cin), std::istreambuf_iterator<char>()};
if (input == self) {
std::cout << "es mi código: " << self.size() << " bytes\n";
} else {
std::cout << "no es mi código: yo tengo " << self.size() << " bytes y la entrada " << input.size() << "\n";
}
return 0;
}// Las funciones de la semana 11: escribir un texto como literal de C++, construir el programa
// que imprime un texto, y completar un molde con una copia de sí mismo (la construcción
// del quine, que es la del teorema de recursión).
#ifndef SELF_H
#define SELF_H
#include <cstddef>
#include <stdexcept>
#include <string>
// El texto s escrito como un literal común de C++, con comillas y secuencias de escape.
// Sirve para textos ASCII y UTF-8: los bytes que no son comilla, barra ni salto pasan igual.
inline std::string cpp_literal(const std::string& s) {
std::string out = "\"";
for (char c : s) {
if (c == '\n') {
out += "\\n";
} else if (c == '"' || c == '\\') {
out += '\\';
out += c;
} else {
out += c;
}
}
out += '"';
return out;
}
// El texto s escrito como raw string literal. Entre R"~( y )~" todo se toma tal cual:
// comillas, barras invertidas y saltos de línea. No sirve si s contiene el cierre )~".
inline std::string raw_literal(const std::string& s) {
const std::string open = "R\"~(";
const std::string close = ")~\"";
if (s.find(close) != std::string::npos) {
throw std::invalid_argument("el texto contiene )~\" y no cabe en un raw string literal");
}
return open + s + close;
}
// El código de un programa de C++ que imprime w y termina. Es la función q de los apuntes:
// de una cadena w a la descripción de una máquina P_w que escribe w.
inline std::string printer_of(const std::string& w) {
return "#include <iostream>\nint main() { std::cout << " + cpp_literal(w) + "; }\n";
}
// La construcción del quine. El molde es el texto de un programa con una arroba en el
// lugar donde debe ir un literal con el molde mismo. Devuelve el programa completo:
// lo que hay antes de la primera arroba, el molde como raw string literal, y el resto.
inline std::string fill_hole(const std::string& tpl) {
const std::size_t hole = tpl.find('@');
if (hole == std::string::npos) {
throw std::invalid_argument("el molde no tiene una arroba");
}
return tpl.substr(0, hole) + raw_literal(tpl) + tpl.substr(hole + 1);
}
#endif// Un quine con payload: escribe su código en la salida estándar y, además, hace otra cosa.
// Un virus tiene la misma forma: la parte que se copia y la parte que actúa. Aquí la segunda
// parte es inofensiva: cuenta sus propias líneas y lo dice por la salida de errores.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>
// Devuelve el código de este programa. Es la construcción del quine, sin imprimir.
std::string own_source() {
const std::string text = @;
const std::size_t hole = text.find('@');
return text.substr(0, hole) + "R\"~(" + text + ")~\"" + text.substr(hole + 1);
}
int main() {
const std::string self = own_source();
// La copia.
std::cout << self;
// El payload.
const std::ptrdiff_t lines = std::count(self.begin(), self.end(), '\n');
std::cerr << "payload: me copié completo, " << lines << " líneas y " << self.size() << " bytes\n";
return 0;
}// Un quine: imprime exactamente su propio código fuente, sin abrir ningún archivo.
#include <cstddef>
#include <iostream>
#include <string>
int main() {
// Parte A: los datos. Es el texto de todo el programa, con una arroba en el lugar
// donde va este mismo literal.
const std::string text = @;
// Parte B: el código. Imprime lo que hay antes de la arroba, después el texto otra
// vez, ahora escrito como literal, y al final lo que hay después de la arroba.
const std::size_t hole = text.find('@');
std::cout << text.substr(0, hole);
std::cout << "R\"~(" << text << ")~\"";
std::cout << text.substr(hole + 1);
return 0;
}// El teorema de recursión en pequeño: el programa obtiene su propio código y después sigue
// calculando con él. Este lee la entrada estándar y dice si es su propio código.
#include <cstddef>
#include <iostream>
#include <iterator>
#include <string>
// Devuelve el código de este programa. Es la construcción del quine, sin imprimir.
std::string own_source() {
const std::string text = @;
const std::size_t hole = text.find('@');
return text.substr(0, hole) + "R\"~(" + text + ")~\"" + text.substr(hole + 1);
}
int main() {
const std::string self = own_source();
const std::string input{std::istreambuf_iterator<char>(std::cin), std::istreambuf_iterator<char>()};
if (input == self) {
std::cout << "es mi código: " << self.size() << " bytes\n";
} else {
std::cout << "no es mi código: yo tengo " << self.size() << " bytes y la entrada " << input.size() << "\n";
}
return 0;
}Errores
Ejemplos con errores a propósito: no compilan, fallan o dan un resultado incorrecto. Los apuntes explican cada uno.
// El intento ingenuo. Imprime un programa, pero no es el suyo: lo que imprime no tiene la
// línea que imprime. Para arreglarlo habría que meter esa línea dentro de las comillas, y
// entonces la línea cambia y hay que volver a meterla.
#include <iostream>
int main() {
std::cout << "#include <iostream>\n\nint main() {\n}\n";
}// No es un quine: abre su propio archivo y lo copia. Deja de funcionar apenas el ejecutable
// se separa del fuente, y no dice nada sobre lo que un programa puede calcular por sí solo.
#include <fstream>
#include <iostream>
int main() {
std::ifstream source(__FILE__);
if (!source) {
std::cerr << "no encuentro mi código fuente\n";
return 1;
}
std::cout << source.rdbuf();
return 0;
}Pruebas
Comprueban lo que afirman los apuntes; se ejecutan con make test.
#!/bin/sh
# Las pruebas que no caben en un assert: compilar programas, ejecutarlos y comparar su salida
# con un archivo, byte por byte. Lo llama make test, desde code/week-11.
set -e
CXX=${CXX:-g++}
CXXFLAGS=${CXXFLAGS:--Wall -Wextra -std=c++20}
BUILD=${BUILD:-build}
tmp=$BUILD/tmp
mkdir -p "$tmp"
# 1. Cada programa es lo que make_self construye con su molde.
for name in quine quine_payload self_check; do
"$BUILD/make_self" < "templates/$name.tpl" | cmp - "$name.cpp"
done
echo "make_self: ok (3 moldes)"
# 2. El quine imprime su fuente. Su salida, compilada, vuelve a imprimir lo mismo.
"$BUILD/quine" > "$tmp/copy.cpp"
cmp "$tmp/copy.cpp" quine.cpp
$CXX $CXXFLAGS "$tmp/copy.cpp" -o "$tmp/copy"
"$tmp/copy" | cmp - quine.cpp
echo "quine: ok ($(wc -c < quine.cpp) bytes, y la copia de la copia es igual)"
# 3. El quine con payload: la salida estándar es el fuente, y el payload dice sus líneas y bytes.
"$BUILD/quine_payload" > "$tmp/payload.out" 2> "$tmp/payload.err"
cmp "$tmp/payload.out" quine_payload.cpp
lines=$(wc -l < quine_payload.cpp)
bytes=$(wc -c < quine_payload.cpp)
echo "payload: me copié completo, $((lines)) líneas y $((bytes)) bytes" | cmp - "$tmp/payload.err"
echo "quine_payload: ok ($((lines)) líneas, $((bytes)) bytes)"
# 4. self_check reconoce su código y solo su código.
"$BUILD/self_check" < self_check.cpp | grep -q '^es mi código'
"$BUILD/self_check" < quine.cpp | grep -q '^no es mi código'
"$BUILD/self_check" < /dev/null | grep -q '^no es mi código'
{ cat self_check.cpp; echo; } | "$BUILD/self_check" | grep -q '^no es mi código'
echo "self_check: ok"
# 5. El intento ingenuo: P2 imprime P1, P1 imprime P0, y ninguno se imprime a sí mismo.
for k in 0 1 2 3; do
"$BUILD/naive_growth" --emit "$k" > "$tmp/p$k.cpp"
done
for k in 1 2 3; do
$CXX $CXXFLAGS "$tmp/p$k.cpp" -o "$tmp/p$k"
"$tmp/p$k" | cmp - "$tmp/p$((k - 1)).cpp"
if "$tmp/p$k" | cmp -s - "$tmp/p$k.cpp"; then
echo "P$k se imprime a sí mismo: no debería"
exit 1
fi
done
echo "naive_growth: ok (P3 imprime P2, P2 imprime P1, P1 imprime P0)"
# 6. Los programas de errors/ compilan y no son quines.
for name in prints_other reads_file; do
$CXX $CXXFLAGS "errors/$name.cpp" -o "$tmp/$name"
done
if "$tmp/prints_other" | cmp -s - errors/prints_other.cpp; then
echo "errors/prints_other.cpp se imprime a sí mismo: no debería"
exit 1
fi
# reads_file sí imprime su fuente, pero solo si se ejecuta desde la carpeta donde se compiló:
# el compilador dejó dentro del ejecutable la ruta errors/reads_file.cpp, y desde otra carpeta
# esa ruta no lleva a nada.
"$tmp/reads_file" | cmp - errors/reads_file.cpp
if (cd "$tmp" && ./reads_file) > "$tmp/reads_file.out" 2> /dev/null; then
echo "errors/reads_file.cpp funcionó sin su archivo: no debería"
exit 1
fi
echo "errors: ok (prints_other no se imprime; reads_file falla sin su archivo)"
# 7. Las cadenas de la sección de Kolmogorov: longitud exacta, siempre las mismas, y los
# compresores devuelven la original.
for kind in pattern count prng; do
"$BUILD/gen_string" "$kind" 100000 > "$tmp/$kind.txt"
test "$(wc -c < "$tmp/$kind.txt")" -eq 100000
"$BUILD/gen_string" "$kind" 100000 | cmp - "$tmp/$kind.txt"
gzip -9 -c "$tmp/$kind.txt" | gzip -dc | cmp - "$tmp/$kind.txt"
xz -9 -c "$tmp/$kind.txt" | xz -dc | cmp - "$tmp/$kind.txt"
done
test "$("$BUILD/gen_string" pattern 12)" = 010101010101
test "$("$BUILD/gen_string" count 17)" = 11011100101110111
# Con un bit por símbolo, ningún código de prefijo baja de n/8 bytes para la cadena del generador.
test "$(gzip -9 -c "$tmp/prng.txt" | wc -c)" -ge 12500
test "$(gzip -9 -c "$tmp/pattern.txt" | wc -c)" -lt 1000
echo "gen_string: ok"// Pruebas de lo que los apuntes afirman sobre las construcciones de la semana: el literal, el
// programa que imprime un texto, el molde que se completa consigo mismo, la frase que se
// describe a sí misma y los conteos de la complejidad de Kolmogorov.
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <stdexcept>
#include <string>
#include <vector>
#include "self.h"
// Lee un literal común de C++ (el que escribe cpp_literal) y devuelve el texto que denota.
static std::string read_literal(const std::string& lit) {
assert(lit.size() >= 2 && lit.front() == '"' && lit.back() == '"');
std::string out;
for (std::size_t i = 1; i + 1 < lit.size(); i++) {
if (lit[i] == '\\') {
i++;
assert(i + 1 < lit.size());
out += (lit[i] == 'n') ? '\n' : lit[i];
} else {
assert(lit[i] != '"' && lit[i] != '\n');
out += lit[i];
}
}
return out;
}
static void test_literal() {
assert(cpp_literal("hola") == "\"hola\"");
assert(cpp_literal("a\"b") == "\"a\\\"b\"");
assert(cpp_literal("a\\b\n") == "\"a\\\\b\\n\"");
// Leer el literal devuelve el texto, también cuando el texto ya es un literal.
std::string w = "int main() {}\n";
for (int k = 0; k < 6; k++) {
assert(read_literal(cpp_literal(w)) == w);
w = cpp_literal(w) + "\n";
}
// El literal siempre es más largo que el texto: al menos las dos comillas.
for (const std::string& s : {std::string(""), std::string("x"), std::string("\"\\\n")}) {
assert(cpp_literal(s).size() >= s.size() + 2);
}
}
static void test_printer() {
// printer_of(w) contiene el literal de w, así que es más largo que w: ningún texto es
// igual al programa que lo imprime. Es la razón por la que el intento ingenuo no termina.
std::string p = "int main() {}\n";
std::vector<std::size_t> sizes;
for (int k = 0; k <= 8; k++) {
sizes.push_back(p.size());
const std::string next = printer_of(p);
assert(next.size() > p.size());
assert(next != p);
// El programa siguiente contiene el literal del anterior, y ese literal denota al anterior.
const std::size_t from = next.find('"', next.find("cout"));
const std::size_t to = next.rfind('"');
assert(read_literal(next.substr(from, to - from + 1)) == p);
p = next;
}
// Los tamaños de la tabla de los apuntes.
const std::vector<std::size_t> expected = {14, 67, 124, 188, 266, 372, 534, 808, 1306};
assert(sizes == expected);
}
static void test_fill_hole() {
// El programa completo es: antes de la arroba, el molde como literal, después de la arroba.
const std::string tpl = "AAA @ BBB";
assert(fill_hole(tpl) == "AAA R\"~(AAA @ BBB)~\" BBB");
// El molde aparece entero, como datos, dentro del programa.
assert(fill_hole(tpl).find(tpl) != std::string::npos);
// El tamaño: dos veces el molde, menos la arroba, más los siete caracteres de R"~( y )~".
for (const std::string& t : {std::string("@"), std::string("x@y@z"), std::string("uno\n@\ndos\n")}) {
assert(fill_hole(t).size() == 2 * t.size() - 1 + 7);
}
// Solo la primera arroba es el hueco.
assert(fill_hole("x@y@z") == "xR\"~(x@y@z)~\"y@z");
// Lo que el programa hace al correr: con el texto del literal vuelve a armarse a sí mismo.
// Aquí se hace la misma cuenta a mano, sin compilar nada.
const std::string program = fill_hole(tpl);
const std::size_t open = program.find("R\"~(") + 4;
const std::size_t close = program.find(")~\"");
const std::string text = program.substr(open, close - open);
assert(text == tpl);
const std::size_t hole = text.find('@');
assert(text.substr(0, hole) + "R\"~(" + text + ")~\"" + text.substr(hole + 1) == program);
// Dos moldes que no sirven.
bool failed = false;
try {
fill_hole("sin hueco");
} catch (const std::invalid_argument&) {
failed = true;
}
assert(failed);
failed = false;
try {
fill_hole("@ con el cierre )~\" adentro");
} catch (const std::invalid_argument&) {
failed = true;
}
assert(failed);
}
static void test_sentence() {
// La frase que se describe a sí misma. La instrucción dice qué hacer con el texto que
// sigue a los dos puntos: escribirlo dos veces, la segunda vez entre comillas.
const std::string part = "Escriban dos veces lo que sigue, la segunda vez entre comillas:";
const std::string sentence = part + " «" + part + "»";
// Obedecer la instrucción: tomar lo que está entre comillas y escribirlo dos veces.
const std::size_t open = sentence.find("«") + std::string("«").size();
const std::size_t close = sentence.find("»");
const std::string quoted = sentence.substr(open, close - open);
const std::string result = quoted + " «" + quoted + "»";
assert(result == sentence);
}
static void test_counting() {
// Cadenas binarias de longitud menor que n: 2^0 + 2^1 + ... + 2^(n-1) = 2^n - 1.
for (std::uint64_t n = 0; n <= 60; n++) {
std::uint64_t shorter = 0;
for (std::uint64_t len = 0; len < n; len++) {
shorter += std::uint64_t{1} << len;
}
assert(shorter == (std::uint64_t{1} << n) - 1);
assert(shorter < (std::uint64_t{1} << n)); // menos descripciones que cadenas de longitud n
}
// Cadenas de longitud n que se pueden comprimir c bits o más: a lo sumo 2^(n-c+1) - 1.
// Para n = 1000000 y c = 10, la fracción es menor que 2^(-9) = 1/512.
for (std::uint64_t n = 10; n <= 60; n++) {
for (std::uint64_t c = 1; c <= n; c++) {
const std::uint64_t descriptions = (std::uint64_t{1} << (n - c + 1)) - 1; // longitud <= n - c
// descriptions / 2^n < 2^(1-c)
assert(descriptions < (std::uint64_t{1} << (n - c + 1)));
}
}
}
int main() {
test_literal();
test_printer();
test_fill_hole();
test_sentence();
test_counting();
std::puts("test_self: ok");
return 0;
}Laboratorio
Archivos de partida del laboratorio de la semana.
#!/bin/sh
# Comprueba un quine. Lo llama el Makefile: sh check.sh quine|length archivo.cpp carpeta
#
# quine la salida del programa debe ser igual a su fuente, byte por byte
# length la salida debe ser el fuente y, después, una línea con su cantidad de bytes
CXX=${CXX:-g++}
CXXFLAGS=${CXXFLAGS:--Wall -Wextra -std=c++20 -O2}
mode=$1
source=$2
build=${3:-build}
if [ ! -f "$source" ]; then
echo "no existe $source"
[ "$mode" = length ] && echo "para el paso 3, copien su quine: cp solution.cpp length.cpp"
exit 1
fi
# 1. El fuente no puede leerse a sí mismo. La lista es corta a propósito: la regla es no usar
# nada que le entregue al programa su propio texto, esté o no en esta lista.
forbidden='fstream|fopen|freopen|filesystem|__FILE__|source_location|# *embed|# *include *"|popen|system *\(|argv|/proc/|R"'
if grep -n -E "$forbidden" "$source" > /dev/null; then
echo "RECHAZADO: $source usa algo que el problema no permite:"
grep -n -o -E "$forbidden" "$source" | sed 's/^/ línea /; s/:/: /'
echo "Un quine no abre archivos ni le pide su texto al compilador, y en este problema"
echo "tampoco se usan raw string literals. Lean las reglas en README.md."
exit 1
fi
# 2. Compilar.
mkdir -p "$build"
if ! $CXX $CXXFLAGS "$source" -o "$build/quine"; then
echo "ERROR DE COMPILACIÓN: $source"
exit 1
fi
# 3. Ejecutar, sin entrada y con un límite de 5 segundos.
timeout 5 "$build/quine" < /dev/null > "$build/output.txt"
status=$?
if [ "$status" -ne 0 ]; then
echo "RE: el programa terminó con código $status (124 quiere decir que pasó de 5 segundos)"
exit 1
fi
# 4. Comparar byte por byte.
if [ "$mode" = length ]; then
{ cat "$source"; echo "$(($(wc -c < "$source")))"; } > "$build/expected.txt"
else
cp "$source" "$build/expected.txt"
fi
if cmp -s "$build/output.txt" "$build/expected.txt"; then
echo "AC: la salida es igual a lo esperado, $(($(wc -c < "$build/expected.txt"))) bytes"
exit 0
fi
echo "WA: la salida no es igual a lo esperado"
echo " esperado: $(($(wc -c < "$build/expected.txt"))) bytes; salida: $(($(wc -c < "$build/output.txt"))) bytes"
where=$(cmp "$build/output.txt" "$build/expected.txt" 2> /dev/null | sed 's/^.*differ: //; s/line/línea/')
if [ -n "$where" ]; then
echo " primera diferencia: $where"
else
echo " una es el comienzo de la otra: sobra o falta texto al final"
fi
echo " para verla: diff $build/output.txt $build/expected.txt | head"
exit 1# Laboratorio opcional de la semana 11: un quine en C++.
# Este problema no usa el juez: la respuesta esperada es el propio fuente.
#
# make compila solution.cpp en build/
# make test paso 2: revisa el fuente, lo compila, lo ejecuta y compara la salida con él
# make test-length paso 3: lo mismo con length.cpp, que además imprime cuántos bytes tiene
# make clean borra lo generado
CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -O2
SOURCE ?= solution.cpp
LENGTH ?= length.cpp
BUILD ?= build
.PHONY: all test test-length clean
all: $(BUILD)/solution
$(BUILD)/solution: $(SOURCE) | $(BUILD)
$(CXX) $(CXXFLAGS) $< -o $@
$(BUILD):
mkdir -p $@
test:
@CXX="$(CXX)" CXXFLAGS="$(CXXFLAGS)" sh check.sh quine $(SOURCE) $(BUILD)
test-length:
@CXX="$(CXX)" CXXFLAGS="$(CXXFLAGS)" sh check.sh length $(LENGTH) $(BUILD)
clean:
rm -rf build# Un quine en C++
Un **quine** es un programa que imprime exactamente su propio código fuente, sin leerlo de ningún lado. Esta
semana vieron por qué existe: el programa se parte en datos y código, los datos describen al código, y el
código imprime los datos dos veces, una como texto y otra como literal. En este problema escriben el suyo.
Es el ejercicio opcional de la semana 11. No tiene casos de prueba con archivos `.in` y `.out`, porque la
respuesta esperada es su propio programa: `make test` compara la salida con el fuente.
## Entrada
Ninguna. El programa no lee nada: ni la entrada estándar, ni argumentos, ni archivos.
## Salida
El contenido de `solution.cpp`, byte por byte: los mismos espacios, los mismos saltos de línea, los mismos
comentarios, el mismo salto de línea final si lo hay. Ni un byte más ni uno menos.
## Reglas
El programa tiene que **contener** lo necesario para reproducirse. No puede pedirle su texto a nadie:
- No abre archivos: nada de `<fstream>`, `fopen`, `freopen` ni `<filesystem>`.
- No le pide su texto al compilador: nada de `__FILE__`, `#embed`, `std::source_location`, ni un `#include`
de un archivo propio (solo se incluyen cabeceras de la biblioteca estándar, entre `<` y `>`).
- No ejecuta otros programas ni mira sus argumentos: nada de `system`, `popen` ni `argv`.
- **No usa raw string literals** (`R"(...)"`). El quine de los apuntes, `quine.cpp`, usa uno, y con eso se
ahorra la parte más interesante del problema: escribir un texto que tiene comillas, barras invertidas y saltos
de línea dentro de un literal común. Aquí la resuelven ustedes.
- Las reglas de C++ del curso siguen valiendo: C++20, sin advertencias con `-Wall -Wextra`, solo biblioteca
estándar, sin variables globales, sin `using namespace std`.
`make test` rechaza un fuente que contenga alguna de esas palabras, con una búsqueda de texto simple. La
búsqueda es una ayuda, no la regla: **la regla es el espíritu**. Un programa que consigue su propio texto por
un camino que la búsqueda no conoce sigue sin ser un quine. Y la búsqueda es tosca: rechaza también una letra
`R` pegada a una comilla dentro de un mensaje, porque así empieza un raw string literal. Si les pasa, cambien
el mensaje.
Un programa vacío no cuenta: en C++ un archivo vacío no compila, porque le falta `main`.
## Paso 1: escribir el quine
Trabajen en `solution.cpp`. El esqueleto es el intento ingenuo: imprime un texto fijo que no es el suyo.
Un plan que funciona, en el orden en que conviene escribirlo:
1. Escriban primero el programa **sin** los datos, con un hueco: una variable `text` cuyo valor todavía no
conocen, y el código que la usa. Marquen el hueco con un carácter que no aparezca antes en el programa.
2. El código tiene que imprimir tres cosas seguidas: lo que hay en `text` antes de la marca; `text` completo,
**escrito como aparece en el fuente** (con sus comillas, y con una barra invertida delante de cada comilla y
de cada barra invertida, y `\n` en lugar de cada salto de línea); y lo que hay en `text` después de la marca.
3. Para lo segundo necesitan una función que reciba un texto y devuelva el literal que lo denota. Es la única
parte delicada. Decidan de entrada cómo va a quedar escrito el literal en el archivo (¿en una sola línea?,
¿un literal por línea?), porque la función tiene que escribirlo exactamente igual.
4. Recién al final llenen el hueco: el valor de `text` es el programa del paso 1, tal cual, con la marca.
Pueden hacerlo a mano o escribir un programa aparte que lo haga por ustedes. Ese programa auxiliar sí
puede abrir archivos: no es el quine.
Cada vez que cambien una coma del código tienen que actualizar los datos. Por eso conviene dejar los datos
para el final.
## Paso 2: comprobarlo
```sh
make test
```
`make test` hace cuatro cosas: revisa que el fuente no use nada prohibido, lo compila con
`g++ -Wall -Wextra -std=c++20 -O2`, lo ejecuta sin entrada (con un límite de 5 segundos) y compara la salida
con `solution.cpp` byte por byte, con `cmp`. Con el esqueleto responde:
```text
$ make test
WA: la salida no es igual a lo esperado
esperado: 508 bytes; salida: 38 bytes
primera diferencia: byte 1, línea 1
para verla: diff build/output.txt build/expected.txt | head
make: *** [Makefile:26: test] Error 1
```
Un programa que abre su propio archivo ni siquiera se compila:
```text
$ make test SOURCE=reads_file.cpp
RECHAZADO: reads_file.cpp usa algo que el problema no permite:
línea 3: fstream
línea 7: fstream
línea 7: __FILE__
Un quine no abre archivos ni le pide su texto al compilador, y en este problema
tampoco se usan raw string literals. Lean las reglas en README.md.
make: *** [Makefile:26: test] Error 1
```
Cuando el quine está bien:
```text
$ make test
AC: la salida es igual a lo esperado, 2190 bytes
```
La cantidad de bytes es la del programa de referencia; la de ustedes será otra.
Los errores más frecuentes, y cómo se ven:
| Lo que dice `make test` | Lo que suele pasar |
|---|---|
| La salida tiene un byte más que lo esperado | Un `std::endl` o un `"\n"` de más al final |
| La primera diferencia está en la línea del literal | La función que escribe el literal no lo escribe como está en el archivo: revisen la sangría y los escapes |
| La primera diferencia está después del literal | Cambiaron el código y no actualizaron los datos |
| La diferencia está en un comentario | Los comentarios también son parte del fuente, y tienen que estar en los datos |
## Paso 3: el quine que sabe cuánto mide
Copien su quine a `length.cpp` y modifíquenlo para que imprima su código y, después, una línea con la cantidad
de bytes del archivo `length.cpp`, en decimal.
```sh
cp solution.cpp length.cpp
make test-length
```
`make test-length` hace lo mismo que `make test`, pero espera el fuente seguido de esa línea. Con la referencia:
```text
$ make test-length
AC: la salida es igual a lo esperado, 2206 bytes
```
El archivo de referencia tiene 2201 bytes y la línea agregada, `2201` y un salto de línea, tiene 5.
Se cuentan bytes, que es lo que cuenta `wc -c` y lo que devuelve `size()` en un `std::string`. Una letra con
tilde ocupa 2 bytes en UTF-8, así que el número puede ser mayor que la cantidad de caracteres que ven.
Piensen antes de programar: el número no puede estar escrito en el fuente. Si lo escribieran, al cambiar
cualquier cosa habría que corregirlo, y al corregirlo podría cambiar la longitud. El programa tiene que
**calcularlo**, y para eso necesita tener su propio código en una variable antes de imprimir nada. Ese es el
contenido del teorema de recursión: un programa puede obtener su propia descripción y después seguir
calculando con ella.
## Para pensar
- ¿Dónde está, en su programa, la parte $A$ y dónde la parte $B$ de la construcción de los apuntes?
- Si le quitan todos los comentarios, ¿cuántas líneas tienen que cambiar? ¿Por qué son el doble de las que
esperaban?
- Su quine, ¿sigue siendo un quine si lo compilan con otro compilador? ¿Y si alguien guarda el archivo con
saltos de línea de Windows?// Un quine: al terminar, este programa debe imprimir exactamente su propio código fuente,
// incluidos estos comentarios, sin abrir ningún archivo.
#include <iostream>
#include <string>
int main() {
// Por hacer. El esqueleto es el intento ingenuo: imprime un texto fijo, que no es el suyo.
// Sigan los pasos del enunciado: los datos en text, y el código que los imprime dos veces.
const std::string text = "#include <iostream>\n#include <string>\n";
std::cout << text;
return 0;
}Compilación
Cómo se compilan y ejecutan los ejemplos.
# Semana 11: autorreferencia. Quines, el teorema de recursión y la complejidad de Kolmogorov.
# Se usa dentro del entorno del curso.
#
# make compila los programas de la clase en build/
# make test corre las pruebas: cada quine se compila, se ejecuta y se compara con su fuente
# make compress la tabla de tamaños comprimidos de la sección de Kolmogorov
# make clean borra lo generado
#
# quine.cpp, quine_payload.cpp y self_check.cpp se construyeron con make_self a partir de las
# moldes de templates/. Las pruebas comprueban que siguen siendo iguales a lo que da su
# molde. El laboratorio está en lab/quine y tiene su propio Makefile: estas reglas no lo tocan.
CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined
BUILD = build
PROGRAMS = make_self naive_growth gen_string quine quine_payload self_check
TESTS = test_self
HEADERS = self.h
.PHONY: all test compress clean
all: $(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%)
$(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(HEADERS) | $(BUILD)
$(CXX) $(CXXFLAGS) $< -o $@
$(BUILD):
mkdir -p $@
test: all
@for t in $(TESTS); do $(BUILD)/$$t || exit 1; done
@CXX="$(CXX)" CXXFLAGS="$(CXXFLAGS)" BUILD="$(BUILD)" sh test_quines.sh
@echo "Todas las pruebas pasaron."
compress: $(BUILD)/gen_string
@sh compress.sh
clean:
rm -rf $(BUILD)