imageMy main area of interest in programming during my school and university years was in computer graphics. I did a lot of hobby programming with games, like the Quake 3 mod Rocket Arena 3, and specifically with fractal graphics. This generated a quite serious outcome during a course on research methodologies where I together with a friend wrote a scientific paper on 4D Julia rendering.

The 2D Julia fractal to the left is a shape that everyone recognizes. The simple formula that defines the Julia and Mandelbrot set is also something that many know:

image

The variable z and constant c are in a normal 2D Julia set complex numbers. A complex number is a tuple of two values, a real and imaginary part, which can be visualized in the complex pane, which is a 2D geometric representation of complex numbers. 

image

Complex numbers can be extended to a four-tuple value with one real and three imaginary units. These are called Quaternions and can be visualized as a four dimensional space. When using the Julia equation with Quaternions we can define a 4D dimensional object. It becomes a lot trickier to visualize however. What is needed is a 4D camera from which you can cast rays (vectors). The algorithm traverse these vectors step by step (from the camera) and for each point the Julia equation is recursively run to determine if the point is part of the Julia set or not.

Here is 2D illustration of how a ray is thrown and sampled at regular intervals:

image

The process of sampling each point can be very time consuming so the distance between sample points can not be to small, but it can not be the to high either as it directly relates to the point resolution you get as exemplified by these two images:

image

The left image has a higher distance between sample points compared to the image to the right. You can clearly see the artifact of how the algorithm works in the rings in the image to the left (each ring is a sample point along the ray). To optimise the sampling process we can move back after a sample hit and then move forward in smaller steps.

image

Here is the Julia set viewed from the side, the constant (Julia seed) is (0.4 0.5i 0j 0k).

image

The raytracing gives coordinates in a 4D space that belongs to the Julia set, each point can be given a color depending on how far the point is from the camera (as above). Further each point can be lighted and shaded. To accurately light a point you need it's surface normal, these normals can be calculated by looking at the relative heights of neighbouring points (pixels).

image

The most fascinating aspect of 4D Julia sets can be viewed when you animated them. To animate them you render pictures with small change to the Julia seed constant or to the camera position. What is particularly interesting is when you move the camera in the fourth dimension. What you get is an animation of how the Julia set looks like from different four dimensional angles. It is hard to describe what happens, but basically the shape morphs into different shapes when viewed from different four dimensional angles :)

During the process of coding our raytracer we accidentally made an error in the quaternion multiplication, which resulted in a very strange shape:

image

We named these über quaternions. Later when we were writing the paper we discovered that we had used commutative multiplication rules which resulted in hypercomplex numbers.

Here is another picture showing how the shape gets more detail depending on the number of times you recurse over the Julia algorithm:

image

Isn't it fascinating and beautiful how such a simple algorithm can define such an intricate structure? The raytracer was witten in C++ and my plan is to (someday, maybe next year) port / rewrite it in F# :)

The paper is very technical so I doubt that it will interest many, but here is the link and abstract:

By using rules defined by quaternion algebra the Julia set can be extended to four dimensions. Techniques for visualizing the four dimensional Julia set as a three dimensional object has previously been explored, however those techniques usually ignores the fourth dimension. In this paper we describe our attempt to extend the already established technique of ray tracing Julia sets to fully incorporate its four dimensional properties. We also discuss an optimisation algorithm that drastically increases the amount of details in images and shortens rendering time.

Link to the paper: Raytracing4D.pdf

Movies:

  1. 4D Camera move: 4d_cameramove.avi
  2. Another 4D Camera move: r4d.avi
  3. Moving the seed in circle (on the complex pane): cycle.avi
  4. Moving the seed from left to right (on the complex pane): cwalk.avi
  5. Moving the camera in a circle around the hypercomplex julia set:  uber_highres.avi

It is worth pointing our that in the two first movies with 4D camera movies it is only the camera that is moving the julia seed never changes, only the angle that the object is viewed at. The paper was written with LaTeX, which was a lot of fun to learn, although quite hard to use. But the output looks so much more professional.

Were you also a graphics geek? Did you write a flame or plasma effect in assembler, did you use allegro to write DOS games? I sure did :)

My first try with writing a DSL for WatiN was such fun experience that I decided to have another go. I wanted to try to create something with a little more natural sentence like syntax. Here are some tests showing of the new syntax:

--- Can filter by author ---
goto address "http://demo.codesaga.com/". 
click the link with the text "MvcContrib".
select "torkel" from the list with the id #author-fitler.
page should contain the text "Filtering view by author torkel".

--- Can filter by date --- 
goto address "http://demo.codesaga.com". 
click the link with the text "xUnit".
set focus to the textbox with the id #date-filter.
click the link with the text "2".
page should contain the text "Filtering view by date".

--- Can expand diff in changsest view (via ajax) ---
goto address "http://demo.codesaga.com/history/xUnit?cs=25434".
click the element with the class name @cs-item-diff.
page should contain the element with the class name @code-cell, wait for
it 3 seconds.

The added verbosity might be to much for programmers but the point of making something like this more readable is to make acceptance tests understandable by non-programmers. I am not saying that acceptance tests is something that shouldn't involve developers. But having them accessible to for non-programmers can be very valuable. I am not sure why, I kind of like the verbosity in this case (I usually don't). It would be very easy to make some words optional so one can write "click #edit" as a shortening of "click the link with the id #edit".

The MGrammar for this language:
module CodingInstinct {
    import Language;
    import Microsoft.Languages;
    export BrowserLang;
 
    language BrowserLang {
                  
        syntax Main = t:Test* => t;
        
        syntax Test = name:TestName
            a:ActionList => Test { Name { name }, ActionList { a } };
                                      
        syntax ActionList
          = item:Action => [item]
          | list:ActionList item:Action => [valuesof(list), item];
                             
        syntax Action = a:ActionDef "." => a;
        syntax ActionDef
            = a:GotoAction => a
            | a:ClickAction => a
            | a:SelectAction => a
            | a:TextAssert => a
            | a:ElementAssert => a
            | a:TypeAction => a
            | a:SetFocusAction => a;
                            
        syntax GotoAction = "goto" "address"? theUrl:StringLiteral
            => GotoAction { Url { theUrl } };
                
        syntax ClickAction = "click" "the"? ("link" | "element")? ec:ElementConstraint 
            => ClickAction { Constraint { ec } };
        
        syntax TypeAction = "type" value:StringLiteral "into" "the" "textbox" ec:ElementConstraint
            => TypeAction { Value { value> }, Constraint { ec } };
            
        syntax SelectAction = "select" value:StringLiteral "from" "the" "list" ec:ElementConstraint
            => SelectAction { Value { value }, Constraint { ec } };
        
        syntax TextAssert = "page should contain" "the" "text" text:StringLiteral 
            => TextAssert { Value { text } };
            
        syntax ElementAssert = "page should contain" "the" "element" ec:ElementConstraint 
            wait:ElementWait?
            => ElementAssert { Constraint { ec }, Wait { wait } };
            
        syntax ElementWait = "wait" "for" "it" sec:Base.Digits ("second" | "seconds") 
            => sec;
            
        syntax SetFocusAction = "set" "focus" "to" "the" "textbox" ec:ElementConstraint 
            => SetFocusAction { Constraint { ec } };
                 
        syntax ElementConstraint
            = "with" "the" "text" name:StringLiteral => TextConstraint { Value { name } } 
            | "with" "the" "id" name:ElementId => IdConstraint { Value { name } } 
            | "with" "the" "class" "name" name:ElementClass => ClassConstraint { Value { name } };
                  
        token TestName = "--- " (Base.Letter|Base.Whitespace)+ " ---";    
        token ElementId = '#' (Base.Letter|'-'|'_')+;
        token ElementClass = '@' (Base.Letter|'-'|'_')+;
                                                    
        interleave Skippable
          = Base.Whitespace+ 
          | Language.Grammar.Comment
          | Base.NewLine
          | ",";
                
        syntax StringLiteral
          = val:Language.Grammar.TextLiteral => val;        
    }

}

Another improvement in this new DSL syntax is the format for specifying an element or class name. In the above grammar these are defined as tokens, where ids begin with # and class names with @ followed by any word. The nice thing with a token is that you can add a Classification attribute to it where you specify what token category it belongs to. Classification names are linked to font and color styles (i.e. syntax highlighting).

image 

To get the DSL to actually execute you need the MGraph node tree that the parser spits. The MGraph is not something that you want work with directly as it is pretty low level. When I did the first version of this WatiN DSL I spent the majority of the time figuring out how to parse and deserialize the MGraph into a custom set of AST classes. In the process I wrote a very basic generic MGraph -> .NET classes deserializer.

Luckily, as Don Box pointed out in the comments to my previous post, SpankyJ has written a much better deserializer that converts the MGraph into Xaml via an MGraphXamlReader. It was very easy to switch to his implementation as he had some useful method extensions on the DynamicParser.

Example:

DynamicParser parser = LoadExampleGrammar();

var xamlMap = new Dictionary<Identifier, Type>
    { { "Person", typeof(Person) } };

var people = parser.Parse<List<object>>(testInput, xamlMap);

But having to define the mapping between MGraph node names and .NET classes manually like this was something I did not like. I wanted something with a more convention based approach. Roger Alsing is also doing some work with MGrammar and he gave me this great piece of code which I modified slightly:

public Dictionary<Identifier, Type> GetTypeMap()
{
  return Assembly
    .GetExecutingAssembly()
    .GetTypes()
    .Where(t => t.Namespace.StartsWith("WatinDsl.Ast"))
    .Where(t => !t.IsAbstract)
    .ToDictionary
    (
      t => (Identifier)t.Name,
      t => t
    );
}

Pretty simple code really,  it just creates a dictionary of all the non abstract types in the namespace WatinDsl.Ast.

I basically rewrote the AST for this new version, now most actions have a Constraint property that determines what element the action is targeting. Here is an sample:

public class ClickAction : IAction
{
    public IElementConstraint Constraint { get; set; }
    
    public void Execute(IBrowser browser)
    {
        browser.Element(Constraint.Get()).Click();
    }
}

public class IdConstraint : IElementConstraint
{
  public string Value { get; set; }

  public AttributeConstraint Get()
  {
    return Find.ById(Value.Substring(1));
  }
}

For the full code: WatinDsl_2.zip

This is still just an experimental spike for learning MGrammar, but it is also an interesting scenario for exploring the potential in a browser automation language. Is a browser automation language, like the one I have created, something that you would find useful? What would your syntax look like?

Working with MGrammar in Intellipad's split view in fullscreen on a 26" monitor is pure joy :)

image

To change the default color schema in intellipad is easy, just modify the Intellipad\Settings\ClassificationFormats.xcml file. It looks like this:

<act:Export Name='{}{Microsoft.Intellipad}ClassificationFormat'>
  <ls:ClassificationFormat Name='Unknown' 
                           FontSize='13' 
                           FontFamily='Consolas' 
                           Foreground='#FFEEEEEE' />
</act:Export>
<act:Export Name='{}{Microsoft.Intellipad}ClassificationFormat'>
  <ls:ClassificationFormat Name='Numeric' 
                           Foreground='#FFEEEEEE' />
</act:Export>

///....

The hard part was to figure out how to change the background color, which currently can't be done by changing some xml config file but can be accomplished with a small python snippet.

@Metadata.CommandExecuted('{Microsoft.Intellipad}BufferView', 
        '{Microsoft.Intellipad}SetBlackBackground', 
        'Ctrl+Shift+F2')
def SetBlackBackground(target, bufferView, args):
   bufferView.TextEditor.TextView.Background = System.Windows.Media.Brushes.Black

I got this snipped from Vijaye Raji (SUPER NINJA). You got to digg someone with SUPER NINJA in their Microsoft email display name :)

image

If you are attending the Øredev conference this week, be sure to checkout the ALT.NET track. First out is Joakim Sundén with "ALT.NET - Are you ready for the Red Pill?", I just reviewed his slides and it's a great introduction to ALT.NET, giving both a detailed background and description of the term without being divisive or elitist. 

I am not attending Øredev this year, I wish I was, besides the ALT.NET track their is a terrific DDD track with presenters like Jimmy Nilsson and Eric Evans. Robert C. Martin is also presenting a keynote and a talk on clean code.

The Cornerstone event Pimp My Code was finally announced today (after some series of delays). I was originally scheduled to talk on Dependency Inversion Principle and Inversion of Control Containers, but due to the delays and the reorganizing from single day conference to a small evening event the schedule was reworked, so I will not be doing the talk. Instead I will hopefully get the chance to perform the talk at Developer Summit next year (probably in mars).

I get mails from time to time asking for my visual studio color scheme settings. The code examples on this blog use the same color scheme I use in visual studio, which is a scheme I tweaked together about 2 years ago after reading this post by Jeff Atwood, in that post he had this screenshot:

 image

I really liked how this looked, so I spent the next weak creating and constantly tweaking a code and html color scheme inspired by the above image (I did manage to get some coding done as well).

This is the result:

image

This is how xml looks like:

image

I was really happy with how the xml color scheme turned out :)

So If you like it:

Updated: Now the files only contain "Fonts & Color" settings.

The only part of the Oslo presentations at PDC that caught my attention was the MGrammar language (Mg).

The Mg language provides simple constructs for describing the shape of a textual language – that shape includes the input syntax as well as the structure and contents of the underlying information

The interesting part of Mg is how it combines schema, data transformation, and functional programming concepts to define rules and lists. Creating and designing a language is hard and requires some knowledge of how parsers work, as Frans Bouma, and Roger Alsing has pointed out, Mg and Oslo is not going to change that. I haven't work professionally with language parsers, I have written a C like language compiler using LEX and YACC, but that was many years ago. One of the most popular tools for language creation today is ANTLR, it would be great if someone knowledgeable in both ANTLR and Mg would write a comparison.

Anyway, I was intrigued by Mg so I decided to play around with it. I decided to create a simple DSL over the WatiN browser automation library. I wanted to be able to execute scripts that looked like this:

test "Searching google for watin"
    goto "http://www.google.se"
    type "watin" into "q"
    click "btnG"
    assert that text "WatiN Home" exists
    assert that element "res" exists
end

Maybe not the best possible DSL for browser testing, one could probably come up with something even more natural sounding. But it will be sufficient for now. To start creating the language specification I started Intellipad (a application that is included in the Oslo CTP). To get the nice three pane view, with input, grammar, and output window is kind of tricky. First switch the current mode to MGrammarMode, this is done by pressing Ctrl+Shift+D to bring up the minibuffer, then enter "SetMode('MGMode')". Now the MGrammar Mode menu should be visible, from this menu select "Tree Preview", this will bring up a open file dialog, in this dialog create an empty .mg file and select that file.

image

I entered my goal DSL in the dynamic parser window and began defining the syntax and data schema. After an hour of trial and error I arrived at this grammar:

module CodingInstinct {
    import Language;
    import Microsoft.Languages;
    export BrowserLang;
 
    language BrowserLang {
                  
        syntax Main = t:Test* => t;
        
        syntax Test = TTest name:StringLiteral a:ActionList TEnd
            => Test { Name { name }, a };
                       
        syntax ActionList
          = item:Action => ActionList[item]
          | list:ActionList item:Action => ActionList[valuesof(list), item];
                             
        syntax Action 
            = a:GotoAction => a
            | a:TypeAction => a
            | a:ClickAction => a
            | a:AssertAction => a;
            
        syntax GotoAction = TGoto theUrl:StringLiteral => GotoAction { Url { theUrl } };
        syntax TypeAction = TType text:StringLiteral TInto id:StringLiteral 
             => TypeAction { Text { text }, ID { id } };
        
        syntax ClickAction = TClick id:StringLiteral => ClickAction { ID { id } }; 
        syntax AssertAction = 
            TAssert TText text:StringLiteral TExists => AssertAction { TextExists { text } }
          |
            TAssert TElement element:StringLiteral TExists => AssertAction { ElementExists { element } }           ;
        
        @{Classification["Keyword"]} token TTest = "test";            
        @{Classification["Keyword"]} token TGoto = "goto";
        @{Classification["Keyword"]} token TEnd = "end";
        @{Classification["Keyword"]} token TType = "type";
        @{Classification["Keyword"]} token TInto = "into";
        @{Classification["Keyword"]} token TClick = "click";
        @{Classification["Keyword"]} token TAssert = "assert that";
        @{Classification["Keyword"]} token TExists = "exists";        
        @{Classification["Keyword"]} token TText = "text";        
        @{Classification["Keyword"]} token TElement = "element";
        
        interleave Skippable
          = Base.Whitespace+ 
          | Language.Grammar.Comment;       
                
        syntax StringLiteral
          = val:Language.Grammar.TextLiteral => val;        
    }

}

I have have no idea if this is a reasonable grammar for my language or if it can be written in a simpler/smarter way. The grammar generates this M node graph:

[
  Test{
    Name{
      "\"Search google for watin\""
    },
    ActionList[
      GotoAction{
        Url{
          "\"http://www.google.se\""
        }
      },
      TypeAction{
        Text{
          "\"asd\""
        },
        ID{
          "\"google\""
        }
      },
      ClickAction{
        ID{
          "\"btnG\""
        }
      },
      AssertAction{
        TextExists{
          "\"text\""
        }
      },
      AssertAction{
        ElementExists{
          "\"asd\""
        }
      }
    ]
  }
]

The problem I had now was how to parse and execute this graph, I could not find any documentation for how to generate C# classes from M schema. What is included in the CTP is a C# library to navigate the node graph that the language parser generates. This node graph is not very easy to work with, I wanted a GotoAction to be automatically mapped to a GotoAction class, the TypeAction to a TypeAction class, etc. To accomplish this I wrote a simple M node graph deserializer.

This is the AST I want the M node graph to deserialize to:

public class Test
{
  public string Name { get; set; }
  public IList<IAction> ActionList { get; private set; }

      public Test()
      {
          ActionList = new List<IAction>();
      }
}

public interface IAction
{
    void Execute(IBrowser browser);
}

public class GotoAction : IAction
{
    public string Url { get; set; }

    public void Execute(IBrowser browser)
    {
        browser.GoTo(Url);
    }
}

It was quite tricky to write a generic deserializer, mostly because the M node object graph is kind of weird (Nodes, Sequences, Labels, Values, EntityMemberLabels, etc). Here is the code:

public class MAstDeserializer
{
    private GraphBuilder builder;

    public MAstDeserializer()
    {
        this.builder = new GraphBuilder();
    }

    public object Deserialze(object node)
    {
        if (builder.IsSequence(node))
        {
            return DeserialzeSeq(node).ToList();
        }

        if (builder.IsNode(node))
        {
            return DeserialzeNode(node);
        }

        return null;
    }

    private object DeserialzeNode(object node)
    {
        var name = builder.GetLabel(node) as Identifier;

        foreach (var child in builder.GetSuccessors(node))
        {
            if (child is string)
            {
                return UnQuote((string)child);
            }
        }

        var obj = Activator.CreateInstance(Assembly.GetExecutingAssembly().FullName, "WatinDsl.Ast." + name.Text).Unwrap();
        
        InitilizeObject(obj, node);
        
        return obj;
    }

    private void InitilizeObject(object obj, object node)
    {
        foreach (var child in builder.GetSuccessors(node))
        {
            if (builder.IsSequence(child))
            {
                foreach (var element in builder.GetSequenceElements(child))
                {
                    AddToList(obj, child, element);
                }
            }
            else if (builder.IsNode(child))
            {
                obj.SetPropery(builder.GetLabel(child).ToString(), DeserialzeNode(child));
            }
        }
    }

    private void AddToList(object obj, object parentNode, object element)
    {
        var propertyInfo = obj.GetType().GetProperty(builder.GetLabel(parentNode).ToString());
        var value = propertyInfo.GetValue(obj, null);
        var method = value.GetType().GetMethod("Add");
        method.Invoke(value, new[] { DeserialzeNode(element) });
    }

    private IEnumerable<object> DeserialzeSeq(object node)
    {
        foreach (var element in builder.GetSequenceElements(node))
        {
            var obj = DeserialzeNode(element);
            yield return obj;
        }
    }

    private object UnQuote(string str)
    {
        return str.Substring(1, str.Length - 2);
    }
}

I guess in future versions of Oslo previews something like the above deserializer will be included as it is essential for creating executable DSLs. Maybe the Oslo team has another option for doing this, for example generating Xaml from the node graph which can then initialise your AST.

So how do we compile and run code in our new WatiN DSL language? First we need to compile the grammar .mg file into a .mgx file, this is done with the MGrammarCompiler, we can then use the .mgx file to create a parser, the parser will generate a node graph which we will deserialize into our custom AST.

public class WatinDslParser
{
  public object Parse(string code)
  {
    return Parse(new StringReader(code));
  }

  public object Parse(TextReader reader)
  {
    var compiler = new MGrammarCompiler();
    compiler.FileNames = new[] { "BrowserLang.mg" };
    compiler.Target = Target.Mgx;
    compiler.References = new string[] { "Languages", "Microsoft.Languages" };
    compiler.Execute(ErrorReporter.Standard);

    var parser = MGrammarCompiler.LoadParserFromMgx("BrowserLang.mgx", "CodingInstinct.BrowserLang");

    object root = parser.ParseObject(reader, ErrorReporter.Standard);

    return root;
  }
}

The reason I compile the grammar from code every time I run a script is so I can easily change the grammar and rerun without going through a separate compiler step. The Parse function above returns the M node graph. Everything is glued together in the WatinDslRunner class:

public class WatinDslRunner
{
  public static void RunFile(string filename)
  {
          var parser = new WatinDslParser();
          var deserializer = new MAstDeserializer();

          using (var reader = new StreamReader(filename, Encoding.UTF8))
          {
              var rootNode = parser.Parse(reader);
              var tests = (IEnumerable)deserializer.Deserialze(rootNode);

              foreach (Test test in tests)
              {
                  RunTest(test);
              }
          }
  }

      public static void RunTest(Test test)
      {
          Console.WriteLine("Running test " + test.Name);
          using (var browser = BrowserFactory.Create(BrowserType.InternetExplorer))
          {
              foreach (var action in test.ActionList)
              {
                  action.Execute(browser);
              }
          }
      }
}

If you have problems with the code above, please remember that the code in this post is just an experimental spike to learn MGrammar and the M Framework library. If you want to experiment with this yourself, download the code+solution: WatinDsl.zip.

Summery and some other thoughts on Oslo/Quadrant

It was quite a bit of work going from my textual DSL to something executable. The majority of the time was spent figuring out the M node graph and how to parse and deserialize it, writing the grammar was very simple. MGrammar will definitely make it easier to create simple data definition languages that could replace some existing xml based solutions, but I doubt that it will be widely used in enterprise apps for creating executable languages. Maybe it is more suited for tool and framework providers. It is the first public release so a lot will probably change and be improved so it is to early to say how much of an impact M/Oslo will have for .NET developers.

I got home from PDC quite puzzled over Oslo and the whole model-driven development thing. They only talked about data, data, data, I don't think they mentioned the word BEHAVIOR even once during any Oslo talk that I attended, to me that is kind of important :) I asked others about this and most agreed that they did not understand the point of Oslo, or how it would improve/change application development significantly.

Sure I found Quadrant to be a cool application that could potentially replace some Excel / Access solutions but what else? In what way is Quadrant interesting for application developers?  It would be interesting to get some comments on what others think about MGrammar, Quadrant & Model-driven development :)