Since in Lisp programs are treated as a data structure--how
could one code a program that could produce a copy of it self.
I think something like:
(defmacro copy-machine (&body copy-me)
`(defmacro copy-machine (&body copy-me)
,@copy-me ;; or ,copy-me I forget which one
)
)
(copy-machine (format t "&A Copy-Machine") ==> ;;should produce
(defmacro copy-machine (&body copy-me)
(format t "&A Copy-Machine")
)
;; I know this is a primitive example. I want it to produce an
;; exact copy of itself. And, I think this example provides an
;; idea about what I am looking for. I want to see an example
;; about how to code a GEB-style Copy Machine.
would prove to be a primitive Turing Copy-Machine.
I am intrested in exploring self-replicating code ala Godel, Escher, Bach
by Dr. Hofstedter.
The above example seems trivial--is their a much better/more elegant
program, one that might have real world applications.
What, in affect, I want to know is how could I code a Lisp program so that
it produces a working copy of itself.
I am just intrested in the mechanism of Copying in a self-reproducing machine.
Thanks for any help you can provide me with.
Happy Coding!!!!!
·································@hotmail.com (Franz Kafka) writes:
> Since in Lisp programs are treated as a data structure--how
> could one code a program that could produce a copy of it self.
In general, any program that gets a copy of itself as an argument or
that knows its own name can produce a copy. You can't copy a program
without a pointer to the original or without hardwired knowledge of
the program shape you intend to create, and without the ability to pry
apart the storage behind the code to whatever degree you want to copy.
Note that even the term 'copy' is somewhat ill-defined and requires
elaboration. See http://www.nhplace.com/kent/PS/EQUAL.html
Some examples...
In a lisp listener, the expression - is bound to the top-level expression
being executed, so typing - to the listener should type back - itself.
Technically, that's self-evaluating. It makes assumptions about the
existing expression being stored externally.
Likewise, you can do (print -) to see (PRINT -) printed.
You could pass a pointer to an expression to be copied this way:
(setq *print-circle* t) ;fail to do this and you'll be sorry
;=> T
(defun copy-tree-and-sharing (x)
;; I did only light testing of this. caveat emptor. -kmp 29-Mar-2003
(let ((table (make-hash-table)))
(labels ((descend (x)
(cond ((atom x) x)
((gethash x table))
(t (let ((replacement (cons nil nil)))
;; FIRST put the replacement in table to avoid
;; infinite recursion, THEN descend
;; -kmp 29-Mar-2003
(setf (gethash x table) replacement)
(setf (car replacement) (descend (car x)))
(setf (cdr replacement) (descend (cdr x)))
replacement)))))
(descend x))))
;=> COPY-TREE-AND-SHARING
;; In this case, we don't assume the expression is stored in -
;; but we instead pass in the expression explicitly.
#1=(copy-tree-and-sharing '#1#)
;=> #1=(COPY-TREE-AND-SHARING (QUOTE #1#))
The other way is to have a program simply produce a copy of its own
source code:
;; I did this one from memory and didn't actually test it, but I think
;; it looks right. -kmp 29-Mar-2003
(let ((let '`(let ((let ',let)) ,let)))
`(let ((let ',let)) ,let))
There are, of course, functional alternatives using the Y operator.
They are copiously documented, though, and I'm not going to regurgitate
that stuff here.
>
> Note that even the term 'copy' is somewhat ill-defined and requires
> elaboration.
>
I am talking about copying in the way that John Van Numann's cellura
automata produced a copy of its self. A fully functional copy of the
program that is capible of producing other fully functional copys.
Kind of how Christopher Langton, or John Koza were defining
copying-machines when they talked about cellular automata.
The programs that are known to copy like this are: some cellular
automata systems, Terra programs from Dr. Ray's Terra program,
Viruses, Worms, and programs that were written to play the game of
CoreWares.
The thing I am intrested in is: how a program could produce an exact
copy of itself? where would it store the template telling what needed
to be made? Would the template telling what to copy and the mechanisms
that made the copy be linked in some way--I am assuming that they
would have to be somehow linked.
It is more from an ALife point of view--kind of like how DNA in cells
can produce identical cells--so that the new cell looks exactly like
the old one and can produce even more copys.
Most issues about this kind of copying was found in: Artificial Life
by Christopher Langston, and Godel, Escher, Bach by Douglas
Hofstedter.
I know it must involve some kind of resursion, or introspection and a
lot of symbolic processing. It also must involve simple rules that can
preform complex tasks--what is called Chaos Theroy or Complexity by
Physistics.
From: Pekka P. Pirinen
Subject: Re: How could Lisp be used to program a Turing Copy-Machine.
Date:
Message-ID: <ud6k25dkt.fsf@globalgraphics.com>
·································@hotmail.com (Franz Kafka) writes:
> I am talking about copying in the way that John Van Numann's cellura
> automata produced a copy of its self. A fully functional copy of the
> program that is capible of producing other fully functional copys.
> [...]
>
> The programs that are known to copy like this are: some cellular
> automata systems, Terra programs from Dr. Ray's Terra program,
> Viruses, Worms, and programs that were written to play the game of
> CoreWares.
Actually, that was a program like that. You need to see that this
type of copying always happens on a substrate that supports it: Terra
programs in Terra, viruses in the OS, and Lisp programs in a Lisp
implementation. Kent's program will produce a copy of itself (the
same datastructure, not just the source code), if you evaluate it. If
you want it to continuously produce new copies, like your examples,
you need to give it a substrate that supports that. Say:
(defun run-quine (quine)
(run-quine (eval quine)))
If you want multiple copies, the substrate needs to support
multiprocessing, so you can run the copy and the original at the same
time. Since there's no standard Lisp interface to MP, I won't bother;
I'm sure you can work that one out.
> The thing I am intrested in is: how a program could produce an exact
> copy of itself? where would it store the template telling what needed
> to be made? Would the template telling what to copy and the mechanisms
> that made the copy be linked in some way
Kent's flourishes somewhat obscured the logic of the program. Most
quines follow this pattern, where the template is used twice: to build
the "frame" of the new copy, and to place a copy of the template in
the frame,
(let ((template '`(let ((template ',template)) ,template)))
`(let ((template ',template)) ,template))
and the frame of the program is just an expression that uses the copy
of the template as a parameter to build a program that has this form.
(This is a recursive definition, but it has fixed points in most
computing systems.)
> It is more from an ALife point of view--kind of like how DNA in cells
> can produce identical cells--so that the new cell looks exactly like
> the old one and can produce even more copys.
It gets much harder when either the substrate is poor (cells,
automatic or biological), or the replicator has to do something else
than just replicate (biological cells, CoreWars fighters). But
basically self-replication is not complicated at all.
--
Pekka P. Pirinen
(format t ··@?" "(format t ····@?\" ~:*~S)")
From the quine page at:
http://www.nyx.net/~gthompso/quine.htm
CL-USER 10 > ((lambda (x)
(list x (list (quote quote) x)))
(quote
(lambda (x)
(list x (list (quote quote) x)))))
((LAMBDA (X) (LIST X (LIST (QUOTE QUOTE) X))) (QUOTE (LAMBDA (X) (LIST X
(LIST (QUOTE QUOTE) X)))))
CL-USER 11 >
Jeff
Franz Kafka wrote:
> Since in Lisp programs are treated as a data structure--how
> could one code a program that could produce a copy of it self.
>
> I think something like:
>
> (defmacro copy-machine (&body copy-me)
> `(defmacro copy-machine (&body copy-me)
> ,@copy-me ;; or ,copy-me I forget which one
> )
> )
>
> (copy-machine (format t "&A Copy-Machine") ==> ;;should produce
> (defmacro copy-machine (&body copy-me)
> (format t "&A Copy-Machine")
> )
> ;; I know this is a primitive example. I want it to produce an
> ;; exact copy of itself. And, I think this example provides an
> ;; idea about what I am looking for. I want to see an example
> ;; about how to code a GEB-style Copy Machine.
>
> would prove to be a primitive Turing Copy-Machine.
>
> I am intrested in exploring self-replicating code ala Godel, Escher, Bach
> by Dr. Hofstedter.
>
> The above example seems trivial--is their a much better/more elegant
> program, one that might have real world applications.
>
> What, in affect, I want to know is how could I code a Lisp program so that
> it produces a working copy of itself.
>
> I am just intrested in the mechanism of Copying in a self-reproducing machine.
>
> Thanks for any help you can provide me with.
>
> Happy Coding!!!!!
From: Steven M. Haflich
Subject: Re: How could Lisp be used to program a Turing Copy-Machine.
Date:
Message-ID: <3E8DC3D0.2090507@alum.mit.edu>
Here is a different packaging of the same idea as a named function:
(defun self ()
((lambda (x) (list 'defun 'self 'nil (list x (list 'quote x))))
'(lambda (x) (list 'defun 'self 'nil (list x (list 'quote x))))))
I've lost track of the original author.