Hello
Here is the latest Caml Weekly News, for the week of September 05 to 12, 2006.
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.
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/
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".
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...
> 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 .
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/
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.