Vous pouvez vous abonner à nos annonces de séminaires
                     http://gallium.inria.fr/seminaires/

                             S E M I N A I R E
       __                                  
      / _`  _   /  /  o                       /| /|   __  __  __ __    _  _
     /   ) __) /  /  / /  / /\/|    -----    / |/ |  /  )(_  /  /  ) ) ) __)
    (___/ (_/ (_ (_ / (__/ /   |            /     | (__/ __)(_ (__/ (_/ (_/
                                                
                          I N R I A - Rocquencourt
                        Amphi Turing du bâtiment 1

                          VENDREDI 24 juin, 10h30

                                 ----------
                                 Mike Hicks
                                 ----------

                           University of Maryland

                   =====================================
                   Lightweight Monadic Programming in ML
                   =====================================

Many useful programming constructions can be expressed as monads. Examples
include probabilistic computations, time-varying expressions, parsers, and
information flow tracking, not to mention effectful features like state and
I/O. In this paper, we present a type-based rewriting algorithm to make
programming with arbitrary monads as easy as using ML's built-in support for
state and I/O. Developers write programs using monadic values of type M t as
if they were of type t, and our algorithm inserts the necessary binds, units,
and monad-to-monad morphisms so that the program typechecks. Our algorithm is
based on Jones' qualified types and enjoys three useful properties: (1)
principal types, i.e., the rewriting we perform is the most general; (2)
coherence, i.e., thanks to the monad and morphism laws, all instances of the
principal rewriting have the same semantics; (3) decidability; i.e., the
solver for generated constraints will always terminate. Throughout the paper
we present simple examples from the domains listed above. Our most complete
example, which illustrates the expressive power of our system, proves that ML
programs rewritten by our algorithm to use the information flow monad are
equivalent to programs in FlowCaml, a domain-specific information flow
tracking language.

This is joint work with Nikhil Swamy and Daan Leijen of Microsoft Research
(Redmond) and Nataliya Guts (University of Maryland).