Re: can s-exprs represent a graph without eval?

[Guy Steele - Sun Microsystems Labs <address@hidden>]

   Date: Thu, 19 Jun 2003 15:30:56 -0400
   Subject: Re: can s-exprs represent a graph without eval?
   From: Geoffrey Knauth <geoff@knauth.org>
   To: ll1-discuss@ai.mit.edu
   
   I've never seen this, it's certainly interesting, but how to you detect 
   that you're just going around in circles?
   (Let's say someone passes you v and you aren't suspecting v has this 
   structure.)

Well, which is it?  If you aren't suspecting,
you aren't going to conduct the test that
might reveal it.

Sometimes an circular structure can be used to "advantage".
Consider this bit of code:

  (mapcar #'+ x '#1=(1 -1))

If x is (1 4 7 10), the result will be (2 3 8 9).

Does this puzzle you?  You get 1 point.
Does this delight you?  You get 5 points.
Does this nauseate you?  You get 10 points.

IIRC, Fred Blair, when he was working on IBM 370 Lisp back
in the 1970s, actually put the analysis into the compiler
to make it understand circular list structure in the code.
So it would produce the same machine code for

(prog (x)
      (setq x 3)
   #1=(cond ((equal x 0) . #2#)
            ((oddp x) (print x))
            (t (setq x (- x 1)) . #1#))
      (setq x (+ x 3))
   #2=(cond ((equal x 5) (return)))
      . #1#))

and

(prog (x)
      (setq x 3)
   A  (cond ((equal x 0) (go B))
            ((oddp x) (print x))
            (t (setq x (- x 1)) (go A)))
      (setq x (+ x 3))
   B  (cond ((equal x 5) (return)))
      (go A)))

the point being the the first version would run a little faster
when INTERPRETED.  Bleah.  De gustibus non disputandum.

--Guy Steele