Hello

Here is the latest Caml Weekly News, for the week of September 05 to 12, 2006.

- O'Caml link db moved
- Olmar - almost a C++ parser for Ocaml
- autoconf macros, first round
- 3.09.3 release candidate 2
- Comparing two things of any two types, in pure OCaml
- OCaml and Quick C-- Output
- Memoization

Archive: http://groups.google.com/group/fa.caml/browse_thread/thread/7025e0728c8f3084/9d0893cdcb4a5e1d#9d0893cdcb4a5e1d

The O'Caml linkdb has been hosted on www.npc.de for seven years. It moves now to its own server http://funlinks.camlcity.org The functionality is exactly the same. Technically, however, there is an important change: The link db software is now entirely written in O'Caml - there isn't even an external web server as nethttpd is used. Parallelisation is achieved by using Netplex, a library part of the not yet released Ocamlnet 2. (The link db software is available under https://gps.dynxs.de/svn/app-linkdb/). Ah yes, and I can now again administer the link db.

Archive: http://groups.google.com/group/fa.caml/browse_thread/thread/0265d2c156c111d0/00295fd395095012#00295fd395095012

It is my pleasure to announce Olmar -- a system to process C++ programs in Ocaml available from http://www.cs.ru.nl/~tews/olmar/ More precisely, Olmar is a patch for the Elkhound/Elsa [1] C/C++ parser that permits the Elsa parser to translate its internal abstract syntax tree into an Ocaml value, which can then be further processed by an Ocaml program. Olmar comes with ast_graph, a tool that can dump the abstract syntax tree in the dot language. You can therefore now admire the syntax tree of Ocaml's minor garbage collector at http://www.cs.ru.nl/~tews/olmar/minor_gc.ps.gz License: BSD (following Elsa/Elkhound) [1] http://www.cs.berkeley.edu/~smcpeak/elkhound/

Archive: http://groups.google.com/group/fa.caml/browse_thread/thread/ea7bba8b161ff15f/730009538715dfb6#730009538715dfb6

Following discussion from last month, I started to work on three sets of macros: - macros checking install caml system - macros trying to determine caml module compilation flags - macros trying to actually compile some code using a caml module Here is a prototype implementation for the first set, bringing AC_PROG_OCAML and AC_PROG_CAMLP4. I didn't really tested portability yet, and didn't implemented caching either, I'm rather getting opinions about their interfaces and behaviour. Features: - minimal ocaml version checking - strict version checking for all tools - minimal working test for native compiler - user-selectable use of optimized versions Those macros are fatal if ocaml is not found for the first one, and if camlp4 is not found for the second. Otherwise, they just set variables, and issues warnings for missing tools or version mismatches. I'm not really sure, however, for the granularity. Grigory used to have another AC_PROG_OCAML_TOOL for ocamllex and ocamlyacc only, but I don't really see what criteria could be used for distinguishing what should be in AC_PROG_OCAML and what should be kept in AC_PROG_OCAML_TOOL, so I prefered to merge them. I know however camlp4 is installable separatly (at least on mandriva), moreover keeping it separated allows to make it fatal if not found. Comments welcomes. (The files are at the archive link.)

We have decided to make a second release candidate for 3.09.3. The only changes between rc1 and rc2 are camlp4-related: - camlp4: install pa_o_fast.o PR#3812 - camlp4: install more modules PR#3689 We would appreciate if camlp4 users (and particularly Hendrik) could test this version and report any problems found with it. Other users are still encouraged to try this one if they haven't tried 3.09.3+rc1. Like the previous one, this version is available from the CVS repository http://camlcvs.inria.fr/cvsserver-eng.html, but under the tag "ocaml3093rc2".

Archive: http://groups.google.com/group/fa.caml/browse_thread/thread/8466f57b4db7981c/e70bf82c9f28d793#e70bf82c9f28d793

This message shows an example of an open, extensible comparison function 'a -> 'b -> bool. Diego Olivier Fernandez Pons wrote about a help system associating (by means of a hashtable) a documentation string to a function. Alas, the hash function is not perfect and collisions are possible. Therefore, we need to validate each hashtable hit by physically (==) comparing the function (whose documentation we need to lookup) against the target function. The functions to document have generally different types. This raises two questions: how to store functions of different types in the same data structure, and how to compare a candidate function against these functions of different types. The physical comparison function (==) cannot be used as it is: we need a comparison function [cmp : 'a -> 'b -> bool] that can take arguments of any two types, returning false if the argument types are different. Jacques Garrigue suggested using Obj.repr. He also wrote ``Type theoretician answer: What you would need to do that transparently inside the type system is generic functions with dynamics.'' and mentioned GADT. It seems however that open polymorphic variants are ideal for the task. We start with let myeq (x : [>]) (y : [>]) = false;; and add one clause, comparing two booleans let myeq x y = match (x,y) with (`T'bool x, `T'bool y) -> x = y | _ -> myeq x y;; We can add another clause, for int->bool functions: let myeq x y = match (x,y) with (`T'int2bool (x : int->bool), `T'int2bool y) -> x == y | _ -> myeq x y;; Let's generate some test data let v1 = true let v2 x = not x let v3 f = f 2 let v4 x = x = 1;; and we are ready for the first test: let t1 = [ myeq (`T'bool v1) (`T'bool v1); myeq (`T'int2bool v4) (`T'int2bool v4); myeq (`T'bool v1) (`T'int2bool v4) ];; which gives val t1 : bool list = [true; true; false] Let us extend myeq once again: let myeq x y = match (x,y) with (`T'int2bool'2bool (x : (int->bool)->bool), `T'int2bool'2bool y) -> x == y | _ -> myeq x y;; We can now write the table associating with each function a documentation string. We use an associative list of sorts: let docs = [(myeq (`T'bool v1), "bool value"); (myeq (`T'int2bool v4), "v4"); (myeq (`T'int2bool'2bool v3), "v3"); ];; let lookup x docs = let rec loop = function [] -> None | ((c,d)::t) -> if c x then Some d else loop t in loop docs ;; Another test: let t2 = [lookup (`T'int2bool'2bool v3) docs; lookup (`T'bool v1) docs; lookup (`T'int2bool v4) docs ];; which evaluates to val t2 : string option list = [Some "v3"; Some "bool value"; Some "v4"] We realize that we forgot about the function v2, which is of the type bool->bool. So, we extend myeq once again let myeq x y = match (x,y) with (`T'bool2bool (x : bool->bool), `T'bool2bool y) -> x == y | _ -> myeq x y;; and extend our documentation let docs = (myeq (`T'bool2bool v2), "negation") :: docs;; let t3 = [lookup (`T'int2bool'2bool v3) docs; lookup (`T'bool2bool v2) docs; lookup (`T'bool v1) docs; lookup (`T'int2bool v4) docs ];; which evaluates to val t3 : string option list = [Some "v3"; Some "negation"; Some "bool value"; Some "v4"]

Small comment: By transparently I meant "without any type annotation". Then I gave a solution using normal datatypes for annotations, and polymorphic methods, and just mentioned that GADTs were not useful in this case. Note that my solution cannot directly use polymorphic variants, as it uses non-regular types, and polymorphic variants have to be regular. But an interesting question is whether that solution could be made more modular, to enable extension with new type constructors. > It seems however that open polymorphic variants are ideal for the > task. We start with > let myeq (x : [>]) (y : [>]) = false;; [...] > We can add another clause, for int->bool functions: > let myeq x y = match (x,y) with > (`T'int2bool (x : int->bool), `T'int2bool y) -> x == y > | _ -> myeq x y;; [...] > Let us extend myeq once again: > let myeq x y = match (x,y) with > (`T'int2bool'2bool (x : (int->bool)->bool), > `T'int2bool'2bool y) -> x == y > | _ -> myeq x y;; While such a solution is appealing, there are drawbacks. 1) You have to add a new case for each new function type, rather than each type constructor. 2) In the open case, there is no static protection against mistyping a variant constructor. But you can check it dynamically: let type_handled x = myeq x x This will return true only if x's type is handled by myeq. 2) Polymorphic variant typing does not always play well with modularity. For instance, you cannot define an hashtable in a module, and add new cases no included in the original type in another module. For this reason, exceptions may be better for extension across modules. This said, I love polymorphic variants anyway...

Archive: http://groups.google.com/group/fa.caml/browse_thread/thread/e5e62301d39499bf/522a6fd5c26d69a6#522a6fd5c26d69a6

> I found an old thread[1] stating that Fermin Reig had replaced the > OCaml code generator to output QC-- instead of Mach. However, I am > unable to find this generator in the current OCaml sources. Does > anyone have links to this source code or any papers that elaborate on > this? > [1] http://groups.google.com/group/fa.caml/browse_thread/thread/cdff5128f6a2fa6b/1caa911cae4c6fc9?lnk=st&q=ocaml+to+C&rnum=9 The c-- generator is not part of the OCaml distribution. You can read about the implementation in my PhD dissertation, available from http://fermin.reig.googlepages.com/reig_phd_2002.pdf .

Archive: http://groups.google.com/group/fa.caml/browse_thread/thread/c2b0a94059b929e8/1d432f8880bb4336#1d432f8880bb4336

While searching Google for info about memoization I found this Slashdot post: http://developers.slashdot.org/comments.pl?sid=142494&cid=11942528 which states: I simply Googled for "memoization Ocaml" and found that code: http://www.emeraldtiger.net/modules.php?op=modload&name=News&file=article&sid=9 The author pointed out how "sweet" polymorphism is... one block of code that can be used to memoize any function. Unfortunately, the URL is dead. Does anybody have another link for that code or some other polymorphic memoizer?

I use the code below to show my students what can be done with higher-order functions. For a real implementation, we would have to use something more efficient than association lists (but then you might end up writing a polymorphic version of the Map module). Improvements are welcome. -------------------- (** [memo f] is a memoized version of function [f]. If [f] makes recursive calls, those are not memoized. In this example we use simple asociation lists. It would be better to use efficietn search trees. Alas, ocaml Map module is not polymorphic (for a good reason?). *) let memo f = let m = ref [] in fun x -> try List.assoc x !m with Not_found -> let y = f x in m := (x, y) :: !m ; y (** [memo_rec f] is a memoized version of a recursive function [f]. The recursive function must not make calls to itself directly, but rather via an extra "self" parameter, see example below. *) let memo_rec f = let m = ref [] in let rec g x = try List.assoc x !m with Not_found -> let y = f g x in m := (x, y) :: !m ; y in g (** [memo_test f stamp renew] is a memoized version of function [f], where [stamp] and [renew] are used to invalidate memoized values and force them being recomputed. For example, [f] could be a function which reads the contents of a file, [stamp] the function which returns the file's modification time, and [renew] the function which compares two modification times. Note that we keep storing new values in an association list without removing old ones, so this creates a memory leak. An intelligent implementation would, again, use efficient search trees. *) let memo_test f stamp renew = let m = ref [] in fun x -> try let y, s = List.assoc x !m in let t = stamp x in if renew s t then let y = f x in m := (x, (y, t)) :: !m ; y else y with Not_found -> let y = f x in let s = stamp x in m := (x, (y, s)) :: !m; y (** Example: the Fibonacci sequence, unmemoized, very inefficient. *) let rec fib_slow = function 0 -> 1 | 1 -> 1 | n -> fib_slow (n - 1) + fib_slow (n - 2) (** Example: a memoized version of the Fibonacci sequence. *) let fib_memo = let rec fib self = function 0 -> 1 | 1 -> 1 | n -> self (n - 1) + self (n - 2) in memo_rec fib

> The particular function I'm trying to memoize is a function of > two integers. I was hoping it might be possible to write a > memoize function that memoizes any function of a small arbitrary > number of parameters. Thinking about it some more I'm beginning > to this this is not possible. It is not very costly to give multiple parameters as a tuple. I think I remember reading that the native code compiler can do this without a heap allocation.

> Unfortunately, the URL is dead. Does anybody have another link for > that code or some other polymorphic memoizer? You may want to take a look at this paper by Bruce McAdam that uses a fix-point combinator to create all sorts of wrappers for functions, including memoization. The examples ore in SML, but translate pretty easily to OCaml. http://www.lfcs.inf.ed.ac.uk/reports/97/ECS-LFCS-97-375/

Here is a quick trick to help you read this CWN if you are viewing it using vim (version 6 or greater).

:set foldmethod=expr

:set foldexpr=getline(v:lnum)=~'^=\\{78}$'?'<1':1

zM

If you know of a better way, please let me know.

If you happen to miss a CWN, you can send me a message and I'll mail it to you, or go take a look at the archive or the RSS feed of the archives.

If you also wish to receive it every week by mail, you may subscribe online.