Previous Contents Next

The Robots of Dawn

As we promised in the last application of the third part (page ??), we will now revisit the problem of robots in order to treat it in a distributed framework where the world is a server and where each robot is an independent process capable of being executed on a remote machine.

This application is a good summary of the possibilities of the Objective CAML language because we will utilize and combine the majority of its features. In addition to the distributed model which is imposed on us by the exercise, we will make use of concurrency to construct a server in which multiple connections will be handled independently while all sharing a single memory representation of the ``world''. All access to and modification of the state of affairs of the world will therefore have to be protected by critical sections.

In order to reuse as much as possible the code that we have already built for robots in one section, and the client-server architecture of another section, we will use functors and inheritance of classes at the same time.

This application is quite minimal, but we will see that its architecture lends itself particularly well to extensions in multiple directions.


We take a representation of the world similar to that which we developed in Part III. The world is a grid of finite size, and each cell of the grid can be occupied by only one robot. A robot is identified by its name and by its position; the world is determined by its size and by the robots that live in it. This information is represented by the following types:

# type position = { x:int ; y:int } ;;

# type robot_info = { name : string ; mutable pos : position }
type world_info = { length : int ; width : int ;
mutable robots : robot_info list } ;;

The world will have to serve two sorts of clients: These two categories of clients and their behavior will determine the collection of messages exchanged by the server and clients.

When a client connects, it declares itself passive (Spy) or active (Enter). A spy receives as response to its connection the global state of the world. Then, it is kept informed of all changes. However, it cannot submit any requests. A robot which connects must supply its characteristics (its name and its initial position); the world then confirms its arrival. Then, it can request information: its own position (GetPos) or the list of robots that surround it (Look). It can also instruct the world to move it. The protocol of requests to the world from distributed robots is represented by the following type:

# type query =
| Spy (* initial declaration requests *)
| Enter of robot_info

| Move of position (* robot requests *)
| GetPos
| Look of int

| World of world_info (* messages delivered by the world *)
| Pos of robot_info
| Exit of robot_info ;;

From this protocol, using the functors from the ``distributed toolbox'' of the previous chapter, we immediately derive the generic server.

# module Pquery = Make_Protocol (struct type t = query end ) ;;
# module Squery = Server (Pquery) ;;

Now we need only specify the behavior of the server by implementing the method process to handle both the data that represent the world and the data for managing connections.

More precisely, the server contains a variable world (of type world_info) which is protected by the lock sem (of type Mutex.t). It also contains a variable spies which is a list of queues of messages to send to observers, with one queue per spy. To activate the processes in charge of sending these messages, the server also maintains a signal (of type Condition.t).

We provide an auxiliary function dist to calculate the distance between two positions:

# let dist p q = max (abs (p.x-q.x)) (abs (p.y-q.y)) ;;
val dist : position -> position -> int = <fun>

The function critical encapsulates the calculation of a value within a critical section:

# let critical m f a =
Mutex.lock m ; let r = f a in Mutex.unlock m ; r ;;
val critical : Mutex.t -> ('a -> 'b) -> 'a -> 'b = <fun>

Here is the definition of the class server implementing the world-server. It is long, but we will follow it up with a step-by-step explanation.

# class server l w n np =
object (self)
inherit [query] Squery.server n np
val world = { length=l ; width=w ; robots=[] }
val sem = Mutex.create ()
val mutable spies = []
val signal = Condition.create ()

method lock = Mutex.lock sem
method unlock = Mutex.unlock sem

method legal_pos p = p.x>=0 && p.x<l && p.y>=0 && p.y<w

method free_pos p =
let is_not_here r = r.pos.x<>p.x || r.pos.y<>p.y
in critical sem (List.for_all is_not_here) world.robots

method legal_move r p =
let dist1 p = (dist r.pos p) <= 1
in (critical sem dist1 p) && self#legal_pos p && self#free_pos p

method queue_message mes =
List.iter (Queue.add mes) spies ;
Condition.broadcast signal

method trace_loop s q =
let foo = Mutex.create () in
let f () =
spies <- q :: spies ;
self#send s (World world) ;
while true do
while Queue.length q = 0 do Condition.wait signal foo done ;
self#send s (Queue.take q)
with _ -> spies <- List.filter ((!=) q) spies ;
Unix.close s
in ignore (Thread.create f ())

method remove_robot r =
self#lock ;
world.robots <- List.filter ((<>) r) world.robots ;
self#queue_message (Exit {r with}) ;

method try_move_robot r p =
if self#legal_move r p
then begin
self#lock ;
r.pos <- p ;
self#queue_message (Pos {r with}) ;

method process_robot s r =
let f () =
world.robots <- r :: world.robots ;
self#send s (Pos r) ;
self#queue_message (Pos r) ;
while true do
Thread.delay 0.5 ;
match self#receive s with
Move p -> self#try_move_robot r p
| GetPos -> self#send s (Pos r)
| Look d ->
self#lock ;
let dist p = max (abs (p.x-r.pos.x)) (abs (p.y-r.pos.y)) in
let l = List.filter (fun x -> (dist x.pos)<=d) world.robots
in self#send s (World { world with robots = l }) ;
| _ -> ()
with _ -> self#unlock ;
self#remove_robot r ;
Unix.close s
in ignore (Thread.create f ())

method process s =
match self#receive s with
Spy -> self#trace_loop s (Queue.create ())
| Enter r ->
( if not (self#legal_pos r.pos && self#free_pos r.pos) then
let i = ref 0 and j = ref 0 in
( try
for x=0 to l do
for y=0 to w do
let p = { x=x ; y=y }
in if self#legal_pos p && self#free_pos p
then ( i:=x ; j:=y; failwith "process" )
done done ;
Unix.close s
with Failure "process" -> r.pos <- { x= !i ; y= !j } )) ;
self#process_robot s r
| _ -> Unix.close s

end ;;
class server :
int ->
int ->
int ->
int ->
val nb_pending : int
val port_num : int
val sem : Mutex.t
val signal : Condition.t
val sock : Unix.file_descr
val mutable spies : Pquery.t Queue.t list
val world : world_info
method free_pos : position -> bool
method legal_move : robot_info -> position -> bool
method legal_pos : position -> bool
method lock : unit
method process : Unix.file_descr -> unit
method process_robot : Unix.file_descr -> robot_info -> unit
method queue_message : Pquery.t -> unit
method receive : Unix.file_descr -> Pquery.t
method remove_robot : robot_info -> unit
method send : Unix.file_descr -> Pquery.t -> unit
method start : unit
method trace_loop : Unix.file_descr -> Pquery.t Queue.t -> unit
method try_move_robot : robot_info -> position -> unit
method unlock : unit

The method process starts out by distinguishing between the two types of client. Depending on whether the client is active or passive, it invokes a processing method called: trace_loop for an observer, process_robot for a robot. In the second case, it checks that the initial position proposed by the client is compatible with the state of the world; if not, it finds a valid initial position. The remainder of the code can be divided into four categories:
  1. General methods: these are methods which we developed in Part III for general worlds. Mainly, it is a matter of verifying that a displacement is legal for a given robot.
  2. Management of observers: each observer is associated with a socket through which it is sent data, with a queue containing all the messages which have not yet been sent to it, and with a process. The method trace_loop is an infinite loop that empties the queue of messages by sending them; it goes to sleep when the queue is empty. The queues are filled, all at the same time, by the method queue_message. Note that after appending a message, the activation signal is sent to all processes.
  3. Management of robots: here again, each robot is associated with a dedicated process. The method process_robot is an infinite loop: it waits for a request, processes it, and responds if necessary. Then it resumes waiting for the next request. Note that it is these robot-management methods which issue calls to the method queue_message when the state of the world has been modified. If the connection with a robot is lost---that is, if an exception is raised while waiting for a request---the robot is considered to have terminated and its departure is signaled to the observers.
  4. Inherited methods: these are the methods of the generic server obtained by application of the functor Server to the protocol of our application.


The functor Client gives us generic functions for connecting with a server according to the particular protocol that concerns us here.

# module Cquery = Client (Pquery) ;;
module Cquery :
module Com :
val send : Unix.file_descr -> Pquery.t -> unit
val receive : Unix.file_descr -> Pquery.t
val connect : string -> int -> Unix.file_descr
val emit_simple : string -> int -> Pquery.t -> unit
val emit_answer : string -> int -> Pquery.t -> Pquery.t

The behavior of a spy is simple: it connects to the server and displays the information that the server sends it. The spy includes three display functions which we provide below:

# let display_robot r =
Printf.printf "The robot %s is located at (%d,%d)\n" r.pos.x r.pos.y ;
flush stdout ;;
val display_robot : robot_info -> unit = <fun>

# let display_exit r = Printf.printf "The robot %s has terminated\n" ;
flush stdout ;;
val display_exit : robot_info -> unit = <fun>

# let display_world w =
Printf.printf "The world is a grid of size %d by %d \n" w.length w.width ;
List.iter display_robot w.robots ;
flush stdout ;;
val display_world : world_info -> unit = <fun>

The primary function of the spy-client is:

# let trace_client name port =
let sock = Cquery.connect name port
in Cquery.Com.send sock Spy ;
( match Cquery.Com.receive sock with
World w -> display_world w
| _ -> failwith "the server did not follow the protocol" ) ;
while true do
match Cquery.Com.receive sock with
Pos r -> display_robot r
| Exit r -> display_exit r
|_ -> failwith "the server did not follow the protocol"
done ;;
val trace_client : string -> int -> unit = <fun>

There are two ways of constructing a graphical display. The first is simple but not very efficient: since the server sends the complete set of information when a connection is established, one can simply open a new connection at regular intervals, display the world in its entirety, and close the connection. The other approach involves using the information sent by the server to maintain a copy of the state of the world. It is then easy to display only the modifications to the state upon reception of messages. It is this second solution which we have implemented.


As we defined them in the previous chapter (cf. page ??), the robots conform to the following signature.

# module type ROBOT =
class robot : int -> int ->
val mutable i : int
val mutable j : int
method get_pos : int * int
method next_pos : unit -> int * int
method set_pos : int * int -> unit
end ;;

The part that we wish to save from the various classes is that which necessarily varies from one type of robot to another and which defines its behavior: the method next_pos.

In addition, we need a method for connecting the robot to the world (start) and a loop that alternately calculates a new position and communicates with the server to submit the chosen position.

We define a functor which, when given a class implementing a virtual robot (that is, conforming to the signature ROBOT), creates, by inheritance, a new class containing the proper methods to make an autonomous client out of the robot.

# module RobotClient (R : ROBOT) =
class robot robname x y hostname port =
object (self)
inherit R.robot x y as super
val mutable socket = Unix.stderr
val mutable rob = { name=robname ; pos={x=x;y=y} }

method private adjust_pos r =
rob.pos <- r.pos ; i <- r.pos.x ; j <- r.pos.y

method get_pos =
Cquery.Com.send socket GetPos ;
match Cquery.Com.receive socket with
Pos r -> self#adjust_pos r ; super#get_pos
| _ -> failwith "the server did not follow the protocol"

method set_pos =
failwith "the method set_pos cannot be used"

method start =
socket <- Cquery.connect hostname port ;
Cquery.Com.send socket (Enter rob) ;
match Cquery.Com.receive socket with
Pos r -> self#adjust_pos r ; self#run
| _ -> failwith "the server did not follow the protocol"

method run =
while true do
let (x,y) = self#next_pos ()
in Cquery.Com.send socket (Move {x=x;y=y}) ;
ignore (self#get_pos)
end ;;
module RobotClient :
functor(R : ROBOT) ->
class robot :
string ->
int ->
int ->
string ->
int ->
val mutable i : int
val mutable j : int
val mutable rob : robot_info
val mutable socket : Unix.file_descr
method private adjust_pos : robot_info -> unit
method get_pos : int * int
method next_pos : unit -> int * int
method run : unit
method set_pos : int * int -> unit
method start : unit

Notice that the method get_pos has been redefined as a query to the server: the instance variables i and j are not reliable, because they can be modified without the consent of the world. For the same reason, the use of set_pos has been made invalid: calling it will always raise an exception. This policy may seem severe, but it's a good bet that if this method were used by next_pos then a discrepancy would appear between the real position (as known by the server) and the supposed position (as known by the client).

We use the functor RobotClient to create various classes corresponding to the various robots.

# module Fix = RobotClient (struct class robot = fix_robot end) ;;
# module Crazy = RobotClient (struct class robot = crazy_robot end) ;;
# module Obstinate = RobotClient (struct class robot = obstinate_robot end) ;;

The following small program provides a way to launch the server and the various clients from the command line. The argument passed to the program specifies which one to launch.

# let port = 1200 in
if Array.length Sys.argv >=2 then
match Sys.argv.(1) with
"1" -> let s = new server 25 30 port 10 in s#start
| "2" -> trace_client "localhost" port
| "3" -> let o = new Fix.robot "fix" 10 10 "localhost" port in o#start
| "4" -> let o = new Crazy.robot "crazy" 10 10 "localhost" port in o#start
| "5" -> let o = new Obstinate.robot "obstinate" 10 10 "localhost" port
in o#start
| _ -> () ;;

To Learn More

The world of robots stimulates the imagination. With the elements already given here, one can easily create an ``intelligent robot'' which is both a robot and a spy. This allows the various inhabitants of the world to cooperate. One can then extend the application to obtain a small action game like ``chickens-foxes-snakes'' in which the foxes chase the chickens, the snakes chase the foxes and the chickens eat the snakes.

Previous Contents Next