8th Light Blog

Recently, I started to read the Knuth’s Art of Computer Science. To spice up the exercises, I am writing them out in ruby. Thinking about the basic math of programming and how to implement it in a high level language like ruby has been fun. The evolution of programming languages has gone far since the book was written. We can use cool new ruby syntax to do multiple steps in an algorithm!

Also, this is an exercise in writing clean code. Some of the algorithms in the book are a bit hard to read in there pure math form. So, when I write them out in ruby, I try to use as much expressiveness without adding clutter. This is no easy task, and often times I have to walk away from an algorithm for awhile and come back to it, because I will have my head deep in the math and less in the code. Or vice versa.

I was showing one of my solutions to a colleague of mine, Doug Bradbury, who saw a better way in ruby to solve the same problem I was with less lines of code and a higher readability. So, I decided to share one of the problems, and in a few days, I will post my version of the solution. We can see different solutions in different languages and different styles. Go ahead and try it out.

Here is the algorithm as written in the book.

This is Euclid’s Algorithm for the greatest common divisor

E0 [Ensure m >= n.] If m < n, exchange m <--> n.
E1 [Find remainder.] Divide m by n and let r be the remainder. (We will have 0 <= r < n.)
E2 [Is it zero?] If r = 0, the algorithm terminates;n is the answer.
E3 [Reduce.] Set m <- n, n <- r, and go back to step E1.


UPDATE: Here is a solution

def are_whole_numbers?(*numbers)
  numbers.each {|number| return false if number.to_i.to_f != number}
  return true
end

def euclid(m, n)
  raise "Must be whole numbers." unless are_whole_numbers?(m, n)
  return euclid(n, m) if m < n

  remainder = m % n

  return n if remainder == 0
  return euclid(n, remainder)
end

#Here are some examples
puts euclid(35.0, 40.0) #should be 17.0
puts euclid(119.0, 544.0) #should be 17.0
puts euclid(555.0, 666.0) #should be 111.0

As we work with our clients to delivery new features to them quickly and with high quality code, we are finding that the fastest way forward is often writing code in Ruby. The problem is that in many cases we are working with an existing application written in a different language. We may need to add a feature to a C++ application or integrate with a Java Library. One of our favorite solutions in this situations is to have multiple applications talking to each other over sockets.

We’ve found that using sockets to communicate between applications is a great way to ‘bolt on’ new functionality. This type of communication has been around for a long time and nearly every language has socket communication in standard libraries or in free open source projects.

Dean Wampler suggested that Applications Should Use Several Languages and socket communication is another way to enable this.

Socket Basics
Most internet communication is built on socket communication, so I won’t try to go into great detail here. I don’t pretend to be an expert. Here is what you need to understand about sockets to use them in your applications.

UDP vs TCP
There are two basic types of IP socket protocols: UDP and TCP. UPD is what I’ll call a ‘send and pray’ protocol. In UDP there is really no difference between server and client. Each node can listen on some port and write on some port. Messages are sent from point to point or broadcast to all nodes. Either way, delivery is not guaranteed. The message will likely make it to the destination, but there are a host of things that could happen that would prevent delivery. Worse, as the sender you can’t know whether of not your message made it unless you implement some kind of response protocol on top.

I’ve used UDP communications for monitoring / metering applications where it isn’t important that every message be delivered, but I’ve also found that I usually end up implementing some kind of delivery guarantee mechanism anyway.

TCP sockets build another layer on top of basic IP communication that does guarantee delivery. Once the connection is established between client and server, both side can communicate knowing that their message will be received. On the Server side, a socket listens on a particular port for new connections. Most libraries call this operation ‘accept.’ A client ‘opens’ a connection to the server. This process involves the client and the server agreeing on a new port for communication. If the server is going to accept multiple connections, then it usually launches a new thread to handle each new connection.

I use TCP Sockets for most inter-application communication. It turns out that in most situations, I want that guaranteed delivery and don’t want to bother with my own acknowledgment protocol. So it’s the TCP Socket that I’ll show you for now.

Over my next few posts, I’ll show you how to communicate via sockets in many languages. We’ll start with Ruby. Ruby has TCP Sockets built in, though there really isn’t much documentation on how to use it. Here is how to do it.

The TCPSocket class can be found in ‘socket’

require 'socket' 

Create a socket server. The first parameter is the address to listen on. If you specify ‘0.0.0.0’ then the server will accept connections from any host. If you specify ‘localhost’ or ‘127.0.0.1’ this the server will only accept connections from sockets on the same computers. The port can be anything you want. Be sure to avoid commonly used ports.

   server = TCPServer.new('localhost', '4138') 

Now, when you call accept on the server it will block until a client opens up a connection.

    server_socket = server.accept

Now that the server is waiting for a new connection, let’s open that connection from a client. Note that this needs to be happening in a separate ruby process. The first parameter is the host address or name of the server. The second is the port on which the server is listening.

    require 'socket'
    client_socket = TCPSocket.new('localhost', '4138')

Now that there is as new connection open the client and server can talk back and forth at will. In this example, the server just echos the clients message back to it. So all together, the Server side looks like this:

    require 'socket' 
    server = TCPServer.new('localhost', '4138') 
    server_socket = server.accept
    message = server_socket.recvfrom(256)[0]
    server_socket.write("You Said: #{message}")

And the Client side:

    require 'socket'
    client_socket = TCPSocket.new('localhost', '4138')
    print "Enter Message:  "
    input = gets
    client_socket.write(input)
    response = client_socket.recvfrom(256)[0]
    puts response

So that’s it, you are communicating between two applications with sockets. If we want the server to continue processing messages, we can loop reading from the socket:

    require 'socket' 
    server = TCPServer.new('localhost', '4138') 
    server_socket = server.accept

    message = ""
    until message.chomp == "quit" do
        message = server_socket.recvfrom(256)[0]
        server_socket.write("You Said: #{message}")
    end

So far our server can only handle one connection at a time. Often times, you’ll want multiple client to be able to open up connections to the server. To do this, we’ll need to launch a new thread each time a client connects. This is a little class that does that. You can implement your own handler object to handle each socket. The handler only needs a ‘serve’ method that takes a socket. The ThreadGroup is a nice little class to keep track of the threads. When a thread finishes, it is automatically removed from the thread group.

require 'socket' 

class MultiTcpServer

  def initialize(handler, port)
    @group = ThreadGroup.new
    @handler = handler
    @server = TCPServer.new('0.0.0.0', port) 
  end

  def connections_open
    return @group.list.size
  end

  def run
    begin
      loop do
        socket = @server.accept
        @group.add(Thread.new {@handler.serve(socket)})
      end
    rescue IOError
    end
  end

  def stop
    @server.close
  end

end

Hopefully this little tutorial was helpful. Next time I’ll take a look at sockets in C++ or Java.