Visitors in LiveCode

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 :

1. How do we represent this data structure as an object in our programming language?
2. 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:

1. Breadth-First Traversal
   1. 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.
2. Depth-First Traversal
   1. 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.