What's a quine? To quote Russ quoting Ken Thompson (in his masterful Turing Award acceptance speech): "More precisely stated, the problem is to write a source program that, when compiled and executed, will produce as output an exact copy of its source." This statement only allows valid programs in the language. The innovation of the Steele method is to squint at this definition. Instead of "compiled and executed", let's change it to "to run through a compiler/interpreter".
A traditional quine must be a valid program in the language. But when you invoke most language runtimes with an invalid program, they aren't silent. They do produce output. Often error diagnostics to help the programmer craft their gibberish into a valid program.
So what does an invalid-program quine look like? Well, we know it has to be an error message. It has to be an error message whose error is itself. Let's take python. Fire up an interpreter and enter an invalid program:
>>> a
Traceback (most recent call last):
File "", line 1, in
NameError: name 'a' is not defined
Is that error message an invalid-program quine? Let's check.
>>> Traceback (most recent call last):
File "", line 1
Traceback (most recent call last):
^
SyntaxError: invalid syntax
Nope. A NameError isn't a NameError. It's a SyntaxError.
So how will we find it? Well, we could try traditional quine-construction techniques, but this requires an in-depth knowledge of each language runtime we want to find an invalid-program quine for. And traditional quine-construction techniques are, well, hard: they require that you work backward and forward at the same time. Let's not do that.
Instead, think back to our last revelation: a NameError isn't a NameError, it's a SyntaxError. But maybe a SyntaxError is a SyntaxError (quine!). Or maybe it's a FrobError, and a FrobError is a FrobError (quine!).
And here's the advantage studying invalid-program quines: not only are they perverse, they're also easy. Take input, run it through the language runtime, compare the error message to the input. If they're different, just repeat. But if they are the same, then the language runtime evaluated the input to the error message, and we've found an invalid-program quine.
Returning to the python example: a SyntaxError isn't a SyntaxError, and it isn't a FrobError. It's an IndentationError. And an IndentationError is an IndentationError. Here, then, is our invalid-program quine for python:
>>> File "<stdin>", line 1
File "<stdin>", line 1
File "<stdin>", line 1
^
IndentationError: unexpected indent
But if you read Russ's post, you already know a python quine. So let's find some invalid-program quines in some more languages. And let's do it faster.
#! /bin/bash
languages="python;py
awk;awk
ruby;rb
gcc cc
javac java
bash sh
ksh ksh
zsh zsh
perl;pl"
# Find an error quine for a language.
# Args:
# $1: compiler for the language
# $2: file suffix
function find_quine_for_language {
COMPILER=$1
SUFFIX=$2
echo "Searching for error quine for $COMPILER"
echo "Yields falsehood when preceded by its quotation" > input.$SUFFIX
echo "" > output.$SUFFIX
found=""
for ((n=1; n <= 24; n++)) do
$COMPILER input.$SUFFIX > output.$SUFFIX 2>&1
echo -n "."
if cmp -s input.$SUFFIX output.$SUFFIX; then
found=true
break
fi
mv output.$SUFFIX input.$SUFFIX
done
echo
if [ ! -z $found ]; then
echo "Found error quine for $COMPILER after $n steps."
echo "================================"
cat input.$SUFFIX
echo "================================"
else
echo "Could not find error quine for $COMPILER after $n steps."
echo "> du -ah input.$SUFFX"
du -ah input.$SUFFIX
fi
}
for language in $languages
do
language=$(echo $language | tr ";" " ")
find_quine_for_language $language
done
First, I've listed some language runtimes and the suffix we should use for files in that language. Then I define the function that tries to find an invalid-program quine for the language. The only added sophistication from my description is a limit to the number of iterations. Why? Most runtimes on the list tell you about the first error, or the first n errors. They think that after this many errors, any more wouldn't be useful. But one of these runtimes keeps nitpicking your by-now-obviously-not-valid program. There is no fixed point. Each error message is longer than the input, and without this limit your machine grinds to a halt. (If you want to know which language leads to a 70 megabyte text file of parse errors, run the program yourself)
The moral of the story? The next time you find yourself in a quine-speed-writing competition, type gibberish and repeat.
3 comments:
f-22 raptor ra atomaders cd wave audio editor asf seek maker stoik smart resizer icon3d ver.2.04 vbfriend blaze dvd copy pprecorder x-treem mp3 manager [url=http://bb-soft.co.cc/zeroads-v1-35-0220-0001-free-download]Zeroads V1.35.0220.0001 free download[/url] polespo fischerpruefung boot locker bj cd organizer drag and view dwg pixwizard vimas singing tutor web speed analyzer godezip 2000 ulead film brennerei [url=http://bb-soft.co.cc/zscompare-pro-v3-02j-free-download]Zscompare Pro V3.02j free download[/url] database maker interactive sequence the sleuthhound vissie flaggenquiz amerika foongrep ii macro expert flashfpx xl delete space saver
Ивестиционно-строительное предприятие ПРИОР предлагает :
- капитальный ремонт квартир и офисов по низким (со скидкой)) ценам
- Евроремонт квартир ,дач также офисных помещений с любым обьемом работ
- высококачественный ремонт, перестройка промышленых и также жилых зданий
- качественный ремонт и также обновление торговых, игровых и развлекательных центров,медицинских,финансовых и правительственных учреждений.
- все виды строительно-инженерных, отделочных работ,покраска,побелка,стяжка,поклейка обоев ,плитка и пр.
- контроль а также гарантия качественного исполнения работ,
Гарантия.
http://remontkiev.org.ua
zoftozerg9981
zoftozerg9982
Post a Comment