LibraryWithoutImplicitExportIsPolynomial - Revision history

JaroslavTulach: /* Can we live with Complete Repositories? */

JaroslavTulach — Thu, 24 Jan 2019 03:48:38 GMT

Can we live with Complete Repositories?

←Older revision		Revision as of 03:48, 24 January 2019
Line 37:		Line 37:
	== Can we live with Complete Repositories? ==		== Can we live with Complete Repositories? ==

-	Some may say that ''complete repositories'' are not practical and they are hard to maintain. This may be correct when it is not easy to identify that one reuses a feature re-exported by some module. For example in case of [[~~BackwardCompatibility#~~Functional ~~Compatibility\|functional~~ compatibility]] one can depend on behaviour of a deeply hidden module (which is re-exported without direct dependency) and this is hard to identify.	+	Some may say that ''complete repositories'' are not practical and they are hard to maintain. This may be correct when it is not easy to identify that one reuses a feature re-exported by some module. For example in case of [[Functional compatibility]] one can depend on behaviour of a deeply hidden module (which is re-exported without direct dependency) and this is hard to identify.

	On the other hand, there are other kind of [[BackwardCompatibility]] where ''complete repositories'' are natural. During compilation one needs all the module [[JAR]]s or header files to be present, not just those that one directly depends on. Even if one includes just '''java.applet''' module (in the proposed [[Modular Java SE]]), one also needs '''java.awt''' because the [http://java.sun.com/javase/6/docs/api/java/applet/Applet.html Applet] class extends (e.g. re-exports) classes from the '''java.awt''' module. The same applies to [[C]]'s use of ''stdio.h'' - it also needs bunch of other include files.		On the other hand, there are other kind of [[BackwardCompatibility]] where ''complete repositories'' are natural. During compilation one needs all the module [[JAR]]s or header files to be present, not just those that one directly depends on. Even if one includes just '''java.applet''' module (in the proposed [[Modular Java SE]]), one also needs '''java.awt''' because the [http://java.sun.com/javase/6/docs/api/java/applet/Applet.html Applet] class extends (e.g. re-exports) classes from the '''java.awt''' module. The same applies to [[C]]'s use of ''stdio.h'' - it also needs bunch of other include files.

JaroslavTulach at 11:10, 8 January 2012

JaroslavTulach — Sun, 08 Jan 2012 11:10:38 GMT

←Older revision		Revision as of 11:10, 8 January 2012
Line 1:		Line 1:
		+	<skin>monobook</skin>
		+
	The [[LibraryReExportIsNPComplete]] outlined the problem one has to face when practicing [[DistributedDevelopment]]. The [[LibraryReExportIsNPComplete\|page]] also proved that in its global scope the problem is [[NP-Complete]] as any [[3SAT]] problem can be transformed to it.		The [[LibraryReExportIsNPComplete]] outlined the problem one has to face when practicing [[DistributedDevelopment]]. The [[LibraryReExportIsNPComplete\|page]] also proved that in its global scope the problem is [[NP-Complete]] as any [[3SAT]] problem can be transformed to it.

Apidesign: /* Making Compilation NP-Complete? */

Apidesign — Sun, 25 Dec 2011 20:35:30 GMT

Making Compilation NP-Complete?

←Older revision		Revision as of 20:35, 25 December 2011
Line 63:		Line 63:

	# '''module without dependencies''' - in almost any system there is at least one ''base'' module that does not have any dependencies. Computing set of dependencies of such module during compilation is obviously a constant operation.		# '''module without dependencies''' - in almost any system there is at least one ''base'' module that does not have any dependencies. Computing set of dependencies of such module during compilation is obviously a constant operation.
-	# when '''compiling a module <math>M</math>''' with direct dependencies on <math>M_1, ..., M_n</math>. We can assume that <math>M_1, ..., M_n</math> have all their transitive dependencies ~~already resolved~~ (otherwise ~~we would~~ not ~~have them in our~~ complete repository). Let's now collect all transitive dependencies of <math>M_1, ..., M_n</math> into a set and verify whether they are all consistent. This has already been explorered in [[#Merge of Configurations\|merge of configurations]] section and is known to be polynomial.	+	# when '''compiling a module <math>M</math>''' with direct dependencies on <math>M_1, ..., M_n</math>. We can assume that <math>M_1, ..., M_n</math> have all their transitive dependencies explicitly enumerated (otherwise they could not be part of the ''complete repository''). Let's now collect all transitive dependencies of <math>M_1, ..., M_n</math> into a set and verify whether they are all consistent. This has already been explorered in [[#Merge of Configurations\|merge of configurations]] section and is known to be polynomial.

	In case the merged configuration of <math>M_1, ..., M_n</math> are consistent, we have new, polynomially sized (at most n times maximal size of configuration of individual module) configuration for module <math>M</math>. If the merged configuration is not consistent, the compilation should fail (in polynomial time) and the module <math>M</math> should not be created at all. As a result the [[NP-Complete]] threat is eliminated during compilation.		In case the merged configuration of <math>M_1, ..., M_n</math> are consistent, we have new, polynomially sized (at most n times maximal size of configuration of individual module) configuration for module <math>M</math>. If the merged configuration is not consistent, the compilation should fail (in polynomial time) and the module <math>M</math> should not be created at all. As a result the [[NP-Complete]] threat is eliminated during compilation.

Apidesign: /* Making Compilation NP-Complete? */

Apidesign — Sun, 25 Dec 2011 20:29:30 GMT

Making Compilation NP-Complete?

←Older revision		Revision as of 20:29, 25 December 2011
Line 63:		Line 63:

	# '''module without dependencies''' - in almost any system there is at least one ''base'' module that does not have any dependencies. Computing set of dependencies of such module during compilation is obviously a constant operation.		# '''module without dependencies''' - in almost any system there is at least one ''base'' module that does not have any dependencies. Computing set of dependencies of such module during compilation is obviously a constant operation.
-	# when compiling a module <math>M</math> with direct dependencies on <math>M_1, ..., M_n</math>. We can assume that <math>M_1, ..., M_n</math> have all their transitive dependencies already resolved (otherwise we would not have them in our complete repository). Let's now collect all transitive dependencies of <math>M_1, ..., M_n</math> into a set and verify whether they are all consistent. This has already been explorered in [[#Merge of Configurations\|merge of configurations]] section and is known to be polynomial.	+	# when '''compiling a module <math>M</math>''' with direct dependencies on <math>M_1, ..., M_n</math>. We can assume that <math>M_1, ..., M_n</math> have all their transitive dependencies already resolved (otherwise we would not have them in our complete repository). Let's now collect all transitive dependencies of <math>M_1, ..., M_n</math> into a set and verify whether they are all consistent. This has already been explorered in [[#Merge of Configurations\|merge of configurations]] section and is known to be polynomial.

	In case the merged configuration of <math>M_1, ..., M_n</math> are consistent, we have new, polynomially sized (at most n times maximal size of configuration of individual module) configuration for module <math>M</math>. If the merged configuration is not consistent, the compilation should fail (in polynomial time) and the module <math>M</math> should not be created at all. As a result the [[NP-Complete]] threat is eliminated during compilation.		In case the merged configuration of <math>M_1, ..., M_n</math> are consistent, we have new, polynomially sized (at most n times maximal size of configuration of individual module) configuration for module <math>M</math>. If the merged configuration is not consistent, the compilation should fail (in polynomial time) and the module <math>M</math> should not be created at all. As a result the [[NP-Complete]] threat is eliminated during compilation.

Apidesign: /* Making Compilation NP-Complete? */

Apidesign — Sun, 25 Dec 2011 20:29:01 GMT

Making Compilation NP-Complete?

←Older revision		Revision as of 20:29, 25 December 2011
Line 63:		Line 63:

	# '''module without dependencies''' - in almost any system there is at least one ''base'' module that does not have any dependencies. Computing set of dependencies of such module during compilation is obviously a constant operation.		# '''module without dependencies''' - in almost any system there is at least one ''base'' module that does not have any dependencies. Computing set of dependencies of such module during compilation is obviously a constant operation.
-	# when compiling a module <math>M</math> with direct dependencies on <math>M_1, ..., M_n</math>. We can assume that <math>M_1, ..., M_n</math> have all their transitive dependencies already resolved. Let's now collect all transitive dependencies of <math>M_1, ..., M_n</math> into a set and verify whether they are all consistent. This has already been explorered in [[#Merge of Configurations\|merge of configurations]] section and is known to be polynomial.	+	# when compiling a module <math>M</math> with direct dependencies on <math>M_1, ..., M_n</math>. We can assume that <math>M_1, ..., M_n</math> have all their transitive dependencies already resolved (otherwise we would not have them in our complete repository). Let's now collect all transitive dependencies of <math>M_1, ..., M_n</math> into a set and verify whether they are all consistent. This has already been explorered in [[#Merge of Configurations\|merge of configurations]] section and is known to be polynomial.

	In case the merged configuration of <math>M_1, ..., M_n</math> are consistent, we have new, polynomially sized (at most n times maximal size of configuration of individual module) configuration for module <math>M</math>. If the merged configuration is not consistent, the compilation should fail (in polynomial time) and the module <math>M</math> should not be created at all. As a result the [[NP-Complete]] threat is eliminated during compilation.		In case the merged configuration of <math>M_1, ..., M_n</math> are consistent, we have new, polynomially sized (at most n times maximal size of configuration of individual module) configuration for module <math>M</math>. If the merged configuration is not consistent, the compilation should fail (in polynomial time) and the module <math>M</math> should not be created at all. As a result the [[NP-Complete]] threat is eliminated during compilation.

Apidesign: /* Merge of Configurations */

Apidesign — Sun, 25 Dec 2011 20:06:08 GMT

Merge of Configurations

←Older revision		Revision as of 20:06, 25 December 2011
Line 54:		Line 54:

	The complexity of the above algorithm is polynomial. The fact that configuration produced by it satisfies all the module dependencies is obvious. The proof that if the algorithm gives up, there is no configuration in the ''complete repository'' to satisfy all the modules dependencies is left for reader's consideration.		The complexity of the above algorithm is polynomial. The fact that configuration produced by it satisfies all the module dependencies is obvious. The proof that if the algorithm gives up, there is no configuration in the ''complete repository'' to satisfy all the modules dependencies is left for reader's consideration.
		+
		+	== Making Compilation [[NP-Complete]]? ==
		+
		+	Recent review of [[LibraryWithoutImplicitExportIsPolynomial\|this proof]] raised an interesting question: Does not the suggestion to generate set of module's transitive [[dependencies]] at compile time mean
		+	that you'd still have to run a general - and possibly [[NP-Complete]] - resolution algorithm at compile time in order to compute that set?
		+
		+	The [[NP-Complete\|NP-Complexity]] during compilation seems to be avoided as the compilation is always done from bottom to top. As such we should be able to apply concept of [[wikipedia:Mathematical_induction\|mathematical induction]]:
		+
		+	# '''module without dependencies''' - in almost any system there is at least one ''base'' module that does not have any dependencies. Computing set of dependencies of such module during compilation is obviously a constant operation.
		+	# when compiling a module <math>M</math> with direct dependencies on <math>M_1, ..., M_n</math>. We can assume that <math>M_1, ..., M_n</math> have all their transitive dependencies already resolved. Let's now collect all transitive dependencies of <math>M_1, ..., M_n</math> into a set and verify whether they are all consistent. This has already been explorered in [[#Merge of Configurations\|merge of configurations]] section and is known to be polynomial.
		+
		+	In case the merged configuration of <math>M_1, ..., M_n</math> are consistent, we have new, polynomially sized (at most n times maximal size of configuration of individual module) configuration for module <math>M</math>. If the merged configuration is not consistent, the compilation should fail (in polynomial time) and the module <math>M</math> should not be created at all. As a result the [[NP-Complete]] threat is eliminated during compilation.

	== Conclusion ==		== Conclusion ==

JaroslavTulach: /* Library Versioning Terminology II */

JaroslavTulach — Wed, 02 Sep 2009 08:49:41 GMT

Library Versioning Terminology II

←Older revision		Revision as of 08:49, 2 September 2009
Line 10:		Line 10:

	A repository <math>R=(M,D)</math> is said to be ''complete'' if '''the transitive dependencies are explicitly enumerated''':		A repository <math>R=(M,D)</math> is said to be ''complete'' if '''the transitive dependencies are explicitly enumerated''':
-	# <math>A_{x.y} \rightarrow B_{u.v} \in D \wedge \exist w >= v B_{u.w} \gg C_{p.q} \in D \Rightarrow \exists r <= q A_{x.y} \rightarrow C_{p.r} \in D</math>	+	# <math>A_{x.y} \rightarrow B_{u.v} \in D \wedge \exist (w >= v) B_{u.w} \gg C_{p.q} \in D \Rightarrow \exists (r <= q) A_{x.y} \rightarrow C_{p.r} \in D</math>
	In the above the symbol <math>\rightarrow</math> may mean dependency with re-export (e.g. <math>\gg</math>) or dependency without re-export (e.g. <math>></math>).		In the above the symbol <math>\rightarrow</math> may mean dependency with re-export (e.g. <math>\gg</math>) or dependency without re-export (e.g. <math>></math>).

JaroslavTulach at 08:26, 2 September 2009

JaroslavTulach — Wed, 02 Sep 2009 08:26:20 GMT

←Older revision		Revision as of 08:26, 2 September 2009
Line 58:		Line 58:

	The way to fight with [[NP-Complete]] nature of [[LibraryReExportIsNPComplete\|Module Dependency Problem]] is to generate ''complete repositories''. It is easy to create such repositories when one is primarily interested in coherent linkage of modules. All that is necessary is to modify our compilers to require (or infer and record) properly specified dependencies on all re-exported modules one is using, not just on the top level module that re-exports them.		The way to fight with [[NP-Complete]] nature of [[LibraryReExportIsNPComplete\|Module Dependency Problem]] is to generate ''complete repositories''. It is easy to create such repositories when one is primarily interested in coherent linkage of modules. All that is necessary is to modify our compilers to require (or infer and record) properly specified dependencies on all re-exported modules one is using, not just on the top level module that re-exports them.
		+
		+	== External Links ==
		+
		+	# Lambda the Ultimate [http://lambda-the-ultimate.org/node/3594 discussion]

JaroslavTulach: /* Merge of Configurations */

JaroslavTulach — Wed, 02 Sep 2009 07:59:07 GMT

Merge of Configurations

←Older revision		Revision as of 07:59, 2 September 2009
Line 45:		Line 45:
	== Merge of Configurations ==		== Merge of Configurations ==

-	One additional issue needs consideration. When starting a system, one often needs to enable more than a single module. Some [[~~modular systems~~]] provide good enough isolation, so running modules can use incompatible versions safely. However some systems require that each module is present in just a single version. The question then is: Is it easy to find out whether a set of modules can be enabled together (while only a single version of a module is present)?	+	One additional issue needs consideration. When starting a system, one often needs to enable more than a single module. Some [[module system]]s provide good enough isolation, so running modules can use incompatible versions safely. However some systems require that each module is present in just a single version. The question then is: Is it easy to find out whether a set of modules can be enabled together (while only a single version of a module is present)?

	Each module is equipped with a configuration (created during compilation). So the problem of enabling more modules reduces to a question whether, given a set of configurations one can find one which satisfies dependencies of all modules. This would be [[NP-Complete]] in common module repository, but in ''complete repositories'' this is a polynomial problem.		Each module is equipped with a configuration (created during compilation). So the problem of enabling more modules reduces to a question whether, given a set of configurations one can find one which satisfies dependencies of all modules. This would be [[NP-Complete]] in common module repository, but in ''complete repositories'' this is a polynomial problem.

	Just visit all the dependencies of all modules and if there is a dependency on module <math>A_{x.y}</math> and <math>A_{p.q}</math>, then:		Just visit all the dependencies of all modules and if there is a dependency on module <math>A_{x.y}</math> and <math>A_{p.q}</math>, then:
-	# '''choose most recent version''': if <math>x ~~\eq~~ p</math> keep just <math>A_{x.max(q, y)}</math>	+	# '''choose most recent version''': if <math>x = p</math> keep just <math>A_{x.max(q, y)}</math>
	# '''detect incompatibilities''': if <math>x \neq p</math> then give up		# '''detect incompatibilities''': if <math>x \neq p</math> then give up

JaroslavTulach: /* Conclusion */

JaroslavTulach — Wed, 02 Sep 2009 07:57:19 GMT

Conclusion

←Older revision		Revision as of 07:57, 2 September 2009
Line 42:		Line 42:

	As the compilation is closely tight to linkage (and ability to link defines [[BinaryCompatibility]]), it is easy to generate ''complete repository'' of modules that can later be easily assembled and linked for execution in polynomial time.		As the compilation is closely tight to linkage (and ability to link defines [[BinaryCompatibility]]), it is easy to generate ''complete repository'' of modules that can later be easily assembled and linked for execution in polynomial time.
		+
		+	== Merge of Configurations ==
		+
		+	One additional issue needs consideration. When starting a system, one often needs to enable more than a single module. Some [[modular systems]] provide good enough isolation, so running modules can use incompatible versions safely. However some systems require that each module is present in just a single version. The question then is: Is it easy to find out whether a set of modules can be enabled together (while only a single version of a module is present)?
		+
		+	Each module is equipped with a configuration (created during compilation). So the problem of enabling more modules reduces to a question whether, given a set of configurations one can find one which satisfies dependencies of all modules. This would be [[NP-Complete]] in common module repository, but in ''complete repositories'' this is a polynomial problem.
		+
		+	Just visit all the dependencies of all modules and if there is a dependency on module <math>A_{x.y}</math> and <math>A_{p.q}</math>, then:
		+	# '''choose most recent version''': if <math>x \eq p</math> keep just <math>A_{x.max(q, y)}</math>
		+	# '''detect incompatibilities''': if <math>x \neq p</math> then give up
		+
		+	The complexity of the above algorithm is polynomial. The fact that configuration produced by it satisfies all the module dependencies is obvious. The proof that if the algorithm gives up, there is no configuration in the ''complete repository'' to satisfy all the modules dependencies is left for reader's consideration.

	== Conclusion ==		== Conclusion ==

	The way to fight with [[NP-Complete]] nature of [[LibraryReExportIsNPComplete\|Module Dependency Problem]] is to generate ''complete repositories''. It is easy to create such repositories when one is primarily interested in coherent linkage of modules. All that is necessary is to modify our compilers to require (or infer and record) properly specified dependencies on all re-exported modules one is using, not just on the top level module that re-exports them.		The way to fight with [[NP-Complete]] nature of [[LibraryReExportIsNPComplete\|Module Dependency Problem]] is to generate ''complete repositories''. It is easy to create such repositories when one is primarily interested in coherent linkage of modules. All that is necessary is to modify our compilers to require (or infer and record) properly specified dependencies on all re-exported modules one is using, not just on the top level module that re-exports them.