doc/rpntutorial.txt

   1 RPNTUTORIAL(1)                      rrdtool                     RPNTUTORIAL(1)
   2
   3
   4
   5 N\bNA\bAM\bME\bE
   6        rpntutorial - Reading RRDtool RPN Expressions by Steve Rader
   7
   8 D\bDE\bES\bSC\bCR\bRI\bIP\bPT\bTI\bIO\bON\bN
   9        This tutorial should help you get to grips with RRDtool RPN expressions
  10        as seen in CDEF arguments of RRDtool graph.
  11
  12 R\bRe\bea\bad\bdi\bin\bng\bg C\bCo\bom\bmp\bpa\bar\bri\bis\bso\bon\bn O\bOp\bpe\ber\bra\bat\bto\bor\brs\bs
  13        The LT, LE, GT, GE and EQ RPN logic operators are not as tricky as they
  14        appear.  These operators act on the two values on the stack preceding
  15        them (to the left).  Read these two values on the stack from left to
  16        right inserting the operator in the middle.  If the resulting statement
  17        is true, then replace the three values from the stack with "1".  If the
  18        statement if false, replace the three values with "0".
  19
  20        For example, think about "2,1,GT".  This RPN expression could be read
  21        as "is two greater than one?"  The answer to that question is "true".
  22        So the three values should be replaced with "1".  Thus the RPN
  23        expression 2,1,GT evaluates to 1.
  24
  25        Now consider "2,1,LE".  This RPN expression could be read as "is two
  26        less than or equal to one?".   The natural response is "no" and thus
  27        the RPN expression 2,1,LE evaluates to 0.
  28
  29 R\bRe\bea\bad\bdi\bin\bng\bg t\bth\bhe\be I\bIF\bF O\bOp\bpe\ber\bra\bat\bto\bor\br
  30        The IF RPN logic operator can be straightforward also.  The key to
  31        reading IF operators is to understand that the condition part of the
  32        traditional "if X than Y else Z" notation has *already* been evaluated.
  33        So the IF operator acts on only one value on the stack: the third value
  34        to the left of the IF value.  The second value to the left of the IF
  35        corresponds to the true ("Y") branch.  And the first value to the left
  36        of the IF corresponds to the false ("Z") branch.  Read the RPN
  37        expression "X,Y,Z,IF" from left to right like so: "if X then Y else Z".
  38
  39        For example, consider "1,10,100,IF".  It looks bizarre to me.  But when
  40        I read "if 1 then 10 else 100" it's crystal clear: 1 is true so the
  41        answer is 10.  Note that only zero is false; all other values are true.
  42        "2,20,200,IF" ("if 2 then 20 else 200") evaluates to 20.  And
  43        "0,1,2,IF" ("if 0 then 1 else 2) evaluates to 2.
  44
  45        Notice that none of the above examples really simulate the whole "if X
  46        then Y else Z" statement.  This is because computer programmers read
  47        this statement as "if Some Condition then Y else Z".  So it's important
  48        to be able to read IF operators along with the LT, LE, GT, GE and EQ
  49        operators.
  50
  51 S\bSo\bom\bme\be E\bEx\bxa\bam\bmp\bpl\ble\bes\bs
  52        While compound expressions can look overly complex, they can be
  53        considered elegantly simple.  To quickly comprehend RPN expressions,
  54        you must know the algorithm for evaluating RPN expressions: iterate
  55        searches from the left to the right looking for an operator.  When it's
  56        found, apply that operator by popping the operator and some number of
  57        values (and by definition, not operators) off the stack.
  58
  59        For example, the stack "1,2,3,+,+" gets "2,3,+" evaluated (as "2+3")
  60        during the first iteration and is replaced by 5.  This results in the
  61        stack "1,5,+".  Finally, "1,5,+" is evaluated resulting in the answer
  62        6.  For convenience, it's useful to write this set of operations as:
  63
  64         1) 1,2,3,+,+    eval is 2,3,+ = 5    result is 1,5,+
  65         2) 1,5,+        eval is 1,5,+ = 6    result is 6
  66         3) 6
  67
  68        Let's use that notation to conveniently solve some complex RPN
  69        expressions with multiple logic operators:
  70
  71         1) 20,10,GT,10,20,IF  eval is 20,10,GT = 1     result is 1,10,20,IF
  72
  73        read the eval as pop "20 is greater than 10" so push 1
  74
  75         2) 1,10,20,IF         eval is 1,10,20,IF = 10  result is 10
  76
  77        read pop "if 1 then 10 else 20" so push 10.  Only 10 is left so 10 is
  78        the answer.
  79
  80        Let's read a complex RPN expression that also has the traditional
  81        multiplication operator:
  82
  83         1) 128,8,*,7000,GT,7000,128,8,*,IF  eval 128,8,*       result is 1024
  84         2) 1024   ,7000,GT,7000,128,8,*,IF  eval 1024,7000,GT  result is 0
  85         3) 0,              7000,128,8,*,IF  eval 128,8,*       result is 1024
  86         4) 0,              7000,1024,   IF                     result is 1024
  87
  88        Now let's go back to the first example of multiple logic operators, but
  89        replace the value 20 with the variable "input":
  90
  91         1) input,10,GT,10,input,IF  eval is input,10,GT  ( lets call this A )
  92
  93        Read eval as "if input > 10 then true" and replace "input,10,GT" with
  94        "A":
  95
  96         2) A,10,input,IF            eval is A,10,input,IF
  97
  98        read "if A then 10 else input".  Now replace A with it's verbose
  99        description again and--voila!--you have an easily readable description
 100        of the expression:
 101
 102         if input > 10 then 10 else input
 103
 104        Finally, let's go back to the first most complex example and replace
 105        the value 128 with "input":
 106
 107         1) input,8,*,7000,GT,7000,input,8,*,IF  eval input,8,*     result is A
 108
 109        where A is "input * 8"
 110
 111         2) A,7000,GT,7000,input,8,*,IF          eval is A,7000,GT  result is B
 112
 113        where B is "if ((input * 8) > 7000) then true"
 114
 115         3) B,7000,input,8,*,IF                  eval is input,8,*  result is C
 116
 117        where C is "input * 8"
 118
 119         4) B,7000,C,IF
 120
 121        At last we have a readable decoding of the complex RPN expression with
 122        a variable:
 123
 124         if ((input * 8) > 7000) then 7000 else (input * 8)
 125
 126 E\bEx\bxe\ber\brc\bci\bis\bse\bes\bs
 127        Exercise 1:
 128
 129        Compute "3,2,*,1,+ and "3,2,1,+,*" by hand.  Rewrite them in
 130        traditional notation.  Explain why they have different answers.
 131
 132        Answer 1:
 133
 134            3*2+1 = 7 and 3*(2+1) = 9.  These expressions have
 135            different answers because the altering of the plus and
 136            times operators alter the order of their evaluation.
 137
 138        Exercise 2:
 139
 140        One may be tempted to shorten the expression
 141
 142         input,8,*,56000,GT,56000,input,*,8,IF
 143
 144        by removing the redundant use of "input,8,*" like so:
 145
 146         input,56000,GT,56000,input,IF,8,*
 147
 148        Use traditional notation to show these expressions are not the same.
 149        Write an expression that's equivalent to the first expression, but uses
 150        the LE and DIV operators.
 151
 152        Answer 2:
 153
 154            if (input <= 56000/8 ) { input*8 } else { 56000 }
 155            input,56000,8,DIV,LE,input,8,*,56000,IF
 156
 157        Exercise 3:
 158
 159        Briefly explain why traditional mathematic notation requires the use of
 160        parentheses.  Explain why RPN notation does not require the use of
 161        parentheses.
 162
 163        Answer 3:
 164
 165            Traditional mathematic expressions are evaluated by
 166            doing multiplication and division first, then addition and
 167            subtraction.  Parentheses are used to force the evaluation of
 168            addition before multiplication (etc).  RPN does not require
 169            parentheses because the ordering of objects on the stack
 170            can force the evaluation of addition before multiplication.
 171
 172        Exercise 4:
 173
 174        Explain why it was desirable for the RRDtool developers to implement
 175        RPN notation instead of traditional mathematical notation.
 176
 177        Answer 4:
 178
 179            The algorithm that implements traditional mathematical
 180            notation is more complex then algorithm used for RPN.
 181            So implementing RPN allowed Tobias Oetiker to write less
 182            code!  (The code is also less complex and therefore less
 183            likely to have bugs.)
 184
 185 A\bAU\bUT\bTH\bHO\bOR\bR
 186        Steve Rader <rader@wiscnet.net>
 187
 188
 189
 190 1.4.8                             2013-05-23                    RPNTUTORIAL(1)