Monthly Archives: March 2012

DFA state minimization

If you follow the generic instruction for converting a NFA to a DFA presented in my earlier post, the DFA you generate will work, but it will not be optimal. It will have too many states opposed to the bare minimum needed to do it’s job properly. This tends to happen more frequently if you give it an input of an expression that in some respect have redundancy. A prime example of this is the expression a+b+|ab. The |ab part is of course, totally useless. But the subset construction algorithm doesn’t know that.

To compare, here is the NFA generated by thompsons construction:

Here is the non-minimized DFA that the subset construction algorithm will generate:

And here is the minimum DFA required to do the job properly:

Quite a difference! So, how do we do this? There are several ways of accomplishing this, some more complex than others. I’m going to give you a working algorithm which admittedly isn’t the fastest. The faster versions are more complex, and would ruin the idea of explaining the algorithm.

For programmers

I’m willing to bet you’re like me, a programmer and not a mathematician. You can describe this algorithm in math terms to no end, and I’m willing to bet that most people are going to miss out on what is really not the most complex algorithm in the world. If you google this you’re going to get the algorithm described as some function which partitions states so that this and that is true. Perhaps this is jealousy on my part since I feel left out of the cool crowd with the greek symbols and all, but I think there are better ways of explaining this stuff.

The algorithm

It’s a bit backwards, but what we’re going to do is to assume that all states can be merged together and then rule out those that can’t. This is going to be represented by a table, where empty squares are those that we cannot tell apart. So, for now, this table looks like this:

+-----+
|s1|  |
+--+--+--+
|s2|  |  |
+--+--+--+--+
|s3|  |  |  |
+--+--+--+--+--+
|s4|  |  |  |  |
+--+--+--+--+--+
   |s0|s1|s2|s3|
   +--+--+--+--+

This table is going to be filled later on. There’s no reason for a full table, we only want the distinct pairs of states.

What we are interested in is to sort the states into groups that may be merged into a single state without altering the functionality of the DFA. So, what we really need to do is to find out how to find these state groups normally referred to as nondistinguishable states. The first rule of this is:

A state that is an accepting state may never be in the same group as a state which is not an accepting state.

So, in our graphs we may never merge a double-circle state with a single circle state. Let’s apply this to our table. We end up with this:

+-----+
|s1|  |
+--+--+--+
|s2|X |X |
+--+--+--+--+
|s3|  |  |X |
+--+--+--+--+--+
|s4|X |X |  |X |
+--+--+--+--+--+
   |s0|s1|s2|s3|
   +--+--+--+--+

We’re not out of the woods yet, still more work to do. There is another rule at work here. It’s easiest to express this in pseudocode. You will apply the algorithm repeatedly until the table stops changing. If you complete a full iteration without any entry getting filled in, you are done.

do {
for (int i = 0; i < numStates; ++i) 
{
  for (int j = i + 1; j < numStates; ++j)
  {
    if (table[i,j].IsEmpty) 
    {
      foreach (var inputsymbol in allValidInputs)
      {
        if (one of the states has a transition but the other one doesn't)
        {
          table[i,j] = X;
        }
        else if (both states have a transition) 
        {
          int iTarget = state at other end of transition from state i;
          int jTarget = state at other end of transition from state j;
          if (!table[iTarget, jTarget].IsEmpty)
          {
            table[i,j] = X;
          }
         }
        else
        {
           // For clarity, if none of the states have transitions
           // on this symbol, don't change the table
        }
      }
    }
  } 
}
} while (table.WasChanged)

What this does is to check if there is any significant difference by checking where the transitions go, and filling in the table as it goes along. Applying this changes the table to look like this:

+-----+
|s1|X |
+--+--+--+
|s2|X |X |
+--+--+--+--+
|s3|X |  |X |
+--+--+--+--+--+
|s4|X |X |  |X |
+--+--+--+--+--+
   |s0|s1|s2|s3|
   +--+--+--+--+

In this example, iterating the algorithm won’t change the table which means we are done. The states s1 and s3 can be merged into one state and s2 and s4 can be merged into another. To illustrate, here is the two nondistinct state groups marked out:

A final caveat is that you might get long chains of states. Say that s0 and s1 will be merged along with s1 and s2, which really means you need to merge s0, s1 and s2 into another state. This is pretty trivial, and I will not elaborate further on this, an example of this can be found in the class DFA of my parser library Piglet, which is available on GitHub.

As a final note, it can be proven that this algorithm generates the smallest possible DFA that accepts the given grammar. All in a few lines of code. Try the algorithm out yourself at the regex visualizer – make a redundant expression and uncheck the Minimize checkbox.

Tagged , , ,

A regular expression visualizer

Sometimes writing software gives you byproducts, and this is one. When implementing Piglet i ran into the issue that I couldn’t use the built in System.Text.Regex classes that I would have liked to use to avoid implementing another regular expression engine. No matter, so I built one of my own. Now when implementing one of those bad boys I figured that the best way of debugging them was to draw the same graphs that you find in the books – for the simple reason that getting an overview of a directed graph by investigating a bunch of references is tricky to say the least!

So, wise from experience I figured that you can’t spend too much time writing a good debugging facility, and it turned out quite nicely. So nice in fact that I decided to share this with the rest of the world.

It’s a simple tool that allows you to input your regular expression and see the deterministic and nondeterministic machines that implements your expression. Useful for understanding regular expressions and finding problems in your expressions.

Deployed on Appharbor, which was a truly pleasant experience indeed, it can be found here. Open sourced, if you feel it can be improved, please do so! The code is on github, as usual. The app itself is a teeny-tiny MVC application, with some javascript written by someone who is notoriously bad at it (me). If you find any issues, please do tell me using the communications channel of your choice.

Hope you find it useful!

Tagged , ,

Introducing Piglet

This is an introductory post for my latest creation, Piglet the friendly parsing and lexing tool. As so much software Piglet is written out of both a sense of satisfaction in solving a difficult problem, and seeing a void where my piece of software might be useful to someone. Piglet is open sourced using the MIT license. This post is intended to compliment the readme on github to form a better picture of why I have written this library and how it can be used.

Why another parser generator?!

Because the other parser generators are too big for easy tasks, and harder to integrate into a project. They are also highly technical and hard to understand for someone who isn’t genuinely interested in old-school comp.sci.

The purpose is for you to have a tool at hand for parsing tasks that are smaller than full blown language construction efforts. Piglet tries to bridge the gap between (ab)using regular expressions and going in guns blazing with a large parsing toolset. It is not going to replace ANTLR or any of those tools, though you certainly can parse larger grammars with Piglet. This is the tool to use if you want a low-treshold, easy to use tool for any context free data.

Code based configuration

Piglet is, in sharp contrast to most other generators configurable in code. You create your parser and use it as naturally as you configure any other object. It has about the same functionality as the yacc/bison family of tools and generates similar parsers. This is an important point because if your parser is configured using a separate input file or even a completely separate tool you are always going to have a distance between the running code and the parser. The parser generators also sometimes generate fairly incomprehensible code. If you have a small parsing task, are you really going to use a generator or are you going to roll your own parser?

There are some tradeoffs in this strategy. Obviously the parser generation is going to be done at runtimes. However, the parsers are reentrant to the construction should only need to be done once. It also enables you to be able to use lambdas as actions when rules are followed, which also means that Piglet can construct type-safe parsers!

Ease of use

Unfortunately parsing is a bit complex and it’s usually required to know a bit about context free grammars to be able to construct a parser. Piglet tries to get around this problem by introducing a fluent configuration interface.

It’s easier to show it straight up. This is a full blown JSON parser. The only thing missing here is really only details such as the ability to write 0x notation for hexadecimal and exponent notation for numbers. There rest is all there.

// Create a configuration object. This object generates all the configuration needed for the parser.
var config = ParserFactory.Fluent();

// Create rules. The first rule is the MAIN rule, the rule that everything must be able
// to condense down to. For JSON this is a single object, since a JSON string is always
// just one object.
var jsonObject = config.Rule();

// Used to represent an element of an object
// which is something like "elementname" : some_value
var jsonElement = config.Rule();

// This represents a value of a json element
var jsonValue = config.Rule();

// This represents an array of values
var jsonArray = config.Rule();

// Now we declare what a jsonObject is made up of
// Literals are found in quotes. Interesting parts that we are interested 
// in are named using the As clause, which makes them accessible in the 
// .WhenFound. The result of WhenFound is returned to the caller.
jsonObject.IsMadeUp.By("{")
		  .Followed.ByListOf<JsonElement>(jsonElement).As("ElementList").ThatIs.SeparatedBy(",").Optional
		  .Followed.By("}")
	.WhenFound( o => new JsonObject { Elements = o.ElementList } );

// Declares what an element is made up of. Note that the rule above uses the
// jsonElement before what it is made of is declared. This is a crucial part
// of parsing. This bit has two interesting named pieces "Name" and "Value".
// Since each bit has a value, this gets assigned to the o parameter to the WhenFound lambda.
jsonElement.IsMadeUp.By(config.QuotedString).As("Name")
		   .Followed.By(":")
		   .Followed.By(jsonValue).As("Value")
	.WhenFound( o => new JsonElement { Name = o.Name, Value = o.Value } );

// A jsonValue has several interpretations, separated by Or clauses.
// Predefined parsing is found for simple types. Note the recursive use
// of jsonObject, values can be full objects themselves! There is no need
// for .WhenFound clauses for single part rules, they
// will always return the value of the single part.
jsonValue.IsMadeUp.By(config.QuotedString)
	.Or.By<int>()
	.Or.By<double>()
	.Or.By(jsonObject)
	.Or.By(jsonArray)
	.Or.By<bool>()
	.Or.By("null").WhenFound(o => null); // Need to specify, since the default will return the string "null"

// This rule could have been merged into the jsonValue rule, as its 
// own .Or.By clause. It's separated for readability only.
jsonArray.IsMadeUp.By("[")
		 .Followed.ByListOf(jsonValue).As("Values").ThatIs.SeparatedBy(",").Optional
		 .Followed.By("]")
	   .WhenFound(o => o.Values);

// When the configuratin is completed - create the parser!
// If the parser creation is unsuccessful, this throws the
// friendliest exception possible to help you find the issue.
var parser = config.CreateParser();

// Here is how you use it!
var jObject = (JsonObject)parser.Parse(
	@"{ 
		 ""Property1"":""va\""lue"", 
		 ""IntegerProperty"" : 1234, 
		 ""array"":[1,2,3,4,5],
		 ""another_object"" : {
			""another_property"":13.37
		 },
		 ""empty_object"" : {
			
		 }
	}");

There is also a less verbose technical interface, which right now includes more functions than the fluent one does. In the interest of brevity in this post I’m not going to describe it in detail. The features that currently only exists in the tech interface are context dependent precedence, token precedence, panic mode error recovery and type specific parser generation (the fluent parsers will all generate an object as an end result). These should all be upcoming features in further versions for the fluent interface.

The fluent configuration interface is right now in a working state, but can certainly use more functions! Common tasks should be easy to accomplish while harder tasks may require you to fall back on the technical configuration. As an exciting preview of things to come, I’m currently working on an embedded domain specific language generator (made using Piglet) called Snout, which when finished should help the maintainability of the fluent interface.

Piglet is totally dependency free, and written in C# 4. The code is well commented and understandable. If you are looking for code that reasonably explains the parser generation algorithm, Piglet is a sensible choice.

In technical terms, Piglet generates LALR(1) parsers – mainly because it’s an easier way of expressing your grammar since you do not require left factoring which is a pretty difficult concept to explain.

More examples

I’ve written a Demo project that is available in the main github repository which contains a few demos. The unit tests for Piglet are also quite extensive and are suitable for learning. I’m hoping to find more time to write a detailed tutorial on how to go from a given format into a complete parser. Suggestions for tutorials and articles are most welcome.

Getting your hands on it

Piglet lives on GitHub if you want the source code and demos. It also lives on NuGet if you just want the binaries.

Contributing

You are most welcome, regardless of skill level. There’s lots of stuff to do! Or just fork it and go to town on your own. I would be flattered if you did.

And if you can’t program, Piglet could use a logo. I’m thinking a piglet would make an appropriate one 🙂

Tagged , , ,

On big balls of mud

There’s an old article on the web about balls of mud, defined by the article as:

“A big ball of mud is haphazardly structured, sprawling, sloppy, duct-tape and bailing wire, spaghetti code jungle. We’ve all seen them. These systems show unmistakable signs of unregulated growth, and repeated, expedient repair. Information is shared promiscuously among distant elements of the system, often to the point where nearly all the important information becomes global or duplicated. The overall structure of the system may never have been well defined. If it was, it may have eroded beyond recognition. Programmers with a shred of architectural sensibility shun these quagmires. Only those who are unconcerned about architecture, and, perhaps, are comfortable with the inertia of the day-to-day chore of patching the holes in these failing dikes, are content to work on such systems.”

It’s almost as if the balls of mud are genetically predisposed to existing. It probably is the most common phenotype of software out there. The article also includes a pretty thought-provoking analysis of why they appear. Now, this article is quite old, and the problem it’s describes is even older. It begs the question as to why these mud balls are so prominent in spite of decades of well-meaning development methodologies.

It seems that none of these processes have worked, because people still produce mud balls all the time.

  • Software engineering was supposed to make us programmers into engineers. At least that was the original purpose of the term, though it has now evolved into an umbrella term that encompasses all other methodologies. The gist of the idea was that by eliminating the rock’n roll hacker mentality of developers and tuning all developers onto the idea that engineering software should be done like you would engineer a bridge. With requirements and analysis and calculations. It didn’t work, because programming isn’t engineering.
  • The waterfall model, nowadays usually more ridiculed than followed seems to try to solve the mud problem by eliminating change once development has started. This is a great idea, except for the nasty thing called reality where requirements change all the time. So it didn’t work.

Code craftmanship is perhaps the latest and most prominent way of addressing mudballs, except that it really doesn’t. It only says that you’d like to be a craftsman and that you want to create quality stuff and that we should celebrate the programmers as craftsmen. To be fair, it doesn’t even call itself a methodology, it is more of a movement.

But agile will solve it right? Agile solves everything!

The interesting thing is that the article is written before Agile became the latest and greatest thing out there. So, has things turned out for the better?

Of course they haven’t! The mud balls are as ubiquitous as ever.

Agile embraces the change and allows fast iterations and a deliver-focused attitude. So, there will be constant changes and patches to whatever you do, and you have quick iterations with fast releases – which is exactly what causes balls of mud – changing things around fast without thinking in the long term. It won’t work. It might even make it worse.

The only way it can possibly solve the mud problem is that it will make developers so happy that they won’t create bad code any more. Possibly by shielding the team so much behind a scrum master so that they can take the time to make the necessary architectural changes to keep an application clean.

I’m not saying that agile is a bad thing, but it feels like acceptance. Are we by our latest ideology accepting that the development world is a muddy one and constructing our ideological base around handling this as best as we can?

Because scrum handles balls of mud fairly well, but it doesn’t fix them or even prevents them from appearing. Perhaps it polishes them a bit.

Are we resigning to our glorious muddy overlords?

Tagged , ,

Foreign language code

If your native language isn’t English you’ll sooner or later run into the issue of what language you’re supposed to write your code in. Confronted with the last system I worked in I haven’t seen any system which wasn’t written in English – but this system was to a large extent written in Swedish. This felt wrong on many levels with me but it started me thinking. Is the choice always clear cut?

While this article is going to be geared towards Swedish, I assume many of the same concepts apply to other languages. Either way, given the current audience of this blog, you’re probably Swedish too.

The case for English

The language itself

It’s going to be in English whether you want it or not. The only way around it is to program in a language with a preprocessor and #define all the keywords into your favourite language which must be universally evil. So you are going to end up with a pigdin programming language with the terms mixed up and it will not read naturally. Especially if your choice of programming language is something which really tries to be readable English and your native tongue has another word order than what English does.

The characters

I know that most modern languages support coding in unicode so you can actually name your stuff in Chinese, but I have never seen this in the wild. Even the humble Swedish characters of Å, Ä and Ö are notably absent even if they might be supported. So they are replaced with their non-embellished cousins which in Swedish are very separate letters indeed. Here’s a particularly evil real world example:

int Las();

I wonder what this function does? Could it be Läs, the Swedish word for Read? Might it be Lås, Swedish for Lock? Perhaps it refers to the law of employee protection commonly abbreviated as LAS? Who knows..

You can get around this by substituting ä with ae, å with aa and ö with oe. Those are the historical predecessors of our diacritical letters, but no-one uses those combinations any more, and it’s even less readable.

Translation issues

Another issue is that some things are not easily translateable, since they are in use with a third party library. Say your library uses a Table object and you want to write a function that goes and performs a check on the table. What are you going to call it? KontrolleraTable()? Or are you going to translate the word table too.

What the hell is a Mutex called in Swedish?

The case for the moon-language of your choice

With all this in mind, why does foreign language code still pop up from time to time? What is the irresistible pull?

Translation issues, again

Just like Mutex is pretty hard if not impossible to translate into Swedish it’s equally hard to translate Swedish business terms into English. If you don’t believe me, take a look at the field of accounting – something which I’ve been involved in pretty recently.

The Swedish word Periodiseringsfond has no real equivalence in the English language. It’s a genuine term, but it’s a legal one which is very specific to Swedish accounting law. Even the first part of the word, Periodisering is problematic. This actually is translatable into Accrual – but that term is completely unknown to most Swedes even though the knowledge of English is generally excellent.

Provided you need to create a class for a Periodiseringsfond, do you invent a word for it like AccrualFund – even though such a thing doesn’t exist outside of your program – just to keep to the rule of everything in English? This was actually the case for one of the larger systems I’ve worked with. That system had a pretty significant invoicing portion and it was all English. But some of that English was definitely a case of bogus translation directly from Swedish.

I’d love to see where the line is drawn – I’m sure that sooner or later every domain driven design made for a foreign audience will run into this problem.

Also, when you are dealing with your customers or users you probably want to have your developers actually talking to them. Are you unintentionally making a problematic conversation between a tech-oriented developer and a real-world user even harder by not even making them speak the same language. A bit part of the domain driven and behaviour driven design is to make this connection easier – are we missing the point simply because it feels wrong to code partly in a foreign language?

Because it does, it feels so damn wrong.

Tagged , ,

Hosting a WPF control inside a MFC window and making the keyboard work

It’s quite possible to host a brand new shiny WPF control inside your smelly old MFC or even Win32 windows. It’s not particularly hard to do so, but you will need to do a few obscure things to make this work. Also, the intellisense that VS provides isn’t operational when working with C++/CLI. So you’ll pretty much have to know what you’re doing.

Similar code such as this can be found, but they often gloss over the details, such as how to deal with feeding the keyboard events to the child window, and how to make sure that the child window will receive tab events. I’ve included this as well, since you’ll probably want those things when integrating your new component.

First off, in your MFC project you’ll need to turn on support for common language runtime (the /clr flag) and you need to set the CLR-tread attribute to STA-thread in the project which ultimately hosts your .exe file. If you don’t do the STA-thread it will crash horribly and it will not be obvious why it has done so. In fact, the only hint is that it seems to crash even before it has a chance to be able to do so. That’s because the default setting is to handle the windows with multiple threads, something which WPF chokes on. The setting is found under Linker->Advanced.

For the sake of discussion lets say you have a dialog which extends the MFC class CDialog. You want to replace the contents of the window with a WPF control. First there is a few things that needs to be added, namely two references that needs to be kept in the dialog to keep the garbage collector from raining on our parade. In the header add two gcroot members:

gcroot m_hwndSource;
gcroot m_wpfControl;

Now to the more interesting bits, how to actually create an area for the WPF control to live in. What you actually need to do is to create something called a HwndSource. This object is a ‘real’ windows window and as such can receive windows messages and are actually understood by the windows system. A fundamental difference between WPF and Winforms/MFC/Win32 is that WPF does not have a HWND for every component that you create. It will only have one outer window and nothing more. This outer window is not created by itself, instead we need to provide such a window for WPF to live in. In some suitable place like the handler for WM_CREATE in your CDialog add this.

System::Windows::Interop::HwndSourceParameters^ sourceParams = gcnew System::Windows::Interop::HwndSourceParameters("MyWpfSourceWnd");
// This sets the position within the parent window
sourceParams->PositionX = 0;
sourceParams->PositionY = 0;
sourceParams->ParentWindow = System::IntPtr(this->GetSafeHwnd());
sourceParams->WindowStyle = WS_VISIBLE | WS_CHILD;

System::Windows::Interop::HwndSource^ source = gcnew System::Windows::Interop::HwndSource(*sourceParams);
MyWpfControl^ wpfControl = gcnew MyWpfControl();

// This creates sets the root visual of the interop component to out user control.
// As a sidenote, THIS is where it crashes if you have forgotten to set STA-thread.
source->RootVisual = wpfControl;

// Adds a keyboard hook!
source->AddHook(gcnew System::Windows::Interop::HwndSourceHook(ChildHwndSourceHook));

// This is the HWND of the interop component, should you choose to save it.
m_wpfChild = (HWND)source->Handle.ToPointer();
   
// This is important! If you do not save these the garbage collector eats them up!!
m_hwndSource = source;
m_wpfControl = wpfControl;

You might have noticed that we also added a hook to the window. This is needed, since if we do not do this your WPF control is never going to receive any keyboard events. The mouse however still works. This is a simple function outlined below:

System::IntPtr ChildHwndSourceHook(
    System::IntPtr /*hwnd*/, int msg,
    System::IntPtr /*wParam*/, System::IntPtr /*lParam*/, bool% handled)
{
    if (msg == WM_GETDLGCODE)
    {
        handled = true;
        // WANTCHARS = input boxes work
        // WANTTAB = tab order works
        // WANTALLKEYS = Enter key will work
        return System::IntPtr(DLGC_WANTCHARS | DLGC_WANTTAB |DLGC_WANTALLKEYS);
    }
    return System::IntPtr(0);
}

This is pretty much all you need to do. Note that there is nothing strange at ALL with the WPF usercontrol. No modifications needed, which also means that you can insert ANY of the cool WPF controls into your MFC application. Also, should you be stuck in Win32 country this works just as well, you just need to provide the parent HWND in another way than this->GetSafeHwnd().

Now go out and create your frankensteinian interop apps to terrorize the neighborhood.

Tagged , , ,