printing recursive objects?

> 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
topologies.


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
tonyk@ontos.com | Burlington, MA 01803, USA
uunet!uupsi!ontos!tonyk | (617) 272-8101 (Fax)
(800) 388-7110 x328 (Direct) | (617) 272-7110 x328 (Front desk)
--

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