# Map Syntax Using the Intermediate Language

This page assumes that you have followed the setup for the syntax extension guide already, so that you have somewhere to work. This page describes how to re-implement the map syntax using the Intermediate Language. Since the grammar is identical, we will not modify it here. So if you have not already implemented the `map` grammar, copy it from the end of the previous part. Also make sure you have added the example code to the `test.bs` file as well, as we will use it for testing purposes throughout this page.

## Creating an AST Node

Similarly to the `repeat` syntax, we need to create a node that can be inserted into the Basic Storm AST in order to be able to generate intermediate code at the right location. Since the `map` syntax introduces additional variables, we need to inherit the `Block` class rather than from the `Expr` class. Since we will be generating code directly, there is no benefit from inheriting from the `ExprBlock` class as we did when we used the Basic Storm AST.

As such, to get started we can replace the old `MapExpr` class with a minimal definition that defines the operations that are used by the syntax:

    use lang:bs;
    use lang:bs:macro;
    use core:lang;
    use core:asm;

    class MapExpr extends Block {
        init(SrcPos pos, Block parent, Expr src, SStr varName) {
            init(pos, parent) {}
        }

        void setTransform(Expr expr) {}
    }

Since the map expression does not do anything at the moment, we get the following error if we try to run the example (using `storm .`):

    @/home/storm/expressions/test.bs(130-136): Syntax error:
    No appropriate constructor for core.Array(core.Int) found. Can not initialize 'result'.
    Expected signature: __init(core.Array(core.Int), void)

As we have seen previously, this message arises because our AST node currently reports that it evaluates to `void`. Since we use attempt to assign the result of our AST node to a variable, the system will report this error.

To fix this error, we need to tell the system that the `MapExpr` node evaluates to an expression of the type `Array<Int>` (or `Int[]`). Like before, we do this by overriding the `result` member like so:

    ExprResult result() : override {
        ExprResult(Value(named{Array<Int>}));
    }

If we run the program now, we will not get a type error. However, we will instead get the message that the abstract function `blockCode` was called. This function is similar to the `code` function in the `Expr` class in that it is called to generate code for the contents of the block. Actually, since the `Block` class inherits directly from the `Expr` class, the `Block` class overrides the `code` function in `Expr` and generates code that initializes the block and then calls `blockCode`. There is, however, no default implementation of the `blockCode` function, which is why we see the error now. This is also the reason why we used `ExprBlock` in the previous page. The `ExprBlock` does implement `blockCode` by simply generating code for all expressions that have been added to it. Since `Block` does only contains variables, it is not possible for the `Block` class to provide a default implementation.

Anyway, to fix the problem, we can simply add a definition of the `blockCode` function to our class:

    void blockCode(CodeGen gen, CodeResult res) : override {}

This time, the program will compile and start running. However, it will crash just after the `MapExpr` with a `Memory access error`. This is not surprising since the `MapExpr` node promised to produce a `Array<Int>`, but did not actually do so.

## Creating an Array

In order to fix the crash, we need to generate code that creates and returns an array in the `blockCode` function. It is a bit cumbersome to do this directly in the Intermediate Language, since we need to take care of allocating memory and executing the constructor. Luckily, the code generation library in Storm provides the function `allocObject` that helps us with this. As such, we can create a variable to store the result as follows:

    core:asm:Var resultVar = res.location(gen);
    allocObject(gen, named{Array<Int>:__init<Array<Int>>}, [], resultVar);
    res.created(gen);

The first line simply retrieves the variable where the result of the `MapExpr` expression should be stored. The next line calls `allocObject` to generate the code for creating the array. The call takes four parameters. The first one is the `CodeGen` object that should receive the generated code, and that contains metadata about the current code generation status. The second parameter is a `Function` that is expected to be the constructor to call. Here, we use the `named` syntax to find the default constructor for the `Array<Int>` class (remember: the `this` parameter is explicit). The next parameter is an array of parameters to the constructor. Since we call the default constructor, we do not need to supply any parameters. The final parameter is the variable where the created object should be stored.

Finally, the last row informs the `CodeResult` class that we have initialized the result, so that it can set up exception handling if required. In this particular case, however, `created` is a no-op since heap allocations are cleaned up anyway. It is, however, still good practice to call `created` to future-proof the code.

If we run the program now, we see that it no longer crashes and prints an empty array. A good first step!

As before, it is possible to view the generated code by printing the `gen` object at the end of the `blockCode` function. By doing this we can see that the `allocObject` function generated the following code in this case:

    fnParam p@core.Array(core.Int) - pointer:04(04)/08(08)@+0x00
    fnCall p[Var0], p@C++:allocType - pointer:04(04)/08(08)@+0x00
    fnParam p[Var0] - pointer:04(04)/08(08)@+0x00
    fnCall p@core.Array(core.Int).__init(core.Array(core.Int)) - none:00(01)@+0x00[member]

That is, it first calls the built-in function `allocType` to allocate memory for the object. It then calls the constructor to initialize the memory.

## Storing the Captured AST Nodes

In order to generate the correct code for the `map` expression, we must first make sure to actually store the expressions we captured from the grammar. Otherwise, it will be hard to do something useful in the `blockCode` function.

We need three things in order to generate relevant code: the expression that evaluates to the source array (`src`), the name of the variable used in the expression `varName`, and the expression that should be evaluated to transform individual elements (received in `setTransform`). The expression `src` is easy, we can simply store it in the class and use it later. We also wish to store the transform expression in a similar way. However, since we do not receive it in the constructor we create a `Maybe<Expr>` (i.e. `Expr?`) variable so that we can leave it uninitialized in the constructor and set it later:

    use lang:bs;
    use lang:bs:macro;
    use core:lang;
    use core:asm;

    class MapExpr extends Block {
        private Expr src;
        private Expr? transform;

        init(SrcPos pos, Block parent, Expr src, SStr varName) {
            init(pos, parent) {
                src = expectCastTo(src, named{Array<Int>}, parent.scope);
            }
        }

        void setTransform(Expr expr) {
            transform = expectCastTo(expr, named{Int}, scope);
        }

        // ...
    }

As before, we use the function `expectCastTo` to help us type-check the source expression, and to perform any implicit conversions if necessary.

The variable `varName` needs a bit more thought. We need to actually create the variable in the constructor. Otherwise the transform expression will not be able to find it, which will eventually result in a name error (as we saw in the previous page). We also save the created variable in a member of the `MapExpr` class so that we can easily find the variable in the `blockCode` function later. This way we do not have to look up the variable by name again.

We can achieve this by defining a member variable `boundVar` that we initialize in the constructor and then add to the block:

    use lang:bs;
    use lang:bs:macro;
    use core:lang;
    use core:asm;

    class MapExpr extends Block {
        private Expr src;
        private Expr? transform;
        private LocalVar boundVar;

        init(SrcPos pos, Block parent, Expr src, SStr varName) {
            init(pos, parent) {
                src = expectCastTo(src, named{Array<Int>}, parent.scope);
                boundVar = LocalVar(varName.v, named{Int}, varName.pos, false);
            }

            add(boundVar);
        }

        // ...
    }

The constructor to `LocalVar` takes four parameters as follows: the first is the name of the variable as a string. Since we have a `SStr`, we extract the string by reading the member `v`. The second parameter is the type of the variable. We wish to store integers, so we simply give the type `Int`. The third parameter is the location of the variable definition, which we retrieve from the `varName` variable through the member `pos`. The final parameter indicates if the variable is a parameter or not. Since this is not a function parameter, we simply pass `false`. After creating the variable, we add it to the `MapExpr`, so that the transform expression can find it.

## Generating Code

Now that we have all information that we need, we can finally start generating code for the `map` construct. As before, we start by sketching the code we wish to generate with placeholders for the different expressions. In this case, we wish to generate the following code:

        # ...

        # create an array, <resultVar>, that will be our result
        # evaluate <src>, store it in <originalArray>
        # evaluate <originalArray>.count(), store it in <originalCount>

        mov <loopCounter>, 0
    loopStart:
        cmp <loopCounter>, <originalCount>
        jmp loopEnd, ifAboveEqual

        # extract element <loopCounter> from <originalArray>, store in <boundVar>
        # evaluate <transform>, store result in <transformed>
        # call <resultVar>.push(<transformed>)

        add <loopCounter>, 1
        jmp loopStart

    loopEnd:
        # ...

The general structure is similar to that of the `repeat` statement. The contents of the loop is, however, a bit more involved since we need to interact with more parts of the system.

Based on the outline above, we can now start generating code, one step at a time. Note that we have already implemented the first step (create an array and store it in `<resultVar>`) to avoid the previous crash.

The next step is therefore to evaluate `src` and store it in a temporary variable. We can actually do this quite simply by utilizing the fact that the `CodeResult` can create the variable for us:

    CodeResult originalArrayRes(named{Array<Int>}, gen.block);
    src.code(gen, originalArrayRes);
    core:asm:Var originalArray = originalArrayRes.location(gen);

The first line creates a `CodeResult`. We instruct it that we wish to receive the result in a variable that is visible inside the currently active block, and that we expect to receive the type `Array<Int>`. This means that we will either reuse a variable that already exists elsewhere in the system, or that the `CodeResult` will create a suitable variable for us. Potentially reusing a variable is perfectly fine, since we will only ever read from the variable, and never modify it.

The second line then asks the `src` expression to generate code, and to place its results in the location we described using the `CodeResult` object. Finally, we extract the variable from the `originalArrayRes` so that it is more convenient to use later on.

The next step is to call `<originalArray>.count` to find the length of the array. We can call functions conveniently by using the member `autoCall` in the `Function` class to generate the code for us. The `autoCall` uses the `CodeResult` class just like the `code` function for expressions, so the code looks very similar to what we have written so far:

    Function countFn = named{Array<Int>:count<Array<Int>>};
    CodeResult originalCountRes(named{Nat}, gen.block);
    countFn.autoCall(gen, [originalArray], originalCountRes);
    core:asm:Var originalCount = originalCountRes.location(gen);

The first line simply stores the function we wish to call in a variable to make the code more readable. The second line creates another `CodeResult` instance. Again, we instruct it that we wish to have the result stored inside a variable that is visible in the active block. This time the type should be `Nat` to match the return type of the `count` function.

In the third line, we call `autoCall` to generate the code necessary for actually calling the function. The first parameter is the `CodeGen` instance where the generated code should be placed, the second parameter is an array of parameters to the function. Here, we pass a single parameter that is used as the `this` parameter. The third and final parameter is our `CodeResult` that indicates where we want the result to be located.

The fourth and last line simply extracts the created variable and stores it in a variable for easy access later.

After extracting the count, we are almost ready to start the loop. First, we need the loop counter. Since we initialize the loop counter ourselves, rather than evaluating an expression to get it, we need to create the variable manually. We can do this using the `createVar` function inside `CodeGen`. We then initialize the variable to zero by moving the value zero into it. Note that the last step is not strictly necessary since the Intermediate Language guarantees that variables are initialized to zero by default. The `mov` instruction is shown here to illustrate the syntax.

    core:asm:Var loopCounter = gen.createVar(named{Nat}).v;
    gen.l << mov(loopCounter, natConst(0));

After creating the variable, we can emit the header of the loop. We start by creating a label that we call `loopStart` and output it, so that we can jump back to the header of the loop later:

    Label loopStart = gen.l.label();
    gen.l << loopStart;

After emitting the label, we emit code for checking if the loop should be terminated. In our case, we should compare the variable `loopCounter` to the variable `originalCount`. We can do this with a `cmp` instruction:

    gen.l << cmp(loopCounter, originalCount);

This sets an internal register in the machine that we can use for conditional jumps. We wish to exit the loop if `loopCounter` is greater than or equal to `originalCount`. Since both values are unsigned integers (`Nat`s), we use the condition `ifAboveEqual` for this (`ifGreaterEqual` can be used for signed numbers). To tell the `jmp` instruction where it should jump to, we need to create the label `loopEnd` already here. We will then emit the label at the end of the loop.

    Label loopEnd = gen.l.label();
    gen.l << jmp(loopEnd, CondFlag:ifAboveEqual);

Next, we emit the body of the loop. The first thing we need to do is to get the current element from the array. We achieve this by calling the `[]` operator like before. One detail to note with the `[]` operator of the `Array` class is that it returns a reference to the element rather than the element itself. This is to allow modifying the element in the array by assigning to it. This does, however, mean that we need to take this into consideration when generating machine code, since we need to dereference the returned value to retrieve the actual value. Basic Storm handles this transparently for us. We can check for this in the code by examining the member `result.ref` inside the function. If it is true, the function returns a reference (i.e. a pointer) to the value rather than the value itself.

In spite of this the different return type, the call looks similar to the ones we have written previously:

    Function accessFunction = named{Array<Int>:"[]"<Array<Int>, Nat>};
    CodeResult elemPtr(accessFunction.result, gen.block);
    accessFunction.autoCall(gen, [originalArray, loopCounter], elemPtr);

There are two differences that might be interesting to observe. First, since the function `[]` is not an identifier according to Basic Storm, we need to enclose it in quotes to be able to write it in the `named` syntax. This is a special case in the `named` syntax to make it possible to retrieve special members like the `[]` function. It is not possible to enclose parts in a name in quotes anywhere else in Basic Storm.

The second difference is that we pass `accessFunction.result` to the constructor for `CodeResult`, rather than simply specifying `named{Int}`. This is to instruct the `CodeResult` that we want a reference to an integer rather than an integer. The constructor accepts a `Value` instance as its first parameter, but since the default constructor of `Value` creates a non-reference by default, simply calling `CodeResult(named{Int}, ...)` would not have the desired effect. We could, however, write `CodeResult(Value(named{Int}, true), ...)` or `CodeResult(Value(named{Int}).asRef(), ...)` instead. However, just passing the result type of the function makes the intent clearer in this case.

After we have acquired a pointer to the current element, we can read the actual value and copy it to the `boundVar` variable. The Intermediate Language allows us to follow pointers by using the `intRel` operand. However, this operand requires that the pointer is in a register beforehand. Since we do not care about the values in any of the three general purpose registers (`a`, `b`, and `c`) at the moment, we can simply use any one of them. As such, we simply pick register `a` for the task. Since we are goint to store a pointer in the register, we use the name `ptrA` to indicate that we are using the pointer-sized version of the register `a`:

    gen.l << mov(ptrA, elemPtr.location(gen));
    gen.l << mov(boundVar.var.v, intRel(ptrA));

In the first line, we load the value returned from the function (stored in `elemPtr`) into the register `ptrA`. We then load an integer from the address that `ptrA` contains by using the operand `intRel` (there are versions for different sizes as well), and store it in the variable we created in the constructor. The member `var` contains a `VarInfo` type, which in turn stores the actual variable inside its `v` member.

Note that the code above utilizes the fact that we are only working with integer types in this implementation. If the array could contain other types, we would have to replace the second `mov` with a copy operation that is appropriate for the contained type. For numeric and pointer types, it is enough to replace `intRel` with `xRel` and specify the size. For value types, however, we need to call the copy constructor, and ensure that any destructors are called at the end of the loop (or in case of an exception). Another option would be to make `boundVar` into a reference rather than a copy of the value. This means that it is possible to assign to the variable in the `map` syntax, but it would avoid copies of value types.

After setting `boundVar` to the current element, we can simply evaluate the `transform` expression. Since the `transform` variable might contain `null`, we must explicitly ensure that it does not contain `null` before using it. Perhaps the cleanest way to do this is to add an `unless` block at the start of the function:

    unless (transform)
        throw InternalError("No transform set for this MapBlock!");

After that, at the end of the function, we can evaluate the expression since Basic Storm now knows that `transform` does not contain `null` in the remainder of the function:

    CodeResult transformed(named{Int}, gen.block);
    transform.code(gen, transformed);

Now that we have computed the new value, we can insert it into the new array by calling the `push` member of the array. Similarly to the `[]` operator, the `push` member expects a reference to the element to be inserted rather than a value. As such, we need to get the address of the variable by using the `lea` (Load Effective Address) instruction in the Intermediate Language before passing it to the `autoCall` function. We could create a separate variable to store the address, but since we only have one temporary value like this, we can simply use the register `a` (using the name `ptrA` to indicate that it is a pointer):

    gen.l << lea(ptrA, transformed.location(gen));
    Function pushFn = named{Array<Int>:push<Array<Int>, Int>};
    pushFn.autoCall(gen, [resultVar, ptrA], CodeResult());

Note that since we are not interested in the result from the `push` function, we can simply pass a default-constructed `CodeResult` to `autoCall` to let it know that we do not need the result. This is a useful thing to do in most situations, as different parts of the system can utilize the knowledge that the result will be discarded to avoid performing some computations. For example, passing a default-constructed `CodeResult` to the AST node for an integer literal generates no code at all, since the node knows that the result will not be used.

Now that we are done with the loop body, we can generate the end of the loop. We need to increment the loop counter to advance to the next element, and then we can jump back to the top of the loop:

    gen.l << add(loopCounter, natConst(1));
    gen.l << jmp(loopStart);

Finally, we need to define the location of the end of the loop by appending the `loopEnd` label to the listing. Otherwise, the `jmp` instruction at the start of the loop will not know where to jump:

    gen.l << loopEnd;

And with this, we have implemented our plan, and we are ready to test our implementation. If you have done everything correctly, the code should now work as expected.

For reference, the final implementation of the semantics are provided below:

    use lang:bs;
    use lang:bs:macro;
    use core:lang;
    use core:asm;

    class MapExpr extends Block {
        private Expr src;
        private Expr? transform;
        private LocalVar boundVar;

        init(SrcPos pos, Block parent, Expr src, SStr varName) {
            init(pos, parent) {
                src = expectCastTo(src, named{Array<Int>}, parent.scope);
                boundVar = LocalVar(varName.v, named{Int}, varName.pos, false);
            }

            add(boundVar);
        }

        void setTransform(Expr expr) {
            transform = expr;
        }

        ExprResult result() : override {
            ExprResult(Value(named{Array<Int>}));
        }

        void blockCode(CodeGen gen, CodeResult res) : override {
            unless (transform)
                throw InternalError("No transform set for a MapBlock!");

            core:asm:Var resultVar = res.location(gen);
            allocObject(gen, named{Array<Int>:__init<Array<Int>>}, [], resultVar);
            res.created(gen);

            CodeResult originalArrayRes(named{Array<Int>}, gen.block);
            src.code(gen, originalArrayRes);
            core:asm:Var originalArray = originalArrayRes.location(gen);

            Function countFn = named{Array<Int>:count<Array<Int>>};
            CodeResult originalCountRes(named{Nat}, gen.block);
            countFn.autoCall(gen, [originalArray], originalCountRes);
            core:asm:Var originalCount = originalCountRes.location(gen);

            core:asm:Var loopCounter = gen.createVar(named{Nat}).v;
            gen.l << mov(loopCounter, natConst(0));

            Label loopStart = gen.l.label();
            gen.l << loopStart;

            Label loopEnd = gen.l.label();
            gen.l << cmp(loopCounter, originalCount);
            gen.l << jmp(loopEnd, CondFlag:ifAboveEqual);

            Function accessFunction = named{Array<Int>:"[]"<Array<Int>, Nat>};
            CodeResult elemPtr(accessFunction.result, gen.block);
            accessFunction.autoCall(gen, [originalArray, loopCounter], elemPtr);

            gen.l << mov(ptrA, elemPtr.location(gen));
            gen.l << mov(boundVar.var.v, intRel(ptrA));

            CodeResult transformed(named{Int}, gen.block);
            transform.code(gen, transformed);

            gen.l << lea(ptrA, transformed.location(gen));
            Function pushFn = named{Array<Int>:push<Array<Int>, Int>};
            pushFn.autoCall(gen, [resultVar, ptrA], CodeResult());

            gen.l << add(loopCounter, natConst(1));
            gen.l << jmp(loopStart);

            gen.l << loopEnd;
        }
    }