self-rep programs or "quines"

[Tomoyuki Tanaka]

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: tan...@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:
[...]

[Will Fitzgerald]

My favorite Lisp expression that evaluates to itself is:

-

It's hard to imagine anything shorter.

[Barry Margolin]

In article <766jam$d...@news.net-link.net>,

Will Fitzgerald <fitzg...@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, bar...@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.

[Florian Weimer]

"Will Fitzgerald" <fitzg...@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. ;)

[Mayer Goldberg]

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

[Tomoyuki Tanaka]

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))
>

--