O'Caml Code

Most of the code depends on OcamlMakefile. Download it and put it somewhere globally. Change the first row in the Makefile to point at it. All projects can share the same OcamlMakefile.

• I made a program that parses W3C HTML 4.01 specifications and generates code to generate correct HTML-code. The generated HTML-code is type checked by the O'Caml-type checker. Thanks to Alain Frisch it is now included in the Bedouin-project.

• Implementation of "Minimal perfect Hash Function". The algorithm is by Rasmus Pagh, Hash and Displace: Efficient Evaluation of Minimal Perfect Functions. (code). It maps ints to ints. 
  However, during the implementation I learned that the storage overhead is at least 2 times the number of keys. Thus, traditional hashing with linear probing is probably better. Rasmus also suggests cuckoo hashing.

• Suffix arrays are very efficient for fast string searching in big texts. I implemented a first nice version, which took 40 s to run on my P4 when applied to the bible (4.5Mb). However, a colleague implemented it using Java. His code only takes 15 s to run. Thus, I had to further tune the code by replacing compare with -, inlining better and removing bound-checking on strings and arrays. The new version runs in 10 s. This is the first time I got beaten by Java, I will have to reevaluate Java.

O'Caml Lessons

I have been programming O'Caml since May 2000. If you do as I say below, you will spend much less time debugging your O'Caml-programs than I do/did.

• Read documentation carefully before sending bug report. 
  There is a big difference between Str.regexp and Str.regexp_string.

• Simple tail-recursive functions are the fastest. 
  Don't spend time creating for-loops with exceptions or inner recursive functions. See the file other_compares.ml for concrete examples.

• Try to make the return type explicit. 
  By writing 'f a b : int', you will find missing argument errors much easier.
• Don't forget the '- 1' in for-loops.
• Add lots of assert.
• Use O'Camldebug to understand why your asserts failed. You should use the cygwin-version on Windows during development.
• Use records, do not use tuples. 
  By having a lot of fst and snd in your code, you loose a lot of the type checking advantage.
• O'Caml isn't a pure language! There are side-effects.
  When you change strings and arrays, if the original string is still needed, don't forget to copy it before destroying them.
• Array.sort sorts in-place!
• Always let Emacs indent!
  Otherwise code using if-then-else and match might not do want you think.
• Don't write let _ = xxx if you know it should be let () = xxx
• Add  'flush stdout' after debug outputs.
  If you get an assert the output buffer will not be emptied, so you might actually think the program fails earlier than it does.
• Use a Makefiles, for example OcamlMakefile.