Design III: Liquidsoap tomorrow?

In the previous post we've seen the problems with the current source at the core of liquidsoap. The point of doing so was to highlight the interest of a more principled design.

We could start with a mathematical notion of stream, but we haven't reached that point yet. As I've illustrated before, sources are inherently interactive objects, which is hard to account for.

Instead, I'll keep the same practical notion of source but do one simplification: we'll work sample by sample. We'll have a #is_ready method that tells whether the source can produce a sample for the current instant. A source is always ready when it is in the middle of a track. And we have the #get method which returns at most one sample, none when the current track ends, and should never be called unless the source #is_ready.

As before, a source is passive by default (it doesn't produce data when not asked to) and caching mechanisms ensure that a source gives consistent answers to several observers. Depending on how/when it is used, a source will generate a stream, possibly undefined at some instants, but otherwise containing samples, metadata and end of track markers. Note that we need more precision than just time to denote a point in such a stream, in order to be able to tell the position relative to end of tracks -- it is possible to have several consecutive end of tracks exactly at the same point in time.

Let us detail caching, which isn't totally trivial. What do we cache: a number N of end of tracks, corresponding to partial #get, possibly followed by a sample. How do we use that cache: for an operator which already had M end of tracks and performs a #get, we return an end of track if M<N, the sample otherwise.

In the current liquidsoap, this M is passed as part of the frame, but there is no way to track which source has produced which end of track. Hence it is possible that M>N, for example in case of a switch which has seen many empty tracks before switching to that source. Even when M<N, it makes it unclear how many end of tracks we should add. I'm not sure whether it is crucial that we keep precise track of who produces which end of track.

What matters is (1) if you listen continuously to a stream, you get exactly all its content and (2) we don't have the first problem with sharing. This is because various operators of a source can only get data at one instant. If I pump it, the source will generate (or find in its cache) an end of track or a sample. It's as simple as this, there's no bad side-effect here. We don't even need to worry about sharing detection, because we can perform caching all the time without changing the stream content -- efficiency isn't an issue for now. (At some point I was worried that sub-instantaneous data is in the cache, i.e. end of tracks, could lead to the same problem as before, but it does not make sense because this data can't be refered to without first generating it: you can't pump a source "after" it has generated end of tracks, you can only pump it, ignore end of tracks, and pump it again.)

For our second problem, we would simply cache the result of #is_ready (rather, rely on the same cache). As with #get, we need to know the number of end of tracks already obtained by the observer to tell him if the source is ready at that precise point.

Some minor remarks:

• We can't distinguish a source that is in the middle or just before the beginning of a track. If you don't listen to a source for a while, and the source is ready when you come back to it, there's no way to know if it is about to start something new or if you missed the beginning of the current track. It's never been a problem, I'll assume we can keep living with it.
• The implementation of end-of-track notification is still a "partial" #get which may be too ad-hoc. The alternative is to attach an end-of-track tag to the last sample. Looks like a meaningless choice to me.
• Note that metadata and end-of-tracks are treated very differently: we never issue a partial #get because of metadata. It corresponds to a view where, end of tracks are "after" the last sample, while metadata is "before" or maybe "inside" samples. We should try to generalize this into a nice notion of event, some being interruptions, some not.
• With Samuel, we have explored other design choices. What I present here isn't his favorite, but it's the most convincing to me. It also has the advantage of being fully defined (at least in my mind).

This new model is not revolutionary. But we gained more than it seems. For example, we can now write an operator that takes two sources and sums them, only producing data when both of them are ready, and not pumping any of them when none is ready. The reason is that in the old frame-based design, we can only get data until either the end of a frame or the end of a track. But if one source ends a track, the other will still fill a frame.

Lifting to frames

The real challenge now is to derive an efficient frame-based model that faithfully reflects the simply sample-based model.

I'll start with the biggest problem: sharing. We can't approximate it anymore, or we'll obtain the same problem. Hence I'm going to propose a two-phase pumping: In a first abstract phase we do a dry run of the pumping methods to know who pumps who at what instant. Then we have a precise picture of the sharing and we can do a real run, computing the actual stream content.

This method forbids some source behaviors: for example if a source acts differently based on the actual values of its input samples, it cannot meaningfully take part to the first phase. That would be a problem with a blank detection source. I believe we can relax this enough to get what liquidsoap currently does. The key is to declare some values as "sparse" or "slow", allowing the change of the value (and hence the reaction of the source) to only take place at the end of the frame. For example blank detection would set a flag that only takes effect for the next frame.

For most sources I want to automatically generate the #simulated_get method from a simple #get. This is why compilation is needed now.

Now, I believe I can run that simulation thing. The nice thing is that once I bite the bullet and decide we need this, there's no question about being more modest in other places. In particular, the new #is_ready will be asked not only if a source is ready at a particular point but for how long. This enables a nice frame-based implementation of the precise sum operator described above. Of course, it goes with a #get that takes not only a start but also a stop position.

Plans

There are several things we can do now:

1. Compile frame-level sources from sample-level sources written in OCaml. This is only about analysing the source, and it does not need be user-friendly. There are a couple tricky analysis to run. For example, a sine source will have a counter decremented at each sample and reset after an end of track, and we'll have to turn this into the natural code for the frame-level sine.
2. Extend liquidsoap scripts with a notation for sources and compile it down to OCaml objects. We'll have to ensure that the user never sees a type error coming from OCaml, but only errors from us, which should be more readable. The main extra challenge is to run liquidsoap code fast. Some of it can be compiled directly to OCaml but function calls won't match exactly. We'll have to inline or leave some interpreter calls.
3. Do cross-source optimizations on top of the previous work. If the user writes a sum of sine sources, inline it into a source that computes directly the sums.
4. Compile to C or even lower level code.

I gave a rather precise proposal of what Step 1 could look like. Still we can discuss some points, try to generalize a few things. My proposition doesn't look as clean as I would like in some places, but it has one great advantage: I'm sure we can program liquidsoap sources with that model, and even do some things currently impossible.

Step 2 presents even more design choices: should users write sources in an OO style like we do? should they work with an explicit notion of time? should time be discrete or continuous?

Design II: Liquidsoap today

In this post, I will give a high level picture of the current internals of liquidsoap, show a few problems with them. The interested reader can read further details on the design of liquidsoap in our papers. In the next post, I'll finally describe a better future for liquidsoap.

The source protocol

In order to get a minimum understanding of liquidsoap's streaming model, let us consider the following example:

output(fallback([queue,playlist]))

What we want here is to produce a stream either from the playlist or the queue of requests, and output it somehow. The fallback between our two sources only switches from one to the other for new tracks. For example, if the queue becomes available while we are in the middle of a playlist track, we'll keep playing the playlist track, and only switch to the queue for the next track. In order to obtain the expected behavior this means that (when possible) unused sources are (almost) frozen in time: the queue doesn't start playing its request until the fallback asks it to do so. The stream of a source isn't defined in itself, but computed in interaction with the source's environment. Simply put, it's on-demand streaming.

Now what happens concretely. Streaming is clocked, and at each cycle of the clock we produce a frame, which is simply a buffer of samples (audio, video or MIDI) of fixed size/duration. The filling of the frame starts from the outputs: Our output passes the frame to the fallback, which passes it to the source that is currently playing a track, the frame is filled, passed back to fallback, which passes it back to output, which outputs the frame to the world.

Sometimes, it'll be a little different: When the child source of fallback ends its track, it won't completely fill the frame, which gives the opportunity for the fallback to select another source. The newly selected source isn't used right away. Instead, the partial frame is returned to the above operator, in our case the output, which passes it back because all it wants is a complete frame -- the story would be different with nested fallbacks. When the partial frame comes back, its filling is completed by the newly selected source.

We perform that kind of computation by having sources communicate with each other using just a few methods: we mainly have #get for filling a frame and #is_ready for knowing if a source has a ready track (ongoing or not).

All this works smoothly when sources are organized along a tree, i.e., when there is no sharing. But we really want sharing, as seen in the following example:

source = fallback([queue,playlist])
output_1(source)
output_2(source)

This means that at each cycle of the clock, the source will be asked twice to fill a frame with a segment of its stream. Of course, the source should give the same data twice: we don't want to split our stream among the two outputs, one frame each. To deal with this, we have some caching mechanisms in #get. In more details, we create new sources by inheriting from a base class which defines #get as a public method wrapping the virtual private method #get_frame which can be written without thinking about sharing at all.

Problem #1

Caching everything is really costly, so we have to detect when sharing is needed. The problem is that sometimes, it's not easy to tell statically:

output(
  switch([
    ({am},fallback([queue,am_playlist]),
    ({pm},fallback([queue,pm_playlist])]))))

Here it looks like the queue is shared, but in fact the first occurrence can only be used in the morning (am), the second only in the afternoon (pm). While we could try to detect some of those cases, it is hopeless to catch them all. So we're bound to over-approximate sharing. This has been done, and isn't too complicated, although it does introduce some activation/deactivation methods that must be used carefully, especially when using transitions. This is okay regarding performance, but it has one nasty side effect: the approximation can have an impact on the stream!

The scenario is as follows: Take a source S which looks like it could be used by operators A and B. Now A asks S to start filling a frame from the middle (it happens, cf. the fallback example above) but the source sees that it could be also be used by B, perhaps to fill a frame from the beginning. So S fills in its cache from the beginning, and copies the part of it that starts from the middle in A's frame. But if B never uses S, we'll have modified our behavior for nothing.

Problem #2

An even worse problem is that we implemented some caching mechanism for #get but not #is_ready. Now, it is possible that a source fills its cache, has no new track to produce, and hence declares itself as not ready. Which might not be correct from the viewpoint of an operator that wants to access the data from the beginning of the cached frame. As a result of this weakness, I recently had to allow what should be illegal behavior in some operators that rely quite precisely on the readiness of their sources. Of course, this is a slippery slope.


Next time, I'll describe a simple way to construct a better source protocol from first principles, avoiding those problems, and even getting more expressiveness by the way. On the other hand, it'll have to be compiled. Stay tuned.

Liquidsoap: retour aux sources

Vous savez sûrement que je passe cette année aux Etats Unis et plus précisemment à Minneapolis, Minnesota. Mais savez-vous vraiment pourquoi? C'est dans cet Etat qu'a été inventé le savon liquide! C'est donc logique que je m'isole ici pour me recueillir et bourriner sur liquidsoap le logiciel.

Quel effet ça fait

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."

Dynamisme=échec

Petite update sur le post précédent.

Après la dernière modification, je me suis rendu compte que je ne prenais pas la linéarité assez au sérieux dans la version actuelle. J'ai essayé de corriger ça, mais je n'ai pas réussi à concilier linéarité et convivialité du système de types (i.e., pas d'annotation barbare).

La morale est qu'il n'y aura probablement pas de vérification statique du boxing temporel dans liquidsoap 1.0. Ce n'est pas la mort du petit cheval, on a déja une vérification dynamique pour la fallibilité (faite à l'instantiation d'une source). J'espère donc trouver le temps d'implémenter une vérification dynamique du boxing, ce serait largement mieux que le rien actuel.

Mise en boîte

Depuis un bon moment, liquidsoap dispose d'un langage de configuration/script fonctionnel, fortement et statiquement typé, qui infère des types à la ML, le tout à l'insu de la plupart des utilisateurs. Pour liquidsoap 1.0 nous irons plus loin dans l'utilisation de concepts avancés avec (un peu) de vrai polymorphisme.

J'ai édité ce post deux ou trois dans les jours suivant sa publication. Peut-être que le blog n'était pas le format idéal.

Pourquoi?

Dans une conf liquidsoap, les fonctions sont parfois utiles pour éviter de recopier du code, ou pour spécifier une action à effectuer en réaction à certains évenements. Mais au coeur même de la génération du flux, les fonctions sont utilisées pour représenter les transitions entre pistes audio. (Détails ici.)

Cette même notion de transition pose des problèmes quant à l'écoulement du temps. Actuellement dans liquidsoap, toutes les sources de flux audio évoluent à la même vitesse, cadencées par une unique horloge. Pour calculer une transition entre deux pistes d'une même source, l'opérateur cross doit obtenir en avance le début de la piste suivante, et le combiner avec la fin de la piste en cours. Cela requiert d'accélérer cette source.

L'implémentation actuelle n'est pas une solution: Les opérateurs qui en ont besoin simulent l'action de l'horloge auprès de leur source, afin de l'accélérer. Cela marche souvent, mais il se peut que deux opérateurs lisent une même source à des vitesses différentes. Le résultat est inattendu, à éviter. Notre mission est d'éviter cela statiquement, avant même la construction des sources. Nous allons donc attacher un paramètre au type des sources, qui représentera son horloge, et spécifier dans le type des opérateurs s'ils requièrent des horloges particulières.

S'il est assez facile de bricoler le système de type pour obtenir l'effet désiré, il faut d'abord identifier les concepts "logiques" mis en jeux. J'ai honte, mais ça m'a pris du temps, car j'ai commencé par chercher dans des contrées exotiques alors que c'est assez connu, bien que pointu.

Polymorphisme

Le polymorphisme est la possibilité de former une quantification universelle sur les types. Si on a un objet de type ∀x. x->x, on peut l'instantier en une fonction de type int->int aussi bien que (bool->bool)->(bool->bool).

Dans les langages dérivés de ML, le polymorphisme est limité à une quantification externe. On peut avoir ∀x. x->x mais pas (∀x. x->x)->int->int. Le polymorphisme dans toute sa généralité, par exemple dans le système F, rend en effet l'inférence de type indécidable.

OCaml permet cependant d'aller un peu plus loin. La clé est que la création d'un type polymorphe doit être explicite dans le programme (cf. ce papier), par exemple associée à la création d'un enregistrement. Considérons la signature suivante:

(** Une source associée à l'horloge 'a *)
type 'a src

(** Une fonction qui renvoie une source qu'on peut
* associer à n'importe quelle horloge. *)
type boxed = { c : 'a. unit -> 'a src }

(** Cet opérateur prend une source en boîte,
* cela pourrait être le cross() de liquidsoap. *)
val box : boxed -> 'a src

val leaf : unit -> 'a src (* en gros, single *)
val node : 'a src list -> 'a src (* en gros, fallback *)

Voyons voir ce qu'on peut et ne peut pas faire avec ce système. On peut créer un certain nombre de sources avec leaf () initialement, elles auront le type '_a src: leur horloge est indéfinie, mais pas généralisable. On est content de ne pas voir de 'a src: cela correspondrait à une source qui peut se brancher sur toutes les horloges à la fois, non-sens. (C'est aussi pour cela qu'on n'a pas écrit boxed = { c : 'a. 'a src }, on n'aurait jamais pu construire de boîte.)

On peut passer une source de type '_a src à notre opérateur node, on obtient une autre source à la même horloge '_a. Si on passe deux sources à node, le système de type requiert que leurs horloges soient les mêmes (des inconnues '_a et '_b sont unifiées).

Maintenant, tentons de former des boîtes:

let b = box { c = leaf }
(* Gagné:
* une boîte qui nous donne une nouvelle feuille à chaque fois,
* horloge au choix. *)

let a = leaf ()
let b = box { c = fun () -> b }
(* Raté, erreur de type:
* la source a est de type '_a src,
* la fonction (fun () -> b) est de type unit -> '_a src,
* qu'on ne peut généraliser en 'a. unit -> 'a src. *)

let b =
box { c = fun () ->
let a = leaf () in
node [a;a] }
(* Gagné, on a une boîte qui nous renvoie une source composée,
* dont on peut choisir l'horloge. *)

On tient clairement le bon concept: le polymorphisme assure que l'horloge peut être choisie. En particulier on va pouvoir créer des nouvelles horloges dédiées à certaines sources (et leurs sous-sources). Reste à transférer ce petit exemple en quelquechose d'agréable à utiliser dans liquidsoap.

Liquidsoap 1.0

Actuellement dans liquidsoap, on écrit des choses comme:

music = playlist("list.txt")
backup = single("default.ogg")
source = fallback([music,backup])
transition = fun (a,b) -> ...
source = cross(transition,source)
output.icecast(source)

En collant au style de notre exemple en OCaml, nous devrions réécrire les choses ainsi:

transition = fun (a,b) -> ...
source =
cross(transition, {
music = playlist("list.txt")
backup = single("default.ogg")
fallback([music,backup])
})
output.icecast(source)

C'est trop lourd, et ma solution ne va différer que d'un epsilon du style courant:

music = playlist("list.txt")
backup = single("default.ogg")
source = fallback([music,backup])
transition = fun (a,b) -> ...
source = cross(transition,{source})
output.icecast(source)

Un point clé qui permet cette simplification est qu'on n'a besoin que d'une partie du polymorphisme: on veut la généricité, mais une seule fois. Pas besoin d'une fonction qui à chaque appel pond une source, comme dans l'exemple en Caml. Il suffit d'une seule source, tant que son horloge est générique.

Je pense qu'on ne peut pas se passer aisément du marqueur {source} qui indique qu'on généralise cette source. Il me semble acceptable de demander à l'utilisateur de marquer le coup quand il utilise cette notion complexe. (Par contre il va nous falloir choisir une syntaxe qui ne rentre pas en conflit avec l'actuel {...}, raccourci pour fun () -> ....)

Comment ça marche

J'ai une implémentation en OCaml qui me semble transposable à liquidsoap.

Comment OCaml vérifie-t-il que { c = fun () -> blah } est bien typé? Il introduit une nouvelle variable de type n pour représenter le 'a de 'a. unit -> 'a src, et vérifie qu'on peut donner le type n src à blah.

Nous allons faire la même chose, mais dans le désordre, pour permettre le genre d'écriture promis plus haut. Pour former une boîte (un type universel) sur une source, il faut que son horloge soit encore indéterminée. On vérifie cela en unifiant le type de cette source avec n src pour une nouvelle variable de type n comme OCaml faisait. Et une fois qu'on a ainsi réussit à former une boîte, on affecte cette variable à type à une valeur interdite Boom pour empêcher son utilisation ailleurs. Au lieu de créer les sources dans une zone protégée, on les crée en dehors, et on les y affecte après coup, ce qui rend alors leur horloge dénuée de sens à l'extérieur.

Un difficulté essentielle du polymorphisme vient du fait que pour inférer, on a besoin de savoir quel type universel on forme. Dans le cas de liquidsoap ma solution est très simple: on ne forme que ∀x. x src. On pourrait avoir d'autres types polymorphes, mais chacun aurait son constructeur particulier.

Ces mécanismes fonctionnent bien sur quelques exemples disponibles dans mon code:

ex0 = single ()
ex0 : '_a src # pas de généralisation, c'est comme avec ref

ex00 = let x = single () in {x}
ex00 : 'a. 'a src

ex1 = fun (x) -> cross(x)
ex1 : 'b. ('a. 'a src) -> 'b src

ex4 = fun (_) -> cross({single("blah.ogg")})
ex4 : 'a.'b. 'a -> 'b src

Un exemple plus subtil est ex2 = fun (x) -> {x}, ou la variation ex4 = fun (x) -> cross({x}) qui se rapproche de ex1. Ici une boîte est formée sur l'argument de la fonction, qui doit donc être une source. Ce genre de construction est problématique: la source doit être introduite avant son horloge. En pratique, cela se traduit par l'impossibilité de former le type de la fonction où devrait apparaitre le symbole interdit: Boom src -> 'a. 'a src.

La vraie vie

Le regard varie selon l'humeur. Je me suis plutôt bien accomodé de ma situation de visiteur de passage à Pittsburgh. Par exemple, après la morne absence de café à la maison, je me suis mis au soluble: wouahou, carrément mieux que rien quand on a pas envie de sortir pour petit-déjeuner. Mais bon, là je m'en lasse, et ça me fait penser à une chanson d'un groupe d'ici.


(Ici, il y avait une vidéo, mais le lien ne pointe plus sur la bonne alors fuck off.)

Sinon, vous pouvez lire:

• Crap art: The creation of art is more important than its consumption.
• Watchmen, le livre pas le film, et surtout l'auteur Alan Moore.

Si vous trouvez ce post vide, disons que c'est du micro-blogging, c'est à la mode... (même liquidsoap est dans le coup).

De la webradio lambda à la λ-webradio

Un article sur quelques aspects théoriques de la conception de liquidsoap, par Samuel et moi-même, a été accepté aux Journées Francophones des Langages Applicatifs (JFLA08). Sous un titre suivant la tradition blagueuse des JFLA (e.g., Le foncteur sonne toujours deux fois) nous présentons le modèle de flux sur lequel sont construits les opérateurs de liquidsoap, puis formalisons le langage de script propre à notre outil. Ça nous change des articles purement techniques, et ça vous changera de la doc des outils de tous les jours: jetez-y donc un oeil!

Linux Mag

Bravo à Romain qui est sur la couverture de Linux Magazine ce mois-ci, avec un article sur l'équipe Savonet qui développe un machin appelé Liquidsoap... la suite dans le numéro de Novembre!

Notification de bonnes vacances

Aujourd'hui est mon dernier jour au labo pour cette deuxième année de thèse. Je vais limite avoir du mal à arrêter de bosser, avec toutes ces questions excitantes qui tournent encore dans ma tête, tous ces trucs à écrire. Pour m'aider à décrocher (hum..) j'ai décidé de passer la journée à coder dans liquidsoap, en me concentrant sur deux-trois trucs chiants et pas du tout glorieux, qui ont trait à l'auto-documentation des fonctions définies dans les scripts liq. Cela devient important à mesure que nous accumulons de petites snippets sympas.

Par exemple, j'utilise liquidsoap pour écouter ma musique, et pour écouter Dolebraï (sur laquelle je mixe les interventions de balbinus sur sa number station). Dans les deux cas j'utilise deux petites fonctions pratiques: je parlerai plus tard de la platine interactive qui permet d'appliquer quelques effets audio, quand elle sera finalisée; l'autre fonctionnalité est un petit hack pour afficher à l'écran les metadonnées du flux joué par liquidsoap.

Le principe est simple: attacher à l'évenement on_metadata une fonction qui exécute la bonne commande. Quelle que soit la méthode, il va tout d'abord nous falloir une fonction pour transformer la métadonnée en chaine de caractères.

# Standard function for displaying metadata.
# Uses "Unknown" when a field is empty.
# @param m Metadata packet to be displayed.
def display_metadata(m)
  artist = m["artist"]
  title  = m["title"]
  artist = if ""==artist then "Unknown" else artist end
  title  = if ""==title  then "Unknown" else title  end
  "#{artist} -- #{title}"
end

OSD (On Screen Display)

OSD est une technologie ancestrale de X. On peut l'utiliser simplement avec l'utilitaire osd_cat qui affiche à l'écran (au dessus de toutes les fenêtres) le texte passé sur son entrée standard. Le problème est que les polices ne sont pas lissées, et qu'il est difficile de trouver une couleur de texte lisible quel que soit le fond au moment de l'affichage. Néanmoins, c'est un début..

# Use X On Screen Display to display metadata info.
# @param ~color    Color of the text.
# @param ~position Position of the text (top|middle|bottom).
# @param ~font     Font used (xfontsel is your friend...)
# @param ~display  Function used to display a metadata packet.
def osd(~color="green",~position="top",
        ~font="-*-courier-*-r-*-*-*-240-*-*-*-*-*-*",
        ~display=display_metadata,
        s)
  osd = 'osd_cat -p #{position} --font #{quote(font)}'
      ^ ' --color #{color}'
  def feedback(m)
    system("echo #{quote(display(m))} | #{osd} &")
  end
  on_metadata(feedback,s)
end

Notify

Notify est une technologie plus moderne émanant de l'intiative freedesktop. Elle est donc disponible avec les gestionnaires de bureau principaux, notamment gnome, kde et xfce. Si ça se trouve on peut même l'utiliser indépendamment du gestionnaire de bureau, mais l'idée ici est que l'intégration permet un comportement plus riche et agréable, ainsi qu'une apparence unifiée. Bref. Encore une fois on a un petit outil simple en ligne de commande: notify-send. Et ce n'est pas plus compliqué à utiliser depuis liquidsoap:

# Use notify to display metadata info.
# @param ~urgency Urgency (low|normal|critical).
# @param ~icon    Icon filename or stock icon to display.
# @param ~time    Timeout in milliseconds.
# @param ~display Function used to display a metadata packet.
# @param ~title   Title of the notification message.
def notify(~urgency="low",~icon="stock_smiley-22",~time=3000,
           ~display=display_metadata,
           ~title="Liquidsoap: new track",s)
  send = 'notify-send -i #{icon} -u #{urgency}'
       ^ ' -t #{time} #{quote(title)} '
  on_metadata(fun (m) -> system(send^quote(display(m))),s)
end

Tout ceci se teste assez simplement. Par exemple, pour faire simple, mettez mes petites fonctions dans un script, ajoutez en dernière ligne un out(notify(playlist("~/ma/musique"))) et c'est parti. Sous Debian les paquets nécessaires sont (liquidsoap et) respectivement xosd-bin et libnotify-bin. Un petit instantané du résultat chez moi:


Et bonnes vacances!

Application

Je suis en conférence, ce qui me laisse plein de temps pour bosser pendant la plupart des exposés... Bremen est plutôt une jolie ville, le campus est super agréable et il fait beau. Blogger s'est mis à me parler en Allemand. Ici j'ai vu Al. Bundy, pour ceux qui connaissent...

Bon sinon, un petit exemple simple m'est venu pour montrer que l'application en Caml n'est pas aussi simple qu'on le pense en présence d'arguments optionels. L'équation f x y = (f x) y, n'est pas toujours vérifiée. En fait, on n'a pas seulement une notion d'application mais bien une multi-application. Si je parle de ça c'est pour mettre au clair l'origine de la multi-abstraction du langage de script de liquidsoap.

# let f ?(a=false) () = a ;;
val f : ?a:bool -> unit -> bool = 
# f () ~a:true ;;
- : bool = true
# (f ()) ~a:true ;;
This expression is not a function, it cannot be applied
# f () ;;
- : bool = false

Scoop

Sam et Balbinus ont frénétiquement commencé un nouveau sous-projet au sein de Savonet: SoapLab! Il s'agit d'une application Gtk à deux facettes. D'abord un ingester, premier maillon du futur système IAS cher à Balbinus: il permet de rapidement examiner un fichier de sa playlist, et d'éditer ses caractéristiques, notamment les points de fade-in/fade-out/crossing. Tout cela bien sûr sur n'importe quelle machine, pas forcément sur le serveur de la radio. Soaplab est aussi un éditeur audio, qui importe/affiche/joue/modifie/exporte une onde sonore. Plutôt classique, mais de bonne facture et surtout, re-utilisant tout le matériel développé dans liquidsoap. Je m'en sers notamment pour inspecter la sortie d'une source liquidsoap.

soaplab --editor '
s = sine(duration=5.)
s = fade.in(duration=2.,type="sin",s)
s = fade.out(duration=2.,type="sin",s)
sequence(merge=true,[s,s,s,s,fallback([])])'

On voit ici quatres pistes de la source s, qui émet des pistes de 5 secondes, sinusoïdales à 440Hz, sur laquelle on a rajouté du fading in et out, de type "sinusoïdal". Les autres types dispos sont dans l'ordre: exponentiel, logarithmique et linéaire.

Un type bien

La fête du ciné se termine. Je n'ai vu que deux films, Boulevard de la Mort et Dialogues avec mon Jardinier. J'ai beaucoup aimé les deux. Ils sont très différents, mais ont cependant un point commun: on sort des deux en réalisant comme les choses simples sont efficaces. Pour le premier je pense à la simplicité de la violence et à celle du ressort "vengeance" qui fait jubiler le public comme rarement. Pour le second il s'agit de la simplicité du retour aux sources, à la nature, au jardinage, s'opposant à la vie urbaine et une création artistique sur-intellectuallisante.

Je ne peux pour ma part me résoudre à la simplicité, et, cherchant de nouvelles lectures, je suis retombé de plus belle sur Philip K. Dick, l'embrouilleur de réalités, avec le volume un (sur deux) de l'intégrale de ses nouvelles. Et, pour changer, je code: j'enrichis le système de type de liquidsoap, et je saisis cette occasion pour écrire un quelques mots sur l'inférence de type.

Pourquoi typer ?

Lors de l'exécution d'un programme, si on ne fait rien pour s'en prémunir, certaines choses absurdes peuvent arriver. Une fonction à binaire peut ne recevoir qu'un argument, on peut se retrouver à additioner un entier et un couple de chaînes de caractères, etc. Il est difficile de prévoir exactement ces problèmes sans exécuter le programme, et cela devient impossible dès lors que le langage devient Turing puissant.

Une première approche consiste à ne rien faire, et laisser le programmeur attendre que l'erreur à l'exécution arrive. C'est litéralement nul, il faut donc donner un nom à cela ("dynamique") et balancer quelques slogans qui font bien ("de toutes façons les tests unitaires sont plus précis que le typage") pour faire bonne figure. La majorité des langages de scripts adoptent cette approche. Selon l'expression absurde à évaluer, une vraie erreur va être levée, ou l'interpréteur va adopter une solution et continuer. Par exemple, si une fonction n'est pas appelée avec tous ses arguments, l'un d'eux pourra avoir la valeur spéciale undefined. Tôt ou tard, cette valeur spéciale posera une vraie erreur (on peut imaginer que l'interpréteur refuse catégoriquement de l'additionner avec quoi que ce soit), et il sera assez difficile pour le programmeur de trouver d'où venait cet undefined, qui aura pu passer de fonction en fonction avant de poser réellement problème. Je ne vais pas en dire plus sur cette approche qui ne fait rien pour le programmeur.

Le typage peut être vu comme une sur-approximation de l'ensemble des comportements qui peuvent arriver. Parfois le typage va donc détecter un problème qui ne peut pas vraiment arriver -- si on écrit une expression absurde dans une branche morte du code. En pratique, ça reste naturel. Quelques exemples rapides: 3 aura le type int; ("trois",3) le type string*int; et la fonction fun x -> x+1 le type int ->int.

Le typage statique consiste à vérifier les types avant l'exécution du programme. Dans certains langages, le programmeur écrit les types de ses variables (C/C++, Java, ...). Cela peut devenir assez lourd. D'autres langages (OCaml, SML...) sont capables de calculer le type le plus général d'une expression, c'est ce qu'on appelle l'inférence. Quand un langage a cette propriété, c'est la panacée: on n'écrit pas les lourdes annotations de type, et on a une vérification statique du code. De plus, aucune information de type n'étant nécessaire à l'exécution, les valeurs sont représentées de façon plus compacte et manipulées de façon plus immédiate, et on obtient des programmes plus rapides.

Le bémol du typage statique inféré, c'est la complexité des messages en cas d'erreur de type. D'autre part, si le système est trop simple, cela contraindra trop le programmeur dans son utilisation du langage. Mais quand on étend le système de type, on complexifie rapidement les erreurs. Il y a là un compromis délicat.

Inférer les types

Comment deviner le type d'une expression? Il suffit de regarder de près, en commencant par les expressions élémentaires et en remontant... Prenons l'exemple de fun x -> x+1.

On commence sur 1, qui a évidemment le type int. Ensuite on rencontre x, dont le type est inconnu. Mais pour que x+1 soit valide il faut bien que x soit un entier. La fonction a donc le type int -> int. Si je la nomme f, on peut maintenant chercher le type de fun y -> f("bla"). On voit qu'on utilise f avec une chaîne comme paramètre au lieu d'un entier, c'est une erreur de type.

Polymorphisme

Une extension simple et qui fonctionne bien est le polymorphisme -- ou l'appelle généricité dans certains langages. Si j'écris fun x -> x, je ne fais aucune hypothèse sur le type de mon argument, et je pourrais utiliser cette fonction sur n'importequelle valeur. C'est possible, OCaml lui donnera par exemple le type 'a -> 'a, qui veut dire pour tout a, a -> a. Exemple moins bidon: la fonction qui retourne une liste ne fait aucune hypothèse sur le type des éléments de la liste, et aura le type 'a list -> 'a list. (Exercice pénible: faites la même chose avec Java...)

Comme inférer ces types ? Il suffit de généraliser sur les variables de type (1) qui ne sont pas instantiées et (2) qui ont été introduites dans la fonction. Quand on type fun x -> x, on vérifie le corps de la fonction sans avoir besoin d'imposer aucune contrainte au type de x, c'est encore une inconnue, que Caml note '_t. L'expression a donc le type '_t -> '_t, qu'on généralisera en 'a -> 'a.

Si par contre je type fun x -> fun y -> x, il faut faire un peu plus attention. Mauvaise solution: la fonction interne a le type '_Ty -> '_Tx, que je généralise en 'a -> 'b, l'expression complète a donc le type '_Tx -> ('a -> 'b), généralisé en 'c -> 'a -> 'b. C'est manifestement faux, car cela veut dire: je prends deux paramètres quelconque et je te renvoie un truc de n'importe quel type.

Si on applique la condition (2) sur l'exemple fun x -> fun y -> x, voila comment cela se passe. La fonction interne a le type '_Ty -> '_Tx, mais '_Tx n'a pas été introduit dans cette fonction interne. On ne généralise qu'en 'a -> '_Tx. La fonction externe a donc le type '_Tx -> 'a -> '_Tx, qu'on généralise en 'b -> 'a -> 'b. C'est correct, cela veut dire: donne moi deux paramètres, je te renvoie un truc du type du premier.

Subtilités avec les références

Encore un petit détail avant de conclure. La liste vide [] peut sans problème avoir un type polymorphe 'a list. Il n'en est pas de même pour une référence ref [], qui doit garder le type '_T list ref, sans généralisation sur '_T. On ne modifie jamais une liste: on en crée une autre qui pointe sur l'ancienne. Et il n'y a aucune problème à ce qu'une liste d'entiers finisse en pointant la même liste vide qu'une liste de chaines. Par contre on modifie une référence, c'est sa raison d'être. Si on utilise notre référence dans l'instruction r := [1] on y range une liste d'entiers cela doit forcer '_T à devenir int. Car si par la suite on utilise un élément de la liste contenue dans la référence, cela ne peut pas être n'importe quoi, ce sera un entier.

Exercice/exemple: vérifier que fun x -> ref [x] a le type 'a -> 'a list ref; que let r = ref [] in (r, fun x -> r := [x]) a le type '_T list ref * ('_T -> unit).

Liquidsoap

Pourquoi j'ai parlé de tout ça ? Ces jours ci, je rafraichis le code de l'inférence de type de liquidsoap. J'ai ces choses en tête et je crois que cela vaut le coup de les présenter. Bien sûr je n'ai pas détaillé tout ce qu'il y avait dans le système de type de liquidsoap. Mais tout ce que j'ai décrit s'y trouve. Ce qui me mène à mon second but: expliquer pourquoi toute cette technologie compliquée est nécessaire dans liquidsoap.

Pour être honnête, ce n'est nécessaire que si l'on accepte le choix des types statiques et inférés dans le langage de script de liquidsoap. Pour moi il n'y a pas photo. Ensuite, on a besoin de fonctions dans le langage pour représenter les transitions. Enfin, nous prévoyons de généraliser liquidsoap, de générateur de flux audio à générateur de flux quelconque, en ajoutant la vidéo dans un premier temps. Pour cela, il faut du polymorphisme: au lieu des objets de type source on aura des objets de type format source où le format pourra être audio, video, etc. avec des informations en fait un peu plus raffinées. Certaines de fonctions actuelles de manipulation de flux, comme le switch() qui passe d'un flux à l'autre, s'étendent naturellement à n'importe quel format. Elles auront donc un type polymorphe. Enfin, si j'ai parlé des limitations de la généralisation pour les références, c'est parce que les types source se comportent pareil.

Le truc chouette, c'est que ça me donne une super excuse pour coder ces trucs que j'adore -- et que je vais enseigner l'an prochain en TP d'un cours de M1 de l'X, au passage. Et même avant l'arrivée du support vidéo, ça rend le langage plus souple et sympa pour un nombre considérable de choses. Mais je ne vais pas me lancer là dedans, c'est assez...

Sucre

Déja un mois depuis mon dernier post, il est temps d'en aligner un autre, dans la lignée des notes bien techniques. Le developpement de liquidsoap continue sûrement et plutôt pas lentement. L'API s'étoffe, notamment avec le crossfade intelligent utilisant les intensités relatives des débuts/fins de fichier, et des traitements de son de fou grâce à la libsoundtouch; le format AAC est supporté; nous n'avons presque plus à rougir du support ALSA; la doc devient plus lisible; et une multitude de petits détails s'améliorent. Romain nous pousse à releaser au plus vite, ce qui devrait se faire vu les grands chantiers qui se profilent de nouveau à l'horizon. Pour ma part j'oscille entre l'excitation de voir tout cela si bien tourner, et l'énervement de passer beaucoup de temps à orchestrer ça, corrigeant ou ajoutant du code selon des priorités qui ne sont plus seulement les miennes: tel utilisateur insiste sur un point, tel développeur fait une modification pas forcément judicieuse... et je ne peux m'empêcher de vite intervenir, peut être à tort.

Après la release, ma priorité sera à l'enrichissement du système de type de liquidsoap, avec du polymorphisme et du sous-typage, amenant une simplification de certains opérateurs, et surtout la possibilité de faire cohabiter des sources manipulant différent formats de flux. Après ça, Sam va pouvoir se faire plaisir avec la vidéo... On envisage aussi de généraliser les notions de fade et de crossfade intelligent au delà de la simple mesure de volume: on peut désormais mesurer et changer le BPM d'une source, on se prend à penser à des transitions préservant la continuité du BPM. Voila pour le futur. J'espère parler de typage la prochaine fois, mais pour tout de suite je vous propose encore de l'analyse syntaxique.

Certains sucres syntaxiques semblent tout simples, mais ne rentrent pas dans la sacro-sainte architecture lex/yacc. Par exemple, le preprocessing, qui permet de n'inclure certaines parties du script que quand telle feature est activée: %ifdef FEATURE CODE %endif. Cela ne peut être traité par le parser, ne serait-ce que parce que la construction peut être utilisée à tous les niveaux de la grammaire, ce qui l'alourdirait considérablement. Autre exemple, la notation bien pratique à la Ruby: "Bonjour #{get_name()}!" au lieu de "Bonjour "+get_name(). Ce n'est pas faisable dans le lexer tout seul, et pénible à traiter au niveau du parser, qui en théorie ne dépend pas du lexer.

La solution est d'accepter de s'éloigner un chouilla de l'archi habituelle, en ajoutant des intermédiaires entre analyse syntaxique et lexicale. C'est particulièrement simple en Caml, où un lexer n'est autre qu'une fonction prenant un état (position dans le texte) et renvoyant le symbole suivant dans le flux. On peut donc écrire des fonctions pour enrober le lexer original, afin d'obtenir les notations décrites -- et on simplifie par ailleurs notre lexer en traitant de la même façon les retours à la ligne pour lever les ambiguités dont je parlais la dernières fois. Un petit exemple, le traitement des %ifdef:

(* takes a function of type Lexing.lexbuf->Lang_parser.token,
and returns a function of the same type *)
let preprocess tokenizer =
let state = ref 0 in (* number of nested %ifdef *)
let rec token lexbuf =
match tokenizer lexbuf with
| Lang_parser.PP_IFDEF ->
begin match tokenizer lexbuf with
| Lang_parser.VAR v ->
if feature_enabled v then begin
incr state ;
token lexbuf
end else
let rec skip () =
match tokenizer lexbuf with
| Lang_parser.PP_ENDIF -> token lexbuf
| _ -> skip ()
in
skip ()
| _ -> failwith "expected a variable after %ifdef"
end
| Lang_parser.PP_ENDIF ->
if !state=0 then failwith "no %ifdef to end here" ;
decr state ;
token lexbuf
| x -> x
in
token

Après avoir défini quelques sucres syntaxiques, on utilise tout simplement le lexer étendu expand (preprocess (strip_newlines Lang_lexer.token)) au lieu de Lang_lexer.token. L'exemple complet se trouve sur notre SVN.

Grammaire

J'ai parlé ici-même, il y a presque un an, d'une petite astuce pour obtenir un langage sans point-virgule dans les séquences, juste un peu whitespace-sensitive, tout en utilisant le générateur de parser (ocaml)yacc. Je suis toujours dans cette optique, car je veux garder cette syntaxe légère, et je crois toujours qu'écrire mon parser à la main est source d'emmerdes au moins à long terme.

Résume de l'épisode précédent: le seul endroit où le retour à la ligne compte, c'est pour distinguer f ; (1,2) de f(1,2). Bien sûr la première expression n'a peu d'intérêt, la séquence ne servant qu'aux effets de bord que f ne fait pas, mais cela ne se voit pas au stage de l'analyse syntaxique. Ma solution a été d'introduire un token VARLPAR qui regroupe la variable et la parenthèse qui la suit si elles ne sont pas séparées par un retour à la ligne.

Second épisode: liquidsoap est en plein boom. Nous avons de nouveaux contributeurs, de nouveaux utilisateurs, on parle de nous, de nouvelles idées sont implémentées, etc.

Une de ces idées est le cross-fading intelligent. Au lieu de passer au cross-fading une fonction de transition qui décrit comment sont combinés les débuts et fins de piste, on y passe une liste de (condition,transition). La condition est une fonction à qui le smart_cross passe les puissances du signal sonore de part et d'autre de la transition. L'opérateur choisit la première fonction de transition dont la condition est validée. On peut ainsi choisir de superposer, fader, en fonction du volume des débuts et fin de piste. Romain a commencé à coder dans utils.liq l'utilisation du smart cross selon la description que mouke de bide-et-musique nous a faite.

Cet opérateur amène le besoin de coder dans notre langage de script des expressions arithmétiques, des comparaisons, etc. Et j'ai donc du étendre la grammaire. Pour faire simple, disons qu'on ajoute *, /, + et -.

Premier conflit: comment distinguer f(x) \n -1 de f(x)-1. Les deux sont naturels, on ne peut en éliminer aucun d'office. A moins d'empêcher le programmeur d'éclater ses expressions arithmétiques sur plusieurs lignes, ce qui est peu naturel et de toute façon difficilement réalisable dans mon cadre.

La solution vient de zmdkrbou, qui me propose de distinguer les expressions closes cexpr et les expressions générales expr. Une expression close peut être utilisée sans ambiguité dans une séquence: pour cela on limite les symboles pouvant apparaitre en tête, i.e. on élimine donc les négatifs -42, qui ne sont présents que dans les expressions générales. On peut obtenir une expression close représentant un négatif en l'entourant de parenthèses. Dans la plupart des règles, on peut continuer à utiliser des expressions générales, mais la règle de séquençage d'expression est restreinte aux expressions closes. Ainsi f(x) - 1, où que soient les retours à la ligne, sera la valeur de f(x) décrémentée de 1. Et on écrira f(x) (-1) (en général sur deux lignes, mais rien n'oblige) pour signifier qu'on évalue f(x) et qu'on retourne -1.

On tient le bon bout, mais l'histoire ne s'arrête pas là, et yacc m'en a fait baver. On a dans notre grammaire la règle (1) expr: cexpr, qui dit qu'une expression close est aussi une expression, et la règle (2) cexpr: cexpr PLUS expr. J'avais laissé un expr à droite du PLUS car l'ambiguité vue ci-dessus n'est présente qu'en début d'expression.

Sachant que l'automate d'analyse syntaxique doit décider de ce qu'il fait en ne regardant qu'un symbole en avant, comment savoir dans la situation cexpr PLUS ... si la cexpr doit être considérée comme une expr, auquel cas on réduit la règle (1), ou s'il faut avancer dans la règle (2) en mangeant de suite le +. L'automate est bête, pour lui une addition peut arriver après une expression générale car une expression générale peut être, en particulier, close. On ne peut le guider qu'avec des priorités, je mets donc une priorité plus faible à la coercion (1) qu'à la règle (2).

Et là, c'est le drame. Les priorités entre l'addition et la multiplication ne sont plus du tout respectées, l'analyseur parenthèse tout à droite comme un sale. On lui donne 2*3+1 il lit 2*(3+1). Après masse de bataille, je m'aperçois que la formulation de la règle (2), bien qu'inambigue, pose problème. On a expr: cexpr PLUS expr | cexpr MULT expr .... Le problème est que l'automate défavorise maintenant la coercion expr:cexpr. Du coup quand il voit le + après le 3 il ne va pas réduire l'expression close 3 en expression pour réduire ensuite l'expression close 2*3. Il va préférer manger le +, ce qui conduit à réduire l'expression close 3+1 en premier.

Au final la règle (2) doit s'écrire cexpr: cexpr PLUS cexpr. Et on n'y perd pas trop. On ne peut plus écrire 3+-1 mais il faut parenthéser en 3+(-1).

La morale: c'est toujours possible d'utiliser le couple lex/yacc pour une syntaxe sans point-virgule, en limitant énormément la sensibilité aux blancs (espace et retour à la ligne), ouf. Par contre l'automate de yacc est bien bête sur une production du type expr: cexpr.

Un jour faudra que je voie si c'est si difficile de ne pas ignorer les retours à la ligne à l'analyse syntaxique, et de les traiter explicitement partout dans la grammaire. A priori c'est lourd, comme il ne compte pas dans la majorité des cas. Mais une astuce n'est pas à exclure..

J'en peux plus

En fin de semaine dernière j'ai donné un coup de collier pour releaser liquidsoap 0.3.2, merci au passage à Romain qui s'est occupé des releases des librairies associées, et du packaging Debian par derrière. Le but pour moi était de passer ensuite une semaine studieuse à écrire mon article. Impossible.

Lundi nous recevons sur la liste savonet-users un mail de mouke. Je cite car l'archive de la mailing-list est plus que pourrie:

I recently discovered LiquidSoap and it seems it is the streamer I have dreamed of for some months. I am the tech guru of the french webradio "Bide et Musique".

Mouke a déja un clone de Bide et Musique qui tourne avec liquidsoap et songe à distribuer son système de gestion de la programmation musicale. La description qu'il en fait est alléchante, cela ferait un beau compagnon à liquidsoap!

Nous avons de plus en plus de résidents sur le canal IRC #savonet chez freenode. La plupart utilisent liquidsoap pour leur radio underground ou étudiante. Avec l'arrivée de ce mail tous les français se sont excités. J'ai passé la nuit à coder, sur la sortie ALSA et plusieurs autres détails; Samuel s'y est remis aussi et a mis au point un opérateur de renormalisation dynamique du volume; Balbinus s'est laissé pousser à coder un opérateur de compression. Et Mouke interface liquidsoap avec son outil. Quand j'arrive à décrocher je me fais rappeler à l'ordre par masse de questions et remarques. Je vais demander aux admins du labo de me désinstaller xchat...

Mais ce n'est pas tout. Car O'Reilly parle de nous, comme me l'apprend Romain: Une radio scriptable avec Liquidsoap et Savonet. Je n'étais pas au courant, mais je remercie Xavier Cazin, qui avait découvert liquidsoap par hasard il y a un an.

Ce genre de phénomène est exponentiel. Ça va dépoter :)

Art & Technique

On pourrait croire que je vais me plonger/noyer dans le débat "la programmation est-elle un art ?", et bien non, je ne vais même pas parler de programmation. Ne pas en parler fournit cependant une excuse valable pour y mettre mon grain de sel, j'en profite... Mon avis personnel est que la programmation est une maladie. Plus sérieusement, je pense que cela relève plus de l'artisanat que de l'art, avec tout l'amour du travail bien fait qui est présent dans beaucoup d'autres disciplines, mais une notion de bien fait qui n'existe pas avec l'art, et qui est liée à la fonctionalité du programme. Les poèmes et autres palindromes écrits dans des langages de programmation, n'ont (dans les cas que j'ai rencontrés) aucun intérêt en tant que programmes.

Revenons à nos moutons. Je voudrais parler de Gumstix, Arduino, PureData et Liquidsoap. L'histoire commence il y a bien longtemps avec la panne de notre Nabaztag. Le lapin wifi est une réussite niveau design, mais n'est pas super solide, et les utilisations possibles de l'engin étaient un peu restreintes: il ne communique qu'avec le serveur officiel, certains services sont payants, on ne peut que jouer de courts fichiers sonores. On peut dire que c'était juste assez bien pour que je commence à penser à le remplacer, mais pas assez pour que je sois prêt à débourser 130€, même pour la nouvelle version avec un nombril-microphone. Bref, je me suis mis à chercher un moyen de fabriquer mon propre lapin wifi, si possible en re-utilisant des pièces. Voici deux trois trucs sur lesquels je suis tombé.

Gumstix

Piloter une carte wifi est une chose compliquée, et en plus ça consomme beaucoup. En revanche il semble relativement aisé de bricoler des circuits communiquant via Bluetooth ou Zigbee. Très bien, mais comment faire le lien avec Internet? Il faut un serveur qui y soit branché et communique avec le lapin. Dans un premier temps ce sera mon portable, mais à terme je crois que ce sera un Gumstix bricolé: un micro-PC linux, plus compact tu meurs, et relativement bon marché.

Arduino

A plus court terme il faut un circuit pour contrôler le haut-parleur, les moteurs et lampes du lapin. Le LEGO Mindstorm c'est rigolo, ça pourrait sûrement faire tout ça, mais c'est pas très compact et surtout super cher. Les microcontrolleurs programmables ça fait peur... Jusqu'à ce que je tombe sur le projet Arduino. Il s'agit d'un projet ouvert (code source et spec. matériel distribuées sous licences libres) qui développe des cartes programmables, avec pour cible première des étudiants en art. Ils semblent avoir un truc facile d'accès, qui tourne avec des outils libres (gcc + IDE à eux), supporté par une certaine communauté. A première vue c'est donc une solution à la fois sérieuse (vrai microcontrolleur, qui parle à n'importe quel composant électronique, qu'on peut à terme monter dans un circuit indépendant de la carte) et assez simple d'accès pour laisser un peu de place à la créativité.

J'ai craqué et acheté le starter kit (carte + matos électronique de base) pour 50€, avec pour premier but de piloter un équivalent du nabaztag depuis mon portable. Ensuite je rajoute le streaming audio, la communication sans-fil, et.. qui sait ?

PureData et Liquidsoap

La communauté des bricoleurs sur Arduino semblent utiliser de temps en temps PureData, je me suis donc repenché un peu sur cet outil.

PD (aka Pure Data) is a real-time graphical programming environment for audio, video, and graphical processing. It is the third major branch of the family of patcher programming languages [...]

Bon. Realtime, ça veut rien dire, tout est temps réel avec assez de puissance. J'arrive pas à comprendre ce qu'est Patcher, si c'est vraiment un langage ou une interface graphique. Je sais pas en quoi PD permet de manipuler audio, vidéo et images de façon plus intéressante que le C. Faudrait que j'essaie ça.

Toujours est-il que PD a l'air très prisé pour réaliser des outils interactifs de synthèse et traitement audio. La question est: quelle différence avec Liquidsoap? Le but initial est différent, jusque là je ne me posais donc même pas la question. Mais après tout ce sont deux architectures assez génériques de traitement de son.

1. La configuration de Liquidsoap n'est pas modifiable à la volée.
2. Liquidsoap n'a pas d'interface graphique pour composer son script.
3. Les possibilités d'interaction avec les sources sont limitées (interface telnet).
4. Liquidsoap a peu de fonctions de synthèse de son, pas de feedback.
5. On a pas d'entrée microphone stable.

Le premier point est délicat, c'est une modif non triviale que je ne ferais pas de sitôt, mais c'est faisable sans aucun doute. Les points 2-4 requierent encore pas mal de code mais aucune modif bien profonde, rien d'infaisable. Il faudrait bosser sur un protocole expressif et structuré pour interagir avec les sources -- à moins qu'on continue avec le telnet, la source mix() marche plutôt bien comme ça, pilotée depuis la GUI en python. Le point 5 requiert du code et du courage, j'ai aucune envie de me faire chier avec le hardware, mais c'est clairement faisable. Au final, j'ai envie de conclure qu'avec quelques contributeurs motivés pour pousser le projet dans cette direction, c'est faisable.

Mais quel avantage par rapport aux projets existants? Un premier truc qui distingue Liquidsoap d'un paquet de toolkits est que sa notion de flux comporte un notion de piste, ce qui permet d'avoir des opérateurs qui opèrent au niveau de la piste (sélecteurs, transitions entre pistes, etc.). Sinon, l'archi est propre et robuste grâce au typage de Caml. Enfin, ça me semble pas mal d'avoir un démon et un langage de script sous l'interface graphique, même si du coup on a pas d'interface graphique dans un premier temps.

J'en apprendrai peut-être plus aux Rencontres Mondiales du Logiciel Libre 2007 cet été à Amiens. J'ai décidé d'y présenter Liquidsoap! Je guette l'appel à présentations pour le thème multimédia sur leur fil RSS. Pour l'instant seuls les thèmes Communautés et Embarqué ont été appelés: ordre de préférence, organisateurs plus rapides?