Parrot Virtual Machine/Squaak Tutorial/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

edit

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?

edit

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

edit

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{{typo help inline|reason=similar to cooner|date=September 2022}}
    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".

Solution

edit

If you don't feel like doing exercises or just want to see what it looks like without doing any trouble, here's what it looks like (this is life generation 9).

    -----------------------------------------
    -----------------------------------------
    -----------------------------------------
    -----O-----------------------------------
    ----OO-----------------------------------
    --OO--O----------------------------------
    -----OO----------------------------------
    --OOOOO------------------OOO-------------
    ------------------------O---O------------
    -----------------------O-----O-----------
    ----------------------O---O---O----------
    ----------------------O--O-O--O----------
    ----------------------O---O---O----------
    -----------------------O-----O-----------
    ------------------------O---O------------
    -------------------------OOO-------------
    -----------------------------------------
    -----------------------------------------
    -----------------------------------------
    -----------------------------------------
    -----------------------------------------

    Life - generation: 9

But really, it doesn't compare to seeing this program run on Parrot :-)

Exercises

edit

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

edit

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!