Tetrahedral Numbers

Here's another one from Programming Praxis this one on tetrahedral numbers. I'll leave you to read the description and just jump straight into the ruby solution. The interesting thing here is to use a lambda to create a method that we can pass around. Here's the entire program ...

def linear(target, f)
    n = 1
    while ( f.call(n) != target)
        n = n + 1
    end
    n
end

def binary(target, f)
    low, high = 1, 2
    while (f.call(high) < target) do high = high*2 end
    mid = (high + low) / 2
    while (fmid = f.call(mid)) != target do
        fmid < target ?  (low, mid = mid, (mid + high) / 2) : (high, mid = mid, (low + mid) / 2)
    end
    mid
end


tetrahedral = lambda { |n| n * (n + 1) * (n + 2) / 6 }

1.upto(10) { |i| puts tetrahedral.call(i) }

puts linear(169179692512835000, tetrahedral)
puts binary(169179692512835000, tetrahedral)

We start out with two methods linear and binary which are pretty straightforward with the exception that both take a function (in this case f) as a parameter. For linear, we start at 1 and continue calling f until the value of f(n) is the same as target. binary is similar, but here we keep doubling the high value until we're above the target and then we calculate the fmid and use it as a high or low value until we converge.

The tetrahedral function itself is created with a lambda so that we can pass it to the other two methods. The next lines are simply tests. Note how much longer the linear method takes than the binary.

As always, let me know if you have questions or comments.

All True

I was working a problem on Programming Praxis yesterday and ended up writing a little piece of code that returned true if every element in a hash was true. It used inject and I thought it would be worth posting a generalized version here.

module Enumerable
    def all_true
        self.inject(true) { |r, v| r && (yield v) }
    end
end

We start by monkey patching the Enumerable module which will make it available for Arrays, Hashes, etc., basically anything that includes Enumerable. Next, we define the method all_true. The only line in the method is an inject which we initialize with true and then give it a block with two parameters, the r(esult) and the v(alue). We then and/&& the r(esult) with whatever the yield of the v(alue) returns.

You can test it with the following code ...

puts "#{[2, 4, 6, 8].all_true { |n| n%2 == 0 }}"
puts "#{[2, 4, 7, 8].all_true { |n| n%2 == 0 }}"

puts "#{{ 2=>2, 4=>4, 6=>6, 8=>8}.all_true { |n| n[0]%2 == 0 && n[1]%2 == 0 }}"
puts "#{{ 2=>2, 4=>4, 7=>7, 8=>8}.all_true { |n| n[0]%2 == 0 && n[1]%2 == 0 }}"

The first two of each set will return true, the second false.

As I've been doing the Programming Praxis problems, I've found myself using inject and its close relative map/collect more and more. I think this is partly because of the types of problems posted there and the influence of the solutions that are generated which tend to be functional programming based. At any rate, having a good understanding of both inject and map/collect will serve you well and simplify many of your day to day programming tasks.

Let me know if you have questions or comments.

Log Monitoring with a Ruby DSL

DSLs (Domain Specific Languages) are small languages built on top of general purpose languages to accomplish specific tasks. Examples of DSLs are things like rake/make for building executables, bc (the Unix/Linux calculator), and macro systems like the C/C++ precompiler and M4. Ruby, because of its syntax provides a great platform for building DSLs.

Recently, at work, we ended up needing to monitor a log file for a particular string. Our OPS group implemented this, but it turned out that we were getting quite a few false positives from the string by itself. We could however do a database check on a couple of items in the string to remove these false positives. The logging software we use didn't really allow this so we ended up putting together a .NET application (Windows box) that would be called when the string was found, it would do the database check, and then do the notifications as necessary. I started thinking that it would be nice if you could match a string and then provide some code to do whatever you'd like in a monitoring type system. Since I'd been looking at DSLs, this seemed like it might be a natural application for them.

Let's start out with a simple program to provide us a log file to monitor ...

while true
    v = rand
    if v < 0.1
        s = "Error"
    elsif v < 0.2
        s = "Warn"
    else
        s = "Info"
    end
    puts "#{Time.new}: #{s}"
    $stdout.flush
    sleep 1
end

So essentially, do forever, get a random number, 1/10 of the time put out an Error, 1/10 of the time put out a Warning, and the rest of the time put out an Info. These will all be preceded by the date/time. Obviously, in a real system, you'd just use your own logs. For this, I just ran this and redirected the output to mylog.txt.

OK, here's the DSL we'd like to implement. I put it in monitor.mon and when we run the program, we'll "interpret" this file. Here it is ...

monitor "Er.*r" do |line, match|
    puts "Error in: #{line} "
end

monitor "Warn" do |line, m|
    puts "Warning in: Match: #{m[0]}: #{line} "
end

monitor "Info"

So in the first item to monitor, we look for something like an "Error" (the ".*" is in there really just to show this can really be a regular expression. The second thing to monitor is the word "Warn", and finally the work "Info". In the first two cases we print a message, with the 2nd one actually showing the "match". We don't give a block to the 3rd one, but the default is to print a message too. Now even though we've done something pretty simple here, there is nothing preventing us from doing whatever we'd like in them that we can do in Ruby. Here, I'm thinking of things like emailing using possibly mailit) or database access as in our above problem using Sequel. At this point, we can "shell out" to the general purpose programming language of Ruby.

So, now we need to interpret the above file. Here's the code for this

require 'file/tail'

class MonitorLog 

    def initialize(filename, number)
        @filename = filename
        @number = number
        @monitors = []
    end

    # Add a new monitor (regex/block).
    def add_monitor(monitor)
        @monitors << monitor
    end

    # Monitor the log using the filename passed in. For each
    # line we'll check for a monitor match.
    def monitor
        File::Tail::Logfile.open(@filename) do |log|
            log.backward(@number).tail do |line| 
                @monitors.each do |m|
                    m.match line
                end
            end
        end
    end

end

# The Monitor class which is a type of Regexp with a block given for checking.
class Monitor

    # Create a new monitor with a regex and a block.
    def initialize(regex, block)
        @regex = Regexp.new regex
        @block = block
    end

    # Match a line. If we match, then we'll call the block
    # with the line and the MatchData.
    def match(line)
        m = @regex.match(line)
        @block.call(line, m) if m != nil
    end
end

# This will normally come from the monitor file where there will be a regular
# expression and a block to execute when it is found. If no block is given,
# we'll just print the line.
def monitor(regex, &block)
    if block_given?
        $monitor_log.add_monitor Monitor.new(regex, block)
    else
        $monitor_log.add_monitor Monitor.new(regex, lambda { |l, m| puts "Match: #{l}" })
    end
end

if __FILE__ == $PROGRAM_NAME

require 'getoptlong'

def usage
    puts "Usage #$0 [-n number] [-f filename] [-m monitor_filename]"
end

# Set up the command line options
opts = GetoptLong.new(
    ["--number", "-n", GetoptLong::REQUIRED_ARGUMENT],
    ["--filename", "-f", GetoptLong::REQUIRED_ARGUMENT],
    ["--monitor_file", "-m", GetoptLong::REQUIRED_ARGUMENT],
    ["--verbose", "-v", GetoptLong::NO_ARGUMENT],
    ["--help", "-h", GetoptLong::NO_ARGUMENT]
    )

# Set the default values for the options
number = 10
filename = 'monitor.log'
monitor_filename = 'monitor.mon'
$verbose = false

# Parse the command line options. If we find one we don't recognize
# an exception will be thrown and we'll rescue with a usage.
begin
    opts.each do | opt, arg|
        case opt
        when "--number"
            number = arg.to_i
        when "--filename"
            filename = arg
        when "--monitor_filename"
            monitor_filename = arg
        when "--verbose"
            $verbose = true
        when "--help"
            usage
            exit
        end
    end
rescue
    usage
    exit
end


# Create the montior log. We make it global as it's used for the monitor()
# creation method above.
$monitor_log = MonitorLog.new(filename, number)

# Load in the monitor file DSL.
load(monitor_filename)

# Start monitoring.
$monitor_log.monitor

end

Our first class is MonitorLog which takes a filename to monitor and a number the number of lines to start back in the file. We also have an array for the different monitors we define in the monitor.mon file. There's a add_monitor which takes a monitor and adds it to the array and finally, the monitor (I know too many monitor variables) which uses the file-tail gem. This method will simply tail the file and for each line call each of the monitors. The Monitor class contains a regular expression to match and a block to execute on a match. In the match method, we check the regular expression and if it matches, we'll call the block with the line we matched and the MatchData. Here, if we had a more interesting regex than I've shown so far, you could grab out things like login IDs or similar from the MatchData if you needed it for something rather than reparsing the line.

Now comes the "interesting" piece, the monitor (I know, I know). Note that this matches with the monitor.mon name and indeed this is what gets called when that file is loaded (see below). The two parameters are the regex and potentially a block. If the block is given we create a Monitor using them and if there's no block, as in the Info then we'll create a lambda that will print out "Match" and the line.

The rest of the code is the "main" program, getting the command line arguments, creating a new $monitor_log (made global for use in the monitor method, here, I'd be interested in a better way to do this), loading the monitor.mon file, and finally starting the monitoring.

Here's how to run this code ruby Monitor.rb -n 20 -f mylog.txt -m monitor.mon.

There's quite a bit missing here to make this a truely useful application. Certainly adding email would get you a long way towards this and is really easy to do. The slightly more difficult thing is to make this work with rotating log files or even multiple log files and these are left as an exercise for the reader ;-).

Let me know if you have questions or comments.

Metaprogramming Ruby - Review

I wrote a review of Metaprogramming Ruby by Paolo Perrotta and much to my surprise, Slashdot published it. You can find it here. Feel free to post comments and thoughts.

Ruby and Simple Dynamic Programming V

I've been reading Paolo Perrotta's new book "Metaprogramming Ruby" recently and enjoying it thoroughly. In the first chapter, he talks about Monkey Patching, the ability to add methods to classes at runtime. This combined with a need recently for an iterator through an array that returns both the index and the value led me to come up with the following code:

# Open the Array class and add a new method "each_with_index".
# This will loop through the array using the each_index method
# and yeild the index and the value of the array at that index.
class Array
    def each_with_index
        self.each_index do | i |
            yield i, self[i]
        end
    end
end

if __FILE__ == $PROGRAM_NAME

# Create a simple array
x = [ "hello", "world", 42, 3.14159, ["test", "an", "array"] ]

# Go through the array and print each index and value in the
# array.
x.each_with_index do | i, v |
    puts "index = #{i} value = #{v}"
end


end

The code is pretty simple. We open the Arrary class, define the new method, and then close the class. There's a bit of test code after that to show that everything works as expected.

Even though I'm only through the first chapter, I can recommend Perrotta's book. It's an easy read (so far anyway) and clearly shows the concepts that it discusses. The form it takes is conversational and the narrative is that you're a programmer, new to Ruby, who is paired with a senior developer Bill. This format may not be for everyone, especially if you're looking for more "formality", but I think it works well here and it's not overdone.

Let me know if you have questions or comments.

Ruby and Simple Dynamic Programming II

In my last post, we went over using method_missing in Ruby to do some simple dynamic programming. In this post we'll take a look at using the Singleton Class (not the Singleton pattern) to do a bit more dynamic programming. Most of this is a rehash of a couple of great posts by Ola Bini here and Peter Jones here.

So, what is the Singleton Class? A Singleton Class is where methods for an individual object are stored. What's this mean? Let's just look at some code.

# Create a class, Foo, that has a single method bar. We'll also
# add a method_missing so that we can see what's called that 
class Foo
    def bar
        puts "Called bar"
    end

    # Put this in so we can see what gets called in foo2 below that's not available.
    def method_missing(name, *args, &block)
        puts "You tried to call #{name} with #{args.inspect}. There is no method with that name."
    end
end


# Create a new Foo
foo = Foo.new

# Call the method that does exist.
foo.bar

# Add a new method to foo. This method, baz, will be added to 
# foo's singleton class.
def foo.baz
    puts "Called baz"
end

# Call the method we just added.
foo.baz

# Another way to add a new method to foo. This method, baz, will be added to 
# foo's singleton class.
class << foo
    def qux
        puts "Called qux"
    end
end

# Call the method we just added.
foo.qux

# Show that we don't have either baz or qux for any other Foo objects.
foo2 = Foo.new
foo2.bar # Should be there
foo2.baz # Should not be there
foo2.qux # Should not be there

# Add two class methods to Foo.
class Foo
    class << self
        def quux
            puts "Called quux"
        end
    end

    def self.quuux
        puts "Called quuux"
    end
end

foo3 = Foo.new
foo3.quux
foo3.quuux

Foo.quux
Foo.quuux

First we define a class Foo (here we're going to use metasyntactic variables, a phrase I just learned here). Anyway, class Foo has two methods, bar and method_missing (see last post). bar just prints out the fact that it was called and method_missing shows any methods called that aren't available. Nothing too awfully interesting here, we've seen things like this a million times. Next, we'll just create a new Foo called foo and then call the bar method on it. After that, we're going to do something a bit new, we're going to add a new method, baz, to foo (note that we're adding it to the object foo and not the class Foo. We'll call foo.baz to show that it works. Following, we're going to add a method qux using a different syntax, but it will do exactly the same thing as the last addition. Then we're going to call qux on foo to show that it works. Where were these methods added? Well, you can see from the next few statements, that they weren't added to all Foos. The fact is they were added to foo's Singleton Class. The Singleton Class sits between the object foo and its class Foo (see Jones' post to see this represented graphically).

Since a class has a class Class (OK, that may have made very little sense), it makes sense that the class Foo itself might have a Singleton Class and if you guessed that, then you guessed correctly. In the next section, we add a couple of methods using two different techniques to Foo (notice that we just reopen it), as class methods. In the same way as happened above, these methods are added to the Foo Singleton Class. We create a new foo3 variable and show that we can't call these new methods using an instance of foo, then we call them using Foo.

OK, so all of this is very interesting and ... so what? What can we do with this. Well, one use for the Singleton Class is for mocking (once again shown in Jones' post).

# Create a class, User, that has a single method get_buy_power. In
# real life a user would have many, many more methods than this.
class User
    def get_buy_power
        # Normally, this would be a complex call to 
        # the database, but here we'll just return
        # a random number * 10000.0. This should give
        # us a number between 0 and 10000.
        rand * 10000.0
    end
end

# A "normal" user. 
user_normal = User.new
puts "user_normal buy power = #{user_normal.get_buy_power}"


# Create a new User
user_small_bp = User.new

# Change the user_small_bp's get_buy_power method to return a small value. This will be
# added to the user_small_bp's singleton class.
class << user_small_bp
    def get_buy_power
        20.0
    end
end

# Print out the buy power for the user_small_bp
puts "user_small_bp buy power = #{user_small_bp.get_buy_power}"


# Create a new User
user_large_bp = User.new

# Change the user's get_buy_power method to return a large value. This will be
# added to the user's singleton class.
class << user_large_bp
    def get_buy_power
        200000.0
    end
end

# Print out the buy power for the user_large_bp
puts "user_large_bp buy power = #{user_large_bp.get_buy_power}"


# We can now use user_small_bp and user_large_bp to run tests on buying stocks 
# without enough buy power or with quite a bit of buy power.


# Create a simple OrderManager that will place orders and send orders. The place_order
# method will check a user's buy power before sending an order through. If the buy power isn't
# large enough, it will simply print a message, otherwise it will send the order and it
# will also print a message.
class OrderManager
    def place_order(user, shares, stock, price)
        if user.get_buy_power > price*shares
            send_order(stock, price, shares)
        else
            puts "Not engough buy power for #{shares} of #{stock} at #{price}"
        end
    end

    private

    def send_order(stock, price, shares)
        puts "Order sent for #{shares} of #{stock} at #{price}"
    end
end

# Create a simple order manager.
order_manager = OrderManager.new

# Place an order for 200 shares of apple at $210.0 with user_small_bp. This should fail.
order_manager.place_order(user_small_bp, 200, "AAPL", 210.0)

# Place an order for 200 shares of apple at $210.0 with user_large_bp. This should succeed.
order_manager.place_order(user_large_bp, 200, "AAPL", 210.0)

Take a look at the code above. In the world that I live in (stock trading software), users have a certain amount of buy power that they can use to purchase stocks. Normally, this value would come out of the database and would be incremented (selling a stock) and decremented I(buying a stock) with each trade (OK, this sentence is incredibly simplistic, but will do for now). We're going to use Singleton Class to change our get_buy_power method (rather than adding as we did earlier). In one case, we'll give the user very little buy power and in the other, quite a bit more. After that, we'll create simple order manager that will allow us to place an order for a user that will check their buy power before sending it.

So there you have it, the Singleton Class and its usage. As always, let me know if you have any questions or comments.

Ruby and Simple Dynamic Programming

I've been reading"Ruby Best Practices" by Gregory T. Brown and it's well worth checking out for anyone interested in Ruby. I'm in the middle of Chapter 3, "Mastering the Dynamic Toolkit" and thought I'd share a some simple bits of code that actually use dynamic programming.

We actually make use of the fact that with Ruby you can add a method_missing method to any class that allows you to capture calls to any method that are ... well missing. Here's a simple example that shows how it works.

# Create a class with the method_missing method. If a method 
# is called on this class and it's not found, then this method
# will be called. We'll then print whatever was passed in along
# with the fact that it's not there.
class MM
    def x
        puts "Called x"
    end

    def y
        puts "Called y"
    end

    def method_missing(name, *args, &block)
        puts "You tried to call #{name} with #{args.inspect}. There is no method with that name."
    end
end

if __FILE__ == $PROGRAM_NAME

    # Create a new MM
    mm = MM.new

    # Call the two mehtods that do exist.
    mm.x
    mm.y

    # Call z (which doesn't exist) both with and without 
    # paramaters.
    mm.z
    mm.z 1, 2, 3
end

This code creates a simple class called MM with three methods, x, y, and method_missing. The first two only print out the fact that they were called and the third will print out any other method that gets called, say z 1,2, 3 and will print out the name and parameters that get passed in to it. The main code just creates a new MM and calls a few methods (existing and not) on it.

Admittedly, this isn't too awfully interesting, but in our next example, we'll actually use method_missing to save ourselves some work. Here's the second bit of code:

# Create a class MM1. The x and y methods require calling
# setup before and teardown after. This means that everytime
# we have to add a new method (say z()), we end up having to
# duplicate this code. 
class MM1

    def setup
        puts "Setup"
    end

    def teardown
        puts "Tear down"
    end

    def x
        setup
        puts "Called x"
        teardown
    end

    def y
        setup
        puts "Called y"
        teardown
    end
end

# Create a class with the method_missing method. Here we
# still require x and y to have setup and teardown called, but
# we wrap it in method_missing as setup_x_teardown or setup_y_teardown.
# This allows us to also add z without having to worry about remembering
# the setup/teardown.
class MM2

    def setup
        puts "Setup"
    end

    def teardown
        puts "Tear down"
    end

    # The method_missing() does all of the work here. We check if the 
    # name is setup_something_teardown and if it is, we call setup,
    # call something with the parameters passed in, and then call teardown.
    # If the method isn't of this form, we just pass it along.
    def method_missing(name, *args, &block)
        case (name)
        when /^setup_(.*)_teardown/
            setup
            send($1, *args, & block) 
            teardown
        else
            super
        end
    end

    def x
        puts "Called x"
    end

    def y
        puts "Called y"
    end
end

if __FILE__ == $PROGRAM_NAME

    # Create a new MM1
    mm1 = MM1.new

    # Call the two mehtods that do exist.
    mm1.x
    mm1.y

    # Create a new MM2
    mm2 = MM2.new
    mm2.setup_x_teardown
    mm2.setup_y_teardown
end

There's two classes here that both "do" the same thing. The first class MM1 has two methods, x and y that require a setup before they are called and a teardown after they are called.

The second class, MM2, has the same requirements, but we're going to handle them a bit differently. We have the same setup and teardown, but we don't have x and y call them directly. Instead we use method_missing to handle the setup and teardown. What we're going to do is use method_missing and then check the name parameter. If it matches something that looks like setup_X_teardown, then we'll call setup, call the method using send, and finally, call teardown. If we don't match the pattern, then we just pass the call up the chain. The main code here creates both an MM1 and an MM2 and shows a bit of how to use them.

Here, in this simple example, you probably wouldn't bother with this. In the book Brown gives a much better use case, but this should give you some ideas at least.

Let me know if you have questions or comments.