in reply to Graphing SQLite's VDBE

bsb:

I really like your conversion from the stack-based code to the graphical format. One suggestion though: You don't show the stack-based code for the graph shown, so it's not as easy as one would like to see how they tie together.

As far as code pointers go, I'll leave that to monks better-versed in Perl than I.

Anyway, on to your other question: Assuming that by "conventional code" you mean a more algebraic form, then here's my take on it:

The most trivial form is to build it by parenthesizing every expression as you encounter it. Suppose, for example, you have the following bit of code:

[1] push 3
[2] push 5
[3] add
[4] push 7
[5] push 9
[6] add
[7] mul
[8] print

[download]
We'd build an algebraic expression with something like this: 
#!/usr/bin/perl -w
use strict;
use warnings;

my @stack = ();

while (<DATA>) {
        chomp;

        print "TOS='" . (@stack ? $stack[$#stack] : '-nil-') . "', "
        .       "stmt = '" . $_ . "'\n";

        my ($operator, $operand) = split;
        if ($operator eq 'push') {
                push @stack, $operand;
        }
        elsif ($operator eq 'print') {
                print "out: '" . (pop @stack) . "'\n";
        }
        elsif ($operator eq 'add') {
                my $lhs = pop @stack;
                my $rhs = pop @stack;
                push @stack, '(' . $lhs . ' + ' . $rhs . ')';
        }
        elsif ($operator eq 'mul') {
                my $lhs = pop @stack;
                my $rhs = pop @stack;
                push @stack, '(' . $lhs . '*' . $rhs . ') ';
        }
}
__DATA__
push 3
push 5
add
push 7
push 9
add
mul
print

[download]
Which gives us the output:

root@swill ~/PerlMonks
$ ./stack_to_infix.pl
TOS='-nil-', stmt = 'push 3'
TOS='3', stmt = 'push 5'
TOS='5', stmt = 'add'
TOS='(5 + 3)', stmt = 'push 7'
TOS='7', stmt = 'push 9'
TOS='9', stmt = 'add'
TOS='(9 + 7)', stmt = 'mul'
TOS='((9 + 7)*(5 + 3)) ', stmt = 'print'
out: '((9 + 7)*(5 + 3)) '

root@swill ~/PerlMonks
$

[download]
Now this trivial technique will do it correctly, but will give you too many parenthesis. With a bit more work, you can get rid of the extra parenthesis to get a minimal expression. Here's how to do it: Instead of storing a single string on the stack, keep a pair: The string and the precedence of the operator. Now, when you're working on an operator, check the precedence of the items you pop from the stack with the precedence of the operator you're processing now. If any operator has a lower precedence, wrap it in parenthesis.

--roboticus

Replies are listed 'Best First'.
Re: Convert stack-based code to "conventional" (was Re: Graphing SQLite's VDBE)
by roboticus (Chancellor) on Jan 24, 2007 at 13:01 UTC
    bsb:

    OK ... I've toyed around with the code and did a version with the extra parenthesis removal. Here ya go:

    #!/usr/bin/perl -w
use strict;
use warnings;

my @stack = ();

sub binop {
        my $op = shift;
        my $prec = shift;

        my $lh = pop @stack;
        my ($lhop, $lhprec) = ($$lh[0], $$lh[1]);

        my $rh = pop @stack;
        my ($rhop, $rhprec) = ($$rh[0], $$rh[1]);

        # Wrap operand(s) with lower precedence
        $lhop = '(' . $lhop . ')' if $prec > $lhprec;
        $rhop = '(' . $rhop . ')' if $prec > $rhprec;

        push @stack, [ $lhop . $op . $rhop, $prec ];
}

while (<DATA>) {
        chomp;

        print "TOS='" . (@stack ? $stack[$#stack][0] : '-nil-') . "' "
        .       "stmt = '" . $_ . "'\n";

        my ($operator, $operand) = split;
        if ($operator eq 'push') {
                # A constant is atomic, so it has high precedence so
                # we don't wrap it
                push @stack, [$operand, 999];
        }
        elsif ($operator eq 'print') {
                my $op = pop @stack;
                my ($operand, $prec) = ($$op[0], $$op[1]);
                print "out: '" . $operand . "'\n";
        }
        elsif ($operator eq 'add') {
                binop '+', 1;
        }
        elsif ($operator eq 'mul') {
                binop '*', 2;
        }
}
__DATA__
push 3
push 5
add
push 7
push 9
add
mul
print

    [download]
    Which gives us: 
    root@swill ~/PerlMonks
$ ./stack_to_infix2.pl
TOS='-nil-' stmt = 'push 3'
TOS='3' stmt = 'push 5'
TOS='5' stmt = 'add'
TOS='5+3' stmt = 'push 7'
TOS='7' stmt = 'push 9'
TOS='9' stmt = 'add'
TOS='9+7' stmt = 'mul'
TOS='(9+7)*(5+3)' stmt = 'print'
out: '(9+7)*(5+3)'

root@swill ~/PerlMonks
$

    [download]
    --roboticus

    P.S. I don't like my code for getting arguments off the stack, but all my attempts at simplifying it failed miserably. I'm sure it's something simple, but I haven't figured it out. What's a better way to do the following? (Or is my problem a bit earlier and I'm pushing the wrong thing on the stack?)

        my $op = pop @stack;
    my ($operand, $prec) = ($$op[0], $$op[1]);

    [download]
[reply]
[d/l]
[select]
      How about

      my ($operand, $prec) =
   map { $_->[0], $_->[1] }
   pop @stack;

      [download]

      It seems to do what you want.

      Cheers,

      JohnGG

[reply]
[d/l]
      OK ... now for a quick round of golf. Here's a version that's a bit tighter and easier to expand: 
      #!/usr/bin/perl -w
use strict;
use warnings;

my @stack = ();

sub binop {
        my ($op,   $prec)   = @_;
        my ($rhop, $rhprec) = @{pop @stack};
        my ($lhop, $lhprec) = @{pop @stack};

        # Wrap operand(s) with lower precedence
        $lhop = '(' . $lhop . ')' if $prec > $lhprec;
        $rhop = '(' . $rhop . ')' if $prec > $rhprec;

        push @stack, [ $lhop . $op . $rhop, $prec ];
}

my %handlers = (
        'push'  => sub { push @stack, [shift, 999]; },
        'print' => sub { print "out: '" . ${@{pop @stack}}[0] . "'\n";
+ },
        'add'   => sub { binop '+', 1; },
        'mul'   => sub { binop '*', 2; }
);

while (<DATA>) {
        chomp;

        print "TOS='" . (@stack ? $stack[$#stack][0] : '-nil-') . "' "
        .       "stmt = '" . $_ . "'\n";

        my ($operator, $operand) = split;
        if ($handlers{$operator}) {
                $handlers{$operator}->($operand);
        }
        else {
                print "Unknown operator: '$operator' for line '$_'\n";
        }
}
__DATA__
push 3
push 5
add
push apples
add
push oranges
push 9
push bananas
push peels
mul
add
add
mul
print

      [download]
      Which gives us: 
      TOS='-nil-' stmt = 'push 3'
TOS='3' stmt = 'push 5'
TOS='5' stmt = 'add'
TOS='3+5' stmt = 'push apples'
TOS='apples' stmt = 'add'
TOS='3+5+apples' stmt = 'push oranges'
TOS='oranges' stmt = 'push 9'
TOS='9' stmt = 'push bananas'
TOS='bananas' stmt = 'push peels'
TOS='peels' stmt = 'mul'
TOS='bananas*peels' stmt = 'add'
TOS='9+bananas*peels' stmt = 'add'
TOS='oranges+9+bananas*peels' stmt = 'mul'
TOS='(3+5+apples)*(oranges+9+bananas*peels)' stmt = 'print'
out: '(3+5+apples)*(oranges+9+bananas*peels)'

      [download]
      --roboticus
[reply]
[d/l]
[select]
Re: Convert stack-based code to "conventional" (was Re: Graphing SQLite's VDBE)
by bsb (Priest) on Jan 25, 2007 at 07:11 UTC
    You don't show the stack-based code for the graph shown, so it's not as easy as one would like to see how they tie together
    Actually, most of the operations do something to the stack, sometimes conditionally, and the textual description is the only source of information. I suppose that I could add some notation like "-2" for something that pops two items. I'll think about your suggestion.

    Thanks for the conversion code, I thought that I'd be bumping into the Halting Problem but maybe your technique would work for most or even all of the VDBE code encountered in practice. There are loops, conditionals and off-stack state used by the opcodes so I think the Halting Problem is lurking there somewhere. 

    create table tape (cur_state, scanned, write, move, next_state);

    [download]
[reply]
[d/l]

In Section Cool Uses for Perl