Thursday, January 5, 2017

Tutorial : dynamic code generation in ELENA, part 2

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:

{ eval : a : b = a * a + b. }

The equivalent Tape will look like this:

Tape ( 
   3, %"tapeOp.var[]", 2, %"tapeOp.var[]", 
   2, %"tapeOp.var[]", %"multiply[1]", %"add[1]" 
)

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:

   #define start      ::= statement;
   #define start      ::= $eof;
   #define statement  ::= expression next_expr;
   #define expression ::= <= ( => object operations <= ) =>;   
   #define object     ::= <= $reference =>;
   #define object     ::= <= $literal =>;
   #define object     ::= <= $numeric =>;
   #define object     ::= "(" expression ")" ;
   #define operations ::= operation operations;
   #define operations ::= $eps;
   #define operation  ::= message parameters <= ^ = =>;
   #define message    ::= <= + $identifier =>;                      
   #define parameters ::= parameter parameters;
   #define parameters ::= $eps; 
   #define parameter  ::= ":" object;
   #define next_expr  ::= $eof;

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:

#import system.

class calculator =
{
   eval : a : b
      = a * a + b.
}.

symbol program =
[   
].

After the project is compiled, we have to select - View - ELENA Interactive and in the console window we will type the following command:

> system'console writeLine:(mytest'calculator eval:2:3)

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 :

symbol program =
[   
    console writeLine:(
        extensions'scripting'scriptEngine
           load &path:"~\scripts\elena.es"
           eval:"mytest'calculator eval:2:3").
].

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: [,.]

#import system.
#import system'dynamic.
#import system'routines.
#import extensions.

symbol program =
[
    // [,.]
    
    var bfProgram := Tape(
        Integer new,
        console, %"readChar[0]", %"convertorOp.toInt[0]", 
        3, %"tapeOp.var[]", 2, %"tapeOp.var[]", %"setAt[2]",            
        3, %"tapeOp.var[]", 2, %"tapeOp.var[]", %"getAt[1]", 
        %"convertorOp.toChar[0]", console, %"write[1]",        
        3, %"tapeOp.var[]", 2, %"tapeOp.var[]", %"getAt[1]", 
        0, %"notequal[1]", 1, %"tapeOp.jumpif[1,]").
        
    var bfTape := Array new:1024 set &every:(&int:n) [ Integer new ].
    
    bfProgram eval:bfTape.
].

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.

class BFTape
{
    object theArray.
    object thePointer.
    object theBrackets.

    constructor new:aLength
    [
        theArray := Array new:aLength set &every: (&int:n) [ Integer new:0 ].
        
        thePointer := Integer new:0.
        
        theBrackets := system'collections'Stack new.
    ]

    append
    [
         (theArray@thePointer) += 1.
    ]
    
    reduce
    [
         (theArray@thePointer) -= 1.
    ]
    
    next
    [
        thePointer += 1.
    ]

    previous
    [
        thePointer -= 1.
    ]
    
    push : bookmark
    [
        theBrackets push:bookmark.
    ]
    
    pop
        => theBrackets.
    
    input
    [
        theArray@thePointer := console readChar toInt.
    ]
    
    output
    [
        console write:((theArray@thePointer) toChar).
    ]

    check = theArray@thePointer != 0.
}

The grammar will look like this:

   #grammar cf

   #define start      ::= <= [ 2 %"system'dynamic'tapeOp.var&args$[]" => commands <= * system'dynamic'Tape ] =>;

   #define commands   ::= command commands;
   #define commands   ::= comment commands;
   #define commands   ::= $eof;

   #define command    ::= <= %"output[0]" => ".";
   #define command    ::= <= %"input[0]" => ",";
   #define command    ::= <= %"previous[0]" => "<";
   #define command    ::= <= %"next[0]" => ">";
   #define command    ::= <= %"append[0]" => "+";
   #define command    ::= <= %"reduce[0]" => "-";
   #define command    ::= <= -2 %"system'dynamic'tapeOp.ptr&args$[]" 1 %"system'dynamic'tapeOp.stack&args$[]" %"push[1]" => "[";
   #define command    ::= <= 0 %"system'dynamic'tapeOp.stack&args$[]" %"check[0]" 1 %"system'dynamic'tapeOp.stack&args$[]" %"pop[0]" %"system'dynamic'tapeOp.jumpif&args$[13]" => "]";

   #define comment    ::= " " comments;
   #define comment    ::= "'" comments;
   #define comment    ::= "!" comments;
   #define comment    ::= $eol;

   #define comments   ::= $chr comments;
   #define comments   ::= $eps;

   #mode symbolic;

After executing the following code:

    #var bfProgram := scriptEngine 
        load &path:"rules.es"
        eval &path:"[,.]".

The following tape will be created:

   Tape (
      2, %"tapeOp.var[], -2, %"tapeOp.ptr[]", 
      1, %"tapeOp.stack[]", %"push[1]", %"input[0]", 
      %"output[0]", 0, 
      %"tapeOp.stack[]", %"check[0]", 1, %"tapeOp.stack[]", 
      %"pop[0]", %"tapeOp.jumpif[1,]"
   ).

which we could execute:

bfProgram eval:(BFTape new:1024).

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:

class TapeAssembler
{    
    object theBrackets.
    object theTape.
    
    constructor new
    [
        theBrackets := Stack new.
        theTape := ArrayList new.
        
        theTape append:(Integer new).
    ]
    
    open
    [
        theBrackets push:(theTape length).
    ]
    
    close
    [
        theTape
            append:3
            append:%"tapeOp.var[]"
            append:2
            append:%"tapeOp.var[]"
            append:%"getAt[1]"
            append:0
            append:%"notequal[1]"
            append:(theBrackets pop)
            append:%"tapeOp.jumpif[1,]".
    ]
    
    input
    [
        theTape
            append:console
            append:%"readChar[0]"
            append:%"convertorOp.toInt[0]"
            append:3
            append:%"tapeOp.var[]"
            append:2
            append:%"tapeOp.var[]"
            append:%"setAt[2]".
    ]
    
    output
    [
        theTape
            append:3
            append:%"tapeOp.var[]"
            append:2
            append:%"tapeOp.var[]"
            append:%"getAt[1]"
            append:%"convertorOp.toChar[0]"
            append:console
            append:%"write[1]".
    ]
    
    next
    [
        theTape
            append:1
            append:3
            append:%"tapeOp.var[]"
            append:%"append[1]".
    ]
    
    previous
    [
        theTape
            append:1
            append:3
            append:%"tapeOp.var[]"
            append:%"reduce[1]".
    ]
    
    increase
    [
        theTape
            append:1
            append:3
            append:%"tapeOp.var[]"
            append:2
            append:%"tapeOp.var[]"
            append:%"getAt[1]"
            append:%"add[1]"
            append:3
            append:%"tapeOp.var[]"
            append:2
            append:%"tapeOp.var[]"
            append:%"setAt[2]".
    ]
    
    decrease
    [
        theTape
            append:1
            append:3
            append:%"tapeOp.var[]"
            append:2
            append:%"tapeOp.var[]"
            append:%"getAt[1]"
            append:%"subtract[1]"
            append:3
            append:%"tapeOp.var[]"
            append:2
            append:%"tapeOp.var[]"
            append:%"setAt[2]".
    ]
    
    get
        = Tape new &array:theTape.
}

The new grammar will be much simpler:

   #grammar cf

   #define start      ::= <= [ 2 %"system'dynamic'tapeOp.var&args$[]" => commands <= %"get[0]" * system'dynamic'Tape ] =>;

   #define commands   ::= command commands;
   #define commands   ::= comment commands;
   #define commands   ::= $eof;

   #define command    ::= <= %"output[0]" => ".";
   #define command    ::= <= %"input[0]" => ",";
   #define command    ::= <= %"previous[0]" => "<";
   #define command    ::= <= %"next[0]" => ">";
   #define command    ::= <= %"increase[0]" => "+";
   #define command    ::= <= %"decrease[0]" => "-";
   #define command    ::= <= %"open[0]" => "[";
   #define command    ::= <= %"close[0]" => "]";

   #define comment    ::= " " comments;
   #define comment    ::= "'" comments;
   #define comment    ::= "!" comments;
   #define comment    ::= $eol;

   #define comments   ::= $chr comments;
   #define comments   ::= $eps;

   #mode symbolic;

After executing the similar code as above:

    #var bfAssemblyProgram := scriptEngine 
        load &path:"rules.es"
        eval &path:"[,.]".

we will receive the following tape:

   Tape (
     2, %"tapeOp.var[], %"open[0]", 
     %"input[0]", %"output[0]", %"close[0]", %"get[0]" 
   ).

which is much simpler.

The tape may be executed like this:

    var bfProgram := bfAssemblyProgram eval:(TapeAssembler new).

    var bfTape := Array new:1024 set &every:(&int:n) [ 0 ].

    bfProgram eval:bfTape.

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

class TapeCGenerator
{    
    object theOutput.
    
    constructor new
    [
        theOutput := system'text'TextBuilder new.
    ]
    
    open
    [
        theOutput writeLine:"while (*p) {".
    ]

    close
    [
        theOutput writeLine:"}".
    ]
    
    input
    [
        theOutput writeLine:"*p = getchar();".
    ]
    
    output
    [
        theOutput writeLine:"putchar(*p);".
    ]
    
    next
    [
        theOutput writeLine:"++p;".
    ]
    
    previous
    [
        theOutput writeLine:"--p;".
    ]

    increase
    [
        theOutput writeLine:"++*p;".
    ]
    
    decrease
    [
        theOutput writeLine:"--*p;".
    ]
    
    get
    [
        theOutput insert:"void execute(char* p) {" &at:0.
        theOutput writeLine:"}".
        
        ^ theOutput literal.
    ]
}

we may easily create the code generator, which will generate the following c function:

void execute(char* p) 
{
   while (*p) {
     *p = getchar();
     putchar(*p);
   }
}

That's it. In this tutorial we have demonstrated the way to generate dynamic code in ELENA using mix-in Tape

No comments:

Post a Comment