OCamlcore Planet

Thread safe heterogenous property lists (dictionaries) / Inside the mind of the inliner / New releases of Ocsigen server, Eliom and O'Browser / Blahcaml 2.0 and Camlhighlight 1.0 / OCaml-Java project: 1.4 release / Other Caml News

Quelle différence entre a→b→c et a→b→c? Pour le savoir, lisez ce qui suit.

De temps en temps, je regarde un article scientifique, ou un bout de code, et je n'en suis pas satisfait. Un truc me chiffonne, ça peut se réparer, mais ya autre chose qui cloche, et au fond c'est tout bancal, ça n'en finit pas, et il vaut mieux tout remettre à plat. Ceci est arrivé récemment dans liquidsoap avec le module de décodage de fichier. Ce n'est pas intéressant de détailler, il y a juste un point dont je voulais parler. Mais avant, je trouve que c'est important de dire qu'il faut remettre les choses à plat de temps en temps.

Donc, il s'agit de décodage. Première question: qu'est ce que c'est un décodeur? J'ai mis un peu de temps à essayer plusieurs styles, pour finalement décider input -> buffer -> unit, une fonction qui prend en entrée une méthode pour lire des données, et un buffer pour écrire le résultat du décodage, et qui ne renvoie rien mais remplit le buffer un peu plus à chaque fois qu'on l'appelle.

A côté de cette notion très générique on a des notions plus spécialisées comme le type file_decoder = { fill : Frame.t -> unit ; close : unit -> unit }. C'est un enregistrement qui contient une fonction de remplissage de flux (on lui donne une frame (un morceau de flux) à remplir) et une fonction de fermeture/nettoyage où l'on libère les ressources allouées pour le décodage.

Ceci étant décidé, j'écris un bout de code générique qui emballe un décodeur pour construire un décodeur_de_fichier:

let file_decoder filename decoder =
  let input = input_from_file filename in
  let buffer = create_buffer () in
  let fill frame =
    while not_enough_data_in buffer do
      decoder input buffer
    done ;
    fill_frame_from_buffer frame buffer
  in
    { fill = fill ; close = fun () -> close input }

Vous me suivez? Maintenant, j'implémente un décodeur, pour le format MP3 en utilisant la bibliothèque mad:

let create_decoder input =
  let resampler = create_resampler () in
  let mad_stream = Mad.openstream input in
    (fun buffer ->
       let data = Mad.decode_frame_float mad_stream in
       let sample_freq,_,_ = Mad.get_output_format fd in
       let content,length =
         resampler ~audio_src_rate:(float sample_freq) data
       in
         put_audio_in_buffer buffer content length)

PAF! Vous voyez le bug? Je parie que non, en tout cas moi je l'avais raté. J'ai réussi à ne pas être d'accord avec moi même, penser a→b→c ici et a→b→c là!...

Le problème, c'est les effets. En mathématiques, une fonction prend un argument et renvoie un résultat. On ne sait pas comment ça se passe "dedans", en tout cas ça n'interagit pas sur le "dehors", et ça se passe pareil à chaque fois: même entrée, même sortie. En informatique, c'est bien plus compliqué. La fonction interagit avec le monde, elle peut afficher quelquechose à l'écran, elle peut aller chercher un résultat sur internet, dans un fichier, ou simplement dans une case mémoire qu'elle partage avec d'autres fonctions. On est ainsi habitué à avoir tout un paquet de fonctions de type a→b, puisqu'il ne s'agit pas seulement de prendre un objet de type a pour calculer un objet de type b mais aussi potentiellement de se livrer à tout un tas d'interactions avec le monde.

Mon code utilise cela, mais se prend les pieds dedans. Ce qui est joli, c'est que j'ai une "solution". Mais voyons d'abord le problème. Notre décodeur prend un canal d'entrée (input), un canal de sortie (buffer), et est supposé avoir comme effet de lire un peu de données en entrée, de les convertir et les écrire en sortie. Il ne renvoie rien d'utile (unit), tout son interet réside dans l'effet; si on l'appelle un assez grand nombre de fois, on finit par avoir assez de données dans notre buffer -- c'est ce qu'on a fait plus haut. On peut cacher un certains nombres d'informations dans le décodeur, c'était mon intention, par exemple j'y ai alloué un resampler pour convertir les données vers la bonne fréquence d'échantillonage: cet outil doit être (et est bien) crée une fois et une seule pour chaque décodeur.

Ce resampler maintient un état interne, tout comme le décodeur mad (mad_stream). Allouer ces objets est aussi un effet! Mais à quel moment a-t-il lieu? Le type ne l'indique pas: dans input->buffer->unit, après quel argument un effet peut-il avoir lieu? Dans le code de file_decoder j'utilise un décodeur comme si le seul effet était le décodage, qui a lieu une fois qu'on a renseigné l'input et l'output. Mais dans le code du décodeur MP3, pas le choix, je m'autorise un effet entre le moment où on m'a donné l'input et le moment où on me donne le décodeur. Résultat, quand on utilise file_decoder avec le create_decoder MP3, on a un son tout haché, car le décodeur et le resampleur sont reinitialisés sans arrêt, ce qui provoque la perte d'une partie des données mémorisées dans leurs buffers internes.

Ces problèmes sont très vicieux, et sont toujours un sujet de recherche active. Mais concrètement, que peut-on y faire avec les outils d'aujourd'hui? Documenter, espérer que tout le monde se comprend? Pas terrible, j'ai réussi à être en désaccord avec moi-même sur une courte période de temps. Comme d'habitude, ce serait bien si le système de type nous servait de garde fou.

En logique, la notion de focalisation (focusing) est liée à la question des effets. Une formule logique est vue comme un jeu entre deux joueurs: un qui prouve l'autre qui réfute, ou encore, l'environnement qui fournit une entrée (argument) et la machine qui renvoie une sortie (valeur de retour). Les connecteurs logiques sont attribués à l'un ou à l'autre joueur: dans (int*int)→(int*int) c'est d'abord l'environnement qui donne un argument, directement composé de deux entiers; puis la machine calcule un résultat, directement composé de deux entiers. Ici je dis directement, car on ne peut pas demander une réponse partielle à la machine, tout ceci vient d'un coup, une unique réponse à une seule question. La dynamique associée au type int→int→(int*int) est exactement la même: il n'y a pas deux questions à l'environnement, mais une seule, les deux entiers en entrée arrivent d'un coup. Là dedans, les seuls effets ne peuvent donc se situer qu'à l'interface entre les deux joueurs, dans le calcul qui se passe entre une question et une réponse.

Commençons à redescendons sur terre. Pour introduire la possibilité d'un effet, en focalisation, on peut introduire un délai. Par exemple, si on veut une paire d'entiers paresseuse (dont le contenu n'est calculé que si nécessaire), on retarde le calcul des int: (unit->int)*(unit->int). Dans l'autre sens, on peut aussi vouloir retarder le moment où un argument est passé, par exemple avec a->(unit*(b->c))... c'est ce qu'il nous faut!

On la refait avec un délai autour du décodeur, implémenté non pas comme (unit*...) mais plus agréablement avec un type variant:

type decoder = Decoder of (buffer -> unit)
type file_decoder = input -> decoder

let file_decoder filename decoder =
  let input = input_from_file filename in
  let buffer = create_buffer () in
  let Decoder f = decoder input in
  let fill frame =
    while not_enough_data_in buffer do
      f buffer
    done ;
    fill_frame_from_buffer frame buffer
  in
    { fill = fill ; close = fun () -> close input }

let create_decoder input =
  let resampler = create_resampler () in
  let mad_stream = Mad.openstream input in
    Decoder (fun buffer ->
       let data = Mad.decode_frame_float mad_stream in
       let sample_freq,_,_ = Mad.get_output_format fd in
       let content,length =
         resampler ~audio_src_rate:(float sample_freq) data
       in
         put_audio_in_buffer buffer content length)

Le code du décodeur MP3 n'a changé que d'un iota, mais cela suffit à forcer sa bonne utilisation dans file_decoder, c'est à dire à passer l'input une fois pour toute, et ne plus passer que le buffer dans les appels suivants. Vraiment? Non, à vrai dire, on peut toujours se prendre les pieds dedans, ne serait-ce que parce que c'est possible de traduire entre le vieux type de décodeur et le nouveau, en violant ainsi la logique qu'on a tenté de forcer. Mais en pratique, ce petit garde fou pousse à faire naturellement la bonne chose, ou au moins à se poser la question.

Tout est bien qui fini bien. Cette histoire pourrait aussi s'intituler "à quoi diable pourrait bien servir un type variant avec un seul constructeur?" Ou encore, "c'est fou comme de belles idées théoriques ont du sens même en dehors de leur strict cadre théorique."

Last year, I was not able to attend FOSDEM due to last minute problems. However, this year I will be there and even attend the Debian for some periods ([http://wiki.debian.org/DebianEvents/FOSDEM/2010]).

I will bring my Openbrick NG with a standard Debian Lenny and probably a Babelbox installation. The Openbrick is a VIA C3 fanless computer. It is not very exotic but it is quite interesting to see this kind of hardware. For years, I have tried to build/use fanless computer. This is not a very popular topic but it introduces problems of heat and noise at a higher level.

I am still setting up the Babelbox, which should have been a Debian Lenny RC1. I will try to upgrade it to Debian Lenny 5.0.3.

See you at FOSDEM 2010.

Thanks to the translation of Eric Cooper and the proofreading job of Prashanth Mundkur, the threads chapter of Xavier Leroy and Didier Rémy's course on Unix system programming in Objective Caml is now available in english for your reading pleasure [1]. [1] http://ocamlunix.forge.ocamlcore.org/threads.html

I used bitstring to reverse engineer the Windows registry “hive” format. I know that bitstring is my own program, but coming back to it two years after I wrote it and using it again for this, I really think this is a brilliant tool. (Bitstring wasn’t my idea — it was inspired by the bitstring manipulation feature in Erlang).

C is supposed to be a good natural programming language for dealing with bits and bytes, right? The ocaml-bitstring program, which analyzes hive files in far more detail than the C program, is half the size and just as fast.

As an example, here’s how we load the hive file and analyze the first part of the header:

let bits = bitstring_of_file filename

(* Split into header + data at the 4KB boundary. *)
let header, data =
  takebits (4096 * 8 ) bits, dropbits (4096 * 8 ) bits

let () =
  bitmatch header with
  { "regf" : 4*8 : string;
    seq1 : 4*8 : littleendian;
    seq2 : 4*8 : littleendian, check (seq1 = seq2);
    last_modified : 64
      : littleendian, bind (nt_to_time_t last_modified);
    1_l (* major *) : 4*8 : littleendian;
    minor : 4*8 : littleendian } ->
      (* ... *)

The bitmatch statement elegantly matches the file. It rejects the file if the first four bytes aren’t “regf” (the file magic number) or if the major version number is not 1. It then unpacks the following fields, converting from the file’s littleendian ordering to host ordering, converting the NT timestamp into a time_t and so on.

Although not shown there, bitstring will also work just fine on arbitrary bit boundaries, albeit more slowly because the generated code is able to make fewer optimizations.

Even though the Windows hive file format is moronic, I successfully used bitstring to reverse engineer it in about 3 days, with some help from the contradictory and often incorrect public documentation out there.

I've already wrote something about OptParse last month. Today I discovered how to create a new option (that is not a string, int or bool) and validate it within the arg parser.

So suppose we want to write an application that can output both txt and html and we want the user to specify the format with command line option. One way would be to use a StdOpt.str_option - eventually with a default option - and to retrive it in application code with OptParse.Opt.get.

However this is not satisfactory as we are mixing the application code with command line parsing. A better way is to create a new type of option with Opt.value_option .

This is the concept :

Note that the function Opt.value_option get a default value, a metavar - that is the sting associated with the option in the help (  -o<txt|html>, --out=<txt|html> Output type ), a corce function, that is, a function that transforms a string in the desired type, and an error function that is used by the parser to give a meaningful error is the option is not correctly validated.

For example :

Now when we use this new option in the application code with OptParse.Opt.get and we can be certain that it was correctly validated.

Biniou is a fully extensible serialization format, more compact and "faster" than JSON. Applications include exchanging and storing records containing large blobs of data such as images or non-UTF-8 text.

Format syntax extension / Other Caml News

Every now and then I need to write a simple combinatorial algorithm. Using monads this is fairly easy and concise, but probably not the fastest way to do it. We start with the definition of a few functions in terms of the List module. The function themselves are kinda of self explanatory. I write this mostly for reference then for real added value.

The previous version of the code uses the List module. If we want a more space efficient implementation of the same functions, we can use a lazy data structure and substitute the functions in the preamble. In this case, instead of writing a lazy list module from scratch, we simply use the Enum module of ExtLib.

In action :