#### JaroslavTulach: /* Hide Incompatibilities! */ - 2011-10-30 06:12:01

Hide Incompatibilities!

 ←Older revision Revision as of 06:12, 30 October 2011 Line 104: Line 104: If you happen to reuse a library that cannot be trusted to keep its [[BackwardCompatibility]], then do whatever you can to not re-export its [[API]]s! This has been discussed in [[Chapter 10]], Cooperating with Other [[API]]s, but in short: If you hide such library for internal use and do not export any of its interfaces, you can use whatever version of library you want (even few years older) and nobody shall notice. Moreover in many [[module system]]s there can even be multiple versions of the same library in case they are not re-exported. If you happen to reuse a library that cannot be trusted to keep its [[BackwardCompatibility]], then do whatever you can to not re-export its [[API]]s! This has been discussed in [[Chapter 10]], Cooperating with Other [[API]]s, but in short: If you hide such library for internal use and do not export any of its interfaces, you can use whatever version of library you want (even few years older) and nobody shall notice. Moreover in many [[module system]]s there can even be multiple versions of the same library in case they are not re-exported. + + ==== Explicit Re-export ==== + + Looks like there is a way to eliminate the NP-Completeness by disabling implicit re-export. See [[LibraryWithoutImplicitExportIsPolynomial]]. However this works only in a system with standardized versioning policy + and without use of [[RangeDependencies]]. == Conclusion == == Conclusion ==

#### JaroslavTulach: /* External Links */ - 2010-07-30 16:25:21

 ←Older revision Revision as of 16:25, 30 July 2010 Line 113: Line 113: # discussion at [http://lambda-the-ultimate.org/node/3588 Lambda the Ultimate] # discussion at [http://lambda-the-ultimate.org/node/3588 Lambda the Ultimate] # LtU guys pointed out that the proof has already been published: [http://people.debian.org/~dburrows/model.pdf D. Burrows, Modelling and Resolving Software Dependencies] # LtU guys pointed out that the proof has already been published: [http://people.debian.org/~dburrows/model.pdf D. Burrows, Modelling and Resolving Software Dependencies] - # Equinox is said to [http://blog.bjhargrave.com/2008/03/equinox-and-google-summer-of-code.html use SAT4J solver] + # [[Equinox]] is said to [http://blog.bjhargrave.com/2008/03/equinox-and-google-summer-of-code.html use SAT4J solver] # EDOS Project seems to find similar proof: See section 3.2 in [http://www.edos-project.org/xwiki/bin/download/Main/D2-1/edos-wp2d1.pdf edos-wp2d1.pdf] # EDOS Project seems to find similar proof: See section 3.2 in [http://www.edos-project.org/xwiki/bin/download/Main/D2-1/edos-wp2d1.pdf edos-wp2d1.pdf]

#### JaroslavTulach: /* Implications */ - 2009-10-16 12:51:20

Implications

 ←Older revision Revision as of 12:51, 16 October 2009 Line 82: Line 82: '''qed'''. '''qed'''. + + == Polemics == + + One of the critiques raised during the LtU review (linked in external sources) is that the kind of situation cannot happen in practise. Surprisingly it can. [[OSGi]] and its [[RangeDependencies]] lead naturally into [[NP-Complete]] problems. [[RangeDependencies|Read more]]... == Implications == == Implications == Line 100: Line 104: If you happen to reuse a library that cannot be trusted to keep its [[BackwardCompatibility]], then do whatever you can to not re-export its [[API]]s! This has been discussed in [[Chapter 10]], Cooperating with Other [[API]]s, but in short: If you hide such library for internal use and do not export any of its interfaces, you can use whatever version of library you want (even few years older) and nobody shall notice. Moreover in many [[module system]]s there can even be multiple versions of the same library in case they are not re-exported. If you happen to reuse a library that cannot be trusted to keep its [[BackwardCompatibility]], then do whatever you can to not re-export its [[API]]s! This has been discussed in [[Chapter 10]], Cooperating with Other [[API]]s, but in short: If you hide such library for internal use and do not export any of its interfaces, you can use whatever version of library you want (even few years older) and nobody shall notice. Moreover in many [[module system]]s there can even be multiple versions of the same library in case they are not re-exported. - == Conclusion == == Conclusion ==

#### JaroslavTulach at 09:31, 12 October 2009 - 2009-10-12 09:31:48

 ←Older revision Revision as of 09:31, 12 October 2009 Line 2: Line 2: This page starts by describing a way to convert any [[3SAT]] problem to a solution of finding whether there is a way to satisfy all dependencies of a library in a repository of libraries. Thus proving that the later problem is [[wikipedia::NP-complete|NP-Complete]]. Then it describes the importance of such observations on our [[DistributedDevelopment|development practices]]. This page starts by describing a way to convert any [[3SAT]] problem to a solution of finding whether there is a way to satisfy all dependencies of a library in a repository of libraries. Thus proving that the later problem is [[wikipedia::NP-complete|NP-Complete]]. Then it describes the importance of such observations on our [[DistributedDevelopment|development practices]]. + + There are similar observations for other module systems ([[RPM]] and [[Debian]], see the external references section), with almost identical proof. The only difference is that both [[RPM]] and [[Debian]] allow easy way to specify negation by use of ''obsolete'' directive (thus it is easy to map the [[3SAT]] formula). The unique feature of [[LibraryReExportIsNPComplete|this]] proof is that it does not need negation at all. Instead it deals with re-export of an [[API]]. As re-export of [[API]]s is quite common in software development, it brings implications of this kind of problem closer to reality. == [[3SAT]] == == [[3SAT]] ==

#### JaroslavTulach: /* Conversion of 3SAT to Module Dependencies Problem */ - 2009-09-02 08:59:19

Conversion of 3SAT to Module Dependencies Problem

 ←Older revision Revision as of 08:59, 2 September 2009 Line 53: Line 53: All these modules and dependencies are added into repository $R$ All these modules and dependencies are added into repository $R$ - Now we will create a module $T_{1.0}$ that depends all formulas: + Now we will create a module $T_{1.0}$ that depends on all formulas: :$T_{1.0} \gg F^1_{1.0}$ :$T_{1.0} \gg F^1_{1.0}$ :$T_{1.0} \gg F^2_{1.0}$ :$T_{1.0} \gg F^2_{1.0}$

#### JaroslavTulach: /* Proof */ - 2009-09-02 08:56:47

Proof

 ←Older revision Revision as of 08:56, 2 September 2009 Line 75: Line 75: For $i$-th ''3-or'' there is $T_{1.0} \gg F^i_{1.0}$ dependency which is satisfied. That means $F^i_{1.1} \in C \vee F^i_{1.2} \in C \vee F^i_{1.3} \in C$ - at least one version of $F^i$ module is present in the configuration. The one $F^i$ that has the satisfied dependency reexports $M^j_{1.0}$ (which means $v_j = true$) or $M^j_{2.0}$ (which means $v_j = false$). Anyway each $i$ ''3-or'' evaluates to $true$. For $i$-th ''3-or'' there is $T_{1.0} \gg F^i_{1.0}$ dependency which is satisfied. That means $F^i_{1.1} \in C \vee F^i_{1.2} \in C \vee F^i_{1.3} \in C$ - at least one version of $F^i$ module is present in the configuration. The one $F^i$ that has the satisfied dependency reexports $M^j_{1.0}$ (which means $v_j = true$) or $M^j_{2.0}$ (which means $v_j = false$). Anyway each $i$ ''3-or'' evaluates to $true$. - The only remaining question is whether a $C$ configuration can force truth variable $v_j$ to be true in one ''3-or'' and false in another. However that would mean that there is re-export via $T_{1.0} \gg F^i_{1.x} \gg M^j_{1.0}$ and also another one via $T_{1.0} \gg F^p_{1.u} \gg M^j_{2.0}$. However those two ''chain of dependencies'' ending in different versions of $M^j$ cannot be in one $C$ as that breaks the last condition of configuration definition. Thus each $M^j$ is represented only by one version and each $v_j$ is evaluated either to true or false, but never both. + The only remaining question is whether a $C$ configuration can force truth variable $v_j$ to be true in one ''3-or'' and false in another. However that would mean that there is re-export via $T_{1.0} \gg F^i_{1.x} \gg M^j_{1.0}$ and also another one via $T_{1.0} \gg F^p_{1.u} \gg M^j_{2.0}$. However those two ''chain of dependencies'' ending in different versions of $M^j$ cannot be in one $C$ as that breaks the last condition of configuration definition (each imported object has just one meaning). Thus each $M^j$ is represented only by one version and each $v_j$ is evaluated either to true or false, but never both. The [[3SAT]] formula's evaluation based on the configuration $C$ is consistent and satisfies the formula. The [[3SAT]] formula's evaluation based on the configuration $C$ is consistent and satisfies the formula.

#### JaroslavTulach: /* Proof */ - 2009-09-02 08:55:25

Proof

 ←Older revision Revision as of 08:55, 2 September 2009 Line 73: Line 73: "$\Rightarrow$": Let's have a $C$ configuration satisfies all dependencies of $T_{1.0}$. Can we also find positive valuation of [[3SAT]] formula? "$\Rightarrow$": Let's have a $C$ configuration satisfies all dependencies of $T_{1.0}$. Can we also find positive valuation of [[3SAT]] formula? - For $i$-th ''3-or'' there is $T_{1.0} \gg F^i_{1.0}$ dependency which is satisfied. That means $F^i_{1.1} \in C \vee F^i_{1.2} \in C \vee F^i_{1.3}$ - at least one version of $F^i$ module is present in the configuration. The one $F^i$ that has the satisfied dependency reexports $M^j_{1.0}$ (which means $v_j = true$) or $M^j_{2.0}$ (which means $v_j = false$). Anyway each $i$ ''3-or'' evaluates to $true$. + For $i$-th ''3-or'' there is $T_{1.0} \gg F^i_{1.0}$ dependency which is satisfied. That means $F^i_{1.1} \in C \vee F^i_{1.2} \in C \vee F^i_{1.3} \in C$ - at least one version of $F^i$ module is present in the configuration. The one $F^i$ that has the satisfied dependency reexports $M^j_{1.0}$ (which means $v_j = true$) or $M^j_{2.0}$ (which means $v_j = false$). Anyway each $i$ ''3-or'' evaluates to $true$. The only remaining question is whether a $C$ configuration can force truth variable $v_j$ to be true in one ''3-or'' and false in another. However that would mean that there is re-export via $T_{1.0} \gg F^i_{1.x} \gg M^j_{1.0}$ and also another one via $T_{1.0} \gg F^p_{1.u} \gg M^j_{2.0}$. However those two ''chain of dependencies'' ending in different versions of $M^j$ cannot be in one $C$ as that breaks the last condition of configuration definition. Thus each $M^j$ is represented only by one version and each $v_j$ is evaluated either to true or false, but never both. The only remaining question is whether a $C$ configuration can force truth variable $v_j$ to be true in one ''3-or'' and false in another. However that would mean that there is re-export via $T_{1.0} \gg F^i_{1.x} \gg M^j_{1.0}$ and also another one via $T_{1.0} \gg F^p_{1.u} \gg M^j_{2.0}$. However those two ''chain of dependencies'' ending in different versions of $M^j$ cannot be in one $C$ as that breaks the last condition of configuration definition. Thus each $M^j$ is represented only by one version and each $v_j$ is evaluated either to true or false, but never both.

#### JaroslavTulach: /* Proof */ - 2009-09-02 08:55:03

Proof

 ←Older revision Revision as of 08:55, 2 September 2009 Line 73: Line 73: "$\Rightarrow$": Let's have a $C$ configuration satisfies all dependencies of $T_{1.0}$. Can we also find positive valuation of [[3SAT]] formula? "$\Rightarrow$": Let's have a $C$ configuration satisfies all dependencies of $T_{1.0}$. Can we also find positive valuation of [[3SAT]] formula? - For $i$-th ''3-or'' there is $T_{1.0} \gg F^i_{1.0}$ dependency which is satisfied. At least by one from $F^i_{1.1}$ or $F^i_{1.2}$ or $F^i_{1.3}$. The one $F^i$ that has the satisfied dependency reexports $M^j_{1.0}$ (which means $v_j = true$) or $M^j_{2.0}$ (which means $v_j = false$). Anyway each $i$ ''3-or'' evaluates to $true$. + For $i$-th ''3-or'' there is $T_{1.0} \gg F^i_{1.0}$ dependency which is satisfied. That means $F^i_{1.1} \in C \vee F^i_{1.2} \in C \vee F^i_{1.3}$ - at least one version of $F^i$ module is present in the configuration. The one $F^i$ that has the satisfied dependency reexports $M^j_{1.0}$ (which means $v_j = true$) or $M^j_{2.0}$ (which means $v_j = false$). Anyway each $i$ ''3-or'' evaluates to $true$. The only remaining question is whether a $C$ configuration can force truth variable $v_j$ to be true in one ''3-or'' and false in another. However that would mean that there is re-export via $T_{1.0} \gg F^i_{1.x} \gg M^j_{1.0}$ and also another one via $T_{1.0} \gg F^p_{1.u} \gg M^j_{2.0}$. However those two ''chain of dependencies'' ending in different versions of $M^j$ cannot be in one $C$ as that breaks the last condition of configuration definition. Thus each $M^j$ is represented only by one version and each $v_j$ is evaluated either to true or false, but never both. The only remaining question is whether a $C$ configuration can force truth variable $v_j$ to be true in one ''3-or'' and false in another. However that would mean that there is re-export via $T_{1.0} \gg F^i_{1.x} \gg M^j_{1.0}$ and also another one via $T_{1.0} \gg F^p_{1.u} \gg M^j_{2.0}$. However those two ''chain of dependencies'' ending in different versions of $M^j$ cannot be in one $C$ as that breaks the last condition of configuration definition. Thus each $M^j$ is represented only by one version and each $v_j$ is evaluated either to true or false, but never both.