Prev: [ANN] ECL 10.4.1
Next: compiling a function from a form: is there a better way?
From: "Antti "Andy" Ylikoski" on 5 Apr 2010 06:11

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

When I first was presented this problem many years ago, I immediately
wrote the Unix program

-------------- This file is /usr/antti/self-print.c

main()
{
system("cat /usr/antti/self-print.c");
}

-------------- Quotation ends

which corresponds to the Common LISP program

-------------- 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 would claim that the self-producing program that these code snippets
correspond to:

PRINT ME

is the globally shortest self-printing program.

One solution which has appeared in the literature is

PRINT THIS TWICE, THE SECOND TIME IN QUOTES
"PRINT THIS TWICE, THE SECOND TIME IN QUOTES"

but this is longer and not really easy to translate into Common LISP
(oh, I'm not a wizard, I merely am a user!!) I feel certain that the
wizards in this group easily can put that into Common LISP....

One more solution is presented in Douglas Hofstadter's famous book
"G�del, Escher, Bach -- an Eternal Golden Braid" but this solution is
so complicated that I did not take the time to translate it into
Common LISP (even though that would have been straightforward...)

kind regards, Mr Antti J. Ylikoski
Helsinki, Finland the E.U.
http://www.hut.fi/~ajy/
From: Tamas K Papp on 5 Apr 2010 06:32
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
From: William D Clinger on 5 Apr 2010 09:26
Antti Andy Ylikoski wrote:
> I would claim that the self-producing program that these code snippets
> correspond to:
>
> PRINT ME
>
> is the globally shortest self-printing program.

In Common Lisp, the following program is one of the shortest
self-producing (but not self-printing) programs:

0

I agree that the "PRINT ME" programs are more interesting than
the shortest self-producing programs.

Will
From: "Antti "Andy" Ylikoski" on 5 Apr 2010 11:12
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......

kind regards, Antti J. Ylikoski
Helsinki, Finland, the E.U.
From: Pascal Costanza on 5 Apr 2010 12:11
On 05/04/2010 15:26, William D Clinger wrote:
> Antti Andy Ylikoski wrote:
>> I would claim that the self-producing program that these code snippets
>> correspond to:
>>
>> PRINT ME
>>
>> is the globally shortest self-printing program.
>
> In Common Lisp, the following program is one of the shortest
> self-producing (but not self-printing) programs:
>
> 0

1 is even shorter.


Pascal

--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
 |  Next  |  Last
Pages: 1 2 3
Prev: [ANN] ECL 10.4.1
Next: compiling a function from a form: is there a better way?