=--------------------------------------------------------------------
appendix to "GEB" FAQ: self-rep programs or "quines"
=--------------------------------------------------------------------
http://www.cs.indiana.edu/hyplan/tanaka/GEB/
http://www.cs.indiana.edu/hyplan/tanaka/GEB/quine.html
;;; TANAKA Tomoyuki ("Mr. Tanaka" or "Tomoyuki")
;;; <http://www.cs.indiana.edu/hyplan/tanaka.html>
;;; e-mail: tanaka@cs.indiana.edu
Language: English (from "Metamagical Themas")
Alphabetize and copy in quotes
"in and copy quotes Alphabetize".
=--------------------------------------------------------------------
contents:
-- 1. introduction
-- 2. Lisp/Scheme self-rep programs
---- TT's favorites
------ T1. "son of Sploge" (Lx.((Lx.x)x)) ((Lx.x)x)
------ T2. quine-palindrome
------ T3. "eval" trick
------ T4. (call/cc call/cc)
---- a few more.
-- 3. some parting thoughts
---- pronunciation of "quine"
---- re T1. "son of Sploge" (Lx.((Lx.x)x)) ((Lx.x)x)
---- how to avoid repetition
---- go upstream in the EVAL chain
=--------------------------------------------------------------------
-- 1. introduction
"self-rep" = self-reproducing, self-replicating, ...
the best/biggest collection of self-rep programs:
http://www.nyx.net/~gthompso/quine.htm
see also: http://math.cornell.edu/~chruska/recursive/selfish.html
is there a place where i can run APL (login as "guest" etc)?
(it's been 20 years since i wrote my last APL program.)
=--------------------------------------------------------------------
-- 2. Lisp/Scheme self-rep programs
in lambda calculus we have Spl = (Lx.xx)(Lx.xx)
which is called "sploge". (what language is this?)
there's the Lisp/Scheme version.
((lambda (x) `(,x ',x)) '(lambda (x) `(,x ',x)))
or
((lambda (x) (list x (list 'quote x)))
'(lambda (x) (list x (list 'quote x))))
=--------------------------------------------------------------------
---- TT's favorites
i did a few variants. my favorite one are these:
Author: TANAKA Tomoyuki
Language: Scheme (Chez Scheme Version 5.0b)
------ T1. "son of Sploge" (Lx.((Lx.x)x)) ((Lx.x)x)
((lambda (x) `((lambda (x) ,x) ',x)) '`((lambda (x) ,x) ',x))
(a better name is "Sploge's well-behaved brother")
------ T2. quine-palindrome
((lambda (x) `(,(reverse x) ',x)) '(`(,(reverse x) ',x) (x) lambda))
"Metamag Themas" p.65 contains an English
quine-palindrome by Sallows.
------ T3. "eval" trick
((lambda (q) ((lambda (x) `((lambda (q) ,((eval q) x)) ',q))
'(lambda (x) `((lambda (q) ,((eval q) x)) ',q))))
'(lambda (x) `(,x ',x)))
------ T4. (call/cc call/cc)
((lambda (c)
(if (procedure? c)
(c '`((lambda (c) (if (procedure? c) (c ',c) ,c)) (call/cc call/cc)))
`((lambda (c) (if (procedure? c) (c ',c) ,c)) (call/cc call/cc))))
(call/cc call/cc))
=--------------------------------------------------------------------
---- a few more.
--- 1.
((lambda (q qq) ((lambda (x) `((lambda (q qq) ,(q x)) . ,(q qq)))
'(lambda (x) `((lambda (q qq) ,(q x)) . ,(q qq)))))
(lambda (q) `(,q ',q))
'(lambda (q) `(,q ',q)))
--- 2.
(call/cc
(lambda (c)
(c ((lambda (c) `(call/cc (lambda (c) (c (,c ',c)))))
'(lambda (c) `(call/cc (lambda (c) (c (,c ',c)))))))))
--- 3.
(call/cc
(lambda (c)
(call/cc
(lambda (cc)
(c ((lambda (c)
`(call/cc
(lambda (c) (call/cc (lambda (cc) (c (,c ',c)))))))
'(lambda (c)
`(call/cc
(lambda (c) (call/cc (lambda (cc) (c (,c ',c)))))))))))))
--- 4.
((lambda (c)
(if (procedure? c) (c 0)
((lambda (c) `((lambda (c) (if (procedure? c) (c 0) (,c ',c)))
(call/cc call/cc)))
'(lambda (c) `((lambda (c) (if (procedure? c) (c 0) (,c ',c)))
(call/cc call/cc))))))
(call/cc call/cc))
=--------------------------------------------------------------------
-- 3. some parting thoughts
http://www.dejanews.com/getdoc.xp?AN=426207567
i just spend several hours thinking about Lisp/Scheme
expressions that evaluated to themselves.
it's easy to get carried away. i'll try to give it a
rest now. some (hopefully) parting thoughts:
---- pronunciation of "quine"
my Webster's dictionary says
Biographical Names
Quine \'kw[0xF5]^-n\
Willard Van Orman 1908- Am. philos.
which means that "Quine" rhymes with "wine".
Jargon file made an error.
---- re T1. "son of Sploge" (Lx.((Lx.x)x)) ((Lx.x)x)
what's the general form of a "self-reductive" form in
lambda calculus? is this in Barendregt's book?
---- how to avoid repetition
i don't like the name "quine" for these things because
that label could be limiting.
self-evaluating forms need not be quines (i.e. repetitive).
in T3
((lambda (q) ((lambda (x) `((lambda (q) ,((eval q) x)) ',q))
'(lambda (x) `((lambda (q) ,((eval q) x)) ',q))))
'(lambda (x) `(,x ',x)))
i was able to avoid repeating (lambda (x) `(,x ',x)) by
using EVAL.
but i still repeated
(lambda (x) `((lambda (q) ,((eval q) x)) ',q))))
is there a clever way to avoid such repetition('repetition)?
---- go upstream in the EVAL chain
one way to avoid repetition('repetition) is to go
upstream in the EVAL chain.
((lambda (c) `((lambda (c) ,c) ',c))
'`((lambda (c)
(if (procedure? c) (c ',c) ,c))
(call/cc call/cc)))
this is not a quine, but if you evaluate it
twice you get T4 above, which is a quine.
this C quine is really nice.
main(a){printf(a="main(a){printf(a=%c%s%c,34,a,34);}",34,a,34);}
=--------------------------------------------------------------------
END