{Begin SubSec Printing Reentrant and Circular List Structures}
{Title Printing Reentrant and Circular List Structures}
{Text
{index *BEGIN* printing circular lists}
{Begin SubSec CIRCLPRINT}
{Title CIRCLPRINT}
{Text
{note CIRCLPRINT was written by P. C. Jackson.}
{it
Note: CIRCLPRINT is a LispUsers package contained on the file {lisp CIRCLPRINT.DCOM}.
}
{fn HPRINT} ({PageRef Fn HPRINT}) is designed primarily for dumping circular or reentrant list structures (as well as other data structures for which {fn READ} is not an inverse of {fn PRINT}) so that they can be read back in by Interlisp. The CIRCLPRINT package is designed for printing circular or reentrant structures so that the user can look at them and understand them.
A reentrant list structure is one that contains more than one occurrence of the same ({fn EQ}) structure. For example, {fn TCONC} ({PageRef Fn TCONC}) makes uses of reentrant list structure so that it does not have to search for the end of the list each time it is called. Thus, if {lisp X} is a list of 3 elements, {lisp (A B C)}, being constructed by {fn TCONC}, the reentrant list structure used by {fn TCONC} for this purpose is:
{lispcode
-----
|.|.|-----------------|
----- |
| |
V V
----- ----- -----
|A|.|---->|B|.|---->|C|/|
----- ----- -----}
This structure would be printed by {fn PRINT} as {lisp ((A B C) C)}. Note that {fn PRINT} would produce the same output for the non-reentrant structure:
{lispcode
----- -----
|.|.|---->|C|/|
----- -----
|
V
----- ----- -----
|A|.|---->|B|.|---->|C|/|
----- ----- -----}
In other words, {fn PRINT} does not indicate the fact that portions of the structure in the first figure are identical. Similarly, if {fn PRINT} is applied to a circular list structure (a special type of reentrant structure) it will never terminate.
For example, if {fn PRINT} is called on the structure:
{lispcode
. -----
|--->|.|/|
| -----
| |
|-----|}
it will print an endless sequence of left parentheses, and if applied to:
{lispcode
. -----
|--->|A|.|----|
| ----- |
| |
|-------------|}
will print a left parenthesis followed by an endless sequence of {lisp A}'s.
The function {index CIRCLPRINT FN}{fn CIRCLPRINT} described below produces output that will exactly describe the structure of any circular or reentrant list structure. This output may be in either single or double-line formats. Below are a few examples of the expressions that {index CIRCLPRINT FN}{fn CIRCLPRINT} would produce to describe the structures discussed above.
First Figure, single line:
{lispcode
((A B *1* C) {bracket 1})}
First Figure, double-line:
{lispcode
((A B C) {bracket 1})
1}
Third Figure, single-line:
{lispcode
(*1* {bracket 1})}
Third Figure, double-line:
{lispcode
({bracket 1})
1}
Forth Figure, single-line:
{lispcode
(*1* A . {bracket 1})}
Forth Figure, double-line:
{lispcode
(A . {bracket 1})
1}
The more complex structure:
{lispcode
. -----
|-------->|.|.|--------------------------|
| ----- |
| | |
| V V
| ----- ----- ----- -----
| |--->|.|.|---->|.|.|---->|A|.|---->|B|.|
| | ----- ----- ----- -----
| | | |↑ |
| |-----| ||-------------------|
| |
|--------------------|}
is printed as follows:
Single-line:
{lispcode
(*2* (*1* {bracket 1} *3* {bracket 2} A *4* B . {bracket 3}) . {bracket 4})}
Double-line:
{lispcode
(({bracket 1} {bracket 2} A B . {bracket 3}) . {bracket 4})
21 3 4}
In both formats, the reentrant nodes in the list structure are labeled by numbers. (A reentrant node is one that has two or more pointers coming into it.)
In the single-line format, the label is printed between asterisks at the beginning of the node (list or tail) that it identifies. In the double-line format, the label is printed below the beginning of the node it identifies. An occurrence of a reentrant node that has already been identified is indicated by printing its label in brackets.
{FnDef {FnName CIRCLPRINT} {FnArgs LIST PRINTFLG RLKNT}
{Text
Prints an expression describing {arg LIST}. If {arg PRINTFLG}={lisp NIL}, double-line format is used, otherwise single-line format. {fn CIRCLPRINT} first calls {fn CIRCLMARK}, and then calls either {fn RLPRIN1} (if {arg PRINTFLG}={lisp T}) or {fn RLPRIN2} (if {arg PRINTFLG}={lisp NIL}). Finally, {fn RLRESTORE} is called to restore {arg LIST} to its unmarked state.
Returns {arg LIST}.
}}
{FnDef {FnName CIRCLMARK} {FnArgs LIST RLKNT}
{Text
Marks each reentrant node in {arg LIST} with a unique number,
starting at {arg RLKNT}+1 (or 1, if {arg RLKNT} is {lisp NIL}). Value is (new) {arg RLKNT}.
Marking {arg LIST} physically alters it. However, the marking is performed undoably. In addition, {arg LIST} can always be restored by specifically
calling {fn RLRESTORE}.
}}
{FnDef {FnName RLPRIN1} {FnArgs LIST}
{Text
Prints an expression describing {arg LIST} in the single-line format. Does not restore {arg LIST} to its un{fn CIRCLMARK}ed state. {arg LIST} must previously have been {fn CIRCLMARK}ed or an error is generated.
}}
{FnDef {FnName RLPRIN2} {FnArgs LIST}
{Text
Same as {fn RLPRIN1}, except that the expression describing {arg LIST}
is printed in the double-line format.
}}
{FnDef {FnName RLRESTORE} {FnArgs LIST}
{Text
Physically restores list to its original, unmarked state.
}}
Note that the user can mark and print several structures which together share common substructures, e.g., several property lists, by making several calls to {fn CIRCLMARK}, followed by calls to {fn RLPRIN1} or {fn RLPRIN2}, and finally to {fn RLRESTORE}.{note how??}
{FnDef {FnName CIRCLMAKER} {FnArgs LIST}
{Text
{arg LIST} may contain labels and references following the convention used by {fn CIRCLPRINT} for printing reentrant structures in single line format, e.g., {lisp (*1* . {bracket 1})}. {fn CIRCLMAKER} performs the necessary {fn RPLACA}'s and {fn RPLACD}'s to make {arg LIST} correspond to the indicated structure. Value is (altered) {arg LIST}.
}}
{FnDef {FnName CIRCLMAKER1} {FnArgs LIST}
{Text
Does the work for {fn CIRCLMAKER}. Uses free variables {var LABELST}{index LABELST Var} and {var REFLST}.{index REFLST Var} {var LABELST} is a list of dotted pairs of labels and corresponding nodes. {var REFLST} is a list of nodes containing references to labels not yet seen. {fn CIRCLMAKER} operates by initializing {var LABELST} and {var REFLST} to {lisp NIL}, and then calling {fn CIRCLMAKER1}. It generates an error if {var REFLST} is not NIL when {fn CIRCLMAKER1} returns. The user can call {fn CIRCLMAKER1} directly to "connect up" several structures that share common substructures, e.g., several property lists.
}}
}{End SubSec CIRCLPRINT}
{Begin SubSec PRINTL}
{Title PRINTL}
{Text
{note PRINTL was written by M. J. Kay.}
{it
Note: PRINTL is a LispUsers package contained on the file {lisp PRINTL.COM}.
}
{note this needs to be explained better}
The {fn PRINTL} package uses a different scheme than {fn CIRCLPRINT} to present circular structures in an easily readable format. {fn PRINTL} uses indentation a la {fn PRETTYPRINT} to make it easier for the user to see the nesting of list structure, and prints index numbers for the beginning and ends of
expressions so that the user can find what is referred back to easily. Note that {fn PRINTL} does not provide an output format which can be read back in to reconstruct the original list structure; it is intended primarily as a debugging aid.
The following example illustrates the use of {fn PRINTL}:
{lispcode
32←(PRINTL (NCONC (SETQQ X (A B C D)) X))
1: (A B C D . {bracket 1}) :1
NIL
33←(PRINTL (LIST X (CDR X) (CDDR X) (CDDDR X]
1: ((A B C D . {bracket 2}) {bracket 3} {bracket 4} {bracket 5}) :1
NIL
34←(PRINTL (LIST X (CONS 'P (CDR X)) (CONS 'Q (CDDR X))
(CONS 'R (CDDDR X]
1: ((A B C D . {bracket 2}) :2
6: (P . {bracket 3}) :6
7: (Q . {bracket 4}) :7
8: (R . {bracket 5})) :1
NIL
35←USE LIST FOR CONS
1: ((A B C D . {bracket 2}) :2
6: (P {bracket 3}) :6
8: (Q {bracket 4}) :8
10 (R {bracket 5})) :1
NIL}
{fn PRINTL} uses the following algorithm: Each list node that is printed ({fn CAR} or {fn CDR}) is assigned a number. The second and subsequent appearences of this list node are represented simply by printing the number corresponding to the node in {lisp {bracket}} brackets. Every line on which the representation of a list begins shows the corresponding number of the {it first} such list, i.e. this number corresponds to the first open parenthesis on the line. Similarly, to the right of every line on which a list ends is printed the number that corresponds to the {it last} close parenthesis on the line. The numbers for those list nodes which do not correspond to the first open parentheses or the last close parentheses on a line can be obtained by simply counting from the last numbered parenthesis. For example, in the line
{lispcode
1: ((A B C D . {bracket 2}) {bracket 3} {bracket 4} {bracket 5}) :1}
2 is {lisp (A B C D)}, 3 is {lisp (B C D)}, 4 is {lisp (C D)}, and 5 is {lisp (D)}.
{FnDef {FnName PRINTL} {FnArgs ITEM DEPTH LMARG RMARG FILE}
{Text
Prints an item which is known to be, or suspected of being a circular list structure, in the form described above. {arg DEPTH} controls the depth of recursion in the {fn CAR} direction and defaults to the value of the varible {var PRINTDEPTH} (initially 4). Elements of the structure at this depth are printed as "{lisp {bracket --}}".
{arg LMARG} is the left margin. If {lisp NIL}, {arg LMARG} defaults to {lisp (POSITION {arg FILE})}. {arg RMARG} is the position at which the righthand column of numbers will be printed. If {lisp NIL}, {arg RMARG} defaults to {lisp (LINELENGTH)}-5.
Printing is to {arg FILE}, which is opened if necessary.
}}
{VarDef {Name PRINTDEPTH}
{Text
The default {arg DEPTH} argument for {fn PRINTL}. Initially 4.
}}
{Def {Type PACom}
{Name PRNTL} {Args ARGS}
{Text
Programmers Assistant command that performs {lisp (PRINTL . {arg ARGS})} provided {lisp (CAR {arg ARGS})} is not a number. If it is, or if {arg ARGS}={lisp NIL}, the item to be printed is taken to be the last event on the history list with a non-null value. Thus {lisp PRNTL 6} will print the last non-null value with {arg DEPTH}=6.
}}
}{End SubSec PRINTL}
{index *END* printing circular lists}
}{End SubSec Printing Reentrant and Circular List Structures}