Awesome

Algorithm Simulator

This is a prototype of a portable algorithm interpreter based on the architecture of SoftwareZator.

What Is The Concept

The concept is to be able to simulate and debug an algorithm by using C# at runtime. For a bigger challenge, we want to be able to use it in a cross-platform project.

It means several things :

I will be unable to use CodeDom or Roslyn to compile code and run it.
I also will be unable to use the Windows Debugger as it is not available with WinRT.
So, I will make my own CodeDom-like architecture, named AlgorithmDom.
And make an interpreter that will analyze the AlgorithmDom and perform an action depending of it.

Remark : the code is not very complicated, but the project architecture is complex because it uses a LOT of abstraction.

Use Case

Any programming learning app (SoftwareZator, Spark, Scratch...).
If you want to download a part of an application from internet in WinRT and want to run it. I guess that we cannot load an Assembly at runtime with WinRT. Download an algorithm and interpret it can be a solution.

Features

Features	Supported
start the algorithm interpreter	yes
stop the algorithm interpreter (even in an infinite loop)	yes
pause the algorithm interpreter	yes
debug mode	yes
[debug mode] step over	yes
[debug mode] step into	yes
[debug mode] step out	yes
[debug mode] breakpoint	yes
variable	yes
array	yes
class	yes
class properties	yes
method	yes
recursivity	yes
loop (while/do while)	yes
call a method	yes
use feature from .Net/WinRT	yes
detect when a user call too many methods in the same thread (aka. stack overflow)	yes
async functions	yes
keep a call stack with info on variables values	yes
try catch	no
interaction with the UI	no
inheritance with classes	no
idle the program	no
programming language parser	no

Performances

Performances are not comparable with a JavaScript runtime or a compiled language like C++. The reason is that this interpreter is made in C# and it's designed to be maintenable, more than fast. It also use a lot of RAM.

Scenarios	Execution time (in millisec)
a loop with 100 iterations	17.5 at first run, 6.6 at second run

The first time you run the interpreter, in particular when you start to run it, performances can be much slower than the second time you run the same program. The reason is that the interpreter put in cache some data used to optimize the execution speed of the binary operator.

How Does It Work

First of all, we create a Program that represents a program with classes and methods.
We add our global variables (it is simpler to manage in the algorithm interpreter).
In a method, we add an algorithm. This algorithm is represented by an action. An action, in SoftwareZator, as in this algorithm interpreter, it is a part of an algorithm that does something. For example :

Assign a value to a variable
Read a file
Do an HTTP request
Display a message
...etc

And then, we start the Simulator.

What Does The Simulator

The first step is to create a dictionary that contains a definition of each variable in the project and their associated values.
Then, we start to simulate/interpret each Action of the algorithm :

We display in the Debug the value of each variables of the project (like Visual Studio does on a breakpoint).
The action will generate an AlgorithmDom (my cross-plateform CodeDom-like architecture)
And we will ask to the Interpreter to analyze it and change, for example, the value of a variable if tha AlgorithmDom is corresponding to an assignation.
In case of exception in the algorithm (for example : I want to read a file that does not exists), we ask to the current Action to bring us some tips to fix this error (imagine that we are in SoftwareZator for example :-) ).

Sample

The following algorithm :

PROGRAM MyApp

    CLASS FirstClass

        FUNCTION Main()
            RETURN FirstMethod(10)
        END FUNCTION

        FUNCTION FirstMethod(num)
            IF (num > 1)
                RETURN FirstMethod(num - 1)
            RETURN num
        END FUNCTION

    END CLASS

END PROGRAM

Can be translated and interpreted by the algorithm interpreter like this in C# :

var program = new AlgorithmProgram("MyApp");
var firstClass = new AlgorithmClassDeclaration("FirstClass");

var entryPoint = new AlgorithmEntryPointMethod(); // FUNCTION Main()
entryPoint.Statements.Add(new AlgorithmReturnStatement(new AlgorithmInvokeMethodExpression(new AlgorithmThisReferenceExpression(), "FirstMethod", new AlgorithmPrimitiveExpression(10)))); // RETURN FirstMethod(10)
firstClass.Members.Add(entryPoint);
    
var firstMethod = new AlgorithmClassMethodDeclaration("FirstMethod", false);
firstMethod.Arguments.Add(new AlgorithmParameterDeclaration("num")); // FUNCTION FirstMethod(num)

var argument = new AlgorithmBinaryOperatorExpression(new AlgorithmVariableReferenceExpression("num"), AlgorithmBinaryOperatorType.Subtraction, new AlgorithmPrimitiveExpression(1)); // num - 1

var returnStatement = new AlgorithmReturnStatement(new AlgorithmInvokeMethodExpression(new AlgorithmThisReferenceExpression(), "FirstMethod", argument)); // RETURN FirstMethod(num - 1)

var condition = new AlgorithmBinaryOperatorExpression(new AlgorithmVariableReferenceExpression("num"), AlgorithmBinaryOperatorType.GreaterThan, new AlgorithmPrimitiveExpression(1));
firstMethod.Statements.Add(new AlgorithmConditionStatement(condition, new AlgorithmStatementCollection() { returnStatement }, null)); // IF (num > 1)
firstMethod.Statements.Add(new AlgorithmReturnStatement(new AlgorithmVariableReferenceExpression("num"))); // RETURN num

firstClass.Members.Add(firstMethod);

program.Classes.Add(firstClass);
program.UpdateEntryPointPath();

var algorithmInterpreter = new AlgorithmInterpreter(program);

var task = algorithmInterpreter.StartAsync(debugMode: true);

task.Wait();

Change log

Check the change log here