Encodage sémantique

Un article de Wikipédia, l'encyclopédie libre.

Un encodage sémantique est une « traduction » entre deux langages formels.

Dans le domaine de l'informatique, les encodages les plus courants sont la compilation d'un langage de programmation en langage machine ou en langage intermédiaire et la conversion d'un document depuis un format de données vers un autre. La compilation d'un langage de mise en forme tel que TeX, LaTeX ou TEI vers PostScript ou PDF est aussi une forme d'encodage. De même, certains pré-processeurs de haut-niveau tels que Apple WorldScript ou Camlp4 pour Objective Caml, procèdent à des encodages entre divers langages de programmation.

[modifier] Définition

Formellement, un encodage d'un langage formel A dans un langage formel B est une fonction $[\cdot] : A \longrightarrow B$ qui, à chaque terme de A, associe un terme de B.

S'il existe un encodage 'satisfaisant' de A vers B, on considère que le langage B est 'au moins aussi puissant' (ou 'expressif') que le langage A.

[modifier] Propriétés des encodages

La notion informelle de « traduction » entre deux langages, ou même l'existence d'une fonction de A vers B, est insuffisante pour comparer l'expressivité de deux langages. En effet, pour peu que le langage B ne soit pas vide, il est toujours possible de trouver une fonction qui à tous les termes de A associe le même terme de B. Il est donc nécessaire de définir dans quelles circonstances un encodage est suffisant.

Cette notion dépend de l'application. Nous présentons ici quelques propriétés classiques considérées comme importantes.

[modifier] Préservation des compositions

$\Rightarrow$: Pour tout opérateur d'arité n $o p A$ dans A, il existe un opérateur d'arité n $o p B$ dans B tel que; $\forall T_A^1,T_A^2,\dots,T_A^n, [op_A(T_A^1,T_A^2,\cdots,T_A^n)] = op_B([T_A^1],[T_A^2],\cdots,[T_A^n])$
Interprétation: Si l'encodage dispose de cette propriété, il est possible de travailler sur des composants séparés, que ce soit pour les compiler ou pour les étudier. Cette propriété est généralement considérée comme indispensable.
$\Leftarrow$: Pour tout opérateur d'arité n $o p A$ dans A, il existe un opérateur d'arité n $o p B$ dans B tel que; $\forall T_B^1,T_B^2,\dots,T_B^n, \exists T_A^1,\dots,T_A^n, op_B(T_B^1,\cdots,T_B^N) = [op_A(T_A^1,T_A^2,\cdots,T_A^n)]$
Interprétation: Cette propriété garantit la possibilité de désencoder les termes encodés.