1RPNTUTORIAL(1) rrdtool RPNTUTORIAL(1)
2
6 rpntutorial - Reading RRDtool RPN Expressions by Steve Rader
7
9 This tutorial should help you get to grips with RRDtool RPN expressions
10 as seen in CDEF arguments of RRDtool graph.
11
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 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 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
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 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 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
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 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 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 Let's use that notation to conveniently solve some complex RPN
69 expressions with multiple logic operators:
70 1) 20,10,GT,10,20,IF eval is 20,10,GT = 1 result is 1,10,20,IF
72 read the eval as pop "20 is greater than 10" so push 1
74 2) 1,10,20,IF eval is 1,10,20,IF = 10 result is 10
76 read pop "if 1 then 10 else 20" so push 10. Only 10 is left so 10 is
78 the answer.
79 Let's read a complex RPN expression that also has the traditional
81 multiplication operator:
82 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,128,8,*,IF eval 128,8,* result is 1024
86 4) 0,7000,1024,IF result is 1024
87 Now let's go back to the first example of multiple logic operators, but
89 replace the value 20 with the variable "input":
90 1) input,10,GT,10,input,IF eval is input,10,GT ( lets call this A )
92 Read eval as "if input > 10 then true" and replace "input,10,GT" with
94 "A":
95 2) A,10,input,IF eval is A,10,input,IF
97 read "if A then 10 else input". Now replace A with it's verbose
99 description again and--voila!--you have a easily readable description
100 of the expression:
101 if input > 10 then 10 else input
103 Finally, let's go back to the first most complex example and replace
105 the value 128 with "input":
106 1) input,8,*,7000,GT,7000,input,8,*,IF eval input,8,* result is A
108 where A is "input * 8"
110 2) A,7000,GT,7000,input,8,*,IF eval is A,7000,GT result is B
112 where B is "if ((input * 8) > 7000) then true"
114 3) B,7000,input,8,*,IF eval is input,8,* result is C
116 where C is "input * 8"
118 4) B,7000,C,IF
120 At last we have a readable decoding of the complex RPN expression with
122 a variable:
123 if ((input * 8) > 7000) then 7000 else (input * 8)
125
127 Exercise 1:
128 Compute "3,2,*,1,+ and "3,2,1,+,*" by hand. Rewrite them in
130 traditional notation. Explain why they have different answers.
131 Answer 1:
133 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 Exercise 2:
139 One may be tempted to shorten the expression
141 input,8,*,56000,GT,56000,input,*,8,IF
143 by removing the redundant use of "input,8,*" like so:
145 input,56000,GT,56000,input,IF,8,*
147 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 Answer 2:
153 if (input <= 56000/8 ) { input*8 } else { 56000 }
155 input,56000,8,DIV,LT,input,8,*,56000,IF
156 Exercise 3:
158 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 Answer 3:
164 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 Exercise 4:
173 Explain why it was desirable for the RRDtool developers to implement
175 RPN notation instead of traditional mathematical notation.
176 Answer 4:
178 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
186 Steve Rader <rader@wiscnet.net>
1871.3.8 2008-12-22 RPNTUTORIAL(1)