Implementing a stack-based language in Raku

I assume there is no need to tell what a stack is, and a stack-based programming is something that uses the stack to perform all the operation. The program flow in such a language resembles a reversed Polish notation, when you first list the operands, and then the operation:

40 2 +

There are a number of stack-based languages, Factor and PostScript being the examples of them. Factor was the topic of one of the days in my recent Advent Calendar.

Now, I’d like to try how Raku can help in building a simple stack-oriented language.

Test cases

This is the goal for today. The interpreter should be able to correctly parse and execute the following test programs:

Printing a test string:

"Hello, World!" print
"World!" "Hello, " print print

Making arithmetic operations:

20 22 + print

Creating and using variables:

42 "x" var
x print

10 x - print
10 "y" var
x y * print

And a bit more complicated case with both maths and variables:

1 2 3 + + "sum" var
sum print

Raku Grammar

Having the test cases prepared, we can define the grammar.

grammar StackyLang {
    rule TOP {
        <thing>+
    }

    rule thing {
        | <literal>
        | <word>        
    }

    rule literal {
        | <string>
        | <number>
    }

    token string {
        '"' <text> '"'
    }

    token text {
        <-["]>*
    }

    token number {
        \d+
    }

    token word {
        | <alpha>\w* 
        | '+' | '-' | '*' | '/'
    }
}

A correct program consists of literals and words, where a literal is a double-quoted string or an integer number, and a word is either an identifier starting with a letter <alpha>\w* or one of the four arithmetic symbols.

Processing

Obviously, the implementation needs a stack. From the test cases, you can see that we also need a storage for variables. Both of these items can be presented by global variables for simplicity.

my @stack;
my %variable;

And we also need to implement the functions working with the stack in response to different word commands in the program.

my %function = 
    print => sub {
        say @stack.pop
    },

    '+' => sub {
        @stack.push(@stack.pop + @stack.pop)
    },
    '-' => sub {
        @stack.push(@stack.pop - @stack.pop)
    },
    '*' => sub {
        @stack.push(@stack.pop * @stack.pop)
    },
    '/' => sub {        
        @stack.push(@stack.pop / @stack.pop)
    },

    var => sub {
        %variable{@stack.pop} = @stack.pop
    },
;

Acting

Finally, add the actions to the grammar so that they are triggered when the grammar parses the next bit of the program.

When we see a literal, i. e., either a string or a number, the only action is to put them on top of the stack:

rule literal {
    | <string> {@stack.push: ~$<string><text>}
    | <number> {@stack.push: +$<number>}
}

When we match a word, we have to execute one of the earlier defined functions.

Notice how the language deals with variables. To create it, you have to first put the value and the string with the variable’s name on the stack, and then create a variable via the var word. When the variable is created, it becomes one of the possible words, and thus it can be used without quotes.

token word {
    [
        | <alpha>\w*
        | '+' | '-' | '*' | '/'
    ]
    {
        if %variable{~$/} {
            @stack.push(%variable{~$/});
        }
        elsif %function{~$/} {
            %function{~$/}();
        }
        else {
            say "ERROR: Unknown word '$/'";
            exit;
        }
    }
}

Running

That’s it. Let us read the text of the program and parse it with the grammar:

my $path = @*ARGS[0];
if ($path) {
    my $program = $path.IO.slurp;
    StackyLang.parse($program);
}

The parse method will also execute the actions. The program with the test cases shown earlier generates the following output:

$ raku stacky.raku test.stacky 
Hello, World!
Hello, 
World!
42
42
32
420
6

That’s all for now. You can find the source code and the test program on GitHub.