Jeff Ferguson

Is Software Development Hard?

2009-08-28T20:41:18-05:00:00

A recent episode of .NET Rocks asked this very question, and listening to the episode made me consider my thoughts on the matter.

[Disclaimer: Some of this post may be interpreted as “beating up on Microsoft”. This is not my intent. I use Microsoft in my examples because Microsoft development experiences have been the totality of my professional career. The issues I apply to Microsoft can assuredly be applied to any other company out there.]

The short answer is “no”. I started writing software for Windows machines in 1989. Back then, I had a copy of the 16-bit Windows 3.0 SDK and the Charles Petzold “Programming Windows” Second Edition book (which I still have, thank you very much). I lived with window classes, message loops, and WM_PAINT messages, all in the C language. No one can look me in the eye with a straight face and say that .NET Windows Forms is harder. If you doubt this, I will give you a copy of the 16-bit Windows SDK and the “Programming Windows” Second Edition book and I will sit down with Visual Studio 2008 and Windows Forms. We’ll both set out to write a standard line-of-business application, and we’ll see who gets done first. Go ahead. I’ll wait. I’ll even give you a head start.

I recognize, however, that I can say that because I understand the toolset. I understand it, in part, because I have had twenty years of experience with the Microsoft tools and technologies. I have lived this life for two decades, and, because of that, my view of the software development world may be colored by my experience. If I take a step back, and consider what a person just coming into the industry might be facing, I recognize that their answer may be “yes”. It would be a legitimate response, and I can think of several reasons why someone with less experience may offer that opinion.

Too Many Choices Make It Hard
Microsoft’s myriad of competing technologies often have overlapping use cases, and it can be difficult for new folks (and veterans alike) to decide what technologies to use. Should my data access layer be written in ADO.NET, use the Entity Framework, or ASP.NET Dynamic Data? Should my collaboration work be Sharepoint or Groove? Should I use WPF or Silverlight Out of Browser? No one provides easy answers to these types of questions (often times because the answer is “it depends”). The choices can be daunting, and the ramifications of the choice can make or break a project.

Demo Code Versus Best Practices Code Make It Hard
Conference demos often showcase the state of the art in the Microsoft tools and technologies set. The demos are carefully designed to highlight a specific feature: perhaps of ease-of-use or a subsystem feature. These demos are designed to be performed quickly without regards to actual best practices. An example of this might be a button on a form with code behind that uses dynamic SQL to access some data. This works well for the demo, but the problem is that the sessions showcasing the demos are recorded for posterity and replayed across the Internet by everyone needing to get a basic understanding of a technology.

This video-based online review of the demo code works well, until the person stumbles across a blog post that tells them that code behind is bad, and dynamic SQL is bad, and not having a separate domain objects layer is bad. Where does this person go after watching the video of the canned demo? Have we confused the new folks by doing one thing in a demo and doing something else in blog posts? Are we compounding the issue by offering different ways to get the same thing done?

Lack of Mentors Make It Hard
Much has been made of the fact that our industry is terrible in the areas of apprenticeships and mentoring. It has been suggested that we, as an industry, put some journeyman program in place to help new people learn the craft. It’s a great idea, but I think we can do things now with what we have in place today before that comes to be reality.

I think us “experts”, or “veterans”, or whatever we want to call ourselves – and I put myself in this category – don’t do enough to reach out to those who could benefit from our level of experience. We are, frankly, all full of ourselves, and love to write about esoteric topics like “Building Your Own C# Compiler Using MSIL, Notepad, and the IL Assembler” (or, in my case, discussing the implementation of lexical analysis state machines). That’s fine, but who do we hang out with? Other experts! Our associates are people who also write the “Building Your Own C# Compiler Using MSIL, Notepad, and the IL Assembler” articles. Do we reach out to those who could benefit from what we know? Do we intimidate them? Are they afraid to reach out to us because we’re “so far ahead”? Are we leaving the poor folks who need to know how to get a Windows Form to talk to a database through a business object in the dust because we’re too busy writing about the internals of BizTalk 2009?

Perhaps we can change that. The next generation hangs out where we “experts” do not: in beginner’s forums, such as the Visual C# Express forums on MSDN. If they, for whatever reason, are “intimidated” by us, maybe we could take the first step by spending some time answering questions on those forums. Perhaps we can spend some time there, answering some “basic” questions and, along the way, imparting some of our knowledge to help the new people. It’s worth a try.

Hard For The Experts … Because We Make It Hard
As I look back on projects that have caught my attention for one reason or another, I wonder if we have brought some of this “difficult software” on ourselves. I have seen many projects become over-engineered, over-thought, and over-designed. I have seen many technical leads spend time on features that won’t be used in the initial version but are built because “someday, the customer will need this”. I have seen teams spend six weeks in requirements and design phases, over-thinking problems and designing the ultimate system with ultimate scalability and ultimate flexibility – regardless of whether or not that flexibility is in the customer’s time frame or budgets. Often times, we don’t build what the customers need, but what we think the customers need. Do we really know better than the customer? Is our over-engineering justified? Often times, the answer is “no”, but we, in our infinite wisdom, build huge scalability, flexibility, and configuration subsystems for design features that the customer may or may not ever use. Software may be “hard” because we over-think the problem and, in so doing, we make it hard.

Build what the customer wants, but no more. You’re not on site to throw technology at people. You’re there to solve someone’s business problem. Build the software that solves their business problem, but don’t build more than that. Don’t over-complicate matters that are already difficult.

Now, if you’ll excuse me, I’m going to subscribe to an RSS feed of the Visual C# Express forum on MSDN.

Prism and Unique Module Names

2009-07-12T22:15:51-05:00:00

This code won’t work in a Prism bootstrapper:

   1:  protected override IModuleCatalog GetModuleCatalog()

   2:  {

   3:      ModuleCatalog NewModuleCatalog = new ModuleCatalog();

   4:      NewModuleCatalog.AddModule(typeof(JeffFerguson.Narrative.Wpf.Units.Module));

   5:      NewModuleCatalog.AddModule(typeof(JeffFerguson.Narrative.Wpf.XbrlDocumentLoader.Module));

   6:      return NewModuleCatalog;

   7:  }

If you run code like this, Prism will throw an exception of type DuplicateModuleException with a message that reads “A duplicated module with name Module has been found by the loader.”.

The issue is that Prism uses module names to distinguish one module for another, and, by default, the class name is used as the module name when a module name is not specified. Since, according to Prism (and much to my chagrin), only the tail end of the class name is used when constructing module names, there are, according to Prism, two classes named Module in the code snippet above.

Fortunately, this is all easily fixed through the use of a ModuleInfo object, where all of the information about a module can be specified and added to a module catalog as a unit. My bootstrapper code looks (in part) like this:

   1:  protected override IModuleCatalog GetModuleCatalog()

   2:  {

   3:      ModuleCatalog NewModuleCatalog = new ModuleCatalog();

   4:      AddModuleToCatalog(typeof(JeffFerguson.Narrative.Wpf.Units.Module), NewModuleCatalog);

   5:      AddModuleToCatalog(typeof(JeffFerguson.Narrative.Wpf.XbrlDocumentLoader.Module), NewModuleCatalog);

   6:      return NewModuleCatalog;

   7:  }

8:

   9:  private void AddModuleToCatalog(Type ModuleType, ModuleCatalog Catalog)

  10:  {

  11:      ModuleInfo NewModuleInfo = new ModuleInfo();

  12:      NewModuleInfo.ModuleName = ModuleType.AssemblyQualifiedName;

  13:      NewModuleInfo.ModuleType = ModuleType.AssemblyQualifiedName;

  14:      Catalog.AddModule(NewModuleInfo);

  15:  }

This code simply uses the module type’s assembly qualified name, which will be unique throughout the application, as the name of the module.

My rant here is that I believe Prism should be using the value of the module type’s AssemblyQualifiedName property, and not just the Name property, by default as the module’s name. The two types in the original example are uniquely named, since the class’ namespace forms a part of its fully qualified name. If I had to name my two Module classes with unique tail names (like “UnitsModule” and “XbrlDocumentLoaderModule”, for example), then I wouldn’t have much need for a unique namespace.

OK. Rant over.

RDBMS and The Right Tool for the Right Job

2009-07-06T21:09:58-05:00:00

I read, with interest, a post by Whitney Weaver about the “No SQL” movement. I have been, to this point, blissfully unaware of this movement. While I am not quite ready to get rid of SQL, I have been known to gripe about some of its applications and wanted to share my thoughts on the subject.

SQL (or, more correctly, a Relational Database Management System, or RDBMS) is fantastic at performing the work for which it was designed: the storage of related data. Through mechanisms such as referential integrity and triggers, the RDBMS platform has become a powerful engine for the storage of data. I remember my first internship in 1987, where I watched people run queries directly against an RDBMS and pull back just the data they needed. It truly was the right tool for the right job.

However, we have spent the last two decades (if not longer) building software systems on top of an RDBMS engine. From ODBC and JDBC to OLE DB to ADO to ADO.NET, we, as an industry, have invested a lot of time and effort into building software bridges to allow our object data (which can often be represented in a two-dimensional object graph, with parent objects holding references to children and collections of children) to be stuffed into an RDBMS. Has it been successful? Perhaps. In my opinion, though, it’s a fragile system overall, for a few reasons:

Dimensional Mismatch: As I noted above, RDBMSs are best at storing one dimensional data in a single row housed in a table. Our object graphs, however, can be two dimensional data representations, with cross-object references and related data. We have overcome this hurdle, for the most part, with careful management of primary and foreign keys, but, without continued care, this sort of system can become out of sync.
Separate Tools, Independent Management: I can design the best object model and data store in the world, but any such system comes down to independent system management by separate groups of people. The developers take care of their object model and the DBAs take care of the database. This works well, until one group decides to change something. Have you ever been on a project where a DBA decides to change the data type of a column, or a developer changes some data validation logic without informing the DBAs? Separate tools and separate maintenance teams offer one more place where something can go wrong. I once attended a class led by Brent Rector who said, “A thing built on top of a thing is not as good as a thing”. I have never forgotten that, and I think of it every time I see one architectural idea, such as classes, built on top of a separate tool, such as an RDBMS.
Not Data, But Data And Behavior: We very rarely pull data from a database and use it as is. Instead, we pull the data and run calculations or validations against the data. Where should this validation and calculation code live? If it is to live in stored procedures – which not all RDBMSs have – then the DBAs are in for a bit of a ride as all of the business logic is implemented in a set-based language like SQL. If, instead, the validation and calculation code is to live in business objects, then people who query the database without using the business objects miss out on the value-added business logic. Again, the “separate tool” idea comes back to bite us.

At this point, you can offer one big rebuttal to all of my whining: “OK, Jeff, then show me something better.” I can’t. For better or for worse, this is where we are today. But I am hopeful that things can change. If we, as a community, didn’t innovate, then we would all still be running Windows 3.1 on top of DOS. Perhaps “No SQL”, as a mantra, is a bit drastic; however, stretching the imagination and moving into new territory is not such a bad idea, either. Personally, I’d like to see a general purpose language carry more tightly integrated object state storage support rather than relying on a separate tool. Time will tell whether or not this will actually happen.

I find it interesting (but not ironic) that we are the industry who says “use the right tool for the right job”, and, in the next sentence, says “of course, everything has to be on the Web, the data format always has to be XML, and the data storage engine always has to be SQL”. I subscribe to the old adage that the answer to any design problem is “it depends”, which aligns much more closely with “use the right tool for the right job” than it does with “the data storage engine always has to be SQL”.

Working with Prism and the Blacklight Controls

2009-06-30T18:58:38-05:00:00

I recently set out to build a WPF application using the Composite Client Application Guidance (lovingly known as “Prism”) code base. Additionally, I wanted to make use of the Blacklight controls – specifically, the DragDockPanelHost and DragDockPanel controls – in the application. I soon discovered that these two code bases didn’t work together “right out of the box”. I found a problem, and a solution, and this post describes both the issue and its resolution.

The architecture promoted by Prism is that of an application made up of an executable shell and a set of module assemblies. In this pattern, each of the application views are implemented in their own module assembly, which is loaded by the shell at runtime. So far, so good.

Since I was interested in using the DragDockPanelHost and DragDockPanel controls in my WPF application, my approach was to put the DragDockPanelHost in my shell application, and a DragDockPanel in each of my Prism modules. With this design, and after assigning a Prism region name to the DragDockPanelHost in the shell application, Prism would do its thing and load each of the DragDockPanels from each module and add them into my DragDockPanelHost region at runtime.

You may be asking yourself, “And how did that work out for you?” To quote Stewie on Family Guy, “Not well, Brian. Not well.”

My first mistake was in assuming that Prism regions worked with any kind of container control, and, therefore, putting a region name on my DragDockPanelHost XAML element would be enough. It wasn’t. Prism, by default, only supports regions defined on containers derived from one of the following classes:

System.Windows.Controls.Primitives.Selector
System.Windows.Controls.ItemsControl
System.Windows.Controls.ContentControl

The DragDockPanelHost class is derived from Canvas, which explains the lack of love that I got from Prism.

Fortunately, Prism has a way to add support for other containers defined as regions through the RegionAdapterBase class. In my solution, I wrote a class, derived from RegionAdapterBase, that defined a region adapter for the Blacklight DragDockPanelHost. The class looks like this:

   1:      public class DragDockPanelHostRegionAdapter : RegionAdapterBase<DragDockPanelHost>

   2:      {

   3:          public DragDockPanelHostRegionAdapter(IRegionBehaviorFactory BehaviorFactory) : base(BehaviorFactory)

   4:          {

   5:          }

6:

   7:          protected override void Adapt(IRegion region, DragDockPanelHost regionTarget)

   8:          {

   9:              region.Views.CollectionChanged += (s, e) =>

  10:                  {

  11:                      if (e.Action == NotifyCollectionChangedAction.Add)

  12:                      {

  13:                          foreach (FrameworkElement CurrentElement in e.NewItems)

  14:                          {

  15:                              UserControl CurrentElementAsUserControl = CurrentElement as UserControl;

  16:                              DragDockPanel PanelToAdd = CurrentElementAsUserControl.Content as DragDockPanel;

  17:                              CurrentElementAsUserControl.Content = null;

  18:                              regionTarget.AddPanel(PanelToAdd);

  19:                          }

  20:                      }

  21:                      else if (e.Action == NotifyCollectionChangedAction.Remove)

  22:                      {

  23:                          foreach (FrameworkElement CurrentElement in e.OldItems)

  24:                              regionTarget.Children.Remove(CurrentElement);

  25:                      }

  26:                  };

  27:          }

28:

  29:          protected override IRegion CreateRegion()

  30:          {

  31:              return new AllActiveRegion();

  32:          }

  33:      }

The generic type used in the RegionAdapterBase class is the type of the class for which you need Prism to support as a region. The body of the effort is in the Adapt() method, which is called when controls are added or removed from the container.

This class needs to be used in the shell’s Prism bootstrapper through an overloaded method called ConfigureRegionAdapterMappings():

   1:      internal class Bootstrapper : UnityBootstrapper

   2:      {

   3:          protected override DependencyObject CreateShell()

   4:          {

   5:              // ... snip

   6:          }

7:

   8:          protected override IModuleCatalog GetModuleCatalog()

   9:          {

  10:              // ... snip

  11:          }

12:

  13:          protected override RegionAdapterMappings ConfigureRegionAdapterMappings()

  14:          {

  15:              RegionAdapterMappings Mappings = base.ConfigureRegionAdapterMappings();

  16:              Mappings.RegisterMapping(typeof(DragDockPanelHost), Container.Resolve<DragDockPanelHostRegionAdapter>());

  17:              return Mappings;

  18:          }

  19:      }

The region adapter is registered with Prism in the RegisterMapping() method of the RegionAdapterMappings class.

With this, I can now define a user control in my Prism module that defines a DragDockPanel:

   1:  <UserControl x:Class="Narrative.Units.View"

   2:      xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"

   3:      xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"

   4:      xmlns:blacklight="clr-namespace:Blacklight.Controls;assembly=Blacklight.WPFControls">

   5:      <blacklight:DragDockPanel Header="Title" />

   6:  </UserControl>

Then I can, in my Prism shell, define a DragDockPanelHost with a region:

   1:  <Window x:Class="App.MainWindow"

   2:      xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"

   3:      xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"

   4:      xmlns:blacklight="clr-namespace:Blacklight.Controls;assembly=Blacklight.WPFControls"

   5:      xmlns:regions="clr-namespace:Microsoft.Practices.Composite.Presentation.Regions;assembly=Microsoft.Practices.Composite.Presentation"

   6:      Title="App Title" Height="300" Width="300" x:Name="Main">

   7:      <Grid x:Name="MainGrid">

   8:          <Grid.RowDefinitions>

   9:              <RowDefinition Height="auto"/>

  10:              <RowDefinition Height="auto"/>

  11:              <RowDefinition Height="*"/>

  12:          </Grid.RowDefinitions>

  13:          <blacklight:DragDockPanelHost Background="Khaki" HorizontalAlignment="Stretch" VerticalAlignment="Stretch" Width="Auto" Height="Auto" Grid.Row="2" x:Name="PanelHost" Margin="15" regions:RegionManager.RegionName="PanelHostRegion" />

  14:      </Grid>

  15:  </Window>

This solved the issue, and I can now have my DragDockPanelHost in a Prism executable shell and a DragDockPanel user control in a Prism module.

Slides and Code for Lexical Analysis Talk

2009-04-10T07:42:39-05:00:00

Last evening, I presented my “Inside Lexical Analysis” talk to the Twin Cities Languages User Group (TCLUG). I have posted both the slide deck and code samples that used during the talk; feel free to grab a copy if you wish. If you have any questions or comments about the material, feel free to get in touch with me and let me know (you can find me on Twitter here, or leave a comment on this blog post).

Many thanks to TCLUG coordinator (and friend and colleague) Jason Bock for arranging the event and allowing me the opportunity to speak!

Expression Evaluation Coming to MGrammar?

2009-04-01T07:47:25-05:00:00

Consider the following simple calculator authored in yacc:

%{  
    #include <stdio.h>   
    int yylex(void);   
    void yyerror(char *);   
%}   
  
%token INTEGER   
  
%%   
   
program:   
        program expr '\n'         { printf("%d\n", $2); }   
        |    
        ;   
  
expr:   
        INTEGER   
        | expr '+' expr           { $$ = $1 + $3; }   
        | expr '-' expr           { $$ = $1 - $3; }   
        ;   
  
%%   
  
void yyerror(char *s) {   
    fprintf(stderr, "%s\n", s);   
}   
  
int main(void) {   
    yyparse();   
    return 0;   
}

A notable feature of this grammar is that the syntax definitions are augmented with C code statements that are executed when the syntax is discovered in the input stream. This code is able to interpret the input and, if necessary, perform a calculation and send the result of the calculation into the abstract syntax tree (AST). Consider, for example, the following fragment from the yacc grammar above:

expr '+' expr           { $$ = $1 + $3; }

The yacc engine will assign temporary variables to matching input as follows:

$1: the first expression
$2: the ‘+’ token
$3: the second expression

An additional variable, called $$, contains the results of the parsed input. In this fragment, the equivalent of an anonymous delegate includes C code to perform the addition operation on the contents of $1 and $3 and place the results in $$. With this, some work can be done “in place” to not only construct, but also to evaluate, the AST.

This background information is necessary to understand the following: MGrammar has no such capability today. Anonymous methods cannot be attached to MGrammar syntax productions, and “in place” interpretations of the AST in this manner is not possible.

However, this doesn’t mean that such a feature will never appear in MGrammar. In discussing this issue in the MSDN Forums for “Oslo”, Microsoft’s Paul Vick made this comment:

I thought I'd interject that we're considering ways to evaluate expressions directly in grammars. It's a pretty useful feature, and we'd love to provide the full M expression capabilities on the RHS of a grammar production. So stay tuned!

Disclaimer:This does not represent an official commitment from Microsoft. Don’t read too much into this. It might happen. It might not. Don’t storm Paul’s office with torches and pitchforks if it doesn’t appear. But Microsoft is thinking about it, and that’s all we can ask.

Error 8013150A Importing TFS Work Item Templates with TFS Power Tools

2009-03-30T09:30:38-05:00:00

I just ran across this error while using the Team Foundation Server Power Tools to import a work item template XML document into a TFS instance:

Error 0x8013150A: An error relating to security occurred.

So it’s a security issue, right? No.

As it turns out, I had edited the XML file in Notepad and added values to a field definition with the ALLOWEDVALUES rule. In my over-zealous copy-and-paste efforts, I had added a few of the allowable values in more than one place:

<FIELD reportable="dimension" type="String" name="MyName" refname="MyProject.MyName">
  <ALLOWEDVALUES>
    <LISTITEM value="Value1" />
    <LISTITEM value="Value2" />
    <LISTITEM value="Value3" />
    <LISTITEM value="Value1" />
    <!-- more values -->
  </ALLOWEDVALUES>
</FIELD>

The attempt to import this file into the TFS Process Editor Power Tool failed with the 8013150A error. After playing with security rights for a while, to no avail, I decided to double check my edits. I found and removed the duplicate entries in Notepad and tried again to load the file into TFS Process Editor Power Tool. Success!

Just thought that I would document the issue in case someone else runs across the same problem. The moral of the story is this: an error message of “an error relating to security occurred” does not necessarily mean that you have a security issue with your file. Check the contents of the file and make sure that is valid with regards to both syntax and semantics. In particular, do not list an item in an ALLOWEDVALUES list more than once … or you’ll get a security error … which makes perfect sense … I guess …

Interpreting Mathematical Operators in MGrammar

2009-03-24T09:23:15-05:00:00

Suppose that you have a need for a domain specific language that supports mathematical expressions. Specifically, you want to support the following:

unsigned integers
signed integers
addition expressions
subtraction expressions

Your first attempt at such a grammar using MGrammar might look like this:

module JeffFerguson.BlogPosts
{
    
    language MathOps
    {
        
        // ignore whitespace
        
        syntax LF = "\u000A";
        syntax CR = "\u000D";
        syntax Space = "\u0020";
        interleave Whitespace = LF | CR | Space;
        
        // operators
        
        token PlusOperator = "+";
        token MinusOperator = "-";
        token StatementEnd = ";";
        
        // numerics
        
        token UnaryOperator = PlusOperator | MinusOperator;
        token Digit = "0".."9";
        token WholeNumber = UnaryOperator? Digit+;
        
        // expressions
        
        syntax AdditionExpression = t1:WholeNumber PlusOperator t2:WholeNumber =>Add[t1,t2];
        syntax SubtractionExpression = t1:WholeNumber MinusOperator t2:WholeNumber => Subtract[t1,t2];
        syntax MathematicalExpression =
            WholeNumber
            | AdditionExpression
            | SubtractionExpression;
                             
        // language syntax
        syntax Statement = e:MathematicalExpression StatementEnd => Statement[valuesof(e)];
        syntax Main = Statement*;
    }
}

There is a subtle problem with this grammar. Suppose that you offer the following input to the grammar:

1;
+2;
-3;
4+5;

This input will give you errors:

[file://untitled1/#4,2-4,4] error 5007: Token JeffFerguson.BlogPosts.MathOps.WholeNumber with text "+5" unexpected. 
[file://untitled1/#4,2-4,4] message 5011: Assuming an insertion of value ';' to continue parsing. Could also have inserted '-', '+'.

The problem is with the “4+5” statement. The issue here is that the “+” symbol is being interpreted as the unary operator for the “5” symbol, and MGrammar is attempting to see the “4” and the “+5” as separate symbols, which is not what was intended. Rather, the input most likely meant to offer the “4+5” (as in “9”, for those of you not up on your math) as an additive operator.

The issue has to do with the fact that MGrammar’s lexical analysis engine runs before the grammatical parser, just as lex runs before yacc. This means that token operations in an MGrammar definition are interpreted before the syntax definitions. Since the unary operator is defined as part of a token definition, then that binding will take precedence over the addition syntax.

This can be fixed by specifying the unary operator as a syntax definition with a slight change to the grammar:

module JeffFerguson.BlogPosts
{
    
    language MathOps
    {
        
        // ignore whitespace
        
        syntax LF = "\u000A";
        syntax CR = "\u000D";
        syntax Space = "\u0020";
        interleave Whitespace = LF | CR | Space;
        
        // operators
        
        token PlusOperator = "+";
        token MinusOperator = "-";
        token StatementEnd = ";";
        
        // numerics
        
        token UnaryOperator = PlusOperator | MinusOperator;
        token Digit = "0".."9";
        syntax WholeNumber =
            n:Digit+ => UnsignedNumber[n]
            | s:UnaryOperator n:Digit+ => SignedNumber[s, valuesof(n)]
            ;
        
        // expressions
        
        syntax AdditionExpression = t1:WholeNumber PlusOperator t2:WholeNumber =>Add[t1,t2];
        syntax SubtractionExpression = t1:WholeNumber MinusOperator t2:WholeNumber => Subtract[t1,t2];
        syntax MathematicalExpression =
            WholeNumber
            | AdditionExpression
            | SubtractionExpression;
                             
        // language syntax
        syntax Statement = e:MathematicalExpression StatementEnd => Statement[valuesof(e)];
        syntax Main = Statement*;
    }
}

The abstract syntax tree (AST) for the input now looks like this:

Main[
  [
    Statement[
      UnsignedNumber[
        [
          "1"
        ]
      ]
    ],
    Statement[
      SignedNumber[
        "+",
        "2"
      ]
    ],
    Statement[
      SignedNumber[
        "-",
        "3"
      ]
    ],
    Statement[
      Add[
        UnsignedNumber[
          [
            "4"
          ]
        ],
        UnsignedNumber[
          [
            "5"
          ]
        ]
      ]
    ]
  ]
]

All better.

Defining String Literals in MGrammar

2009-03-21T19:03:12-05:00:00

Consider a language authored in MGrammar that recognizes a keyword named “keyword” as well as string literals:

module MyModule
{
    language MyLanguage
    {
        // ignore whitespace
        
        syntax LF = "\u000A";
        syntax CR = "\u000D";
        syntax Space = "\u0020";
        interleave Whitespace = LF | CR | Space;
        
        // string literals
        token Quote = "\"";
        token StringLiteral = Quote a:any* Quote => StringLiteral[a];
        token Keyword = "keyword";
        
        // statements
        token Semicolon = ";";
        syntax Statement = s:(Keyword | StringLiteral) Semicolon => Statement[s];
        syntax Main = Statement*;
    }
}

Now consider some sample input:

keyword;
"this is a string";
keyword;

Given this sample input, you would expect the abstract syntax tree (AST) for this input to define two “keyword" statements and one string literal. This is, in fact, exactly what happens:

Main[
  [
    Statement[
      [
        "keyword"
      ]
    ],
    Statement[
      [
        StringLiteral[
          "this is a string"
        ]
      ]
    ],
    Statement[
      [
        "keyword"
      ]
    ]
  ]
]

But what happens when two string literals appear in the input, as in the following example?

keyword;
"this is a string";
keyword;
"this is another string";
keyword;

Given this sample input, you would expect the abstract syntax tree (AST) for this input to define two “keyword" statements and two string literals. This is, in fact, not what happens. The AST you’ll get back looks like this:

Main[
  [
    Statement[
      [
        "keyword"
      ]
    ],
    Statement[
      [
        StringLiteral[
          "this is a string\";\r\nkeyword;\r\n\"this is another string"
        ]
      ]
    ],
    Statement[
      [
        "keyword"
      ]
    ]
  ]
]

The problem lies in the grammar’s definition of a string literal. The definition states that a string literal starts with a quotation mark and finishes with a quotation mark. The input parsing engine for M, however, is as greedy as possible, swallowing as much input as possible until the syntax definition can no longer be satisfied. In this case, it finds the very last quotation mark in the input and uses that entire text as the string literal. This is not what we want.

The workaround for this is to reduce our definition of what should appear between the quotation marks from the any keyword, which states that any character can appear, to a definition which states that any character but a quotation mark can appear. The definition now looks like this:

token StringLiteral = Quote a:(any - Quote)* Quote => StringLiteral[a];

The AST for the input now looks as we expect:

Main[
  [
    Statement[
      [
        "keyword"
      ]
    ],
    Statement[
      [
        StringLiteral[
          "this is a string"
        ]
      ]
    ],
    Statement[
      [
        "keyword"
      ]
    ],
    Statement[
      [
        StringLiteral[
          "this is another string"
        ]
      ]
    ],
    Statement[
      [
        "keyword"
      ]
    ]
  ]
]

Much better!

Making MGrammar Graph Traversal Easier

2009-03-18T08:06:06-05:00:00

Do you enjoy writing the code to navigate graphs produced by MGrammar, looking for the nodes that you need? Neither do I.

I have written a small helper class to make graph navigation just a little bit easier. The class, which I have called GraphNavigator, performs all of the navigation and calls delegates when interesting nodes are found. Here is an example usage:

        1: GraphNavigator Nav = new GraphNavigator("Grammar.mgx", "JeffFerguson.Calculatix.Grammars.Calculus");

       2: Nav.AddNodeProcessorDelegate("Line", LineNodeDelegate);

       3: Nav.AddNodeProcessorDelegate("Point", PointNodeDelegate);

       4: Nav.AddNodeProcessorDelegate("Show", ShowNodeDelegate);

       5: Nav.AddNodeProcessorDelegate("StringLiteral", StringLiteralNodeDelegate);

       6: Nav.AddNodeProcessorDelegate("Slope", SlopeNodeDelegate);

       7: Nav.Parse("SourceInputFile.txt");

The key here is in the AddNodeProcessorDelegate() method. It accepts two arguments:

the name of a node
a delegate to a method to be called when the named node is found during graph traversal. In the first example on line 2, the GraphNavigator is instructed to call the LineNodeDelegate() method when a node labeled “Line” is found in the tree.

The delegates, when called, are called with two arguments:

a reference to the GraphBuilder object used to build the graph
an object representing the discovered node

An example delegate implementation is as follows:

       1: private void LineNodeDelegate(GraphBuilder builder, object LineNode)

       2: {

       3:     Line NewLine = new Line();

       4:     NewLine.Name = builder.GetSequenceElementAt(LineNode, 0) as string;

       5:     NewLine.Point2 = thisValueStack.Pop() as Point;

       6:     NewLine.Point1 = thisValueStack.Pop() as Point;

       7:     thisLines.Add(NewLine);

       8: }

This seemed, at least to me, a bit easier than doing all of the navigation inline.

The implementation of the GraphNavigator class, which really isn’t all that complicated, is as follows:

       1: using System.Dataflow;

       2: using System.IO;

       3: using System.Collections.Generic;

       4:  

       5: namespace JeffFerguson.Oslo.MGrammar

       6: {

       7:     internal class GraphNavigator

       8:     {

       9:         internal delegate void NodeProcessorDelegate(GraphBuilder Builder, object Node);

  

        private DynamicParser thisParser;

        private object thisGraphRoot;

        private Dictionary<string, NodeProcessorDelegate> thisNodeDictionary;

  

        //-----------------------------------------------------------------------------------

        //-----------------------------------------------------------------------------------

        internal GraphNavigator(string MgxFile, string LanguageName)

        {

            thisParser = DynamicParser.LoadFromMgx(MgxFile, LanguageName);

            thisNodeDictionary = new Dictionary<string, NodeProcessorDelegate>();

        }

  

        //-----------------------------------------------------------------------------------

        //-----------------------------------------------------------------------------------

        internal void AddNodeProcessorDelegate(string NodeName, NodeProcessorDelegate NodeDelegate)

        {

            thisNodeDictionary.Add(NodeName, NodeDelegate);

        }

  

        //-----------------------------------------------------------------------------------

        //-----------------------------------------------------------------------------------

        internal void Parse(string SourceFileName)

        {

            StreamReader SourceFileReader = File.OpenText(SourceFileName);

            Parse(SourceFileReader);

            SourceFileReader.Close();

            SourceFileReader.Dispose();

        }

  

        //-----------------------------------------------------------------------------------

        //-----------------------------------------------------------------------------------

        internal void Parse(StreamReader SourceStreamReader)

        {

            thisGraphRoot = thisParser.Parse<object>(null, SourceStreamReader, ErrorReporter.Standard);

            EnumerateGraph(new GraphBuilder(), thisGraphRoot);

        }

  

        //-----------------------------------------------------------------------------------

        //-----------------------------------------------------------------------------------

        private void EnumerateGraph(GraphBuilder builder, object node)

        {

            NodeProcessorDelegate NodeDelegate = null;

            object Label = builder.GetLabel(node);

  

            if (Label != null)

            {

                Identifier IdentifierLabel = Label as Identifier;

                if (IdentifierLabel != null)

                    thisNodeDictionary.TryGetValue(IdentifierLabel.Text, out NodeDelegate);

            }

            foreach (object ChildNode in builder.GetSequenceElements(node))

            {

                if ((ChildNode is string) == false)

                    EnumerateGraph(builder, ChildNode);

            }

            if (NodeDelegate != null)

                NodeDelegate(builder, node);

        }

    }

}

I hope you find it useful. Enjoy!