An algorithm interpreter in C# for WinRT
C#
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
Sources
Tests
Tools
.gitattributes
.gitignore
Algo.sln
AlgoBASIC syntax example.docx
CHANGELOG.md
README.md

README.md

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

  1. First of all, we create a Program that represents a program with classes and methods.
  2. We add our global variables (it is simpler to manage in the algorithm interpreter).
  3. 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 :
  1. And then, we start the Simulator.

What Does The Simulator

  1. The first step is to create a dictionary that contains a definition of each variable in the project and their associated values.
  2. 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