** Brainfuck Interpreter Contest ** [abgeschlossen]
-
Generierst Du IL-Code?
Her mit dem Code.
-
BTW: ich hatte zwar erst vorgeschlagen IL Code zu generieren, das ist aber eigentlich doof.
Erstmal hat der C# Compiler vermutlich selbst nen ganz netten Optimizer, den man nicht verschwenden sollte, und zweitens ist die Fehlersuche sicher einfacher, wenn man C# Code generiert statt IL Code.
Bzw. auch die Suche nach neuen Patterns die man dem eigenen Optimizer anlernen könnte wird dadurch vermutlich viel einfacher.
-
OK, hier der erste lauffähige Versuch.
CompilingEvaluatornimmt die Rolle des Interpreters ein, d.h. starten mitnew TestSession<Brainfuck.CompilingEvaluator>().Run();. Das InterfaceSmusste ich public machen. Ob es auch ohne geht, weiß ich nicht, dazu müsste man den Code ja in dasselbe Assembly generieren.using System; using System.Reflection; using System.Reflection.Emit; using System.Collections.Generic; namespace Brainfuck { class SimpleCompiler { private static void GenerateCode(string program, MethodBuilder mBuilder) { ILGenerator ilgen = mBuilder.GetILGenerator(); // Note: the types can't be changed arbitrarily. The Load and Store instructions have to be adjusted as well. Type pointerType = typeof(uint); Type dataType = typeof(short), dataArrayType = typeof(short[]); int dataSize = 32768; // Declare and initialize data pointer LocalBuilder pointer = ilgen.DeclareLocal(pointerType, false); ilgen.Emit(OpCodes.Ldc_I4_0); ilgen.Emit(OpCodes.Stloc, pointer); // Declare and initialize data array LocalBuilder dataArray = ilgen.DeclareLocal(dataArrayType, false); ilgen.Emit(OpCodes.Ldc_I4, dataSize); ilgen.Emit(OpCodes.Newarr, dataType); ilgen.Emit(OpCodes.Stloc, dataArray); // Declare parameter ParameterBuilder systemParam = mBuilder.DefineParameter(1, ParameterAttributes.In, "s"); // Manage labels: // [ creates two labels: one for the current instruction and one for the instruction after the loop // ] jumps to the corresponding top of stack and marks the other one Stack<Label> labelStack = new Stack<Label>(); for (int i = 0; i < program.Length; ++i) { switch (program[i]) { case '<': // Decrease data pointer ilgen.Emit(OpCodes.Ldloc, pointer); ilgen.Emit(OpCodes.Ldc_I4_1); ilgen.Emit(OpCodes.Sub); ilgen.Emit(OpCodes.Stloc, pointer); break; case '>': // Increase data pointer ilgen.Emit(OpCodes.Ldloc, pointer); ilgen.Emit(OpCodes.Ldc_I4_1); ilgen.Emit(OpCodes.Add); ilgen.Emit(OpCodes.Stloc, pointer); break; case '+': // Increase current data // Prepare Store ilgen.Emit(OpCodes.Ldloc, dataArray); ilgen.Emit(OpCodes.Ldloc, pointer); // Load current data ilgen.Emit(OpCodes.Ldloc, dataArray); ilgen.Emit(OpCodes.Ldloc, pointer); ilgen.Emit(OpCodes.Ldelem_I2); // Increase ilgen.Emit(OpCodes.Ldc_I4_1); ilgen.Emit(OpCodes.Add); // Now the result is on top of the stack, store it ilgen.Emit(OpCodes.Stelem_I2); break; case '-': // Decrease current data // Prepare Store ilgen.Emit(OpCodes.Ldloc, dataArray); ilgen.Emit(OpCodes.Ldloc, pointer); // Load current data ilgen.Emit(OpCodes.Ldloc, dataArray); ilgen.Emit(OpCodes.Ldloc, pointer); ilgen.Emit(OpCodes.Ldelem_I2); // Increase ilgen.Emit(OpCodes.Ldc_I4_1); ilgen.Emit(OpCodes.Sub); // Now the result is on top of the stack, store it ilgen.Emit(OpCodes.Stelem_I2); break; case '[': { // Enter loop if current data != 0, skip loop otherwise Label thisInstruction = ilgen.DefineLabel(); Label followingInstruction = ilgen.DefineLabel(); // Push two labels: // thisInstruction: label to which the corresponding ] has to jump // followingInstruction: label of the instruction after the corresponding ] // only thisInstruction will be marked here labelStack.Push(thisInstruction); labelStack.Push(followingInstruction); ilgen.MarkLabel(thisInstruction); // Load current data ilgen.Emit(OpCodes.Ldloc, dataArray); ilgen.Emit(OpCodes.Ldloc, pointer); ilgen.Emit(OpCodes.Ldelem_I2); // Compare with 0 and branch ilgen.Emit(OpCodes.Ldc_I4_0); ilgen.Emit(OpCodes.Beq, followingInstruction); } break; case ']': { // Jump to the beginning of the loop // (Alternative implementation: Exit loop if current data == 0, jump to the beginning otherwise) // Pop two labels: // nextInstruction is the instruction after the loop, marked here // loopBegin is the label that was marked when translating the corresponding [ Label nextInstruction = labelStack.Pop(); Label loopBegin = labelStack.Pop(); ilgen.Emit(OpCodes.Br, loopBegin); ilgen.MarkLabel(nextInstruction); } break; case '.': { // Write current data: // Call s.W(dataArray[pointer]) MethodInfo writeMethod = typeof(S).GetMethod("W"); ilgen.Emit(OpCodes.Ldarg, 1); // Load current data ilgen.Emit(OpCodes.Ldloc, dataArray); ilgen.Emit(OpCodes.Ldloc, pointer); ilgen.Emit(OpCodes.Ldelem_I2); // Call shell.W ilgen.Emit(OpCodes.Call, writeMethod); } break; case ',': { // Read into current data: // Call s.R() and assign the result to dataArray[pointer] MethodInfo readMethod = typeof(S).GetMethod("R"); // Prepare Store ilgen.Emit(OpCodes.Ldloc, dataArray); ilgen.Emit(OpCodes.Ldloc, pointer); // Call shell.R() ilgen.Emit(OpCodes.Ldarg, 1); ilgen.Emit(OpCodes.Call, readMethod); // Assign result ilgen.Emit(OpCodes.Stelem_I2); } break; } } ilgen.Emit(OpCodes.Ret); } public static void CompileAndRun(S system) { AssemblyName asmName = new AssemblyName("Brainfuck"); AssemblyBuilder asmBuilder = System.Threading.Thread.GetDomain().DefineDynamicAssembly(asmName, AssemblyBuilderAccess.Run); ModuleBuilder modBuilder = asmBuilder.DefineDynamicModule("Brainfuck.exe"); TypeBuilder typeBuilder = modBuilder.DefineType( "Brainfuck", TypeAttributes.Public | TypeAttributes.Class); MethodBuilder runMethodBuilder = typeBuilder.DefineMethod( "Run", MethodAttributes.HideBySig | MethodAttributes.Public, typeof(void), new Type[] { typeof(S) }); GenerateCode(system.P, runMethodBuilder); Type brainfuckTempType = typeBuilder.CreateType(); MethodInfo runMethod = brainfuckTempType.GetMethod("Run"); ConstructorInfo ctor = brainfuckTempType.GetConstructor(Type.EmptyTypes); Object compiledProgram = ctor.Invoke(new object[] {}); runMethod.Invoke(compiledProgram, new object[] { system }); } } class CompilingEvaluator { public void R(S s) { SimpleCompiler.CompileAndRun(s); } } }hustbaer: Das sagst du jetzt!
Ich hatte mir das erst auch ein bisschen anders vorgestellt, nicht daran gedacht, dass das ja eine Stackmaschine ist.
