JigsawServices

From APIDesign

(Difference between revisions)
Jump to: navigation, search
Line 1: Line 1:
[[Jigsaw]] is a project that modularizes [[Java]] core parts with the plan to set an example up the [[modularity]] should be done in [[Java]]. [[NetBeans]] IDE needs to [[netbeans:Jigsaw|care]] about [[Jigsaw]], as [[NetBeans]] IDE is the primary tooling for [[OpenJDK]]. I am interested in the project due to another reason as well: [[dependencies]] in [[modular system]]s are subject to [[NP-Complete]] problems: The [[LibraryReExportIsNPComplete]] and for example [[OSGi]] suffers from that. It would be amazing, if we could learn from past mistakes and come up with a system of [[dependencies] that is not inherently [[NP-Complete]].
[[Jigsaw]] is a project that modularizes [[Java]] core parts with the plan to set an example up the [[modularity]] should be done in [[Java]]. [[NetBeans]] IDE needs to [[netbeans:Jigsaw|care]] about [[Jigsaw]], as [[NetBeans]] IDE is the primary tooling for [[OpenJDK]]. I am interested in the project due to another reason as well: [[dependencies]] in [[modular system]]s are subject to [[NP-Complete]] problems: The [[LibraryReExportIsNPComplete]] and for example [[OSGi]] suffers from that. It would be amazing, if we could learn from past mistakes and come up with a system of [[dependencies] that is not inherently [[NP-Complete]].
 +
 +
 +
One of the primary suspects for the complexity were [[RangeDependenciesAnalysed|range dependencies]], but we [[RangeDependenciesAnalysed|know now]] that it is not the real problem. A threat of [[NP-Complete]]ness still remains in the form of services. Here is a simple sketch showing why system with service dependencies can solve [[3-SAT]]. The full proof would be similar to [[LibraryReExportIsNPComplete]]. Imagine a module which requires two services:
 +
 +
<source lang="java">
 +
module base {
 +
requires service a;
 +
requires service b;
 +
}
 +
</source>
 +
 +
and let's imagine that there are two modules providing service ''a'' named ''A1'', 'A2'' and there are two modules providing service ''b'' named ''B1'', ''B2''. We need to select at least one of the A modules and one of the B modules. But the problem is that while resolving these modules, they may render themselves as mutually incompatible. Imagine:
 +
 +
# Try ''A1'' - [[good]], it resolves
 +
# Try ''A2'' - no it does not resolve, conflicts with some dependencies of ''A1''
 +
# Try ''B1'' - no it does not resolve, conflicts with some dependencies of ''A1''
 +
# Try ''B2'' - no it does not resolve, conflicts with some dependencies of ''A2''
 +
 +
Time to give up? No, not at all. Let's ''backtrack'' and instead of using ''A1'' let's try ''A2'':
 +
 +
# Try ''A2'' - [[good]], it resolves (as ''A1'' is disabled)
 +
# Try ''B1'' - [[good]], it resolves now (as ''A1'' is disabled and ''A2'' has more suitable [[dependencies]])
 +
 +
The fact that we have multiple choices and we need to try them in various combinations makes the whole system [[NP-Complete]] (as that is basically the [[3-SAT]] problem). How could we eliminate [[NP-Complete]]ness?

Revision as of 08:46, 21 June 2012

Jigsaw is a project that modularizes Java core parts with the plan to set an example up the modularity should be done in Java. NetBeans IDE needs to care about Jigsaw, as NetBeans IDE is the primary tooling for OpenJDK. I am interested in the project due to another reason as well: dependencies in modular systems are subject to NP-Complete problems: The LibraryReExportIsNPComplete and for example OSGi suffers from that. It would be amazing, if we could learn from past mistakes and come up with a system of [[dependencies] that is not inherently NP-Complete.


One of the primary suspects for the complexity were range dependencies, but we know now that it is not the real problem. A threat of NP-Completeness still remains in the form of services. Here is a simple sketch showing why system with service dependencies can solve 3-SAT. The full proof would be similar to LibraryReExportIsNPComplete. Imagine a module which requires two services: 

module base {
  requires service a;
  requires service b;
}

and let's imagine that there are two modules providing service a named A1, 'A2 and there are two modules providing service b named B1, B2. We need to select at least one of the A modules and one of the B modules. But the problem is that while resolving these modules, they may render themselves as mutually incompatible. Imagine:

  1. Try A1 - good, it resolves
  2. Try A2 - no it does not resolve, conflicts with some dependencies of A1
  3. Try B1 - no it does not resolve, conflicts with some dependencies of A1
  4. Try B2 - no it does not resolve, conflicts with some dependencies of A2

Time to give up? No, not at all. Let's backtrack and instead of using A1 let's try A2:

  1. Try A2 - good, it resolves (as A1 is disabled)
  2. Try B1 - good, it resolves now (as A1 is disabled and A2 has more suitable dependencies)

The fact that we have multiple choices and we need to try them in various combinations makes the whole system NP-Complete (as that is basically the 3-SAT problem). How could we eliminate NP-Completeness?

Retrieved from "http://wiki.apidesign.org/wiki/JigsawServices"
Personal tools
buy