4

In a Lisp dialect, I've implemented ANSI-CL-like support for printing objects such that their circular and shared structure is encoded. This is enabled by the special variable *print-circle*. Similarly to ANSI-CL, I have it working when it traverses objects that have custom print methods. But there are tricky corner cases.

For reference, let's make this diagram. Object X is the thing being printed, and the pyramid underneath it represents the dependent tree of constituent objects: nested lists, and whatever. Object O is a constituent which is an OOP object with a custom print method. When this is invoked, it can print various objects such as objects R and NR. R is reachable through one or more of the slots of object O. Object NR is not reachable that way: the print method pulls it from a global variable or whatever:

                     X
                     |
                    / \
                   /   \
                  /     \
                 /       \
                /         \
               <_________O_>
                         |
                        / print
                     ,-'   `---.
                     |         |
                     R         NR
                     |         |
                    / \       / \
                   <___>     <___>

Now I developed an algorithm which works in two passes. When the printer is called out of the blue to print X (not a recursive call) and circle printing is enabled, it creates a new circle printing context which contains a hash table for cycle detection. Before doing anything else, the function walks the entire graph rooted at X, which reaches O and recurses into R. It then knows all the duplicate objects and cycles, and can proceed to walk the structure and generate the circular notation. It has no knowledge of NR. However, when object O's print method is called, and recurses into the printer to print the object NR, the printer will supplement the hash table by walking the object NR at that point. Everything is cool if NR is self-contained: it can have internal cycles and shared substructure. What we ensure is that the label numbering for the objects occurring in NR doesn't conflict. If X and R use labels 1 through 21, then any labels under NR start at 22.

The troublesome case is this one:

                     X
                     |
                    / \
                   /   Y < ----------.
                  /     \            |
                 /       \           | 
                /         \          |
               <_________O_>         |
                         |           |
                        / print      |
                     ,-'   `---.     |
                     |         |     |
                     R         NR    |
                     |         |     |
                    / \       / \    |
                   <___>     <   >--'

Suppose NR contains a backpointer into the previously traversed structure, either X or R, to some object Y. The algorithm will break down; if that referenced object Y does not appear two or more times in the originally traversed structure, then it was not noted by the algorithm as requiring the special label def/ref notation. It cannot be correctly rendered as a #<n># reference. (If Y did appear two or more times prior to processing NR, then the occurrence of it encountered via NR is just another occurrence that will be rendered correctly. For instance if Y is represented as label 17, it will turn into #17#.) If Y appeared once, though, we can no longer go back and patch the #17= label definition in front of it in the output that we already printed; by the time we call the print method which recurses into NR, prior structure has already been printed.

Good sub-case of bad case:

                     X
                     |
                    / \  rendered as #17=Y
                   /   Y < ----------.
                  /     \            |
                 /       \           |
                /         \          |
               <_________O_>         |
                         |           |
                        / print      |
                     ,-'   `---.     |
                     |         |     |
                     R         NR    |
                     |         |     |
                    / \       / \    |
                   <_Y_>     <__Y>---'
     Rendered as #17#         Also rendered as #17#: lucky!

If the second occurrence of Y under R is missing, then the top Y is just rendered as itself without the #17= label. When printing NR, we therefore cannot render Y as #17#; that would be a dangling label ref. We might render Y as a new object, say number 256: #256=(...) which might recurse into NR again, where the second printing of Y becomes #256#. Or we could recognize the situation and throw an exception: a print method pitched us a curve ball unsupported by *print-circle*.

The question is: is it a requirement in ANSI Common Lisp to handle that case? Can print methods procure absolutely any existing object from the image, pass it to the printer recursively, and must it be handled properly, no matter that it is unrelated to the object O and not reachable through that object's slots?

2

The answer is: yes, but the printer is not required to sweep the whole image, only the objects provided to printing functions.

Nothing forbids the Lisp printer from performing multiple passes or any other technique it can afford.

With multiple passes, the printer could populate per-stream hash tables with the duplicates in the first pass starting with a null stream (e.g. a broadcast-stream with no component streams), stopping recursion on the found duplicates with #n#, then actually print to the destination stream including the #n= markers before the first instance of each duplicate object.

Without multiple passes, the printer could create a special purpose stream which records the position of every printed object to insert #n= markers internally. One thing that can get simpler with this approach is the per-stream circularity bookkeeping. However, column counting would not be accurate.

Pretty printers (more advanced than plain printing) usually use a mix of techniques: multiple passes, where the stream used on each pass is a special purpose one with adjustable size, column, circularity table and all other state it needs, plus either performing a last pass or writing intermediate results into the destination tream.

This has only scratched the surface regarding the Lisp printer, especially a pretty printer. I suggest you search the web for more information, there are a bunch of papers about the subject. Start with CLtL2 §27. Pretty Printing and XP - A Common Lisp Pretty Printing System.

As long as you use write, prin1, princ or format with ~a, ~s or ~w on the same stream inside print-object, the printer will consider any given object for circularity. It doesn't matter if a given object is part of some other object's structure or not. Also, the printer doesn't have to take into account every object in memory, only those that are actually printed.

Essentially, it seems you've duplicated the Lisp printer's behavior regarding duplicates. By not relying on the printer's effort, you cannot actually guarantee that your own #n=/#n# are unique regarding the top-most write operation that initializes the printer's own circularity context.

  • (To clarify, I do not have a printer to rely on; I'm working on a Lisp dialect. I.e I have implemented ANSI-CL-Like circular notation in a non-ANSI-CL Lisp dialect. I am not confined by ANSI CL requirements: but that's a separate consideration from knowing what exactly they are! I should know where my own requirements stand in respect to ANSI CL ones. – Kaz Mar 7 '17 at 3:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.