There has been some discussion in comp.theory on self-modifying
programs (and languages that let one pull off this trick). Here's
another twist: a self-infecting code, a function that infects
(eventually, itself) with every call, kind of what computer virus
does. I came across this unusual (well, at least for me) behavior when
trying to implement rings, that is, circular lists, in a strict
LISP. Just for the exercise. By strict LISP I mean LISP with no
variables, no progn(), no cheating with the internal list
representation, etc, just a pure, functional subset of LISP.

Ring is an example of an "infinite" data structure, in a sense that,
unlike a finite list, there is always a predecessor and successor to
any element in the ring. Therefore, the ring is implemented
"recursively", in terms of links. A link is made of a link value and a
function that, when called, generates another link. Function
'make-ring' already shows self-infecting traits, in that it generates
a data structure and inserts itself as a part of it.  Here is how a
ring of three elements looks like

Eval: (make-ring '(1 2 3))
Result: (1 (lambda nil (list 2 (function
(lambda nil (list 3 (function (lambda nil (make-ring (list 1 2 3))))))))))

The most curious things is the function 'reverse-order'. Instead of
reshuffling the entire ring (which make take "infinite" amount of time
-:) it modifies only one link. But it also inserts itself into the
"functional" part of the link. Whenever you want to get another
element of the reversed list, the function infects the next link,
etc. So, it keeps the body of the "host" intact but modifies the "DNA"
slightly. And every instance of the "DNA" replication just passes the
infection on and on, and on.

The full code is archived in comp.sources.misc. The archive consists
of a README file (which you're reading) and the virus.el file. The
latter is the snapshot of a Emacs buffer in the Lisp-Interaction
mode. In this node, one can enter expressions and evaluate them.  So,
you'll see expressions and the result of their evaluation right under.
The program was created under Emacs-18.58 and also works on
Emacs-19.xx.

Though it may look like the code is specific to Emacs, it's not; it's
just the regular lisp (but I happen to use Emacs as a lisp
interpreter).  The code is so elementary it would run (maybe without a
single change) on any lisp interpreter and probably on scheme.

>>>>> virus.el file:

;------------------------------------------------------------------------
;			Messing with rings - cyclic lists
;
; A link of a ring is a list such that
; (car link) is current elem
; (car (cdr link)) is a function that returns the next link

(defun Rcar (R)				; Car of the ring R
  (car R))
Rcar

(defun Rcdr (R)				; Cdr of ring R, gives the next link
  (funcall (car (cdr R))))
Rcdr

; Turn a list into the ring
; Note that we use the same trick to create a function body on the
; fly and then make it a function by 'eval'-ing it

; It's going to be absolutely incomprehensible. You'd better do
; (make-ring '(1 2 3)) to get an idea what's cookin' in here

(defun make-ring (L)			
  (defun quote-ring (L)
    (list 'function (list 'lambda '() (list 'make-ring (cons 'list L)))))
  (defun add-elem (L orig-L Res-list)
    (if (cdr L)
	(list 'list (car L) (list 'function
	      (list 'lambda nil (add-elem (cdr L) orig-L Res-list))))
	(list 'list (car L) (quote-ring orig-L))
	))
  (eval (add-elem L L nil)))
make-ring

(setq fg (make-ring '(1 2 3)))
(1 (lambda nil (list 2 (function (lambda nil (list 3 (function (lambda nil (make-ring (list 1 2 3))))))))))


; Some ring-manipulation functions

(defun nth (n R)			; n-th elem of R, numbering starts
  (if (= n 0)				; from 0
      (Rcar R)
    (nth (1- n) (Rcdr R))))
nth

(nth 0 fg)
1

(nth 1 fg)
2
					; Write 'no-elem' consecutive ring
					; elements into a list
(defun ring-to-list (no-elems R)
  (if (< no-elems 0)
      nil
    (append (list (Rcar R)) (ring-to-list (1- no-elems) (Rcdr R)))))
ring-to-list

(ring-to-list 7 fg)
(1 2 3 1 2 3 1 2)

; Rotate a ring to the left
(defun left-rotate (R) (Rcdr R))
left-rotate

(ring-to-list 7 (left-rotate fg))
(2 3 1 2 3 1 2 3)

(ring-to-list 7 (left-rotate (left-rotate fg)))
(3 1 2 3 1 2 3 1)


; Rotation to the right
; Note that it's impossible to find how many elements a ring contains
; (unless we resort to cheating: messing with the internal ring
; representation). Indeed, if we have only Rcar and Rcdr, there is no
; way to tell the head and the tail apart.
; Watching for periodicity doesn't help either. Really, for any N>0
; consider a ring with N ones followed by a zero. We need to scan up to
; N+1 elems of the ring to avoid a mistake of thinking that the ring
; consists of only one 1. 
; Anyway, it's possible to define a function right-rotate that returns
; the right-rotated ring without trying to find the length of the
; ring. But we need to know the max size of any ring.

(defconst max-ring-size 15 "Maximum 'size' of any ring")
max-ring-size

					; Check to see are two rings the
					; same
(defun rings-the-same-p (R1 R2)		; They are considered the same if they
  (defun the-same-up-to-n (n R1 R2)	; have up to max-ring-size
    (or					; matching elements
     (= 0 n)
     (and
      (eq (Rcar R1) (Rcar R2))
      (the-same-up-to-n (1- n) (Rcdr R1) (Rcdr R2)))))
  (the-same-up-to-n max-ring-size R1 R2))
rings-the-same-p

(rings-the-same-p fg fg)
t

(rings-the-same-p (Rcdr fg) fg)
nil

					; Rotate right. We take advantage
					; of the fact that rotating the
					; ring to the left long enough
					; would give a right-rotated ring
					; (left-rotate (right-rotate R)) = R
(defun right-rotate (R)
  (defun right-rotated-p (R1 R2)	; if R1 is right-rotated R2
    (rings-the-same-p (left-rotate R1) R2))
  (defun try-rotate (R1 R2)
    (let					
	((candidate (left-rotate R1)))
      (if (right-rotated-p candidate R2)
	candidate
	(try-rotate candidate R2))))
  (try-rotate R R))
right-rotate

(ring-to-list 7 (right-rotate fg))
(3 1 2 3 1 2 3 1)

(ring-to-list 7 (right-rotate (right-rotate fg)))
(2 3 1 2 3 1 2 3)


					; Doesn't it look like a virus
					; propagation in the computer
					; system?
(defun reverse-order (R)
  (list (Rcar R) (list 'lambda '() 
		       (list 'reverse-order (list 'quote (right-rotate R))))))
reverse-order

(reverse-order fg)
(1 (lambda nil (reverse-order (quote (3 (lambda nil (make-ring (list 1 2 3))))))))

(ring-to-list 7 fg)
(1 2 3 1 2 3 1 2)

(ring-to-list 7 (reverse-order fg))
(1 3 2 1 3 2 1 3)

(ring-to-list 13 (make-ring '(1 2 3 4 5)))
(1 2 3 4 5 1 2 3 4 5 1 2 3 4)

(ring-to-list 13 (reverse-order (make-ring '(1 2 3 4 5))))
(1 5 4 3 2 1 5 4 3 2 1 5 4 3)