Quines

Quines are self-reproducing programs, at least that's how this page defines them:

    http://www.nyx.net/~gthompso/quine.htm

Here are the Tcl entries, as swiped from the Tcl page on that site...


Joe Miller - this has the unfortunate side effect of putting itself in x.

    set x {set x {@}; regsub @ $x $x x; set x}; regsub @ $x $x x; set x

Frank Stajano ([email protected]) - basically the same as above

    set l {set l {L};regsub L $l $l p;puts $p};regsub L $l $l p;puts $p

Joe Miller

    join [split a{a} a] {join [split a{a} a] }

Joe Miller

    join {{} \{ \}} {join {{} \{ \}} }

user

    format [set a {format [set a {%s}] $a}] $a

user

    subst -noc [set a {subst -noc [set a {$a}]}]

Not from the site, but perhaps as instructive:

KBK (12 January 2001) -- Working through a quine can help understand how to write a procedure that generates Tcl code, and how to use the [info] command. Consider the following:

 proc Quine {} {
    append s { } [list proc Quine [info args Quine] [info body Quine]] \n
    append s { puts [Quine]} \n
    return $s
 }
 puts [Quine]

Of course, since [info args Quine] is known to be empty, the following would also work:

 proc Quine {} {
    append s { } [list proc Quine {} [info body Quine]] \n { puts [Quine]} \n
 }
 puts [Quine]

The technique is useful in writing Tcl procedures that generate Tcl code, for instance to make other procedures, compose widget bindings, or execute complicated [uplevel] constructs.


Here is a variant of the previous example that uses no hardcoded values, so Quine is self replicating, and then a "rename Quine A" will still work, i.e. A is self replicating.

 proc Quine {} {
    set procName [lindex [info level 0] 0]
    set argList [info args $procName]
    set body [info body $procName]
    puts "[list proc $procName $argList $body]\n$procName\n"
 }
 Quine

or a more terse version

 proc Quine {} {
    foreach {p a} [info level 0] {set b [info body $p]}
    puts "[list proc $p $a $b]\n$p\n"
 }
 Quine

-BBH


RS has the shortest Tcl quine:

 {}

The empty string is a legal script, can be used as argument to eval, and returns - an empty string, which is the complete source text.

 % expr {{}==[eval {}]}   
 1

QED.

(AMG: I understand QED is Latin for "So what?")

HJG From wikipedia: Q. E. D. is an abbreviation of the Latin phrase "quod erat demonstrandum" (literally, "which was to be demonstrated").

FW: Heh, yeah. Though technically you mean

, not

  {}

;) The blank string has been noted several times as the fundamental multiple-language quine (for languages that don't require any code to do nothing, at least).

Oh, and also, your test script isn't exactly right, because a quine is usually supposed to print something (or nothing), not return it, but the empty script does both correctly, so you're sort of right. - RS: Empty strings have to be grouped with "" or {}, which are not part of the value. But testing Emacs Lisp, I see

 (eval ())
 nil
 (eval nil)
 nil

so the latter has Quine nature, but is not empty.

FW: All I was saying is that {} is only how you represent it as an argument to eval. As an actual script, for example in a .tcl file, it's empty.


FW: Note that quines that introspect their code, for example using [info], don't count. No challenge there. That's little harder than reading in the source file. The challenge is to do it blind, without going into infinite regress like puts {puts {puts {puts {...}}}}. Also, a normal quine doesn't have to be evaluated at the console, it actually prints its value rather than returning it.

DKF: Taking the above restrictions and one of the existing examples:

 puts [join [split "puts \[a{a}]" a] {join [split "puts \[a{a}]" a] }]

Zarutian defines a Double Quine as two programs that reproduce each other. Program A produces the source code of program B and vice versa.

AMG: See http://www0.us.ioccc.org/2000/dhyang.c for the world's greatest triple quine. dhyang.c itself isn't a quine, but it produces one on stdout. dhyang.c makes dhyang-2.c makes dhyang-3.c makes dhyang-4.c makes dhyang-5.c which is identical to dhyang-2.c. And it looks damn cool doing it. You must see it to believe it, and even then you won't believe it.

Now we need a Tcl port. :^)


DKF: Tcl 8.5 provides additional opportunities for making quines:

apply {{} {return [info level 0]}}

Indeed, this makes it simple to construct a quine that does almost anything else you might want, so long as you put the whole payload before returning as above.


KBK: Indeed, apply provides the machinery for more traditional quines, such as:

apply {f {list apply $f $f}} {f {list apply $f $f}}

kefka

set f {set f {%s};format $f $f};format $f $f