From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <warrensomebody@gmail.com>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled 
	version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104])
	by yquem.inria.fr (Postfix) with ESMTP id 625C4BBB7
	for <caml-list@yquem.inria.fr>; Sat, 21 Jun 2008 20:23:58 +0200 (CEST)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AmQBAKrjXEjRVcivc2dsb2JhbACSJUMBDAMEBAkPBZcchBM
X-IronPort-AV: E=Sophos;i="4.27,684,1204498800"; 
   d="scan'208";a="14343503"
Received: from wf-out-1314.google.com ([209.85.200.175])
  by mail3-smtp-sop.national.inria.fr with ESMTP; 21 Jun 2008 20:23:57 +0200
Received: by wf-out-1314.google.com with SMTP id 24so1488466wfg.15
        for <caml-list@yquem.inria.fr>; Sat, 21 Jun 2008 11:23:55 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=gamma;
        h=domainkey-signature:received:received:message-id:from:to
         :content-type:content-transfer-encoding:mime-version:subject:date
         :x-mailer;
        bh=C9Rb2WEJr+pKm6AJ+vVu6uGLjugt7tdNvDbtmIhbVFg=;
        b=vAXmTFlWylfnk9Av0BF0wBBLal8kiMM24vM+6Au7hAt/cNiPmXPMIo72mOUwWy7pkj
         wTkAN4h1Hb4Nxd2uV+CoUVPeoXnQMfTjR43SmdPLLsiR+dd4yfT8fQR/Sg7F/uXVm/fj
         vxHv9sG37YVxNClyEZUUP3DOWDsLHGfVhSWCs=
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=message-id:from:to:content-type:content-transfer-encoding
         :mime-version:subject:date:x-mailer;
        b=TFNcuMmKNknHyAIfYrzVcLGWHUiZoMFY3jTt7g6CYYF2xCXRUX1AQsSmaYkGZziyYU
         RbVDSazazMi3R4Kx7/V4J0fU4QXHUlY3OQF9rw5ph36PrD9WvufjtfMmMdr9hnbEYCfQ
         6jM/pV+SrQw5sz5YaXCGD4ZcoUre3DhGbFOWk=
Received: by 10.142.158.17 with SMTP id g17mr2478282wfe.212.1214072635577;
        Sat, 21 Jun 2008 11:23:55 -0700 (PDT)
Received: from timesink.local ( [98.210.196.241])
        by mx.google.com with ESMTPS id 29sm5130221wfg.0.2008.06.21.11.23.54
        (version=TLSv1/SSLv3 cipher=RC4-MD5);
        Sat, 21 Jun 2008 11:23:54 -0700 (PDT)
Message-Id: <3822B729-FD99-429E-8150-CEAA57E4D84F@gmail.com>
From: Warren Harris <warrensomebody@gmail.com>
To: caml-list@yquem.inria.fr
Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
Content-Transfer-Encoding: 7bit
Mime-Version: 1.0 (Apple Message framework v924)
Subject: cost of monads
Date: Sat, 21 Jun 2008 11:23:54 -0700
X-Mailer: Apple Mail (2.924)
X-Spam: no; 0.00; monads:01 ocaml:01 abstraction:01 transformers:01 avoided:01 haskell:01 ocaml:01 sig:01 val:01 val:01 sig:01 struct:01 struct:01 warren:98 warren:98 

I'm considering writing a moderate sized program with high performance  
needs in a monad / monad transformer style in ocaml. Although I  
believe that this abstraction will offer me benefits in hiding some  
complexity, some of the monad transformers I would like to "stack" are  
quite simple (e.g. a state-transition monad), and I'm concerned that  
my program will be paying a high performance cost due to high function  
call overhead -- ones which cannot be optimized away due to module  
boundaries.

I know that the real answer here is "profile it and find out"... but I  
thought that asking for other's experience might be a good first step.  
Perhaps someone can offer a technique to make this work well, or a  
word of caution on why this should be avoided. I realize that most of  
the monad work happens in haskell (and I sometimes feel that I'm  
reinventing the wheel -- although it's very educational!), but I'd  
prefer to stick with ocaml if possible.

Warren


(* -*- Mode: Caml; tab-width: 4; indent-tabs-mode: nil -*- *)
(******************************************************************************)

module type MONAD =
sig
   type 'a t
   val return : 'a -> 'a t
   val (>>=) : 'a t -> ('a -> 'b t) -> 'b t
end

module type ID_MONAD =
sig
   type 'a t
   val return : 'a -> 'a t
   val (>>=) : 'a t -> ('a -> 'b t) -> 'b t
   val run : 'a t -> 'a
end

module IdM : ID_MONAD =
struct
   type 'a t = 'a
   let return a = a
   let (>>=) m f = f m
   let run a = a
end

(******************************************************************************)

module type STATE_MONAD =
sig
   type 'a t
   val return : 'a -> 'a t
   val (>>=) : 'a t -> ('a -> 'b t) -> 'b t

   type s
   type 'a m
   val lift : 'a m -> 'a t
   val run : 'a t -> s -> 'a m
   val gets : s t
   val puts : s -> unit t
end

module type STATE = sig type s end

module StateT(M:MONAD)(S:STATE) : STATE_MONAD with type s = S.s =
struct
   type 'a m = 'a M.t
   type s = S.s
   type 'a t = s -> ('a * s) M.t
   let return a s = M.return (a, s)
   let (>>=) m f s = M.(>>=) (m s) (fun (a, s) -> f a s)

   let lift m s = M.(>>=) m (fun a -> M.return (a,s))
   let run m s = M.(>>=) (m s) (fun (a, _) -> M.return a)
   let gets s = M.return (s, s)
   let puts s _ = M.return ((), s)
end

(******************************************************************************)

module type KMONAD =
sig
   type 'a t
   val return : 'a -> 'a t
   val (>>=) : 'a t -> ('a -> 'b t) -> 'b t

   type 'a m
   type ans
   val lift : 'a m -> 'a t
   val run : ans t -> ans m
   val callcc : (('a -> 'b t) -> 'a t) -> 'a t
end

module type K = sig type ans end

module KMonadT(M:MONAD)(K:K) : KMONAD with type ans = K.ans =
struct
   type ans = K.ans
   type 'a m = 'a M.t
   type 'a t = ('a m -> ans m) -> ans m
   let lift m k = k m
   let return a k = k (M.return a)
   let (>>=) m f k = m (fun am -> M.(>>=) am (fun a -> f a k))
   let run m = m (fun a -> a)
   let callcc f k = f (fun a _ -> return a k) k
end

(******************************************************************************)