# Map Syntax Using the Basic Storm AST

This page assumes that you have followed the setup for the syntax extension guide already, so that you have somewhere to work. In this stage we will implement the `map` syntax in terms of Basic Storm. Compared to the `repeat` syntax, the `map` syntax has the added complexity that it introduces new variables that should only be visible inside the body of the construct. As such, we need to also consider the scoping of our new construct.

## Syntax

The first step is, as with the `repeat` statement, to create the grammar for the new syntax. We do this by creating a file `syntax.bnf` inside the `map` directory we created in the setup. As previously, we start by defining the the delimiters:

    use lang.bs;

    optional delimiter = SDelimiter;
    required delimiter = SRequiredDelimiter;

After this, we add a production that defines the grammar for our extension. Since the `map` syntax acts as an expression, we extend `SExpr` instead of `SStmt` this time. As previously, we start by adding the production itself and worry about the transforms later. We can write the map syntax as follows:

    SExpr : "map", "(", SExpr ~ "for" ~ SName ~ "in" ~ SExpr, ")";

Note that we use the `~` separator instead of `,` around the keywords `for` and `in`. Since `SExpr` and `SName` may be plain identifiers, it is useful to require a whitespace around them to avoid surprises. For example, if the `~` after `for` and `in` were replaced with a `,` it would be possible to write: `map(x forx inarray)`. This does not look sensible, and would likely surprise developers, so we disallow it.

As a sidenote: this ambiguity does not introduce problems in this particular case. It is, however, useful to be careful when working with grammars, as they may inadvertently interfere with other parts of the grammar. For example, if the `spawn` keyword in Basic Storm would not require a space after it, then the expression: `spawnThread()` would parse as `spawn Thread()`, which is most likely not wat the developer intended.

We also add annotations for syntax highlighting of the keywords:

    SExpr : "map" #keyword, "(", SExpr ~ "for" #keyword ~ SName #varName ~ "in" #keyword ~ SExpr, ")";

We are now ready to test that our grammar behaves as we expect. In the `test.bs` file we used before, add the following code to use our new syntax:

    Int[] values = [8, 10, 3];
    Int[] result = map(x + 2 for x in values);
    print(result.toS);

As in the previous example, we also need to include the package where the syntax is located. To do this, we need to add the line `use expressions:map` to the top of the file. After doing this, we can run the test program (by typing `storm .` in the terminal) to see if the grammar works as expected. Since we have not yet implemented the semantics, we expect to get some form of error at this point, as long as it is not a parse error. And indeed, running the example produces the following error message:

    @/home/storm/expressions/map/syntax.bnf(89-177): Syntax error:
    No return value specified for a production that does not return 'void'.

This makes sense since we have not specified a return value for our production yet.

## Semantics

Since the syntax seems to be working as expected, we can now start working on the semantics of the `map` expression. To simplify the implementation a bit, we assume that we are working with arrays of integers. It is of course possible to lift this limitation if we wished to, but it requires some care to get type inference right with regards to array literals. Working only with integers also simplifies the implementation of the IR version of the implementation.

Since the `for` syntax needs to provide a loop variable that is only visible to the expression "inside" the construct, we need to create a new scope for this expression. In Basic Storm, we do this by creating a `Block` instance. Each `Block` instance roughly corresponds to a pair of curly braces (`{}`) in that it introduces a new scope where we can store local variables.

The `Block` class actually corresponds to something that is slightly less than a pair of curly braces (`{}`). Namely, a `Block` only provides a place to store variables. It does not contain any expressions. Luckily, Basic Storm provides a subclass that both provides a new scope and is able to contain expressions. This class is called `ExprBlock` since it contains a list of expressions. As such, we will use the `ExprBlock` here to simplify our implementation. The IR implementation of the `map` construct will use a plain `Block` for this purpose since we do not need the ability to store expressions there.

As such, we can start our implementation by creating a new file called `semantics.bs` and adding the following code to it:

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

    class MapExpr extends ExprBlock {
        init(SrcPos pos, Block parent) {
            init(pos, parent) {}
        }
    }

Note that the constructor of `ExprBlock` (and also `Block`) requires two parameters: both a `SrcPos` (the same as `Expr`) and a `Block`. The `Block` parameter specifies the block inside which the new block is created. This makes the scope in Basic Storm hierarchichal, meaning that the system does not only look inside the currently active block for variables, but also in enclosing blocks. In the case of our `map` syntax, this makes it possible to use not only the loop variable in the expression, but also variables from outside the loop.

We can then start to add annotations to the grammar to create our new class. As a start, we just create the `MapBlock` as follows:

    SExpr => MapBlock(pos, block)
      : "map" #keyword, "(", SExpr ~ "for" #keyword ~ SName #varName
      ~ "in" #keyword ~ SExpr, ")";

If we run the program now, we get a different error. This time the error points to the code in our test program:

    @/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)

This error occurs because we have essentially transformed the `map` expression into an empty block. As such, our test code is now equivalent to:

    Int[] values = [8, 10, 3];
    Int[] result = {};
    print(result.toS);

Since an empty block evaluates to `void`, it is clear why the error arises when the compiler attempts to initialize `result`. This just means that we need to fill our block with some useful code!

As a starting point, we can create some simple code using the `pattern` macro again and add that to our block by calling the `add` function:

    init(SrcPos pos, Block parent) {
        init(pos, parent) {}

        add(pattern(this) {
                Array<Int> out;
                out << 9;
                out;
            });
    }

For now, we create a block that creates an array (`out`), adds a single number to the array, and then returns it back to the caller. We then add this block to our `MapExpr` by calling the `add` function. If we run the code at this point, it will produce an array that only contains the number 9 without any errors.

To inspect the generated AST, we can simply print the `MapExpr` block at the end of the constructor by adding a `print` statement: `print(this.toS)`. Currently, it produces the following output:

    {
        {
            core.Array(core.Int) out(core.Array(core.Int)());
            out << 9;
            out;
        };
    }

As we can see, we do indeed have two nested blocks. The outermost one is the `MapExpr` block, and the innermost one is the block inside the `pattern` that we added. We do not technically need two blocks like this, but it simplifies the implementation a bit and helps us hide internal variables.

## Using the Input

The next step is to actually read data from the input array. We can do this similarly to the `repeat` statement. The first step is to capture the expression in the grammar and pass it as a variable to the `MapExpr` class. In the grammar, we simply bind the expression that corresponds to the source array to the variable `src` and pass it to `MapExpr`:

    SExpr => MapExpr(pos, block, src)
      : "map" #keyword, "(", SExpr ~ "for" #keyword ~ SName #varName
      ~ "in" #keyword ~ SExpr(block) src, ")";

Then, we modify the `MapExpr` constructor to accept the new parameter and use it in our pattern:

    init(SrcPos pos, Block parent, Expr src) {
        init(pos, parent) {}

        add(pattern(this) {
                Array<Int> original = ${src};
                Array<Int> out;
                for (Nat i = 0; i < original.count(); i++) {
                    out << original[i];
                }
                out;
            });
    }

Note that we start by saving the value of the expression `${src}` in the variable `original` in the beginning of the pattern, rather than using `${src}` throughout. Since `${src}` inserts the expression `src` into all locations where it appear, using `${src}` more than once would cause the expression in `src` to be evaluated more than once. Since we simply supply a variable in our example, this would be fine. However, if `src` were a more complex expression that potentially had side-effects (like function calls), this would cause our `map` expression to not behave according to the programmer's expectations. Assigning `${src}` to a variable with the proper type has the additional benefit that Basic Storm will automatically perform any type conversions for us during the assignment, so we do not need the call to `expectCastTo` call that was required in the `repeat` syntax. We can still insert it if we wish to, as it does not do any damage.

The remainder of the pattern simply copies the contents of `original` to `out` using a loop. There are, of course, other ways to do this more concisely, but we will use this structure to actually perform transform each element later on.

If we run the program now, we will find that the program (unsurprisingly) produces a copy of our original array. Again, it is possible to print the `MapExpr` at the end of the constructor to see what the pattern actually expanded to:

    {
        {
            core.Array(core.Int) original = values;
            core.Array(core.Int) out(core.Array(core.Int)());
            {
                core.Nat i = 0;
                for (i < core.ArrayBase.count(original); core.Nat.*++(i)) {
                    out << core.Array(core.Int).[](original, i);
                };
            };
            out;
        };
    }

In particular, we can see that `${src}` was replaced by the variable `values`, since we used that variable in our test program. We can also see that the `for` loop actually expands to two blocks. One that declares the loop variable, and one that implements the remainder of the loop logic.

## Transforming Values

The final step of our implementation is to use the second expression to actually transform the values. To do this, we need to update the grammar to bind the relevant parts of the match to variables and pass them to our `MapExpr` class:

    SExpr => MapExpr(pos, block, src, var, tfm)
      : "map" #keyword, "(", SExpr(block) tfm ~ "for" #keyword ~ SName var #varName
      ~ "in" #keyword ~ SExpr(block) src, ")";

Then we modify the constructor of `MapExpr` so that it creates a variable with the specified name and adds it to itself:

    init(SrcPos pos, Block parent, Expr src, SStr varName, Expr tfm) {
        init(pos, parent) {}

        Var local(this, named{Int}, varName, Actuals());
        add(local);

        // The remainder of the constructor is as before.
    }

The class `Var` is a variable declaration statement. The constructor call corresponds to a declaration like `Int x();`. The first parameter is the block in which the variable shall be created, the second parameter is the type of the variable, the third is the name (and position, as a `SStr`), and the final parameter is the parameters to the constructor call. We wish to call the default constructor, so we pass a default-constructed `Actuals` object.

Creating the variable declaration in this manner will automatically create a `LocalVar` object that describes the actual variable and add it to the block passed as the first parameter. To properly initialize the variable we do, however, also need to add the variable declaration statement to the block. We do this using the `add` function as before. At this point, we can run our program and verify that it works as intended. If we print the `MapExpr` class, we can see that the implementation currently produces the following code:

    {
        core.Int x;
        {
            core.Array(core.Int) original = values;
            core.Array(core.Int) out(core.Array(core.Int)());
            {
                core.Nat i = 0;
                for (i < core.ArrayBase.count(original); core.Nat.*++(i)) {
                    out << core.Array(core.Int).[](original, i);
                };
            };
            out;
        };
    }

That is, we declare the variable `x` in the outermost scope, just as we hoped!

So far, all seems well. Let's proceed to actually use the variable with the expression. We wish to produce a loop that looks like this:

    for (Nat i = 0; i < original.count(); i++) {
        <varName> = original[i];
        out << <tfm>;
    }

That is, we first set the variable we created to the element that we found at the current index of the array. After that, we can evaluate the `tfm` expression (which might use the variable) to produce the transformed value for our array.

The first part, the assignment, requires us to be able to access the variable. Simply adding `${varName} = original[i]` will sadly not work, since the `${}` syntax expects the expression that appears inside of it to evaluate to an `Expr`. Luckily, Basic Storm provides an expression that lets us access a variable. It is called `LocalVarAccess`, and we can simply give it a position and the variable we wish to access. For the second part, we can simply insert `tfm` using `${tfm}` since `tfm` is already an `Expr`. This means that we change our `pattern` to the following:

    add(pattern(this) {
            Array<Int> original = ${src};
            Array<Int> out;
            for (Nat i = 0; i < original.count(); i++) {
                ${LocalVarAccess(pos, local.var)} = original[i];
                out << ${tfm};
            }
            out;
        });

If we run the program at this point, we will get a surprising error:

    @/home/storm/expressions/test.bs(143-144): Syntax error:
    Can not find "x" with parameters ().

In an attempt to debug the issue, we can try to print the `MapExpr` at the end of the constructor once more. If we do this, we get the following output:

    {
        core.Int x;
        {
            core.Array(core.Int) original = values;
            core.Array(core.Int) out(core.Array(core.Int)());
            {
                core.Nat i = 0;
                for (i < core.ArrayBase.count(original); core.Nat.*++(i)) {
                    x = core.Array(core.Int).[](original, i);
                    out << <x[invalid] + 2>;
                };
            };
            out;
        };
    }

The output looks as we would expect, except for the last line inside the loop (`out << <x[invalid] + 2>`). The angle brackets (`<>`) are normal, they are simply used to clarify the precedence of operators in the textual representation. However, we would expect it to read `out << <x + w>`, not `out << <x[invalid] + 2>`. Why is `x` invalid in this location, when we could assign to `x` on the line before?

## Fixing the Scope

To understand why the error occurs, we must understand how Basic Storm resolves names.

In general, name resolution in Basic Storm happens as soon as nodes in the AST are created. This is why it is necessary to pass a `Block` to the `SExpr` and `SStmt` rules in the Basic Storm syntax. Otherwise the system would not know how to resolve names!

As a sidenote, this might make you wonder why the error was not reported as soon as it was discovered. The reason for this is that some parts of Basic Storm need to be able to detect and re-try failed name lookups. One example of this is the `=` operator. For example, consider an assignment like `a.b = c`. However, `a.b` does not exist, so the `=` operator should attempt to lookup `a.b(c)` instead to see if `b` is an assignment function in this context. To achieve this, the `=` operator must be able to detect and recover from name resolution errors. With the current implementation, it can simply examine the AST node that corresponds to the left-hand side and see if it corresponds to an invalid name, and act accordingly. This would be more difficult if Basic Storm reported name resolution errors directly.

The upside of this behavior is that it makes it clear why the local variables we introduced inside the pattern are not visible to the `tfm` expression. Since we never use the block produced by the `pattern` as a parent block for anything, the variables in the `pattern` block will never be reachable by name lookups in the `tfm` expression, even after we make the variable in the `MapExpr` itself visible.

Regardless, we need to ensure that the names that appear inside the `tfm` expression are resolved in the proper scope. We can solve this in the grammar by passing the newly created `MapExpr` rather than the parent block to the `tfm` expression. Luckily, the `MapExpr` is bound to the `me` variable in the grammar, so we can just replace `block` with `me` as follows:

    SExpr => MapExpr(pos, block, src, var, tfm)
      : "map" #keyword, "(", SExpr(me) tfm ~ "for" #keyword ~ SName var #varName
      ~ "in" #keyword ~ SExpr(block) src, ")";

Nowever, this introduces another issue. If we try to run the program now, we get the following error:

    @/home/storm/expressions/map/syntax.bnf(89-247): Syntax error:
    Can not use 'me' this early!

If we examine the grammar a bit more closely, we can see the problem. We have specified that in order to create `tfm`, the Syntax Language needs to create the contents of the variable `me`. However, to create the variable `me` requires calling `MapExpr(pos, block, src, var, tfm)`, which involves having created `tfm`. As such, `tfm` must be created before `me`, and `me` must be created before `tfm`. That is not possible.

To solve the issue, we must allow the `MapExpr` to be created without the `tfm` expression. We can do this by creating another `ExprBlock` in the `MapExpr` constructor, and then later insert the `tfm` expression into that block. To do this, we modify the constructor to not require the `tfm` parameter:

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

    class MapExpr extends ExprBlock {
        private ExprBlock loopBody;

        init(SrcPos pos, Block parent, Expr src, SStr varName) {
            init(pos, parent) {
                loopBody(pos, parent);
            }

            Var local(this, named{Int}, varName, Actuals());
            add(local);

            add(pattern(this) {
                    Array<Int> original = ${src};
                    Array<Int> out;
                    for (Nat i = 0; i < original.count(); i++) {
                        ${LocalVarAccess(pos, local.var)} = original[i];
                        out << ${loopBody};
                    }
                    out;
                });
        }
    }

This change essentially replaces the usage of `tfm` with another `ExprBlock` called `loopBody`. We use the loop body as a placeholder to make it easy to insert the actual loop body later on.

Since the constructor of `MapExpr` no longer requres the `tfm` expression as a parameter, we can resolve the issue in the grammar by simply removing the last parameter to `MapExpr` (to make it read `MapExpr(pos, block, src, var)`). If we run the program now, it will produce another error:

    @/home/storm/expressions/map/semantics.bs(491-493): Syntax error:
    Can not find an implementation of the operator << for core.Array(core.Int)&, void.

To understand why the error occurred, we can once again print the generated syntax tree:

    {
        core.Int x;
        {
            core.Array(core.Int) original = values;
            core.Array(core.Int) out(core.Array(core.Int)());
            {
                core.Nat i = 0;
                for (i < core.ArrayBase.count(original); core.Nat.*++(i)) {
                    x = core.Array(core.Int).[](original, i);
                    out << {
                    };
                };
            };
            out;
        };
    }

From this output, it is fairly easy to see the issue. The last line in the loop currently reads: `out << {};`. Again, since empty blocks evaluate to `void`, we are currently trying to insert a value of the type `void` into an array that stores integers. This is what the compiler complains about.

Luckily, it is fairly easy to fix the error. We simply need to insert the `tfm` expression into our empty block. We can do this conveniently by creating a member function in the `MapExpr` class that we call from the grammar. We call the function `setTransform` and implement it as follows:

    void setTransform(Expr expr) {
        loopBody.add(expr);
    }

We can then call the function from the grammar by replacing `tfm` with `-> setTransform`. This means that the syntax transform will call `me.setTransform(<node>)` when the variable `me` is created, which is exactly what we need. As such, we can change our production into the following:

    SExpr => MapExpr(pos, block, src, var)
      : "map" #keyword, "(", SExpr(me) -> setTransform ~ "for" #keyword ~ SName var #varName
      ~ "in" #keyword ~ SExpr(block) src, ")";

And with that, the circular dependency is resolved while making sure that the transform expression is passed to the `MapExpr` in the end. To inspect the final tree, we can add a `print` statement to the end of the `setTransform` function. It produces the following output, which is what the compiler eventually turns into machine code:

    {
        core.Int x;
        {
            core.Array(core.Int) original = values;
            core.Array(core.Int) out(core.Array(core.Int)());
            {
                core.Nat i = 0;
                for (i < core.ArrayBase.count(original); core.Nat.*++(i)) {
                    x = core.Array(core.Int).[](original, i);
                    out << {
                        x + 2;
                    };
                };
            };
            out;
        };
    }

As we can see, the expression `x + 2` was inserted into the previously empty block, which caused the block evaluate to the correct type. Note that since we embedded the transform expression inside a block, it is necessary to use a call to `expectCastTo` to make sure that automatic type inference works properly in some cases. For simplicity, this was omitted from the code above.

For completeness, the final implementation of the `MapExpr` class is as follows:

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

    class MapExpr extends ExprBlock {
        private ExprBlock loopBody;

        init(SrcPos pos, Block parent, Expr src, SStr varName) {
            init(pos, parent) {
                loopBody(pos, parent);
            }

            Var local(this, named{Int}, varName, Actuals());
            add(local);

            add(pattern(this) {
                    Array<Int> original = ${src};
                    Array<Int> out;
                    for (Nat i = 0; i < original.count(); i++) {
                        ${LocalVarAccess(pos, local.var)} = original[i];
                        out << ${loopBody};
                    }
                    out;
                });
        }

        void setTransform(Expr expr) {
            loopBody.add(expectCastTo(expr, named{Int}, scope));
        }
    }