Untitled

using System;

namespace Abstrakte_Uebung1
{
        internal class StackMachine
        {
                private static void Main()
                {
                        // escape the static context (this is a C# class)
                        new StackMachine().Interpret();
                }


                // although this is C# code, everything is declared "C-like" (arrays, indexers to arrays ~ pointers... )

                // the stack
                private int[] stackMemory = new int[1024];
                private int sp = -1;
                private int fp = -1;

                // contains the actual program code
                private Operation[] programMemory = new Operation[1024];
                private int pc = 0;

                // memory for function arguments
                private int[] argumentMemory = new int[1024];

                private void Interpret()
                {
                        // would normally parse an input file
                        LoadProgram(programMemory);

                        while(true)
                        {
                                // fetch instruction
                                OpCode instruction = programMemory[pc].Instruction;
                                int intArgument = programMemory[pc].IntArgument;
                                string stringArgument = programMemory[pc].StringArgument;

                                // increment program counter
                                pc++;

                                // execute instruction
                                switch(instruction)
                                {
                                        case OpCode.Ldc:

                                                // load constant - push argument onto stack
                                                stackMemory[++sp] = intArgument;
                                                break;

                                        case OpCode.Add:

                                                // add - pop two arguments, add them, push result back onto stack
                                                sp--;
                                                stackMemory[sp] = stackMemory[sp] + stackMemory[sp+1];
                                                break;

                                        case OpCode.Eq:

                                                // equals - like add, but compare the values, push 1 if equal, 0 otherwise
                                                sp--;
                                                stackMemory[sp] = stackMemory[sp] == stackMemory[sp+1] ? 1 : 0;
                                                break;

                                        case OpCode.End:

                                                // end instruction - print result (= last element on stack) and end interpretation
                                                Console.WriteLine("Result: " + stackMemory[0]);
                                                Console.Read();
                                                return;

                                        case OpCode.Call:

                                                // push current PC onto stack
                                                stackMemory[++sp] = pc;

                                                // update pc to location after the label
                                                int addressOfLabel = GetAddressOfLabel(stringArgument);
                                                pc = addressOfLabel + 1;
                                                break;

                                        case OpCode.Ret:

                                                // restore old pc
                                                pc = stackMemory[sp - 1];

                                                // remember return value
                                                int retVal = stackMemory[sp];

                                                // move sp down
                                                sp = fp;

                                                // restore old FP
                                                fp = stackMemory[fp];

                                                // write return value to sp
                                                stackMemory[sp] = retVal;
                                                break;

                                        case OpCode.Goto:

                                                // simple update pc
                                                pc = GetAddressOfLabel(stringArgument);
                                                break;

                                        case OpCode.GoFalse:

                                                // check if top element of stack is 0
                                                if (stackMemory[sp] == 0)
                                                {
                                                        // if true, update pc to location after label
                                                        pc = GetAddressOfLabel(stringArgument) + 1;
                                                }

                                                // discard top element (= condition) in any case
                                                sp--;
                                                break;

                                        case OpCode.BindArg:

                                                // get from stack (according to Frame Layout)
                                                argumentMemory[intArgument] = stackMemory[fp + 1 + intArgument];
                                                break;

                                        case OpCode.GetArg:

                                                // load value from specified location and push onto stack
                                                stackMemory[++sp] = argumentMemory[intArgument];
                                                break;

                                        case OpCode.Mark:

                                                // mark the beginning of a stack frame
                                                stackMemory[++sp] = fp;
                                                fp = sp;
                                                break;

                                        /* Stackframe Layout (growing upwards):
                                         *
                                         * ---------------
                                         * Callee Stack...
                                         * ---------------
                                         * Old PC
                                         * ---------------
                                         * ...
                                     * Locals
                                         * ---------------
                                         * ...
                                     * Arguments
                                         * ---------------
                                         * Old FP          <- FP
                                         * ---------------
                                         * Caller Stack...
                                         * ---------------
                                         */

                                        // calling conventions:
                                    //
                                        // before call:
                                        // caller has to mark the beginning of the stackframe
                                        // and then push the arguments followed by the locals (that need saving)
                                        //
                                        // after call:
                                        // if locals were pushed, caller has to restore them
                                        // (SP will point to the former marked stack location after the call)
                                }
                        }
                }

                // helper function, finds the address of a label in the program memory
                private int GetAddressOfLabel(string label)
                {
                        int addressOfLabel = 0;

                        for (int i = 0; i < 1023; i++)
                                if (programMemory[i].Instruction == OpCode.Label &&
                                        programMemory[i].StringArgument == label)
                                        addressOfLabel = i;
                        return addressOfLabel;
                }


                // operations are defined by a code and and optional arguments
                private struct Operation
                {
                        public OpCode Instruction { get; set; }
                        public int IntArgument { get; set; }
                        public string StringArgument { get; set; }
                }


                enum OpCode
                {
                        Ldc,
                        Add,
                        Eq,
                        End,
                        Call,
                        Ret,
                        Label,
                        GoFalse,
                        Goto,
                        BindArg,
                        GetArg,
                        Mark,
                }

                private void LoadProgram(Operation[] memory)
                {
                        // main function
                        memory[0] = new Operation { Instruction = OpCode.Mark };
                        memory[1] = new Operation { Instruction = OpCode.Ldc, IntArgument = 2 };
                        memory[3] = new Operation { Instruction = OpCode.Call, StringArgument = "DoubleTo65536" };
                        memory[4] = new Operation { Instruction = OpCode.End };


                        /*
                         * Get constant value.
                         *
                         * FUNC GetFourtyTwo()
                         *    42
                         * END
                         */
                        memory[500] = new Operation { Instruction = OpCode.Label, StringArgument = "GetFourtyTwo" };
                        memory[501] = new Operation { Instruction = OpCode.Ldc, IntArgument = 42 };
                        memory[502] = new Operation { Instruction = OpCode.Ret };

                        /*
                         * Get calculated value.
                         *
                         * FUNC GetFivePlusTwo()
                         *    5 + 2
                         * END
                         */
                        memory[600] = new Operation { Instruction = OpCode.Label, StringArgument = "GetFivePlusTwo" };
                        memory[601] = new Operation { Instruction = OpCode.Ldc, IntArgument = 5 };
                        memory[602] = new Operation { Instruction = OpCode.Ldc, IntArgument = 2 };
                        memory[603] = new Operation { Instruction = OpCode.Add };
                        memory[604] = new Operation { Instruction = OpCode.Ret };


                        /*
                         * Check if without else.
                         *
             * FUNC CheckIf()
             *    IF 4 + 2 = 6 THEN 100 END
             * END
             */
                        memory[700] = new Operation { Instruction = OpCode.Label, StringArgument = "CheckIf" };
                        memory[701] = new Operation { Instruction = OpCode.Ldc, IntArgument = 4 };
                        memory[702] = new Operation { Instruction = OpCode.Ldc, IntArgument = 2 };
                        memory[703] = new Operation { Instruction = OpCode.Add};
                        memory[704] = new Operation { Instruction = OpCode.Ldc, IntArgument = 6 };
                        memory[705] = new Operation { Instruction = OpCode.Eq };
                        memory[706] = new Operation { Instruction = OpCode.GoFalse, StringArgument = "If1_False"};
                        memory[707] = new Operation { Instruction = OpCode.Ldc, IntArgument = 100 };
                        memory[708] = new Operation { Instruction = OpCode.Label, StringArgument = "After_If1" };
                        memory[709] = new Operation { Instruction = OpCode.Ret };

                        memory[710] = new Operation { Instruction = OpCode.Label, StringArgument = "If1_False" };
                        memory[711] = new Operation { Instruction = OpCode.Ldc, IntArgument = 0 }; // "empty" expressions are not allowed, return 0 instead
                        memory[712] = new Operation { Instruction = OpCode.Goto, StringArgument = "After_If1" };


                        /*
                         * Check If with Else.
                         *
                         * FUNC CheckIfElse()
                         *    IF 4 + 2 = 7 THEN 100 ELSE 200 END
                         * END
                         */
                        memory[700] = new Operation { Instruction = OpCode.Label, StringArgument = "CheckIfElse" };
                        memory[701] = new Operation { Instruction = OpCode.Ldc, IntArgument = 4 };
                        memory[702] = new Operation { Instruction = OpCode.Ldc, IntArgument = 2 };
                        memory[703] = new Operation { Instruction = OpCode.Add };
                        memory[704] = new Operation { Instruction = OpCode.Ldc, IntArgument = 7 };
                        memory[705] = new Operation { Instruction = OpCode.Eq };
                        memory[706] = new Operation { Instruction = OpCode.GoFalse, StringArgument = "If1_False" };
                        memory[707] = new Operation { Instruction = OpCode.Ldc, IntArgument = 100 };
                        memory[708] = new Operation { Instruction = OpCode.Label, StringArgument = "After_If1" };
                        memory[709] = new Operation { Instruction = OpCode.Ret };

                        memory[710] = new Operation { Instruction = OpCode.Label, StringArgument = "If1_False" };
                        memory[711] = new Operation { Instruction = OpCode.Ldc, IntArgument = 200 };
                        memory[712] = new Operation { Instruction = OpCode.Goto, StringArgument = "After_If1" };


                        /*
                         * Test parameters.
                         *
                         * FUNC Add(x y)
                         *    x + y
                         * END
                         */
                        memory[800] = new Operation { Instruction = OpCode.Label, StringArgument = "Add" };
                        memory[801] = new Operation { Instruction = OpCode.BindArg, IntArgument = 0 }; // bind argument x to memory location 0
                        memory[802] = new Operation { Instruction = OpCode.BindArg, IntArgument = 1 }; // store argument y in memory location 1
                        memory[803] = new Operation { Instruction = OpCode.GetArg, IntArgument = 0 };
                        memory[804] = new Operation { Instruction = OpCode.GetArg, IntArgument = 1 };
                        memory[805] = new Operation { Instruction = OpCode.Add };
                        memory[806] = new Operation { Instruction = OpCode.Ret };


                        /*
                         * Nested function call.
                         *
             * FUNC Triple(x)
             *    x + Add(x x)
             * END
             */
                        memory[850] = new Operation { Instruction = OpCode.Label, StringArgument = "Triple" };
                        memory[851] = new Operation { Instruction = OpCode.BindArg, IntArgument = 0 }; // bind argument x to memory location 0
                        memory[852] = new Operation { Instruction = OpCode.GetArg, IntArgument = 0 };
                        memory[853] = new Operation { Instruction = OpCode.Mark };
                        memory[854] = new Operation { Instruction = OpCode.GetArg, IntArgument = 0 };
                        memory[855] = new Operation { Instruction = OpCode.GetArg, IntArgument = 0 };
                        memory[856] = new Operation { Instruction = OpCode.Call, StringArgument = "Add"};
                        memory[857] = new Operation { Instruction = OpCode.Add };
                        memory[858] = new Operation { Instruction = OpCode.Ret };


                        /*
                         * Finally add some recursion ;)
                         * Only call with powers of 2!
                         *
                         * FUNC DoubleTo65536(x)
                         *    IF x = 65536 THEN x ELSE DoubleTo65536(Add(x x) END
                         * END
                         */
                        memory[900] = new Operation { Instruction = OpCode.Label, StringArgument = "DoubleTo65536" };
                        memory[901] = new Operation { Instruction = OpCode.BindArg, IntArgument = 0 }; // bind argument x to memory location 0

                        // compare
                        memory[902] = new Operation { Instruction = OpCode.GetArg, IntArgument = 0 };
                        memory[903] = new Operation { Instruction = OpCode.Ldc, IntArgument = 65536 };
                        memory[904] = new Operation { Instruction = OpCode.Eq };

                        // "True" branch
                        memory[905] = new Operation { Instruction = OpCode.GoFalse, StringArgument = "If2_False" };
                        memory[906] = new Operation { Instruction = OpCode.GetArg, IntArgument = 0 };
                        memory[907] = new Operation { Instruction = OpCode.Label, StringArgument = "After_If2" };
                        memory[908] = new Operation { Instruction = OpCode.Ret };

                        // "False" branch
                        memory[909] = new Operation { Instruction = OpCode.Label, StringArgument = "If2_False" };
                        memory[910] = new Operation { Instruction = OpCode.Mark };
                        memory[911] = new Operation { Instruction = OpCode.Mark };
                        memory[912] = new Operation { Instruction = OpCode.GetArg, IntArgument = 0 };
                        memory[913] = new Operation { Instruction = OpCode.GetArg, IntArgument = 0 };
                        memory[914] = new Operation { Instruction = OpCode.Call, StringArgument = "Add"};
                        memory[915] = new Operation { Instruction = OpCode.Call, StringArgument = "DoubleTo65536" };
                        memory[916] = new Operation { Instruction = OpCode.Goto, StringArgument = "After_If2" };


                        /*
                         * Wrong calculation because local variables are not saved on the stack.
                         * Storing of locals is currently NOT implemented!
                         *
                         * FUNC SaveLocals(x y)
                         *    x + Add(y y) + x
                         * END
                         */
                        memory[960] = new Operation { Instruction = OpCode.Label, StringArgument = "SaveLocals" };
                        memory[961] = new Operation { Instruction = OpCode.BindArg, IntArgument = 0 }; // bind argument x to memory location 0
                        memory[962] = new Operation { Instruction = OpCode.BindArg, IntArgument = 1 }; // bind argument y to memory location 1
                        memory[963] = new Operation { Instruction = OpCode.GetArg, IntArgument = 0 };
                        memory[964] = new Operation { Instruction = OpCode.Mark };
                        memory[965] = new Operation { Instruction = OpCode.GetArg, IntArgument = 1 };
                        memory[966] = new Operation { Instruction = OpCode.GetArg, IntArgument = 1 };
                        memory[967] = new Operation { Instruction = OpCode.Call, StringArgument = "Add" };
                        memory[968] = new Operation { Instruction = OpCode.Add };
                        memory[969] = new Operation { Instruction = OpCode.GetArg, IntArgument = 0 }; // x was overridden with y in Call of Add!
                        memory[970] = new Operation { Instruction = OpCode.Add };
                        memory[971] = new Operation { Instruction = OpCode.Ret };
                }
        }
}