aboutsummaryrefslogtreecommitdiffstats
path: root/doc/doc/design/s2_4
diff options
context:
space:
mode:
Diffstat (limited to 'doc/doc/design/s2_4')
-rw-r--r--doc/doc/design/s2_4345
1 files changed, 0 insertions, 345 deletions
diff --git a/doc/doc/design/s2_4 b/doc/doc/design/s2_4
deleted file mode 100644
index 38d25e7..0000000
--- a/doc/doc/design/s2_4
+++ /dev/null
@@ -1,345 +0,0 @@
-@SubSection
- @Tag { objects.impl }
- @Title { Implementation of objects and concatenation }
-@Begin
-@PP
-In this section we discuss the implementation of objects and concatenation,
-and especially mark alignment. The first step is to use an operator
-precedence parser to convert input such as
-@ID @Code "a |0.5i b /0.2i c | d"
-into parse trees such as
-@ID @Eq {
-@Fig {
-@Tree {
-@Node @FCircle fraction
-@FirstSub {
- @Node @FCircle bar
- @FirstSub { @Node @FCircle a }
- @NextSub { @Node @FEllipse 0.5i }
- @NextSub { @Node @FCircle b }
-}
-@NextSub { @Node @FEllipse 0.2i }
-@NextSub {
- @Node @FCircle bar
- @FirstSub { @Node @FCircle c }
- @NextSub { @Node @FCircle }
- @NextSub { @Node @FCircle d }
-}
-}
-}
-}
-Missing objects are replaced by empty objects, and sequences of
-concatenation operators are consolidated:
-@ID @Eq {
-@Fig {
-@Tree {
-@Node @FCircle bar
-@FirstSub { @Node @FCircle a }
-@NextSub { @Node @FEllipse 0.2i }
-@NextSub {
- @Node @FCircle bar
- @FirstSub { @Node @FCircle c }
- @NextSub { @Node @FEllipse 0.3i }
- @NextSub { @Node @FCircle d }
-}
-}
-}
-&2m ==> &2m
-@Fig {
-@Tree {
-@Node @FCircle bar
-@FirstSub { @Node @FCircle a }
-@NextSub { @Node @FEllipse 0.2i }
-@NextSub { @Node @FCircle c }
-@NextSub { @Node @FEllipse 0.3i }
-@NextSub { @Node @FCircle d }
-}
-}
-}
-to make manifest their associativity and reduce the depth of the tree
-for efficiency later.
-@PP
-The required semantic information is the size of each subobject,
-consisting of four integers: width to left and right of the
-distinguished column mark, and height above and below the distinguished
-row mark. These numbers are always non-negative in Basser Lout, but
-this restriction is unnecessary and should be dropped.
-@PP
-For the leaves, which are simple words, the numbers are obtained from
-font tables. For the higher levels we apply recursive rules. Suppose
-that @Eq { hgap(x, g, y) } returns the desired distance between the
-column marks of objects @Eq { x } and @Eq { y } when they are separated by
-gap @Eq { g }: @Eq { right(x) + length(g) + left(y) } when the gap mode is
-edge-to-edge, the larger of @Eq { length(g) } and
-@Eq { right(x) + left(y) } when the mode is mark-to-mark, and so on. Given
-an object
-@ID @Eq {
-X = x sub 1 ````` bar g sub 1 ````` ... ````` { "-2p" @Font "^"}bar g sub i-1
-````` x sub i ````` ... ````` bar g sub n-1 ````` x sub n
-}
-we may calculate its size as follows:
-@ID @Eq {
-left(X) ^= left( x sub 1 ) + hgap( x sub 1 , g sub 1 , x sub 2 )
-+ ... + hgap( x sub i-1 , g sub i-1 , x sub i )
-/1.4vx
-right(X) ^= hgap( x sub i , g sub i , x sub i+1 )
-+ ... + hgap( x sub n-1 , g sub n-1 , x sub n ) + right( x sub n )
-/1.4vx
-"above"(X) ^= "above"(x sub 1 ) up ... up "above"(x sub n )
-/1.4vx
-"below"(X) ^= "below"(x sub 1 ) up ... up "below"(x sub n )
-}
-where @Eq { non up } returns the larger of its two parameters. Similar
-formulas are easily derived for the other operators.
-@PP
-For purposes of exposition we will now make the simplifying
-assumptions that all gaps are {@Code "0i"}, all column marks lie at
-the left edge, and all row marks lie at the top edge. Then the size
-of each object can be expressed by just two numbers, width and
-height, and the four formulas reduce to
-@ID @Eq {
-width( x sub 1 rel bar ... rel bar x sub n ) ^=
-width( x sub 1 ) + ... + width( x sub n )
-/1.4vx
-height( x sub 1 rel bar ... rel bar x sub n ) ^=
-height( x sub 1 ) up ... up height( x sub n )
-}
-The corresponding formulas for vertical concatenation are
-@ID @Eq {
-width( x sub 1 rel "/" ... rel "/" x sub n ) ^=
-width( x sub 1 ) up ... up width( x sub n )
-/1.4vx
-height( x sub 1 rel "/" ... rel "/" x sub n ) ^=
-height( x sub 1 ) + ... + height( x sub n )
-}
-According to these formulas, the height of
-@ID @Eq { @Fig { @Tree {
-@Node @FCircle fraction
-@LeftSub {
- @Node @FCircle bar
- @LeftSub { @Node @FCircle a }
- @RightSub { @Node @FCircle b }
-}
-@RightSub {
- @Node @FCircle bar
- @LeftSub { @Node @FCircle c }
- @RightSub { @Node @FCircle d }
-}
-}}}
-is
-@ID @Eq {
-[ height(a) up height(b)] + [ height(c) up height(d)]
-}
-which is correct, but for width they yield
-@ID @Eq {
-[ width(a) + width(b)] up [ width(c) + width(d)]
-}
-which is not, since it does not take the merging of column marks into
-account. The asymmetry between horizontal and vertical has come
-about because the row entries, such as @Eq {a} and {@Eq {b}}, are
-adjacent in the tree, but the column entries, such as @Eq {a} and
-{@Eq {c}}, are not. It would be possible to solve this cross-linking
-problem by augmenting the size information stored in each node to
-record the number of marks and the size of each, but the author has
-preferred the following method which makes structural changes to the
-tree instead.
-@PP
-If @Eq { a } and @Eq { c } share a column mark, they each might as well
-have width { @Eq {width(a) up width(c) }}, since all width calculations
-apply to entire columns. Accordingly, we introduce a new operator,
-@Eq {COL}, defined by
-@ID @Eq { width( x sub 1 bin COL ... bin COL x sub n ) =
-width( x sub 1 ) up ... up width( x sub n )
-}
-and replace both @Eq { a } and @Eq { c } by {@Eq { a bin COL c }}. To
-prevent @Eq { COL } operators from disturbing height calculations, we
-define a binary operator called @Eq { SPLIT } by
-@ID @Eq { width( x bin SPLIT y) ^= width(x)
-/1.4vx
-height( x bin SPLIT y) ^= height(y) }
-which switches height and width calculations onto different
-subtrees. Then the transformation
-@ID @Eq {
-@Fig { @Tree {
- @Node @FCircle a
-}}
-&2m ==> &2m
-@Fig { @Tree {
- @Node @FEllipse SPLIT
- @LeftSub {
- @Node @FEllipse COL
- @LeftSub { @Node @FCircle a }
- @RightSub { @Node @FCircle c }
- }
- @RightSub { @Node @FCircle a }
-}}
-}
-# where @Eq { S } denotes a @Eq { SPLIT } node and @Eq { C } denotes a
-# @Eq { COL } node,
-widens @Eq { a } to @Eq {width(a) up width(c) } without affecting its height;
-it is applied to every object that shares its column mark with at least
-one other object. A similar transformation involving a @Eq { ROW } operator
-deals with shared row marks. The effect on our little table is to replace
-@ID @Eq { @Fig { @Tree {
-@Node @FCircle fraction
-@LeftSub {
- @Node @FCircle bar
- @LeftSub { @Node @FCircle a }
- @RightSub { @Node @FCircle b }
-}
-@RightSub {
- @Node @FCircle bar
- @LeftSub { @Node @FCircle c }
- @RightSub { @Node @FCircle d }
-}
-}}}
-by
-@ID @Eq { @Fig maxlabels { "70" } { @Tree hmargin { "0.1c" } {
-@Node @FCircle fraction
-@FirstSub {
- @Node @FCircle bar
- @FirstSub {
- @Node @FEllipse SPLIT
- @FirstSub {
- @Node @FEllipse COL
- @FirstSub { @Node @FCircle a }
- @NextSub { @Node @FCircle c }
- }
- @NextSub {
- @Node @FEllipse ROW
- @FirstSub { @Node @FCircle a }
- @NextSub { @Node @FCircle b }
- }
- }
- @NextSub {
- @Node @FEllipse SPLIT
- @FirstSub {
- @Node @FEllipse COL
- @FirstSub { @Node @FCircle b }
- @NextSub { @Node @FCircle d }
- }
- @NextSub {
- @Node @FEllipse ROW
- @FirstSub { @Node @FCircle a }
- @NextSub { @Node @FCircle b }
- }
- }
-}
-@NextSub {
- @Node @FCircle bar
- @FirstSub {
- @Node @FEllipse SPLIT
- @FirstSub {
- @Node @FEllipse COL
- @FirstSub { @Node @FCircle a }
- @NextSub { @Node @FCircle c }
- }
- @NextSub {
- @Node @FEllipse ROW
- @FirstSub { @Node @FCircle c }
- @NextSub { @Node @FCircle d }
- }
- }
- @NextSub {
- @Node @FEllipse SPLIT
- @FirstSub {
- @Node @FEllipse COL
- @FirstSub { @Node @FCircle b }
- @NextSub { @Node @FCircle d }
- }
- @NextSub {
- @Node @FEllipse ROW
- @FirstSub { @Node @FCircle c }
- @NextSub { @Node @FCircle d }
- }
- }
-}
-}}}
-In fact, common subexpressions are identified (trivially) and the result
-is a directed acyclic graph; each affected leaf has two parents, one for
-width and one for height; and each @Eq { COL } or @Eq { ROW } node has
-one parent and one child for each object lying on the corresponding
-mark. The data structure roughly doubles in size, and this occurs only
-rarely in practice.
-@PP
-This method can cope with any legal input, including
-@ID @OneRow @Code {
-"{ a // c | d } | { b / e }"
-"/ { f / i } | { g | h // j }"
-}
-which produces overlapping spanning columns:
-@ID @I @Fig {
- @FBox margin { 0.2c } width { 1.6c } 1.2f @Font a |
- @FBox margin { 0.2c } width { 0.6c } 1.2f @Font b |
-// @FBox margin { 0.2c } width { 0.6c } 1.2f @Font c |
- @FBox margin { 0.2c } width { 0.6c } 1.2f @Font d |
- @FBox margin { 0.2c } width { 0.6c } 1.2f @Font e |
-// @FBox margin { 0.2c } width { 0.6c } 1.2f @Font f |
- @FBox margin { 0.2c } width { 0.6c } 1.2f @Font g |
- @FBox margin { 0.2c } width { 0.6c } 1.2f @Font h |
-// @FBox margin { 0.2c } width { 0.6c } 1.2f @Font i |
- @FBox margin { 0.2c } width { 1.6c } 1.2f @Font j |
-}
-The boxes have been added to clarify the structure. The width of this
-object is formally
-@ID @Eq { ((width(a) up (x + y)) + z) up (x + ((y + z) up width(j))) }
-where
-@IL
-@ListItem @Eq { x = width(c) up width(`f`) up width(i) }
-@ListItem @Eq { y = width(d`) up width(g) }
-@ListItem @Eq { z = width(b) up width(e) up width(h) }
-@EL
-It seems clear that @Eq { y } at least must appear twice in any
-expression for the width of this object made out of simple addition
-and maxing operations, showing that an ordinary tree
-structure is insufficient for overlapping spanning columns. The Basser
-Lout interpreter actually rejects such structures, owing to the author's
-doubts about the implementability of @I Constrained and @I AdjustSize
-(Section {@NumberOf constraints}) on them; but with hindsight this caution
-was unnecessary.
-@PP
-The directed acyclic graph is ordered in the sense that the order of
-the edges entering and leaving each node matters. The structure is
-highly dynamic, and traversals both with and against the arrows are
-required. After a few ad-hoc attempts to extend the usual tree
-representation had failed, the author developed a representation based
-on doubly linked lists of records denoting links, whose flexibility more
-than compensated for the somewhat excessive memory consumption. For example,
-@ID @Eq { @Fig {
- A:: @FCircle a |2c |2c B:: @FCircle b
-/1.5c C:: @FCircle c | D:: @FCircle d
-// A @JoinFigures arrow { forward } C
-// A @JoinFigures arrow { forward } D
-// B @JoinFigures arrow { forward } D
-}}
-is represented by
-@CD @Eq { @Fig maxlabels { "300" } {
-A:: @DagBox mid { @BlackDot } base { a } |2c |2c |2c |2c
-B:: @DagBox mid { @BlackDot } base { b }
-/1c L:: @DagBox top { @BlackDot } mid { @BlackDot } base { LK }
-| M:: @DagBox top { @BlackDot } mid { @BlackDot } base { LK }
-| | N:: @DagBox top { @BlackDot } mid { @BlackDot } base { LK }
-/1c
-C:: @DagBox top { @BlackDot } base { c } | |
-D:: @DagBox top { @BlackDot } base { d }
-// @TVShape nw { A@MID@CTR } ne { A@MID@CTR } sw {L@MID@CTR } se { M@MID@CTR }
-// @TVShape nw { L@TOP@CTR } ne { L@TOP@CTR } sw {C@TOP@CTR } se { C@TOP@CTR }
-// @TVShape nw { M@TOP@CTR } ne { N@TOP@CTR } sw {D@TOP@CTR } se { D@TOP@CTR }
-// @TVShape nw { B@MID@CTR } ne { B@MID@CTR } sw {N@MID@CTR } se { N@MID@CTR }
-}}
-where @Eq { LK } tags a record representing a link. The first list
-in any node contains all the incoming links, the second contains the
-outgoing ones. The node serves as the header for both lists. The
-required operations reduce to simple appends, deletes, and traversals
-of doubly linked lists, all having small constant cost. There is a
-highly tuned memory allocator, and care is taken to dispose of each node
-when the last incoming link is deleted, so that there is no need for
-garbage collection.
-@PP
-In normal use the number of nodes at higher levels of the dag is small
-in comparison with the leaves and their incoming links, so we may
-estimate the space complexity at about 60 bytes per input word (20 bytes
-per link, 40 per leaf node). Careful optimization could easily halve
-this, but since memory is reclaimed after printing each page there is
-little need.
-@End @SubSection
generated by cgit (git 2.34.1) at 2024-09-19 16:10:07 +0000