From: hopkins@coulin.turing.ac.uk (Don Hopkins)
Newsgroups: comp.lang.scheme
Subject: Re: deriving quines
Date: 15 Apr 92 23:13:36 GMT
Reply-To: hopkins@uk.ac.turing
Organization: The Turing Institute, Glasgow, Scotland.

In article <1992Apr15.053029.6329@pasteur.Berkeley.EDU>, c60a-tf@congo.Berkeley.EDU (Matt Wright) writes:
|> In article <1992Apr7.013639.20954@turing.ac.uk> hopkins@uk.ac.turing writes:
|> ->A grad student friend of mine once showed me a technique for deriving a quine
|> ->(a self reproducing program, that when evaluated, returns itself) in a sufficiently
|> ->powerful language, like Scheme or Lisp. 
|> ->
|> -> [...]
|> ->PS: the BASIC program:
|> ->10 LIST
|> ->isn't the kind of program I'm talking about. (Basic isn't powerful enough,
|> ->anyway.)
|> 
|> Actually, I dimly recall seeing a BASIC program that could print itself, I'm
|> sorry to say.  That's about the only thing BASIC is powerful enough for,
|> though, IMHO.  :-) Not to mention that it was 20 or 30 disgusting lines
|> long; nothing like the incredibly cool ((lambda (lambda) ...)) version.
|> (Although it won't really work, since LAMBDA is a keyword and can't be a
|> variable name.  But it's certainly elegant!)
|> 
|> -Matt

I made a little typo in lisp quine, leaving out a level of parens. It
should be:

((lambda (x) (list x (list (quote quote) x)))
 (quote (lambda (x) (list x (list (quote quote) x)))))

And here is a BASIC quine. I tested this out on Rich Skrenta's
Apple ][ emulator. This is the first time in a long time
that I have written a basic program, and the first time *ever*
I've typed one into emacs, and dragged and dropped the source 
code into an Apple (albeit a soft Apple emulator). 

100 DATA "FOR X = 100 TO 230 STEP 10"
110 DATA "READ A$"
120 DATA "PRINT X;* DATA *;CHR$(34);A$;CHR$(34)"
130 DATA "NEXT X"
140 DATA "RESTORE"
150 DATA "FOR X = 500 TO 630 STEP 10"
160 DATA "PRINT X;* *;"
170 DATA "READ A$"
180 DATA "FOR Y = 1 TO LEN(A$)"
190 DATA "B$ = MID$(A$,Y,1): IF B$ = CHR$(42) THEN B$ = CHR$(34)"
200 DATA "PRINT B$;"
210 DATA "NEXT Y"
220 DATA "PRINT"
230 DATA "NEXT X"
500 FOR X = 100 TO 230 STEP 10
510 READ A$
520 PRINT X;" DATA ";CHR$(34);A$;CHR$(34)
530 NEXT X
540 RESTORE
550 FOR X = 500 TO 630 STEP 10
560 PRINT X;" ";
570 READ A$
580 FOR Y = 1 TO LEN(A$)
590 B$ = MID$(A$,Y,1): IF B$ = CHR$(42) THEN B$ = CHR$(34)
600 PRINT B$;
610 NEXT Y
620 PRINT
630 NEXT X 

The main problem is dealing with the quotes in the literal
program text. A much simpler problem to solve in lisp. 
It's easy to write a pascal or C quine using the same 
structure as the above basic program, you just have to
deal with each language's idiosynchratic quoting convention.
Like doubling the single quotes in pascal or putting 
backslashes back into the C strings. 

Anyway, I wasn't looking for quines, I was looking for a
technique for *deriving* quines in sufficiently powerful
languages. (BASIC, C, and Pascal are *NOT* sufficiently
powerful). In this case sufficiently powerful means programs
are first class data structures. I was able to derive a
PostScript quine, but I have lost it, and that's why I
am trying to find a reference to the technique I used to
derive it. (Sure you can do it by hand like I did with 
BASIC but that's not nearly as fascinating as having a 
general purpose technique.)

Here's a PostScript quine that Stan Switzer came up with
(by hand):

{{[exch /dup load /exec load] cvx} dup exec}

Remember, it's not the size that counts, it's the technique!

	-Don