| ←Older revision |
Revision as of 13:12, 8 January 2012 |
| Line 3: |
Line 3: |
| | [[Dependencies]] are important part of every [[Module system]]. [[Dependencies]] are here to abstract the complex relationship between a [[module]] and environment it needs for its own execution, compilation, linkage, etc. [[Dependencies]] are always a simplification of the real requirements, but that does not stop people from inventing new and new ways how to specify them more precisely. | | [[Dependencies]] are important part of every [[Module system]]. [[Dependencies]] are here to abstract the complex relationship between a [[module]] and environment it needs for its own execution, compilation, linkage, etc. [[Dependencies]] are always a simplification of the real requirements, but that does not stop people from inventing new and new ways how to specify them more precisely. |
| | | | |
| - | It [[dependencies|has already been discussed]] that dependency needs some lower bound (the moment when the needed [[API]] is first introduced) and also some higher bound (as incompatible changes are so often). How do we formalize it? Well, let's use some mathematics and describe dependencies as [[interval]]! As a result a dependency on any compatible version 1.4.3 and later, would be written as <math>some.library \in [ 1.4.3, 2.0)</math>. | + | It [[dependencies|has already been discussed]] that dependency needs some lower bound (the moment when the needed [[API]] is first introduced) and also some higher bound (as incompatible changes are so often). How do we formalize it? Well, let's use some mathematics and describe dependencies as [[interval]]! As a result a dependency on any compatible version 1.4.3 and later (in the interpretation of [[semantic versioning]]), would be written as <math>some.library \in [ 1.4.3, 2.0)</math>. |
| | | | |
| - | This looks like a very good solution. It is also very [[Rationalism|rationalistic]]. It is reusing knowledge gained by mathematics in past and thus it cannot be wrong! Moreover it is ''general'' enough - one can use the same notation to express [[dependencies|equality dependency]] by writing <math>some.library \in [1.4.3, 1.4.3]</math>. And also it is ''flexible'' as one can also depend on a smaller range of versions <math>some.library \in [1.4.3, 1.5)</math>. Last, but not least this solution also supports some level of [[cluelessness]] as it builds on something every programmer must have heart of during own school days. | + | This looks like a very good solution. It is also very [[Rationalism|rationalistic]]. It is reusing knowledge gained and verified by mathematicians in the past. How could something like that be wrong!? Moreover it is ''general'' enough - one can use the same notation to express [[dependencies|equality dependency]] by writing <math>some.library \in [1.4.3, 1.4.3]</math>. And also it is more flexible as one can also depend on a smaller range of versions <math>some.library \in [1.4.3, 1.5)</math>. Last, but not least this solution also supports some level of [[cluelessness]] as it builds on something every programmer must have heart of during own school days. |
| | | | |
| - | No wonder that everyone one who wants to be seen as providing ''well designed'', ''deeply thought out'', ''powerful'' and ''theoretically backed'' solution will choose [[interval]]s. This is probably the reason why [[OSGi]] decided to use this kind of dependencies. | + | No wonder that everyone one who wants to be seen as providing ''well designed'', ''deeply thought out'', ''powerful'' and ''theoretically backed'' solution will choose [[interval]]s. This is probably the reason why [[OSGi]] decided to use this kind of dependencies. However there is important hidden catch: |
| | + | [[wikipedia::Too_Much_Love_Will_Kill_You|Too Much Flexibility]] may lead to [[NP-Complete]] (e.g. almost unsolvable problems). This page outlines the problems as well as possible solution to avoid [[NP-Complete]]ness. |
| | | | |
| | + | == Enhanced Range [[Dependencies]] == |
| | | | |
| - | ==== [[wikipedia::Too_Much_Love_Will_Kill_You|Too Much Flexibility will Kill You]]! ====
| + | {{:Upper bound}} |
| - | | + | |
| - | Although it may seem flexible, overusing [[RangeDependencies]] may lead to system that is too complex and almost no longer manageable. What traditionally happens only when people release incompatible versions (due to [[TransitivityOfIncompatibleChange]]) can suddenly happen in regular situations.
| + | |
| - | | + | |
| - | The [[LibraryReExportIsNPComplete|proof]] claiming that managing module [[dependencies]] is [[NP-Complete]] operates with three types of modules:
| + | |
| - | | + | |
| - | # <math>M^i</math> which is present in two incompatible versions
| + | |
| - | # <math>F^j</math> which is present in three compatible versions
| + | |
| - | # a single module <math>T</math>
| + | |
| - | | + | |
| - | The [[LibraryReExportIsNPComplete|claim]] is made that finding whether module <math>T</math> can be enabled is [[NP-Complete]].
| + | |
| - | | + | |
| - | One of the most profound critiques however argues that it is wrong if three compatible versions of module <math>F^j</math> depend on incompatible versions of some other modules. This is valid observation, yet one can easily address it using [[RangeDependencies]]!
| + | |
| - | | + | |
| - | # instead of two incompatible versions of <math>M^i</math> define two compatible versions: <math>M^i_{1.1}</math> and <math>M^i_{1.2}</math>
| + | |
| - | # use strict range for dependencies of <math>F^j</math>, so <math>F^j_{1.1}</math> depends on <math>M^i \in [1.1, 1.1]</math> or <math>F^j_{1.2}</math> depends on <math>M^i \in [1.2, 1.2]</math>
| + | |
| - | # single module <math>T</math> continue to depend on classical range of <math>F^j \in [1.0, 2.0)</math>
| + | |
| - | | + | |
| - | This scenario describes accepted practices of [[DistributedDevelopment]]. Imagine, there is one team providing various versions of module <math>M^i</math>. This team does its best to keep [[BackwardCompatibility]]. It is using versioning in the traditional way to denote compatible versions - e.g. the first ''major'' number stays the same, the second ''minor'' one is incremented with each new, compatible version.
| + | |
| - | | + | |
| - | Yet there is some other distant team producing module(s) <math>F^j</math> and this team (or its quality department) is afraid of ''signing blank checks'' and trusting the ''M''-team to produce compatible versions. Thus they use restricted [[RangeDependency]] to require just subset of the versions (only those known during testing).
| + | |
| - | | + | |
| - | This is all that needs to happen. No incompatibilities, just a simple use of [[RangeDependencies]] and we are now facing an [[NP-Complete]] problem. This probably explains why there is [[3SAT]] solver behind [[Equinox]]. Finding the right setup of modules depending on each other with [[RangeDependencies]] can be really hard. [[NP-Complete]]ly hard.
| + | |