Le truc qui fait que la gestion des dépendances est NP-complet c’est pas le graphe de dépendance en soi, si je me trompe pas, c’est qu’à chaque dépendance on a le choix entre plusieurs versions de dépendance et les contraintes qui font que certaines de ces versions ne sont pas toutes compatibles entre elles, ce qui nous donne un genre de problème de satisfaction de contraintes.
Effectivement, c'est ce que je me suis dit après avoir écrit le message, la NP-complétude vient peut être de la prise en compte des conflits entre paquets (ce qui revient à gérer la négation logique dans le problème SAT sous-jacent).
Après que les compilateurs effectuent déjà de l'élimination de code mort, je le sais bien. Mon interrogation, dans la lignée de celle d'arnaudus, est plutôt de savoir à quel point il est difficile de ne garder que ce qui est nécessaire et suffisant pour faire tourner le binaire, ni plus ni moins.
Dans l'exemple que j'ai écrit, il me semble bien que le compilateur OCaml va me lier statiquement tout le module List bien qu'une grande partie de son code ne soit pas utilisé. Dans le cas d'un langage orienté objet, si mon binaire n'utilise pas toutes les méthodes d'un objet, il n'est pas nécessaire de compiler les méthodes non utilisées. Mais à quel point cela peut-il perturber le schème de compilation pour le code d'un objet ?
Quand on fait de la liaison dynamique, on reporte la difficulté sur le gestionnaire de paquet qui doit alors gérer un problème NP-complet (mais c'est sans doute lié au problème de conflits, qui n'existe pas pour la liaison statique). En revanche, pour la liaison statique, ce n'est pas sûr que le problème soit tellement plus simple si on ne veut garder que ce qui est absolument nécessaire, ni plus ni moins, et résoudre la question dans son entière généralité.
Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
[^] # Re: À boire et à manger
Posté par kantien . En réponse au journal Un développeur qui dénonce. Évalué à 4.
Effectivement, c'est ce que je me suis dit après avoir écrit le message, la NP-complétude vient peut être de la prise en compte des conflits entre paquets (ce qui revient à gérer la négation logique dans le problème SAT sous-jacent).
Après que les compilateurs effectuent déjà de l'élimination de code mort, je le sais bien. Mon interrogation, dans la lignée de celle d'arnaudus, est plutôt de savoir à quel point il est difficile de ne garder que ce qui est nécessaire et suffisant pour faire tourner le binaire, ni plus ni moins.
Dans l'exemple que j'ai écrit, il me semble bien que le compilateur OCaml va me lier statiquement tout le module
Listbien qu'une grande partie de son code ne soit pas utilisé. Dans le cas d'un langage orienté objet, si mon binaire n'utilise pas toutes les méthodes d'un objet, il n'est pas nécessaire de compiler les méthodes non utilisées. Mais à quel point cela peut-il perturber le schème de compilation pour le code d'un objet ?Quand on fait de la liaison dynamique, on reporte la difficulté sur le gestionnaire de paquet qui doit alors gérer un problème NP-complet (mais c'est sans doute lié au problème de conflits, qui n'existe pas pour la liaison statique). En revanche, pour la liaison statique, ce n'est pas sûr que le problème soit tellement plus simple si on ne veut garder que ce qui est absolument nécessaire, ni plus ni moins, et résoudre la question dans son entière généralité.
Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.