B::DeparseTree for Better Location Reporting

Where am I now — Really?

B::DeparseTree for Better Location Reporting

(enter "s" to see presenter text for slides)

A Perl Error


Use of uninitialized value $prev[0] in array element at YAPC2018/prev.pl line 5.

where line 5 is:


sub boom { $prev[$prev[$_[1]]]; }

Which prev were we talking about?

More errors where line numbers are not good enough

Use of uninitialized value $_ in numeric gt (>) at YAPC2018/map.pl line 4

where line 5 is:


map { $_ > 1 ? 1 : $_ } @_ if $_;

and finally...


Useless use of private variable in void context at YAPC2018/eval.pl line 8

where line 4 is...


eval { $code };

Laziness, Impatience, Hubris

“We will encourage you to develop the three great virtues of a programmer: laziness, impatience, and hubris.”

Laziness: The quality that makes you go to great effort to reduce overall energy expenditure.

Impatience: The anger you feel when the computer is being lazy.

Laziness is the first of Larry Wall's great virtues of a programmer.

Laziness: The quality that makes you go to great effort to reduce overall energy expenditure.

Let's face it. Writing something as big and complex as Perl even in its first inceptions is a lot of work. Writing a programming language is probably not something that most of us have the chops to do ourselves. But Larry undertook that so he would not have to think about writing Unix pipes with awk, grep, cut, sed, and so on. In the long run, using Perl would save him and others a bit of work

So assuming you can someone like me to do the work to write this code, then Perl programs can spend less effort in figuring out where in the line you are when there's something wrong.

Now onto to the second virtue...[down]

Impatience: The anger you feel when the computer is being lazy.

At least for me this has been particularly irksome. The computer "knows" which divide or index is the problem: the information is available, not lost. It just needs to be instructed to tell you. [next]

Programmer to Computer

A programmer may write ...


$a / $b / $c

The Perl 5 interpreter sees (according to B::Concise)...

In order to solve this problem, we need to go into a little of the nitty-gritty of how Perl5 works. If you are familiar with compilers, this will look familiar.

In the Perl5 implementation, the code you write gets translated some thing called a B::OP tree, and running a Perl program then is simply walking the tree and performing various actions along the way. In short we say we "evaluate" the tree. If there are loops in the tree, some of the tree nodes may get executed repeatedly for each iteration of a loop.

So let's see the B::OP tree for this...[next]

Perl module B::Concise shows the Op tree, and it can can display an OP::Tree in a couple of different ways. I have chosen the tree-oriented way rather than a linear-sequence. So as a result you'll see numbers at the left which indicate the instruction sequence were it shown in the linear ordering. And on the extreme right, the number which is one more than the number on the extreme left, if that exists.

So note that the first instruction, instruction 8, listed is in fact the last one in the sequence. Interesting. And then there is a skip to from the last instruction to the first one; then the second instruction and another skip to an instruction near the end. Those of you who are astute might see the pattern here. We'll come back to this later.

I have simplified the instructions a little by removing instructions that have been replaced by some other instruction or "optimized" away.

Instruction 2, the nextstate instruction, isn't an instruction at all. It simply marks a statement boundary. It contains values for a file name and line number.

When you are tracing instructions such as inside a debugger, that instruction is called dbstate instead. In fact that's how the Perl interpreter knows whether to pause and call the debugger or not.

All the instructions, in instruction order, after a nextstate or dbstate up to the next nextstate/dbstate are associated the last nextstate/dbstate instruction. In particular, all of the instructions from instruction 2 onto 8 are associated with line 1 of div.pl.

And now you should see what the problem is. There are two divide B::OPs in that sequence of instructions, and what we want to do now is say a little more about each, other than they come from the same line.

To get a sense of how to do this, let's see how this is very similar to human-language translation.

[next]


8  <@> leave[1 ref] vKP/REFC ->(end)
1     <0> enter ->2
2     <;> nextstate(main 1 div.pl:1) v:{ ->3
7     <2> divide[t5] vK/2 ->8
5        <2> divide[t3] sK/2 ->6
3              <#> gvsv[*a] s ->4
4              <#> gvsv[*b] s ->5
6           <#> gvsv[*c] s ->7

Gaelic to English

Gaelic: Tha mi ag ithe an taigeis

English: I am eating the haggis

Gaelic: Tha (= am/are/is) mi (= I/me) ag ithe an taigeis

English: I am eating the haggis

In a literal translation the word order is jumbled a bit as it was in Perl to Optree.

There is also one other feature that is similar to what we saw that I'll mention. Notice that the Gaelic uses a couple of generic words like "Tha" for either "am", "are", "is", and "mi" for "I" or "me". In the English we need to choose the right word among the several possibilities. In the previous Perl example, we used $a, $b, and $c, and these variables could be either a my variable, an our variable, a local variable, or a global variable. In the OPtree OP node this has been made clear that the dollar variables are not my variables

So how do we make sense of this in a more rigorous way? The first Perl listing gave a clue. So does this haggis sentence translation.

But let me tease this out just a little bit longer by showing that in human language you've already seen something similar to the nextstate position mark followed by a bunch of instructions. I am referring to a side-by-side translation of poetry.... [next]

Side-by-side Scots-English Translation

1: Fair fa' your honest, sonsie face,
2: Great chieftain o the puddin'-race!

1: Good luck to you and your honest, plump face,
2: Great chieftain of the sausage race!

In the above, you can assume that the entire first line of the Scots is roughly like the first line of the English, and the second line of the Scots is like the second line of the English.

Since Scots and English are so close, you can do a word-for-word translation for the most part.

In this particular example words at the beginning of one sentence match words at the beginning of the other, and those at the end of Scots match those at the end of English.

And I've used this heuristic in debugging my Perl and C programs where I guess that if the address is near the preceding nextstate, it is probably towards the beginning of the source code.

But then things can get funky, because there are these little things like "Fair fa" becoming sort of equivalent to "Good luck to you and". Also, as we saw, words can get jumbled around. So let's looks at a side-by-side translation of simple Perl and its optree instructions. [next]

Side-by-side Perl translation


  $x = 1;  # line 1
  $y = 2;  # line 2


1  <0> enter
2  <;> nextstate(main 1 assign.pl:1) v:{
3  <$> const[IV 1] s
4  <#> gvsv[*x] sqnnpp
5  <2> sassign vKS/2

6  <;> nextstate(main 1 assign.pl:2) v:{
7  <$> const[IV 2] s
8  <#> gvsv[*y] s
9  <2> sassign vKS/2
a  <@> leave[1 ref] vKP/REFC

Above I have written the instructions in instruction order rather than as a tree.

Although it is pretty much the same as the side-by-side translation, there is one one caveat...

Let's ignore the additional nextstate instruction which is more like a meta-instruction than an instruction that does a computation.

Instead of the order variable, =, constant, we have find in Perl Ops constant, variable, sassign. In general, the operator like sassign comes last. So in contrast the Gaelic-English translation, the first instruction of the Optree translation does not match first token of the Perl code. The same can be said of the last token.

This kind of operator-last arrangement is called Polish-Prefix notation, used also in HP calculators of the days of yore, and the programming languages Forth and Postscript. A recent language that uses Polish-Prefix is the Bitcoin Script Language.

The advantage of listing instructions this way is simple: by the time you get to the operation to be performed, assignment, all of the data is available on an execution stack.

Now that we have explored how this resembles a human-language translation problem, rather than a programmer-versus-computer problem, we can ask: how would we get more detail in the correspondences between the two translations?

In human language translation you would diagram a grammar on top of the sentence and then match corresponding grammar parts between the two translations.

Perl already provides this tree structure which pretty much follows its source-code grammar. [next]

Parse to Text

Here is a diagram of the tree we saw before. It is not an "abstract" syntax tree, but it is a syntax tree.

Now we'll show how to reconstruct the source text from this tree. This is in fact how the Perl module B::Deparse works. B::Deparse has been available in Perl for 20 years or so. B::DeparseTree is my extension to B::Deparse which saves additional information to pick out the fragments for a given B::Op instruction.

For those know how compilers work, this sort of thing should look familiar. It is called a "syntax-directed translation." Using the node type and information propagated through adjacent nodes, we can create a Perl source-code string that characterizes what the tree rooted at that node does.

I have written the instruction order near each node in the tree. However, we can think of that as a memory address as well. And then the game becomes, if I give you an instruction number or memory address what Perl source-code fragment does that represent?

Here we have only two node types: gvsv and divide. In B::Deparse the information obtained from a node's children are strings of Perl source-code fragments. Information passed down from above is an operator-precedence number that is used to determine whether to surround the final result in parentheses.

In B::DeparseTree we need to keep more information. We keep a hash of node addresses, so you can query information about any node in the tree. We also pass down the parent's address so that we can walk up the tree. This is useful so that we can give context around the point of interest.

Although this may not be needed in the future, right now, instead of passing back strings to a parent, we pass back our own kind of tree node structure which has richer information about the text fragment. This helps not only in debugging, but also it allows us to make more sophisticated decisions about how to format the code. For example, if the fragment is a block table with a large number of entries, that may change how we want to format a list parameter that might appear after the block in a grep expression. [next]

Perl fragments associated with B::OPs

In this diagram, I've given a Perl source-code translation for each node.

The way I got this was to apply rules for gvsv and divide to each of the nodes. I have kept the instruction numbers from the last slide to show that how, given an instruction number, we can report what Perl code is associated with it.

So if I am at instruction 3, the translation to Perl would be $a; if at instruction 4, the $b. At instruction 5 we get $a/$b. At instruction 7 we have $a/$b/$c. And with this you now can see how a program can tell you which divide you were working on.

Next I will give the Perl code which I used to create these strings. It doesn't take too much imagination to see what's going on: for gvsv you pick out the name of the variable that has a dollar sigil at the beginning. For divide take the string for the left child and right child but slap a "/" in between them.

I give some specific Perl code next, but before leaving this slide, let me just point out that the string for each node is created purely on information from the node's parent or children. In compiler terminology this is called "inherited" or "synthesized" attributes. [next]

`divide` rule


sub divide {
    my ($self, $op, $context) = @_;
    my $left = $self->deparse($op->first);
    my $right = $self->deparse($op->last);

    my $str =  $left . '/' . $right;
    return $self->maybe_parens($str, $context, 19)
}

This code is a simplification of what B::Deparse does. There isn't a rule for "divide" specifically, but instead for the B::OP's that "divide" is a part of. "divide" is a binary operator or BINOP.

There are other complications as well which I am not showing. The above gives you a sense of how this works. This code resembles the B::Deparse code: a string is built up over the course of executing the subroutine. Note that there is a fair bit of boilerplate in getting strings from the child nodes

The line at the bottom is interesting in that it makes use of information from the parent to decide whether or not to enclose the string in parentheses. If this were an addition operator but my parent was a multiplication operator, its context value would be higher than mine, 19. So I'd know that parentheses are need around the addition operation. [next]

`gvsv` rule


sub gvsv {
   my ($self, $op, $context) = @_;
   my $str = $self->gv_name($op);
   return $self->maybe_local($op, $str);
}

Simplifying the 100's of rule codes

Compare


my $str =  $left . '/' . $right;

with:


my $str =  sprintf("%s/%s", $left , $right);

Simplifying rule code - templating


our $PP_RULES = {
    divide => ("%p/%p", [[0, 19], [1, 19]]),
    ...
}

Lingering Problems: Translation

Fair fa' your honest..

Good luck to you and your honest...

If we are are reading "to" where are we in the Scots?


#1: my @prev = (undef, 0, 1);
    COP (0x7fee65ad8728) dbstate
    BINOP (0x7fee65ad8788) aassign [2]
        UNOP (0x7fee60d08198) null [157]
            OP (0x7fee60d08160) PUSHMARK  // What's this? ...
            OP (0x7fee60d08220) undef
            SVOP (0x7fee60d081e0) const  IV (0x7fee61806c88) 0
            SVOP (0x7fee60d08120) const  IV (0x7fee61806c10) 1
        UNOP (0x7fee60d080c0) null [157]
            OP (0x7fee65ad87d0) PUSHMARK  // and this?
            OP (0x7fee60d08258) padav [1] my @prev = (undef, 0, 1);


pushmark, pushmark B::OP=SCALAR(0x7fee6823fe78)
	at address 0x7fee60d08160:
my(@prev) = (undef, 0, 1)
             |

Lingering Problem: PC location in a call


foreach( my $x =0 ; $x < 1; $x++) {   # Line 1
  print_line();                       # Line 2
}
sub print_line {
  print "call from line " . [caller(0)]->[2] . "\n";
}

prints "call from line 1".

From StackOverflow

Devel::Trepan Deparse with Fibonacci

Links...

- fin

Where am I now — Really?

B::DeparseTree for Better Location Reporting

A Perl Error

More errors where line numbers are not good enough

Laziness, Impatience, Hubris

Programmer to Computer

Gaelic to English

Side-by-side Scots-English Translation

Side-by-side Perl translation

Parse to Text

Perl fragments associated with B::OPs

divide rule

gvsv rule

Simplifying the 100's of rule codes

Simplifying rule code - templating

Lingering Problems: Translation

Lingering Problem: PC location in a call

Devel::Trepan Deparse with Fibonacci

Links...

`divide` rule

`gvsv` rule