In this article we will see that system'dynamic'Tape mixin can be used to implement Turing machine. To demonstrate this Brainf**k interpreter will be created.
In the previous tutorial it was shown that system'dynamic'Tape and system'dynamic'Struct mix-in objects can be used to execute the dynamic code without reflection and run-time compilation. This approach allows us actually to build new code even in stand-alone application. But it is quite clear that it is not very practical. Let's implement the following code:
The equivalent Tape will look like this:
The more complex code the more bulky sequence should be created. Of course we should not write the whole code using Tape, still the task to write and debug it is quite challenging. But on the other hand, the computer may easily generate it using ELENA Script Engine.
ELENA Script Engine is a simple context-free parser. Basing on the user-defined grammar it will generate the output which could be interpreted by ELENA VM (stand-alone version will be implemented later). The commands are quite simple : load the symbol, create the array, send a message.
Our simple grammar may look like this:
Let's try to use it to communicate with our code. We will have to create a new console application (type : console, namespace - mytest) which contains the following code:
After the project is compiled, we have to select - View - ELENA Interactive and in the console window we will type the following command:
The result is 7
The script engine can be used from the application as well. But before we have to switch our project type to vmconsole (select Project - Options, in the Project dialog select vm_console in type combobox and press ok)
Now write the following code in program symbol :
The result is the same:7
Now we are ready to go to our main task : Brainf**k interpreter.
Let's create a new vm_console project. We will start with the simple loopback sample in BF: [,.]
Note %"tapeOp.jumpif[1,]" extension is used for jumping (i.e. changing the index of the next element to be loaded by Tape)
If we will try to implement the tape for more complicated sample (e.g. hello world) the array will be much bigger. So it is time to use the script engine.
Let's start with a simpler task : instead of generating the tape directly (like we did it in the previous example) we will generate the set of instruction for our help object : BFTape.
The grammar will look like this:
After executing the following code:
The following tape will be created:
which we could execute:
Note that even for our simple task the resulting tape is quite big. Secondly for context-free grammar it is not possible to generate the tape directly (because of the loop). So how can we overcome these drawbacks?
Let's try it once again. First we will need another helper:
The new grammar will be much simpler:
After executing the similar code as above:
we will receive the following tape:
which is much simpler.
The tape may be executed like this:
So instead of trying to construct the tape directly we use the script engine to generate a list of instruction how to create the required tape. The main advantages of this approach : the required grammar is context free and simple, the generated list of instruction may be used for another target. For example if we replace TapeAssembler with TapeCGenerator
we may easily create the code generator, which will generate the following c function:
That's it. In this tutorial we have demonstrated the way to generate dynamic code in ELENA using mix-in Tape