LC : Knock knock
User : Who’s there
LC : LiveCode
User : LiveCode who
LC : LiveCode visitors
Joking aside, today we will look at one of the most powerful design patterns when it comes to working on trees – a data structure that is as important to computer science as real trees are to human life.
But first, let’s have a closer look at what the tree data structure represents, and why we might find it useful to define trees.
I’m not going to bore you with the mathematical details, so let’s consider that a tree is a collection of objects (nodes) , where every such object has exactly 1 parent node, but can have more than one child nodes.
This figure should be illustrative of what we mean by a tree in computer science : we have a root node, which has no parents, and then each node has a certain number of child nodes. We also define a special kind of node, called a Leaf, which has no children at all, and which can never have children.
There are several interesting questions that arrive once we fix what we understand by a tree :
- How do we represent this data structure as an object in our programming language?
- Are there any algorithms that help us process information in such data structures in an efficient and easy to understand way?
Answering the first question is rather easy: we can represent them as dictionaries (aka arrays in LiveCode Script) where we create a tree-like structure by having nested dictionaries. A minimal definition of a Node would then look something like
function MinimalNode pChildren
local tResult
put pChildren into tResult["children"]
return tResult
end MinimalNode
However, the spirited reader will have figured out by now that this definition is, to use a technical term, (almost) useless : we do not actually store any information in the nodes except the structure of the tree itself.
Hence, we can define a more useful variant of MinimalNode which adds two fields to each node in the tree : a kind label (defining what the node represents), and a value label (defining what value the node holds).
We also define a few helper functions and commands, to make sure that the nodes we generate are consistent, and to make sure that if we change the name of the labels in the future, we will only have to make a single change to the code, i.e. in the set/get functions
private command setKind @pNode, pKind
put pKind into pNode["kind"]
end setKind
private function getNodeKind pNode
return pNode["kind"]
end getNodeKind
private command setChildren @pNode, pChildren
put pChildren into pNode["children"]
end setChildren
private command setInternalValue @pNode, pValue
put pValue into pNode["value"]
end setInternalValue
Once the helpers are defined, we can move on to define our two categories of tree nodes : Leaves and Nodes.
function Leaf
local tResul
setKind tResult, "leaf"
return tResult
end Leaf
function Node pKind, pValue, pChildren
local tResult
setKind tResult, pKind
setInternalValue tResult, pValue
setChildren tResult, pChildren
return tResult
end Node
Now that we know how to define a tree, we can try to answer the second question we presented earlier : are there any algorithms that help us process information in such data structures in an efficient and easy to understand way?
Perhaps unsurprisingly, the answer is obviously : there isn’t just one such algorithm, there are multiple. Probably the best known algorithms are:
- Breadth-First Traversal
- In this case we have a single function that uses another data structure, called a queue (much like a queue at a supermarket) that manages nodes which have not yet been processed and which feeds us with nodes to process. You can think of this like going through an apartment block, and not going up the stairs to the next floor until you’ve been to all the flats on the current floor.
- Depth-First Traversal
- By contrast, with a depth-first approach, we process full paths from the root of the tree to its leaves, until we exhaust all these paths. Going back to the analogy I made for Breadth-First Traversals, this would be like starting at the ground floor, visiting exactly one apartment on each floor and going up one floor each time, only to then backtrack to the previous floor when we hit the penthouse.
There are cases to be made for either of these choices, however for specific use-cases they both prove to be unsatisfactory.
One such specific use case would be when we have different kinds of nodes and we want to perform operations that depend on the specific type of node. Now, we could achieve this by simply switching on the kind of the node and writing all the code in the code for the traversal, however this is not a particularly wise choice from a code design point of view as it would result in a monolithic block of code.
Luckily, the world of software architecture provides us with a very elegant way out of our conundrum : the Visitor Pattern.
Let me illustrate this concept using an analogy : assume the tree is a person living in its house. The Visitor comes with a basket of items (specific methods for each kind of node), and knocks on the door of the house. The person answers the door and accepts, out of the basket, the item that is appropriate for its kind. Then it performs the action mentioned by the item and returns the results to the visitor, which collects all the results and combines them to give an output.
Typically speaking, in more “mainstream” programming language, the visitor pattern is achieved using something called “polymorphism”. Here, we leverage user-defined types in order to define both tree Nodes and Visitors as classes and using a back-and-forth mechanism known as double dispatch to achieve this. Schematically, this would look like this:
(As a parenthesis, the mechanism is called double dispatch because it depends on the run-time types of both the Visitor and the Node)
Now, as anyone who has used LiveCode knows, these mechanisms are not directly available to us. However, that does not mean that they cannot be implemented. The key to implementing this pattern is to find a way of simulating double dispatch within LiveCode. If we go back to the definition of double dispatch, the answer becomes semi-obvious : we can use a combination of dictionaries to map node types to their corresponding visitor methods by using strings, and using the dispatch function mechanism built into the core language to perform execution.
Hence, consider these statements:
local tVisitorMap
command addVisitorToMap pVisitorName, pNodeKind, pHandler
put pHandler into tVisitorMap[pVisitorName][pNodeKind]
end addVisitorToMap
They essentially give us a way of populating this double dispatch map (if you want to go beyond the scope of this post, google “virtual table lookup” and you will see that we are actually implementing one of the core features of any programming language!)
Hence, we can implement the actual acceptor by doing
function AcceptVisitor @pVisitor, pNode
local tNodeKind
put getNodeKind(pNode) into tNodeKind
dispatch function tVisitorMap[pVisitor["name"]][tNodeKind] with pVisitor, pNode
return the result
end AcceptVisitor
In our case, we represent the visitor as being an object that has a label “name” which basically describes which visitor gets executed (remember, each implementation of a visitor serves a different purpose). This approach is preferred over just passing a string to the visitor as it allows us to build stateful visitors, using the pVisitor parameter to also store state.
One example where this might come in handy is if we were to implement a visitor that pretty-prints a tree, and we would like to know the depth we are currently processing (the depth of a node is its distance to the root of the tree) so that we know how much indentation to add before printing the contents of a node.
Example 1 : Converting Binary Expression Trees to their String Representation
As a first example, we will show a visitor that takes a tree representing binary expressions on numbers and generates a string representation out of that.
Our system has 2 kinds of nodes : num and binop.
Num kind nodes contain an integer as their value.
BinOp kind nodes contain three variables : a left subtree, an operator, and a right subtree.
Hence, we can define the following visitor functions
function visitBinOpNodeToString @pVisitor, pNode
local tLeftResult, tRightResult
put AcceptVisitor(pVisitor, pNode["children"][1]) into tLeftResult
put AcceptVisitor(pVisitor, pNode["children"][2]) into tRightResult
return "(" & tLeftResult & " " & pNode["value"] & " " & tRightResult & ")"
end visitBinOpNodeToString
function visitNumNodeToString @pVisitor, pNode
return pNode["value"]
end visitNumNodeToString
Now we need to register these two visitors with the tVisitorMap, so that they become available to the AcceptVisitor call.
command registerToStringVisitor
addVisitorToMap "toString", "binop", "visitBinOpNodeToString"
addVisitorToMap "toString", "num", "visitNumNodeToString"
end registerToStringVisitor
Indeed, if we build an example tree using this function
function getExampleTree
local tLeafAsList
put Leaf() into tLeafAsList[1]
local tLeftOp, tRightOp, tRoot
put Node("num", 1, tLeafAsList) into tLeftOp
put Node("num", 2, tLeafAsList) into tRightOp
local tNodeList
put tLeftOp into tNodeList[1]
put tRightOp into tNodeList[2]
local tPlusNode
put Node("binop", "+", tNodeList) into tPlusNode
local tChildrenList
put tPlusNode into tChildrenlist[1]
put tPlusNode into tChildrenList[2]
return Node("binop","*",tChildrenList)
end getExampleTree</code
Now we can get the string representation of this by calling
command runNumbersExperiment
registerToStringVisitor
local tTree, tVisitor
put getExampleTree() into tTree
put "toString" into tVisitor["name"]
answer AcceptVisitor(tVisitor, tTree)
end runNumbersExperiment
And indeed the result is ((1+2) * (1+2)) as we would expect.
Example 2 : Using this in a livecode stack to operate on widgets
At this point you might reasonably ask yourself the following question:
Why should I care about this stuff?
Well the reason is that this pattern turns out to be extremely powerful and flexible when it comes to operating on user interfaces in a modular way.
Consider the following sample stack (provided as a download at the end of the post). It represents a simple tab book with three tabs, and each tab contains three check boxes grouped together.
Now we might reasonably want to gather information about these check boxes in one go, or have a way of easily extending our interface without adding too much code that needs to handle that. Hence, we can build the following internal tree representation of this stack:
function getTree
local tLeaf
put Leaf() into tLeaf[1]
local tElements, tForces, tParticles
put Node("checkbox", "check1", tLeaf) into tElements[1]
put Node("checkbox", "check2", tLeaf) into tElements[2]
put Node("checkbox", "check3", tLeaf) into tElements[3]
put Node("checkbox", "check4", tLeaf) into tForces[1]
put Node("checkbox", "check5", tLeaf) into tForces[2]
put Node("checkbox", "check6", tLeaf) into tForces[3]
put Node("checkbox", "check7", tLeaf) into tParticles[1]
put Node("checkbox", "check8", tLeaf) into tParticles[2]
put Node("checkbox", "check9", tLeaf) into tParticles[3]
local tElemGroup, tForceGroup, tParticleGroup
put Node("group", empty, tElements) into tElemGroup
put Node("group", empty, tForces) into tForceGroup
put Node("group", empty, tParticles) into tParticleGroup
local tGroups
put tElemGroup into tGroups[1]
put tForceGroup into tGroups[2]
put tParticleGroup into tGroups[3]
return Node("root", empty, tGroups)
end getTree
We shall present two visitors that work on this group.
Visitor 1 : Printing the tree
Because this is *a representation* of our Widget tree, but not the actual tree used internally by LiveCode, it would be good to have a way of debugging it. Hence, we can define a treePrinter visitor that pretty-prints the tree.
We start by registering the relevant components into the map:
command registerTreePrinterVisitor
addVisitorToMap "treePrinter", "checkbox", "treePrinterVisitCheckbox"
addVisitorToMap "treePrinter", "group", "treePrinterVisitGroup"
addVisitorToMap "treePrinter", "root", "treePrinterVisitRoot"
end registerTreePrinterVisitor
And then we define the actual visitors:
function treePrinterVisitCheckbox @pVisitor, pNode
local tResult
repeat with i = 1 to pVisitor["depth"] - 2
put " " after tResult
end repeat
put "|--" after tResult
put "Checkbox(" & the label of button pNode["value"] & ", "& the hilite of button pNode["value"] &")" after tResult
return tResult
end treePrinterVisitCheckbox
function treePrinterVisitGroup @pVisitor, pNode
local tResult
repeat with i = 1 to pVisitor["depth"] - 2
put " " after tResult
end repeat
put "|--" after tResult
add 2 to pVisitor["depth"]
put "Group()" & cr after tResult
repeat for each key tKey in pNode["children"]
put AcceptVisitor(pVisitor, pNode["children"][tKey]) & cr after tResult
end repeat
subtract 2 from pVisitor["depth"]
return tResult
end treePrinterVisitGroup
function treePrinterVisitRoot @pVisitor, pNode
local tResult
add 2 to pVisitor["depth"]
put "Root()" & cr after tResult
repeat for each key tKey in pNode["children"]
put AcceptVisitor(pVisitor, pNode["children"][tKey]) after tResult
end repeat
subtract 2 from pVisitor["depth"]
return tResult
end treePrinterVisitRoot
This should be quite self-explanatory. The only special thing here is that we are (for the first time) using the fact that our visitor is an object rather than a name in our advantage, by being able to pass around a “depth” parameter which comes in handy for pretty printing.
Running this is easy :
on mouseUp
registerTreePrinterVisitor
setTarget "button1"
local tVisitor
put "treePrinter" into tVisitor["name"]
put 0 into tVisitor["depth"]
local tTree
put getTree() into tTree
answer AcceptVisitor(tVisitor, tTree)
end mouseUp
It might be useful to explain what the “setTarget” command does. Because the AcceptVisitor code lives in the parent stack and we are calling it from a button of the stack, we need to use the “dispatch function … [to target]” syntax in order to overcome going about the message path the wrong way round. But since we want our AcceptVisitor to stay as generic as possible (not coupled to a certain button) we need to set the target to ourselves before calling it.
If we run this code, we should get a result along the lines of:
Visitor 2 : Getting all the checked checkboxes
In this case we actually get something useful out of our visitor : we want a comma separated list of all the checked checkboxes, i.e. their short name and their label.
Again, we start with registering the appropriate visitors
command registerSelectedChecksVisitor
addVisitorToMap "selectedChecks", "root", "selectedChecksVisitorRoot"
addVisitorToMap "selectedChecks", "group", "selectedChecksVisitorGroup"
addVisitorToMap "selectedChecks", "checkbox", "selectedChecksVisitorCheckbox"
end registerSelectedChecksVisitor
And the appropriate visitors:
function selectedChecksVisitorRoot @pVisitor, pNode
local tResult
repeat for each key tKey in pNode["children"]
put AcceptVisitor(pVisitor, pNode["children"][tKey]) after tResult
end repeat
return tResult
end selectedChecksVisitorRoot
function selectedChecksVisitorGroup @pVisitor, pNode
local tResult
repeat for each key tKey in pNode["children"]
put AcceptVisitor(pVisitor, pNode["children"][tKey]) after tResult
end repeat
return tResult
end selectedChecksVisitorGroup
function selectedChecksVisitorCheckbox @pVisitor, pNode
if the hilite of button pNode["value"] then
return the short name of button pNode["value"] & "," & the label of button pNode["value"] & cr
else
return empty
end if
end selectedChecksVisitorCheckbox
In this case we observe that the visitors are much simpler. Indeed, this presents an opportunity to improve our visitor interface: both the visitors for Groups and Roots do nothing more than aggregate results from their child nodes. Hence, we can add a function:
function AcceptVisitorIntoChildren @pVisitor, pNode
local tResult
repeat for each key tKey in pNode["children"]
put AcceptVisitor(pVisitor, pNode["children"][tKey]) after tResult
end repeat
return tResult
end AcceptVisitorIntoChildren
Hence, our previous visitors become:
function selectedChecksVisitorRoot @pVisitor, pNode
return AcceptVisitorIntoChildren(pVisitor, pNode)
end selectedChecksVisitorRoot
and
function selectedChecksVisitorGroup @pVisitor, pNode
return AcceptVisitorIntoChildren(pVisitor, pNode)
end selectedChecksVisitorGroup
Making our code clearly more readable.
Again, running it will yield something along the lines of
(the mouseUp method is similar to the one presented for visitor 1, it is left up to the reader to find the *subtle* differences)
To conclude, I believe we have proven that the visitor pattern is a useful tool for a software engineer, as it presents a nice and easily extendible way of dealing with trees in code, with direct applicability to UI code.
9 comments
Join the conversationSphere - December 24, 2018
I love this! GOing to read it completely again this xmas! Have nice days!
Alex Brisan - January 4, 2019
Thanks Sphere 🙂 – Alex B.
Trevor DeVore - December 26, 2018
Thank you for the interesting article Alex. I didn’t see a link to the example stack but it was easy enough to create a working example based on the article as was a useful exercise. I have a question about your use of the Leaf node. In the code you add a Leaf node to every checkbox node. Why is that? Does it serve a practical purpose that is not explored in this article? Is it just that every tree branch is supposed to terminate in a Leaf?
Alex Brisan - January 4, 2019
Hi again,
I guess it might have something to do with the fact that a tree structure (with leaves) has been placed in my brain since 1st year of Uni – it doesn’t really serve a practical purpose in this article – you could replace it with an empty list of children and then check for that in the visitor.
I think one could argue that using Leaf nodes makes the code slightly more elegant, but I’m not too adamant on that.
Cheers
Alex B.
Trevor DeVore - December 26, 2018
Alex – one other thought. What about moving the AcceptVisitorIntoChildren logic into AcceptVisitor? If a function is registered for a node type then the function is dispatched. Otherwise a recursive call to AcceptVisitor is made on the children nodes.
Alex Brisan - January 4, 2019
Hi Trevor,
Excellent question! It has to do with somewhat unfortunate naming on my side 🙂 AcceptVisitorIntoChildren is suited to the particular use case I’m presenting, but in order to keep it generic the logic has to be separated from AcceptVisitor. We might have cases when we don’t want to aggregate the results of children and then the logic would not be suitable.
Hope I’ve cleared it up.
Cheers,
Alex B.
Max - December 31, 2018
Why don’t you use XML? XML library is in livecode and it is simpler for this task.
Alex Brisan - January 4, 2019
Hi Max,
Thanks for your comment. Indeed, in this field there are multiple ways of doing things – otherwise we’d both be out of jobs 🙂
I was trying to illustrate a technique that I find intriguing and give an example that is applicable to LiveCode. However, I must admit it’s not immediately obvious to me how you would use the XML library in this case – LiveCode stacks are saved as binary files.
However, when you are dealing with XML that holds data, you would probably not be wrong in using that library. As I said – it’s important to choose the right tool for your particular task.
Thanks,
Alex B.
Fred - January 15, 2019
Thanks. I was litterally watching paint dry these last few days, so I created a sample stack based on this.
https://forums.livecode.com/viewtopic.php?f=9&t=32039