Algorithms from 6.2 (January/February 2008)

Python has a nifty class called Template. Essentially, a Template is a string containing symbols to be replaced by values. After using it in a couple of small Python projects, I decided that a REALbasic version was in order. The result is available from my web site; here, I would like to work through the design and some of the implementation. Getting Started The first choice was a class name. "Template" was the obvious choice, but I opted for "TemplateString" instead; it seemed to express the idea of the class a little more explicitly. I wanted TemplateString objects to be immutable; that is, once created, its public state could not be changed. Such objects are thread-safe, so I would be comfortable keeping static references to them. Immutability would make TemplateString easier to test, and would make it a better fit for the object-functional programming style that I am coming to favor. The use case I had in mind for TemplateString was to write a template string like "SELECT * FROM Table1 WHERE userID=$userID$", and pass a value for $userID$ to be plugged in at runtime. You might immediately wonder why the existing function Replace wouldn't do. In this case, it would. But handling template strings with multiple keys and escaped $ is trickier, as we will see. Template String Syntax The syntax for a template string is simple. The key marker is a single character; by default it is $, but can be set to any character for each TemplateString object. A key is a string of the form $someStringNotContainingKeyMarker$. The string inside the markers is the "key name". Everything else is literal text, with one exception; $$ is the escape used to represent the literal character "$". The Python Template class specifies a key as something of the form $identifier, where "identifier" is an identifier as defined in the Python grammar. But I did not have a copy of the REALbasic grammar at hand, and REALbasic of course does not lend itself to any metaprogramming possibilities such an approach might provide. TemplateString Interface Here is a functional specification of the interface. Create TemplateString objects with a template string and optional key marker Create objects in-line Provide read-only access to the template string and key marker Get a list of key names Pass a list of key-value pairs and receive in return a string with values plugged in Provide a partial list of key-value pairs and receive in return a new TemplateString object with some keys filled in Passing keys not in the template should result in an exception It is mostly straightforward to go from this wish list to method prototypes. Sub Constructor(s as String, marker as String = "$") Function Template() as String Function Marker() as String Function Keys() as String() One point requiring some thought is the manner in which we pass key-value pairs. A Dictionary is an obvious choice, and for some situations it should be useful. But my bit of experience using TemplateString showed that it was a bit too much. Instead, I found that I preferred passing an array of the form key1, value1, ..., keyN, valueN. And by declaring the list as ParamArray, I could write code like dim query as String = sqlTemplate.Replace("userID", "47") So I ended up adding both. Function Replace(map as Dictionary) as String Function Replace(ParamArray mapElements as String) as String This proved to be convenient when implementing the class. Next are the methods for specializing one TemplateString to another. Function Evaluate(map as Dictionary) as TemplateString Function Evaluate(ParamArray mapElements as String) as TemplateString In addition, I added a function Operator_Convert() as String that returns the Template property. This makes it possible to write code that looks as if some type inference is happening. That is, I can write dim t as new TemplateString("$key1$ $key2$") dim s as String = t.Evaluate("key1", "value1", "key2", "value2") dim t2 as TemplateString = t.Evaluate("key1", "value1") Among the possibilities opened by Operator_Convert is template composition. As part of the interface, I should also say what happens when the keys passed do not agree with the keys present in the template. Passing a key not in the template should result in a KeyNotFoundException. One could simply skip it, but it is reasonable to require only valid keys, and to ignore this error here can make for hard-to-find errors later. Not passing a key that is in the template could be resolved equally well in various ways. I have opted to assume that missing keys are to be replaced with "". Finally, it is convenient from time to time to create ephemeral TemplateString objects in-line. Recent changes to the REALbasic language prevent one from writing code like (new TemplateString("$foo$")).Replace("foo", "bar"), but we can provide the same functionality with a shared method Create that simply wraps the "new TemplateString" part. TemplateString Implementation Implementing TemplateString is a little more subtle than doing some find and replace operations. Here is an example to keep in mind. $$key$$$key$$$ Replacing the key 'key' with "foo" yields $key$foo$ Not only is Replace not enough to handle this example, I was unable to write a regular expression to do it. It is probably possible using zero-width assertions, and I invite you to try. Perhaps not coincidentally, TemplateString requires the technique we have been developing for writing small parsers. Our source code, a template string, contains two token types, literal text and symbols. So, following the Interpreter pattern, we define corresponding classes TemplateStringTokenLiteral and TemplateStringTokenSymbol, both inheriting from a common superclass TemplateStringToken. Here is the code for the superclass. Sub Constructor(s as String) me.pValue = s End Sub Function Value.Get return me.pValue End Get Function Interpret(context as Dictionary) As String return raiseEvent Interpret(context) End Function The context parameter will be nothing more than a Dictionary containing the keys and values passed to Replace. The Interpret event is trivially implemented in TemplateStringTokenLiteral; it simply returns its literal value. In TemplateStringTokenSymbol, the Interpret event handler looks up its key in the context Dictionary and returns the corresponding value, or "" if the key is not present. Here is the first implementation of Replace(map as Dictionary). Function Replace(map as Dictionary) As String if map is nil then dim oops as new NilObjectException oops.Message = "TemplateString.Replace: map is nil.") raise oops end if //check for invalid keys dim output() as String for i as Integer = 0 to Ubound(me.Tokens) output.Append me.Tokens(i).Interpret(map) next return Join(output, "") End Function The code to check for invalid keys is omitted here for brevity, but it is in the project. Implementing Replace(ParamArray mapElements as String) is then a matter of parsing the array mapElements into a Dictionary and calling the first version of Replace. Private Function ParseMapElementList(mapElements() as String) As Dictionary if UBound(mapElements) mod 2 = 0 then dim oops as new UnsupportedFormatException oops.Message = "TemplateString: mapElements is missing an entry." raise oops end if dim map as new Dictionary for i as Integer = 0 to UBound(mapElements) - 1 Step 2 map.Value(mapElements(i)) = mapElements(i + 1) next return map End Function Function Replace(ParamArray mapElements as String) As String return me.Replace(me.ParseMapElementList(mapElements)) End Function The implementation of Evaluate reduces to calling Replace, so I omit it here. Parsing Code The code to parse a template string into an array of TemplateStringTokens follows the same scheme as code from recent columns. The algorithm is this: the parser starts in stateLiteral. It begins scanning through the characters until it hits a key marker. When this happens, the parser has to check the next character to see whether the marker is escaped. If not, it creates a TemplateStringTokenLiteral, then switches state to stateSymbol and scans until it hits a key marker, at which point it creates a TemplateStringTokenSymbol and switches back to stateLiteral. The code is, of course, available in the project. Named Parameters in Replace and Evaluate Parameters in REALbasic methods are positional; that is, the order of the parameters in a method call is significant. Some other languages, including Python, support so-called named parameters. That is, given a function like InStr(source as String, find as String) as Integer, you can call it using the following syntax: return InStr(find = "6", source="0123456789") We can think of Replace and Evaluate as functions that take named parameters, with the formal parameters defined at runtime by the template string passed to the constructor. I am not sure that this is of great importance, but at a minimum we have a working example of named parameters in action in REALbasic code. TemplateString remains a work in progress; indeed, it underwent significant changes in the course of writing this article. The project is available at my web site www.declareSub.com, and I invite your feedback.

Clearance Sale!

A TemplateString Class

Real-Life Parsing

Print:
PDF: