home | articles | site map | contacts
about us
consulting
client login
support
contacts
  Creating a C# .NET External Domain Specific Language to Map a Dungeon
  2/27/2011 (Modified 2/28/2011)
Follow PrimaryObjects on Twitter Subscribe to Primary Objects via RSS More Software Articles
by Primary Objects
enter email address
 

Introduction

Creating your own programming language can be a daunting task. After all, that's why developers choose existing programming languages, such as C#, Ruby, Perl, JavaScript or other traditional languages. However, in certain instances, a case may arise where non-developer business users may be required to configure and modify programming logic. Since not all business users can be programmers in the native programming language, it may be beneficial to implement a domain specific language that 3rd-party users can utilize. Simple examples of such a language might include Windows INI files or XML configuration files. However, we can create an even more specific custom programming language, just for our software purposes, by using an External Domain Specific Language.

Domain specific languages (DSL) can provide enhanced readability and understanding of programming code, particularly by non-developers. Where regular programming code might exist, a domain specific language can help boost productivity by allowing non-developers and business users to modify logic. In our previous article, we implemented a simple Internal DSL through the use of fluent interfaces. The logic for our internal DSL existed within the program's code, as standard C# .NET source code. However, by removing the logic from our C# .NET source, we can implement an External DSL, allowing outside users to directly manipulate program logic with our own, custom, programming language.

In this article, we'll create our own simple programming language for mapping a dungeon role-playing game. Our language will consist of an external domain specific language, including types, source code sections, and strings. Our main program will load the external DSL code file into a state machine and execute the program, allowing us to walk through a deep, dank dungeon in search of treasure!

 
C# ASP .NET External Domain Specific LanguagesA Dungeon Inside and Out

An internal DSL typically includes well-named API methods, which make it easy to match programming logic against business requirements and constructs. Since an internal DSL is written in the native programming language (ie., C# .NET), additional functionality for parsing and processing is not required. For our dungeon example, an internal domain specific language might look similar to the following:
void Main()
{
   State emptyRoom = new State("Empty Room");
   State treasureRoom = new State("Treasure Room");

   Event southEvent = new Event("south");
   Event northEvent = new Event("north");

   emptyRoom.AddTransition(southEvent, treasureRoom);
   treasureRoom.AddTransition(northEvent, emptyRoom);
}

In the above example, we've defined C# .NET code to implement a state machine with two states, representing rooms in the dungeon. Since the code is hard-coded, users would be unable to modify the logic. We can extend our application by allowing configuration through an external domain specific language, namely, a custom programming language. The custom programming language would only include terms needed to produce desired functionality, which in our case, includes traversing a set of rooms (ie., states) and invoking actions.

Sweeping the Dungeon Clean

Similar to the above internal DSL, an example external domain specific language might appear as follows:

events
  moveSouth south
  moveNorth north
end

state emptyRoom
  "Empty Room"
end

state treasureRoom
  "Treasure Room"
end

connect emptyRoom to treasureRoom by moveSouth
connect treasureRoom to emptyRoom by moveNorth

The above code requires no knowledge of C# .NET, nor any other programming language, and yet it allows the user to implement a fully operating program. The DSL created further down in this article will be similar to the above example, but we'll be adding an additional construct to include actions within a state.

Speaking the Language of the Dungeon Dwellers

To get started, we'll want to define some basic programming terms, which can be utilized in the external domain specific language source code. Since we'll be configuring a basic state machine, we can limit the required programming concepts to include commands, events, and states. To avoid complex parsing, we'll simply tokenize the source code by spaces, and parse by section. We'll ignore looping, function calls, and other more complicated constructs. We'll include the following rules:

The keyword "end" terminates a section, resetting the state machine.
The keyword "commands" begins a section for defining state machine commands (actions).
The keyword "events" begins a section for defining state machine events, used for moving to the next state.
The keyword "state" begins a section for defining a state. A state may include actions and transitions.
The keyword "action" defines a named action to be executed by a state.
The keyword "transitions" beings a section within a state for triggering target states by event.
The keyword "." terminates a transitions section.
The keyword "=>" defines a mapping for a transition, linking an event to a state.

We can choose any type of character or phrase to use in our domain specific languages. In this example, I've chosen some relatively simple keywords and characters, such as the period character to end a transition section, and the familiar C# .NET lambda symbol to mark a transition of event to state.

Hello, Dungeon!

An example for our language would be as follows:

commands
  sayHello "Hello World"
  sayGoodbye "Goodbye world"
end

events
  sayHi hi
  sayBye bye
end

state idle
  action sayHello
  transitions
     sayBye => byeState
  .
end

state byeState
  action sayGoodbye
  transitions
     sayHi => idle
  .
end

Loading this code into our state machine would produce the following result:

Executing idle
sayHello (Hello World)

> bye

Executing byeState
sayGoodbye (Goodbye world)

> hi

Executing idle
sayHello (Hello World)

As you can see in the above example, we've created a program for defining a simple toggle state machine. The machine consists of two states: Hello and Goodbye (or more precisely, idle and byeState).

Our Own Frankenstein Brain

To get started, we'll implement a basic state machine for storing the loaded program code. The state machine will consist of States, Commands, Events, and Transitions. By implementing the state machine in an object oriented design, we can easily instantiate the state machine parts based upon the code file. We'll start by defining the basic components of our state machine, which include Commands and Events.

A Nameless Event

We'll define an abstract Event class, which will serve as the base class for our Commands and Events. This base class will include a Name and a Code, as follows:
    public abstract class AbstractEvent
    {
        public string Name;
        public string Code;

        public AbstractEvent()
        {
        }

        public AbstractEvent(string name, string code)
        {
            Name = name;
            Code = code;
        }
    }

We can then define the Command and Event class as follows:

    public class Command : AbstractEvent
    {
        public Command()
        {
        }

        public Command(string name, string eventCode)
        {
            Name = name;
            Code = eventCode;
        }
    }

    public class Event : AbstractEvent
    {
        public Event()
        {
        }

        public Event(string name, string eventCode)
        {
            Name = name;
            Code = eventCode;
        }
    }

The All-Powerful State Class

We can move on to implementing our State class, which will serve as the overall "node" object for our state machine. In our dungeon example, each State object will represent a room in the dungeon. We can define the State as follows:

    public class State
    {
        public string Name;
        private List<Command> _actions = new List<Command>();
        private Dictionary<string, Transition> _transitions = new
Dictionary<string, Transition>(); public State(string name) { Name = name; } public void AddTransition(Event anEvent, State state) { if (state != null) { _transitions.Add(anEvent.Code, new Transition(this, anEvent, state)); } } public void AddAction(Command action) { _actions.Add(action); } public List<State> GetTargets() { List<State> result = new List<State>(); foreach (KeyValuePair<string, Transition> item in _transitions) { result.Add(item.Value.Target); } return result; } public List<string> GetEventCodes() { List<string> result = new List<string>(); foreach (KeyValuePair<string, Transition> item in _transitions) { result.Add(item.Value.EventCode); } return result; } public bool HasTransition(string eventCode) { return _transitions.ContainsKey(eventCode); } public State GetTargetState(string eventCode) { return _transitions[eventCode].Target; } public void Execute() { Console.WriteLine("Executing " + Name); foreach (Command command in _actions) { // Execute command Console.WriteLine(command.Name + " (" + command.Code + ")"); } } }

In the above code, we've defined a State object. The State object includes a list of Transitions and a list of Actions. Actions will be executed when the state is active. In our example, an action simply prints text. However, a state could be expanded to provide a variety of features or calculations. Transitions will map paths from this state to the next. Each transition will contain an event (such as responding to a code), which triggers the transition to the next state.

Arms and Legs for our Beast

With our State object defined, we can move on to connecting them together with Transitions. The Transition class can be defined as follows:

    public class Transition
    {
        public State Source;
        public State Target;
        public Event Trigger; 
        public string EventCode
        {
            get
            {
                return Trigger.Code;
            }
        }

        public Transition()
        {
        }

        public Transition(State source, Event trigger, State target)
        {
            Source = source;
            Trigger = trigger;
            Target = target;
        }
    }

The Transition class contains a Source state, a Target state, and a Trigger. In order for a State (the Source) to transition to the next State (the Target), an event will need to fire (the Trigger). The Transition class is the key to link States together, mapping a complete state machine object.

The Machine

Finally, we can implement the encapsulating StateMachine class, which holds the entire state machine mapping. Since each State is connected to the next via Transition links, we only need to point to the starting State. Just as with a linked list, we can traverse the state machine by following the paths. Our StateMachine can be defined as follows:

    public class StateMachine
    {
        public State Start;
        private List<Event> _resetEvents = new List<Event>();

        public StateMachine(State start)
        {
            Start = start;
        }

        public List<State> GetStates(State start)
        {
            List<State> result = new List<State>();

            // Add the starting state.
            result.Add(start);

            // Add all reachable states.
            result.AddRange(start.GetTargets());

            return result;
        }

        public void AddResetEvent(Event anEvent)
        {
            _resetEvents.Add(anEvent);
        }

        public bool IsResetEvent(string eventCode)
        {
            foreach (Event anEvent in _resetEvents)
            {
                if (anEvent.Code == eventCode)
                {
                    return true;
                }
            }

            return false;
        }

        public List<string> GetResetEventCodes()
        {
            List<string> result = new List<string>();

            foreach (Event anEvent in _resetEvents)
            {
                result.Add(anEvent.Code);
            }

            return result;
        }
    }

The StateMachine contains a starting State, which can be traversed through to the subsequent states. We've also included a few utility methods to make our custom applications a little more interesting. These methods include getting a list of all states in the state machine and adding reset events (which exits the current state and immediately resets the state machine).

Giving our Monster a Go

With the state machine defined, we can actually use it right now, with a simple internal domain specific language. We can manually instantiate states and connect them with transitions.

void Main()
{
  State idle = new State("idle");
  State waitingForByeCommand = new State("waitingForByeCommand");

  Event sayHi = new Event("sayHi", "hi");
  Event sayBye = new Event("sayBye", "bye");

  idle.AddTransition(sayBye, waitingForByeCommand);

  waitingForByeCommand.AddTransition(sayHi, idle);

  StateMachine machine = new StateMachine(idle);
  Controller controller = new Controller(machine);

  ...
}

The above program would execute our basic state machine, although the logic is hard-coded within C# .NET. By de-coupling the programming logic from C# and providing a custom programming language, as an external domain specific language, we can allow any user to modify and/or create custom applications with a simple text file.

Re-working the Main Program

We can modify the above main program, to allow for reading a custom programming file and executing the state machine, as follows:

static void Main()
{
  string command = "";

  // Get application folder.
  string path = Path.GetDirectoryName(Assembly.GetEntryAssembly().Location);

  // Setup a state machine by reading the external domain specific language program.
  Parser parser = new Parser();
  StateMachine machine = parser.GetStateMachine(path + "\\dungeon.txt");
  Console.WriteLine("Loading of External DSL completed.\n");

  // Setup controller to run state machine.
  Controller controller = new Controller(machine);

  // Display some help.
  Console.WriteLine("> Q = Quit, ? = Available Commands");
  Console.WriteLine("> Entering the dungeon.");

  // Execute the starting state.
  controller.CurrentState.Execute();

  // Read commands from user to activate state machine.
  while (command.ToLower() != "q")
  {
    Console.Write("> ");

    // Read a command.
    command = Console.ReadLine();

    // Send the command to our state machine.
    HandleCommand(controller, command);
  }
}

private static void HandleCommand(Controller controller, string command)
{
  if (!controller.Handle(command))
  {
    if (command == "?")
    {
      // Display available commands for the given state.
      foreach (string eventCode in controller.CurrentState.GetEventCodes())
      {
        Console.WriteLine(eventCode);
      }
    }
    else if (command.ToLower() != "q")
    {
      Console.WriteLine("Huh?");
    }
  }
}

The above main program loads custom programming code from a text file. The contents are then parsed and loaded into the state machine. We can then execute the state machine based upon input from the command line. The HandleCommand helper method simply sends the user command from the command-line to the Controller, for processing in the state machine.

Speaking the Language of the Villagers

The state machine implementation is fairly basic in nature, which will help us in parsing an external domain specific language. One of the more complex tasks in implementing an external domain specific language is the parsing of source code. While internal domain specific languages (ie., fluent interfaces, well-named APIs, method chaining, etc) come with built-in parsing support via the native programming language (C#, Java, Lisp, etc), our custom external DSL will need its own parser defined. A programming language parser can be as simple or complex as you need. You could choose to handle a variety of formatting, special characters, comments, and more. However, for our example, we'll simply parse by spaces and toggle the reading of sections by tracking our state in the code file.

Since we'll be tracking our own state as we read through the code file, we can actually take advantage of our own state machine class. We'll configure our own internal state machine to parse the code file and instantiate the user's (external) state machine.

Once our parser state machine is configured, we can tokenize the code file input, and process each token based upon the parser's current state as follows:

        private StateMachine ParseDSL(string content)
        {
            StateMachine stateMachine = null;
            State currentState = null;
            Command command = null;
            Event anEvent = null;
            State state = null;
            Transition transition = null;

            // Encode strings before parsing.
            content = Utility.PreProcess(content);

            string separators = " \r\n\t";
            string[] tokens = content.Split(separators.ToCharArray());

            foreach (string token in tokens)
            {
                // Decode strings from token.
                string tokenValue = Utility.PostProcess(token);

                string tokenLwr = tokenValue.ToLower();

                // Pass the token to our state machine to handle.
                bool handled = _controller.Handle(tokenLwr);

                if (!handled && tokenLwr.Length > 0)
                {
                    // Process the token under our current state.
                    switch (_controller.CurrentState.Name)
                    {
                        case "waitingForCommand":
                        {
                            // Read a Command Name.
                            command = new Command();
                            command.Name = tokenValue;

                            // Move state to read Command Code.
                            _controller.Handle(_startCode);

                            break;
                        }
                        case "waitingForCommandCode":
                        {
                            // Read a Command Code.
                            command.Code = tokenValue;

                            _commandList.Add(command.Name, command);

                            // Move state back to read Command Name.
                            _controller.Handle(_endCode);

                            break;
                        }
                        case "waitingForEvent":
                        {
                            // Read an Event Name.
                            anEvent = new Event();
                            anEvent.Name = tokenValue;

                            // Move state to read an Event Code.
                            _controller.Handle(_startCode);

                            break;
                        }
                        case "waitingForEventCode":
                        {
                            // Read an Event Code.
                            anEvent.Code = tokenValue;

                            _eventList.Add(anEvent.Name, anEvent);

                            // Move state back to read an Event Name.
                            _controller.Handle(_endCode);

                            break;
                        }
                        case "waitingForState":
                        {
                            // Read a State Name, stay in this state until command read.
                            state = new State(tokenValue);
                            currentState = state;

                            _stateList.Add(tokenValue, state);

                            break;
                        }
                        case "waitingForAction":
                        {
                            // Read an Action Name.
                            state.AddAction(_commandList[tokenValue]);

                            // Move state back to reading a State.
                            _controller.Handle(_endCode);

                            break;
                        }
                        case "waitingForTransition":
                        {
                            // Read a Transition Trigger.
                            transition = new Transition();
                            transition.Source = currentState;
                            transition.Trigger = _eventList[tokenValue];

                            break;
                        }
                        case "waitingForTransitionState":
                        {
                            // Read a Transition Target.
                            if (_stateList.ContainsKey(tokenValue))
                            {
                                transition.Target = _stateList[tokenValue];
                                currentState.AddTransition(transition.Trigger,
transition.Target); } else { // Add reference to bind later. _symbolTableForStateList.Add(new
Utility.SymbolTableForState(currentState, transition, "Target",
_stateList, tokenValue)); } // Move state back to reading a Transition. _controller.Handle(_endCode); break; } } } } // Resolve any references to unknown states. Utility.ResolveReferences(_symbolTableForStateList); // Create the state machine with the starting state. stateMachine = new StateMachine(_stateList["idle"]); return stateMachine; }

In the above code, we loop through each token read from the code file. Depending on our parser's current state, we process the token accordingly (such as creating a new State or Transition object, setting the Name or Code property, etc). Once completed, we resolve any references and return the final state machine. 

A Little Wizard Magic - Resolving References

The parser itself is fairly straight-forward. It simply processes each token in the text file based upon the parser's state. However, with an external domain specific language, a common issue that arises is being able to reference an object that has yet to be defined. In our example, we'll be referencing states that are defined further down in the code file. If we were to simply add a transition to the named state, our program would crash upon assigning a null reference. This is due to the fact that the state doesn't yet exist. To correct this issue, we can check for the case (waitingForTransitionState) to identify when a state is ready that is not yet within our state dictionary. We can then add the state name and context to a symbol table and resolve the reference upon completion of parsing.

We can take advantage of C# .NET reflection to resolve the state reference by assigning the located object to the state in context. After adding the transition, the state will be connected to the context state, thus resolving the reference.
        public static void ResolveReferences(List<Utility.SymbolTableForState>
symbolTableForStateList) { // Go through each item added to the lookup state list to resolve. for (int i = 0; i < symbolTableForStateList.Count; i++) { // Get the type and field for the target property name to assign. Type type = symbolTableForStateList[i].Transition.GetType(); FieldInfo field = type.GetField(symbolTableForStateList[i].PropertyName); // Get the state and value for the transition. object obj = symbolTableForStateList[i].Transition; object value = symbolTableForStateList[i].
Dictionary[symbolTableForStateList[i].Token]; // Assign the state to the transition. field.SetValue(obj, value); // Add the transition to the parent state. Transition transition = (Transition)obj; symbolTableForStateList[i].CurrentState.
AddTransition(transition.Trigger, transition.Target); } }

Our Dungeon Program Rocks

We've now completed our C# .NET external domain specific language implementation and can now create our program code file. We'll use our custom programming language, as defined by the parser, to create our dungeon program. Note, that since we parse upon spaces, the code file is quite flexible with regard to new lines, spacing, indentation, and even bad characters (all of which are simply ignored when processing). Our dungeon is defined as follows:

commands
  tree "You see a circle of trees."
  pit "You see a dark bottomless pit."
  light "You see an endless white light."
  box "You see an ominous box with a smaller glitter inside."
  treasure "You find a pile of sparkling treasure!"
  fall "You try to move past the pit, but slip and fall into oblivion."
  reset "Type 'reincarnate' for a new life."
end

events
  moveNorth north
  moveSouth south
  moveEast east
  moveWest west
  openBox open
  reincarnate reincarnate
end

state idle
  action light
  transitions
    moveNorth => treeState
    moveSouth => pitState
  .
end

state treeState
  action tree
  transitions
    moveSouth => idle
  .
end

state pitState
  action pit
  transitions
    moveNorth => idle
    moveSouth => fallState
    moveEast => boxState
  .
end

state boxState
  action box
  transitions
    moveWest => pitState
    openBox => treasureState
  .
end

state treasureState
  action treasure
  transitions
    moveWest => pitState
  .
end

state fallState
  action fall
  transitions
    reincarnate => idle
  .
  action reset
end

In the above external domain specific language, we've defined several states. Note, while we've used indentation for readability, all extraneous spacing and new lines are ignored. Since we're using a state machine for our parser, we can include any combination of sections, provided they contain the proper enclosing section names. For example, each state defines actions and transitions. We can include the actions at the top of the state definition, at the bottom, or spread between the top and bottom. In addition, the order of states is not important, since we resolve references to unknown states at the end of parsing.

Crawling the Dungeon

Running the example program with our dungeon.txt code file produces the following output:

...
Executing idle
Executing waitingForState
Executing waitingForAction
Executing waitingForState
Executing waitingForTransition
Executing waitingForTransitionState
Executing waitingForTransition
Executing waitingForState
Executing waitingForAction
Executing waitingForTransitionState
Executing waitingForTransition
Executing waitingForState
Executing waitingForAction
Executing waitingForState
Executing idle
Loading of External DSL completed.

> Q = Quit, ? = Available Commands
> Entering the dungeon.
Executing idle
light (You see an endless white light.)
> ?
north
south
> north
Executing treeState
tree (You see a circle of trees.)
> south
Executing idle
light (You see an endless white light.)
> south
Executing pitState
pit (You see a dark bottomless pit.)
> east
Executing boxState
box (You see an ominous box with a smaller glitter inside.)
>?
west
open
> open
Executing treasureState
treasure (You find a pile of sparkling treasure!)
> q

A Challenge, Young Warrior

For a fun excercise, feel free to extend the dungeon code file with additional rooms, actions, story-line, and goals! Using the domain specific language, you could easily extend the application to include portals, penalties, items, mazes, and more. Feel free to post a link to your code file in the comments below, so others can try it out!

Download @ GitHub

You can download the project source code on GitHub by visiting the project home page.

 Conclusion

Domain specific languages in C# .NET can provide both enhanced readability and powerful functionality, allowing non-developer users to modify and/or create custom programming logic within your software. While internal DSLs are often easier to create based upon built-in compilation, external DSLs can provide enhanced power and flexibility for manipulating logic. A variety of patterns exist for implementing DSLs, including common formats such as INI, XML, or custom programming languages. By allowing users to modify and enhance program code, software applications can maintain a longer life-span and provide extended feature functionality into the future.

About the Author

This article was written by , founder and chief developer of Primary Objects, a software and web application development company. You can contact Primary Objects regarding your software development needs at http://www.primaryobjects.com

   
comments powered by Disqus
Profile
Learn more about Primary Objects and our goals ..  More
09/09/2013
Primary Objects releases SentimentView Twitter sentiment analysis engine .. More
05/31/2013
Primary Objects releases ColorBot interactive machine learning, AI .. More
Home | About Us | Services | Client Login | Job Opportunities | Contact Us
Copyright © Primary Objects 2013
Privacy Policy
Follow us on Twitter