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

[Neel Krishnaswami <address@hidden>]

James McCartney writes:
> 
> S-exprs can represent trees of data easily. I am wondering if
> s-exprs, or some other syntax, can be used to represent a graph just
> on reading, without eval.
> 
> I assume something simple could be done where you have a syntax to
> bind symbols, and then access their bindings. Does Lisp do this
> already? or is graph data just written as Lisp code and eval'ed?

Yes, it can. The basic idea is that you can look at a graph as a tree
with shared substructure. So you basically need a literal syntax for
naming and referring to particular subtrees.

So the infinite list (3 3 3 3 3 ...), which might be created with the
following expression:

  (define infinite-list (let ((lst (cons 3 'null)))
                           (set-cdr! lst lst)
                           lst))

can also be written as (using the Scheme SRFI-38 notation, which I
think is also used by Common Lisp):

  (define infinite-list #1=(3 . #1#))

#1= names the subtree, and #1# refers to it. 

Hope this helps. 

-- 
Neel Krishnaswami
neelk@alum.mit.edu