Since Lisp data structures and Lisp code have the same syntactic
structure, and since the 'eval' command allows data to be treated as
code, and the 'quote' command allows code to be treated as data, Lisp has
the potential to support self-rewriting programs. I have heard people
refer to these, but I've never actually seen one. Could anyone give me a
reference? Has anyone here ever written a self-modifying Lisp program?
I think this is really exciting, and I'd be most grateful if anyone could
tell me more.
...Thanks in advance
--
--== Nicholas James
--== ······@uoguelph.ca
--== http://www.uoguelph.ca/~njames/
In article <··········@ccshst05.cs.uoguelph.ca>, ······@uoguelph.ca (Nick D
James) wrote:
>Since Lisp data structures and Lisp code have the same syntactic
>structure, and since the 'eval' command allows data to be treated as
>code, and the 'quote' command allows code to be treated as data, Lisp has
>the potential to support self-rewriting programs. I have heard people
>refer to these, but I've never actually seen one. Could anyone give me a
>reference? Has anyone here ever written a self-modifying Lisp program?
>I think this is really exciting, and I'd be most grateful if anyone could
>tell me more.
>
this is not such an exotic a thing to do in lisp as you make it sound.
most lisp programmers do this all the time.
when one writes a macro in lisp, for example, one is writing a program
which will manipulate a lisp data structure in the process of it's being
evaluated. so when you use lisp macros in your code (certainly their most
common use), you are using "self-modifying" or perhaps more accurately
self-constructing programs.
i agree it is "really exciting". it is one the distinguishing strengths of
lisp and one of the key things that makes lisp a particularly good language
for building abstractions.
"macro" is perhaps not a good enough label for it. i.e., it is in a
completely different category from "macros" in a language such as C.
--
David A. Duff
The MITRE Corporation
AI Technical Center
703-883-7731
····@mitre.org
In article <··········@ccshst05.cs.uoguelph.ca> ······@uoguelph.ca (Nick D
James) writes:
> Thanks for all the responses! ...
Actually, I don't think we did too good a job on this one. Here's a more
typical example of classic self-modifying code that computes factorials
using caching.
(defun fact (n)
(if (= n 0)
1
(fact-aux n '(1) 1)))
(defun fact-aux (n lst m)
(if (= n 1)
(if (null (cdr lst))
(cadr (rplacd lst (list (* (car lst) m))))
(cadr lst))
(if (null (cdr lst))
(fact-aux (1- n) (cdr (rplacd lst (list (* (car lst) m)))) (1+ m))
(fact-aux (1- n) (cdr lst) (1+ m)))))
Of course, this isn't entirely kosher in Common Lisp, but there's a good
chance your implementation will do the right thing. Here are some results
for Lucid 4.1.1 on my SPARCstation 20:
USER> (load "~/lisp/fact.lisp")
#P"/a/hydra/home/hydra/rar/lisp/fact.lisp"
USER> (progn (fact 1000) (values))
USER> (defun fact (n)(if (= n 0) 1 (fact-aux n '(1) 1)))
FACT
USER> (time (progn (fact 1000) (values)))
Elapsed Real Time = 0.52 seconds
Total Run Time = 0.50 seconds
User Run Time = 0.44 seconds
System Run Time = 0.06 seconds
Process Page Faults = 912
Dynamic Bytes Consed = 919,584
Ephemeral Bytes Consed = 582,040
There were 2 ephemeral GCs
USER> (time (progn (fact 1000) (values)))
Elapsed Real Time = 0.09 seconds
Total Run Time = 0.08 seconds
User Run Time = 0.08 seconds
System Run Time = 0.00 seconds
Process Page Faults = 0
Dynamic Bytes Consed = 0
Ephemeral Bytes Consed = 70,152
USER>
Summing up,
Although this example is trivial it elegantly illustrates why Lisp
is *the* language for artificial intelligence.
-- Ian Mason
but
This technique is similar to the machine language tricks of self-
modifying code and should be used with similar care. The freedom
to hang yourself should not be construed as an invitation to do so,
but again points out the similarities of LISP to machine language
and highlights the differences between LISP and contemporary high-
level languages.
-- John Allen
Ain't Lisp grand!?
-- rar
···@violet.csl.sri.com (Bob Riemenschneider) wrote:
>In article <··········@ccshst05.cs.uoguelph.ca> ······@uoguelph.ca (Nick D
>James) writes:
>
>> Thanks for all the responses! ...
>
>Actually, I don't think we did too good a job on this one. Here's a more
>typical example of classic self-modifying code that computes factorials
>using caching.
>
> (defun fact (n)
> (if (= n 0)
> 1
> (fact-aux n '(1) 1)))
>
> (defun fact-aux (n lst m)
> (if (= n 1)
> (if (null (cdr lst))
> (cadr (rplacd lst (list (* (car lst) m))))
> (cadr lst))
> (if (null (cdr lst))
> (fact-aux (1- n) (cdr (rplacd lst (list (* (car lst) m)))) (1+ m))
> (fact-aux (1- n) (cdr lst) (1+ m)))))
>
>Of course, this isn't entirely kosher in Common Lisp, but there's a good
>chance your implementation will do the right thing. Here are some results
>for Lucid 4.1.1 on my SPARCstation 20:
<snipped>
>Summing up,
>
> Although this example is trivial it elegantly illustrates why Lisp
> is *the* language for artificial intelligence.
>
> -- Ian Mason
>
>but
>
> This technique is similar to the machine language tricks of self-
> modifying code and should be used with similar care. The freedom
> to hang yourself should not be construed as an invitation to do so,
> but again points out the similarities of LISP to machine language
> and highlights the differences between LISP and contemporary high-
> level languages.
>
> -- John Allen
>
>Ain't Lisp grand!?
> -- rar
Confirmed!
This example puzzled me to try it in the simpliest of the simple lisps:
AutoLISP (used in AutoCAD)
Code follows:
;;; SELF-MOD.LSP
;;; example for self-modifying code within AutoLISP
;;; works only with simple lisps which store functions as lambda lists
;;; This is the normal recursive definition of the factorial
;;; its simple but inefficient, because it doesn't store intermediate
results
(defun fact-simple (n)
(cond ((zerop n ) 1)
(T (* n (fact-simple (1- n))))))
;;; therefore we cache previously calculated results in the function
;;; itself
;;;
;;; (fact 1) -> 1
;;; creates:
;;; (defun fact (n)
;;; (cond ((zerop n) 1)
;;; ((= n 1) 1)
;;; (T .. (* n (fact (1- n))))))
;;;
;;; (fact 4) -> 24
;;; creates:
;;; (defun fact (n)
;;; (cond ((zerop n) 1)
;;; ((= n 1) 1)
;;; ((= n 4) 24)
;;; (T .. (* n (fact (1- n))))))
;;;
;;; fact: ((n) (cond ((zerop n) 1) .. (T .. (* n (fac (1- n)))))))
;;; car cadr cdadr (last (cdadr fact))
(defun fact (n / old result)
(cond ((zerop n) 1)
(T
(setq old fact)
(setq fact (list '(n)
(cons 'cond
(append (butlast (cdadr old))
(list (list (list '= 'n n)
(setq result (* n (fact (1- n))))))
(list (last (cdadr old)))))
))
result
)
)
)
;;; helper functions for list manipulation
;;; list without the last
(defun butlast (lst)
(head lst (- (length lst) 2)))
;;; all elements until the including (nth n lst),
;;; (head '(0 1 2 3) 2) -> '(0 1 2)
(defun head (lst n)
(if (not (minusp n))
(cons (car lst) (head (cdr lst) (1- n)))))
---
Fellow comp.lang.lisp'er:
You see, AutoLISP doesn't even provide rplacd nor butlast, but
everything's possible.
The / in the param list for defun should be read as &aux
It stores only the asked results not all intermediates, so the cond list
remains pretty short.
Follow-Up set to comp.cad.autocad
---
Reini Urban, TU Graz, Architecture & X-RAY
<······@sbox.tu-graz.ac.at> http://xarch.tu-graz.ac.at/autocad/
Attention! From: header is garbled on purpose!
(defun tail (l n)
(cond ((zerop n) l)
(t (tail (cdr l) (1- n)))))
In article <··········@ccshst05.cs.uoguelph.ca>,
Nick D James <······@uoguelph.ca> wrote:
>Since Lisp data structures and Lisp code have the same syntactic
>structure, and since the 'eval' command allows data to be treated as
>code, and the 'quote' command allows code to be treated as data, Lisp has
>the potential to support self-rewriting programs. I have heard people
>refer to these, but I've never actually seen one. Could anyone give me a
>reference? Has anyone here ever written a self-modifying Lisp program?
>I think this is really exciting, and I'd be most grateful if anyone could
>tell me more.
While it's possible in principle, it's not commonly done. First of all,
most production Lisp programs are compiled, so the original list structure
of the code is lost. Second, even when running in interpreted mode, the
source list structure may be hidden behind an opaque data type that's used
to represent functions (to hold the environment component of an interpreted
closure, or a trampoline to simplify the implementation of FUNCALL and
APPLY). Finally, there are often clearer ways to accomplish what you might
want to do with self-modifying code by using variables with function values
and/or higher-order functions.
However, here's a way to have a self-modifying program:
(setq *func*
'(lambda (n)
(if (zerop n) 1
(progn (let ((old (first (third (fourth (third *func*))))))
(setf (first (third (fourth (third *func*))))
(if (eq old '*) '+ '*)))
(* n (funcall (coerce *func* 'function) (1- n)))))))
(funcall *func* 10)
This is essentially a factorial-like function. However, before each
recursion it alternates the function between multiplication and addition by
modifying the function name in the list structure (I hope I got the
location right). Strictly speaking, the above code is invalid because it
modifies a constant; it can be made valid by calling COPY-LIST when
initially assigning to *func*.
Here's a way to do it without self-modification:
(defconst PLUS #'+)
(defconst TIMES #'*)
(defvar *operator* TIMES)
(defun funny-factorial (n)
(if (zerop n) 1
(progn (setq *operator* (if (eq operator TIMES) PLUS TIMES))
(funcall *operator* n (funny-factorial (1- n))))))
Much clearer, IMHO.
--
Barry Margolin
BBN Planet, Cambridge, MA
······@bbnplanet.com - Phone (617) 873-3126 - Fax (617) 873-5508
(BBN customers, please call (800) 632-7638 option 1 for support)
In article <··········@ccshst05.cs.uoguelph.ca> ······@uoguelph.ca (Nick D James) writes:
>
> Since Lisp data structures and Lisp code have the same syntactic
> structure, and since the 'eval' command allows data to be treated as
> code, and the 'quote' command allows code to be treated as data, Lisp has
> the potential to support self-rewriting programs. I have heard people
> refer to these, but I've never actually seen one. Could anyone give me a
> reference? Has anyone here ever written a self-modifying Lisp program?
> I think this is really exciting, and I'd be most grateful if anyone could
> tell me more.
>
There was a fad several years ago called "core wars". I don't know if there
are still people doing this or not. The idea was to write an assembly
language program that modified itself and other parts of memory. For
example it could write itself to another part of memory and then execute
itself there. A game was made out of this by having two such programs start
at the same time in effect. The program that was clever enough to survive
the other programs memory writes would not break and hence was declared the
victor.
I suspect there is some science to self modifying programs, but I don't know
of any. Maybe somebody else does and could speak up.
You are right, it is easy to write self modifying Lisp programs. For
example the following should work
(setq /a
'(lambda (x)
(print (length x))
(setq /a (list* (first x) (second x) (third x) (third x) (cdddr x)))
(funcall x /a)))
(funcall /a /a)
Its output is probably as exciting as watching paint dry. One challenge
would be to write a more interesting self modifying program.
If this coincidently happens to be an answer for some students' exercise, I
recommend modifying the above program a bit so that all students don't have
the same answer.
--
William P. Vrotney - ·······@netcom.com
Nick D James (······@uoguelph.ca) wrote:
: Since Lisp data structures and Lisp code have the same syntactic
: structure, and since the 'eval' command allows data to be treated as
: code, and the 'quote' command allows code to be treated as data, Lisp has
: the potential to support self-rewriting programs. I have heard people
: refer to these, but I've never actually seen one. Could anyone give me a
: reference? Has anyone here ever written a self-modifying Lisp program?
: I think this is really exciting, and I'd be most grateful if anyone could
: tell me more.
That is my "self-modifying" code. It works in MCL 3.0.
(defun foo (new)
(let ((old #1= '(nil)))
(prog1
(first old)
(setf (first #1#) new))))
But it is really bad code, because of modifying _constants_, which should
(and could) result in errors. Especially on Systems with MP.
Forget about writing self-modifying code
CU Christoph
--
Christoph Oechslein 09367/7477
Untere Weinbergstr. 20 97273 Kuernach
Thanks for all the responses! I can see why it is dangerous to write
such code, but I am interested in it only as a curiosity. I didn't know
that macros were different in Lisp than elsewhere. And, no, it's not
part of an assignment. I just finished an introductory course in AI, and
learned a little bit of Lisp there. I had read about self-modifying lisp
programs in Douglas Hofstadter books long before I took the course. The
course rekindled my interest. Thanks again for all the responses and
examples.
--
--== Nicholas James
--== ······@uoguelph.ca
--== http://www.uoguelph.ca/~njames/
One use of self-modifying functions is to provide for learning without
introducing data structures outside the function. If some function takes
a long time to execute, always returns the same result when called with
the same arguments, and is expected to be called often with the same
arguments, it may be useful to learn what the result is for each
frequently used set of arguments. This learning can be stored inside
the function by having the function modify itself each time it is
called with a new set of arguments.
Here is a simple example which computes the square of a number.
The example has been fully tested in Allegro Common Lisp.
The learner_square function takes only one argument but can be modified
readily to use more than one. When learner_square is first defined, the
middle of the lambda_list is:
(COND (NIL)
(T (LET* # # # RESULT)))
When learner_square is called with x = 3, it returns 9 and redefines
itself so now the middle of the lambda_list is:
(COND (NIL)
((EQUAL X 3) 9)
(T (LET* # # # RESULT)))
If learner_square is ever called again with x=3, 9 is returned from
the cond without recomputing the result and without the function
redefining itself.
If learner_square is called with x = -7, it returns 49 and redefines
itself so now the middle of the lambda_list is:
(COND (NIL)
((EQUAL X -7) 49)
((EQUAL X 3) 9)
(T (LET* # # # RESULT)))
So now it will return the answer without having to calculate or redefine
itself if it is called with x=3 or x=-7.
(defun learner_square (x)
(cond (nil) ; The (nil) is just a placeholder
(t
(let* ((result (* x x))
(lambda_list (function-lambda-expression
(symbol-function 'learner_square)))
(arguments (cadr lambda_list))
(body (caddr (caddr lambda_list)))
(answers (cdr body)))
(rplacd answers
(cons (list (list 'equal 'x x) result)
(cdr answers)))
(eval `(defun learner_square ,arguments ,body))
result))))
This function was a lot simpler to write in older versions of Lisp.
Common Lisp makes it a big deal to get the lambda list defining a
function. Bring back getd.
From: David Place
Subject: Re: Self-Modifying Lisp Programs?
Date:
Message-ID: <32AEBDE6.14BF@entuit.com>
Nick D James wrote:
>
> Since Lisp data structures and Lisp code have the same syntactic
> structure, and since the 'eval' command allows data to be treated as
> code, and the 'quote' command allows code to be treated as data, Lisp has
> the potential to support self-rewriting programs. I have heard people
> refer to these, but I've never actually seen one. Could anyone give me a
> reference? Has anyone here ever written a self-modifying Lisp program?
> I think this is really exciting, and I'd be most grateful if anyone could
> tell me more.
>
> ...Thanks in advance
>
I'd be interested to know why you think self-modifying programs
are exciting. What will they do that is better or different?
--
David F. Place
President -- Enhanced Intuition, Inc.
·············@entuit.com
In article <·············@entuit.com>, ······@entuit.com wrote:
> Nick D James wrote:
> >
> > Since Lisp data structures and Lisp code have the same syntactic
> > structure, and since the 'eval' command allows data to be treated as
> > code, and the 'quote' command allows code to be treated as data, Lisp has
> > the potential to support self-rewriting programs. I have heard people
> > refer to these, but I've never actually seen one. Could anyone give me a
> > reference? Has anyone here ever written a self-modifying Lisp program?
> > I think this is really exciting, and I'd be most grateful if anyone could
> > tell me more.
> >
> > ...Thanks in advance
> >
>
> I'd be interested to know why you think self-modifying programs
> are exciting. What will they do that is better or different?
>
> --
> David F. Place
> President -- Enhanced Intuition, Inc.
> ·············@entuit.com
I recall that one of the research principals at the CYC project at MCC had
done some early research (Sorry, I can't find the name, or the source...)
that involved a LISP program that added code to itself. The added code
represented a new heuristic that the program had "discovered" in it's quest
to find new and interesting things in some domain such as the real numbers.
The new code was not particularly good code, nor was the intent very clear,
but the code worked, and did something that was not in the origonal
program. In particular, the program "discovered" prime numbers, then went
to investigate anti-primes -- highly composite numbers.
The point of the research was to see if a program could be constructed in
such a way that it could learn and self extend.
All of the programs would get to a certain point and either tear them
selves apart, or simply run out of ideas to explore (so to speak).
So you see, it is an interesting idea, but no small example program would
illustrate *why* you would want to do this.
No, I haven't seen the program -- but I'd like to. It must be a real piece
of work.
--
cul8r
Michael & Bobbi Haynie
········@nauticom.net (Michael Haynie) wrote:
>I recall that one of the research principals at the CYC project at MCC had
>done some early research (Sorry, I can't find the name, or the source...)
>that involved a LISP program that added code to itself. The added code
>represented a new heuristic that the program had "discovered" in it's quest
>to find new and interesting things in some domain such as the real numbers.
>The new code was not particularly good code, nor was the intent very clear,
>but the code worked, and did something that was not in the origonal
>program. In particular, the program "discovered" prime numbers, then went
>to investigate anti-primes -- highly composite numbers.
I believe you're referring to Lenat's program AM (for Automatic
Mathematician). It also "discovered" the Goldbach conjecture.
See:
Lenat, DB and Brown JS 1984
Why AM and Eurisk appear to work
Artificial Intellegence 23:260-94
I don't know if the code is available online - I don't recall seeing
it in any of the "classic AI' collections.
-- steve
Michael Haynie wrote:
>
> In article <·············@entuit.com>, ······@entuit.com wrote:
>
> > Nick D James wrote:
> > >
> > > Since Lisp data structures and Lisp code have the same syntactic
> > > structure, and since the 'eval' command allows data to be treated as
> > > code, and the 'quote' command allows code to be treated as data, Lisp has
> > > the potential to support self-rewriting programs. I have heard people
> > > refer to these, but I've never actually seen one. Could anyone give me a
> > > reference? Has anyone here ever written a self-modifying Lisp program?
> > > I think this is really exciting, and I'd be most grateful if anyone could
> > > tell me more.
> > >
> > > ...Thanks in advance
> > >
> >
> > I'd be interested to know why you think self-modifying programs
> > are exciting. What will they do that is better or different?
> >
> > --
> > David F. Place
> > President -- Enhanced Intuition, Inc.
> > ·············@entuit.com
>
> I recall that one of the research principals at the CYC project at MCC had
> done some early research (Sorry, I can't find the name, or the source...)
> that involved a LISP program that added code to itself. The added code
> represented a new heuristic that the program had "discovered" in it's quest
> to find new and interesting things in some domain such as the real numbers.
> The new code was not particularly good code, nor was the intent very clear,
> but the code worked, and did something that was not in the origonal
> program. In particular, the program "discovered" prime numbers, then went
> to investigate anti-primes -- highly composite numbers.
>
> The point of the research was to see if a program could be constructed in
> such a way that it could learn and self extend.
>
> All of the programs would get to a certain point and either tear them
> selves apart, or simply run out of ideas to explore (so to speak).
>
> So you see, it is an interesting idea, but no small example program would
> illustrate *why* you would want to do this.
>
> No, I haven't seen the program -- but I'd like to. It must be a real piece
> of work.
>
> --
> cul8r
>
> Michael & Bobbi Haynie
Why is this SELF MODIFYING code?
It is not clear to me why any of the above would require any
side-effects to any lisp objects except perhaps using (setf fdefinition)
or (setf gethash). No need to side-effect any list or function objects,
and no need to call EVAL.
I am drawing a distinction between two things:
1. Use of dynamic language features:
Creating function objects at run-time. Examples: the
function-factories of Norvig or the adder function in chapter 7.1.1
of Steele. This is not uncommon practice.
2. Self-modifying code:
Changing a data structure used by either:
-the implementation, to represent a function (either intpreted or
compiled),
or -the application, to represent the source code for a function.
The only example I can think of where this is necessary is in
building trampolines for implementing a Lisp/CLOS system. While I
believe that the learning example COULD be done using self-modifying
code, I believe it is BETTER done using dynamic language features.
In article <···································@pgh.nauticom.net>,
········@nauticom.net (Michael Haynie) wrote:
> In article <·············@entuit.com>, ······@entuit.com wrote:
>
> > Nick D James wrote:
> >
> > I'd be interested to know why you think self-modifying programs
> > are exciting. What will they do that is better or different?
> >
>
> I recall that one of the research principals at the CYC project at MCC had
> done some early research (Sorry, I can't find the name, or the source...)
> that involved a LISP program that added code to itself. The added code
> represented a new heuristic that the program had "discovered" in it's quest
> to find new and interesting things in some domain such as the real numbers.
> The new code was not particularly good code, nor was the intent very clear,
> but the code worked, and did something that was not in the origonal
> program. In particular, the program "discovered" prime numbers, then went
> to investigate anti-primes -- highly composite numbers.
>
fyi, i think the program was eurisko (sp?). i think the author was doug
lenat. i think this work predates the cyc project.
you (and the original poster of the question about self-modifying programs)
may also be interested in checking out work in the area of "genetic
programming". there's been a lot of work in this area over the last
several years, and there are several books on the subject, with john koza
(sp?) being perhaps the most visible author. at least some of the work
that i know about has involved looking at evolving little lisp (or
lisp-like) programs.
--
David Duff
MITRE Corporation AI Technical Center
McLean, Virginia USA
In article <·············@cme.nist.gov> Tom Kramer <······@cme.nist.gov> writes:
One use of self-modifying functions is to provide for learning without
introducing data structures outside the function. If some function takes
a long time to execute, always returns the same result when called with
the same arguments, and is expected to be called often with the same
arguments, it may be useful to learn what the result is for each
frequently used set of arguments. This learning can be stored inside
the function by having the function modify itself each time it is
called with a new set of arguments.
Here is a simple example which computes the square of a number.
This function was a lot simpler to write in older versions of Lisp.
Common Lisp makes it a big deal to get the lambda list defining a
function. Bring back getd.
[...]
Common Lisp makes it easy to do something like this:
(defun memoize (fn)
(let ((cache (make-hash-table :test #'equal)))
#'(lambda (&rest args)
(multiple-value-bind (val found?) (gethash args cache)
(if found?
val
(setf (gethash args cache) (apply fn args)))))))
So, one can do:
(defun fun (x y) (list y x))
(setf (symbol-function 'fun) (memoize #'fun))
When (FUN 52 13) is evaluated the first time, LIST is called, but
on every subsequent evaluation, the value is taken from the cache.
Actually, MEMOIZE creates self-modifying closures (the code stays
intact, of course).
rthappe
Nick D James (······@uoguelph.ca) writes:
> Since Lisp data structures and Lisp code have the same syntactic
> structure, and since the 'eval' command allows data to be treated as
> code, and the 'quote' command allows code to be treated as data, Lisp has
> the potential to support self-rewriting programs. I have heard people
> refer to these, but I've never actually seen one. Could anyone give me a
> reference? Has anyone here ever written a self-modifying Lisp program?
> I think this is really exciting, and I'd be most grateful if anyone could
> tell me more.
>
> ...Thanks in advance
>
> --
> --== Nicholas James
> --== ······@uoguelph.ca
> --== http://www.uoguelph.ca/~njames/
I'm just starting out in the LISP arena, migrating from the TCL world. In
response to your question - not LISP, but I have created self-modifying
TCL code to generate "n"-forking if-elseif-else trees in variables for
execution. From what I understand about LISP at this point in time, it
would not be unrealistic to see self-modifying LISP code.
Good Luck...
--
===================================================================
"I couldn't have put it into words then, I needed a new mystery."
- John Fowles, The MAGUS.
===================================================================