Programming on Trees

• Download source - 1.1 MB

Introduction

In this article, I present some very general programming concepts I came up with long ago, but have not implemented yet. I hope that, perhaps, the interest will be sufficient to motivate me to work on them.

Partially, these ideas were implemented in WPF, Xamarin, Angular and React but they go beyond what those three frameworks offer.

Even though these paradigms are related to visual programming, they can also be applied to non-visual programming as will be explained below.

They are not tied to any particular programming language either, but, at this point, I plan to implement them in C# first. Also, all the samples in this article are given in C# language.

Neither do I tie these concepts to any specific Markup language for building trees: XAML, JSON, HTML can all be tried.

Also, I discuss only what I want to implement, not any specific ways to implement it. For example, the Binding notification concept is not tied to any particular implementation whether it is based on an Observer pattern (as WPF implements it) or it is based on a special loop that checks for changes (as in Angular) is up to the implementor.

Composition Trees

Software engineering is an art of composing complex objects from simpler re-usable ones. Of course, the simpler objects can (and should) also be composed from even simpler and even more re-usable objects, etc.

Such composition creates a tree structure on the software - with the most complex object - usually the resulting program being the root of the tree.

Here is a picture illustrating the composition:

"Top Level Obj" consists of two objects: "Level1 Obj1", a "Level1 Obj2". "Level1 Obj1" in turn consists of two objects: "Level2 Obj1" and "Level2 Obj2". This brings about the following tree structure:

Class Composition Tree

Class Composition Tree is built naturally when you create classes containing objects of other classes.

Take a look at the following ClassCompositionTest sample. The sample describes a very simplified model of an insurance company.

InsuranceCompany class contains CompanyName and property Insurances, which is a collection of Insurance objects. Insurance contains Supervisor property of Person type, InsuranceName property and property Subscribers which is a collection of objects of type Person. Class Person only contains Name property.

This establishes a natural class containment hierarchy: InsuranceCompany contains InsuranceName property and a collection of type Insurance. In turn, Insurance contains InsuranceSupervisor and InsuranceName properties and a collection of type Person. Person contains a property Name.

Note that the class tree nodes can be of two types:

1. Nodes containing objects accessible by unique name within that node
2. Nodes which are collections of similar objects

This is an important characteristic of all trees we'll be dealing with. The data of such trees is well represented by JSON notations with objects accessible by names listed within curly brackets and object collections listed within square brackets.

For example, coming up with some imaginary data for the objects described above, will result in the following JSON:

InsuranceCompany :
{
   CompanyName : "Geico",
   Insurances :
   [
      {
        InsuranceName : "Great Home Insurance",
        InsuranceSupervisor : 
        {
           { Name: "James Clarc" }
        },
        Subscribers : 
        [
           { Name : "Joe Doe" },
           { Name : "Jane Smith" } 
        ]
      },
      {
        InsuranceName : "Not So Great Home Insurance",
        InsuranceSupervisor : 
        {
           { Name: "Tom Jefferson" }
        },
        Subscribers : 
        [
           { Name : "Sam Adams" },
           { Name : "John Buchanan" } 
        ]
      }
   ]
}  

You can also use JSON to reflect the shape (skeleton) of the tree without listing any data:

InsuranceCompany :
{
  CompanyName : string,
  Insurances : 
  [
    { 
      InsuranceName : string
      InsuranceSupervisor : { Name : string }
      Subscribers : 
      [
         { Name : string } 
      ]
    }
  ]
}

Here is a picture representation of the skeleton tree:

Note that the nodes containing named objects are shown with the lines corresponding to the named properties beginning at the same (node) vertex:

While, the collection nodes are shown with the horizontal line segment that has vertical line(s) stemming from it:

Data Trees

A private case of Class Composition Trees are Data Trees where each class represents only data. Our trees in the previous section are actually pure data trees - since the classes presented above only have properties without any other functionality.

HTML DOM

HTML DOM is a good example of a composition tree with each element HTML (aside from the root node) being inside another element - its parent. The HTML Visuals corresponding to the HTML elements are following the same containment hierarchy - the visual corresponding to the parent contains the visual corresponding to a child HTML node.

Examples of collection nodes in HTML tree are items within a list or table rows within a table or table columns within a table row.

React and Angular Virtual DOMs

React and Angular Virtual DOMs are another example of composition. These are simplified trees that use some external data (in case of React - property values and in case of Angular - data containing classes) to generate the real HTML DOM.

React and Angular are great examples of Tree Transformations, where the original simpler trees are transformed into more complex trees.

The picture above shows the transformations of the React Virtual DOM into the HTML DOM (using React framework) and finally into the Browser Visuals (using the browser functionality).

The Virtual to Real DOM generation is done via expansion of some virtual DOM nodes - the expanded nodes can turn much more sophisticated nodes:

WPF Logical and Visual Trees

One of the best and most powerful examples of Trees and Tree Transformations are WPF Logical and Visual Trees.

There are two ways in which one can program expansions of logical tree nodes in WPF - using ControlTemplates - this is more similar to React and using DataTemplates - this is more similar to Angular.

Example of ControlTemplate expansion is given within ControlTemplateExample solution. Here is what you see if you run the project:

Here is the relevant XAML code (logical tree):

<Grid>
    <Grid.Resources>
        <ControlTemplate x:Key="LabeledTextInputControlTemplate" 
                         TargetType="local:LabeledTextInput">
            <Grid>
                <Grid.ColumnDefinitions>
                    <ColumnDefinition Width="Auto" />
                    <ColumnDefinition Width="*" />
                </Grid.ColumnDefinitions>
                <TextBlock Text="{TemplateBinding Label}"
                           HorizontalAlignment="Right"
                           VerticalAlignment="Center"
                           Margin="0,0,5,0" />
                <TextBox HorizontalAlignment="Stretch"
                         Grid.Column="1"
                         Text="{Binding Path=Text, 
                                            RelativeSource={RelativeSource Mode=TemplatedParent},
                                            Mode=TwoWay}" />
            </Grid>
        </ControlTemplate>
    </Grid.Resources>
    <local:LabeledTextInput Label="Enter Text:"
                            HorizontalAlignment="Stretch"
                            VerticalAlignment="Center"
                            Height="30"
                            Margin="10" 
                            Template="{StaticResource LabeledTextInputControlTemplate}"/>

</Grid>

WPF framework expands the LabeledTextInput control using its control template; it expands TextBox as well. We can visualize the resulting Visual Tree, e.g., using snoop:

LabeledTextInput is part of the Visual Tree, but it has a lot of descendent nodes in it.

Running DataTemplateExample solution will produce exactly the same visuals. The difference is that here, we use a DataTemplate instead of a ControlTemplate. DataTemplate describes how to create a visual tree node from a non-visual data represented by ViewModel class. Here is the ViewModel code:

public class ViewModel : INotifyPropertyChanged
{
    public event PropertyChangedEventHandler PropertyChanged;

    void OnPropertyChanged(string propertyName)
    {
        PropertyChanged?.Invoke(this, new PropertyChangedEventArgs(propertyName));
    }

    public string Label { get; set; }

    #region Text Property
    private string _text;
    public string Text
    {
        get
        {
            return this._text;
        }
        set
        {
            if (this._text == value)
            {
                return;
            }

            this._text = value;
            this.OnPropertyChanged(nameof(Text));
        }
    }
    #endregion Text Property
}  

You can see that this class has two properties: Label and Text. Property Text is notifiable (its updates will trigger INotifyPropertyChanged.PropertyChagned event), while property Label is not assumed to change.

Here is the relevant XAML code:

<Grid>
    <Grid.Resources>
        <local:ViewModel x:Key="TheViewModel" 
                         Label="Enter Text:"/>

        <DataTemplate x:Key="ViewModelDataTemplate">
            <Grid>
                <Grid.ColumnDefinitions>
                    <ColumnDefinition Width="Auto" />
                    <ColumnDefinition Width="*" />
                </Grid.ColumnDefinitions>
                <TextBlock Text="{Binding Path=Label}"
                           HorizontalAlignment="Right"
                           VerticalAlignment="Center"
                           Margin="0,0,5,0" />
                <TextBox HorizontalAlignment="Stretch"
                         Grid.Column="1"
                         Text="{Binding Path=Text, 
                                        Mode=TwoWay}" />
            </Grid>
        </DataTemplate>
    </Grid.Resources>
    <ContentControl ContentTemplate="{StaticResource ViewModelDataTemplate}"
                    Content="{StaticResource TheViewModel}" 
                    VerticalAlignment="Center" 
                    Margin="10"/>
</Grid>  

ContentControl is a special WPF control that marries the non-visual (view model) object (contained in property Content) and the DataTemplate (contained in property ContentTemplate). Both the view model and the DataTemplate are given as resources of the Grid panel containing the ContentControl.

Trees in Xamarin

Xamarin provides its own tree objects that translate into different visuals on different platforms. Xamarin for WPF translates the Xamarin tree into WPF visual tree.

Xamarin on other platforms converts the Xamarin tree to a tree of visual elements on that platform.

Comparison of Trees on Various Frameworks

Attached Properties

WPF and Xamarin provide special properties that can be implemented outside of the class that uses them called Attached Properties. They are very useful for several things including the complex object composition as will be described later.

The attached property allows to attach a value of a property to any object by creating a Map (Dictionary) of objects into the property values. They are bulkier and slower than usual properties, but they very useful for the following:

1. Sparse Representation - no need for extra memory if the object contains only default value of the attached property.
2. Property Notifications - Attached Properties allow to provide a callback called every time when the property is modified.
3. Attached properties can be used for attaching a value to an object without modifying the object's type.
4. Attached properties can be the targets of the bindings.

Binding on Trees

React, Angular, Xamarin and WPF all take advantage of the notion of the Bindings. Binding is a way to synchronize two property values on the tree:

WPF has the most powerful bindings of the 4 frameworks mentioned above - its binding has RelativeSource parameter that allows it to bind to a property path off an element higher up on the tree. None of the other frameworks allow anything like that. It is especially disappointing when it comes to Xamarin - which have a .NET tree structure with .NET events but fails to implement RelativeSource.

WPF also has MultiBinding allowing to bind the binding target to multiple sources, so that whenever each one of the sources changes, the target gets updated:

Other frameworks do not provide the MultiBinding directly even though in one can hack something close to MultiBinding in Angular also.

Events on Trees

WPF has a notion of special events called Routed Events propagating up (bubbling) and down (tunneling) the visual tree. In HTML, there are some predefined events that can bubble up the HTML DOM. Still, WPF events are much more powerful, because of the following reasons:

1. They can also tunnel - propagate from the tree root to the current element - something that the HTML events cannot do.
2. One can create a custom bubbling or tunnelling event - while in HTML, the only events that can bubble are predefined events.
3. One can create an attached bubbling or tunneling event in WPF - an event defined outside of the WPF node type while other frameworks do not provide any of-the-shelf way of doing it.

Unfortunately, the current Xamarin version does not allow event bubbling or tunneling either.

Genericity of the Framework

WPF is the most generic framework out of the listed above. It has the fewest number of basic objects from which any other object can be built. WPF Button can be composed out of basic object in the same way as a most complex WPF page. WPF uses DirectX to convert WPF visual trees into real visuals on the screen.

Other frameworks do not provide this level of genericity. While Angular and React to some degree are limited by HTML5 capabilities, the Xamarin could probably do better in a sense of providing more basic object to compose everything in every framework. Xamarin button becomes a Mac button on Mac computers or tablets instead of being composed out of finer level elements like panels, borders and icons.

Since my knowledge of Mac/IPhone and Lunix/Android UI packages is limited, I do not know if there are more basic packages used on those platform that allow to create the visuals for the UI elements (buttons, drop-downs, checkboxes) and so on from more basic elements and basic events, but I believe that there should be. Once the visuals are created, the behaviors and events can be wired via the basic tree.

Main Ideas of the Article

Of all the tree processing frameworks listed above, WPF is the most powerful one as shown above. There are two disadvantages of using WPF, though:

1. Microsoft went sour on WPF, stopping to promote it.
2. WPF works only on .NET platforms. Silverlight used to provide similar (though considerably less powerful) capabilities on other platforms, but MS essentially killed Silverlight.

The main ideas of the article (not implemented yet) consist of the following steps:

1. Create a powerful framework that would allow to process and transform information on generic trees. Such framework would provide all the powerful paradigms described above including Bindings, Attached Events with propagation on trees, Attached Properties.
2. Create a minimal set of primitive visual elements like borders, panels, Icons, Images, etc.
3. Create useful controls (Buttons, CheckBoxes, etc.) out of those primitive elements.
4. Map this primitive visual elements to corresponding visuals on any platform. Once the primitives are correctly mapped, the complex controls should be working also.

In this article, I'll be mostly concentrating on the first point - creating requirements for a framework that would provide more power in operating with Trees than even WPF.

The first tree package I plan to build in C#, while later, I hope, I'll be able to port it also to JavaScript and maybe, Java.

I would like to emphasise again, that this article will not describe the implementation of the functionality - it will only describe the requirements for the functionality. The implementations can still be up to the person or group that implements it. For example, the binding notifications could be implemented via Observer pattern (e.g. C# events) or via a loop that checks for changes - the way it is done in Angular.

Attached Properties

Attached Properties can be easily implemented in almost any language. An example of Non-WPF C# implementation can be found in Plain C# implementation of WPF Concepts - Part 1 AProps and Introduction to Bindings.

Bindings on Trees

What is a Binding

Let us first discuss what is a Binding, and why a Binding is better than an Observer pattern (e.g., a C# event).

The Source binding object is usually selected via some binding parameters with respect to the Target binding object. In particular in WPF, it can be chosen in the following ways:

1. By default, it is set to be contained in the special DataContext property of the target element.
2. If Binding.Source property is specified, the source element is chosen to be that object.
3. If Binding.ElementName is specified, the source object is chosen to be the element of the name within XAML.
4. If Binding.RelativeSource is specified, the binding's source object is looked up the visual tree by various parameters (e.g., by the source object type).

WPF is the only framework I know that allows to choose the binding's source object up the tree using RelativeSource property. None of the other frameworks take tree structure into consideration at all for the binding.

Now I will answer the question in what ways Binding is stronger than using Observers (C# events) for property change notifications. Binding will kick and change the target value under the following conditions:

1. The Binding is created and set on an object while the paths to the source and target properties as well as the Tree structure (if required) exists.
2. The paths and the Tree structure are created while the Binding exists.
3. The source property changes while the Binding and the source and target paths and the Tree structure (if required) exist.

The first two conditions provide for the fact that the Binding should fire and change the required property value at the initialization stage. The last condition is the most common one - the Target should be notified and changed when the source changes.

An Observer (or C# event) will only work for the last condition. Observers do not fire at the initialization stage. This annoying shortcoming should be familiar to most developers who work with C# events. If the event is used to keep several property values in sync, one has to take care also about the initialization when the two objects containing those events are created or the event handler is added.

Binding takes care of the initialization automatically. In that respect, Binding is more useful and stronger paradigms than change notification events.

ObservableCollection and Collection Binding

In C#, ObservableCollection<T> is a collection that implements ICollectionChanged interface containing CollectionChanged event. Using this event, one can get an enumeration of items that are added to or removed from a collection, thus keeping the information about items within the collection up to date.

Collection binding is used in WPF when ItemsControl.ItemsSource property is bound to a property that contains an ObservableCollection<T>. The ItemsControl's visuals will get updated when the property changes to a different collection and also when the collection itself changes (its items are added or removed).

Current Frameworks Bindings Limitations and Ways to Improve them

As was mentioned above, WPF still has the most powerful binding mechanism of all frameworks known to me and listed here (in spite of the fact that Angular, React and Xamarin frameworks were created long after WPF). In fact, WPF is the only framework whose binding takes advantage of the fact that its elements are arranged in a tree structure (via Binding.RelativeSource property).

In spite of the above, WPF has a lot of limitations to its binding, which an ideal framework can fix. Here is a list of such limitations and the proposed fixes.

1. In WPF, only a DependencyProperty defined on an DependencyObject can serve as a Binding's Target. This requirement is artificial and can be removed as I showed in WPF-less Property Bindings in Depth - One Way Property Bindings.
2. In WPF, the Binding source property can be given a complex path, while the target property can only be defined on the target directly. In fact, one can treat source and target in a fully symmetric way and it is easy to create the bindings that allow complex paths on the target side also (as was also shown in WPF-less Property Bindings in Depth - One Way Property Bindings).
3. One way vs two way binding - WPF, Xamarin and Angular allow two way bindings, while React allows only one way bindings. I never came across an application that would need a two way binding AT THE SAME TIME. Usually, when, say a TextBox.Text property is modified by a user, it does not have to be modified at the same time by some data coming from the back end and vice versa. This made me think of the following proposal for binding direction - make the binding always one way and MAKE IT EASY TO CHANGE the DIRECTION of some bindings that AT DIFFERENT TIMES might require different directions.
4. Another way to improve binding is to allow choosing the source of the binding in more elaborate ways. For example, RelativeSource that searches for the source of the Binding up the visual tree, can allow filtering the candidates based on various property values on top of filtering them by their Type.

Change Notification on Trees and Generalization of Property and Collection Bindings

In this sub-section, I plan to describe a further generalization of the Binding concept.

Let us start with a sample which is very similar to the one in the beginning of the article:

InsuranceCompany :
{
   CompanyName : "Geico",
   Insurances :
   [
      {
        InsuranceName : "Great Home Insurance",
        InsuranceSupervisor : 
        {
           { Name: "James Clarc" }
        },
        Subscribers : 
        [
           { 
              Name : "Joe Doe",
              YearlyProfit : $600
           },
           { 
              Name : "Jane Smith",
              YearlyProfit : $400
           } 
        ]
      },
      {
        InsuranceName : "Not So Great Home Insurance",
        InsuranceSupervisor : 
        {
           { Name: "Tom Jefferson" }
        },
        Subscribers : 
        [
           { 
              Name : "Sam Adams",
              YearlyProfit : $100
           },
           { 
              Name : "John Buchanan",
              YearlyProfit : $200
           } 
        ]
      }
   ]
}  

The only difference so far, is that we added YearlyProfit field for every Subscriber.

Here is the Tree's skeleton:

InsuranceCompany :
{
  CompanyName : string,
  Insurances : 
  [
    { 
      InsuranceName : string
      InsuranceSupervisor : { Name : string }
      Subscribers : 
      [
         { 
            Name : string,
            YearlyProfit : number
         } 
      ]
    }
  ]
}

Assume that we want to add YearlyProfit field at the Insurance level and also at the top (company) level to be a sum of all Subscriber level YearlyProfit values under the Insurance or under the whole Company. The aggregated level values should change when a Subscriber level Yearly profit is changed or when a Subscriber is added or removed.

We should be able to create an Insurance level binding specifying the Source and Target paths, as well as an aggregation converter:

InsuranceYearlyProfitBinding : 
{
   SourcePath : "Subscribers/YearlyProfit",
   TargetPath : "YearlyProfit",
   Converter : "typeof(SumAggregationConverter)"
}  

The Company Level binding would have even longer source:

CompanyYearlyProfitBinding : 
{
   SourcePath : "Insurances/Subscribers/YearlyProfit",
   TargetPath : "YearlyProfit",
   Converter : "typeof(SumAggregationConverter)"
}  

One can also come up with cases, when not all the Subscribers should be counted by only some of them corresponding to a certain condition. This can add a Where clause to the bindings.

One can also come up with binding connections from the deeper nodes within the tree to the nodes higher up (analogous to the RelativeSource WPF binding but potentially more complex).

Tree Transformations

Types of Transformations

Tree transformations allow to create a more complex tree from a less complex one.

I gave several Tree Transformation examples above - in particular, the Virtual DOM transforming into a real HTML DOM and WPF Logical to Visual Tree Transformations.

In general, under any transformation, some nodes are expanded into a whole hierarchy of nodes, while the rest of the structure of the tree remains the same.

There are two ways the WPF's Logical Tree nodes are expanded into the Visual Tree nodes:

1. Via ControlTemplates
2. Via DataTemplates

ControlTemplate expansion results in a recursive composition of nodes, while DataTemplate expansion turns non-visual data into a visual hierarchy.

ControlTemplate transformation is very similar to creating components in React. I call this way of transformation "Component Node Expansion". In the coming sub-section, I describe it in more details.

Component Node Expansion

Assume that you have a number of various tree nodes (e.g., WPF elements or React components) that you want to be working together (and, in case of the visual nodes, also situated together).

You can combine them together in their own Component Subtree and create a Component node corresponding to that Component Subtree, so that every Component node in the tree will be replaced by the Component Subtree.

The picture above shows a very simple component LabeledTextComponent whose Component Subtree consists of the root node with two named nodes - LabelComponent and TextInputComponent. If you know WPF, imagine a control consisting of a TextBlock followed by a TextBox - the TextBlock will contain the name of the field while the TextBox will contain the field value.

Following this WPF example, all the instances of LabeledTextComponent within the Logical Tree will be expanded into the full Component subtree during the Logical's Tree transformation into the Visual Tree.

In WPF, the Component Subtree is determined by the ControlTemplate of the Component (WPF Control). In React, the Component Subtree is usually determined by the embedded HTML-like JSX code.

Note that Component-Part relationship can be recursive, i.e., a Composite component can become part of a larger component.

The elements in the Component Subtree can be connected in various ways - e.g. via Bindings of their properties or via code behind or via WPF Control Triggers - this is beyond this article's scope.

In order for the components to be customizable, they should have some customization parameters (properties). For example, our simple LabeledTextComponent should have at least two properties:

1. Label - containing the name of the text field
2. Value - containing the value of the text field

These properties should be connected to the corresponding properties with the sub-components via binding - in our case, the property Label of the LabelComponent, should be bound to the property Label on the LabelTextComponent, while the property Text on TextInputComponent should be bound to the property Text on the LabeledTextComponent.

In WPF, this is achieved via the Binding with RelativeSource set to TemplatedParent mode. In React, this is achieved via this.props class member containing names and values of various properties for the super component.

In WPF, the same Control (Component) can have various ControlTemplate implementations, which is very flexible, but can lead to the following problem. Assume that you want to control some property of a sub-component that does not exist in the original Control. The most wide-spread WPF example would be controlling the Border's CornerRadius property of, say a Button that does not have CornerRadius. You can, of course, sub-class a Button, creating, e.g., ButtonWithCornerRadius class. But then you would have to further subclass it for any combination of properties that the original class Button does not have. Moreover, if you would want to give every Button within already existing code, a corner radius, you would have to replace all those instances by the new class ButtonWithCornerRadius.

This is where the Attached Properties come in very handy. You can create a property CornerRadius outside of the Button class and then use it within the class, as if it was a property of the class. You can also bind the ControlTemplate Border's CornerRadius property to the attached property on the Button.

ButtonCornerRadius sample shows how to attach a new property CornerRadius to a WPF Button without subclassing it. You will see a blue 'Button' with CornerRadius equal 10px when running it:

Here is the relevant XAML code:

<Button local:AttachedProps.CornerRadius="10"
        Width="100"
        Height="50"
        HorizontalAlignment="Center"
        VerticalAlignment="Center">
    <Button.Template>
        <ControlTemplate TargetType="Button">
            <Border Background="Blue"
                    CornerRadius="{TemplateBinding local:AttachedProps.CornerRadius}" />
        </ControlTemplate>
    </Button.Template>
</Button> 

Line local:AttachedProps.CornerRadius="10" sets the attached property CornerRadius on the Button to 10px, while CornerRadius="{TemplateBinding local:AttachedProps.CornerRadius}" line binds the CornerRadius of the Border within the ControlTemplate to the attached property of the Button

This type of Part-Component bindings can also be generalized and used outside of both WPF and React.

Events Propagating on Trees

Lastly, I am going to spend a couple of paragraphs talking about the Events Propagating on Trees. Such events are called Routed Events in WPF.

It is easy to implement bubbling and tunneling events outside of WPF as I showed in Generic (Non-WPF) Tree to LINQ and Event Propagation on Trees.

Such events can be triggered at a tree node and handled at a different tree node (e.g., one of the ancestors of the node at which the event is triggered).

I would like to remind you why such events are important. When you compose any component out of basic elements (e.g., composing a button out of borders, icons and texts), usually events are triggered at the bottom element, e.g., a MouseDown event will can be triggered on the button's border, not on the button itself. It is important that such event propagates up the tree to the button itself, where the handlers for such events can be attached.

Conclusion

In this article, I formulate and generalize the concepts coming from WPF, Xamarin, Angular and React frameworks.

The purpose of this discussion was to lay a foundation of a generic platform independent framework that will have more composition power than any of the frameworks listed above and at the same time can be used for creating GUI on various platforms.