Caml Weekly News Previous week Up Next week

Hello

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

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

O'Caml link db moved

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

Gerd Stolpmann announced:
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. 
			

Olmar - almost a C++ parser for Ocaml

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

Hendrik Tews announced:
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/ 
			

autoconf macros, first round

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

Guillaume Rousse announced:
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.)
			

3.09.3 release candidate 2

Damien Doligez:
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".
			

Comparing two things of any two types, in pure OCaml

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

Oleg said:
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"] 
			
Jacques Garrigue then said:
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... 
			

OCaml and Quick C-- Output

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

Sachin Shah asked and Fermin Reig answered:
> 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 .
			

Memoization

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

Erik de Castro Lopo asked:
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?
			
Andrej Bauer answered:
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
			
Erik de Castro Lopo then asked and Mike Lin answered:
> 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.
			
William Neumann answered the original post:
> 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/
			

Using folding to read the cwn in vim 6+

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.


Old cwn

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.


Alan Schmitt