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.
World-Server
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:
-
passive clients which simply observe the positions of various robots.
They will allow us to build the clients in charge of displays. We will call
them spies.
- active clients, able to ask the server to move robots and thus modify
its state.
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 () =
try
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)
done
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 name=r.name}) ;
self#unlock
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 name=r.name}) ;
self#unlock
end
method process_robot s r =
let f () =
try
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 }) ;
self#unlock
| _ -> ()
done
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 ->
object
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
end
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:
-
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.
- 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.
- 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.
- Inherited methods: these are the methods of the generic server
obtained by application of the functor Server to the protocol of our
application.
Observer-client
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 :
sig
module Com :
sig
val send : Unix.file_descr -> Pquery.t -> unit
val receive : Unix.file_descr -> Pquery.t
end
val connect : string -> int -> Unix.file_descr
val emit_simple : string -> int -> Pquery.t -> unit
val emit_answer : string -> int -> Pquery.t -> Pquery.t
end
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.name 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" r.name ;
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.
Robot-Client
As we defined them in the previous chapter (cf. page ??),
the robots conform to the following signature.
# module type ROBOT =
sig
class robot : int -> int ->
object
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
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) =
struct
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)
done
end
end ;;
module RobotClient :
functor(R : ROBOT) ->
sig
class robot :
string ->
int ->
int ->
string ->
int ->
object
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
end
end
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.