Prev: [ANN] ECL 10.4.1
Next: compiling a function from a form: is there a better way?
From: Ron Garret on 6 Apr 2010 10:41
In article <rNOSPAMon-643D9A.16165905042010(a)news.albasani.net>,
RG <rNOSPAMon(a)flownet.com> wrote:

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

Heh, I just thought of a much better way to tell that joke:

Zen master Kwine was raking pebbles in the garden when a student
approached and asked, "Maseter, what is the shortest self-replicating
Lisp program?"

The master was silent. The student was annoyed and said, "Master, why
will you not answer my question?"

The master looked up and said, "But I did answer your question."

At that moment the student was enlightened.

:-)
From: "Antti "Andy" Ylikoski" on 8 Apr 2010 04:54
5.4.2010 19:34, Tamas K Papp kirjoitti:
> 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

Thank you for advising me!

As a matter of fact I'm not a total newbie about LISP.

In the years 1985-1986 I wrote my MSc thesis ("diploma thesis") at the
Nokia R&D department, using the MRS (the Metalevel Reasoning System)
written in the Stanford University, by the HPP (the Heuristic
Programming Project.)

Unfortunately, the MRS contained a fatal bug -- in the routines which
STASH and fetch predicate logic formulas into/from the database.
Because of this, and because of some highly unfortunate external
events, the prototype which I built never became a running expert
system. (The expert system I designed was intended to carry out the
automated diagnosis of the feedwater system of a nuclear power plant.
I still vividly recall when I was told that this task was so difficult
that humans could not do it -- so the electric utility company had
wished for a computer program to carry out the task:-)))))

The Stanford University Heuristic Programming Project originally had
wanted to write a program which could reason about itself. However,
they had created a general-purpose reasoning program -- so the MRS
could be utilized as an expert system shell!!! That was the time when
the ART (Automated Reasoning Tool) by Inference Corp. (most probably a
commercial trade mark) and the KEE (Knowledge Engineering Environment)
by Intellicorp (also most probably a commercial trade mark) and the
OPS5 ("Official Production System 5") by Forgy et al. were in the
vogue.

And what does this have to do with LISP? The MRS was written in LISP.
There even existed a Symbolics Zetalisp version so we could run MRS in
a Symbolics 3600 LISP Machine. BTW if they have corrected the bug in
Stanford then the individuals amongst us who read this and who wish to
write expert systems might ask if they still could give out copies of
the MRS from the documents of the Stanford HPP.

I'm familiar with Seigel's book "Practical Common LISP"; the somewhat
older Winston's book "LISP, 3rd Edition"; Paul Graham's book "On
Lisp"; Peter Norvig's book "Paradigms of Artificial Intelligence
Programming"; and Doug Hoyte's book "Let Over Lambda"; and Keene's
book "Object-Oriented Programming in Common LISP". And a repertoire
of Artificial Intelligence textbooks. I also own Steele's "Common
LISP, the Language."

But, I said I'm a user not a wizard. When some wizardry concerning
LAMBDA and 'QUOTE etc etc is required, my LISP skills do not exactly
shine. They might shine if I had had more time to dedicate to this
queen of programming languages.

BTW I'm in the process of finishing my PhD research. My main result
is that the question about the class NP (nondeterministic
polynomial-time) actually is a symbolic reasoning problem -- hence the
idea of a formal theory of symbolic reasoning systems, and a formal
theory of Artificial Intelligence systems.

And, of course, thence my interest in LISP (and Smalltalk). I never
was a Prolog enthusiast.

kind regards, Antti J. Ylikoski
Helsinki, Finland, the E.U.

PS. I invented one more short self-outputting Common LISP program:

(PRINT -)

but I do admit that that is hackery, not a real quinification-based
self-printing program.

Idem

From: Pascal J. Bourguignon on 8 Apr 2010 06:24
"Antti \"Andy\" Ylikoski" <antti.ylikoski(a)gmail.com> writes:

> PS. I invented one more short self-outputting Common LISP program:
>
> (PRINT -)
>
> but I do admit that that is hackery, not a real quinification-based
> self-printing program.

Yes, like the programs such as 0 or 1, this is not a self sufficient
program (but then which is?).

In the case of a self evaluating atom, you need the REPL to print it.
In the case of your (print -), you need the REPL to bind - to (print -).


On the other hand, this form, similar to yours, is a quine:

#1=(print '#1#)

Here is the definition I use:

(defun form-is-a-quine (form)
(let ((path (string (gensym "/tmp/quine-")))
(*print-circle* t)
(*PRINT-ARRAY* t)
(*PRINT-LENGTH* nil)
(*PRINT-LEVEL* nil)
(*PRINT-READABLY* t)) ; excluding non printable readably programs...
(unwind-protect
(progn
(with-open-file (src path :direction :output
:if-does-not-exist :create)
(print form src))
(let ((output (read-from-string
(with-output-to-string (*standard-output*)
(load path :verbose nil :print nil)))))
(string=
(prin1-to-string output)
(prin1-to-string form))))
(delete-file path))))


C/USER[49]> (form-is-a-quine '(print -))
NIL
C/USER[50]> (form-is-a-quine '#1=(print '#1#))
T

I would really like to use equal instead of string=, but prin1 already
deals satisfactorily with circular structure, so I take this
shortcut...

--
__Pascal Bourguignon__
From: "Antti "Andy" Ylikoski" on 13 Apr 2010 09:30
Pascal J. Bourguignon wrote:
> "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.
>
>

Yes you are perfectly correct that the "eniuq" does not produce itself.

That is the reason why I wrote about it here in the newsgroup.

I attempted to faithfully translate Hofstadter's self producing progam
into Common LISP and the result was that which I submitted.

Of course a translation which goes according to the model of this self
producing LAMBDA expression is that which I should have written... But
as I said that flawed expression is the result of attempting to
character by character translate Hofstadter's program ... Which was
being carried out with insufficient knowledge from my part!!!

kind regards, A. J. Y.
First  |  Prev  | 
Pages: 1 2 3
Prev: [ANN] ECL 10.4.1
Next: compiling a function from a form: is there a better way?