Wild Stabs In The Dark

Almost a full-blown LISP interpreter :)

noreply@blogger.com (Patagonian Toothfish) — Mon, 18 Aug 2008 15:22:00 +0000

[9th August 2008]

So I've been playing with the Eden library again, and I finished putting in some very cool functionality while watching China put on a phenomenal show for the Olympic Games Opening Ceremony...

Eden now supports cons! So we can build and return lists now, such as the following examples:

   (cons 'maple' (list 'birch' 'oak' 'larch')) => ('maple' 'birch' 'oak' 'larch')      
(list 'maple' (list 'birch' 'oak' 'larch')) => ('maple' ('birch' 'oak' 'larch'))

Date is now a first class atom-type, so we can do things like:

   (defun next_sunday (x? f?)      
    (prog       
        (setq d (if (nil-p x) today x))       
        (date (+ d (- 7 (day_of_week d))) f)))

To make the programmer's life easier, we also supports optional arguments to defun! To designate the formal parameter as optional, append it with a question mark. All formal parameters after the first optional one are implicitly optional. If no argument is bound to an optional parameter, it is initialised with nil.

Of course, + now handles dates and time-spans :)

[Ten days later]

OK. cons works, as do car, cdr and all the test functions like listp (which has an alias, a-la Scheme, of list?), atom? and nil?.

I've spent the last few days re-implementing the evaluation engine to dynamically support new native functions using reflection and cleaning up various odd-bits (yes, I was watching the Olympic Games and it did reduce my productivity a bit).

   (defun make-list (x)      
    (cond       
        ((list? x) x)       
        (t (cons x nil))))
    (defun append (l x)      
    (cond       
        ((atom? l) (cons l (make-list x)))       
        ((nil? l) (make-list x))       
        (t (cons (car l) (append (cdr l) x)))       
    ))
    (defun reverse (l)      
    (cond       
        ((nil? l) l)       
        ((atom? l) nil)       
        ((list? (car l)) (append (reverse (cdr l)) (list (reverse (car l)))))       
        (t       
            (append (reverse (cdr l)) (car l))       
        )       
    ))

allows us to call

(reverse (list 'a' 'b' (list 'c' 'd') 'e' 'f')), which returns with (f e (d c) b a) as we expect!

In addition to optional parameters, easy-to-integrate native functions, properly stacked evaluation of (mutually) recursive functions, scoped parameters and variables, and multiple-statement defun definitions, we have all the makings of a full-blown, yet neat and compact LISP interpreter!

Next, I think I'll get it to support lambdas and mapcar!

While I'm at it, let me stress on the importance of writing unit tests, specially while developing foundational pieces like this one.

I've been using the native testing framework in Visual Studio 2008, and it's a breeze to be able to run off a whole suite of tests to make sure that a fix I put in for one bug didn't break something else somewhere.

Furthermore, as the tests get more and more complex and involved, it's comforting to know that the system is just growing stronger every time a feature gets added without anything being broken! I now have over 200 test expressions which are run after every major recompile, assuring that all the functionality is working as it should be...

Stay tuned!

Post 6: Expression Evaluator - Finale

noreply@blogger.com (Patagonian Toothfish) — Thu, 07 Aug 2008 15:21:00 +0000

We have, in the previous posts, seen how to build an expression evaluator and integrate it into our calling environment.

The concepts we have discussed provide a solid basis for an evaluation engine that can be extended further.

For example, we could support custom functions with a defun function:

(defun <function name> <list of formal parameters> <function body>)

It's easy to see how we could implement the defun function as a known function, which would store the body and formal parameter list in a hash table indexed by the function name. We could then modify the Apply function to bind values to the formal parameters and evaluate the body.

We could support variable binding with the setq function:

(setq <var_name> <expr>)

We could do this by storing the value of the expression in a global symbol table indexed by the var_name, and modifying the Apply function to do look for the value of a variable first in the scoped symbol table and then the global one.

We could support conditional operations with the cond function, which returns the result associated with the first test expression that evaluates to 'true':

(cond ((test_1) (result_1)) ... ((test_n) (result_n)))

We could even expand our processing to perform evaluation of the function name:

((cond ((> w 20) "square") (t "cube")) p)

so that we get the value of (square p) if w > 20 and (cube p) otherwise!

With a few more modifications, we can support recursive functions such as the classic expression for a factorial

        (defun decr (x) (- x 1))        
(defun fact (x) (cond ((> x 0) (* x (fact (decr x)))) (t 1)))

Executing the above strings in order would allow us to compute factorials of any integer from that point on!

double fact10 = 10.ToString().Evaluate(null);

Cool?

Contact me if you would like to get your hands on this library!

One last thing - in honour of my newest niece who was born just as the first full implementation of this project was completed, I'm calling this library Eden. We'll be likely releasing BrightSword.Eden as a free download from the company home page soon.

Post 5: Expression Evaluator - Integration

noreply@blogger.com (Patagonian Toothfish) — Sat, 02 Aug 2008 04:29:00 +0000

So far, we've used "constant" s-expressions as examples for evaluation, and that's pretty cool, but it is, of course, a great deal more interesting to be able to compute expression values when the expression contains variables bound to values at run-time.

For example, the formula for computing the Body Mass Index of a healthy human is given by the following formula:

BMI = (Weight in Kilograms / (Height in Meters) x (Height in Meters))

or as an s-expression

(div weight (prod height height))

If we were able to pass in the values for weight and height for various people, we could get the expression evaluator to compute the BMI.

To accomplish this, we make a few modifications to the Evaluate function, and pass in an addition symbol table with values for the variables.

   public static Expression Evaluate(this Expression _this, Dictionary<string, object> Symbols)      
{       
    switch (_this.Children.Count)       
    {       
        case 0:       
            /* atomic value */       
            {       
                switch (_this.Token)       
                {       
                    ...
                        case E_TOKEN.ValidName:      
                        {       
                            switch (_this.TokenValue.ToLower())       
                            {       
                                ... other "known" tokens 
                                    default:      
                                    {       
                                        try       
                                        {       
                                            _this.SetValue(Symbols[_this.TokenValue]);       
                                        }       
                                        catch (KeyNotFoundException)       
                                        {       
                                            _this.RegisterMissingSymbol(_this.TokenValue);       
                                        }       
                                    }       
                                    break;       
                            }       
                        }       
                        break; 
                        case E_TOKEN.Text:      
                    case E_TOKEN.ValidNumber:       
                    case E_TOKEN.SingleQuotedText:       
                    case E_TOKEN.DoubleQuotedText:       
                        {       
                            _this.SetValue(_this.TokenValue);       
                        }       
                        break; 
                        default:      
                        {       
                            throw new EvaluatorException(_this, "Evaluate Error: Unknown Token!");       
                        }       
                } 
                    return _this;      
            } 
            ...      
    }       
}

To call our evaluator from some other code, we could do the following:

       string strExpression = ... get the string from a resource or database
        Dictionary<string, object> Symbols = new Dictionary<string, object>();      
    Symbols["height"] = ... input from a form or database;       
    Symbols["weight"] = ... input from a form or database; 
        double BMI = strExpression.Evaluate(Symbols).ValueAsNumber;

Now if the customer wanted the formula changed on the fly to the non metric version, all we need to do is change the expression to be evaluated to

BMI = ( Weight in Pounds / ( Height in inches ) x ( Height in inches ) ) x 703

(prod (div weight (prod height height) 703)

and the compiled version of the code doesn't change at all!

Post 4: Expression Evaluator - Object Typing

noreply@blogger.com (Patagonian Toothfish) — Fri, 01 Aug 2008 02:04:00 +0000

We have seen how the evaluation engine recursively evaluates an expression tree and associates a value with each Expression object. We have also seen how the values associated with the Expression object are examined only by the individual function processors. Let's look at the function processor for the "+" function again

       case "+":   
        {  
            try  
            {  
                return Functor.SetValue(Arguments.Aggregate(0.0d, (result, x) => result += x.Evaluate().ValueAsNumber);  
            }  
            catch  
            { } 
                return Functor.SetNil();  
        }

We notice the generic Aggregate function on Arguments returns a double, and consequently the lambda expression returns a double, using the native += operator to operate on double values. This means that we have to somehow express the value of the Expression x as a double. Further, we need to ensure that the value associated with the Functor is henceforth interpretable as a double.

We also need to handle the case where it cannot be expressed as a number, and we'll deal with that in a moment.

We can also imagine other scalar types - like strings and boolean values - of immense importance when we want to do comparison expressions like:

(> a b)

We therefore create a Variant class (again a throwback to my C/C++ days) where a class can encapsulate a given value and represent it, if possible, in various types. In our case, we are going to support strings, numbers (doubles) and booleans, so our variant class looks something like:

   public class VariantValue      
{       
    public E_VALUETYPE ValueType { get; protected internal set; } 
       public object UntypedValue { get; protected internal set; }     
        public virtual bool IsNumber      
    {       
        get       
        {       
            try       
            {       
                CastToNumber(this.UntypedValue);       
                return true;       
            }       
            catch       
            {       
                return false;       
            }       
        }       
    } 
        protected static double CastToNumber(object value)      
    {       
        try       
        {       
            return System.Convert.ToDouble(value);       
        }       
        catch       
        {       
            throw new InvalidCastException("Cannot express (" + value.ToString() + ") as a Number");       
        }       
    } 
        public virtual double ValueAsNumber      
    {       
        get       
        {       
            try       
            {       
                return CastToNumber(this.UntypedValue);       
            }       
            catch       
            {       
                return double.NaN;       
            }       
        } 
            set      
        {       
            this.UntypedValue = value;       
            this.ValueType = E_VALUETYPE.Number;       
        }       
    } 
        #region Boolean ...
        #region String ...
        protected internal virtual VariantValue SetValue(bool value) { this.ValueAsBoolean = value; return this; }      
    protected internal virtual VariantValue SetValue(double value) { this.ValueAsNumber = value; return this; }       
    protected internal virtual VariantValue SetValue(string value) { this.ValueAsString = value; return this; } 
        protected internal virtual VariantValue SetNil() ...
        protected internal virtual VariantValue SetValue(VariantValue value) ... 
        protected internal virtual VariantValue SetValue(object value) ...      
}

We can see how the VariantValue class stores the raw value in the UntypedValue property and tries to represent it as a Number, Boolean or String when required. This is important because a value can have more than one representation.

The Is... accessor properties allow callers to query if the value can be represented in the appropriate type.

The ValueAs... accessor properties return the value as the appropriate type if possible. They will never throw any exceptions. They are helped by the internal CastTo... functions, which do throw exceptions. When we examine the SetValue(object) function, we'll see how the exceptions play a crucial role in helping us decide how best to represent a generic object.

The ValueAs... mutator properties save the raw value in the UntypedValue property. Since the type of the value is known to them, they also store the type information in the ValueType property.

The code below is the SetValue(object) function. It is called when the type-specific version of SetValue cannot be called (for example when the value is obtained from a symbol table - look at the section on integration).

We successively attempt to coerce the value into one of the three known types, using the exceptions thrown from the CastTo... functions to signal that coercion was unsuccessful.

       protected internal virtual VariantValue SetValue(object value)      
    {       
        if (value == null) { return SetNil(); } 
            // [true] can be coerced to a number if we don't do this      
        if ((value is long) || (value is double))       
        {       
            this.ValueAsNumber = CastToNumber(value); return this;       
        } 
            if (value is bool)      
        {       
            this.ValueAsBoolean = CastToBoolean(value); return this;       
        } 
            try      
        {       
            this.ValueAsNumber = CastToNumber(value);       
            return this;       
        }       
        catch       
        { } 
            try      
        {       
            this.ValueAsBoolean = CastToBoolean(value);       
            return this;       
        }       
        catch       
        { } 
            try      
        {       
            this.ValueAsString = CastToString(value);       
            return this;       
        }       
        catch       
        { } 
            this.UntypedValue = value;      
        this.ValueType = E_VALUETYPE.Uninitialized; 
            return this;      
    }

Since every Expression object is associated with a value, we can make life easy and simply derive the Expression class from the VariantValue class. We are effectively saying that an Expression is a VariantValue.

   public class Expression : VariantValue  
   ...

We're close to putting the finishing touches on our expression evaluator. The last post in this series will deal with integration with the calling environment, allowing us to use the evaluator within the context of any other application.

Post 3: Expression Evaluator - The Expression Class and Evaluation

noreply@blogger.com (Patagonian Toothfish) — Thu, 31 Jul 2008 02:03:00 +0000

The Expression Class is a n-ary tree representation of a given S-Expression.

In its simplest form, the class would look something like:

   public class Expression      
{       
    protected Expression m_Parent = null;       
    public virtual Expression Parent { get { return m_Parent; } } 
        protected List<Expression> m_Children = new List<Expression>();      
    public virtual List<Expression> Children { get { return m_Children; } } 
        protected string m_TokenValue = String.Empty;      
    public string TokenValue { get { return m_TokenValue; } } 
        ... other housekeeping properties ...

At this point in the evaluation cycle, we have simply created a different representation of the S-Expression.

We actually perform the evaluation of each node by recursively evaluating each of the children and merging their results. The obvious questions here are:

How exactly do we merge the results?
How do we evaluate the children?

It would also be important to discuss the issue of the type of the result.

Let's go back to a simple S-Expression

        (+ 1 2 3 4)

The Expression tree generated would be:

        Root (1 Child)                 >> (5 Children)                         "+" (0 Children) 
              "1" (0 Children) 
              "2" (0 Children) 
              "3" (0 Children) 
              "4" (0 Children)

In order to apply meaning to the expression, we define the convention that the first child represents some operation which has to be performed on all its siblings in order, which when applied, results in the value associated with the first child. Further, we define that the value of a node is the value of the first child.

In our example case, we define that the value of the Root node is the value of the anonymous ">>" node, which in turn is the value of the "+" node, which in turn is the value resulting from applying the "+" function on "1", "2", "3" and "4".

We notice that we have now answered the first question "How do we merge the results".

To answer the second question, let's take a closer look at the Evaluate function of the Expression class, shown here in its simplified form:

   public Expression Evaluate()      
{       
    switch (this.Children.Count)       
    {       
        case 0:       
            /* atomic value */       
            {       
                switch (this.Token)       
                {       
                    case E_TOKEN.SExprStart:       
                        break; 
                        case E_TOKEN.ValidName:      
                    case E_TOKEN.Text:       
                    case E_TOKEN.ValidNumber:       
                    case E_TOKEN.SingleQuotedText:       
                    case E_TOKEN.DoubleQuotedText:       
                        {       
                            this.SetValue(this.TokenValue);       
                        }       
                        break; 
                        default:      
                        {       
                            throw new EvaluatorException(this, "Evaluate Error: Unknown Token!");       
                        }       
                } 
                    return _this;      
            } 
            case 1:      
            /* s-expr or root node */       
            {       
                return this.SetValue(this.Children[0].Evaluate());       
            } 
            default:      
            /* function call */       
            {       
                // apply first child to the remaining children       
                return this.SetValue(Apply(this.Children[0], this.Children.Skip(1).ToList()));       
            }       
    }       
}

We can see the straightforward processing of the Root and Atom cases. The default case deals with the situation where the first child needs to be "applied" on the other children. Apply is the most elaborate function in this project, but it's quite simple really. If all we did was addition, this is what Apply() would look like:

        private static Expression Apply(Expression Functor, List<Expression> Arguments)        
{         
    string strFunc = Functor.TokenValue;         
          switch (strFunc.ToLower())        
    {         
        #region SUM/CONCAT         
        case "+":         
        case "add":         
        case "sum":         
            {         
                try         
                {         
                    return Functor.SetValue(Arguments.Aggregate(0.0d, (result, x) => result += x.Evaluate().ValueAsNumber);         
                }         
                catch         
                { } 
                      return Functor.SetNil();        
            }         
        #endregion 
          }        
}

The lambda expressions and List extension functions in C# make writing the processor sections a breeze. It's easy to see how the first child's value (the Functor argument to Apply) is set to the sum of the other children (the Arguments argument to Apply).

We are only left with one major issue to discuss - that of the value type.

Post 2: Expression Evaluator - Building an Expression Tree

noreply@blogger.com (Patagonian Toothfish) — Wed, 30 Jul 2008 10:01:00 +0000

The Parse function described in the previous posts allows us to specify a ParseEventHandler delegated function which will be called-back by the parser.

We use this function to monitor the parsing of an expression string, and build a corresponding expression tree, which can then be evaluated. This is one of several approaches we could take for the evaluation process - alternatively, we could proceed with the evaluation in-situ, with a makeshift stack. I took this approach because it allows us to re-use the expression strings without having the re-parse - which is something we'll need to support user-defined functions.

The building of the expression tree is straightforward. We require a simple class to keep track of the Root node of the expression, and the Current node - which represents the S-Expression being parsed currently.

We write a simple ParseEventHandler delegate, which hooks the SExprStart state to signify the creation of a sub-tree, and the Atom state to signify leaf nodes of the expression tree. We pass along a ParserContext object to keep a reference to the Root and the Current nodes of the expression tree.

   public class ParserContext      
{       
    public Expression Root { get; private set; }       
    public Expression Current { get; set; } 
        public ParserContext(Expression Root)      
    {       
        this.Root = Root;       
        this.Current = Root;       
    }       
}

The ParseEventHandler function is simple and elegant. All we're doing here is listening for three events:

SExprStart : Signifying a new S-Expression child. Our handler creates a child and sets it as the current parent, so future nodes will get bound to it.
SExprFinish: Signifying the completion of the current S-Expression. Our handler "pops the stack", as it were, and marks the parent node as the current parent.
Atom: Signifying a leaf-node child of the current parent. Simply creates and attaches a leaf-node, leaving the current parent intact.

   protected static void ParseEventHandler(ParseEventArgs e)      
{       
    ParserContext pctx = e.ParserContext as ParserContext;       
    if (pctx == null) return; 
        switch (e.Token)      
    {       
        case E_TOKEN.SExprStart:       
            {       
                pctx.Current = new Expression(pctx.Current, ">>", e.State, e.Token);       
            }       
            return; 
            case E_TOKEN.SExprFinish:      
            {       
                pctx.Current = pctx.Current.Parent;       
            }       
            return;       
    } 
        switch (e.State)      
    {       
        case E_PARSESTATE.Atom:       
            {       
                Expression exIgnore = pctx.Current.NewChild(e.TokenValue, e.State, e.Token);       
            }       
            return; 
            case E_PARSESTATE.Failure:      
            {       
                throw new ParseException(String.Format("*** FAILURE {0}] : [ {1} ], {2}, {3}", e.ErrorDescription, e.TokenValue, e.State, e.Token));       
            }       
    }       
}

To actually call the parser, all we do is pass in a reference to the handler and context instance:

Expression Root = new Expression();

Parser.Parse(pszExpression, new ParseEventHandler(ParseEventHandler), new ParserContext(Root));

// ... at this point, Root has been built up, or parsing has failed and thrown an exception

We'll discuss the Expression class in detail in the next post.

Eden is Born!

noreply@blogger.com (Patagonian Toothfish) — Wed, 30 Jul 2008 07:11:00 +0000

Eden Trinity Azariah was born today in Moncton, Canada to my brother and sister-in-law!

Mom and baby are doing well!

Big sister Tabitha couldn't be happier!

Welcome, baby Eden!

Post 1: Expression Evaluator - The Parser

noreply@blogger.com (Patagonian Toothfish) — Fri, 25 Jul 2008 02:01:00 +0000

We can take the classic state-machine approach to build the S-Expression parser, and use the C# event constructs to perform appropriate callbacks as we encounter specific states.

The Parser class contains a single static function which can parse a string and call the handler at appropriate points for further processing. A context object is passed through along to the handler for its use.

The Parse function consists of a single loop that walks the string from beginning to end, using the Tokenizer helper class to break up the string into lexically interesting chunks, and transitioning the state machine through the various states. We'll discuss Tokenizer::NextToken in detail next.

The state machine has the following states:

        Start 
      Finish 
      SExprStart 
      SExprFinish 
      AtomOrSExpr 
      Atom 
      Failure

Each of these states is of interest to the caller of the Parse function, as each state represents effectively a result of parsing the string.

The Parse results for a simple string are given - it's easy to walk through the body of the Parse function and see why the results came out the way they did:

   Input String: (test "(f1 a b)" (f2 c d)) 
         Start, 
      SExprStart, ( 
      Atom - ValidName, test 
      Atom - DoubleQuotedText, (f1 a b) 
      SExprStart, ( 
      Atom - ValidName, f2 
      Atom - ValidName, c 
      Atom - ValidName, d 
      SExprFinish, ) 
      SExprFinish, ) 
      Finish,

The grammar we described earlier define what state we want to be in after encountering a particular token, and this structure is reflected in the state machine. The Tokenizer also goes a little further and reports if the text it encounters would conform to a valid variable name, or a valid number. This helps us when we want to do some further processing of the parsed results.

   public static E_PARSERESULT Parse(this string psz, ParseEventHandler ParseEventHandler, object context)      
{       
    int sStart = 0, sFinish = 0; int expr_nest = 0; 
        E_PARSESTATE state = E_PARSESTATE.Start; 
        while (sFinish <= psz.Length)      
    {       
        switch (state)       
        {       
            case E_PARSESTATE.Start:       
                {       
                    expr_nest = 0; 
                        // dispense the notification.      
                    ParseEventHandler(new ParseEventArgs(psz, context, state, E_TOKEN.MAX, 0, 0)); 
                        state = E_PARSESTATE.AtomOrSExpr;      
                };       
                break;       
            case E_PARSESTATE.Finish:       
                {       
                    if (expr_nest != 0) { state = E_PARSESTATE.Failure; break; } 
                        // dispense the notification.      
                    ParseEventHandler(new ParseEventArgs(psz, context, state, E_TOKEN.MAX, 0, 0)); 
                        // we're done...      
                    return E_PARSERESULT.S_OK;       
                }       
        } 
            E_TOKEN tok = Tokenizer.NextToken(psz, sFinish, out sStart, out sFinish); 
            switch (state)      
        {  
            case E_PARSESTATE.SExprStart:       
                {       
                    // SExpr ::= SExprStart (Atom | SExpr)* SExprFinish       
                    switch (tok)       
                    {       
                        case E_TOKEN.SExprStart: // (       
                            {       
                                expr_nest++; 
                                    ParseEventHandler(new ParseEventArgs(psz, context, E_PARSESTATE.SExprStart, tok, sStart, sFinish));      
                                state = E_PARSESTATE.AtomOrSExpr;       
                            }       
                            break; 
                            case E_TOKEN.EOF:      
                            {       
                                sFinish = sStart; state = E_PARSESTATE.Finish;       
                            }       
                            break; 
                            default:      
                            {       
                                ParseEventHandler(new ParseEventArgs(psz, context, E_PARSESTATE.SExprStart, tok, sStart, sFinish, "Unexpected token found instead of SExprStart", 0));       
                                state = E_PARSESTATE.Failure;       
                            };       
                            break;       
                    }       
                }       
                break; 
                case E_PARSESTATE.AtomOrSExpr:      
                {       
                    switch (tok)       
                    {       
                        case E_TOKEN.DoubleQuotedText:       
                        case E_TOKEN.SingleQuotedText:       
                            {       
                                ParseEventHandler(new ParseEventArgs(psz, context, E_PARSESTATE.Atom, tok, sStart+1, sFinish-1));       
                                state = E_PARSESTATE.AtomOrSExpr;       
                            }       
                            break; 
                            case E_TOKEN.ValidName:      
                        case E_TOKEN.ValidNumber:       
                        case E_TOKEN.Text:       
                            {       
                                ParseEventHandler(new ParseEventArgs(psz, context, E_PARSESTATE.Atom, tok, sStart, sFinish));       
                                state = E_PARSESTATE.AtomOrSExpr;       
                            }       
                            break; 
                            case E_TOKEN.SExprStart: // (      
                            {       
                                sFinish = sStart; //rewind token       
                                state = E_PARSESTATE.SExprStart;       
                            }       
                            break; 
                            case E_TOKEN.SExprFinish: // )      
                            {       
                                sFinish = sStart; //rewind token       
                                state = E_PARSESTATE.SExprFinish;       
                            }       
                            break; 
                            case E_TOKEN.EOF:      
                            {       
                                state = E_PARSESTATE.Finish;       
                            }       
                            break; 
                            default:      
                            {       
                                ParseEventHandler(new ParseEventArgs(psz, context, E_PARSESTATE.Failure, tok, sStart, sFinish, "Unexpected token found without matching SExprFinish", 0));       
                                state = E_PARSESTATE.Failure;       
                            };       
                            break;       
                    }       
                }       
                break; 
                case E_PARSESTATE.SExprFinish:      
                {       
                    switch (tok)       
                    {       
                        case E_TOKEN.SExprFinish: // )       
                            {       
                                expr_nest--; 
                                    ParseEventHandler(new ParseEventArgs(psz, context, E_PARSESTATE.SExprFinish, tok, sStart, sFinish));      
                                state = (expr_nest == 0) ? E_PARSESTATE.Finish : E_PARSESTATE.AtomOrSExpr;       
                            }       
                            break; 
                            case E_TOKEN.EOF:      
                            {       
                                sFinish = sStart; state = E_PARSESTATE.Finish;       
                            }       
                            break; 
                            default:      
                            {       
                                ParseEventHandler(new ParseEventArgs(psz, context, E_PARSESTATE.Failure, tok, sStart, sFinish, "Unexpected token found instead of SExprFinish", 0));       
                                state = E_PARSESTATE.Failure;       
                            };       
                            break;       
                    }       
                }       
                break; 
                case E_PARSESTATE.Failure:      
            default:       
                {       
                    ParseEventHandler(new ParseEventArgs(psz, context, E_PARSESTATE.Failure, E_TOKEN.MAX, sStart, sFinish, "Parser Failure", 0));       
                }       
                return E_PARSERESULT.E_FAILURE; 
            }      
    }; // while (curpos < psz.Length) 
        {      
        ParseEventHandler(new ParseEventArgs(psz, context, E_PARSESTATE.Failure, E_TOKEN.MAX, sStart, sFinish));       
    } 
        return E_PARSERESULT.E_FAILURE;      
}

The Tokenizer helper class has a bunch of text processing functions which simply make life easier. The primary function, that of tokenizing - or chopping up the input text - is carried out by the NextToken function:

   public static E_TOKEN NextToken(string psz, int s, out int sTokBegin, out int sTokEnd)      
{       
    sTokBegin = -1; sTokEnd = psz.Length - 1;       
    if (s < 0) { return E_TOKEN.EOF; } 
        int sb = SnarfWhiteSpace(psz, s); 
        sTokBegin = sb;      
    if (sb == psz.Length) { return E_TOKEN.EOF; } 
        // (      
    if (IsOpenParen(psz[sb]))       
    {       
        sTokEnd = ++sb; return E_TOKEN.SExprStart;       
    } 
        // )      
    if (IsCloseParen(psz[sb]))       
    {       
        sTokEnd = ++sb; return E_TOKEN.SExprFinish;       
    } 
        // '...'      
    int se = sb;       
    if (psz[sb] == '\'')       
    {       
        return SnarfQuotedText(psz, sb, out sTokBegin, out sTokEnd, psz[sb]) ? E_TOKEN.SingleQuotedText : E_TOKEN.EOF;       
    }       
    sb = se; 
        // "..."      
    se = sb;       
    if (psz[sb] == '"')       
    {       
        return SnarfQuotedText(psz, sb, out sTokBegin, out sTokEnd, psz[sb]) ? E_TOKEN.DoubleQuotedText : E_TOKEN.EOF;       
    }       
    sb = se; 
        {      
        sb++; 
            bool fOK = true;      
        for (; (sb < psz.Length) && fOK; sb++)       
        {       
            char ch = psz[sb];       
            fOK = (!(IsWhiteSpace(ch) || IsOpenParen(ch) || IsCloseParen(ch)));       
        } 
            if (!fOK) { --sb; } 
            if (sb <= psz.Length)      
        {       
            sTokEnd = sb; sTokBegin = SnarfWhiteSpace(psz, sTokBegin); 
                string strToken = psz.Substring(sTokBegin, sTokEnd - sTokBegin); 
                if (IsValidName(strToken)) { return E_TOKEN.ValidName; }      
            if (IsValidNumber(strToken)) { return E_TOKEN.ValidNumber; } 
                return E_TOKEN.Text;      
        } 
            sTokEnd = sb; return E_TOKEN.EOF;      
    }       
}

The tokenizing approach is a throwback to my C/C++ days, when strings were null-delimited arrays of characters, and traipsing over them using a bunch of indices to keep track of sub-strings were the most efficient way of dealing with them. The NextToken function is passed in a tentative starting point (typically the point where it left off last) and it returns the next interesting token encountered after that point in the string.

A few points of note:

The Tokenizer class has been made internal to the Parser class and therefore has no interface footprint. Of course, with the C# partial class structure, we could put it in a separate file but keep it as a part of the Parser class.

We take care to ensure that the Parser and Tokenizer are both static classes (with all static functions, obviously). This is a great way to ensure that there is no state associated with the classes themselves, so the classes are multi-thread ready.

One sweet syntactic bonus is to write the Parse function as an extension class of the String type, so if you include the namespace containing the Parser, all strings automatically have the Parse function stuck on to them - very chic!

Part 0: Building a Basic Expression Evaluator

noreply@blogger.com (Patagonian Toothfish) — Mon, 21 Jul 2008 10:01:00 +0000

Quite often in our work, we come across situations where we would have to customize some business-logic quickly and on-the-fly. One such situation is when we have a workflow coded up, but the logic for transitioning between states is not fully known or is likely to change when the customers finally decide what they want.

In some of such situations, we would really love it if we could store the state transition-logic in a form that is easily editable at customization-time and dynamically evaluable to allow the workflow's behaviour to evolve and refine over time.

Being a classic computer scientist at heart, I decided to see if we could embed a little LISP evaluation engine and perhaps write and store the customization logic as a LISP expression, which would be evaluated at run-time and allow for the flexibility we needed. Then, being a classic masochist, I decided to spend a few days and see if I could build the evaluation engine itself. (Actually, I did google up for an embeddable LISP engine, but found that the gymnastics involved in integrating the engine into our environment wouldn't be worth the trouble!)

The evaluator we built takes a string s-expression value, and reduces it to a single scalar value. We built it in stages, and I'll describe the building process similarly. Unlike a full blown LISP implementation, all our functions return a single scalar - so there isn't support for the cons primitive.

The lexical structure for the little language we're building is:

        Program ::= Atom | SExpr 
      Atom ::= number | boolean | string  
      SExpr ::= "(" Atom | SExpr ")" 
      number is a pattern conforming to the following IEEE regular expression for a floating point: ^[-+]?[0-9]*\\.?[0-9]+([eE][-+]?[0-9]*\\.?[0-9]+)?$. 
      boolean is one of the following strings : t, true, false, nil and f. Each corresponding to its commonly known, self-explanatory value 
      string is a pattern conforming to an unquoted sequence of non-white-space characters, or a quoted sequence of characters including white-space

Semantically, we will use the general LISP convention where the car or first element of the SExpr is the function we want to apply to the cdr or the remainder of the SExpr. We will also pre-define some of the well-known functions we want to process.

So for example, we might want to evaluate the following strings and expect the associated results:

        (+ 1 2 3 4) => 10 
      (+ 1 2 (* 3 2)) => 8 
      (+ "hello" " " "world") => "hello world" 
      (and (> 4 2 1) (<= 3 4 4 5)) => true

The cool thing to notice is that we want our engine to deal with dynamically typing the values into either numbers, boolean values or strings. The well-known functions also have to be intelligent and decide, for example, when to sum numbers and when to concatenate strings.

Of course, as the engine evolves, we want to pay special attention to integrating it into an environment from which it could be called, and introduce support for custom functions to supplement the well-known ones. Further improvements would include support for recursive and mutually recursive functions.

The posts following will outline the approach to building the evaluation engine and providing the support we desire.

Home!

noreply@blogger.com (Patagonian Toothfish) — Tue, 24 Jun 2008 06:29:00 +0000

After the disappointment of the weekend, we decided we'd look around the area some more, and look at the other houses we had liked, and other options. We're praying hard that we'll find the right home soon!

We just walked past the agents on Playne Street - picking up brochures, and walked into Dawes First National. The agent gave us brochures of some houses, and then mentioned that a new home had come up for sale in the same neighbourhood of the other two houses we had put offers in on!

We drove up to the new house and absolutely loved it!

It's smaller than the other homes, but it has an absolutely gorgeous Australian bush garden out back, and we fell in love with it the moment we saw it.

So much so that the negotiations were short and sharp. To cut a long story short, we put in an offer on the house today, and just found out that the offer had been accepted!

We bought a house today! Can't wait to get it set up and have everyone visit!

The only bummer was that we would have to wait an extra month for the settlement - the lady selling the house needs to find alternate accommodation - but it means we have a little more time to sort out the finances!

House-hunting

noreply@blogger.com (Patagonian Toothfish) — Sun, 22 Jun 2008 06:50:00 +0000

We spent the last week looking around the suburbs for houses.

Went over to Upwey on Monday to look at some hill homes. The people are indeed very friendly and the place is beautiful, but owning a hill home seems to be a lot of work - lots of risk of bush-fires in the summer, and the yards are quite hard to maintain with all the falling leaves!

In the meanwhile, the temporary accomodation on Lonsdale Street was turning out to be too expensive, so we've been looking at other short-term rental options. Decided on a place in Brunswick which isn't cheap, but very convenient.

While Smitha went over to Brunswick to sort out the rental, I headed down to Frankston on Tuesday. We've been talking to some agents by email about interesting houses here - and we had an appointment with one of the agents. This place is quite beautiful and I think this is the better option compared to Upwey.

Came back to Frankston all this week - looked at over a dozen homes! The agents are quite friendly and the market is a buyer's market but not really desperate to sell. We were able to find a few homes we liked and we took time every evening to stack-rank the houses we had seen.

Here's a rainbow we caught from the car of one of the real-estate agents as they ferried us around the houses.

On Saturday, Marcus came along with us to Frankston to check out some of the open houses. We put an offer in on one of the houses we liked most.

This morning we found out that the house we had put an offer on had counter-signed the offer. Before negotiating, we decided we'd put an offer in on another house in the same neighbourhood. Called up the agent and put in the offer.

We just found out that the offer on the second home was bested by someone else - by a sliver. I guess this means we aren't going to get either of these houses. We really liked the second home...

Goodbye Lonsdale, Hello Brunswick

noreply@blogger.com (Patagonian Toothfish) — Sat, 21 Jun 2008 06:59:00 +0000

The view from the Lonsdale Street place was awesome - here's a sunrise taken from the balcony!

We moved into the Brunswick Road apartment today. Thanks to Christine for giving us the link to this place!

14 June 08 - The Travels (and travails) of Marcus

noreply@blogger.com (Patagonian Toothfish) — Sat, 14 Jun 2008 13:19:00 +0000

Bought a weekly Zone 1+2 pass to do the house-hunt next week. Decided that we should go over some of the suburbs to check them out again.

Called Marcus at 11:00 AM and woke him up! Told him we should head out to the outer suburbs before sundown.

Went over to the Library and started compiling lists of real-estate agents to call. Came back to the apartment after the library and ate lunch - sandwiches, leftover casserole and fruit. By now it was 1:00 PM, and we were still waiting for Marcus. He finally arrived - and still hadn't had anything to eat.

Walked over to Flinders Street Station, and popped into Flora's - an Indian restaurant which reinforced every experience I've had of Indian food outside India - for Marcus' lunch. When we finally left Flora's at 2:00 PM and walked across the street to the station, where we found out that the next Belgrave train was at 2:30 - barely 3 hours before dark. I was quite frustrated that the whole day was more-or-less gone before we even started.

The Saturday schedule on the Belgrave line consists of a Lilydale service, with a synchronized spur service off Ringwood to Belgrave, and it took about 15 minutes longer than the usual hour.

We got off at Upwey and walked up the street, taking in the cool air, the fresh smell of the trees, the sound of sulphur-crested cockatoos and king parrots as they flew in formation around the trees. Definitely breathtaking in more ways than one!

The property we wanted to look at was a sharp uphill walk from the station. The place itself was not attractive looking but the view around the area was phenomenal. Both Smitha and Marcus were apprehensive about the region though - given its distance from the city and the remote, hill-country feel. Personally, though, it takes me back to a happier time - back to the wooded hills of New Hampshire and Vermont, and the simple wisdom and charm of the people who live there.

Stopped off at a real-estate agent's office on the way back to Upwey station, just to get a feel for the people and the available houses. He took us to see a beautiful house - too big and expensive for us - and we decided to head back home. It was already dark even though it was only around 5:30 PM.

We got off at Spencer Street, headed over to the Crown Casino Food Court for a doner kebab, parted ways with Marcus and headed for home.

As we walked back home from Parliament Station, we called Tabitha and sang her a Happy Birthday - she was thrilled - and then called and talked to the families at home in India.

Then we sat down and took stock of the day...

We'll go over the same checklist of things we're looking for in a home for any of the houses we'll consider - distance from the city, distance from the railway station to the home, distance to church, grocery stores, hospitals, the cost factor, the construction quality, the size of the home, the general value for money and other factors which aren't so tangible like safety, security and the attractiveness of the area.

That in mind, next week should be interesting - we've lined up at least a dozen agents in the Upwey, Frankston and Berwick areas, and hopefully we'll be able to get a nice home soon!

13 June 08 - Friday the Thirteenth

noreply@blogger.com (Patagonian Toothfish) — Fri, 13 Jun 2008 13:19:00 +0000

Slept in till 9:30 this morning. Decided to have brunch before heading out to the city - famous Aussie lamb sausages. While I cooked up the sausages, Smitha packed our bags and tidied the place up, because we may have to move to a place in St. Kilda tomorrow morning.

Yet another day hunting for Internet access. Walked over to "Australia on Collins" - a massive mall on Collins Street - where there's free access for everyone but no power points. Checked mail and sent off a bunch of messages.

Left around half-past-three for St. Kilda - tram 96 from Bourke Street. It took an awfully long time to finally reach Hotel Esplanade, by which time we had received three increasingly agitated calls from the agent exclaiming she'd been waiting for us! When we finally met her, she exuded such a thorny demeanour that I'd decided that there was no way we were dealing with this woman! Despite her protestations that she was a "precise" woman, she hadn't any details about whether we had to pay bills, and generally speaking, spoke extremely rudely! Called her up from the tram on the way back to decline her graceless offer!

Met Marcus at our apartment. Went over to the Elephant and Wheelbarrow for a pint of Guinness. It was nice to savour the bitter taste and take in the noise and bustle of an English pub on football night. Walked up and down the streets looking for a place to eat. Finally wandered into the local Greek Restaurant and had a wonderful meal of grilled lamb and chicken, those famous Greek dips - tzatziki, taramasalata, hummus and babaghanouj - with pita bread.

Wonderful evening!

12 June 08 - Part 1 : Roaming Around The Countryside

noreply@blogger.com (Patagonian Toothfish) — Thu, 12 Jun 2008 11:17:00 +0000

Woke up early today. Walked over to the State Library and tried to get in with the laptop bag. The library staff are capricious about letting in that bag - the last time they let me go in, and today they asked me to check it into a locker because it didn't fit the silly frame.

Had a coffee at Starbucks and thought I'd get wireless access there - but found out that you need a Telstra connection to get that. Gave up on checking mail today.

Bought a Zone 1+2 day pass and decided to do some scouting around the area.

First off towards Belgrave - we'd seen a couple of places out in Upper Fern Tree Gully and Upwey and we wanted to see how long it would take to travel there and back. As the train made its way towards the outer suburbs, we were struck by how quiet the suburbs are. Melbourne itself isn't a bustling city - not like New York or London or even Sydney - but the 'burbs are right quiet!

Starting at Boronia, we got views of the mountains and the forests that make up the Dandenongs. The train was mostly empty by now - our carriage had a couple of high-school kids listening to music and making out.

Boronia - Ferntree Gully - Upper Ferntree Gully - Upwey - Tecoma - Belgrave

The views are amazing! The train runs along the flank of a mountain with the tops of trees below it on one side, and more trees towering up on the other. It would be amazing to live here - if only it wasn't an hour outside the city!

Belgrave Station Street is a short stretch of little curio shops and restaurants and real-estate agent offices. We have a Fish 'n Chips lunch sold by a friendly but miserly Greek vendor at one of the restaurants on the street. Walked back down to the station after lunch and took the train back to Richmond.

From Richmond we took the Frankston Line to see that side of the country. It's now around 3:00 and some of the schools seem to be letting out. The train goes on towards Aspendale and the suburbs we think we might to live in.

Aspendale - Edithvale - Chelsea - Bonbeach - Carrum - Seaford - Kannanook

The train runs along the Nepean Highway - we get glimpses of the turquoise ocean and the beach. Again - it would be lovely to live here. There are even a few "For Sale" signs up - we need to call Dan, the real-estate agent we've been in touch with from when we were in India.

The school kids on the train are lively and noisy, and they all seem to live within a few stops of school. There seem to be a lot more people living in these suburbs than on the Belgrave line, I think.

We reach Frankston and it starts to rain. This area has a rugged maritime beauty to it - sand and sea and gray sky pouring with rain.

It's only a 20 minute bus-ride to Dandenong City from here and we take the bus from just outside the station. Acres of quiet green farmland go by and the bus weaves in and out of bus-stops marking out the little streets crossing the highway. We reach Dandenong and get in to the station to get to Berwick.

The 4:20 to Berwick was cancelled - the next one is about 30 minutes later but lands up being delayed a quarter of an hour more. When it arrives it's crowded. Everyone is quite upset with the delays and two school girls on the train are confused about the station they want to get off. The display on the train says that the next station was the one that went by six stations ago! When they finally realize that they needed to get off where we got on, they're hysterical...

We finally arrive at Berwick and wait at the station for our friend to pick us up...

11 June 08 - Wandering around Melbourne

noreply@blogger.com (Patagonian Toothfish) — Wed, 11 Jun 2008 10:58:00 +0000

Woke up around 7:30 AM. Smitha made scrambled eggs and tea for breakfast.

Walked down to Bourke Street and took the tram to South Melbourne to get to York Street. Went to the Centrelink building but was told there was no need for me to register at all! Silly Marcus. Walked back and took the tram to Parliament. Went to the ATO and signed up for the TFN. Walked down to the apartment and had lunch - ham and cheese and fruit. Opened the bank account.

Since we had a few hours to kill and a Zone 1 day-pass in our hands, we decided to take a train out of Southern Cross as far as we could on the Frankston line - all the way to Bentleigh. The sun was setting by the time we reached, and we walked up and down the main street, looking at all the closed shops and the lighted, but empty, real-estate offices. It sure gets sleepy outside the city.

We came back to Southern Cross and took the tram over to Crown Casino to meet Marcus for dinner there. The buffet has a great spread and we were stuffed by the time we left - it was nice to have carved ham slices again. Walked around and down the bank of the Yarra river and waited for the tram back. Walked back to Lonsdale at 11:00 pm but we felt quite safe.

It was a long day and we had a blast!

10 June 08 - First Day In Melbourne

noreply@blogger.com (Patagonian Toothfish) — Tue, 10 Jun 2008 09:54:00 +0000

Woke up at 11:00 AM - needed all that sleep, and besides, that's 5:30 AM Indian time! - the rest was most welcome though.

Walked up to the DIMIA office at the corner of Spring and Lonsdale - got directions to the closest Centrelink Office (York Street or Footscray). Walked back down to Commonwealth Bank and found out details about getting a bank account. Then off to Safeway to do a proper grocery run and get something for lunch.

Found some wonderful Washington cherries and a couple of apples, rocket lettuce, swiss cheese and ham, crusty sesame rolls and some egg-salad from the deli. Came back to the apartment and made ham & cheese sandwiches for lunch.

Walked to the State Library after lunch. It's such a pleasure to go back to a proper library and be surrounded by books and music and people reading and studying - I'd quite forgotten the feeling after my college days and I must say I was very happy to be back.

Stopped off in the QV building and managed to get a post-paid connection with a phone for Smitha and a pre-paid SIM for myself. Now we are no longer incommunicado! Called Marcus who was waiting for us by that time at the apartment. Hung out with Marcus for a while, and then cooked dinner (green-pepper and sausage casserole) and ate. Tasmanian Butter is yummy.

Hello From Melbourne

noreply@blogger.com (Patagonian Toothfish) — Mon, 09 Jun 2008 07:09:00 +0000

Arrived in Tullamarine after a couple hours to change planes in Bangkok.

Thai Airways air service was average in every way - below-average in terms of food - but ok otherwise. The lack of fluency in English really shows in the way the air service staff interact with the passengers. Watched "Horton Hears A Who" and a few episodes of "Prison Break" and got to sleep on the BKK-MEL sector with an extra free seat between us. The good thing I could say was that we landed roughly on time in both Bangkok and Melbourne.

Melbourne immigration staff was friendly and efficient. Customs and immigration were a breeze, and we stepped out into the cool Melbourne air an hour or so before I thought we would.

Took a taxi from the airport to Lonsdale Street - cost us 55 bucks but I didn't have a choice! Had to wait on the street with all the baggage for Marcus and the manager of the little studio apartment we're renting. Marcus arrived to meet us after we waited for 20 minutes on the street and the manager soon after. The apartment is on the 12th floor, and is cute and surprisingly comfortable. The view out onto Lonsdale Street and the edge of China Town is beautiful.

Marcus walked with us to get some basic supplies - eggs, milk and cereal - for tomorrow's breakfast. It's quite cool outside - around 12 degrees C - and Smitha and I were very happy to have a warm bed for the night.

We'll get to see Melbourne in daylight tomorrow...

Leaving From Bangalore

noreply@blogger.com (Patagonian Toothfish) — Sun, 08 Jun 2008 18:25:00 +0000

We're leaving today for Melbourne via Bangkok.

Got to fly out from the "spanking new" BIAL airport. The drive up here from home was pretty peaceful, since we live on the outside of the Ring Road and don't have to deal with any traffic to get to the airport.

Goodbyes are always hard, and today was no different. The whole family turned up to send us off (and given the number of times we've said goodbye, to make sure we would finally leave!)

The airport is nice - not great, but nice. The staff who work here, though, think no end of themselves.

We had weight issues with at baggage counter, and the Thai Airways manager - an constipated-looking twerp with the face of a squashed beetle - was the most arrogant of all, and was not even courteous enough to look at me when we were trying to point out that the variation was under 10% (a reasonable expectation given the rough and tumble that the scales go though). He walked away when I asked him to escalate the issue, and it turned out that he was the senior-most cretin working the night. Asking them for a feedback form was met with "we have no customer-feedback form". I was seething by the time I was done with him and we took off the bags, removed about 7 kilos of stuff into a bag which we gave to our folks who were still waiting outside, and were put through the whole rigmarole of standing in line again! And when we finally reached the head of the line, we were asked to even weigh the carry-on baggage!

This is the last time I'll be dealing with Thai Airways. I'm sorry they're part of Star Alliance - I should've taken the Qantas ticket and taken the miles on my frequent-flyer account there!

The rest of the check-in procedure was a breeze. The emigration staff were courteous and efficient and very cooperative (I've only two free pages in my passport and I generally ask them to stamp their stuff on an otherwise occupied page. The security check was over before it began, and the lounge is nice and spacious. Free Internet Access (for only an hour, natch!) means that you get to see this post fresh off the presses.

They've just called for boarding and I'm going to rush. This will be the last post from Bangalore for a while now! See you from the other side of the equator!

US Patent 7165225

noreply@blogger.com (Patagonian Toothfish) — Fri, 18 Apr 2008 19:05:00 +0000

Wow! So after 7 years, the US Patent Office finally assigned this patent to Microsoft, where I worked when we filed this patent application.

http://www.patentstorm.us/patents/7165225-claims.html

Guess this makes me an "inventor" or something...*smirk*

The Virtual Machine Farm

noreply@blogger.com (Patagonian Toothfish) — Wed, 09 Apr 2008 17:57:00 +0000

Several people have asked me about how I set up the Virtual Machine Farm to make development of multiple projects on multiple platforms easy. I don't claim to be an expert in this field, but I've stood on the shoulders of giants and I have been able to get a workable solution.

The Host Hardware

I'm a roaming developer these days, so I don't have a heavy-duty, dedicated development desktop unit I can use. This may change, but I'm not likely to change the approach even if it does.

Right now I'm developing on a little Acer laptop with the following specs:

A single Turion 64x2 processor
4GB RAM (of which only 3GB is actually available - given memory-mapped IO and all)
160 GB HD partitioned into a System partition (Windows Vista Home Premium) of 40GB and a work partition of 100 GB. This work partition contains all the VMs.
A very sub-optimal 1280x800 14" display. I would change this for my old Dell's 1600x1200 in half-a-heartbeat

The host machine runs Vista Home Premium as installed by the manufacturer, with most of the third-party crud removed. I don't want to muck around too much on this system, because my goal is to be able to restore this system in about 4 minutes flat, install Microsoft Virtual PC, and get back to normal, even in the case of some very crazy crash.

Once most of the third party crap is done, Vista's footprint hovers around 1.5GB of used RAM, excluding the aggressive caching stuff it does.

It goes without saying that the Virtual PCs will benefit from beefier metal, but the system is adequate as it stands. The amount of RAM and the presence of hardware virtualization makes all the difference though, as does having a dual-core CPU. Virtual PCs simulate single-cores, and even if Virtual PC itself runs only on one core, it leaves the other core available to the host machine.

The Base Virtual Operating System

I used to prefer developing on Windows XP simply because we had Ghost images set up to get a machine up and running fast, and the OS itself is relatively skinny.

I use nLite to strip down a Windows XP SP2 installation to around 215MB or so. Since I'm installing the XP on a Virtual PC with a very small set of standard hardware devices being simulated, I can be pretty aggressive and even leave out things like drivers which bloat the typical install and serve no additional purpose.

I leave out most non-development-type things - I'll never use Windows Media Player in the VM, for example - and keep a bare minimum of the system components (IE, Notepad and Calc are essentials, for example).

Turn off System Restore and Hibernation support, and sparingly turn-off services that you know you won't need. Don't remove services even though nLite allows you to. You may need them some day in the future, and the impact on the footprint isn't worth the headache of having to re-do the whole VM farm.

Once we get a clean, light XP ISO, we can create a base Virtual Machine and install the system on there. I make the virtual HD something like 4GB in size, which after defragmentation, preparation and compaction, comes to under 2GB, and I can burn that on a single DVD. It is not surprising that the skinny OS with nothing but IE on it has a runtime footprint under 90MB in size.

You can safely allocate 256MB for this Virtual Machine and never swap the guest OS, but you won't because we will NEVER run this HD directly. It's going to form the base of a hierarchy of differenced disks, so we'll just mark it as read-only as soon as we finish running all possible updates at the time of installation. I'll take a backup onto DVD at this stage.

Tip: The Guest OS Swap File

Just in case though, I create a second virtual hard drive to act as the swap hard drive, and stick it on a flash drive made from an SD card which goes permanently into the card-reader. I do this for all other Virtual Machines I build - and the SD card doesn't have to be ReadyBoost grade, even!

Tip: Defragmentation, Preparation and Compaction

I use the Whitney Family Defragmenter to defrag all my virtual hard drives, prepare the hard drives for compaction, and compact before backing up or storing. It makes a big difference to the size of the VHD file.

Tip: NTFS Compression

I always turn OFF NTFS compression of the VHD file in the host operation, and turn ON NTFS compression of the Virtual Disk in the guest OS. NTFS compression does not work for files that are over 4GB in size.

The Development Base

I like to use Emacs for my development, and I also like my PATH and other system variables set, regardless of the development platform.

So I create a VPC using a virtual HD that differences from the Base OS HD, and install cygwin, Emacs, other tools I need, and do all the system variable and directory configuration as required. This is the one I spend time with, because tweaking things carefully here pays off later, and I won't have to do it again.

Again, I won't be using this VHD directly, since all my development platform VPCs will difference from this one. I'll mark it as read-only and take a backup onto DVD as well.

The Platforms

I usually use VS 2003 for the older projects we work on, and I've decided to use VS 2008 for the newer ones. We just skipped a whole version.

So I create two VPCs, each with hard-drives that are differenced from the Development Base VHD. It's like OO-inheritance, since both of these VPCs have the configuration I've set up carefully.

I'll install VS 2003 with full-kit on one, and VS 2008 on the other. As newer platforms are required, I'll do the same for them. These are bulky VHDs, but they carry everything they need with them and they can get a new employee or laptop fully battle-ready in less than half-an-hour.

I'll actually never use these VHDs directly either. I'll back these up on an external hard drive.

The Projects

These are individual instances of VMs, each with a VHD differencing from the appropriate platform setup, which can serve as a clean room, sequestered environment for each project. It's also easy to be able to host these VMs on a single test-bed server, configure their networking, and allow clients to do the UAT-phase of the project from a closely-monitored environment before deploying it to the field and testing it there.

In these Virtual Machines, we also hook up a separate VHD mapped to a well-known junction-point (like C:\work), which SVN can use to keep the local project copy of the repository, and from which all the building can be done. This is useful because we can backup ONLY this VHD regularly - these are lightweight enough to generally be backed up on to a single CD or a 2GB flash-drive even.

Benefits

Standardization

VM-based development platforms are by-definition identical, and we never have issues along the lines of having to deal with users' idiosyncrasies with regard to folders and paths. People can use each others' machines without any loss of productivity.

Portability is also a big benefit because we can sometimes use faster hardware while demo-ing or at a roadshow, without having to worry about whether the setup is perfect.

Backup and Redundancy

We back up at critical points, and frequently back up valuable work. In conjunction with judicious use of SVN, we can survive a many-layered failure of computing hardware and still get back to a known state relatively quickly.

Ease of Management

It's easier than one imagines to manage this farm of VMs, because each piece of software is installed exactly once. The only downside is that each leaf-node (Project) VM will have to do the incremental Windows Update, but since project life-cycles are what they are, this is fairly expected.

Demo Software

We can install demo software branching off at the appropriate level on the tree to check out stuff before rolling it out into our general use. The most recent case-in-point is actually the VS 2008 tree, which has a trunk with the stock install, and a fork with the Silverlight beta and other not-yet-ready-for-primetime stuff.

Conclusion

I hope this post helps someone.

It'll certainly make things clearer to me when I read things next year and wonder why we're doing something like this!

If anyone wants specifics on things like which services I've turned off, which system modules I've deleted with nLite, or what development tools I use, shoot me a mail and I'll consider a follow up of this document.

Technorati Tags: Microsoft Virtual PC,Visual Studio,Software Development,System Management

Silverlight Weirdness (the sequel to Silverlight Woes)

noreply@blogger.com (Patagonian Toothfish) — Wed, 09 Apr 2008 13:06:00 +0000

First off, let me thank Scott Guthrie for taking the time to respond to my mails and pointing me to Peter Puszkiewicz, and let me thank him for helping me debug this situation...

Peter requested that I try the following steps:

<quote>

1. I'll call this one out, but it's a lot of work, so maybe don't try this first. you seem to have a lot of stuff installed (including two versions of Blend)... why don't you clean your vm and start by just following Bradley's post. Get the base package running, then add to it to find the culprit

2. go to Silverlight.net and view a Silverlight sample. Does the control launch for you at all? does it launch for a beta 1 sample? Best way to be sure is to right-click on screen space that you expect to be Siverlight and check to see if a menu with the sigle item "Silverlight Configuration" shows up

3. Can you send me the full registry hive for the Silverlight ClSID? I remember that some tools expected to find progID AgControl.AgControl to find a path to npctrl.dll... this may still be the case

4. Along those lines, can you run Process Monitor, attach (filter) it to your instance of devenv.exe, and send me a dump of what is happening while you are trying to start up the Silverlight project? I'd like to see what it's looking for an not finding. If you're not familiar, Process Monitor is a great tool from Microsoft/SysInternals which allows you to monitor HDD/Registry requests from processes. It is also free:)

5. Make sure you have access to (read access) to all Silverlight dll's/registry keys. You can find the relevant keys by looking for posts from DHarvey on the Silverlight.net forums. Alternatively, I can send them tomorrow.

6. Try running VS as an admin

</quote>

Now, I had started with a clean VM with nothing but Visual Studio to start with, and I'd never been able to get the base package working. The installation of Blend was more an act of desperation hoping the installation would iron out any wrinkles in the VS 2K8 install, so I wasn't going to try this instanter...
I remember having been to Silverlight.net and trying time-after-time to install Silverlight, which would report a successful installation but request me to install again. I thought I fixed that somehow!
I did this - walking all over the registry and looking for anything weird. Never found anything out of the ordinary here...
This was a good thing to try. But before I started doing this, I decided to verify Step 2 again.
This was a given since I was running the VM as an Administrator.
Ditto...

Now I've followed some pretty interesting steps to set up my Virtual Machine farm, so I decided to start at the root installation - a VM with nothing on it but a light version of Windows XP SP2, properly patched and updated. So no Visual Studio, no Microsoft Office, nothing!

I fired up IE and sauntered on to http://silverlight.net/showcase.

Right there, I realized that I had NEVER been able to install Silverlight properly. I then spent the next 2 hours installing and re-installing Silverlight, and turning on several services I had earlier turned off to tweak the VM installation to have a smaller footprint - each time being told the install was successful, but only to be invited to reinstall when I went to check out the showcase. The installation log and Event Viewer both showed me that the installations were "successful"!

It lies like a Persian Rug!

Then I got the idea of running procmon while IE loaded http://silverlight.net/showcase and trying to figure out what went wrong. After combing through about 25,000 lines of diagnostics looking for weirdness, I found that IE reported that it had successfully loaded the Silverlight DLLs!

The only innocent-looking failure was that it couldn't load DSOUND.dll - fair enough, you don't need DirectSound to browse the web, do you?

Now since I was running a development environment in a virtual machine, I reasonably assumed I wasn't going to need Wireless Networking, UPnP, Sound, System Restore, Help and Support, Windows Media Player among other modules which only contribute bloat to a development environment. I had therefore stripped them out using nLite before installing my development tools.

Anyway - just to cover all bases, I fished out a dsound.dll from another Windows XP installation and plonked it into the VM - and whadyaknow - it worked!! I was able to view all the Silverlight demonstrations I could find.

I must confess I'm a little peeved by the strange dependency that Silverlight has on sound, of all things! This is supposed to be a development and web-application platform - and while it's arguable that sound and video make the user experience rich and cool, I don't think that it's defensible to make sound a mandatory prerequisite of the platform - and it's completely inexpiable that the platform would die without giving a clue of this strange dependency!

In sum - I'm finally able to get started on Silverlight.

At least I know His Gu-ness will respond to a mail in a timely manner if I'm similarly stumped the next time! And I can always use procman before mailing him next time!

Technorati Tags: Silverlight,Visual Studio 2008

Silverlight Woes

noreply@blogger.com (Patagonian Toothfish) — Tue, 08 Apr 2008 08:30:00 +0000

So I've installed VS 2008, and all the stuff required to check out the Silverlight platform on a fresh new Virtual PC dedicated to do nothing else!

Here's all the stuff installed:

Release version of Visual Studio 2008
Silverlight Tools Beta 1 for Visual Studio 2008 from http://www.microsoft.com/downloads/details.aspx?FamilyId=E0BAE58E-9C0B-4090-A1DB-F134D9F095FD&displaylang=en
Expression Blend, Expression Web
Blend 2 December Preview, Blend 2.5 March 08 Preview, ASP.NET MVC Preview 2 from Microsoft Downloads

I've already read BradleyB's blog posts at http://weblogs.asp.net/bradleyb/archive/2008/03/06/installation-tips-for-sivliverlight-tools-beta-1-for-visual-studio-2008.aspx, and have followed all the instructions therein!

My System Setup after all the jazz installed is:

Fired up VS and created a new Silverlight project, and expected to be able to write the canonical Hello World...and this is what I got:

Fine - this might be some general first-boot problem. If you try to "Reload the designer", as suggested, I get:

Hmm...looks like it either really can't find the control, or there's some weirdness with Visual Studio acting as a Silverlight host!

Rooted around the Registry looking for the CLSID in question, and sure enough, it refers to AgControl.AgControl1 - the Silverlight control. Now, if I remember correctly, an HRESULT of 0x8007007e generally indicates "File Not Found". The InprocServer for this control points to the Silverlight installation directory, and to a valid DLL. What gives?

I've hunted all over the web for anyone reporting this weirdness, without success. I've re-installed everything on a clean VM with only the stock Visual Studio 2008 as a starting point.

Next attempt will be to try with Visual Studio 2005 and Silverlight!

Bummer...I was really looking forward to using Linq and all...

Finally, anyone who has a clue about what may help can mail me at john.azariah-at-gmail.com! Thanks

Technorati Tags: Silverlight,Visual Studio 2008

Wooot!

noreply@blogger.com (Patagonian Toothfish) — Wed, 30 Jan 2008 09:25:00 +0000

My company is now ISO 9001:2000 certified!

The Importance Of Marketing

noreply@blogger.com (Patagonian Toothfish) — Wed, 30 Jan 2008 07:19:00 +0000

Both the ISO auditors are keen on, and very knowledgeable about, Indian food. Being foodies ourselves, we were joking with them about the best biriyani in the world being made in Bangalore - even after taking into account Delhi, Karachi and Hyderabad. (Let the ~~flame~~ cookout wars begin!)

Anyway - come lunch time, and we decided to drive down to a South-Indian restaurant in Serangoon Road. Anyone who has been to Serangoon Road knows how the aromas of each restaurant on the street loudly proclaim the goodies obtainable inside. We stood outside the restaurant we had chosen, waiting for admittance behind a crowd of people, when we spied a place that billed itself as a Hyderabadi Biriyani house, and walked over.

While all the places around it were buzzing and overflowing with the lunch crowd, this place was empty.

Empty! In Singapore! This is a place where a hawker can viably sell food at 2 AM, on a Thursday morning, in Tampines, in the rain! We were stunned, but since Peter had eaten there before and vouched for the food, we went in and sat down anyway.

The service was predictably good - we were the only customers there after all. The food arrived on time and there was a rude plenty of it. It even tasted fantastic - probably the best Hyderabadi biriyani I've had outside Hyderabad, and definitely better than a good many I've had inside. A thoroughly good time was had by all, and several people in the group were publicly discussing what they were going to order again when they came back!

We were puzzled how an Indian restaurant, in the middle of Little India, with excellent food and decor, could be empty during the lunch crowd when people were queuing up outside the neighbours. Puzzled enough to accost the head waiter and ask him when he brought us the post-prandial tea.

His response stunned us - the owners didn't want to invest in marketing!

Imagine that - you invest in infrastructure, rent a place in the right location, serve a darn fine lunch, impress customers enough to want to come back to you, but don't invest in marketing! One wonders if the owner might have become more 'profitable' by closing down the place, firing the chefs, and selling away his equipment!

That's an interesting lesson for a geek like me - that success in selling something is at least as dependent on marketing as it is on getting the product done right...products don't actually sell themselves all the time!