Postfix expressions revisited

The previous entry (Ruby: postfix expressions) left with the promise to improve some parts using Ruby style tools.

We restart with the same tokenizer and implement the evaluator the same way but remove code duplication. Next we try to make tests easier to read.

Remove code duplication

The four operators implementation in the Evaluator class are very similar. We can remove the similarity by applying what we call meta programming (say we are going to write dynamic code that generates code at runtime).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
require 'tokenizer'

class Evaluator

  def initialize
    @stack = []
  end
  
  def compute expr
    
    @tokenizer = Tokenizer.new(expr)
    
    loop do
      
      type, token = @tokenizer.next
      
      break unless token

      case type
      
        when :error
          @stack.clear
          @stack << [:error, token]
          break
          
        when :operator
          break if self.send(token) == :error
        
        when :operand
          @stack << token
          
      end
      
    end

    expr.close
    
    @stack
    
  end
  
  private
  
  def pop_operands
    
    if @stack.length < 2
      @stack.clear
      @stack << [:error, "Missing operands at line #{@tokenizer.lineno}"]
      return :error
    end
    
    b = @stack.pop
    a = @stack.pop
    
    return a, b
    
  end
end

Instead of writing four methods for the operators, we write code that generates them when Ruby runs it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
require 'tokenizer'

class Evaluator

  def initialize
    @stack = []
  end
  
  def compute expr
    
    @tokenizer = Tokenizer.new(expr)
    
    loop do
      
      type, token = @tokenizer.next
      
      break unless token

      case type
      
        when :error
          @stack.clear
          @stack << [:error, token]
          break
          
        when :operator
          break if self.send(token) == :error
        
        when :operand
          @stack << token
          
      end
      
    end

    expr.close
    
    @stack
    
  end
  
  private
  
  def pop_operands
    
    if @stack.length < 2
      @stack.clear
      @stack << [:error, "Missing operands at line #{@tokenizer.lineno}"]
      return :error
    end
    
    b = @stack.pop
    a = @stack.pop
    
    return a, b
    
  end
  
  [:+, :-, :*, :/].each do |op|
  
    define_method(op) do
    
      a, b = pop_operands
    
      return :error if a == :error
    
      @stack << a.send(op, b)
      
    end
    
  end
  
end

Line 59 loops through the four method names we want to add, using the define_method method that adds instance methods to the class being defined. The code is generic through the use of the send method (Ruby sends messages to the objects when we think it calls some method).

Rewrite the tests…

1
2
3
4
5
6
7
8
9
10
11
'3 4 +'.should_evaluate_to(7)
'7 4 - 2 *'.should_evaluate_to(6)
'11 4 + 3 /'.should_evaluate_to(5)
  
# test errors
'3 + '.should_evaluate_to([:error, "Missing operands at line 1"])
'22 a +'.should_evaluate_to([:error, 'Invalid token "a" at line 1'])
'3.5 2 +'.should_evaluate_to([:error, 'Invalid token "3.5" at line 1'])

# show failure message
'3 4 *'.should_evaluate_to(7)

We need to add the should_evaluate_to method to the standard String class. Ruby allows you to modify any class by re-opening the class definition.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
require 'test/unit'
require 'stringio'

require 'evaluator'

class TokenizerTests < Test::Unit::TestCase
end

class String

  def should_evaluate_to *expected_value
  
    caller[0] =~ /(.*):/
    message = "Wrong evaluation at #{$1}"
    
    expression = self
    
    TokenizerTests.send(:define_method, "test '#{self}' ") do
      
      evaluator = Evaluator.new
    
      assert_equal expected_value, evaluator.compute(StringIO.new(expression)), message
    
    end
    
  end
  
end

Test methods are added when we use the new should_evaluate_to method we add to the String class.

Re-opening a class definition is as simple as writing the class keyword followed by the class name (line 9), as a normal definition. Next we add our new method (line 11).

The should_evaluate_to method prepares the error message (line 13), otherwise the failure message won’t point to the line number that is accurate for the developer, it would always show line 22 where the assertion happens. We use Ruby’s caller method that returns the current call stack.

Line 18 calls the private define_method method, hence we use send to bypass the private limitation, to add a test method with the name containing the expression under test. Notice that the name contains spaces and single quote characters that are invalid characters for method names defined with the def keyword.

We get the expression string, the file name, the line number where the assertion failed and both expected and actual values.

Conclusion

The meta-programming can make reading code much harder, it does not matter if you have never to dig into that code. It is part of the language and opens new options for the programmers.

We re-opened the String class and that is maybe not recommended as it can break code (hide standard methods, break the class behavior) and again make code harder to read if you don’t expect such things. Here the change is local to our file and the script is not part of a bigger file collection.