Re: [Caml-list] The Implicit Accumulator: a design pattern using optional arguments

[Jon Harrop <jon@ffconsultancy.com>]

On Wednesday 27 June 2007 16:06:51 Quôc Peyrot wrote:
> I mean, for someone like me, with quite some experience in the asm/c/c
> ++ world (i.e. a garbage collector-less world) but not much in other
> languages, it's easy to naively think of a garbage collector as a
> fancy feature to prevent from having to call "free/delete". But I'm
> starting to realize there is a whole new set of powerful design
> patterns which come along. It has been said multiple times on this
> mailing list, but I think we really miss a book about these design
> patterns and optimization tricks often specific to a given (or a set
> of) feature (functional, lazy computations, garbage collector...).

This is an excellent idea. I'll write an OCaml Journal article on design 
patterns! :-)

> > Other advanced optimization techniques that can be used for benefit
> > in very specialized situations include (explicit) continuation coding:
> > rather than returning a value (e.g. a tuple), you take as an argument
> > a function to which you then pass on your return value(s). This is
> > quite
> > useful whenever "execution flow branches out into multiple paths that
> > have to be taken", and may sometimes (though rarely) also be used for
> > good as a poor man's VALUES/MULTIPLE-VALUE-BIND substitute.
>
> I didn't get that part at all. I think I would need an example to
> understand
> why it is interesting to pass the function instead of just returning
> the tuple
> and processing it.

I think Thomas is referring to continuation passing style (CPS). That isn't an 
optimization though (it slows things down) but it does let you abstract away 
mutation. However, it is not entirely safe in the absence of linear types.

For example, the immutable Map and mutable Hashtbl both map keys to values. If 
you wrap them with an API written in CPS then you can switch between Maps and 
Hashtbls transparently:

module type MAP = sig
  type t
  val create : unit -> t
  val add : string -> string -> t -> (t -> 'a) -> 'a
  val remove : string -> t -> (t -> 'a) -> 'a
  val copy : t -> (t * t -> 'a) -> 'a
end;;

module Pure : MAP = struct
  module Map = Map.Make(String)

  type t = string Map.t

  let create() = Map.empty

  let add k v m f = f(Map.add k v m)
  let remove k m f = f(Map.remove k m)
  let copy m f = f(m, m)
end;;

module Impure : MAP = struct
  type t = (string, string) Hashtbl.t

  let create() = Hashtbl.create 1

  let add k v m f =
    Hashtbl.replace m k v;
    let f_m = f m in
    Hashtbl.remove m k;
    f_m

  let remove k m f =
    let v = Hashtbl.find m k in
    Hashtbl.remove m k;
    let f_m = f m in
    Hashtbl.add m k v;
    f_m

  let copy m f = f(m, Hashtbl.copy m)
end;;

However, this is not completely safe because you might erroneously return a 
map or hash table from the continuation "f" passed to these functions. 
Enforcing this statically requires linear types.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?e