2013-03-22T10:08:41+01:00tag:blog.huoc.org,2009:atomtag:blog.huoc.org,2009:posts/static-type-assert-c11Statically asserting types in C11Nhat Minh Lê (rz0)2013-03-22T10:08:41+01:002013-04-07T13:09:32+02:00
<p>Yesterday, at the lab. Just another day at work… but then! After
wrapping up the last lemma of my proof, I spontaneously decided my
labmate needed to know more about C and its typing system, and even
though we discussed none of the stuff I’m going to talk about now, it
brings me to today’s topic: how to force the compiler to do some type
checking at compile time (in C11)?
</p><p>That might be a bit of a dumb question, so let me clarify. The
compiler does a lot of type checking by itself, but imagine that for
some reason, you have two type names and you want to know whether they
are the same. Of course, you could just look at them, but what if you
want to do it <em>programmatically</em>? What about if you had a value and
a type name?
</p><p>This blog post is all about trying to answer that, so, if you don’t
really care about fun (modern) C tricks that you’ll probably never
use, you can stop reading now. :-) If not…
</p><h3>Checking whether two types are equal
</h3><p>The setting is as follows: you have two type names <code>T</code> and <code>U</code>, that
you probably got through layers and layers of hardcore preprocessor
macroing. You’ve been dispatching, splitting, combining, and you’re
now wondering whether that type <code>T</code> the user gave you matches the type
<code>U</code> of the specialized routine you’ve selected — just as
a precaution. (We’ll assume the types are "simple types" that only
have a left-hand-side component.)
</p><h4>Solution 1: with variable definitions
</h4><p>There’s a couple of things you can try, depending on the current
syntactic context. If you have access to variable definitions (at file
or function scope) and don’t mind relying on dead code elimination
from your compiler, you can simply create two variables and try to
assign one to the other, like so:
</p><pre><code>#define CHECK_TYPE_COMPAT(T, U) T t; U u = t
</code></pre><p>If <code>U</code> can’t be assigned to <code>T</code>, the program won’t type check and the
compiler will complain. Assignment is great since almost every type
has it (exceptions being arrays and incomplete types). There’s one
problem, however: <code>CHECK_TYPE_COMPAT(int *, const int *)</code> compiles
happily. You might be tempted to write the following, then:
</p><pre><code>#define CHECK_TYPE_COMPAT(T, U) T t0; U u0 = t0; U u1; T t1 = u1
</code></pre><p>It does solve the above issue, but what about <code>CHECK_TYPE_COMPAT(void
*, int *)</code> or <code>CHECK_TYPE_COMPAT(double, int)</code>? Obviously, this method
does not work well if you want to test compatibility (equality, in
standard jargon), but sometimes you just want to know whether <code>U</code> is
assignable to <code>T</code>, and for that purpose, it’s a fine technique.
</p><p>Another issue here is that you’re creating variables. In function
scope, you can put a block around your definitions, to isolate them;
however, at the top level, you’ll have to mint variable names, e.g.,
with <code>__LINE__</code>.
</p><h4>Solution 2: with <code>typedef</code>
</h4><p>With C11, you now have a pretty nifty alternative in the form of
<code>typedef</code>. Of course, <code>typedef</code> itself is hardly a new
construct. What’s new, however, is that you can now have multiple
definitions of a <code>typedef</code> name. The only constraint is that they must
be equal… which is exactly what we’re looking for!
</p><pre><code>#define CHECK_TYPE_COMPAT(T, U) \
typedef T TC##__LINE__; typedef U TC##__LINE__
</code></pre><p>And here you go, manual type checking for everybody! And we don’t even
generate variables anymore. Isn’t that perfect?
</p><p>Well, of course, the answer is no; using <code>__LINE__</code> means you can only
have one of these per line, which may become problematic if you’re
macro-expanding a lot, but there isn’t much you can do about it as
long as you rely on introducing declarations. Besides, it doesn’t work
everywhere…
</p><h4>Solution 3: with assignments
</h4><p>If you’ve been following, you should notice that the previous
solutions only work if you have access to declarations, which excludes
cases when you’d like to do it from within expressions. For these
special occasions, you can use assignments instead… which brings us
to a related but slightly different problem.
</p><h3>Checking whether a value can be assigned to a type
</h3><p>Here’s another story: you are given a type name <code>T</code> and an expression
<code>x</code>. You want to know whether you could assign <code>x</code> to an object of
type <code>T</code>. That’s a pretty legitimate situation when writing type-aware
and other kinds of pseudo-polymorphic macros, I guess.
</p><p>In any case, this check most probably needs to take place in the
context of an expression, otherwise, <code>x</code> would be pretty limited. So,
let’s assume we are in an expression. We can’t declare any new
variable, so the previous tricks won’t work. But C99 offers a nice
little feature I’m sure you all know and love (I do): compound
litterals.
</p><p>Compound litterals are nice in that they let you create anonymous
aggregate values… but they don’t actually need to be constant. In
the general case, compount litterals introduce anonymous
objects. Using that fact, we can come up with a first attempt:
</p><pre><code>#define CHECK_ASSIGNABLE(T, x) ((T){ 0 } = (x))
</code></pre><p>To check whether you can assign <code>x</code> to an object of type <code>T</code>… simply
create an object of type <code>T</code> and try to assign to it. You need to pass
something inside the braces, so I put <code>0</code>. It’s fine, though, since
zero is the default initializer for every type in C.
</p><p>Now, the only issue is that we just want to <em>check</em>, not read the
value of <code>x</code> (which might be a side-effecting expression). Time to
apply the good old tricks to deny evaluation! Finally, we get
something like this:
</p><pre><code>#define CHECK_ASSIGNABLE(T, x) (0 && ((T){ 0 } = (x)))
</code></pre><p>This concludes this short blog post. You can try it at home, too, if
your compiler supports C99 (or C11 for the <code>typedef</code> method
above). Also, I haven’t given any code for solution 3; it’s very
similar to <code>CHECK_ASSIGNABLE</code>. I’ll leave it as an exercise to the
bored reader. If you’re really bored, you could also try to think
about what the limits of these techniques are — of course, they have
shortcomings, since they’re basically hacks, but in a sense, I find it
amazing enough that such tricks exist (and work) in the first place.
</p>
tag:blog.huoc.org,2009:posts/assertions-defensifLe C et ses raisons : assertions ou programmation défensive ?Nhat Minh Lê (rz0)2012-06-11T23:48:11+02:002012-06-11T23:48:11+02:00
<div class="Edito"><p>Je profite d’une <a class="extern" href="http://www.siteduzero.com/forum-83-775787-p1-verification-des-parametres-d-une-fonction.html">question récente sur le Site du
Zéro</a> pour écrire un petit billet sur un sujet que je
voulais aborder depuis un moment : les assertions, leur usage en C,
et le lien avec la programmation par contrats ainsi que la
programmation dite défensive.
</p></div><h3>Le problème
</h3><p>Le contexte est le suivant : on a une fonction, qui accepte des
arguments et renvoie un résultat (valeur de retour, ou en écrivant
dans des pointeurs passés en arguments). Ça ne casse pas de briques,
pour l’instant.
</p><p>Dans un monde idéal, chaque paramètre de la fonction a un type qui
décrit toutes les valeurs qu’un argument peut prendre, et s’il
y a erreur de typage à la compilation, c’est que l’on s’est planté
dans notre logique de programme.
</p><p>En pratique, ça ne se passe jamais comme ça dans un langage avec un
système de types (très) faible comme le C. On n’a pas de type pour
dire « un entier entre 1 et 10 » ou encore « un pointeur valide » ;
clairement, il y a des valeurs pour lesquelles la fonction ne peut pas
faire ce pour quoi elle est prévue.
</p><p>Prenons un exemple, une fonction pas très utile qui ajoute un entier
à une variable en mémoire et retourne l’ancienne valeur, avant
addition :
</p><pre><code>int
exchange_add(int *p, int x)
{
int old = *p;
*p += x;
return old;
}
</code></pre><p>Que peut-on dire de cette fonction ? Quelles sont les valeurs valides
en entrée ? Quel est le domaine des valeurs de retour ?
</p><ul><li><p>Le paramètre <code>p</code> doit être un pointeur valide sur un <code>int</code>. En
particulier, <code>p</code> ne peut pas être nul ; mais sont également exclus
les pointeurs vers d’autres types d’objets, ou de la mémoire non
allouée.
</p></li><li><p>La somme de <code>*p</code> et <code>x</code> ne doit pas dépasser <code>INT_MAX</code>, car les
dépassements entiers en C sont indéfinis.
</p></li><li><p>La valeur de retour, quant à elle, peut être un peu n’importe quoi.
</p></li></ul><p>On voit donc que le domaine (en entrée) sur lequel la fonction est
réellement définie est bien loin de ce que laisserait croire le
typage. Que peut-on faire ?
</p><h3>Solution 1 : ne rien faire
</h3><p>Bah oui, l’appelant n’a qu’à pas faire de bêtises ! S’il fait
n’importe quoi, c’est de sa faute, nah…
</p><h3>Solution 2 : agrandir le domaine de définition
</h3><p>Une solution plus conciliante est d’étendre le domaine de définition,
en traitant à part certaines valeurs qui causeraient une erreur avec
le code précédent, par exemple en ne faisant rien quand <code>p</code> est nul :
</p><pre><code>int
exchange_add(int *p, int x)
{
if (p == NULL)
return 0;
int old = *p;
*p += x;
return old;
}
</code></pre><p><code>exchange_add</code> est maintenant définie pour une valeur supplémentaire :
le pointeur nul. Cela nous pose un problème, toutefois, quant à la
valeur à retourner… on peut choisir quelque chose d’arbitraire,
comme zéro, ou changer la signature de la fonction pour pouvoir
identifier les cas exceptionnels ; c’est selon les besoins.
</p><p>Cette méthode s’appelle la programmation défensive : on essaie
d’anticiper les erreurs possibles et de les ajouter au domaine de
définition. Il faut remarquer, cependant, qu’en général il est
impossible de couvrir toutes les valeurs possibles autorisées par le
typage, ne serait-ce que parce que l’on n’a typiquement aucun moyen de
savoir si un pointeur est valide…
</p><h3>Solution 3 : détecter et prévenir
</h3><p>Entre les deux extrêmes ci-dessus, on a une solution intermédiaire qui
consiste à effectuer les tests comme si l’on programmait
défensivement… sauf qu’au lieu de renvoyer un résultat, on se
contente de détecter le problème… Détecter le problème ? Mais
pourquoi faire ?
</p><p>Le plus souvent, il s’agit d’en avertir le programmeur, généralement
par un petit message dans une sortie de débogage ou juste sur
<code>stderr</code>. Une fois l’avertissement envoyé, on a plusieurs choix :
</p><ul><li>quitter le programme ;
</li><li>quitter la fonction ;
</li><li>continuer comme si de rien n’était ;
</li><li>ou éventuellement emprunter un chemin non local (p.ex. avec un
<code>longjmp</code>, ce qui se traduirait dans d’autres langages par une
exception).
</li></ul><p>La décision de prévenir l’utilisateur du programme et l’action qui
suit dépendent le plus souvent de la nature de l’exécution. Si c’est
le programmeur même qui fait tourner son programme à des fins de
tests, l’avertir est la moindre des choses, et arrêter le programme,
afin qu’il puisse être débogué, n’est pas une mauvaise idée. En
production… tout dépend des contraintes et des mécanismes de
secours disponibles.
</p><p>Cette approche est basée sur l’idée de contrats : la notion que c’est
à l’appelant d’établir un certain nombre de conditions avant de passer
la main à la fonction sous contrats. Celle-ci est libre de vérifier
ses termes par prudence et par courtoisie, mais rien ne l’y
contraint. Entre autres, si certaines propriétés ne sont pas vérifiées
pour une raison ou une autre (trop compliquées ou impossibles
à vérifier, p.ex. qu’un pointeur non nul est valide), aucune garantie
n’est donnée. La différence fondamentale avec la programmation
défensive est que le domaine de définition de la fonction ne change
pas. Encore une fois, <em>aucune garantie</em>.
</p><h3>Assertions et contrats
</h3><p>J’ai mentionné <code>assert</code> dans mon titre, mais quel est donc le rapport
avec tout ça ?
</p><p><code>assert</code> est une macro-fonction définie dans <code>assert.h</code>. Elle teste
une condition qui <em>devrait</em> être vérifiée ; et si ce n’est pas le
cas… <i>boum</i> ! <code>assert</code> avertit l’utilisateur sur <code>stderr</code> avant de
quitter le programme. Si vous avez suivi, c’est l’un des cas de figure
évoqués dans la troisième solution ci-dessus. Par exemple :
</p><pre><code>int
exchange_add(int *p, int x)
{
assert(p != NULL);
int old = *p;
*p += x;
return old;
}
</code></pre><p>Un autre scénario est également pris en charge, avec la macro
<code>NDEBUG</code> ; si celle-ci est définie par l’utilisateur avant d’inclure
<code>assert.h</code> (typiquement <i>via</i> l’invocation du compilateur), les appels
à la macro <code>assert</code> sont sans effets. Cela correspond au cas de figure
où aucun avertissement n’est émis, et le programme tente de continuer
malgré la violation de contrat.
</p><p>En pratique, <code>assert</code> est rarement suffisant ; on a souvent envie d’un
mécanisme plus flexible (plus finement configurable, affichant plus
d’informations pour le débogage, etc.), et il n’est pas rare de se
créer sa propre collection de macros similaires.
</p><h3>Conclusion : assertions ou défensif ?
</h3><p>Finalement, la programmation défensive n’est-elle pas juste un cas
particulier de la solution 3 ? Si l’on se place hors du contexte
immédiat du C, et que l’on regarde des langages tels que Java, il est
courant de lever une exception au lieu de retourner une valeur ;
est-ce défensif, ou par contrats ?
</p><p>Au fond, peu importe. L’important est de savoir ce que l’on fait, et
savoir l’expliquer. Il y a beaucoup de nuances, et chacun a ses
préférences. Si je devais me prononcer, je dirais que c’est surtout
une question philosophique, à la base : les valeurs supplémentaires
prises en charge dans les tests font-elles partie du domaine de
définition de la fonction ? Autrement dit, est-ce qu’un utilisateur
peut légitimement prétendre passer <code>NULL</code> à ma fonction
<code>exchange_add</code> ? Est-ce un comportement que j’estime valide et que je
souhaite garantir ? Pour moi, non, mais c’est essentiellement une
question de goûts.
</p><p>À titre personnel, je dirais qu’avec le temps, je me suis mis à écrire
du code avec de plus en plus d’assertions (ou équivalents). Ce n’est
pas tant une décision idéologique que pragmatique : cela m’aide
à tester et déboguer, sans m’imposer la lourdeur et le coût de la
programmation défensive. En pratique, cela me permet d’écrire des
contrats relativement élaborés, ou pour de petites fonctions
fréquemment appelées (p.ex. des accesseurs) pour lesquelles la
programmation défensive est souvent exclue pour des raisons de
performances en production.<sup>1</sup>
</p><div class="Notes"><p class="note"><dfn class="notedfn"><sup>1</sup></dfn> Si j’ai le temps et la motivation, je publierai peut-être un
autre billet sur ce que j’ai appris (par l’expérience) sur
l’écriture de contrats dans la pratique.
</p></div><h3>Bonus : quelle résolution après une assertion fausse ?
</h3><p>J’ai évoqué plus haut que l’on avait plusieurs possibilités quant à la
résolution d’une assertion fausse : on peut ne rien faire, quitter le
programme, etc.
</p><p>Ne rien faire (pour du code en production) et prévenir puis quitter le
programme (en phase de test) sont des options populaires, probablement
parce que ce sont les choix par défauts disponibles avec
<code>assert</code>. Juste afficher un avertissement et continuer est également
très répandu, pour du code destiné à l’utilisateur final.
</p><p>Mais qu’en est-il du scénario où l’on veut pouvoir se rattraper ?
Continuer comme si de rien n’était va probablement engendrer des
comportements bizarres au mieux, et juste planter le programme un peu
plus loin dans beaucoup de cas.
</p><p>Si l’on a du courage, on peut opter pour un style défensif (mais cela
demande à ce que toute l’application soit construite autour de cette
approche, pour propager et gérer correctement les erreurs
« imprévues »), et dérouler la pile jusqu’à atteindre un état que l’on
considère stable ou récupérable (bonne chance…).
</p><p>De manière similaire, si l’on a un système d’exceptions ou équivalent
en place, on peut l’utiliser pour dérouler la pile. On substitue la
gestion délicate des ressources non locales (pensez RAII en C++ ou
<code>finally</code> en Java, et imaginez vous faire ça en C…) à la lourdeur de
devoir gérer des codes d’erreurs en retour des fonctions appelées.
</p><p>L’un ou l’autre, c’est beaucoup de boulot, et risqué en même
temps. Risqué parce qu’une petite erreur imprévue dans la gestion des
erreurs imprévues (autant dire que cela ne manquera pas de se
produire…) peut vite compromettre l’état « stable » duquel on
souhaite repartir (fuites de ressources, corruption mémoire, et j’en
passe).
</p><p>Et puis, parfois, il est tout simplement trop tard : si l’on détecte
une valeur aberrante dans un champ de structure, il est tout à fait
possible que la mémoire soit vastement corrompue, et que quelqu’un ait
écrit des choses où il ne fallait pas, y compris, par hasard, là où
l’on a eu la bonne idée de regarder… Le C tout seul ne fournit pas
vraiment les bons outils pour garder tout cela sous contrôle…
</p><p>Il n’y a pas une réponse unique à ce problème : « que faire quand le
programme rencontre une erreur fatale » est une question difficile et
mérite généralement que l’on s’y intéresse de manière spécifique.
C’est le but des stratégies de secours (<i>fallback</i> en anglais) dans
les systèmes complexes et importants. Soudainement mettre fin au
programme peut paraître brutal, mais c’est parfois une option tout
à fait viable, si par exemple un mécanisme de réplication se charge de
prendre le relais.
</p><p>Mais tout cela dépasse d’un peu loin le cadre de ce modeste
billet. :-)
</p>
tag:blog.huoc.org,2009:posts/indirect-call-inliningDoes your compiler handle indirect function call folding and inlining?Nhat Minh Lê (rz0)2012-06-09T10:16:32+02:002012-06-09T10:16:32+02:00
<p>Every once in a while, I ask myself this question: does my C<sup>1</sup>
compiler correctly optimize <em>it</em>? And today, <em>it</em> is indirect function
call inlining. I usually poke around the output of various compilers
I use, every few months or so, to see how their understanding of my
code has evolved… but this time around I decided to write something
a bit more structured so I could share it with whoever might be
interested in the same data.
</p><p>You can find the <a class="extern" href="http://git.huoc.org/?p=finline-test.git;a=summary">code and listings on my Git page</a> and
the <a class="extern" href="http://www.huoc.org/~minh/finline.html">HTML-formatted results on its own web page</a>. But
what is this all about?
</p><div class="Notes"><p class="note"><dfn class="notedfn"><sup>1</sup></dfn> This whole test was designed for C and C compilers. Though it
is also probably relevant to C++ to the extent that most of the
tested compilers also process C++, the test code and patterns are
not what you’d typically find in C++. Hence, how meaningful this
information may be to the average C++ programmer is questionable.
</p></div><h3>What is being tested
</h3><p>The tests exercise various scenarios involving inlining in the
presence of indirect function calls through function
pointers. Inlining can occur at different levels: for the outer
function being directly called, and for the function arguments called
from within the first inlined function. To make this completely clear,
let’s look at an example:
</p><pre><code>static inline int foo(int (int));
static inline int f0(int);
static inline int
foo(int f(int))
{
return f(42);
}
</code></pre><p>When <code>foo(f0)</code> is called somewhere, and if the compiler decides to
inline it, then it also gets an opportunity to <em>fold</em> and <em>inline</em>
<code>f0</code> at its call site.
</p><p>I won’t go into the details of what each test does; you should really
read the description on the <a class="extern" href="http://www.huoc.org/~minh/finline.html">results page</a> and then <a class="extern" href="http://git.huoc.org/?p=finline-test.git;a=blob;f=finline.c">the
code</a> for yourself. Things to look out for:
</p><ol><li><p>Inlining of <em>direct calls</em> (outer function and subsequent calls in
the direct chain between <code>call_*</code> functions). This should be
trivial.
</p></li><li><p><em>Folding</em> of known function constants. This is where things are
likely to go wrong. The tests exhibit various ways to pass the
function pointer constants around: as arguments or in a constant
structure (compound literal or <code>const</code> variable); with explicit
typing or hidden behind a void pointer.
</p></li><li><p>Elimination of <em>indirect calls</em> (either into a direct call or
inline call when possible), after the folding pass. This is not
difficult <i>per se</i> once constant propagation has been done, but some
compilers "forget" to do so.
</p></li></ol><p>One thing that has <em>not</em> been tested is indirect call chaining, as it
is really not that common in C (maybe due to the cumbersome syntaxe
associated).
</p><h3>Why it matters
</h3><p>A rather difficult question, really. Truth be told, it may not matter
to you. The kind of scenario described here most prominently arises
when inline functions are used for their generative properties, rather
than simply to make some call faster.<sup>2</sup>
</p><p>For example, you could imagine having two versions of <code>qsort</code>: the
default one, which exists as an external definition, and
a specializable one, which expands inline. Defining specialized
versions of <code>qsort</code> would then be a matter of wrapping the inline call
in a definition of your own.
</p><p>Whether this is "good", "bad", "interesting", or downright "awful", is
for you to decide. But if, like me, you think that this may have fun
applications, then you should check first that whatever compilers you
wish to build with do the job. And this is why I wrote this little
test.
</p><div class="Notes"><p class="note"><dfn class="notedfn"><sup>2</sup></dfn> In a sense, as opposed to how we used to write macros to get
"faster functions", we can now — with enough compiler support —
write inline functions instead of macros to generate code. Inlining
replaces macro expansion, and constant propagation does a similar
job to argument substitution.
</p></div><h3>Conclusions
</h3><p>From the results, I think we can draw a few general conclusions:
</p><ul><li><p>Non-optimizing compilers such as PCC predictably produce code that
does not take advantage of the inlining and folding opportunities;
when using such a compiler, using inline expansions to generate code
is likely to just bloat your program without much guaranteed gain
(there should be a trade-off there between increased code size,
which impacts code caching negatively, and separate call sites,
which improves indirect call prediction).
</p></li><li><p>Passing known functions as direct arguments seems to work reasonably
well for all optimizing compilers. In the worst case, no further
inlining takes place after constant folding (ICC and old GCC 3.x),
but at least indirect calls have been eliminated.
</p></li><li><p>Passing functions in structures yields mixed results. Compound
literals and constant variables do not behave the same but incur
different penalties depending on the compiler (ICC prefers literals
but old GCC does better with constant variables).
</p></li></ul><p>Overall, if you want to cater to the widest range of (optimizing)
compilers, keeping to immediate parameters is the safest choice. For
modern C99 compilers only, I believe compound literals will become (if
they’re not already) a viable alternative in the near future.
</p>
tag:blog.huoc.org,2009:posts/pointeurs-restrictLe C et ses raisons : les pointeurs restreintsNhat Minh Lê (rz0)2012-05-29T17:21:51+02:002012-05-29T22:05:50+02:00
<div class="Edito"><p>Après un an et demi de pause, le <em>Code et ses raisons</em> revient !
Dans ce nouvel épisode, je vais vous parler des pointeurs
restreints, introduits en C99 avec le mot-clef <code>restrict</code>. C’est une
question qui revient souvent parmi les enthousiastes qui découvrent
le C99… Les explications sur Internet (merci Google) ne manquent
pas, mais comme on m’a posé la question plusieurs fois, je me suis
dit que j’allais rédiger ma propre réponse une bonne fois pour toute
dans un petit billet !
</p></div><h3><code>restrict</code>, où, comment ?
</h3><p>Hop, dans le vif du sujet ! <code>restrict</code> est un qualificateur de type
(comme <code>const</code> ou <code>volatile</code>) ajouté en C99. Il ne s’applique qu’aux
types pointeurs. Syntaxiquement, pas de problème donc… il suffit de
se rappeler que les qualificateurs se placent <em>à droite</em> du signe <code>*</code>
qui déclare le pointeur :
</p><pre><code>int * restrict // pointeur restreint sur int
int * restrict * // pointeur sur pointeur restreint sur int
int restrict * // ILLÉGAL
int ** restrict // pointeur restreint sur pointeur sur int
</code></pre><p>Un peu comme pour pointeur sur <code>const</code>, un pointeur normal peut être
affecté à un pointeur déclaré <code>restrict</code>. Mais l’inverse est également
vrai. En fait, <code>restrict</code> n’a pas beaucoup d’influence sur le typage
à la compilation ; ses effets sont d’ordre dynamique.
</p><h3>Une définition intuitive
</h3><p>Si vous lisez la description de la norme à propos de <code>restrict</code> (toute
une section lui est dédiée), vous vous rendrez vite compte que c’est
assez indigeste. Même avec l’habitude de lire des spécifications, des
références et des normes, la définition n’en demeure pas moins
relativement obscure…
</p><p>Mais, en essence, quelle est l’intention derrière <code>restrict</code> ? Il faut
savoir que <code>restrict</code> n’est utile que dans le contexte d’optimisations
du compilateur. Vous ne gagnez rien en ce qui concerne
l’expressivité ; au contraire, en utilisant <code>restrict</code>, vous <em>vous</em>
imposez des contraintes supplémentaires. Déclarer un pointeur comme
restreint, c’est assurer au compilateur que vous avez pris soin de
vérifier certaines hypothèses pour lui, qu’il pourra utiliser pour
mieux optimiser votre code. Mais quelles hypothèses au juste ?
</p><p>L’idée est d’avoir un unique pointeur (le pointeur restreint) vers une
zone mémoire qui lui est attitrée. Tant qu’il existe (tant que l’on se
trouve dans la durée de vie de la variable correspondante), aucun
autre pointeur ne peut être utilisé pour accéder au même objet en
mémoire… à moins d’en avoir hérité le titre. En effet, affecter un
pointeur (ou le résultat d’une opération sur celui-ci) à un autre lui
transfère non seulement la valeur, mais également les droits d’accès
du premier.
</p><h3>La règle du pouce
</h3><p>En fait, il est très courant de supposer cette propriété sans s’en
apercevoir : la plupart du temps, dans un contexte donné, on accède
à chaque objet séparément, <i>via</i> son propre pointeur. On peut
éventuellement en faire une copie, ou prendre l’adresse d’un de ses
sous-éléments (p.ex. un membre d’une structure ou un élément d’un
tableau), mais tout va bien, car ce faisant, on se donne le droit
d’utiliser ces nouveaux pointeurs pour accéder à la même zone mémoire.
</p><p>Votre compilateur est suffisamment intelligent pour comprendre que si
un pointeur <code>q</code> prend pour valeur le résultat d’un calcul basé sur un
autre pointeur <code>p</code>, alors <code>q</code> doit aussi pouvoir avoir accès aux mêmes
éléments. (Et c’est garanti par la norme.)
</p><p>En pratique, <code>restrict</code> se comporte quasiment comme nous l’avons
décrit jusqu’ici, à l’exception que la norme spécifie quelques
subtilités concernant l’écriture. On peut résumer son fonctionnement
en deux règles pas trop compliquées. Soit <code>p</code> un pointeur restreint
(déclaré <code>T * restrict p</code>), alors :
</p><ul><li><p>Soit la valeur pointée par <code>p</code> n’est jamais modifiée durant toute la
durée de vie de <code>p</code>, et <code>restrict</code> ne garantit rien de spécial dans
ce cas.
</p></li><li><p>Soit la valeur pointée par <code>p</code> change à un moment ou un autre durant
la vie de <code>p</code> (directement dans la fonction qui a déclaré <code>p</code>, ou
indirectement dans une des fonctions appelée par celle-ci), et dans
ce cas seulement <code>restrict</code> postule que tout accès à cette valeur
(en lecture ou en écriture) durant la durée de vie de <code>p</code> doit
passer par <code>p</code> (directement, ou indirectement <i>via</i> un pointeur
résultant d’une opération sur <code>p</code>).
</p></li></ul><h3>Dans la pratique
</h3><p>Des règles ci-dessus, nous pouvons déduire deux cas de figure
pratiques :
</p><ul><li><p>Un pointeur restreint sur un objet constant (<code>T const * restrict</code>)
garantit que durant toute sa durée de vie, l’objet pointé n’est
jamais modifié du tout. C’est une conséquence directe : si la valeur
devait changer, l’écriture devrait obligatoirement se faire en
passant par notre pointeur restreint ; or, celui-ci pointe sur un
objet constant : impossible, donc.
</p></li><li><p>Un pointeur restreint sur un objet non constant garantit que seules
les fonctions auxquelles on passe une copie ou un dérivé de ce
pointeur peuvent modifier la valeur pointée. Ou de manière
équivalente, que toute action qui ne touche pas à ce pointeur
directement ou indirectement ne peut pas changer la valeur pointée.
</p></li></ul><p>Mais plus concrètement encore, qu’est-ce que cela nous interdit ? Les
possibilités sont multiples, mais voici quelques pistes de
réflexion :
</p><ul><li><p>Dans une fonction qui prend des pointeurs restreints en arguments,
écrire dans l’un ne doit pas changer la valeur lue dans l’autre.
</p></li><li><p>Appeler une fonction sans lui passer un certain pointeur restreint
implique qu’elle n’a pas accès à cette adresse par d’autres moyens
(p.ex. une variable globale).
</p></li></ul><p>Typiquement, l’usage de <code>restrict</code> se limite aux paramètres de
fonctions ; il est possible d’utiliser le mot-clef dans d’autres
contextes (p.ex. sur un membre de structure), mais la sémantique est
plus complexe, et moins utile.
</p><h3>Une histoire d’optimisation
</h3><p>Plus haut, j’ai mentionné le fait que <code>restrict</code> trouve son utilité
dans l’optimisation avant tout. Cependant, contrairement à <code>inline</code>,
un autre ajout de C99, il n’est pas aisé pour quelqu’un qui ne fait
pas de compilation ou de programmation bas niveau de comprendre
l’impact que peut avoir <code>restrict</code> sur l’efficacité de son
programme. Après tout, à quoi cela sert-il de garantir que l’on
n’accède pas au même emplacement mémoire par deux pointeurs
différents ?
</p><h4>Compilation des variables et des pointeurs, introduction accélérée
</h4><p>Pour comprendre pourquoi c’est utile, il faut regarder comment un
compilateur typique gère les opérations sur les pointeurs. Naïvement,
on pourrait penser que chaque opération comportant un accès à la
mémoire <i>via</i> un pointeur induit une instruction pour lire la valeur
à l’adresse concernée une fois traduit en langage machine. En vérité,
ce n’est pas forcément le cas. Il serait plus précis de dire qu’un
compilateur (typique) travaille tout d’abord avec des variables
abstraites (vous pouvez voir cela comme une mémoire séparée, qui
n’existe pas réellement, et qui sert au compilateur pour raisonner sur
les calculs qu’on lui demande d’effectuer), qu’il est obligé de
synchroniser de temps à autre avec la vraie mémoire de
l’ordinateur. Un exemple :
</p><pre><code>int x;
f(&x);
/*
* La valeur de x peut avoir changé ; il faut la relire depuis la
* mémoire.
*/
</code></pre><p>Comme la mémoire abstraite avec laquelle travaille le compilateur
n’existe que dans sa tête au moment où il compile un bout de code
précis, dès lors qu’il interagit avec d’autres composants, il est
obligé de matérialiser ses pensées dans la vraie mémoire, afin d’être
cohérent avec ceux-ci. Il existe deux types de synchronisation,
correspondant à la lecture et l’écriture :
</p><ul><li><p>Si le compilateur veut que la valeur d’une variable soit lisible par
un autre bout de code, il faut qu’il l’inscrive dans la mémoire.
</p></li><li><p>Inversement, s’il veut lire la valeur d’une variable qui a été
écrite par un autre bout de code, il faut qu’il la charge depuis la
mémoire.
</p></li></ul><p>Interagir avec la mémoire réelle peut être coûteux en soi, mais un
problème plus important encore est que de telles opérations sont
autant de contraintes supplémentaires pour le compilateur, qui
l’empêchent de transformer et réarranger librement les opérations…
</p><h4>Mémoire abstraite et problèmes d’alias
</h4><p>C’est là qu’intervient la notion d’alias, directement liée à nos
pointeurs restreints. Un pointeur est un alias d’un autre, à un moment
donné de l’exécution, s’il pointe au même endroit.
</p><p>Avoir des alias, c’est mal, du moins, ça mène la vie dure à votre
compilateur. Prenons un exemple :
</p><pre><code>void
foo(int *p, int *q)
{
/* ... */
}
</code></pre><p>Dans cette fonction <code>foo</code>, si nous mettons de côté l’arithmétique des
pointeurs, nous nous retrouvons avec deux cas :
</p><ul><li><code>p</code> et <code>q</code> sont égaux ;
</li><li>ou <code>p</code> et <code>q</code> sont différents.
</li></ul><p>On a un problème d’alias. Ici, le compilateur n’est pas capable de
représenter correctement dans son espace de variables abstraites les
« variables » <code>*p</code> et <code>*q</code> (les objets pointés par <code>p</code> et <code>q</code>). En
effet, il pourrait s’agir d’une seule variable si <code>p</code> et <code>q</code> sont
égaux, ou de deux variables si les adresses sont distinctes. Il
faudrait explorer les deux possibilités séparément, ce qui n’est pas
faisable (si on avait <i>n</i> pointeurs…).
</p><p>Une solution pragmatique, mais pas vraiment satisfaisante, est de
considérer les accès à <code>*p</code> et <code>*q</code> comme des opérations externes, qui
requièrent une synchronisation avec la vraie mémoire. En quelque
sorte, on est obligé d’abandonner notre modèle dans lequel un pointeur
désigne une variable pour une boîte noire capable de renvoyer ou
stocker une valeur qu’on lui donne. Et tout cela parce que l’on est
incapable d’identifier ladite variable pointée !
</p><div class="Remarque">Je ne vais pas le détailler, mais si on ajoute l’arithmétique des
pointeurs, on se retrouve avec trois options :
<ul><li><code>p</code> et <code>q</code> pointent sur des objets disjoints en mémoire ;
</li><li><code>p</code> et <code>q</code> pointent à la même adresse exactement ;
</li><li><code>p</code> et <code>q</code> pointent sur différentes parties d’un même objet en
mémoire (par exemple un tableau d’entiers).
</li></ul></div><p>Maintenant, regardons ce qui se passe si nous déclarons nos deux
pointeurs <code>restrict</code> :
</p><pre><code>void
foo(int * restrict p, int * restrict q)
{
/* ... */
}
</code></pre><p>D’après les règles décrites plus haut, nous savons que selon que
l’objet pointé soit modifié ou non, les propriétés
changent. Néanmoins, nous pouvons toujours choisir de représenter <code>*p</code>
et <code>*q</code> comme deux variables distinctes dans l’espace abstrait. En
effet :
</p><ul><li><p>Si durant l’exécution de <code>foo</code>, quelqu’un écrit dans l’emplacement
associé à <code>p</code> ou à <code>q</code>, alors les règles qui gouvernent les
pointeurs restreints nous garantissent que <code>p</code> et <code>q</code> pointent sur
des objets différents.
</p></li><li><p>Sinon, la valeur des objets pointés ne change jamais, et nous nous
retrouvons avec deux variables abstraites parfaitement égales,
à tout moment ; sans conséquence pour la suite des opérations.
</p></li></ul><h4>Un mot sur la vectorisation
</h4><p>Nous avons vu comment <code>restrict</code> permettait d’affiner notre
représentation des variables pointées, ce qui permet d’être plus
agressif au niveau des échanges avec la mémoire réelle.
</p><p>Un autre effet positif, qui est souvent davantage médiatisé, mais qui
découle essentiellement des mêmes principes, est une meilleure
vectorisation du code. La vectorisation (ou auto-vectorisation) est
l’optimisation par laquelle le compilateur traduit des boucles ou
morceaux de boucles en instructions spécialisées qui opèrent sur des
(petits) tableaux de plusieurs valeurs à la fois.
</p><p>Typiquement, ces instructions se présentent comme des opérations
classiques sur les scalaires, excepté qu’elles consomment et
produisent des vecteurs. Une conséquence de cette description en
apparence anodine est que le compilateur doit pouvoir réarranger les
boucles afin de grouper plusieurs lectures et plusieurs écritures
ensemble. Dans le cas où les pointeurs utilisés pour ces accès se
comportent comme des boîtes noires, de telles permutations sont en
général illégales, car une inscription dans la boîte noire pourrait
influencer le prochain chargement depuis une <em>autre</em> boîte noire. Et
nous retrouvons notre cher problème d’alias.
</p><p>Pour illustrer cette question, regardons un dernier exemple, une
fonction qui additionne deux vecteurs et place le résultat dans un
troisième :
</p><pre><code>int *
vector_add(int *a, int *b, int *result, size_t n)
{
for (size_t i = 0; i < n; ++i)
result[i] = a[i] + b[i];
return result;
}
</code></pre><p>Admettons que <code>n</code> soit un multiple de 4 et que par chance, nous
disposions d’une instruction machine qui ajoute deux vecteurs de
taille fixe 4 et place le résultat dans un troisième. Il faudrait
modifier la boucle précédente pour traiter les données par paquets de
4, comme suit :
</p><pre><code>int *
vector_add_1(int *a, int *b, int *result, size_t n)
{
for (size_t i = 0; i < n; i += 4) {
int tmp[4];
tmp[0] = a[i] + b[i];
tmp[1] = a[i+1] + b[i+1];
tmp[2] = a[i+2] + b[i+2];
tmp[3] = a[i+3] + b[i+3];
memcpy(result + i, tmp, 4 * sizeof *result);
}
return result;
}
</code></pre><p>La variable <code>tmp</code> illustre ici le fait que notre instruction
vectorielle prend place entièrement avant l’écriture dans le
tableau-résultat. Malheureusement, ces deux fonctions ne sont pas
équivalentes dans le cas où <code>a</code>, ou <code>b</code>, et <code>result</code> pointent sur des
parties du même vecteur !
</p><h3>Conclusion
</h3><p>Voilà qui conclut notre petit tour des pointeurs restreints. J’espère
que cela aura été instructif pour certains, ou donné envie à d’autres
d’essayer le mot-clef <code>restrict</code> ! Pour ma part, j’ai encore un peu de
mal à me faire à son usage. La charge de réflexion supplémentaire pour
savoir quand un pointeur doit être restreint ou non n’est pas
exactement négligeable, et je ne pense pas non plus qu’il faille
essayer de toute spécifier à l’aide de ce seul qualificateur, mais,
comme pour <code>const</code>, il permet d’expliciter certaines hypothèses que je
fais parfois sans m’en apercevoir, et en cela, je considère son ajout
comme une bonne chose… les performances, c’est que du bonus ! ;)
</p>
tag:blog.huoc.org,2009:posts/breves-de-maiBrèves de maiGabriel Scherer (gasche)2012-05-27T15:40:00+02:002012-05-27T15:40:00+02:00
<p>Ce matin j’ai lu tous les liens qui m’avaient l’air intéressants, mais
trop longs pour que je prenne le temps de les lire pendant la
semaine. Ils font donc parti de la petite centaine de nouvelles,
issues principalement de mes flux de syndication, que j’ai accumulées
au cours de la semaine. Je me suis dit que cette sélection serait
parfaite pour un petit billet, et le voilà.
</p><h3>Xerox parc et la naissance de l’informatique contemporaine
</h3><p><a class="extern" href="http://interstices.info/jcms/int_64091/xerox-parc-et-la-naissance-de-linformatique-contemporaine">http://interstices.info/jcms/int_64091/xerox-parc-et-la-naissance-de-linformatique-contemporaine</a>
</p><p>(source : Ptival)
</p><p>C’est intéressant et bien raconté ; en particulier j’aime bien le soin
qui a été pris dans cet article de s’intéresser aux chercheurs
individuellement, et de garder leur trace pour montrer d’où les gens
venaient et où ils sont partis. Ça donne une meilleure vision du
milieu des laboratoires privés de recherche aux USA dans ces années
là. J’ai l’impression que nous manquons un peu de ce genre de choses
en France : quelles sont aujourd’hui les entreprises installées en
France qui ont une politique de recherche ambitieuse et intéressante
en informatique ? Il y a des interactions avec des acteurs industriels
(dans le domaine de la fiabilité du logiciel par exemple, les
entreprises d’aéronautique, de train ou d’automobile ont des contacts
avec le milieu de la recherche), mais pas à ma connaissance de vrais
laboratoires de recherche non publics ayant une politique sur le long
terme, en tout cas dans les domaines qui m’intéressent le plus.
</p><p>Il y a par contre un petit je ne sais quoi qui est casse-pieds sur ce
site. Il y a beaucoup de liens externes vers Wikipédia (liens « W »), et
c’est bien, mais sinon il y a des « encarts » qui sont désagréables
à utiliser (liens « ? »), et de même les liens internes (liens « i ») sont
malcommodes.
</p><h3>Story Bricks : The Future of User-Driven Narrative is At Stake
</h3><p><a class="extern" href="http://aigamedev.com/open/interview/storybricks-preview/">Http://aigamedev.com/open/interview/storybricks-preview/</a>
</p><p>Un point intéressant sur l’interface graphique que l’on voit, qui
est bien une forme de programmation visuelle : il y a du typage
apparent. Ça se voit bien sur <a class="extern" href="https://aigamedev.com/wp-content/blogs.dir/5/files/2012/05/RodolfoJuliette-280x300.png">cette
image</a>
par exemple : les connecteurs entre blocs ont une forme précise qui
définit leur type ; par exemple les émotions ont un connecteur en
forme de cœur, et les messages (de conversation) en forme de
bulle. C’est une technique maintenant bien connue pour rendre le
typage tangible aux utilisateurs, mais il est intéressant de voir
que même des gens dont le domaine métier n’est pas directement la
conception de langages (même s’il en est proche) les ont intégrées.
</p><p>Ça me fait penser, au moins visuellement, au travail de Sean
Mcdirmid sur le concept de <em>touch programming</em> (<a class="extern" href="http://lambda-the-ultimate.org/node/4257">sur
Lambda-the-Ultimate
(LtU)</a>, et <a class="extern" href="http://alarmingdevelopment.org/?p=616">sur le
blog</a> de Jonathan Edwards).
</p><p>Plus généralement c’est le genre de projet qui montre qu’il continue
à y avoir une interaction intéressante entre le domaine de
l’intelligence artificielle (AI) et celui des langages de
programmation. Je connais peu le domaine mais j’ai l’impression qu’une
des questions importantes en AI des jeux vidéos est de trouver le bon
langage déclaratif pour décrire le système désiré (automates,
<i>behavior trees</i>, <i>rule-based systems</i>, …).
</p><p>Par contre je n’aime pas trop la façon dont le projet se vend. Ils
ont une page Kickstarter qui demande au public de leur donner de
l’argent pour financer le développement, mais pour donner quoi en
retour ? Ils comptent simplement commercialiser leur produit et le
revendre ensuite à d’autres concepteurs de jeux vidéo. Je pense
qu’un travail entièrement financé par le public devrait, au final,
revenir au public — par exemple sous la forme d’un logiciel
libre. Je peux comprendre que ce n’est pas dans la culture du
domaine du jeu vidéo ; que certains joueurs soient satisfaits de
financer un jeu pour pouvoir simplement y jouer en retour, parce
qu’il a l’air bien (mais je m’attends au moins à ce que les
personnes qui ont donné reçoivent une version du jeu en retour), ou
financer un groupe de musique pour le simple plaisir de pouvoir
entendre leur nouvel album. Visiblement ça ne marche pas bien fort
pour ce projet ; et je pense que c’est parce qu’il joue plutôt sur le
développement de nouvelles abstractions, qui auraient sans doute, au
moins au départ, peu d’impact sur l’utilisateur final, et qui
gagneraient donc plus à être rendues libres.
</p><p>En plus, même moi qui ne fait plus partie du milieu du jeu vidéo,
j’ai déjà entendu trop de fois le refrain « avec notre nouveau jeu,
les personnages auront de vraies émotions et ce sera formidable ». Je
ne comprends pas comment on peut encore séduire avec un discours
aussi stéréotypé. En plus leur discours est parfois franchement
condescendant :
</p><blockquote><div><p>But, it takes a bit of imagination to draw the line between where
we are today and what we can be. Imagination that gamers have that
others tend to lack. Game developers are happy providing the same
old types of gameplay that people are ready to pay for rather than
taking risks. Investors aren’t sure that there is even a demand
for MMOs or new forms of gameplay.
</p></div></blockquote><h3>The quest to replace passwords
</h3><p><a class="extern" href="http://www.lightbluetouchpaper.org/2012/05/22/the-quest-to-replace-passwords/">http://www.lightbluetouchpaper.org/2012/05/22/the-quest-to-replace-passwords/</a>
</p><p>(source : Bruce Schneier)
</p><p>Une présentation intéressante d’un article de recherche sur les
façons de comprendre et comparer les techniques
d’authentification. L’auteur dit explicitement que cette recherche
est le fruit d’une section <em>Related Works</em> bien écrite, ce qui
renforce mon idée que c’est souvent la partie la plus importante
d’un article.
</p><h3>A uTouch architecture introduction
</h3><p><a class="extern" href="http://lwn.net/SubscriberLink/497905/b8c6ef50db5cfb2c/">http://lwn.net/SubscriberLink/497905/b8c6ef50db5cfb2c/</a>
</p><p>(Je trouve que LWN fait un boulot formidable; si vous vous
intéressez à GNU/Linux, n’hésitez pas à vous abonner !)
</p><p>Ce lien sans grande prétention fait une description technique des
interrogations que se posent les développeurs desktop Linux pour la
gestion du « touch », toutes ces nouvelles méthodes d’entrée que l’on
caresse des doigts. L’article, et les commentaires qui le suivent,
montrent bien que ces nouvelles méthodes d’entrée posent des problèmes
pour les développeurs.
</p><p>Le problème de fond est que langage des événement d’entrées est
ambigu : contrairement aux appuis de touches atomiques sur un
clavier ou de boutons sur une souris, un même signal peut être
interprété de plusieurs façons différentes. L’appui à un endroit
peut être un clic ou, s’il est prolongé dans le temps et suivi par
un déplacement du doigt, être en fait seulement le début d’un
déplacement ; pour le savoir il faut attendre, mais les bons
principes d’interface utilisateur poussent au contraire à envoyer un
retour immédiat à l’utilisateur ; il devient donc nécessaire de
modéliser des états intermédiaires ambigus, et ce n’est pas de la
tarte à gérer pour le développeur.
</p><p>(On avait déjà des problèmes de ce genre avec les doubles et triple
clics, ou les « accords » sur le clavier, mais dans le cadre du
« touch » ils semblent prendre une place encore plus importante.)
</p><p>Ce que je trouve intéressant est que c’est exactement le problème
dont parlait dmbarbour dans son dernier billet, <a class="extern" href="http://awelonblue.wordpress.com/2012/05/20/abandoning-commitment-in-hci/">Abandoning
Commitment in Human Computer
Interfaces</a>
(<i>fun fact</i> : mon cerveau a fait une typo et j’ai commencé par
écrire <i>Huser</i> Computer Interfaces). Ce billet a d’ailleurs donné
lieu à une <a class="extern" href="http://www.reddit.com/r/programming/comments/tx6s3/abandoning_commitment_in_human_computer_interfaces/">discussion
fournie</a>
sur reddit ; mais son niveau d’abstraction un peu trop élevé rend
difficile, je trouve, une discussion vraiment convaincante.
</p><p>Je me demande comment ces choses-là vont évoluer avec l’apparition
de nouvelles méthodes d’entrée. dmbarbour (il est un peu trop
insistant sur ses sujets fétiches, et un peu trop abstrait, mais
c’est quand même un type intéressant) en parle dans <a href="#comment-70840">une autre
discussion</a>
sur LtU.
</p><p>En ce moment on nous fait rêver avec des gants 3D (« comme dans
Minority Report huhu ») et autres gadgets du genre. Je pense qu’une
généralisation de ces périphériques pourrait changer les outils
qu’on utilise pour éditer les programmes<sup>1</sup>, et donc la syntaxe, mais
sans doute pas fondamentalement la sémantique des langages de
programmation.
</p><div class="Notes"><p class="note"><dfn class="notedfn"><sup>1</sup></dfn> Ça me semble plus facile que pour éditer du texte libre
</p></div><p>(par exemples pour les auteurs et journalistes), parce que les
programmes informatiques sont plus structurés.
</p><h3>How the professor who fooled Wikipedia got caught by reddit
</h3><p><a class="extern" href="http://www.theatlantic.com/national/archive/2012/05/how-the-professor-who-fooled-wikipedia-got-caught-by-reddit/257134/">http://www.theatlantic.com/national/archive/2012/05/how-the-professor-who-fooled-wikipedia-got-caught-by-reddit/257134/</a>
</p><p>(source : Bruce Schneier)
</p><p>J’ai un peu honte de le mettre entre d’autres liens que je trouve
objectivement intéressants, mais je trouve l’histoire amusante. Un
professeur fait un cours sur « comment falsifier des faits
historiques », ils montent un <em>hoax</em> qui survit sur Wikipédia, et
l’année d’après ils essaient de faire pareil sur reddit, et se font
démontrer. Un petit moment de Schadenfreude.
</p><h3>Les communs culturels et la justice sociale : fondations pour un nouvel humanisme européen
</h3><p><a class="extern" href="http://paigrain.debatpublic.net/?p=4846">http://paigrain.debatpublic.net/?p=4846</a>
</p><p>Un billet qui a le tout premier avantage de me faire déculpabiliser un
peu à l’idée d’écrire systématiquement des pavés.
</p><p>Il y a quelque chose qui me met mal à l’aise dans les débats actuels
sur le partage des fichiers soumis au droit d’auteur, le piratage,
HADOPI, etc. Une grande partie du débat concerne « ce qui est juste »,
et des discussions de comment adapter les moyens techniques à cette
idée de ce qui est juste.
</p><p>J’ai l’intuition que ce n’est pas forcément la bonne approche :
quand un changement technique rend extrêmement simple de faire
quelque chose (partager des fichiers), et que tout le monde le fait,
est-ce que ça a du sens d’essayer de discuter de si c’est « bien » ou
« mal » ? Mon intuition est que dans ce cas c’est à la société
d’adapter ses notions de justice aux possibilités techniques, et pas
l’inverse.
</p><p>Je n’ai jamais réfléchi très en profondeur à la question (par manque
de temps) et je pense qu’il y a des choses à dire sur le
sujet. Philippe Aigrain met en avant une notion d’« échanges
non marchands » (il a écrit un livre sur le sujet, que je n’ai pas eu
le temps de lire) qui est intéressante et qui s’approche peut-être
de cette idée de reconnaître et accepter les pratiques de société.
</p><p>Je trouve le billet un peu (trop) politique, sans doute parce qu’il
s’agit d’une transcription d’un texte initialement écrit dans un
autre contexte ; mais ça reste une lecture intéressante sur ce sujet
d’ensemble.
</p><p>Dans le même genre et aussi dans mes lectures de ces derniers jours :
</p><ul><li><p>OWNI a <a class="extern" href="http://owni.fr/2012/05/24/pour-que-vive-le-domaine-public-numerique/">un bon
article</a>
de de Lionel Maurel sur Communia, une nébuleuse « initiative
européenne » qui s’intéresse de près au Domaine Public et fait
pression pour renforcer ce concept dans le droit d’auteur européen,
en le présentant comme une richesse plutôt que comme <em>les limbes</em><sup>2</sup>
des œuvres de l’esprit.
</p></li><li><p>John Purdy (un type dont je ne me souviens plus comment le blog
est arrivé dans mon lecteur de flux) a un petit billet nommé
<a class="extern" href="http://evincarofautumn.blogspot.fr/2012/05/utopian-university.html">Utopian
University</a>
sur un lieu de vie pour l’aide à la création
(artistique et/ou informatique). Avec un commentaire intéressant
qui m’a permis d’apprendre l’existence d’un <a class="extern" href="http://www.basicincome.org/bien/">réseau
mondial</a> en faveur du salaire
minimal automatique (traduction maladroite ; Wikipédia parle
d’<a class="extern" href="http://fr.wikipedia.org/wiki/Allocation_universelle">allocation
universelle</a>).
</p></li><li><p><a class="extern" href="http://www.gironde.pref.gouv.fr/Dossiers-d-actus/Lancement-d-un-Guide-de-l-intelligence-economique-pour-la-recherche">Lancement d'un guide de l'intelligence économique pour la
recherche</a>.
Je n’ai pas lu ce lien récemment mais j’ai lu il y a quelques
semaines le document qu’il présente, le « guide de l’intelligence
économique pour la recherche ». Ce document d’une vingtaine de pages
a été écrit par le ministère de la recherche, et il explique en gros
comment les acteurs du monde de la recherche devraient essayer de
faire gagner de l’argent à l’État avec leur travail. La position sur
le logiciel libre est hideuse ; de manière général ce document
(dont j’espère qu’il montre la vision du gouvernement précédent, et
pas de l’actuel, mais je suis légèrement pessimiste sur ces
sujets-là) on y lit que pour être un bon chercheur qui « valorise »
(financièrement, bien sûr) son travail, il faut surtout n’en parler
à personne.
</p></li></ul><div class="Notes"><p class="note"><dfn class="notedfn"><sup>2</sup></dfn> quand on cherche "les limbes" sur internet on trouve dans les
</p></div><p>premier résultats "définition des limbes dans Inception". Où va-t-on,
mon bon monsieur ou ma bonne dame ?
</p><h3>Flymake
</h3><p><a class="extern" href="http://flymake.sourceforge.net/">http://flymake.sourceforge.net/</a>
</p><p>Il faudrait vraiment que j’apprenne à m’en servir.
</p><h3>En route pour HTTP 2.0
</h3><p><a class="extern" href="http://linuxfr.org/news/en-route-pour-http-2-0">http://linuxfr.org/news/en-route-pour-http-2-0</a>
</p><p>Il y a vraiment de bonnes dépêches sur LinuxFR (oui, je suis un
groupie de patrick_g, je lis religieusement ses dépêches noyau ;
d’ailleurs j’ai essayé de l’encourager à faire traduire ses dépêches
vers l’anglais, pour leur donner un lectorat plus large, mais il n’a
pas pris ma suggestion au sérieux et je n’ai pas le temps de m’en
occuper tout seul). Cette présentation de HTTP 2.0 est vraiment
passionnante (bon après c’est technique, hein), en particulier
l’interview de Willie Tarreau qui dit des choses très intéressantes
sur les processus de normalisation.
</p><p>D’ailleurs, contrairement à d’autres fois, la discussion dans les
commentaires est plutôt intéressante. J’ai l’impression que les
visiteurs de LinuxFR sont souvent très pertinents sur les questions
d’administration système et de réseau, beaucoup plus que par exemple
les langages de programmation (j’arrête de lire les commentaires sur
les dépêches Go, Pypy ou Scala sur LinuxFR, le rapport signal/bruit
est trop faible).
</p><h3>Thoughts on Gamifying Textbooks
</h3><p><a class="extern" href="http://blog.ezyang.com/2012/05/thoughts-on-gamifying-textbooks/">http://blog.ezyang.com/2012/05/thoughts-on-gamifying-textbooks/</a>
</p><p>Edward Yang est un type très intéressant et, bien que j’aie arrêté de
suivre Planet Haskell (signal/bruit), son blog est resté dans mes flux
de syndication. Récemment il a fait le pari d’implémenter du logiciel
interactif sur le web pour jouer avec des arbres de preuve formelle
(le résultat n’est pas non plus à en tomber par terre à mon avis, mais
la combinaison technique, <a class="extern" href="http://blog.ezyang.com/2012/05/what-happens-when-you-mix-three-research-programming-languages-together/">Haskell + Ur/Web +
Coq</a>,
mérite le plus grand respect). Ça l’a mis en verve et il fait des
grands discours sur l’éducation avec de nouveaux moyens techniques, et
ce n’est pas mal.
</p><h3>No-cost desktop software development is dead on Windows 8
</h3><p><a class="extern" href="http://arstechnica.com/information-technology/2012/05/no-cost-desktop-software-development-is-dead-on-windows-8/">http://arstechnica.com/information-technology/2012/05/no-cost-desktop-software-development-is-dead-on-windows-8/</a>
</p><p>Le choix de Microsoft de restreindre l’accès à leurs outils de
développement et utilitaires de compilation pour Windows me paraît
très mauvais, et surtout susceptible d’avoir des conséquences
importantes sur le long terme (s’ils ne changent pas d’avis, ce que je
leur souhaite).
</p><p>Pour conclure, j’ai discuté de ça avec Nhat (rz0) par e-mail, et, en
tant que développeur orienté bas niveau, il semble partager mon
scepticisme sur la question :
</p><blockquote><div><p>Il est dommage de voir Microsoft abandonner, voire rejeter,
certaines catégories de programmeurs après ce qui est apparu pendant
quelques années comme une période d’ouverture, avec Visual Studio
Express. C’est peut-être une option défendable d’un point de vue
<i>marketing</i> à court terme, mais le risque dans la durée est de voir
une raréfaction des talents dans des domaines tels que la
programmation systèmes sous Windows, pourtant essentiels à leur
propre écosystème.
</p></div></blockquote>
tag:blog.huoc.org,2009:posts/conditionals-constants-c11-genericCompile-time conditionals and unique constants using C11 _GenericNhat Minh Lê (rz0)2012-05-16T18:42:17+02:002012-05-16T18:58:45+02:00
<p>About a month ago, I started playing around with the new C standard,
namely C11, and its new features. While I have always been fond of
some of them, such as explicit alignment support, others never really
caught my interest. One of those not-so-interesting additions was the
new <code>_Generic</code> construct, which allows rather limited <i>ad-hoc</i>
compile-time type-based dispatching. While I reckon it was necessary
in order to support the <code><tgmath.h></code> header in a meaningful way, as
well as, <em>perhaps</em>, the growing number of integral types, I’d never
seen it as anything more than that: an implementor’s device given
standard blessing.
</p><p>Well, that was until a few days ago. While experimenting with a macro
of mine, I tried to improve it by using C11 features, and, in doing
so, stumbled upon a rather less boring use of <code>_Generic</code>: compile-time
"type-level" constants, and conditional compilation based on it!
(Well, maybe it sounds obvious to some of you; for the rest, please
read on!)
</p><h3>The basics of <code>_Generic</code> constants
</h3><p>Usually, symbolic constants are some arbitrary literal cast to an
appropriate type, like this:
</p><pre><code>#define MY_MAGIC_PONY ((pony_t)-1)
</code></pre><p>This works for integer and floating point values, but is not
guaranteed by the standard to work for pointers (except for <code>0</code>, which
yields a null pointer constant). You might want to try anyway, or you
may take the address of some private dummy object instead.
</p><pre><code>#define MY_MAGIC_PONY (&my_magic_pony_)
extern struct pony my_magic_pony_;
</code></pre><p>Well, the bad news is that if you need that constant at run time,
there’s not much I can do for you; you’ll have to keep using that. On
the bright side, if the constant is only needed at compile time
(e.g. if it is always generated by some macro, to induce a specific
path in a conditional), there may be hope still.
</p><p>With <code>_Generic</code>, you can now specify conditions based on types, which
means, you can use dummy types instead of dummy values for your
symbolic compile-time-only constants:
</p><pre><code>#define MY_MAGIC_PONY ((struct dummy_magic_pony *)NULL)
struct dummy_magic_pony;
#define MY_MAGIC_MACRO(..., p, ...) \
... _Generic((p), \
struct dummy_magic_pony *: ..., \
default: ...) ...
</code></pre><p>OK, so what does this bring us? Well, three things:
</p><ul><li>We don’t need to create random objects for pointer constants.
</li><li>We don’t need to set aside a special value.
</li><li>And we don’t need to rely on the compiler eliminating spurious dead
branches everywhere because of macro expansion.
</li></ul><h3>Sample application 1: default arguments
</h3><p>So, we’ve seen how it’s done; sounds trivial, looks trivial, but what
can we use it for? If this were just for me, I’d say "it comes in
handy when you write complex macros sometimes", but I tried to come up
with a simple enough example for this short article: default
arguments. In case you may be wondering, though, this is <em>for
demonstration purposes only</em>; don’t try this at home… well, what
I mean is that probably nobody is going to use this, which is totally
fine.
</p><p>Anyway, while it is well-known(?) that default arguments were possible
in C99 using preprocessor hacks, all solutions I’ve seen were rather
cumbersome to implement (you’re welcome to prove me wrong; I haven’t
tried too hard to look for the nicest way).
</p><p>Probably the most usable solution comes with free keyword arguments
(called <i>named parameters</i>, in some languages, as well) as
a bonus. Just use a structure as your last parameter and stuff it with
a compound literal. The disadvantage is that your defaults are all
zeros (or whatever default initializer you get for the field
type)… unless you name all of your arguments and include defaults in
the compound literal; but that’s not what we’re aiming for here: we’re
looking for plain old optional positional parameters.
</p><p>You could also count the number of arguments in the variable argument
list of a macro, but this requires a lot of boilerplate to define
a version for each possible number of arguments.
</p><p>Lastly, you could use arbitrary symbols and test for equality using
preprocessor logic (for those who don’t know, it <em>is</em> possible with
the standard C99 preprocessor to macro-branch on whether a given
argument is equal to a few different things… it just requires quite
a lot of work in the background and has some limitations as well —
read the sources of any heavyweight preprocessor library and you’ll
see; e.g. the one provided with <a class="extern" href="http://sourceforge.net/projects/cos/">COS</a>). However, this has some quirks
(which are outside of the scope of this article) and is definitely not
for the casual preprocessor user. But the overall design is rather
appealing, so we’ll keep with that except…
</p><p>We can now use <code>_Generic</code> type constants instead of symbols. Let’s
look at some code:
</p><pre><code>/* Generic definitions, for all functions thereafter. */
struct dflarg_;
#define DFLARG ((struct dflarg_ *)NULL)
#define IFDFL(arg, dflval) \
_Generic((arg), \
struct dflarg_ *: dflval, \
default: (arg))
/*
* Some function foobar with two optional arguments.
* We take the second (non-optional) argument as part of
* __VA_ARGS__ so the list is never empty.
*/
int foobar(int, int, int, int);
#define foobar(x, ...) \
foobar_((x), __VA_ARGS__, DFLARG, DFLARG)
#define foobar_(x, y, z, t, ...) \
(foobar)((x), (y), IFDFL((z), 42), IFDFL((t), 36))
</code></pre><p>And here you go! Default arguments in C11 using <code>_Generic</code>.
</p><h3>Sample application 2: argument list length check
</h3><p>In our previous example, you’ve probably noticed that <code>foobar</code> now
accepts extra arguments, which is not exactly ideal. More generally,
it happens quite often with variadic macros (in my experience,
especially "helper" macros that tend to be buried under more
user-friendly ones, and that may need to handle the results of
concatenating, splitting, mapping, and other operations on previous
argument lists) that there’s a limit to how many arguments you
actually want to handle.
</p><p>Again, it is possible with the C99 preprocessor to check for the
argument list length, but this typically involves even more heavy
preprocessor logic than before, as you’ll want to do arithmetic with
the preprocessor. There are ways to avoid the arithmetics, but as far
as I know, they all require quite a bit of preprocessor
metaprogramming in their own right.
</p><p>With C11 and <code>_Generic</code>, however, you could just use a type-level
constant… how? This is really just more of the above (well, it <em>is</em>
the same trick, after all):
</p><pre><code>/* Our end-of-list marker is really just another default. */
#define EOARGS DFLARG
#define ISEOARGS(arg) \
_Generic((arg), \
struct dflarg_ *: true, \
default: false)
#define foobar(x, ...) \
foobar_((x), __VA_ARGS__, DFLARG, DFLARG, EOARGS)
#define foobar_(x, y, z, t, eoargs, ...) \
(_Static_assert(ISEOARGS(eoargs), \
"too many arguments to foobar"), \
(foobar)((x), (y), IFDFL((z), 42), IFDFL((t), 36)))
</code></pre><p>If you try this code… it should fail. That is because
<code>_Static_assert</code> is a declaration according to the C11 grammar. This
can be worked around by wrapping the <code>_Static_assert</code> in an inline
structure declaration within a compound literal, like so:
</p><pre><code>#define inline_static_assert(x, s) \
((void)(const struct { int _unused; \
_Static_assert((x), s); }){ 0 })
</code></pre><p>Unfortunately, this (supposedly corrected) code does not compile
with Clang 3.0. Otherwise, we’d get the following final macro for
<code>foobar_</code>:
</p><pre><code>#define foobar_(x, y, z, t, eoargs, ...) \
(inline_static_assert(ISEOARGS(eoargs), \
"too many arguments to foobar"), \
(foobar)((x), (y), IFDFL((z), 42), IFDFL((t), 36)))
</code></pre><p>I only have the N1570 draft so I can’t say for sure that this is
correct, but my copy specifically states that a <code>_Static_assert</code> can
occur inside a structure declaration (§ 6.7.2.1).
</p><p>Hence we’re left with emulating <code>_Static_assert</code>, with the traditional
negative array size trick, for example:
</p><pre><code>#define inline_static_assert(x, s) \
((void)(char * [(x) ? 1 : -1]){ s })
</code></pre><p>Now, the following call will fail to compile, although with an ugly
message — can’t have it all, I guess:
</p><pre><code>foobar(6, 7, 1+1, 3*4, 5/5);
</code></pre><h3>Conclusion
</h3><p>Well, this is it. <code>_Generic</code> is not widely supported yet, but
hopefully support will come soon enough (and in the meantime, you can
use <a class="extern" href="http://p99.gforge.inria.fr/">P99</a> if you’re so inclined), at least for people living outside
of the C-hater kingdom that Visual Studio has become. And once it
does, I think it will help with simplifying some preprocessor hacks
that used to require a lot of added ma^Wlogic in order to branch at
macro-expansion time.
</p>