1RPNTUTORIAL(1)                      rrdtool                     RPNTUTORIAL(1)
2
3
4

NAME

6       rpntutorial - Reading RRDtool RPN Expressions by Steve Rader
7

DESCRIPTION

9       This tutorial should help you get to grips with RRDtool RPN expressions
10       as seen in CDEF arguments of RRDtool graph.
11

Reading Comparison Operators

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

Reading the IF Operator

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

Some Examples

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

Exercises

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

AUTHOR

186       Steve Rader <rader@wiscnet.net>
187
188
189
1901.4.8                             2013-05-23                    RPNTUTORIAL(1)
Impressum