Collecting attributes

I’m proceeding with the redesign of my diagrams library slowly but surely. I don’t have a lot of time to work on it, hence the “slowly”. But progress is being made. It’s still very much in the design phase, which makes it difficult for others to help, but Lennart has created a diagrams page on the Haskell wiki which I hope can be a good way to have an open design process and get input from the community. There’s a lot of stuff I have written down that I haven’t gotten around to putting on that page yet, but I hope to do that soon.

Occasionally I plan to write some blog posts about interesting issues that arise in the design; today is the first.

Here’s the background: a diagram is essentially a tree of sub-diagrams (although there will be a principled way to refer to subdiagrams in other parts of the tree; more on this in a future post), with leaves corresponding to atomic primitives. Every node in the tree can (optionally) have some associated style attributes, such as stroke width and color, fill color, font, and other such things. When we encounter a primitive at a leaf, how do we know what attributes to use when rendering it? It may have some associated attributes, but its parent node might also have some associated attributes, and other ancestor nodes higher up the tree might have attributes as well.

What we’d really like to do is have a Style data type which has a Monoid instance:

data Style = Style { strokeWidth :: Double
                   , strokeColour :: Colour
                   ... }

instance Monoid Style where
  ...

Then to determine the style to use for a leaf, we just combine the styles of all its ancestors using the monoid.

So, how to implement this Monoid instance? Well, first of all, what I wrote above is slightly bogus; at the very least each particular attribute ought to be optional, so it should look something more like this:

data Style = Style { strokeWidth :: Maybe Double
                   , strokeColour :: Maybe Colour
                   ... }

To combine two Style records, we match them up field-by-field, and Just trumps Nothing.

So far, so good. But how do we combine two fields containing Just? It seems we have two choices: we can be biased towards the top of the tree (i.e. parent attributes override child attributes) or towards the bottom (i.e. child attributes override parent attributes). Indeed, Data.Monoid contains two newtypes, First and Last, whose Monoid instances exhibit exactly this behavior.

But here’s the problem: in this application, one of these choices isn’t obviously better than the other. In fact, it’s easy to imagine situations where each would be the desired behavior. For example, imagine that we have created a subdiagram that we want to use many times throughout a larger diagram. Most of the time it will be blue, so it makes sense to specify that attribute as part of the subdiagram itself. However, in one place we want it to be red, so we’d like to be able to override its attributes with parent attributes. On the other hand, imagine a situation where a diagram is going to be composed of many different subdiagrams, which all share the property that they are blue. To avoid repeating ourselves, it makes sense to specify “blueness” as an attribute of the parent diagram and have all the subdiagrams inherit it. However, one subdiagram should be red, so we’d like to be able to override the parent attribute in this particular child.

What to do? A first cut might look something like this:

data Override a = Default | OverrideUp a | OverrideDown a

data Style = Style { strokeWidth :: Override Double
                   , strokeColour :: Override Colour
                   ... }

The intention is that OverrideUp a overrides any attributes above/before it, and OverrideDown a overrides any attributes below/after it. However, there’s a problem: what should

(OverrideDown a) `mappend` (OverrideUp b)

be? The OverrideDown a claims to override the OverrideUp b… and vice versa! So this doesn’t really work. We need a way to specify relative priorities. So, another solution would just be to assign each attribute with a priority:

data Prioritized a = Default | Priority Double a

data Style = Style { strokeWidth :: Prioritized Double
                   , strokeColour :: Prioritized Colour
                   ... }

For the Monoid instance, we just take the value with maximum priority. This allows us to do what we wanted—overriding parent or child attributes is done simply by assigning a higher priority. However, I really dislike this solution. Having to specify a priority is annoying—but not only that, figuring out what priority to use to achieve your desired effect requires global knowledge about the value of the priorities used elsewhere. One improvement we could make is to adopt the solution used by CSS: attributes are leaf-biased by default, but assigning a priority can override this. That is,

data Prioritized a = Default | Priority (Maybe Double) a

where the Monoid instance chooses the value with the highest priority, or the right/leaf-most value if no priorities are specified. This might be the best option—but it’s still somewhat unsatisfactory.

I wonder about a solution that allows you to say, “I want to override the attribute on THAT node”—where “THAT” represents some way to refer to a particular node by name (what these names look like will be the subject of another post). This might solve the problem of arbitrariness with the numerical priorities, but might also be veering into the realm of the overengineered…

About these ads
This entry was posted in haskell, projects and tagged , , , , . Bookmark the permalink.

56 Responses to Collecting attributes

  1. I always found CSS sufficiently powerful for styling, while staying very usable. The only thing I really miss is variables.

    One thing that is essential in CSS is specificity of the selectors, which you did not mention yet.

  2. Another way to look at the problem is to think about how diagrams are actually produced in a typical drawing application. The general idea there is that parent attributes override whatever children bring to the table. If you don’t want something to be overridden, don’t make it a child of a node that sets the attribute in question. If you want them to belong together, make them siblings under a grouping node.

    Of course it might also depend on the application whether the child or the parent enjoys priority by default. In this sense, drawing apps and CSS go the opposite way, and for good reasons. That might also be an indication that there is no (elegant, easy to understand etc.) one-size-fits-all solution.

    • Brent says:

      Hi Gergely,

      Can you elaborate on this? Why is it that drawing apps have parent attributes overriding child attributes? Can you give an example of the sort of app you’re referring to?

      • Well, I was just thinking about what happens if I select a bunch of objects that are not grouped and try to set some property. The expected outcome is that the property will be set for all of them. In fact, this is actual copying in most cases, and the colour stays with the pieces even if they are treated separately from then on.

        In the end, I believe I had editing operations in mind instead of the actual structure. But this also suggests that there are several angles you can look at the problem from, and the right solution depends on how you want to manipulate your scene graph, what you want to use it for.

        In the case of a drawing app there is probably little use for overriding attributes, since it would be a lot of hidden state for the artist to keep track of. But if you want to make a distinction between content (structure) and presentation (possibly a different structure) in some way, like CSS, you might even want to define a transformation language (e.g. to provide generated content in nodes like particle systems).

        Another point to think about is that you might not necessarily want to override properties but combine them in some way depending on the node. Maybe that’s the best option: provide a hook to combine two values into a third one, and you can just fill that slot with a default (like override child/parent) that can be changed on a per-node basis.

        Sorry, this post turned out as unstructured rambling instead of a coherent line of thought. ;)

        • Sebastian says:

          As Conal said below, you shouldn’t include in the DSL things which are not domain specific. A transformation language seems to be such a thing for me. I think Haskell and SYB already solve this.

          • Indeed. In this case, the structures the transformation connects are the DSLs. A ‘content language’ and a ‘presentation language’. On the other hand, there might be value in providing a sensible set of combinators that makes it easy to describe the transformations, which is effectively a third language. Ouch, overengineering.

  3. ben says:

    In general, I don’t think that’s doable with a monoid. Essentially, it seems like the meaning of both (OvererideDown a) and (OverrideUp b) is that

    x `mappend` (OverrideDown a) == x `overrideDown` a
    x `mappend` (OverrideUp b) == x `overrideUp` b

    where the two camel-cased functions implement the appropriately-biased composition functions corresponding to the title-cased constructors. But that means

    x `mappend` (OverrideDown a) `mappend` (OverrideUp b) ==
    x `overrideDown` a `overrideUp` b

    and we need to associate those two function applications somehow. The monoid laws require that

    (x `mappend` (OverrideDown a)) `mappend` (OverrideUp b) == x `mappend` ((OverrideDown a) `mappend` (OverrideUp b))

    but clearly

    (x `overrideDown` a) `overrideUp` b != x `overrideDown` (a `overrideUp` b)

    so this is ambiguous and not a monoid. If you want to specify the composition operators, you might want to add a constructor ComposeBy (Style -> Style -> Style) Diagram to the Diagram type. Then you can overlay the associativity of the style composition onto the tree structure already present in the Diagram.

    • Brent says:

      Indeed, you’ve hit the problem on the head. Interesting idea with the ComposeBy constructor, I’ll have to ponder it some more.

  4. JadeNB says:

    Vaguely in line with Gergely’s suggestion, would it make sense to have a special, phantom node ‘DontInherit’ whose only purpose is that its children inherit nothing (including the grand-parent’s attributes) from it?

  5. Personally, I get a lot more clarity about design decisions like this when I start with a different question. First, I ask what is a precise, simple, and compelling denotational model for my data type. Then I ask what makes sense in that model, and the answer is usually very clear. That is, once I have a compelling model, I know what behavior I have to implement. (A lot is covered by type class morphisms.) Without a model, I’m shooting in the dark (hacking API design & implementation).

    • Brent says:

      I should make myself a WWCD? (What Would Conal Do?) bracelet. =) I find this approach very compelling as well—but I admit I’m often at a loss as to how to even begin figuring out what a precise, simple, compelling denotational model is for a given data type. But thanks for the gentle nudge—I’ve started thinking about this for Diagram. I might send you some ideas in order to get your feedback if that’s OK with you!

      • I’d love to help you brainstorm about denotational models for diagrams. This process (what I call “denotational design”) is often difficult for me, and is by far the most clarifying exercise I know in doing library design. I always want to end up with powerful & well-behaved libraries, and I know of no more efficient route to get there.

  6. Lenny222 says:

    Thanks for mentioning the Wiki page.

    Are you sure you want to pack all attributes in a single data structure?

    For example if a node doesn’t have a stroke: you’d end up with strokeWith = Nothing, strokeColor = Nothing, strokeDashPattern = Nothing, strokeMiterLimit = Nothing etc…

    I’d encapsulate stroke, fill in their own data structures, so a style for the above example would end up having a single “stroke = Nothing”.

    This would also make it clear when a node doesn’t have a stroke. In your design, how would you define that? Having strokeWidth=Nothing and/or the color?

  7. Lenny222 says:

    Regarding the inheritance: why is that really necessary?
    How do nodes end up in the tree?

    Can’t each node just have their own style information which is used in any case and can’t a node just say “set the stroke color of all my children to blue” if necessary and just map over all child nodes?

    • JoeThornber says:

      I agree with Lenny222 here; you should be concentrating on the combinators that you use to build these structures, not the structures themselves. So if you want to change the colour of a sub diagram you would just use something like:

      changeColour :: Colour -> Diagram -> Diagram

      • Assuming that by “structures”, you mean representation, then Amen. And, going further, concentrate not only on the API’s form (signature), but also (and more importantly) on its essence (denotation/model).

      • Brent says:

        I don’t think this really solves the problem either. If I do

        changeColour c d

        and d also contains a nested call to ‘changeColour’, what do I get? It really is the denotation of the ‘changeColour’ operation that I’m interested in here, not the particular data structure it’s operating on.

    • Brent says:

      Allowing nodes to contain *instructions* whose denotation involves mutating the global Diagram is just ugly! And I don’t think it really solves the problem, either: if you have multiple nodes specifying conflicting effects, how do you decide which one wins? Just by which one gets run first? That’s even harder to reason about than relative precedences.

      • Lenny222 says:

        I am opposed changing global state. The thing that imho confuses us is: are we talking about data structures or about a monadic DSL?

        I am thinking in terms of this:

        yellowCircle x y radius = yellowStroke $ circleShape x y radius

        If someone wrote

        blueCircle = blueFill . yellowCircle

        the circle would be blue, because that’s how i feel attributes are overwritten.

  8. DavidA says:

    My reference point for this kind of thing would be SVG (an XML standard for scalable vector graphics). In SVG, child attributes always override parent attributes. The reason is that when you’re rendering, that means that you can collect attributes on a stack as you step down the tree.

    If I understand correctly, then the use case in which you thought you might want parent to override child was if you’re embedding a common element from elsewhere in the tree. In SVG, you would do this with the “use” element. Perhaps the solution to your problem is to give the “use” element special semantics – such that attributes stated in the “use” element itself override attributes of the element that is being used.

    This doesn’t conflict with the statement that children always override parents, since the element that is used is not actually a child of the “use” element (rather, it is a node elsewhere in the tree).

    Hope that helps.

  9. sclv says:

    A sketch of some ideas for a related approach…

    data StyleAttrib = StrokeWidth Double | StrokeColor Color | etc…

    newtype Style = Style [StyleAttrib]

    Then have functions which maintain the invariant that there is at most one of each style attrib per style (or don’t, and always just get the first matching).

    Then have some catamorphisms that can set or delete attributes on diagrams and their children, or shallowly on a single diagram.

    myDiagram `clearAttribsDeep` strokeWidth

    myDiagram `setAttribsDeep` (StrokeWidth 10)

    myDiagram `setAttrib` (Color Blue)

  10. Sebastian says:

    I’d prefer “child attributes override parent attributes”.

    Considering your example of “a subdiagram that we want to use many times throughout a larger diagram. Most of the time it will be blue, … However, in one place we want it to be red”:
    Here, I think, the subdiagram is a “template” with a parameter which can be instanciated with the parameter set to red or blue.

    Can’t you use just a function mySubdiagram::Color -> Diagram?
    To instantiate the template, you just call the function when you build the composite diagram.
    Do you really need to represent that template in the diagram tree, isn’t it suficient to have the instantiated template in the tree?

    • Brent says:

      I think “children override parents” is the right default too. And what you describe—having a parameterized template for the subdiagrams—would be the right way to go most of the time. But what if you import a subdiagram from a module someone else wrote, and editing it so that it is a function of the color is infeasible or impossible?

      • In all this discussion of attributes and possible over-riding mechanisms & policies, is there really a *domain-specific* problem being solved? I suspect it’s a domain-independent issue, and so I’d go for a domain-independent solution, keeping the domain-specific semantics as simple as possible, and leveraging the careful design, generality, orthogonality, consistency, and familiarity that comes from applying general solutions wherever possible.

        Brent — your “but what if you import …” remark is an example. Whatever domain/data-type we consider, the concern you raise is applicable. In other words, this issue is not domain-specific.

  11. Rick Fleischer says:

    What about treating the child’s properties as transformations of the incoming parent properties. For instance, “make this width twice the incoming width,” or “tilt this color 15% towards gray.” Or even “average the incoming colors.” “Use he parent value” or “replace the parent value with this one” are only a couple of points in an infinitely large transformation space. I should also point out that the problem of combining attributes is at least as old as Simula, and probably older. I don’t know of a definitive solution. I don’t know if my comment has any relevance to your discussion, so I end here.

  12. conal says:

    Hi Rick. A few comments:

    * I like that you’ve loosened up from replacements to transformations.

    * The discussion is still mired in representation and hence arbitrary.

    * Transforming parent context makes for an “exponentially” more complex semantic model than is probably necessary. (In a literal sense, i.e., introducing an additional function space to accommodate incoming information.)

  13. Lenny222 says:

    Hi Brent,

    just wanted to let you know: i am prototyping a data model for what i have in mind here:

    http://chlor.svn.sourceforge.net/viewvc/chlor/trunk/haskell/Chlor/

    Feel free to be inspired or to ignore it. Could be a another approach.

    Lenny

  14. Lenny222 says:

    Some progress:

    http://www.haskell.org/haskellwiki/User:Lenny222/Chlor

    I have the basic box model working, most basic shape functions and a line chart function.

  15. Lenny222 says:

    I am quite pleased with my prototype’s progress:

    http://www.haskell.org/haskellwiki/Chlor

    On the way i figured, basing the highlevel stuff on boxes is the right thing.

    E.g. the shapes example works like this: create a box, split the box in a grid of boxes, zip the boxes with a list of shapes:

    http://chlor.svn.sourceforge.net/viewvc/chlor/trunk/haskell/examples/shapes.hs?revision=751&view=markup

    Now i am thinking about how to introduce nice State monads to make the tree-construction nicer.

    • Brent says:

      Lenny: very cool! This is definitely very different from the direction I have been heading — in fact I’ve moved *away* from the box model because boxes are too arbitrary and lead to all sorts of weird corner cases (what happens if you rotate a box? what happens if you want a *circular* diagram? etc.) But that’s not a problem, there’s a huge design space and plenty of room for exploring! I hope Chlor continues to evolve into something really beautiful and useful.

      • Lenny222 says:

        Thanks, Brent. For the low-level stuff i am not so sure, myself. The box-model works quite well for the layout/composing of high-level stuff, like different charts and shapes. At least zipping shape-gerating functions with boxes feels so functional. :)

      • Lenny222 says:

        Regarding boxes: i thought they were necessary to describe the highlevel structure of composite graphics, like in a TeX or DTP document.

        … like saying “put a histogram in the upper-left corner, but a pie chart next to it, here is a line chart and something fluffy, … here is the data and oh align them in a nice grid”

        In this sense there is no need to rotate boxes. Boxes are a way to define “something is going to be drawn in this area”.

        For the low-level view (paths, text, primitive shapes etc) i do not have any sugar yet. Currently i just have comfortable functions creating lists of primitives.

        I think my approach and other approaches like yours can be combined. They are just focusing on different level of abstractions.

  16. Lenny – Do you have a denotational basis for this design? If so, is it spelled out somewhere? (And is the implementation faithful to the model?)

  17. I would be astonished if boxes indeed turn out to be necessary. Do you have any ideas on how to prove necessity, as opposed to being the product of habit (mental rut)?

    • Lenny222 says:

      Hi Conal,

      sorry, i am not sure what “denotational basis” means.

      The necessity for boxes comes from the fact that first of all i think it is good design to separate the definition of what i want to draw from where/how big i want that to draw.

      Most complex text/graphics diagrams i’ve seen are assembled in DTP programs like Adobe InDesign. A box model feels natural in this context.

      To clarify: boxes are just parameters you feed into functions to generate complex graphics within those.

  18. Hi Lenny,

    By “denotational basis”, I meant having a precise model of what your data types mean, and a corresponding compositional definition of the meanings of your building blocks. Denotational semantics applied to data types. There are some related exchanges between Brent & me earlier in these post comments.

    I’m uncomfortable with claims of necessity, accompanied by informal arguments, since I’ve noticed such claims & arguments hiding unspoken assumptions. And similarly with naturalness, which can be hard to distinguish from habit.

    • Lenny222 says:

      I have seen you discussion at the top of this page before, but could not quite figure out what “denotational basis” means back then. Neither Google nor dict.leo.org proved to be very helpful.

      I am not quite sure whether discussing “necessity” alone without explaining “regarding what?” is too meaningful.

      If you need to put something on the screen in a grid-like layout, you need to define where and how big. I use “boxes” which contain exactly this information (size and position), nothing more. How would you remove this without losing the contained information.

      For example, have a look at the 4th row in http://www.haskell.org/sitewiki/images/b/ba/Chlor_boxes.png

      I defined this complex grid layout just by saying “take this box, split it and merge the lower-right boxes”.

      I’d be happy to hear about more effective ways to do the same.

      • Sebastian says:

        A way to do it without boxes:
        All drawings (combinations of graphic primitives) implement a function:
        given: a vector x.
        result: the smallest factor a for which this condition holds:
        The drawing is completely on the side of “The” plane (in 2D, thats an infinite line) represented by a*x (perpendicular to a*x and contains the point a*x) x points awai from.

        So when x points to the right, you get the right border and so on.
        This is nicer than boxes because it works with rotated drawings, too.

        example:

        http://www.alice-dsl.net/sebastiansetzer/images/border.svg

  19. Brent says:

    Hey, that’s an excellent idea! I was thinking along the lines of general bounding regions, but something like this seems closer to what we actually want. Of course, the important question is: how well does this compose?

    • Sebastian says:

      border of a composition:
      a_1 = border(object1, x)
      a_2 = border(object2, x)
      a = min(a1, a2)
      compose two objects in a direction:
      a_1 = border(object1, x)
      a_2 = border(object2, -x)
      move object2 in direction x so that a_1 = a_2

      • Brent says:

        Beautiful!

        • Lenny222 says:

          By the way, i still hope that some Haskell hackers could join forces to collaborate on a rich vector graphics framework.

          What’s important to me are only two things:

          1) It has to be platform-independent. Since Cairo/Gtk is a nightmare on Mac, at least an optional pure-Haskell backend like my library provides should be available.

          2) Grid-like composability of highlevel components should be elgegant (in my library this is achieved by zipping functions and boxes).

          What do you think?
          I think we can achieve more by contributing on the same thing.

      • Sebastian says:

        I have extended the drawing for this, too:

        http://www.alice-dsl.net/sebastiansetzer/images/compose.svg

        Another function:
        center(object, x) = (border(object, x) + border(object, -x)) / 2
        Or something like this. Maybe you need to normalize x for this to work properly, but I hope you know what I want to tell you…

        More alignments:
        – compose without inverting x (so the two objects will be aligned at the same side of a border)
        – compose two alignments, for example:
        – same top-border
        – left border = right border

      • Sebastian says:

        replace “a1 = a2″ with “a1 + a2 = 0″

      • Lenny222 says:

        That’s nice one.

        I just think our approaches are different. You seem to describe documents in a bottom/up view, while mine is top/down view.

        You do something like

        a = border(object1, x)

        In my approach this does not make much sense, because i define with boxes where to put which “objects” and how big.

        For example: i don’t need to find out what the right border of a circle is, because i defined it by a box.

        Do you plan to include affine maps or just rotated coordinate system? I could add that to boxes too, once i am entirely convinced the costs of this generalization pays of in practise.

        I don’t think a rotated or arbitrarily distorted coordinate systems seperates us – i could add this to my box-model too. What is different is the bottom/up vs top/down-view. Maybe those models can meet somewhere in the middle.

        • Sebastian says:

          What I think you can’t do with boxes:
          Given two objects which are not rectangular (for example circles). Compose them. Rotate the result (by an angle that’s not a multilpe of 90 degrees). Compose that rotated object again with a third object.

          Because, when you rotate the box in which a circle is contained, you cant find the right border of the cirle anymore, when you look at the box only.

          Top-Down:
          Given the top-most box, rotate by some angle. When the rotated box shall fit into the top-most box, it will be smaller. You’ve “lost” some space.

        • Sebastian says:

          Of course, it would be even nicer if you could compose two objects, based on the “path” that borders them:

          http://www.alice-dsl.net/sebastiansetzer/images/compose_concave.svg

          This way, you could even compose characters of a word, without needing kerning information.

          But that’s much more difficult, I think.

        • Lenny222 says:

          On the low-level i agree.

          I think over time you’ll assemble a library of complex charts/diagrams/graphics routine and that you’ll spend more time using and assembling them than programming new graphics from scratch.

          Like what can be seen here: http://infobeautiful.s3.amazonaws.com/p_index_550.jpg

          How would you describe a highlevel-graphic in your view and how would you compose them, e.g. in a grid?

  20. Lenny222 says:

    I just realized the NodeBox provides such abox model, too: http://nodebox.net/code/index.php/Grid

  21. Lenny222 says:

    I just realized the NodeBox provides such a box model, too: http://nodebox.net/code/index.php/Grid

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s