Turing machine implementation with WF4 and FlowChart

A couple of days ago I received a tweet about a real hardware implementation of the Turing Machine (http://www.aturingmachine.com/). Impressed about this implementation, I was thinking about how to implement a simple Turing Machine counting program with the use of Workflow Foundation 4. And that’s where the story starts about my first experience with WF4.

Turing machine definition

At Wikipedia a definition of the Turing machine can be found: http://en.wikipedia.org/wiki/Turing_machine. To keep it short, a Turing machine consists of two parts

• A tape of unlimited length which is separated in cells
• A machine that can read/write on the tape

The machine is a finite state machine. The machine is in one state and with the use of a set of rules the machine can transfer to a different state. A rule contains the following parts

• current state
• symbol read
• next state
• symbol to write
• move direction

The following rule [state: 0, read: blank, new state: 1, write: blank, move: left] will be executed by the machine when the current state is 0 and the value of the cell on the tape is blank. When the rule is executed, the machine will transfer to state 1, keeps the cell blank and will move the tape one cell to the left. A next rule for state 1 will be executed based on the new cell value read on the new tape position.

The machine part will be written with the use of a workflow diagram. This diagram will contain the different states and rule actions.

Counting rules

The rules for making counting possible (as taken from the aturingmachine.com website)

[state: 0, read: 1, new state: 0 write: 1, move: right]
[state: 0, read: 0, new state: 0, write: 0, move: right]
[state: 0, read: blank, new state: 1, write: blank, move: left]

[state: 1, read: 0, new state: 0, write: 0, move: right]
[state: 1, read: 1, new state: 1, write: 0, move: left]
[state: 1, read: blank, new state: 0, write: 1, move: right]

Tape implementation

The tape is a collection of cells which has an unlimited length. New cells can be added at the start or end of the written tape part. To support this functionality, an implementation is made based on a List collection making it possible to not only add new values at the end of the tape but also at the beginning.

public class Tape : ITape
    {
        public int Position { get; private set; }
        public int Length { get { return _internalCollection.Count; } }

        private List<int?> _internalCollection;

        public Tape()
        {
            Position = 0;
            _internalCollection = new List<int?>(){null};
        }

        public int? ReadCell()
        {
            return _internalCollection[Position];
        }

        public void WriteCell(int? cellValue)
        {
            _internalCollection[Position] = cellValue;
        }

        public void MoveCell(MoveDirection direction)
        {
            switch(direction){
                case MoveDirection.Left:
                    if (Position == 0)
                    {
                        _internalCollection.Insert(0, null);
                    }
                    else
                    {
                        Position--;
                    }
                    break;
                case MoveDirection.Right:
                    Position++;
                    if (Position == _internalCollection.Count)
                    {
                        _internalCollection.Add(null);
                    }
                    break;
            }
        }

        public override string ToString()
        {
            StringBuilder tapeValue = new StringBuilder("[");
            foreach (var cell in _internalCollection)
            {
                if (cell == null) { tapeValue.Append(" "); } else { tapeValue.Append(cell.ToString()); }
            }
            tapeValue.Append("] ");
            return tapeValue.ToString();
        }
    }

Flowchart

The state workflow of Workflow Foundation 3 is not part of version 4. The alternative given is the flowchart. With the flow chart certain types of state machine workflows can be implemented (but not all of them). A flowchart is powerful and simple to use, making it possible to loop back to previous executed activities. This is very useful for moving between the different states.

Together with the Flowchart, two activities are introducted: FlowDecision and FlowSwitch. A FlowDecision can be seen as an if condition while the FlowSwitch is like a switch statement in code. The FlowSwitch will be the central decision node for each state within the turing machine counting implementation

Workflow implementation with standard activities

A console workflow application is used for this implementation. An instance of the Tape is set as variable on the FlowChart.

The counting program can be developed with the use of the standard activities provided by WF4. The following activities are used

• FlowSwitch: based on the cell value an execution path is chosen
• InvokeMethod: used for executing the WriteCell and MoveCell methods
• WriteLine: write the value of all cell values to the console.
• Delay: this activiity is optional. Some delay to make output more readable during execution

The default path of the FlowSwitch activity is used for supporting the blank values. This is because of the fact that FlowSwitch works with string values, making it impossible to define a path for a null value.

Custom activities

The InvokeMethod activity is a generic activity to make execution of a method possible. It takes some time to configure each activity. The method parameters (for example the cell value which should be written) are implemented as a Parameter collection, which are not directly visible from the property editor within Visual Studio. To simplify/fasten this assignment process, custom activities will be developed to support the specific methods on the Tape instance.

Custom code activities are based on the CodeActivity or NativeActivity class. The CodeActivity is for creating simple synchronous custom activities. This model is suitable for the custom activities needed by the turing machine workflow. When you want to use all of the functionality exposed by the WF4 runtime, you should use the NativeActivity base class.

Two custom activities are developed

• MoveCell activity: for moving the position on the tape one cell. The Direction property holds the move direction
• WriteCell activity: for writing a cell value on the current position. The CellValue property holds the value which should be written

namespace TuringMachine.Activities
{
    [Designer(typeof(MoveCellDesigner))]
    public sealed class MoveCell : CodeActivity
    {
        [RequiredArgument()]
        public InArgument<ITape> Tape { get; set; }

        public MoveDirection Direction { get; set; }

        protected override void Execute(CodeActivityContext context)
        {
            var tape = context.GetValue(Tape);
            tape.MoveCell(Direction);
        }
    }
}

namespace TuringMachine.Activities
{
    [Designer(typeof(WriteCellDesigner))]
    public sealed class WriteCell : CodeActivity
    {
        [RequiredArgument()]
        public InArgument<Nullable<int>> CellValue { get; set; }

        [RequiredArgument()]
        public InArgument<ITape> Tape { get; set; }

        protected override void Execute(CodeActivityContext context)
        {
            var tape = context.GetValue(Tape);
            var cellValue = context.GetValue(CellValue);

            tape.WriteCell(cellValue);
        }
    }
}

The InArgument type used for the properties can hold (besides a value like a normal property) an expression. Those expression are defined using the VB.Net language (so null should be defined as Nothing)

The custom activities are added to the Workflow Toolbox making it possible to drag them into the workflow. You can change the property values from within the Property editor

Custom design

When viewing the diagram, it is still not directly clear which values are written and to which direction the position on the tape is moved. WF4 makes it possible to assign a design to a custom activity. The design of the activity is developed with XAML. Assignment is done with the use of the Designer attribute (as shown in the code above)

The XAML used for the MoveCell activity makes it possible to directly select the move direction from within the diagram

<sap:ActivityDesigner x:Class="TuringMachine.Activities.Designer.MoveCellDesigner"
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    xmlns:sap="clr-namespace:System.Activities.Presentation;assembly=System.Activities.Presentation"
    xmlns:sapv="clr-namespace:System.Activities.Presentation.View;assembly=System.Activities.Presentation"
    xmlns:sys="clr-namespace:System;assembly=mscorlib"
    xmlns:tm="clr-namespace:TuringMachine.Classes;assembly=TuringMachine.Classes">
    <sap:ActivityDesigner.Resources>
        <ObjectDataProvider MethodName="GetValues" ObjectType="{x:Type sys:Enum}" x:Key="MoveDirectionValues">
            <ObjectDataProvider.MethodParameters>
                <x:TypeExtension TypeName="tm:MoveDirection"/>
            </ObjectDataProvider.MethodParameters>
        </ObjectDataProvider>
    </sap:ActivityDesigner.Resources>
    <Grid>
        <Grid.ColumnDefinitions>
            <ColumnDefinition Width="auto"/>
            <ColumnDefinition Width="*"/>
        </Grid.ColumnDefinitions>
        <Grid.RowDefinitions>
            <RowDefinition Height="*"/>
        </Grid.RowDefinitions>
        <TextBlock VerticalAlignment="Center">Direction:</TextBlock>
        <ComboBox Grid.Column="1" ItemsSource="{Binding Source={StaticResource MoveDirectionValues}}" SelectedValue="{Binding ModelItem.Direction, Mode=TwoWay}"></ComboBox>
    </Grid>
</sap:ActivityDesigner>

And the WriteCell Activity makes the cell value assignment possible from within the workflow diagram. For the WriteCell activity an ExpressionTextBox is used, supporting the InArgument expression possibilities.

<sap:ActivityDesigner x:Class="TuringMachine.Activities.Designer.WriteCellDesigner"
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    xmlns:sap="clr-namespace:System.Activities.Presentation;assembly=System.Activities.Presentation"
    xmlns:sapv="clr-namespace:System.Activities.Presentation.View;assembly=System.Activities.Presentation"
    xmlns:conv="clr-namespace:System.Activities.Presentation.Converters;assembly=System.Activities.Presentation"
    xmlns:local="clr-namespace:TuringMachine.Activities.Designer"
    xmlns:sys="clr-namespace:System;assembly=mscorlib">
  <sap:ActivityDesigner.Resources>
    <conv:ArgumentToExpressionConverter x:Key="expressionConverter"/>
  </sap:ActivityDesigner.Resources>
  <Grid>
        <Grid.ColumnDefinitions>
            <ColumnDefinition Width="auto"/>
            <ColumnDefinition Width="*"/>
        </Grid.ColumnDefinitions>
        <Grid.RowDefinitions>
            <RowDefinition Height="*"/>
        </Grid.RowDefinitions>
        <TextBlock VerticalAlignment="Center">Cell value</TextBlock>
        <sapv:ExpressionTextBox Grid.Column="1" Expression="{Binding Path=ModelItem.CellValue, Mode=TwoWay, ConverterParameter=In, Converter={StaticResource expressionConverter}}" ExpressionType="{local:NullableExtension sys:Int32}" OwnerActivity="{Binding Path=ModelItem}"></sapv:ExpressionTextBox>
    </Grid>
</sap:ActivityDesigner>

Workflow implementation with custom activities

With the use of the developed custom activities together with their design, the diagram of the workflow will give us directly more information related to the execution of the program

What’s next?

My first impression about WF4 is that the usage is more simplified. Within the previous version of WF you had to write a lot of code to execute external methods. With the use of the CodeActivity (or NativeActivity) class it is easy to implement custom activities. The possibility to use XAML to layout your custom activities is very powerful. It makes it possible to implement diagrams which are visual more meaningful (especially useful when hosting the WF designer within your own application). While the FlowChart is not a real State Workflow, it is suitable for the implementation written above. The usage feels more natural, just like developing a sequence workflow.

While developing the counting workflow I had some issues with the support of Nullable types and the ExpressionTextBox. I needed to implement an TypeExtension to make it possible to define the ExpressionType as a Nullable. This was not what I expected because XAML 2009 (XAML version of .Net 4) should make it possible to define the type as {x:Type TypeName=System:Nullable`1[[System.Int32]]}. But this syntax is not accepted as valid.

Source code

The visual studio 2010 solution including the workflows and source code files can be found at (http://johandekoning.codeplex.com -> browse to WF/TuringMachine)