Thursday, April 3, 2008

Solutions to the Exercises in Episode 5

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.

Keeping the Current block up to date
Sometimes we need to access the current block's symbol table. In order to be able to do so, we need a reference to the "current block". We do this by declaring a package variable called "$?BLOCK", declared with "our" (as opposed with "my"). This variable will always point to the "current" block. As blocks can nest, we use a "stack", on which newly created blocks are stored.
Whenever a new block is created, we assign this to $?BLOCK, and store it onto the stack, so that the next time a new block is created, the "old" current block isn't lost. Whenever a scope is closed, we pop off the current block from the stack, and restore the previous "current" block.

Why unshift/shift and not push/pop?
When we're talking about stacks, it would seem logical to talk about stack operations such as "push" and "pop". Instead, we use the operations "unshift" and "shift". If you're not a Perl programmer (such as myself), these names might not make sense. However, it's pretty easy. Instead of pushing a new object onto the "top" of the stack, you unshift objects onto this stack. Just see it as an old school bus, with only one entrance (at the front of the bus). Pushing a new person means taking the first free seat when entering, while unshifting a new person means everybody moves (shifts) one place to the back, so the new person can sit in the front seat. You might think this is not as efficient (more stuff is moved around), but that's not really true (actually: I guess (and certainly hope) the shift and unshift operations are implemented more effectively than the bus metaphor; I don't know how it is implemented).

So why unshift/shift, and not push/pop? When restoring the previous "current block", we need to know exactly where it is (what position). It would be nice to be able to always refer to the "first passenger on the bus", instead of the last person. We know how to reference the first passenger (it's on seat no. 0 (it was designed by an IT guy)); we don't really know what is the seat no. of the last person: s/he might sit in the middle, or at the back.

I hope it's clear what I mean here... otherwise, have a look at the code, and try to figure out what's happening:
method block($/, $key) {  
our $?BLOCK;
our @?BLOCK;
if $key eq 'open' {

$?BLOCK :=

:node($/) );
else {
my $past := @?BLOCK.shift();
$?BLOCK := @?BLOCK[0];

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


Joeri said...

Possibly a silly question, but why do we need $?BLOCK if it is always equivalent to @?BLOCK[0]?
Alternatively, why do we store $?BLOCK on the stack?

Why not do
$?BLOCK :=;

It is not even necessary to change the TOP procedure to reflect this different approach, although this would spare an additional unshift

Joeri said...

You would also need to change the second part of the function of course:
my $past := $?BLOCK;
$?BLOCK := @?BLOCK.shift();

caradoc said...

Important point: If you use this you do not have to use shift/unshift anymore, but instead you could use push and pop (which would obviously require different PIR code, but that should be easy enough).

caradoc said...

BTW: caradoc = joeri
I just changed my screen name and apparently that is not change is not reflected on older posts