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:
1. re attached: -- T1. "son of Sploge" (Lx.((Lx.x)x)) ((Lx.x)x)
what's the general form of a "self-reductive" form in
lambda calclus? is this in Barendregt's book?
2. i don't like the name "quine" for these things because that
label could be limiting.
a self-evaluating form need not be a quine (i.e. repetitive).
in T2
((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?
=--------------------------------------------------------------------
appendix to "GEB" FAQ: self-rep programs or "quines"
=--------------------------------------------------------------------
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: ······@cs.indiana.edu
=--------------------------------------------------------------------
contents:
-- introduction
-- Lisp/Scheme self-rep programs by TT
=--------------------------------------------------------------------
-- introduction
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
i'll probably do an APL one soon.
(it's been 20 years since i wrote my last APL program.)
=--------------------------------------------------------------------
-- Lisp/Scheme self-rep programs by TT
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))))
=--------------------------------------------------------------------
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))
-- T2.
((lambda (q) ((lambda (x) `((lambda (q) ,((eval q) x)) ',q))
'(lambda (x) `((lambda (q) ,((eval q) x)) ',q))))
'(lambda (x) `(,x ',x)))
-- T3.
((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))
=--------------------------------------------------------------------
here are 4 more:
[...]
In article <··········@news.net-link.net>,
Will Fitzgerald <··········@neodesic.com> wrote:
>My favorite Lisp expression that evaluates to itself is:
>
>-
That only evaluates to itself when typed to the R-E-P loop, not in any
other context. Most quines are more general.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Don't bother cc'ing followups to me.
"Will Fitzgerald" <··········@neodesic.com> writes:
> My favorite Lisp expression that evaluates to itself is:
>
> -
This doesn't work with Elisp and most (all?) Scheme implementations.
But `0' does work. ;)
i couldn't stop thinking about these quines.
1. quine-palindrome
((lambda (x) `(,(reverse x) ',x)) '(`(,(reverse x) ',x) (x) lambda))
2. this C quine is really nice. (see URLs below for the author)
main(a){printf(a="main(a){printf(a=%c%s%c,34,a,34);}",34,a,34);}
3. avoiding repetition
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 form above is not a quine, but if you evaluate it
twice you get T3 below, which is a quine.
--------------------------------------------------------------------
> http://www.cs.indiana.edu/hyplan/tanaka/GEB/quine.html
> http://www.nyx.net/~gthompso/quine.htm
> http://math.cornell.edu/~chruska/recursive/selfish.html
>
>-- T1. "son of Sploge" (Lx.((Lx.x)x)) ((Lx.x)x)
>
> ((lambda (x) `((lambda (x) ,x) ',x)) '`((lambda (x) ,x) ',x))
>
>-- T2.
> ((lambda (q) ((lambda (x) `((lambda (q) ,((eval q) x)) ',q))
> '(lambda (x) `((lambda (q) ,((eval q) x)) ',q))))
> '(lambda (x) `(,x ',x)))
>
>-- T3.
> ((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))
>
--
;;; TANAKA Tomoyuki ("Mr. Tanaka" or "Tomoyuki")
;;; http://www.cs.indiana.edu/hyplan/tanaka.html
How about this one: If you run it, it prints out the program that defines it:
(define foo
(lambda ()
((lambda (m)
`(define foo
(lambda ()
(,m ',m))))
'(lambda (m)
`(define foo
(lambda ()
(,m ',m)))))))
Best regards,
Mayer