Þ   briarpig  » mu  » writer

     A typical Lisp environment, whether Scheme or some other Lisp variant, usually has an interactive session of some sort called a repl, standing for read/eval/print loop. The first input phase is done by a reader; the last output phase is done by a writer — often a pretty printer showing tree-shaped structures with nesting revealed by indentation.

     Lisp trees of lists can be reasonably formatted for human consumption (or display) using a pretty printer tuned for some maximum target line length. Any single list that's too long to fit on a single line can be split over multiple lines, with children suitably indented to show nesting.

     To print Lisp syntax code and data in a nice format, Wil currently uses code shown on this page, deriving from a Ygg pretty printer Wil wrote using C++ in the early 90's.

     The writer shown on this page is something of an incomplete prototype still under development. When it's complete, it will serve as a guide for writing new pretty printers in the toy language itself, with greater runtime flexibility. The role of this writer in C++ is more of a bootstrapping scaffold.

     The pretty printer shown here can handle cycle structures without looping infinitely. Cycles and shared structure appear using a Lisp syntax convention defined later.

     This writer uses thorn C++ classes of near generic nature — ypp2dm in the map demo (cf ») plus yno and yoo in the meter demo (cf » and ») — as part of internal state to manage maps and measure content length and line lengths.

     At the time of writing, the reader page is still pending, so code references to constants in class yi2br (in-stream to box reader) are not yet linked to definitions.

     The yM virtual machine api (and associated internal ykMgbv managing addresses of well known constant symbols and objects) won't appear until even later.

     Because Lisp syntax permits nesting of lists, it's more accurate to say tree processing instead of list processing when speaking about Lisp. And when you allow mutation or forward references to make cycles, you can actualy make arbitrary graphs, and not just trees which cannot have cycles.

     By convention, Lisp code and data is shown in tree format, with child nodes indented according to one scheme or another. For example, you can indent to align with another earlier child in a list, or you might instead indent a distance proportional to depth. Either works fine if you're consistent.

     Wil first learned Lisp in college when his boss Mark suggested Wil consider it, since Wil was interested in dataflow systems, and under Lisp, both code and data have the same form. Wil said, "But what does this syntax mean?"

     Mark said, "It's a tree. If you break a line inside a list, the next thing shown on a following line is indented. By convention you align siblings on successive lines to help show they are children of a less indented parent above."

     "That's it?" Wil asked, and Mark nodded. "Cool. The only syntax convention is indented children? Neat."

     So after two minutes, Wil learned all there was to know about basic structure in Lisp syntax. Everything else concerns format of individual tokens for atoms. (The meaning of any list depends on members and their locations.)

     Consider a desired format this writer targets — we need to pick one of several options. (You can also support several, then select one, but the current api aims for fewer options beyond target max line length.) But first let's establish terms used to describe a planned output format.

     The following code fragment is valid Scheme syntax, but it's written in odd style — almost like C in the way closing delimitors are stacked below opening parens. (Note: paren is short for parenthesis — get used to it.)

     Even though verbose, Wil often wrote Ygg code like above in the 90's because because it fit the same style he used when writing C++: it was easier to cut and paste with block shifts using a dumb text editor. Just like in C++, whitespace has no meaning in Lisp beyond breaking tokens. So code above is considered identical to the next expression below:

     The code fragment above is the original, using conventional Scheme style: closing parens appear on the same line as the last member of a preceding list. If you spread the last three closing parens over three lines, under opening parens, you get exactly what was shown earlier. Same thing.

     What else do you see in the code above? If a long expression breaks over multiple lines, by convention the first two children appear on one line if the second child will also fit. Subsequent children align under the second child. Compare this to a near alternative, where a third child simply indents:

     The variation above is only sightly different: it aligns to depth — two spaces per indent — instead of aligning to a previous sibling. Let's name these two different styles:

• sib-aligned » new lines: indent to last sibling
• depth-aligned » new lines: indent by depth

     The second depth-aligned example above was printd by the writer shown on this page. It would be quite easy to support both formats — sib-aligned and depth-aligned — but the code only shows depth-aligned formatting. Wil prefers depth-aligned because it uses less horizontal space.

     Let's look at one more example so you can compare the two styles again. Below is another sample of Scheme code Wil found; it shows the original (partly) sib-aligned style:

     When the expression above is reformatted in depth-aligned format by the writer using a target max line length of 50, you get the output shown below:

     The pretty printer in writer class yb2ow shown on this page aims to write in depth-aligned format as shown above. It still has a couple quirks someplace because Wil wrote all the logic by trial and error, making small changes when an unexpected result appeared in output. Current code still has a few line length related odd effects.

     The max line length targeted by current writer code causes something ugly to occur when nested tree depth pushes minimum indent out close to max line length: line breaks occur constantly after every short expression prints. Output in this case looks like blades of grass mashed over at the tips by a heavy weight represented by the limit.

     What would look better? Well, if a line is deeply indented due to depth, maybe max line length should be locally increased by some amount. This would make max line length relative to depth, in part, with more consistent results: limits would shift rightward as depth increased.

     If Wil was reworking code now instead of writing this page, he might have a min line length as well as a max, so depth plus min would be the effect max line length everywhere when it exceeded global max length.

     Current code counts levels of recursion, to limit maximum nesting handled by a writer, so there exists a maximum depth of structure that can be printed. Limiting stack use is the main purpose; the current limit was arbitrarily chosen and is subject to later reconsideration when the topic of bounding resource usage is addressed again.

     The stack depth limit used now is a stopgap measure picked in the absence of more specific requirements. However, it seems reasonable that a writer of limited purpose might handle no more than hundreds of nesting levels.

     Two mutually recursive internal methods named _wmap() and _wpeel() visit the graph to be printed prior to all writing to find shared structure and cycles. An arbitrary max nesting depth of 512 is imposed by _wmap(). Obviously any other constant can be used instead.

     The current writer class is named yb2ow, which stands for thorn box to out-stream writer. This name is harder to remember than ywriter, but does explain behavior slightly more. The name is actually a slight misnomer because it actually prints any peg and not just any box, so it also prints immediate values as well. (Perhaps it should be named yp2ow, but p for peg or pointer already occurs often as it is.)

     This writer must output a format understood by the futue reader (coming soon), but this leaves complete freedom in choice of whitespace used in layout because whitespace is not significant. So a main feature of yb2ow is support for pretty printing output to match Lisp convention — indenting nested expessions after line breaks — while coping with cycles in the graph, so cyclic graphs can be printed and read correctly. The reader understands the same cycle notation used by this writer. Some Lisp implementations support notation for cyclic structures; this writer uses this notation too.

     (By coincidence, features in the current writer were finished almost exactly one year ago today. So writing some of this requires figuring out intentions from a year ago.)

     If you use method wshow() to write a graph, it first looks for cycles in the graph and records box addresses in a map of cycles when the same box address is seen more than one time. This actually detects shared structure generally, of which graph cycles are just a subcase. Each box seen more than once is assigned a monotonically increasing integer name that's unique in the graph being printed by one wshow() call.

     For example, suppose the peg you print with wshow() points to a pair which refers to itself — let's say both car and cdr slots both point at the pair itself. In this case, the integer name of this pair is 1 and printing the pair should display this output:

     What does this notation mean? The first time a cycled box (pair in this case) is encountered, it is preceded by syntax #1=, meaning the next object has integer name 1, and any subsequent re-appearance of that box is printed as #1# instead of being printed in its entirety again.

     In addition to handling cyclic references like this, the pretty printer also has to work even in lines that contain syntax like the above. For example, the pretty printing code metering output size must figure out the expression shown above will write fourteen bytes (in this case) and come up with exactly the same answer when metering the size as it does when actually printing real output.

     For example, #1=(#1# . #1#) was inserted in the expression shown above. The reader parses this correctly and the writer shown on this page writes it out again, so it round-trips without change. And metering code correctly figures out the list beginning with #t fits on that line, without reckoning size is "infinite," or some indeterminate number.

     The primary public api for writer yb2ow has three different ways to print a value, and one way to measure length, so you can choose whether or not to get pretty printing, and whether cycles and shared structure should be detected and handled. Service varies from maximal to minimal as follows:

• wshow() - maximal: pretty print, detect cycles
• wshape() - format: pretty print, ignore cycles
• wwrite() - no format: single line, flat format
• wlen() - minimal: wwrite() length without i/o

     Each of those methods is really just an entry point prepping initial state before using a recursive internal api common to all the methods. The first three printing methods set two boolean values, w_show and w_flat, to indicate desired format. Internal settings work like this:

• wshow()  - w_show=true, w_flat=false
• wshape() - w_show=false, w_flat=false
• wwrite() - w_show=false, w_flat=true

     In effect, w_flat means "no pretty printing," and w_show means "detect cycles."

     Internally, boolean flag w_flat causes private _wflat() to print without line breaks; otherwise private _wpretty() writes a pretty print format. But this division of labor overlaps when _wpretty() decides something fits all on one line and uses _wflat() to print it; thus pretty printing devolves to flat printing in leaf cases.

     The yb2ow.h header file defines the following api.

class yb2ow «

     An instance of writer class yb2ow can be instantiated on the stack temporarily, just long enough to print a graph reachable from a particular virtual machine — this usage should be efficient. But you can also instantiate yb2ow inside another object since it won't really use resources except when a print call is in progress (because hashmaps are cleared when printing is done, which releases all pages allocated from the pile referenced by member w_H).

     mu, toy, peg, imm, tag, box, symbol, token, number, bigint, class, method, reader, writer « Þ, eval, env, vm, gc, world, pcode, compiler, asm, lathe, lisp, smalltalk, design, weight, jar, card, harp, debug, profile

     (thorn, todo, names, fd, iovec, assert, log, run, hex, crc, buf, in, out, quote, escape, compare, file, deck, cow, arc, blob, tree, slice, rand, time, stat, hash, heap, node, primes, page, book, pile, stack, atomic, lock, mutex, thread, map, meter, list, iter, ctype)

     This writer's implementation assumes every object graph printed is immutable, and refrains from changing any bits anywhere in a graph printed, in case other code concurrently uses (parts of) that graph at the same time.

     Wil's original Ygg pretty printer from the early 90's used bits in each box named cycle and visited to perform the task of marking a graph prior to printing, in order to identify cycles in the graph. This approach needed exclusive access to a graph being printed, making Ygg inherently single threaded when printing.

     The current cycle detection scheme uses a separate pair of maps in ypp2dm — part of the writer's member state — so printing does not alter any part of a graph being written. This supports concurrent use of objects in the graph during a print operation, as long as no one else alters the graph.

     Because gc moves boxes when garbage collection occurs, and because writer yb2ow holds pointers to boxes in maps (without making these visible as gc roots that can be updated) current writer code assumes gc will not occur in any space overlapping the graph being printed. So using yb2ow to pretty print a graph means gc must be disabled during a single call to print a graph.

     (This is just one of many quirks making the current implementation just a toy. A pretty printer written in the toy language itself would allow gc to occur at the same time.)

yb2ow.cpp «

     The following non-inline writer methods implement the class api. The constructor takes a yM vm (virtual machine) instance, which provides standard symbol address for quote, quasiquote, unquote, and unquote-splicing, since these might not be the same in every virtual machine.

     Each writer also takes a yPBH pile for heap allocation (in case it's not the one used by the the vm), and a out stream subclass of yo to receive all content written — which is implicitly assumed single threaded and dedicated to this purpose (without being written by anyone else).