Creating PowerShell Stacks and Expression Evaluators

To demonstrate that dynamic modules in PowerShell can be used to easily create objects with methods and properties, Phil Factor implements an expression analyser written in PowerShell, using a variation of Dijkstra's Shunting Algorithm.

PowerShell has a surprising number of different ways of creating objects that have data and methods. Although it is only recently that PowerShell has supported objects directly by means of classes, dynamic modules are a great way of getting the same result. It enables the programmer to create type-constrained data structures that have methods. The problem has been that they don’t seem that easy to understand, and in order to explain them in a way that makes sense, it really needs something convincing and practical by way of an example; what is needed is a demonstration of when a dynamic module would be useful.

One use that seems obvious to me is the stack, also known as the ‘LIFO’ buffer, which is an abstract data structure that is like a stack of plates in a canteen. It has some classic methods, ‘pop()’ where you grab a plate, ‘push()’ where you put a plate on the stack, ‘peek()’ where you see what plate is on the top of the stack and ‘count()’ where you find out how many plates there are. You may need a ‘clear()’ method too. When you’re debugging the workings of a stack, it is nice to be able to see the data.

I use stacks for writing expression analysers. Generally I like at least two stacks, probably up to four. They tend to be different sizes and may have other differences. If written as objects, the code becomes much cleaner and easier to read. Why do I write expression analysers? You might imagine that you would never need such a thing, but once you have one, reasons for using it just keep appearing. They are handy for parsing document-based hierarchical data structures, for parsing grammars and for creating Domain-Specific Languages (DSLs). A DSL is handy when you’re writing a complex application because it cuts down dependencies, and allows you to develop scripts for complex workflows without recompiling .

What I describe here is a cut-down version of what I use, just to illustrate the way of creating and using stacks. I extend this basic algorithm, originally from Dijkstra’s shunting algorithm, into a complete language interpreter. All it needs is a third stack to implement block iterations and ‘while’ loops. Why not use PowerShell itself as your DSL? I’ve tried that, but my experience is that it is pretty-well impossible to eliminate script-injection attacks, and I also find that there isn’t quite enough control.

You’ll notice that the function has dynamic modules that are created as custom objects, one for each stack we need. (the return stack isn’t necessary at this stage, and you may also need an iteration stack too)

The initialisation code that we passed as a scriptblock named @TheStackCode is called with whatever arguments you need. In our case we just need to specify the height of the stack that we require: (-argumentlist 20).

The value stack is saved in a variable for use later. You’ll see that each function has become a method (a ScriptMethod) so that this will work …

The Push() method pushes the string object supplied as a parameter onto the stack and the Pop() method takes each off in turn. The array that is used to store the stack values can be accessed via the object’s TheStack member (a PowerShell NoteProperty) if required for debugging.

The only other part is the initialisation code.

Yes, a lot of magic goes on under the covers to make it so simple, but you have an object that provides information to intellisense and plays well with the Get-Method cmdlet.

So here is the complete code for the expression analyser.

And I have a simple unit-test on the same page to check out that the basic operations are working (it doesn’t catch all the edge cases!). Why are the simple expressions so much easier to do? This is because wherever I can, I am checking against the same expression in PowerShell. Sometimes the operators are different or don’t exist in PowerShell, which uses the static maths class from .net when it can.