TL;DR; I published my first Windows Phone application to get familiar with the tools. It is a visual Brainfuck interpreter. The code is published on GitHub. You can get the app from the Windows Phone marketplace. These series of articles detail my experience switching to the new development platform.

NOTE: THIS IS NOT A TUTORIAL. DO NOT COPY CODE BECAUSE IT IS LIKELY THAT IT DOES NOT FOLLOW BEST PRACTICES.


Part 0 - Visual Brainfuck for Windows Phone
Part 1 - The Interpreter
Part 2 – XAML and Tools
Part 3 - MVVM
Part 4 - Animations


The articles will not quote all the code they refer to. You can view the code directly on GitHub.

Immutability

   At first I intended to write an immutable interpreter. After some thought I decided against it because an immutable interpreter would require that the tape (array of bytes) is cloned on each step of the execution. The array could potentially grow to thousands of bytes and I was afraid that this could lead to bad performance and high memory usage. Maybe there is some functional programming trick to work around this issue but I could not think of it so my array and the pointers in the interpreter stayed mutable.

Threading

   My first version of the interpreter spawned a thread inside it and raised events to report changes in state like changing value of a cell or moving the pointer. However when I thought how I could implement step by step execution in the future it became obvious that this design is wrong and threading really belongs to the ViewModel. This caused the interpreter to be rewritten in a way where it exposed a sequence of execution steps which the UI could consume one by one in a loop while managing the thread. The interpreter is not thread safe and it only reports its state when a step is finished (via the StepInfo class) and not in between. The caller provides locking while executing a step or extracting state. In both version of the interpreter it accepts callback delegates to handle output and input provided by the caller.

The Interpreter and Tombstoning

   Windows Phone does not have true multitasking. When the user navigates away from the app the OS pauses it and sometimes kills it to save memory and battery power. Before the app is killed it has the chance to save its state. A process known as Tombstoning. When the user navigates back to the app the app it is started and can resume from Tombstoning. It gets its state back, restores it and continues execution.

   The most interesting part about the Tombstoning in BF for WP is saving and restoring the state of the interpreter especially when it is running on a separate thread. If I had implemented an immutable interpreter I would not have had any problems – just get the last state and save it. However a mutable interpreter needs a way to extract valid state and not some intermediate result and this is why there are locks around the ExecuteStep and GetInterpreterData method calls. Here is the GetInterpterData method which also demonstrates what state is stored:

public InterpreterData GetInterpreterData()
{
   return new InterpreterData
   {
       Source = source,
       SourceIndex = sourceIndex,
       Tape = (byte[])tape.Clone(),
       TapeIndex = tapeIndex,
       InternalState = internalState,
       CellWindowRadius = CellWindowRadius,
       LoopsBeginnings = loopsBeginnings.ToArray()
   };
}
   Source is the source code of the Brainfuck program, tape is the array of bytes and it is cloned so that it is not changed later, tapeIndex is the index of the tape pointer, InternalState will be discussed later, CellWindowRadius is not really important here and LoopBeginnings are the indexes where currently executing loops start (the '[' in BF code). Note that the opposite of loop beginnings is not needed as part of the state because it is only needed when the Brainfuck loop should not be executed (should be jumped over) and this always happens in a single execution step.

   The first problem I ran into was that Stack<T> (used for loop beginnings) is not serializable on Windows Phone. List<T> is serializable  on the phone and Stack<T> is serializable in normal .NET Framework. Go figure! I had to dump it in an array and make sure it is restored in reverse order.

   The second problem was far more severe. I was using this method to create the inner loop of the interpreter:

public IEnumerable<StepInfo> Run()
{
   sourceIndex = 0;
   tapeIndex = 0;
   tape = new byte[256];
   loopsBeginnings.Clear();

   if (String.IsNullOrEmpty(source))
   {
       yield return new StepInfo(StepType.End, -1, null);
       yield break;
   }

   while (sourceIndex < source.Length)
   {
       yield return ProcessToken();
       sourceIndex++;
   }

   yield return new StepInfo(StepType.End, sourceIndex, GetVisibleCells());
}

I am somewhat proud of this code. It uses the iterators feature to manage the state of the interpreter and uses nice single method with a loop to do all the processing. The iterator introduced in C# 2.0 builds a state machine internally to facilitate this. It is called "state machine" for a reason – it has state. Because I need to restore this state and the iterators feature hides it I had to replace the Run method with this much uglier method:

public StepInfo ExecuteStep()
{
   switch (internalState)
   {
       case InternalInterpreterState.Uninitialized:
           sourceIndex = 0;
           tapeIndex = 0;
           tape = new byte[256];
           loopsBeginnings.Clear();
           if (String.IsNullOrEmpty(source))
           {
               internalState = InternalInterpreterState.Finished;
               return new StepInfo(StepType.End, -1, null);
           }

           internalState = InternalInterpreterState.Running;
           return ProcessToken();
       case InternalInterpreterState.Running:
           sourceIndex++;
           if (sourceIndex < source.Length)
           {
               return ProcessToken();
           }

           internalState = InternalInterpreterState.FinalStep;
           goto lbFinalStep;
       case InternalInterpreterState.FinalStep:
       lbFinalStep:
           internalState = InternalInterpreterState.Finished;
           if (loopsBeginnings.Count == 0)
           {
               return new StepInfo(StepType.End, sourceIndex, GetVisibleCells());
           }
           else
           {
               return new StepInfo(StepType.UnmatchedOpeningBracketLoopError, loopsBeginnings.Pop() + 1, GetVisibleCells());
           }
       case InternalInterpreterState.Finished:
           throw new Exception("Execution has finished");
       default:
           throw new Exception("Unexpected internal state");
   }
}

The internalState field keeps the state of the state machine. I was sad to see my cool method go but on the bright side I got a chance to use goto legitimately and annoy purists.

   The moral of the story? State hides in the strangest of places.

   In part 2 of the series I am going to report my experience with XAML and the Windows Phone APIs.