Episode 9: Wrap up and Conclusion

Welcome to the final Episode of the Parrot Compiler Tools Tutorial! Let's review the previous episodes, and summarize this tutorial.

Review
In Episode 1, we introduced the Parrot Compiler Tools (PCT), gave a high-level feature overview of Squaak, the case study language that we are implementing in this tutorial, and we generated a language shell that we use as a foundation to implement Squaak.

Episode 2 discussed the general structure of PCT-based compilers. After this, we described each of the four default compilation stages: parse phase, parse tree to PAST, PAST to POST and POST to PIR. We also added a command line banner and command line prompt to the interactive language shell.

In Episode 3, we introduced the full grammar of the Squaak language. After this, we started implementing the first bits, after which we were able to generate code for (simple) assignments.

In Episode 4 we discussed the construction of Parrot Abstract Syntax Tree nodes in more detail, after which we implemented the if-statement and throw-statement.

Episode 5 focused on variable declarations and variable scope. We implemented the necessary infrastructure to handle global and local variables correctly. In Episode 6 we continued the discussion of scope, but now in the context of subroutines. After this we implemented subroutine invocation.

Episode 7 extended our grammar to handle complex expressions that allows us to use arithmetic and other operators. We discussed how to use PCT's built-in support for handling operator precedence.

In the previous episode, Episode 8, we discussed the grammar and action methods for handling the aggregate data types of Squaak: arrays and hashes. We also touched on the topic of argument passing by reference and by value.

If you followed the tutorial and did the exercises, your implementation should be complete. Although a lot of the implementation was discussed, some parts were left as the proverbial exercise to the reader. This is to stimulate you to get your hands dirty and figure out things for yourself, while the text contained enough hints (in my opinion) to solve the given problems. Sure enough, this approach requires you to spend more time and think for yourself, but I think you're reading all this stuff to learn something. The extra time spent is well worth it, in my opinion.

Now it's time to see what we can do with this language. Squaak is more than just the average calculator example, which is often provided in beginner's discussions on parsers; it's a complete programming language.

What's Next?
This is the last episode of the Parrot Compiler Tools tutorial. We showed how we implemented a complete language for the Parrot virtual machine in only a few hundred lines of source code. Surely, this must be the proof that the PCT really is an effective toolkit for implementing languages. At the moment of writing, the PCT still lacks efficient support for certain language constructs. Therefore, we focused on the parts that are easy to build with the PCT. Once the PCT is feature complete, there's bound to be another tutorial on advanced features. Think of object-oriented programming, closures, coroutines, and advanced control-flow such as return statements. Most of them can be done already, but are too complex for this tutorial's level.

The Game of Life
You might have noticed that Squaak looks a bit like Lua, although it does differ in some points. This is not entirely accidental. In the distribution of the Lua source code, there's an example called "life.lua", which implements Conway's "Game of Life". This is a nice demonstration program, and it's easy to port it to Squaak. Its implementation is shown below. Run it, and enjoy!

## John Conway's Game of Life
## Implementation based on life.lua, found in Lua's distribution.
##
var width          = 40    # width of "board"
var height         = 20    # height of "board"
var generation     = 1     # generation couner
var numgenerations = 50    # how often should we evolve?

## initialize board to all zeroes
sub initboard(board)
    for var y = 0, height do
        for var x = 0, width do
            board[y][x] = 0
        end
    end
end

## spawn new life in board, at position (left, top),
## the life data is stored in shapedata, and shape width and
## height are specified.
sub spawn(board, left, top, shapew, shapeh, shapedata)
    for var y = 0, shapeh - 1 do
        for var x = 0, shapew - 1 do
            board[top + y][left + x] = shapedata[y * shapew + x]
        end
    end
end

## calculate the next generation.
sub evolve(thisgen, nextgen)
    var ym1 = height - 1
    var y   = height
    var yp1 = 1
    var yi  = height

    while yi > 0 do
        var xm1 = width-1
        var x   = width
        var xp1 = 1
        var xi  = width

        while xi > 0 do

            var sum = thisgen[ym1][xm1]
                    + thisgen[ym1][x]
                    + thisgen[ym1][xp1]
                    + thisgen[y][xm1]
                    + thisgen[y][xp1]
                    + thisgen[yp1][xm1]
                    + thisgen[yp1][x]
                    + thisgen[yp1][xp1]

            nextgen[y][x] = sum==2 and thisgen[y][x] or sum==3

            xm1 = x
            x   = xp1
            xp1 = xp1 + 1
            xi  = xi - 1
        end

        ym1 = y
        y   = yp1
        yp1 = yp1 + 1
        yi  = yi - 1

    end
end

## display thisgen to stdout.
sub display(thisgen)
    var line = ""
    for var y = 0, height do
        for var x = 0, width do
            if thisgen[y][x] == 0 then
                line = line .. "-"
            else
                line = line .. "O"
            end

        end
        line = line .. "\n"
    end
    print(line, "\nLife - generation: ", generation)
end

## main program
sub main()
    var heart   = [1,0,1,1,0,1,1,1,1]
    var glider  = [0,0,1,1,0,1,0,1,1]
    var explode = [0,1,0,1,1,1,1,0,1,0,1,0]

    var thisgen = []
    initboard(thisgen)

    var nextgen = []
    initboard(nextgen)

    spawn(thisgen,3,5,3,3,heart)
    spawn(thisgen,5,4,3,3,glider)
    spawn(thisgen,25,10,3,4,explode)

    while generation <= numgenerations do
        evolve(thisgen, nextgen)
        display(thisgen)
        generation = generation + 1

        ## prevent switching nextgen and thisgen around,
        ## just call evolve with arguments switched.
        evolve(nextgen, thisgen)
        display(nextgen)
        generation = generation + 1

    end
end

## start here.
main()

Note the use of a subroutine "print". Check out the file src/builtins/say.pir, and rename the sub "say" (which was generated by the language shell creation script) to "print".

Exercises
Squaak was designed to be a simple language, offering enough features to get some work done, but at the same time keeping it simple. Of course, after reading this tutorial, You are an expert too ;-) If you feel like adding more features, here are some suggestions.

• Implement prefix and postfix increment/decrement operators, allowing you to write "generation++" instead of "generation = generation + 1".
• Implement augmenting assign operators, such as "+=" and friends.
• Extend the grammar to allow multiple variable declarations in one statement, allowing you to write "var x = 1, y, z =3". Of course, the initialization part should still be optional. How do you make sure that the identifier and initialization expression are kept together?
• Implement a mechanism (such as an "import" statement) to include or load another Squaak file, so Squaak programs can be split into multiple files. The PCT does not have any support for this, so you'll need to write a bit of PIR to do this.
  
• Improve the for-statement, to allow for a negative step. Note that the loop condition becomes more complex when doing so.
  

Note that these are suggestions, and I did not implement them myself, so I won't have a solution for you at the end.

Final words and Acknowledgments
By now, you should have got a good impression of the PCT and you should be able to work on other languages targeting Parrot. Currently, work has been done on ECMAScript, Python, Ruby and of course Perl 6. Most of them are not complete yet (hint, hint).

I hope you enjoyed reading this tutorial and learned enough to feel confident about working on other (existing) languages targeting Parrot. The Perl 6 implementation can still use more contributors!

Many thanks to all who read this tutorial and provided me with hints, tips and feedback! Thank You for reading this!

License
The source code in this tutorial has been released by the author into the public domain. Where this is not possible by law, the author grants license to use this file for any reason without any rights reserved, and with no warranty express or implied or fitness for a particular purpose.

Episode 8: Hashtables and Arrays

Welcome to Episode 8! This is the second-last episode in this tutorial. After this episode, we'll have a complete implementation of our Squaak language.
This episode focuses on aggregate data structures: arrays and hashtables. We'll discuss the syntax to assign to them and to construct them. We'll see that implementing the action methods is really easy, almost trivial. After that, we'll make some notes on aggregates as arguments, and how they differ from the basic data types when passing them around as subroutine arguments.

Arrays and Hashtables
Besides basic data types such as integer, floating-point and string, Squaak has two aggregate data types: array and hashtable. An array is an object that can store a sequence of values. The values in this sequence can be of different types, unlike some languages that require all elements of an array to be the same type. An example of using arrays is shown below:

grades[0] = "A"
grades[1] = "A+"
grades[2] = "B+"
grades[3] = "C+"

A hashtable stores key-value pairs; the key is used as index to store a value. Keys must be string constants, but the value can be of any type. An example is shown below:

lastnames{"larry"}   = "wall"
lastnames{"allison"} = "randal"

Array constructors
Just as there are integer literals (42) and string literals ("hello world") that can be assigned to variables, you can have array literals. Below is the grammar rule for this:

rule array_constructor {
   '[' [ <expression> [',' <expression>]*]? ']'
   {*}
}

Some examples are shown below:

foo = []
bar = [1, "hi", 3.14]
baz = [1, [2, 3, 4] ]

The first example creates an empty array and assigns this to foo. The second example shows the construction of three elements, assigning the array to bar. Note that the elements of one array can be of different types. The third example shows the construction of nested arrays. This means that element baz[1][0] evaluates to the value 2 (indexing starts at 0).

Hashtable constructors
Besides array literals, Squaak supports hashtable literals, that can be constructed through a hashtable constructor. The syntax for this is expressed below:

rule hash_constructor {
    '{' [<named_field> [',' <named_field>]* ]? '}'
     {*}
}

rule named_field {
    <string_constant> '=>' <expression>
    {*}
}

Some examples are shown below:

foo = {}
bar = { "larry" => "wall", "allison" => "randal" }
baz = { "a" => { "b" => 42} }

The first line creates an empty hashtable and assigns this to foo. The second creates a hashtable with two fields: "larry" and "allison". Their respective values are: "wall" and "randal". The third line shows that hashtables can be nested, too. There, a hashtable is constructed that has one field, called "a", and its value is another hashtable, containing a field "b" that has the value 42.

Implementation
You might think implementing support for arrays and hashtables looks rather difficult. Well, it's not. Actually, the implementation is rather straightforward. First, we're going to update the grammar rule for primary:

rule primary {
    <identifier> <postfix_expression>*
    {*}
}

rule postfix_expression {
    | <index> {*}   #= index
    | <key> {*}     #= key
}

rule index {
    '[' <expression> ']'
    {*}
}

rule key {
    '{' <expression> '}'
    {*}
}

A primary object is now an identifier followed by any number of postfix-expressions. A postfix expression is either a hashtable key or an array index. Allowing any number of postfix expressions allows to nest arrays and hashtables in each other, allowing us to write, for instance:

foo{"key"}[42][0]{"hi"}

Of course, you as a Squaak programmer must make sure that foo is actually a hashtable, and that foo{"key"} yields an array, and so forth. Implementing this is actually quite simple. First, let us see how to implement the action method index.

method index($/) {
    my $index := $( $<expression> );

    my $past := PAST::Var.new( $index,
                             :scope('keyed'),
                             :viviself('Undef'),
                             :vivibase('ResizablePMCArray'),
                             :node($/) );
    make $past;
}

First, we retrieve the PAST node for expression. Then, we create a keyed variable access operation, by creating a PAST::Var node and setting its scope to 'keyed'. If a PAST::Var node has keyed scope, then the first child is evaluated as the aggregate object, and the second child is evaluated as the index on that aggregate.

But wait! The PAST::Var node we just created has only one child!

Here's where the updated action method for primary comes in. This is shown below.

method primary($/) {
    my $past := $( $<identifier> );

    for $<postfix_expression> {
        my $expr := $( $_ );
        $expr.unshift( $past );
        $past := $expr;
    }
    make $past;
}

First, the PAST node for identifier is retrieved. Then, for each postfix-expression, we get the PAST node, and unshift the (current) $past onto it. Effectively, the (current) $past is set as the first child of $expr. And you know what $expr contains: that's the keyed variable access node, that was created in the action method index.
After that, $past is set to $expr; either there's another postfix-expression, in which case this $past will be set as the first child of that next postfix-expression, or, the current $past is set as the result object.

Implementing Constructors
To implement the array and hashtable constructors, we're going to take advantage of Parrot's Calling Conventions (PCC). The PCC supports, amongst others, optional parameters, named parameters and slurpy parameters. If you're Dutch, you might think that slurpy parameters make a lot of noise ("slurpen" is a Dutch verb meaning drinking carefully, which you usually do if your beverage is hot, making noise in the process), but you would be wrong. Slurpy parameters will store all remaining arguments that have not yet been stored in other parameters (implying that there can only be one slurpy (positional) parameter, and it should come after all normal (positional) parameters). Parrot will automatically create an aggregate to store these remaining arguments. Besides positional slurpy parameters, you can also define a named slurpy parameter, which will store all remaining named parameters, after all normal (named) arguments have been stored.

You might be confused by now.

Let's look at an example, as this issue is worth a few brain cells to store.

.sub foo
  .param pmc a
  .param pmc b
  .param pmc c :slurpy
  .param pmc k :named('x')
  .param pmc l :named('y')
  .param pmc m :named :slurpy

.end

foo(1, 2, 3, 4, 6 :named('y'), 5 :named('x'), 7 :named('p'), 8 :named('q') )

This will result in the following mapping:

a: 1
b: 2
c: {3, 4}
k: 5
l: 6
m: {"p"=>7, "q"=>8}

So, after the positional parameters (a, b), c is declared as a slurpy parameters, storing all remaining positional parameters. Parameters k and l are declared as named parameters, which have the respective names "x" and "y". Using these names, values can be passed. After the named parameters, there's the parameter m, which is both flagged as named and slurpy. This parameter will store all remaining named arguments that have not yet been stored by the normal named parameters.

The interesting parameters for us are "c" and "m". For the positional slurpy parameter, Parrot creates an array, while for the named slurpy parameter a hashtable is created. This happens to be exactly what we need! Implementing the array and hash constructors becomes trivial:

.sub '!array'
  .param pmc fields :slurpy
  .return (fields)
.end

.sub '!hash'
  .param pmc fields :named :slurpy
  .return (fields)
.end

Array and hashtable constructors can then be compiled into subroutine calls to the respective Parrot subroutines, passing all fields as arguments. (Note that these names start with a "!", which is not a valid Squaak identifier. This prevents us from calling these subs in normal Squaak code).

Basic data types and Aggregates as arguments
All data types, both basic and aggregate data types are represented by Parrot Magic Cookies (PMCs). The PMC is one of the four built-in data types that Parrot can handle; the others are integer, floating-point and string. Currently, the PCT can only generate code to handle PMCs, not the other basic data types.
Parrot has registers for each its four built-in data types. The integer, floating-point and string registers store the actual data value, while PMC registers store a reference to the PMC object. This has consequences for how PMCs are handled when passing them as arguments. When passing a PMC as an argument, the invoked subroutine gets access to the PMC reference; in other words, PMCs are passed by reference. This means that the subroutine can change the original argument that was passed by the caller. Of course, it depends what instructions are being generated, what the invoked subroutine does to the references.
In Squaak, when passing basic data values, these cannot be changed by the invoked subroutine. When assigning a new value to a parameter, a whole new object is created and bound to the parameter identifier. No changes are made to the original argument.
Aggregate data types are handled differently, however. When an invoked subroutine assigns to an index or hashtable field of a parameter, then the original argument is affected.
In other words, basic data types have by value semantics, while aggregate data types have by reference semantics. A short example to demonstrate this:

sub foo(a,b,c)
  a       = 42
  b[0]    = 1
  c{"hi"} = 2
end

var a = 0
var b = []
var c = {}
foo(a,b,c)

print(a, b[0], c{"hi"} ) # prints 0, 1, 2

What's Next?
This was the last episode to discuss implementation details to make Parrot (run) Squaak. After doing this episode's exercises, your implementation should be fairly complete. Next episode will be the last of this series, in which we'll recap what we did, and demonstrate our language with a nice demo program.

Exercises

1. We've shown how to implement keyed variable access for arrays, by implementing the action method for index. The same principle can be applied to keyed access for hashtables. Implement the action method for key.
2. Implement the action methods for array_constructor and hash_constructor. Use a PAST::Op node and set the pasttype to 'call'. Use the "name" attribute to specify the names of the subs to be invoked (e.g., :name("!array") ). Note that all hash fields must be passed as named arguments. Check out PDD26 for doing this, and look for a "named " method.
   
3. We'd like to add a little bit of syntactic sugar for accessing hashtable keys. Instead of writing foo{"key"}, I'd like to write foo.key. Of course, this only works for keys that do not contain spaces and such. Add the appropriate grammar rule (call it "member") that enables this syntax, and write the associated action method. Make sure this member name is converted to a string.
   Hint: use a PAST::Val node for the string conversion.
   

License
The source code in this tutorial has been released by the author into the public domain. Where this is not possible by law, the author grants license to use this file for any reason without any rights reserved, and with no warranty express or implied or fitness for a particular purpose.

Episode 7: Operators and Precedence

Up till now, we've implemented a great deal of the Squaak language. We've seen assignments, control-flow statements, variable declarations and scope, subroutines and invocation. Our expressions have been limited so far to singular values, such as string literals and integer constants.
In this episode, we'll enhance Squaak so it can handle operators, so you can construct more complex expressions.

Operators, precedence and parse trees
We will first briefly introduce the problem with recursive-descent parsers (which parsers generated with the PCT are) when parsing expressions. Consider the following mini-grammar, which is a very basic calculator.

rule TOP {
   <expression>*
}

rule expression {
   <term>
}

rule term {
   <factor> [ <addop> <factor> ]*
}

token addop { '+' | '-' }

rule factor {
   <value> [ <mulop> <value> ]*
}

token mulop { '*' | '/' | '%' }

rule value{
   | <number>
   | '(' <expression> ')'
}

This basic expression grammar implements operator precedence by taking advantage of the nature of a recursive-descent parser (if you haven't seen the word, google it). However, the big disadvantage of parsing expressions this way, is that the parse trees can become quite large. Perhaps more importantly, the parsing process is not very efficient. Let's take a look at some sample input. We won't show the parse trees as shown in Episode 2, but we'll just show an outline.

input: 42 results in this parse tree:

TOP
  expression
    term
      factor
        value
          number
            42

As you can see, the input of this single number will invoke 6 grammar rules before parsing the actual digits. Not that bad, you might think.

input: "1 + 2" results in this parse tree (we ignore the operator for now):

TOP
  expression
    term
      factor
      | value
      |   number
      |     1
      factor
        value
          number
            2

Only a few more grammar rules are invoked, not really a problem either.

input: "(1 + 2) * 3" results in this parse tree:

TOP
  expression
    term
      factor
        value
        | expression
        |   term
        |   | factor
        |   |   value
        |   |     number
        |   |       1
        |   term
        |     factor
        |       value
        |         number
        |           2
        value
          number
            3

Right; 16 grammar rules just to parse this simple input. I'd call this slightly inefficient. The point is, implementing operator precedence using a recursive-descent parser is somewhat problematic, and given the fact there are better methods to parse expressions like these, not the way to go. Check out this nice explanation or google it.

Bottom-up parsing and stacks: operator tables
I would like to explain to you how bottom-up parsing works for expressions (or bottom-up parsers in general; Yacc/Bison are parser generators that generate bottom-up parsers for your grammar specification), taking operator precedence into account. However, it's been about 6 years that I did this in a CS class, and I don't remember the particular details. If you really want to know, check out the links at the end of the previous section. It's actually worth checking out. For now, I'll just assume you know what the problem is, so that I'll introduce the solution for PCT-based compilers immediately.
At some point when parsing your input, you might encounter an expression. At this point, we'd like the parser to switch from top-down to bottom-up parsing. The Parrot Grammar Engine supports this, and is used as follows:

rule expression is optable { ... }

Note that we used the word "expression" here, but you can name it anything. This declares that, whenever you need an expression, the bottom-up parser is activated. Of course, this "optable" must be populated with some operators that we need to be able to parse. This can be done by declaring operators as follows:

proto 'infix:*' is tighter('infix:+') { ... }

This defines the operator "*" (the "infix:" is a prefix that tells the operator parser that this operator is an infix operator; there are other types, such as prefix, postfix and others). The "is tighter" clause tells that the "*" operator has a higher precedence than the "+" operator. As you could have guessed, there are other clauses to declare equivalent precedence ("is equiv") and lower precedence ("is looser").

It is very important to spell all clauses, such as "is equiv" correctly (for instance, not "is equil"), otherwise you might get some cryptic error message when trying to run your compiler. See the references section for the optable guide, that has more details on this.

Of course, the expression parser does not just parse operators, it must also parse the operands. So, how do we declare the most basic entity that represents an operand? It can be anything, from a basic integer-constant, a function call, or even a function definition (but adding two function definition doesn't really make sense, does it?). The operands are parsed in a recursive-descent fashion, so somewhere the parser must switch back from bottom-up (expression parsing) to top-down. To declare this "switch-back" point, write:

proto 'term:' is tighter('prefix:-')
              is parsed(&term)       { ... }

The name "term:" is a built-in name of the operator bottom-up parser; it is invoked every time a new operand is needed. The "is parsed" clause tells the parser that "term" (which accidentally looks like "term:", but you could also have named it anything else) parses the operands.

Note: it is very important to add a "is tighter" clause to the declaration of the "term:" rule. Otherwise your expression parser will not work! My knowledge here is a bit limited, but I usually define it as "is tighter" relative to the tightest operator defined.

Squaak Operators
We have defined the entry and exit point of the expression (bottom-up) parser, now it's time to add the operators. Let's have a look at Squaak's operators and their precedence. The operators are listed with decreasing precedence (so that high-precedence operators are listed at the top). (I'm not sure if this precedence table is common compared to other languages; some operators may have a different precedence w.r.t. other operators than you're used to. At least the mathematical operators are organized according to standard math rules).

unary "-"
unary "not"
* / %
+ - ..
< <= >= > != ==
and
or

(".." is the string concatenation operator). Besides defining an entry and exit point for the expression parser, you need to define some operator as a reference point, so that other operators' precedence can be defined relative to that reference point. My personal preference is to declare the operator with the lowest precedence as the reference point. This can be done like this:

proto 'infix:or' is precedence('1') { ... }

Now, other operators can be defined:

proto 'infix:and' is tighter('infix:or') { ... }
proto 'infix:<' is tighter('infix:and') { ... }
proto 'infix:+' is tighter('infix:<') { ... }
proto 'infix:*' is tighter('infix:+') { ... }
proto 'prefix:not' is tighter('infix:*') { ... }
proto 'prefix:-' is tighter('prefix:not') { ... }

Note that some operators are missing. See the exercises section for this. For more details on the use of the optable, check out docs/pct/pct_optable_guide.pod in the Parrot repository.

Short-circuiting logical operators
Squaak has two logical operators: and and or; and results true if and only if both operands evaluate to true, while or results true if at least one of its operands evaluates to true. Both operands are short-circuited, which means that they don't evaluate both operands if that's unnecessary. For instance, if the first operand of the and operator evaluates to false, then there's no need to evaluate the second operand, as the final result of the and-expression cannot become true anymore (remember: both operands must evaluate to true).

Let's think about how to implement this. When evaluating an and-expression, we first evaluate the first operand, and if it's true, only then does it make sense to evaluate the second operand. This behavior looks very much the same as an if-statement, doesn't it? In an if-statement, the first child is always evaluated, and if true, the second child (the "then" block) is evaluated (remember, the third child -- the "else" clause -- is optional). It would be great to be able to implement the and operator using a PAST::Op( :pasttype('if') ) node. Well, you can, using the "is pasttype" clause! Here's how:

proto 'infix:and' is tighter('infix:or')
                  is pasttype('if') { ... }

So what about the or operator? When evaluating an or-expression, the first operand is evaluated. If it evaluates to true, then there's no need to evaluate the second operand, as the result of the or-expression is already true! Only if the first operand evaluates to false, is it necessary to evaluate the second child. Mmmmm.... what we're saying here is, unless the first operand evaluates to true, evaluate the second child. Guess what pasttype you'd need for that!

Operators PAST types and PIR instructions
In the previous section, we introduced the "pasttype" clause that you can specify. This means that for that operator (for instance, the "and" operator we discussed), a PAST::Op( :pasttype('if') ) node is created. What happens if you don't specify a pasttype?

In that case a default PAST::Op node is created, and the default pasttype is 'call'. In other words, a PAST::Op node is created that calls the declared operator. For instance, the "infix:+" operator results in a call to the subroutine "infix:+". This means you'll need to implement subroutines for each operator.
Now, that's a bit of a shame. Obviously, some languages have very exotic semantics for the "+" operator, but many languages just want to use Parrot's built-in add instruction. How do we achieve that?
Instead of adding a "pasttype" clause, specify a "pirop" clause. The "pirop", or "PIR operator", clause tells the code generator what operator should be generated. Instead of generating a subroutine invocation with the operands as arguments, it will generate the specified instruction with the operator's operands as arguments. Neat huh? Let's look at an example:

proto 'infix:+' is tighter('infix:<')
                is pirop('n_add') { ... } 

This specifies to use the "n_add" instruction, which tells Parrot to create a new result object instead of changing one of the operands. Why not just the "add" instruction (which takes two operands, updating the first), you might think. Well, if you leave out this "is pirop" stuff, this will be generated:

$P12 = "infix:+"($P10, $P11)

You see, three registers are involved. As we mentioned before, PCT does not do any optimizations. Therefore, instead of the generated instruction above, it just emit the following:

n_add $P12, $P10, $P11

which means that the PMCs in registers $P10 and $P11 are added, and assigned to a newly created PMC which is stored in register $P12.

To circumfix or not to circumfix
Squaak supports parenthesized expressions. Parentheses can be used to change the order of evaluation in an expression, just as you're probably have seen this in other languages. Besides infix, prefix and postfix operators, you can define circumfix operators, which is specified with the left and right delimiter. This is an ideal way to implement parenthesized expressions:

proto 'circumfix:( )' is looser('infix:+')
                      is pirop('set') { ... }

By default, a subroutine invocation will be generated for each operator, in this case a call to "circumfix:( )". However, we are merely interested in the expression that has been parenthesized. The subroutine would merely return the expression. Instead, we can use the pirop attribute to specify what PIR operation should be generated; in this case that is the "set" operation, which sets one register to the contents of another.

This solution works fine, except that "set" instructions are a bit of a waste. What happens is, the contents of some register is just copied to another register, which is then used in further code generation. This "set" instruction might as well be optimized away. Currently, there are no optimizations implemented in the PCT.
There is an alternative solution for adding grammar rules for the parenthesized expressions, by adding it as an alternative of term. The grammar rule term then ends up as:

rule term {
    | <float_constant> {*}     #= float_constant
    | <integer_constant> {*}   #= integer_constant
    | <string_constant&gt {*}  #= string_constant
    | <primary> {*}            #= primary
    | '(' <expression> ')' {*} #= expression
}

Of course, although we save one generated instruction, the parser will be slightly more inefficient, for reasons that we discussed at the beginning of this episode. Of course, you are free to decide for yourself how to implement this; this section just explains both methods. At some point, optimizations will be implemented in the PCT. I suspect "useless" instructions (such as the "set" instruction we just saw) will then be removed.

Expression parser's action method
For all grammar rules we introduced, we also introduced an action method that is invoked after the grammar rule was done matching. What about the action method for the optable? Naturally, there must be some actions to be executed.

Well, there is, but to be frank, I cannot explain it to you. Every time I needed the action method for an optable, I just copied it from an existing actions file. Of course, the action method's name should match the name of the optable (the rule that has the "is optable" clause). So, here goes:

method expression($/, $key) {
    if ($key eq 'end') {
        make $($<expr>);
    }
    else {
        my $past := PAST::Op.new(
                      :name($<type>),
                      :pasttype($<top><pasttype>),
                      :pirop($<top><pirop>),
                      :lvalue($<top><lvalue>),
                      :node($/) );
        for @($/) {
            $past.push( $($_) );
        }
        make $past;
    }
}

What's Next?
This episode covered the implementation of operators, which allows us to write complex expressions. By now, most of our language is implemented, except for one thing: aggregate data structures. This will be the topic of Episode 8. We will introduce the two aggregate data types: array and hashtables, and see how we can implement these. We'll also discuss what happens when we pass such aggregates as subroutine arguments, and the difference with the basic data types.

Exercises

1. Currently, Squaak only has grammar rules for integer and string constants, not floating point constants. Implement this grammar rule. A floating-point number consists of zero or more digits, followed by a dot and at least one digit, or, at least one digit followed by a dot and any number of digits. Examples are: 42.0, 1., .0001. There may be no whitespace between the individual digits and the dot. Make sure you understand the difference between a "rule" and a "token".
   Hint: currently, the Parrot Grammar Engine (PGE), the component that "executes" the regular expressions (your grammar rules), matches alternative subrules in order. This means that this won't work:
   

   rule term {
     | <integer_constant>
     | <float_constant>
     ...
   }
   

   because when giving the input "42.0", "42" will be matched by <integer_constant>, and the dot and "0" will remain. Therefore, put the <float_constant> alternative in rule term before <integer_constant>. At some point, PGE will support longest-token matching, so that this issue will disappear.
2. Implement the missing operators: (binary) "-", "<=", ">=", "==", "!=", "/", "%", "or"
   

References

• docs/pct/pct_optable_guide.pod
  

License
The source code in this tutorial has been released by the author into the public domain. Where this is not possible by law, the author grants license to use this file for any reason without any rights reserved, and with no warranty express or implied or fitness for a particular purpose.

Episode 6: Scope and Subroutines

In Episode 5, we looked at variable declarations and implementing scope. We covered a lot of information then, but did not tell the full story, in order to keep that post short. In this episode we'll address the missing parts, which will also result in implementing subroutines.

Variables
In the previous episode, we entered local variables into the current block's symbol table. As we've seen earlier, using the do-block statement, scopes may nest. Consider this example:

do
   var x = 42
   do
      print(x)
   end
end

In this example, the print statement should print 42, even though x was not declared in the scope where it is referenced. How does the compiler know it's still a local variable? That's simple: it should look in all scopes, starting at the innermost scope. Only when the variable is found in any scope, should its scope be set to "lexical", so that the right instructions are being generated.

The solution I came up with is shown below. Please note that I'm not 100% sure if this is the "best" solution, but my personal understanding of the PAST compiler is limited. So, while this solution works, I may teach you the wrong "habit". Please be aware of this.

method identifier($/) {
    our @?BLOCK;

    my $name  := ~$<ident>;
    my $scope := 'package'; # default value

    # go through all scopes and check if the symbol
    # is registered as a local. If so, set scope to
    # local.
    for @?BLOCK {
        if $_.symbol($name) {
            $scope := 'lexical';
        }
    }

    make PAST::Var.new( :name($name),
                        :scope($scope),
                        :viviself('Undef'),
                        :node($/) );
}

Viviself
You might have noticed the viviself attribute before. This attribute will result in extra instructions that will initialize the variable if it doesn't exist. As you know, global variables spring into life automatically when they're used. Earlier we mentioned that uninitialized variables have a default value of "Undef": the viviself attribute does this.
For local variables, we use this mechanism to set the (optional) initialization value. When the identifier is a parameter, the parameter will be initialized automatically if it doesn't receive a value when the subroutine it belongs to is invoked. Effectively this means that all parameters in Squaak are optional!

Subroutines
We already mentioned subroutines before, and introduced the PAST::Block node type. We also briefly mentioned the blocktype attribute that can be set on a PAST::Block node, which indicates whether the block is to be executed immediately (for instance, a do-block or if statement) or it represents a declaration (for instance, subroutines). Let us now look at the grammar rule for subroutine definitions:

rule sub_definition {
    'sub' <identifier> <parameters>
    <statement>*
    'end'
    {*}
}

rule parameters {
    '(' [<identifier> [',' <identifier>]* ]? ')'
    {*}
}

This is rather straightforward, and the action methods for these rules are quite simple, as you will see. First, however, let's have a look at the rule for sub definitions. Why is the sub body defined as <statement>* and not as a <block>? Surely, a subroutine defines a new scope, which was already covered by <block> Well, you're right in that. However, as we will see, by the time that a new PAST::Block node would be created, we are too late! The parameters would already have been parsed, and not entered into the block's symbol table. That's a problem, because parameters are most likely to be used in the subroutine's body, and as they are not registered as local variables (which they are), any usage of parameters would not be compiled down to the right instructions to fetch any parameters.

So, how do we solve this in an efficient way?

The solution is simple. The only place where parameters live, is in the subroutine's body, represented by a PAST::Block node. Why don't we create the PAST::Block node in the action method for the parameters rule. By doing so, the block is already in place and the parameters are registered as local symbols right in time. Let's look at the action methods.

method parameters($/) {
    our $?BLOCK;
    our @?BLOCK;

    my $past := PAST::Block.new( :blocktype('declaration'),
                                 :node($/) );

    # now add all parameters to this block
    for $<identifier> {
        my $param := $( $_ );
        $param.scope('parameter');
        $past.push($param);

        # register the parameter as a local symbol
        $past.symbol($param.name(), :scope('lexical'));
    }

    # now put the block into place on the scope stack
    $?BLOCK := $past;
    @?BLOCK.unshift($past);

    make $past;
}

method sub_definition($/) {
    our $?BLOCK;
    our @?BLOCK;

    my $past := $( $<parameters> );
    my $name := $( $<identifier> );

    # set the sub's name
    $past.name( $name.name() );

    # add all statements to the sub's body
    for $<statement> {
        $past.push( $( $_ ) );
    }

    # and remove the block from the scope
    # stack and restore the current block
    @?BLOCK.shift();
    $?BLOCK := @?BLOCK[0];

    make $past;
}

First, let's check out the parse action for parameters. First, a new PAST::Block node is created. Then, we iterate over the list of identifiers (which may be empty), each representing a parameter. After retrieving the result object for a parameter (which is just an identifier), we set its scope to "parameter", and we add it to the block object. After that, we register the parameter as a symbol in the block object, specifying the scope as "lexical". Parameters are just a special kind of local variables, and there's no difference in a parameter and a declared local variable in a subroutine, except that a parameter will usually be initialized with a value that is passed when the subroutine is invoked.
After handling the parameters, we set the current block (referred to by our package variable $?BLOCK) to PAST::Block node we just created, and push it on the scope stack (referred to by our package variable @?BLOCK).

After the whole subroutine definition is parsed, the action method sub_definition is invoked. This will retrieve the result object for parameters, which is the PAST::Block node that will represent the sub. After retrieving the result object for the sub's name, we set the name on the block node, and add all statements to the block. After this, we pop off this block node of the scope stack (@?BLOCK), and restore the current block ($?BLOCK).

Pretty easy, huh?

Subroutine invocation
Once you defined a subroutine, you'll want to invoke it. In the exercises of Episode 5, we already gave some tips on how to create the PAST nodes for a subroutine invocation. In this section, we'll give a complete description. First we'll introduce the grammar rules.

rule sub_call {
    <primary> <arguments>
    {*}
}

Not only allows this to invoke subroutines by their name, you can also store the subroutines in an array or hash field, and invoke them from there. Let's take a look at the action method, which is really quite straightforward.

method sub_call($/) {
    my $invocant := $( $<primary> );
    my $past     := $( $<arguments> );
    $past.unshift($invocant);
    make $past;
}

method arguments($/) {
    my $past := PAST::Op.new( :pasttype('call'), :node($/) );
    for $<expression> {
        $past.push( $( $_ ) );
    }
    make $past;
}

The result object of the sub_call method should be a PAST::Op node (of type 'call'), which contains a number of child nodes: the first one is the invocant object, and all remaining children are the arguments to that sub call.
In order to "move" the result objects of the arguments to the sub_call method, we create the PAST::Op node in the method arguments, which is then retrieved by sub_call. In sub_call, the invocant object is set as the first child (using unshift). This is all too easy, isn't it? :-)

What's Next?
In this episode we finished the implementation of scope in Squaak, and implemented subroutines. Our language is coming along nicely! In the next episode, we'll explore how to implement operators and an operator precedence table for efficient expression parsing.

In the mean time, should you have any problems or questions, don't hesitate to leave a comment!

Exercises

1. By now you should have a good idea on the implementation of scope in Squaak. We haven't implemented the for-statement yet, as it needs proper scope handling to implement. Implement this. Check out episode 3 for the BNF rules that define the syntax of the for-statement. When implementing it, you will run into the same issue as we did when implementing subroutines and parameters. Use the same trick for the implementation of the for-statement.

License
The source code in this tutorial has been released by the author into the public domain. Where this is not possible by law, the author grants license to use this file for any reason without any rights reserved, and with no warranty express or implied or fitness for a particular purpose.

Episode 5: Variable declaration and Scope

Episode 4 discussed the implementation of some statement types, such as the if-statement. In this episode we'll talk about variable declarations and scope handling. It's going to be a long story, so take your time to read this episode.

Globals, locals and default values
Squaak variables have one of two scopes: either they're global, or they're local. In order to create a global variable, you just assign some expression to an identifier (which hasn't been declared as a local). Local variables, on the other hand, must be declared using the "var" keyword. In other words, at any given point during the parsing phase, we have a list of variables that are known to be local variables. When an identifier is parsed, it is looked up and if found, its scope is set to local. If not, its scope is assumed to be global. When using an uninitialized variable, its value is set to an object called "Undef". Some examples are shown below.

x = 42             # x was not declared, so it is global
var k = 10         # k is local and initialized to 10
a + b              # neither a nor b was declared;         
                   # both default to the value "Undef"

Scoping and Symbol Tables
Earlier we mentioned the need to store declared local variables. In compiler jargon, such a data structure to store declarations is called a symbol table. For each individual scope, there's a separate symbol table.

Squaak has a so-called do-block statement, that is defined below.

rule do_block {
    'do' <block> 'end'
    {*}
}

Each do-block defines a new scope; local variables declared between the "do" and "end" keywords are local to that block. An example to clarify this is shown below:

do
  var x = 1
  print(x)      # prints 1

  do
    var x = 2
    print(x)    # prints 2
  end

  print(x)      # prints 1
end

So, each do/end pair defines a new scope, in which any declared variables hide variables with the same name in outer scopes. This behavior is common in many programming languages.
The PCT has built-in support for symbol tables; a PAST::Block object has a method symbol that can be used to enter new symbols and query the table for existing ones.
In PCT, a PAST::Block object represents a scope. There are two blocktypes: "immediate" and "declaration". An "immediate" block can be used to represent the blocks of statements in an do-block statement, for instance:

do  
  block 
end

When executing this statement, block is executed immediately. A "declaration" block, on the other hand, represents a block of statements that can be invoked at a later point, typically these are subroutines. So, in this example:

sub foo(x)
  print(x)
end

a PAST::Block object is created for the subroutine "foo". The blocktype is set to "declaration", as the subroutine is defined, not executed (immediately). For now you can forget about the blocktype, but now that I've told you, you'll recognize it when you see it. We'll come back to it in a later episode.

Implementing Scope
So, we know how to use global variables, declare local variables, and about PAST::Block objects representing scopes. How do we make our compiler to generate the right PIR instructions? After all, when handling a global variable, Parrot must handle this differently from handling a local variable.
When creating PAST::Var nodes to represent the variables, we must know whether the variable is a local or a global variable. So, when handling variable declarations (of local variables; globals are not declared), we need to register the identifier as a local in the current block's symbol table. First, we'll take a look at the implementation of variable declarations.

Variable declaration
The following is the grammar rule for variable declarations. This is a type of statement, so I assume you know how to extend the statement rule to allow for variable declarations.

rule variable_declaration {
    'var' <identifier> ['=' <expression>]?
    {*}
}

A local variable is declared using the "var" keyword, and has an optional initialization expression. If the latter is missing, the variable's value defaults to the undefined value called "Undef". Let's see what the parse action looks like:

method variable_declaration($/) {
    # get the PAST for the identifier
    my $past := $( $<identifier> );

    # this is a local (it's being defined)
    $past.scope('lexical');

    # set a declaration flag
    $past.isdecl(1);

    # check for the initialization expression
    if $<expression> {
        # use the viviself clause to add a
        # an initialization expression
        $past.viviself( $( $<expression>[0] );
    }
    else { # no initialization, default to "Undef"
        $past.viviself('Undef');
    }
    make $past;
}

Well, that wasn't too hard, was it? Let's analyze what we just did. First we retrieved the PAST node for the identifier, which we then decorated by setting its scope to "lexical" (a local variable is said to be lexically scoped, hence "lexical"), and setting a flag indicating this node represents a declaration (isdecl). So, besides representing variables in other statements (for instance, assignments), a PAST::Var node is also used as a declaration statement.

Earlier in this episode we mentioned the need to register local variables in the current scope block when they are declared. So, when executing the parse action for variable-declaration, there should already be a PAST::Block node around, that can be used to register the symbol being declared. As we learned in Episode 4, PAST nodes are created in a depth-first fashion; the leafs are created first, and then the nodes "higher" in the parse tree. This implies that a PAST::Block node is created after the statement nodes (which variable_declaration is) that will be the children of the block. In the next section we'll see how to solve this problem.

Implementing a scope stack
In order to make sure that a PAST::Block node is created before any statements are parsed (and their parse actions are executed -- these might need to enter symbols in the block's symbol table), we add a few extra parse actions. Let's take a look at them.

rule TOP {
    {*}                              #= open
    <statement>*
    [ $ || <.panic: syntax error> ]
    {*}                              #= close
}

We now have two parse actions for TOP, which are differentiated by an additional key parameter. The first parse action is executed before any input is parsed, which is particularly suitable for any initialization actions you might need. The second action (which was already there) is executed after the whole input string is parsed. Now we can create a PAST::Block node before any statements are parsed, so that when we need the current block, it's there (somewhere, later we'll see where exactly). Let's take a look at the parse action for TOP.

method TOP($/, $key) {
   our $?BLOCK;
   our @?BLOCK;

   if $key eq 'open' {
      $?BLOCK := PAST::Block.new( :blocktype('declaration'),
                                  :node($/) );
      @?BLOCK.unshift($?BLOCK);
   }
   else { # key is 'close'
      my $past := @?BLOCK.shift();

      for $<statement> {
         $past.push( $( $_ ) );
      }
      make $past;
   }
}

Let's see what's happening here. When the parse action is invoked for the first time (when $key equals "open"), a new PAST::Block node is created and assigned to a strange-looking (if you don't know Perl, like me. Oh wait, this is Perl. Never mind..) variable called $?BLOCK. This variable is declared as "our", which means that it is a package variable. This means that the variable is shared by all methods in the same package (or class), and, equally important, the variable is still around after the parse action is done. Please refer to the Perl 6 specification for more semantics on "our". The variable $?BLOCK holds the current block.
After that, this block is unshifted onto another funny-looking variable, called @?BLOCK. This variable has a "@" sigil, meaning this is an array. The unshift method puts its argument on the front of the list. In a sense, you could think of the front of this list as the top of a stack. Later we'll see why this stack is necessary.
This @?BLOCK variable is also declared with "our", meaning it's also package-scoped. However, as we call a method on this variable, it should have been already created; otherwise you'd invoke the method on an undefined ("Undef") variable. So, this variable should have been created before the parsing starts. We can do this in the compiler's main program, squaak.pir.
Before doing so, let's take a quick look at the "else" part of the parse action for TOP, which is executed after the whole input string is parsed. The PAST::Block node is retrieved from @?BLOCK, which makes sense, as it was created in the first part of the method and unshifted on @?BLOCK. Now this node can be used as the final result object of TOP. So, now we've seen how to use the scope stack, let's have a look at its implementation.

A List Class
We'll implement the scope stack as a ResizablePMCArray object. This is a built-in PMC type. However, this built-in PMC does not have any methods; in PIR it can only be used as an operand of the built-in shift and unshift instructions. In order to allow us to write this as method calls, we create a new subclass of ResizablePMCArray. The code below creates the new class and defines the methods we need.

 1 .namespace
 2 .sub 'initlist' :anon :init :load
 3   subclass $P0, 'ResizablePMCArray', 'List'
 4   new $P1, 'List'
 5   set_hll_global ['Squaak';'Grammar';'Actions'], '@?BLOCK', $P1
 6 .end

 7 .namespace ['List']

 8 .sub 'unshift' :method
 9   .param pmc obj
10   unshift self, obj
11 .end

12 .sub 'shift' :method
13   shift $P0, self
14   .return ($P0)
15 .end

Well, here you have it: part of the small amount of PIR code you need to write for the Squaak compiler (there's some more for some built-in subroutines, more on that later). Let's discuss this code snippet in more detail (if you know PIR, you could skip this section).
Line 1 resets the namespace to the root namespace in Parrot, so that the sub 'initlist' is stored in that namespace. The sub 'initlist' defined in lines 2-6 has some flags: :anon means that the sub is not stored by name in the namespace, implying it cannot be looked up by name. The :init flag means that the sub is executed before the main program (the "main" sub) is executed. The :load flag makes sure that the sub is executed if this file was compiled and loaded by another file through the load_bytecode instruction. If you don't understand this, no worries. You can forget about it now. In any case, we know for sure there's a List class when we need it, because the class creation is done before running the actual compiler code.
Line 3 creates a new subclass of ResizablePMCArray, called "List". This results in a new class object, which is left in register $P0, but it's not used after that.
Line 4 creates a new List object, and stores it in register $P1. Line 5, stores this List object by name of "@?BLOCK" (that name should ring a bell now...) in the namespace of the Actions class. The semicolons in between the several key strings indicate nested namespaces. So, lines 4 and 5 are important, because the create the @?BLOCK variable and store it in a place that can be accessed from the action methods in the Actions class.
Lines 7-11 define the unshift method, which is a method in the "List" namespace. This means that it can be invoked as a method on a List object. As the sub is marked with the :method flag, the sub has an implicit first parameter called "self", which refers to the invocant object. The unshift method invokes Parrot's unshift instruction on self, passing the obj argument as the second operand. So, obj is unshifted onto self, which is the List object itself.
Finally, lines 12-15 define the "shift" method, which does the opposite of "unshift", removing the first element and returning it to its caller.

Storing Symbols
Now, we set up the necessary infrastructure to store the current scope block, and we created a datastructure that acts as a scope stack, which we will need later. We'll now go back to the parse action for variable_declaration, because we didn't enter the declared variable into the current block's symbol table yet. We'll see how to do that now.
First, we need to make the current block accessible from the method variable_declaration. We've already seen how to do that, using the "our" keyword. It doesn't really matter where in the action method we enter the symbol's name into the symbol table, but let's do it at the end, after the initialization stuff. Naturally, we're only going to enter the symbol if it's not there already; duplicate variable declarations (in the same scope) should result in an error message (using the panic method of the match object).
The code to be added to the method variable_declaration looks then like this:

method variable_declaration($/) {
    our $?BLOCK;

    # get the PAST node for identifier

    # set the scope and declaration flag

    # do the initialization stuff

    # cache the name into a local variable
    my $name := $past.name();

    if $?BLOCK.symbol( $name ) {
      # symbol is already present
      $/.panic("Error: symbol " ~ $name
               ~ " was already defined.\n");
    }
    else {
      $?BLOCK.symbol( $name, :scope('lexical') );
    }

    make $past;
}

What's Next?
With this code in place, variable declarations are handled correctly. However, we didn't update the parse action for identifier, which creates the PAST::Var node and sets its scope; currently all identifiers' scope is set to 'package' (which means it's a global variable). As we already covered a lot of material in this episode, we'll leave this for the next episode. In the next episode, we'll also cover subroutines, which is another important aspect of any programming language. Hope to catch you later!

Exercises

1. In this episode, we changed the action method for the TOP rule; it is now invoked twice, once at the beginning of the parse, once at the end of the parse. The block rule, which defines a block to be a series of statements, represents a new scope. This rule is used in for instance if-statement (the then-part and else-part), while-statement (the loop body) and others. Update the parse action for block so it is invoked twice; once before parsing the statements, during which a new PAST::Block is created and stored onto the scope stack, and once after parsing the statements, during which this PAST node is set as the result object. Make sure $?BLOCK is always pointing to the current block. In order to do this exercise correctly, you should understand well what the shift and unshift methods do, and why we didn't implement methods to push and pop, which are more appropriate words in the context of a (scope) stack.
   

License
The source code in this tutorial has been released by the author into the public domain. Where this is not possible by law, the author grants license to use this file for any reason without any rights reserved, and with no warranty express or implied or fitness for a particular purpose.