Home page > OCaml > A Monad for OCaml Duppy
A Monad for OCaml Duppy
Saturday 7 May 2011, by
The context
Duppy is the OCaml module that we have developped with the Savonet Team as a solution for all scheduling tasks in Liquidsoap.
Duppy was initially intended as a nice way to create a simple scheduler that supports the following:
- Delayed tasks, that is tasks to be exectued after a given delay
- Reading and writing on
Unix.fdfile descriptors without blocking the calling thread - Custom priority system whith a pool of threads running concurrent queues processing tasks according to their priorities
For instance, for a HTTP server, a client acessing a local file such as an image, should be processed with maximum priority but a client requesting a php page should be processed with low priority, because executing a php script can potentially take a long time whereas reading from a local file is fast. Also, one php page may be using many images so serving the images faster is important to ensure a smooth data flow to the client.
Duppy was initially considered as a slight abstraction — namely a functional abstraction over Unix.select, but not necessarily of a very general scope. However, I realized lately that a much more interesting use of Duppy could be done.
Servers in Liquidsoap
The main use of Duppy in Liquidsoap is for implementing the various servers (telnet and harbor, our native implementation of the icecast source protocol) as well as implementing delayed tasks within the main language.
Concerning the server part, the code was written using exception catching as follows:
let serve_task socket task =
(..code for serving task..)
if (..some condition, for instance that the task is recognized..) then
(..code processing task..)
raise (Answer "P = NP!")
else
raise (Answer "Invalid request")
let login socket data =
(...code checking authentication..)
if not (..login correct..) then
raise (Answer "Wrong Authentification data")
let process_client socket request =
try
(..parse login data..)
(* Check login *)
login socket data;
(.. parse task request..)
(* Process data *)
serve_task socket task
with
| Answer s -> reply s; close socketWhen implementing a complex protocol, such as the Icecast source protocol, this allows to have very readable code, using an exception to stop the execution flow. The ultimate goal being the possibility to seperate more clearly the protocol logic from the control flow of the execution, in order to be able to proof-read the code more conveniently.
However, this approach has a major drawback: it messes with the semantics of exceptions, which are usually used to raise errors in OCaml.
Although not necessarily an issue for simple flows, in the case of protocols such as Icecast source protocol, where two totally different version of the protocol have to be supported, with different authentication schemes, etc.. this quickly became a nightmare.
In order to cope with the complex execution flow when using exception-based programming, it becomes necessary to add multiple type of exceptions and to catch and process them accordingly. This impacts the readability of the code very quickly, to the point where using exceptions is no longer really interesting.
Furthermore, OCaml does not offer the possibility to know which exceptions may be raised by a given function. which does not make it easy to verify that all possible catching cases are covered..
What about a Monad!
Seperating execution flow from the computaiton logic and encapsulating side-effects are the two main advantages of using monads in functional programming. Therefore, why about implementing those using a monad!
Basically, processing a request from a client consists of composing computations which either return immediatly with a response or return a result to use with the next one.
Furthermore, we would like those computations to be implemented using the Duppy scheduler, which has great advantages for writing and reading on network sockets and also to prioritize the different steps of the computation.
We consider thus computations of type ('a,'b)t. A computation ('a,'b)t either:
- returns a value of type
'a, which is passed to the next computation - returns a value of type
'bwhich is sent back to the previous computation
The main fonctions of the monad are:
module Monad :
sig
(** Type representing a computation
* which returns a value of type ['a]
* or raises a value of type ['b] *)
type ('a,'b) t
(** [return x] create a computation that
* returns value [x]. *)
val return : 'a -> ('a,'b) t
(** [raise x] create a computation that raises
* value [x]. *)
val raise : 'b -> ('a,'b) t
(** Compose two computations.
* [bind f g] is equivalent to:
* [let x = f in g x] where [x]
* has f's return type. *)
val bind : ('a,'b) t -> ('a -> ('c,'b) t) -> ('c,'b) t
(** [>>=] is an alternative notation
* for [bind] *)
val (>>=) : ('a,'b) t -> ('a -> ('c,'b) t) -> ('c,'b) t
(** [catch f g] redirects values [x] raised during
* [f]'s execution to [g]. The name suggests the
* usual [try .. with ..] exception catching. *)
val catch : ('a,'b) t -> ('b -> ('a,'c) t) -> ('a,'c) t
(** [=<<] is an alternative notation for catch. *)
val (=<<) : ('b -> ('a,'c) t) -> ('a,'b) t -> ('a,'c) t
(** [run f ~return ~raise ()] executes [f] and process
* returned values with [return] or raised values
* with [raise]. *)
val run : return:('a -> unit) -> raise:('b -> unit) -> ('a,'b) t -> unit
endMutexes and Conditions are also implemented within the monad, but we do not describe them here.
Finally, there is a camlp4 syntax extension, which allows to write code using this monad in a natural syntax:
duppy check_http x =
if x = "HTTP" then
duppy_return Http
else
duppy_raise Not_http
in
duppy_try
check_htttp x
with
| Not_http -> (...)Priorities and I/O operations
The main advantage of the Duppy monad is the handling of priorities and I/O operations.
Concerning priorities, a duppy computation can be rescheduled at any time with a new priority and optionally a delay. For instance the following computation:
duppy f x =
duppy_do
(..computation code..)
with
{ priority = Slow;
handler = h }When f is called, its execution is sent to a queue processing tasks of Slow priority.
Likewise, reading or writing a value from and to a Unix.file_descriptor is very simple:
duppy read_crlf () =
duppy_read
Duppy.Split "\r\n"
with
{ handler = h;
priority = Fast }In this code, f_crlf is a computation that reads from a file descriptor specified in handler until the first \r\n marker has been seen.
It is scheduled with a Fast priority because all read/write operations in Duppy are executed only when they will not block.
Code examples
Several examples using the Duppy monad are available. The module has two examples, a telnet and a HTTP server, which can be browsed online:
The monad is also used in liquidsoap, for the internal telnet server, which is very similar to the Telnet server above, but also for the harbor server, which implements the source part of the icecast protocol, and for the newoutput.harbor, which implements the listener part of the icecast protocol. These two examples can also be browsed online:
Difference with Lwt
The reader familiar with Lwt may wonder what is the difference with this module. The essential difference is that Duppy does not implement light-weight threads but rather a pool of queues picking up different tasks one by one.
Therefore, it allows to specify priorities for the queues and does not require that you rewrite all your code using compatible versions of the blocking functions.
Conclusion
Monads can be very useful in order to encapsulate specific computation flows. In this case, we have used a monad to have a notion of exception raising that is compatible with the Duppy scheduler. Eventually, this allows to write code that is easy to proof-read and that takes advantage of all advanced functionalities of the scheduler without being obscured by many irrelevant technical details..
RSS 2.0
2 Forum messages