CSP, the pi-calculus and CPA-2005

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

CSP, the pi-calculus and CPA-2005

P.H.Welch

Hi,

This is the busiest mailing list to which I'm subscribed - by quite a bit!
Which is good, :).  I'm afraid I'm only a quiet observer right now, but
it's very interesting and useful.  One day I hope to chip in.

This is a small chip in.  For a concurrency interest list, it is surprising
to see no discussion based on analysing what you are doing and what you are
wanting to do using the viewpoint and mathematics of process algebra - in
particular, Hoare's CSP and Milner's pi-calculus.  These have lots to offer
about practical issues (and, certainly, Java ones) and are starting to get
together - a powerful combination.

For the interested, here are three URLs on recent and about-to-happen
conferences:

  http://www.cs.auc.dk/~luca/BICI/PA-05/         (1-5 August, 2005)
  http://www.lsbu.ac.uk/menass/csp25/            (6-8 July, 2004)
  http://wotug.org/cpa2005/programme.shtml       (18-21 September, 2005)

The first two celebrated the first 25 years of process algebra - and are
well worth tracking down the proceedings.  The third is about to happen
in Eindhoven, The Netherlands.  CPA is only a small conference with
a single stream of presentations, including evening Fringe sessions in
the hotel (basement) bar.  If any are this (European) side of the Atlantic
next month, you may enjoy!

I guess this is a (last minute) call for delegates, but I hope it's more
than that.  The reason we take these algebras so seriously is that we do
want to build complex systems that work ... much more easily than we manage
to achieve at the moment.  The ideas spinning from the maths gives us
formal (i.e steady/precise) platforms from which very efficient technology
grows (much of which is Java relevant).  These include highly dynamic
systems, including mobility and location awareness, hardware design and
hardware-software co-design, new languages, old languages, embedded,
distributed and super computing and more.

Many thanks for your time,

Peter Welch.
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: CSP, the pi-calculus and CPA-2005

Miles Sabin
P.H.Welch wrote,
> This is a small chip in.  For a concurrency interest list, it is
> surprising to see no discussion based on analysing what you are doing
> and what you are wanting to do using the viewpoint and mathematics of
> process algebra - in particular, Hoare's CSP and Milner's
> pi-calculus.  These have lots to offer about practical issues (and,
> certainly, Java ones) and are starting to get together - a powerful
> combination.

I think you'll find that many of the people on this list have an
interest in process algebras in one way or another. But I'm not quite
so surprised that they don't get discussed here ... the process algebra
approach to concurrency is very different from the threads, locks and
shared state approach that's hard-wired into Java and reflected in JSR
166.

FWIW, JSR 121, the Java Isolation API, has a CSP/pi-ish feel to it:
communication is based on message passing rather than shared state,
communication channels can be passed across communication channels for
scope extrusion. Pete Soper's collected various things you might find
interesting here,

  http://www.bitser.net/isolate-interest/

Cheers,


Miles
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: CSP, the pi-calculus and CPA-2005

P.H.Welch
In reply to this post by P.H.Welch

Thanks to Miles Sabin and Peter Soper for their replies.

Miles wrote:
> I think you'll find that many of the people on this list have an
> interest in process algebras in one way or another. But I'm not quite
> so surprised that they don't get discussed here ... the process algebra
> approach to concurrency is very different from the threads, locks and
> shared state approach that's hard-wired into Java and reflected in JSR
> 166.

No, there's a misunderstanding here about what process algebra offers.

Regarding threads, locks and shared state there is plenty on offer -
like formal characterisations that allow formal reasoning and automated
model-checking.  In turn, this leads to precise design of the various
high-level locking mechanisms you want, correct implementation, correct
low-level code generation ... all the way down to correct and fast hardware
support ... all the way up to correct applications.

CSP/pi mechanisms are extremely primitive, have a rich mathematics and
can be formed into patterns that capture any synchronisation mechanism
you fancy - some will be more useful than others, of course!  For instance,
CSP "events" are the basis for channel communications (all sorts), barriers
(multiway synchronisation) and pretty much anything.

Shared state?  Easy!  Let x be a variable visible to many threads.  Then:

  Var (x, value) = load.x!value -> Var (x, value)
                   []
                   store.x?newValue -> Var (x, newValue)

is a process allowing its use by any number of threads (= other processes).
In the above, "Var" is a generic variable process, "x" is an integer specific
to a particular variable (e.g. it may be its address) and "value" is some
initial value for that variable.  The channel names "load" and "store" reflect
the point of view of processes using the variables.

Any process knowing "x" can now use the variable.  For instance, an assignment:

  x = y

is modelled as the CSP process:

  load.y?tmp -> store.x!tmp -> SKIP

which looks interestingly like a compilation to machine code, though to a machine
that is formally specified, :).

Of course, there is absolutely no protection against arbitrary interleaving of
loads and stores on the same variable by multiple processes - the point being
that such problems fall naturally into the scope of CSP.  Fixing them, through
higher level constraints ("healthiness conditions") can now begin.

Another example: variables with various "atomic" update operators ...

  AtomicVar (x, value) =
    load.x!value -> AtomicVar (x, value)
    []
    store.x?newValue -> AtomicVar (x, newValue)
    []
    getAndSet.x?newValue -> getAndSetReply.x!value -> AtomicVar (x, newValue)
    []
    compareAndSet.x?expect?update ->
      (compareAndSetReply.x!true -> AtomicVar (x, newValue) <| expect = value |>
       compareAndSetReply.x!false -> AtomicVar (x, value)
      )

etc.  Again, the point is that it's easy to express this stuff formally and
that we should do so.  Apart from anything else, it makes their implementation
and applications using them amenable to automated model checking ... which can
save months/years of debugging.  CSP has the commercial FDR ("Failures-
Divergences-Refinement") model checker of Formal Systems (Europe) Ltd:

  http://www.fsel.com/software.html

It's commercial - you have to pay (I have no relationship with Formal Systems!),
though it's cheap for university research.  But it's really useful.

A while back, we had to build a formal (CSP) model of the standard Java monitor
mechanisms (synchronized/wait/notify/notifyAll).  The trickiest part was making
as sure as possible that we had captured all the informally expressed semantics
from the original "specifications" - an impossible thing to prove, of course.
Anyway, the CSP modelling is quite short - slides 20-36 of:

  http://www.cs.kent.ac.uk/projects/ofa/jcsp/csp-java-model.ppt

The reason we had to do this was to correct the JCSP implementation of CSP
external choice, [] - the JCSP "Alternative", where a process waits passively
for any one of a number of events to occur and reacts accordingly.  We released
JCSP back in 1997 but a bug in its "Alternative" didn't show up till 1999, when
it caused a bit of a panic!  Took a whole week to "fix".  Concerned, we built
the CSP model of Java monitors and could then apply FDR to check that our Java
implementation of choice was equivalent to a direct CSP choice.  Applying the
check to our original implementation threw up the counter-example trace that
yielded the deadlock our users had encountered.  The check took about just
a few (< 5) seconds.  Really should have done that way back!  Anyone interested
can look at the rest of the slides above or read the paper:

  http://www.wotug.org/paperdb/send_file.php?id=44

which also contains the formal model of Java monitors.  This paper is from 2000.
Are there other formal specifications of this?  If not, why ... ?

BTW, JCSP is outlined in the final chapter of Doug Lea's book and is available
from:

  http://www.cs.kent.ac.uk/projects/ofa/jcsp/

Although the page doesn't say so, L-GPL open source is available - just ask!
Must update the website, :(.  The release hasn't been updated for a while ...
but it will be.  There's a distributed JCSP Network Edition from Quickstone:

  http://www.quickstone.com/xcsp/jcspnetworkedition/

that is also going public - when I can get around to integrating it cleanly
with the core release.

For those who have not seen JCSP, this is a library of standard Java packages
giving access to the CSP/occam concurrency model, with a dash of pi-calculus
mobility (mobile channels, barriers and terminated-but-rerunnable-processes)
thrown in.  It integrates seamlessly with standard Java thread-and-locks
concurrency - you choose whatever mix suits your application, though you must
take care to conform to the occam parallel healthiness conditions (that the
Java compiler does not police!).

Again, I'm trying to refute Miles' assertion that:

>                                             ... the process algebra
> approach to concurrency is very different from the threads, locks and
> shared state approach that's hard-wired into Java and reflected in JSR
> 166.

:).

Miles added:
> FWIW, JSR 121, the Java Isolation API, has a CSP/pi-ish feel to it:
> communication is based on message passing rather than shared state,
> communication channels can be passed across communication channels for
> scope extrusion. Pete Soper's collected various things you might find
> interesting here,
>
>   http://www.bitser.net/isolate-interest/

and Peter Soper wrote:
>                                          ... and it reminded me of the
> potential of intersecting CSP and pi with JSR121 isolates. I finally
> located a copy of slides that include Miles Sabin's pi-related ones (see
> slide 31) that he presented to a UK university some time ago:
>
>   http://www.bitser.net/isolate-interest/slides20040623.pdf

Thanks for this!  With Isolates, I guess you were forced into a CSP/pi-like
channel mechanism, :).

Just a few notes on the above slides ("The Java Isolation API").  Slide 23:

  o CSP style programming
     o Always use Isolates instead of Threads
     o Practically suitable only for course-grained designs

The last sub-point is an artifact of the first sub-point.  The first point
is the whole point of Isolates - to give security from one "process" being
messed around by another (either through interference or failure).  This is
absolutely fair and necessary in the context of Java.  But if you can police
the necessary care yourself, JCSP (for example) allows CSP style programming
in Java with as fine-grained design as Threads allow.

occam-pi guarantees against erroneous (unsynchronised) process interference
through language design and rules enforced by the compiler - so no run-time
checks are needed, :).  Security against failure of another process is only
partial.  For the kind of applications for which Isolates are designed,
we would have to do a lot more work.

In a wider context, CSP/pi style programming can be extremely fine-grained.
We are working on a project attempting low-level modelling of nanite assemblies
(artificial blood platelets and blood clotting).  This uses all the dynamic
mobility mechanisms built into occam-pi (an extension of the classical occam
language supporting mobile channels, barriers, processes and much more).
We are aiming at models involving (initially) tens of millions of dynamically
constructed, mobile, location-aware, and self-assembling processes - each
process being pretty tiny!

occam-pi carries overheads of only 8 bytes per process, with around 50 ns
process construction time (using Brinch Hansen's parallel memory allocation
algorithm) and 50 ns channel communication overhead (using all the transputer
tricks) on modern Pentiums 4s ... assuming cache hits, that is, :).
URLs for the curious:

  http://www.cs.kent.ac.uk/projects/ofa/kroc/      (occam-pi home and download)
  http://frmb.org/occ21-extensions.html            (summary of pi-extensions)
  http://rmox.net/prelude/                         (research OS)

Other points: I really liked the pi-calc slides (31 and following).  Yes,
there is a nice, happy and useful relationship.  The Link mechanism is
a little different to both CSP and pi - being bound to both Isolates (one
at each end).  In CSP/pi (and in JCSP/occam-pi), channels are independent
entities usable by any process that lays its hands on them.  When you create
them, you just create them - processes can use them if they can see them and
can take it in turns, which is a bit more flexible.  Language (algebra) rules
prevent confusion.

Many apologies for going on too long.  Summary:

  (1) Formal specification of concurrency synchronisation mechanisms (including
      memory models) should be undertaken for all sorts of very practical
      reasons.  We should have moved away from natural language specs long ago.
 
  (2) Formal specification in CSP is usually pretty easy, if you have a
      reasonably tight informal specification ... and finds you out if you
      haven't.  CSP also allows access to the FDR2 model checker.  [Note:
      we have draft CSP specifications for pi-calc mobile channels and,
      soon, for (occam-pi) mobile processes.]
   
  (3) Both the CSP and pi-calculus process algebras address message passing
      via channels between non-shared-memory processes ... but they do much
      much more than that.  :)

Peter Welch.
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

RE: Re: CSP, the pi-calculus and CPA-2005

Boehm, Hans
In reply to this post by P.H.Welch
> A while back, we had to build a formal (CSP) model of the standard
Java monitor mechanisms
> (synchronized/wait/notify/notifyAll).  The trickiest part was making
as sure as possible
> that we had captured all the informally expressed semantics from the
original "specifications"
> - an impossible thing to prove, of course. Anyway, the CSP modelling
is quite short - slides 20-36 of:

>  http://www.cs.kent.ac.uk/projects/ofa/jcsp/csp-java-model.ppt

As far as I can tell, your CSP model of Java monitors ignores the memory
model
issues (JSR 133), as does most theoretical work that I've seen.  That
doesn't make it
useless by any means, but you have to be careful to remember what you're
modeling,
and what you're not.

If I understand correctly, a number of very common Java concurrency bugs
seem
to just quietly disappear in the CSP translation, e.g. double-checked
locking.
(This doesn't argue that we should all be writing the CSP version.  The
Java
memory model is there for a reason, namely to get reasonable
performance.)

Hans

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Re: CSP, the pi-calculus and CPA-2005

Miles Sabin
In reply to this post by P.H.Welch
P.H.Welch wrote,

> Thanks to Miles Sabin and Peter Soper for their replies.
>
> Miles wrote:
> > I think you'll find that many of the people on this list have an
> > interest in process algebras in one way or another. But I'm not
> > quite so surprised that they don't get discussed here ... the
> > process algebra approach to concurrency is very different from the
> > threads, locks and shared state approach that's hard-wired into
> > Java and reflected in JSR 166.
>
> No, there's a misunderstanding here about what process algebra
> offers.
>
> Regarding threads, locks and shared state there is plenty on offer -
> like formal characterisations that allow formal reasoning and
> automated model-checking.  In turn, this leads to precise design of
> the various high-level locking mechanisms you want, correct
> implementation, correct low-level code generation ... all the way
> down to correct and fast hardware support ... all the way up to
> correct applications.

No argument here ... if you look at the Java Memory Model documents
produced by JSR 133 you'll find exactly that. But this only takes us
from the machine level to a level somewhat below that addressed by JSR
166.

> CSP/pi mechanisms are extremely primitive, have a rich mathematics
> and can be formed into patterns that capture any synchronisation
> mechanism you fancy - some will be more useful than others, of
> course!  For instance, CSP "events" are the basis for channel
> communications (all sorts), barriers (multiway synchronisation) and
> pretty much anything.
<snip/>
> Again, the point is that it's easy to express this stuff formally and
> that we should do so.  Apart from anything else, it makes their
> implementation and applications using them amenable to automated model
> checking ... which can save months/years of debugging.

Understood. But this isn't much practical help to the people who are the
intended consumers of java.util.concurrent. From there up to the
application level things get much more complicated, hence much harder
to specify formally, particularly when you lack first-class language
support for your formalism or programming model of choice.

One of the most common problems here is that typical applications have
to deal not just with the intrinsic sources of concurrency supported by
a particular programming language, but also with concurrency due to
network interaction. This isn't particularly well integrated in Java
(you can't, for example, _directly_ wait on both a monitor and I/O), or
in any other mainstream programming language that I'm aware of (Erlang
comes close, but I'm not sure it could really be characterized as
mainstream).

Systematic handling of failure and cancellation are probably the next
two most common problems, and whilst they're non-negotiable for
production quality systems, they're rarely handled smoothly by
specification languages.

Speaking anecdotally, I've found the concurrent hierarchical state
machines model extremely helpful when designing network applications.
But the translation from a formal specification to running Java code is
an extremely delicate process, one which is most certainly not
correctness-proof-preserving.

In summary: I actually agree with almost all you say, I just don't think
that Java (but not just Java) provides an environment which supports
the direct application of these techniques other than as informal
guidelines.

> Miles added:
> > FWIW, JSR 121, the Java Isolation API, has a CSP/pi-ish feel to it:
> > communication is based on message passing rather than shared state,
> > communication channels can be passed across communication channels
> > for scope extrusion. Pete Soper's collected various things you
> > might find interesting here,

> Thanks for this!  With Isolates, I guess you were forced into a
> CSP/pi-like channel mechanism, :).
<snip/>

Indeed.

> Yes, there is a nice, happy and useful relationship.  The Link
> mechanism is a little different to both CSP and pi - being bound to
> both Isolates (one at each end).  In CSP/pi (and in JCSP/occam-pi),
> channels are independent entities usable by any process that lays its
> hands on them.  When you create them, you just create them -
> processes can use them if they can see them and can take it in turns,
> which is a bit more flexible.  Language (algebra) rules prevent
> confusion.

Yes, we were aware of this at the time. There are a variety of
implementation reasons which make unbound Links problematic. I hope a
revision of JSR 121 will support them one day, but for now I'd just
like to see a release of what we've done so far.

If you have any comments on the isolation API we'd be delighted to hear
them ... the best place would probably be the isolate-interest list ...
subscription details here,

  http://www.bitser.net/isolate-interest/

Cheers,


Miles
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Navigable{Map, Set} must not inherit from Sorted{Map, Set}

Remi Forax
The problem :
   I have a user defined implementation of a Set
   (FastTraversalSet) and this implementation
   already provides some traversal methods that
   i could use to retrofit the class
   in order to implement NavigableSet interface.
   But i think i can't do this without risking to break
   the semantic of my program.

   Because NavigableSet inherits from SortedSet
   (an interface that already exists in the JDK),
   if i retrofit my class some code in my program
   could have a different behavior :

   void doSomething(Set<String> set) {
     if (set instanceof SortedSet)
       // before retrofitting:
       //   it's a tree set, or a wrapper on a tree set
       //   like unmodifiableSet(...)
       // after retrofitting:
       //   oups FastTraversalSet match
     else
       // it's my implementation
   }

   The fact that NavigableSet inherits from SortedSet
   prevents me to retrofit FastTraversalSet.

   Please, Navigable{Set,Map} must not inherits
   from Sorted{Set,Map}.

Rémi Forax


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Navigable{Map, Set} must not inherit from Sorted{Map, Set}

Doug Lea
Rémi Forax wrote:

>
>    void doSomething(Set<String> set) {
>      if (set instanceof SortedSet)
>        // before retrofitting:
>        //   it's a tree set, or a wrapper on a tree set
>        //   like unmodifiableSet(...)
>        // after retrofitting:
>        //   oups FastTraversalSet match
>      else
>        // it's my implementation
>    }
>
>    The fact that NavigableSet inherits from SortedSet
>    prevents me to retrofit FastTraversalSet.
>
>    Please, Navigable{Set,Map} must not inherits
>    from Sorted{Set,Map}.
>

According to this, it seems that you do not want any interface to
ever inherit from Sorted{Set,Map}. So even if we changed Navigable
to not inherit Sorted, someone else will someday cause you the
same problem. Whenever you use instanceof in this way, you are
committing yourself to change your code in the future. (You never know
exactly when or why though -- if you did, you probably wouldn't have
used instanceof.)

Sorry to make your life more complicated, but we won't be changing this.

-Doug








_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Navigable{Map, Set} must not inherit from Sorted{Map, Set}

Remi Forax
Doug Lea a écrit :
 > Rémi Forax wrote:
 >
 >>
 >>    void doSomething(Set<String> set) {
 >>      if (set instanceof SortedSet)
 >>        // before retrofitting:
 >>        //   it's a tree set, or a wrapper on a tree set
 >>        //   like unmodifiableSet(...)
 >>        // after retrofitting:
 >>        //   oups FastTraversalSet match
 >>      else
 >>        // it's my implementation
 >>    }
 >>
 >>    The fact that NavigableSet inherits from SortedSet
 >>    prevents me to retrofit FastTraversalSet.
 >>
 >>    Please, Navigable{Set,Map} must not inherits
 >>    from Sorted{Set,Map}.
 >>
 >
 > According to this, it seems that you do not want any interface to
 > ever inherit from Sorted{Set,Map}.

No, anyone can write an interface that inherit from Sorted{Set,Map}
because i'm free to not use its library.
That not the case of the JDK.
If i want the next Java, i get the new JDK API bundle with it.

 > So even if we changed Navigable
 > to not inherit Sorted, someone else will someday cause you the
 > same problem.

I can choose to not use the library that do this.
I can't do the same with the JDK.

 > Whenever you use instanceof in this way, you are
 > committing yourself to change your code in the future. (You never know
 > exactly when or why though -- if you did, you probably wouldn't have
 > used instanceof.)

Yes your right its a "bad design", but i think i have no
way in Java to avoid such code.
Take by example java.util.Collections and count how many instanceof
you can find. I'm not the only one to use such design :)

 >
 > Sorry to make your life more complicated, but we won't be changing this.

i think it could make not only my life more complicated.

 >
 > -Doug
 >
 >

Rémi


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

RE: Navigable{Map, Set} must not inherit fromSorted{Map, Set}

David Holmes
In reply to this post by Doug Lea
> Rémi Forax wrote:
> >
> >    void doSomething(Set<String> set) {
> >      if (set instanceof SortedSet)
> >        // before retrofitting:
> >        //   it's a tree set, or a wrapper on a tree set
> >        //   like unmodifiableSet(...)
> >        // after retrofitting:
> >        //   oups FastTraversalSet match
> >      else
> >        // it's my implementation
> >    }

Is there some reason you can't invert the test and check for your
implementation first? That way you don't care what interfaces it implements.

David Holmes

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Navigable{Map, Set} must not inherit fromSorted{Map, Set}

Remi Forax
David Holmes wrote:

>>Rémi Forax wrote:
>>    
>>
>>>   void doSomething(Set<String> set) {
>>>     if (set instanceof SortedSet)
>>>       // before retrofitting:
>>>       //   it's a tree set, or a wrapper on a tree set
>>>       //   like unmodifiableSet(...)
>>>       // after retrofitting:
>>>       //   oups FastTraversalSet match
>>>     else
>>>       // it's my implementation
>>>   }
>>>      
>>>
>
>Is there some reason you can't invert the test and check for your
>implementation first? That way you don't care what interfaces it implements.
>
>David Holmes
>  
>
I can invert the test but this code was written two years ago and not by me.
It works so i prefer not to touch it if it's possible.
I  have to maintain the program and extends some specific parts.
It seems not a good idea to have to rewrite a code because i want to
retrofit a class.

The fact that NavigableSet inherits from SortedSet prevents me to
retrofit my class
without changing some other parts of the program.

Rémi Forax

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Navigable{Map, Set} must not inherit fromSorted{Map, Set}

tpeierls
Remi Forax wrote:
> I can invert the test but this code was written two years ago and not by me.
> It works so i prefer not to touch it if it's possible.
> I have to maintain the program and extends some specific parts.
> It seems not a good idea to have to rewrite a code because i want to
> retrofit a class.
>
> The fact that NavigableSet inherits from SortedSet prevents me to
> retrofit my class without changing some other parts of the program.

I'm encountering similar difficulties. I wrote some classes back before Collections came out that
have been working perfectly for years. I'd like to retrofit them to implement Collection
interfaces, but the interface hierarchy used by Collections is incompatible with algorithms I am
using. I could go back and modify my code, but it depends on some intricate instanceof tests that
I'm afraid are too delicate to mess with (and I'm not sure at this point exactly how they work),
so instead I'd like to ask if it would be possible to change the Collections interface hierarchy
so that Map implements Set.

I've done some initial work to verify that this could be accomplished in a way that would not
cause any problems for existing code. If anyone is interested I can describe the technique.

--tim


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

RE: Navigable{Map, Set} must not inherit fromSorted{Map, Set}

David Holmes
In reply to this post by Remi Forax
Remi,
> It works so i prefer not to touch it if it's possible.

But it won't work in Java 6 so you are going to have to do something
regardless and inverting the test is a simple fix.

> It seems not a good idea to have to rewrite a code because i want to
> retrofit a class.

If the retrofit is perfectly compatible with what you have then there would
be no need to rewrite things. But you are trying to retrofit something that
is incompatible with what you have. The simple solution is "don't do that".

The choice was made that a NavigableSet isA SortedSet. You have a situation
where you'd like the functionality of NavigableSet but your implementation
is not a SortedSet and doesn't want to be. Something has to give.

Cheers,
David Holmes

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

RE: Navigable{Map, Set} must not inherit fromSorted{Map, Set}

David Holmes
I wrote:
> But it won't work in Java 6 so you are going to have to do something
> regardless and inverting the test is a simple fix.

Sorry I lost the context a little. If you retrofit your code to implement
NavigableSet then the other code will break - otherwise the other code will
still work in Java 6.

The choice really comes down to how bad you want to implement NavigableSet.

For what it is worth that instanceof test should be written the other way
regardless - always look for the most specific type first, which in this
case is your implementation class.

David Holmes

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest