printing recursive objects?

Tony Kanawati <ontos!tonyk@uu.psi.com>
Tue, 4 May 1993 16:23:30 GMT

          From comp.compilers

Related articles
printing recursive objects? haahr@mv.us.adobe.com (Paul Haahr) (1993-05-03)
Re: printing recursive objects? johnl@cs.indiana.edu (John Lacey) (1993-05-04)
printing recursive objects? ontos!tonyk@uu.psi.com (Tony Kanawati) (1993-05-04)
printing recursive objects? davis@ilog.ilog.fr (1993-05-05)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Tony Kanawati <ontos!tonyk@uu.psi.com>
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
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)
--


Post a followup to this message

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