Prev: [ANN] ECL 10.4.1
Next: compiling a function from a form: is there a better way?
From: Tamas K Papp on 5 Apr 2010 12:34
On Mon, 05 Apr 2010 18:12:06 +0300, Antti \"Andy\" Ylikoski wrote:

> 5.4.2010 13:32, Tamas K Papp kirjoitti:
>> On Mon, 05 Apr 2010 13:11:43 +0300, Antti \"Andy\" Ylikoski wrote:
>>
>>> -------------- This file is C:\AI\self-print.lsp
>>>
>>> ;;; The globally simplest self printing program. ;;; ;;; Corresponds
>>> to the self printing program ;;; PRINT THIS ;;;
>>> ;;; Antti J. Ylikoski 04-05-2010.
>>> ;;;
>>>
>>> (defun self-print ()
>>> (with-open-file (stream "c:\\AI\\self-print.lsp")
>>> (pprint (read stream))))
>>>
>>> -------------- Quotation ends
>>
>> I am under the impression that people who play around with these things
>> want programs that _generate_ their own source code (and Lisp may be a
>> nice language for that). Using the OS/filesystem to retrieve the
>> source code is not a particularly interesting solution.
>>
>> In contrast, check out this solution from Wikipedia [1]:
>>
>> ((LAMBDA (X) (LIST X (LIST 'QUOTE X))) '(LAMBDA (X) (LIST X (LIST
>> 'QUOTE X))))
>>
>> It is quite elegant, and understanding it is a good exercise.
>>
>> Best,
>>
>> Tamas
>>
>> [1]
>> http://en.wikipedia.org/wiki/Quine_%28computing%29#Scheme_.28also_valid_Common_Lisp.29
>
> Thank you very much for the pointer, and clarifying the point.
>
> I attempted to convert Hofstadter's program into Common LISP and ended
> up with the following:
>
> ---- Start of quotation
>
> ;;; Self printing program from Douglas Hofstadter's book, ;;; p. 498,
> ISBN 0-394-74502-7.
> ;;;(well, at least my attempt at it...) ;;;
> ;;; Antti Ylikoski 04-05-2010.
> ;;;
>
> (defun eniuq (template)
> (format t "~S ( \" ~S \" ) ." template template))
>
> (eniuq "(defun eniuq (template)
> (format t \" ~S ( \" ~S \" ) . \" template template))
> eniuq")
>
> ---- End of quotation
>
> Either my skill here is imperfect, or Hofstadter may have committed an
> error (he probably hasn't run his program), or both. I would bet on the
> first alternative......

I would bet on that too :-) I read that book a long time ago, but an
idiomatic Lisp implementation of "eniuq" could be exactly the function
I copied from Wikipedia. Please do try to understand it first, it
will help.

Now that you have got some quines, I am not sure what you want to do
with Lisp. A very powerful feature and unique feature of the Lisp
family is the ability to transform Lisp code easily. Quines are an
amusing example of that, but it gives you many practical advantages,
too. If you are interested in Lisp beyond quines and want to learn
more of it, just start reading a good book, eg
http://www.gigamonkeys.com/book/

Best,

Tamas
From: Pascal J. Bourguignon on 5 Apr 2010 13:26
"Antti \"Andy\" Ylikoski" <antti.ylikoski(a)gmail.com> writes:

> 5.4.2010 13:32, Tamas K Papp kirjoitti:
>> On Mon, 05 Apr 2010 13:11:43 +0300, Antti \"Andy\" Ylikoski wrote:
>>
>>> -------------- This file is C:\AI\self-print.lsp
>>>
>>> ;;; The globally simplest self printing program. ;;;
>>> ;;; Corresponds to the self printing program ;;; PRINT THIS
>>> ;;;
>>> ;;; Antti J. Ylikoski 04-05-2010.
>>> ;;;
>>>
>>> (defun self-print ()
>>> (with-open-file (stream "c:\\AI\\self-print.lsp")
>>> (pprint (read stream))))
>>>
>>> -------------- Quotation ends
>>
>> I am under the impression that people who play around with these
>> things want programs that _generate_ their own source code (and Lisp
>> may be a nice language for that). Using the OS/filesystem to retrieve
>> the source code is not a particularly interesting solution.
>>
>> In contrast, check out this solution from Wikipedia [1]:
>>
>> ((LAMBDA (X) (LIST X (LIST 'QUOTE X))) '(LAMBDA (X) (LIST X (LIST 'QUOTE X))))
>>
>> It is quite elegant, and understanding it is a good exercise.
>>
>> Best,
>>
>> Tamas
>>
>> [1] http://en.wikipedia.org/wiki/Quine_%28computing%29#Scheme_.28also_valid_Common_Lisp.29
>
> Thank you very much for the pointer, and clarifying the point.
>
> I attempted to convert Hofstadter's program into Common LISP and ended
> up with the following:
>
> ---- Start of quotation
>
> ;;; Self printing program from Douglas Hofstadter's book,
> ;;; p. 498, ISBN 0-394-74502-7.
> ;;;(well, at least my attempt at it...)
> ;;;
> ;;; Antti Ylikoski 04-05-2010.
> ;;;
>
> (defun eniuq (template)
> (format t "~S ( \" ~S \" ) ." template template))
>
> (eniuq "(defun eniuq (template)
> (format t \" ~S ( \" ~S \" ) . \" template template))
> eniuq")
>
> ---- End of quotation
>
> Either my skill here is imperfect, or Hofstadter may have committed an
> error (he probably hasn't run his program), or both. I would bet on
> the first alternative......


First, they are often called Quines, after W.V. Quine.
http://en.wikipedia.org/wiki/Willard_Van_Orman_Quine
You will probably get more hits using this keyword.


Next, in the case of lisp, you have to choose whether you will work at
the text level or at the sexp level.

Arguably, lisp sources are sexps, text is a mere serialization used to
store the sexps into "text" files, but we could as well save the sexps
in files structured differently (and design an editor (or emacs
extension) to read and edit directly these structured sexp files).


In either case, the quine should produce "itself" without relying on an
source file, but should produce itself. Your eniuq implementation does
not:


C/USER[2]> (load "~/src/lisp/eniuq.lisp")
;; Loading file /Users/pjb/src/lisp/eniuq.lisp ...
"(defun eniuq (template)
(format t \" ~S ( \" ~S \" ) . \" template template))
eniuq" ( "
"(defun eniuq (template)
(format t \" ~S ( \" ~S \" ) . \" template template))
eniuq" " ) .
;; Loaded file /Users/pjb/src/lisp/eniuq.lisp
T


In addition, if you're considering lisp sexps, you should allow for the
various forms of printed ("serialized") sexps. eg. NIL can be printed
and read either as NIL or (). If you consider sexps, you should accept
both (otherwise it means you want to deal at the text level).


http://www.informatimago.com/develop/lisp/small-cl-pgms/quine.lisp


Now, what's interesting about quines is that the program may do
something more than just producing itself. For example, you could write
an artificial intelligence that would include a self replicating
procedure that could be applied to spread itself amongst all the
computers of the world! "Skynet!!!" ;-)




Concerning:

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

the question I'd be interested in is, having reduced it to pure lambda
calculus (list is easy, quote is harder: you'd need to develop a lambda
calculus (ie functional) representation of lambda calculus), to compute
the probability of occurence of such a quine (of families of such
quines, including those with random payloads) given random appearance
of lambda calculus forms.


--
__Pascal Bourguignon__
From: William D Clinger on 5 Apr 2010 18:28
Pascal Costanza wrote:
> > 0
>
> 1 is even shorter.

Skinnier.

Will
From: RG on 5 Apr 2010 20:16
In article
<487598aa-a387-4cd4-81c3-60845ff3314b(a)n34g2000yqb.googlegroups.com>,
William D Clinger <cesura17(a)yahoo.com> wrote:

> Pascal Costanza wrote:
> > > 0
> >
> > 1 is even shorter.
>
> Skinnier.
>
> Will

You're all wrong. The shortest self-replicating program is this one:
From: refun on 6 Apr 2010 07:22
In article <zHiun.6416$4c4.4784(a)uutiset.elisa.fi>, antti.ylikoski(a)gmail.com
says...

> The question of programs which produce themselves, and in particular
> the question of the shortest self-producing program, is a well-known
> brain teaser.

Here's another Lisp quine:

(let ((let '`(let ((let ',let)) ,let)))
`(let ((let ',let)) ,let))

;(equal (eval quine) (eval (eval quine))) => T

I've first encountered it on c.l.l, a couple of months ago while reading some
old posts, but I can't remember the actual posts, so I just re-derived it, as
once one understands the idea behind it, it's quite easy to do.

It might also be worth noticing that it's a more general Lisp quine, as it
works both in CL and Scheme, and maybe in some other Lisp dialects that have
backquote, quote and the same syntax for LET.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: [ANN] ECL 10.4.1
Next: compiling a function from a form: is there a better way?