printing recursive objects?

Tony Kanawati <ontos!>
Tue, 4 May 1993 16:23:30 GMT

          From comp.compilers

Related articles
printing recursive objects? (Paul Haahr) (1993-05-03)
Re: printing recursive objects? (John Lacey) (1993-05-04)
printing recursive objects? ontos! (Tony Kanawati) (1993-05-04)
printing recursive objects? (1993-05-05)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Tony Kanawati <ontos!>
X-Organization: Ontos, Inc.; Burlington, Mass; USA
Keywords: Lisp
Organization: Compilers Central
Date: Tue, 4 May 1993 16:23:30 GMT
X-Phone: (617) 272-7110 x328

> Given an arbitrary recursive structure, say a lisp sexpr, how do you print
> it in a form that can be read back to create the same structure?

With pure data and a Lisp/Scheme READ/WRITE procedures, it is not possible
to perform your task; because you cannot print nor read *REFERENCES*.

However, if you really need to do this, you can create procedures that
read and write such structures using the following concepts:

1. Traverse the recursive circular structure, as a graph, and associate
      each object with a unique number. This can be done using the eq?
      predicate for identity testing, which will also make sure that you do
      not loop forever.

*. Now, you should have a list of all the unique objects in your structure.

2. Each object should be one of:

      a. Atom, or
      b. cons ref1 ref2
      c. vector of size N, contents: ref1 ... refN
      d. ...

With a multi-pass read/write policy, you will be able to construct the
objects, and then link them together, and recreate the original

Algorithms that come to mind: Graph traversal (depth first, breadth
first), topological sorting (may simplify the construction sequence).
Antoun (Tony) Kanawati | ONTOS, Inc., 3 Burlington Woods | Burlington, MA 01803, USA
uunet!uupsi!ontos!tonyk | (617) 272-8101 (Fax)
(800) 388-7110 x328 (Direct) | (617) 272-7110 x328 (Front desk)

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.