Re: Little people supporting Ada, possibly through AdaCore?

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Thu, 19 Jul 2012 05:42:19 -0700 (PDT), Maciej Sobczak wrote:

> W dniu czwartek, 19 lipca 2012 10:23:41 UTC+2 u�ytkownik Dmitry A. Kazakov napisa�:
> 
>> >> True. However a set of truly unordered elements cannot be implemented
>> >> otherwise than on top of an ordered set.
>> > 
>> > Why?
>> 
>> I guess it is related to computability.
> 
> Why? I see no relation. Or, to put it in more concrete terms - I don't
> care about implementation details; the purpose of abstraction is to be
> independent from them.

Yes, but that was not the point, which was that the underlying
implementation would need some ordered set and thus an ad-hoc order induced
by that.

The actual question was how to shape the interface of an unordered set so
that the clients could not exploit hidden order(s). As an example, maybe
not very good one, but anyway, consider sets of characters from ASCII,
EBCDIC. Let we wanted to prevent users to rely on ASCII'Succ ('I') = 'J',
because that might be untrue for EBCDIC. For example, should it be possible
to iterate elements in the set:

   for I in S'Range loop
       E := S (I);
   end loop;

or only this way:

   for E in S loop
       ... -- Unspecified order
   end loop;

or maybe there should be operations creating ordered snapshots of the
unordered original?

I think that unordered interfaces could be potentially useful for parallel
computing and very large [mutable/remote] sets, which could not be
iterated.

>> > Membership test does not require any order.
>> 
>> You need to enumerate elements to be able to compute it.
> 
> No, you don't need to enumerate. If I remember correctly, the Pascal
> language provides sets as a language-level entity and membership test is
> commonly implemented as logical, bitwise operation. Now, you can argue
> that bitsets rely on some assumed ordering of implicitly assigned position
> numbers or whatever, but wait until I finish my hardware-based
> implementation of logical operations on bit-cubes. No ordering is
> required, it is just an artifact of our current, very limited hardware.

As I said, it is related to computability. You could have an "oracle"
telling if X is in S. "oracle" = incomputable by other means (i.e. by FSA).
But when computable, then ordered.

>> In that case you would need to
>> identify elements in the set in order to compare them with the testee. That
>> again would require some order.
> 
> No. Just wait until I finish my organic neural network, where sets are
> just implemented as multiple neurons connected to the owner, all triggered
> with the same signal. The membership test is O(1) and has nothing to do
> with enumeration (and therefore nothing to do with ordering).

You could simply say that the membership relation is implemented by an
incidence matrix, which is an equivalent to neurons wiring. But rows and
columns of the matrix are enumerated, that gives you an order.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de