Re: How to get Ada to ?cross the chasm??

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

On 18-05-06 20:40 , Dmitry A. Kazakov wrote:
> On 2018-05-06 17:32, Niklas Holsti wrote:
>> On 18-05-06 12:53 , Dmitry A. Kazakov wrote:
>>> On 2018-05-06 10:34, Niklas Holsti wrote:
>>    ...
>>>> Moving the focus back to Ada, efficient applicative data structures
>>>> are interesting for real-time systems because they could reduce
>>>> locking/blocking times: a "reader task" could quickly grab a (logical)
>>>> immutable copy of a large data structure and read the data at its own
>>>> speed, without interfering with "writer" tasks that transform their
>>>> own (logical) copies of the data structure.
>>>
>>> You need to merge incoherent copies at some point later.
>>
>> In my applications, that would not be a big problem. In many cases the
>> writers can be serialized, in other cases writers update separate
>> parts of the data structure and merging would be easy. Other
>> applications could have more problems, but applicative data structures
>> do tend to provide high-level, merge-like operations.
>
> Maybe it is not a structure, but a set of assorted buckets of data?

Both cases occur in satellite SW. An example of the former case 
(structure) is various forms of configuration data (some people may know 
the acronym "PUS") that guide the real-time processing but are also 
subject to changes from ground commands. An example of the latter case 
(buckets) is the so-called "data pool" that stores data acquired from 
various SW and HW sources, with various sampling periods, and is 
periodically monitored and reported (telemetered) and sporadically used 
for computations and control decisions.

> Whatever it is under real-time constraint you need to have each
> update visible within some bounded time interval.

Visibility is not often a problem; stability is. A reader task must 
usually be provided with data that are stable and coherent for the 
duration of the reader task job, even if higher-priority, 
higher-frequency writer tasks need to update the data concurrently.

>>> I have an intuitive feeling that in general lock-free approach does
>>> not work at large scale and is effective only at the low level and
>>> tight times.
>>
>> If the data structure is applicative, it does not have to be
>> lock-free. The applicative property should make lock holding durations
>> very short because the structure looks immutable to pure readers.
>
> "Applicative" is not a substantial property that hints any concrete
> implementation of publisher/subscribers bound through the data
> structure. If Ada should do anything, then provide much better support
> for user ADTs than it has now.

An applicative data structure is a data structure that can be mutated 
only by constructing what seems to be a modified copy of the entire 
original data structure, but without actually copying most of the data, 
and leaving the original data structure available unmodified.

In other words, a mutated version of the structure can be constructed 
only by applying a function to the original version, with the function 
returning the mutated version without harm to the original version.

Such data structures tend to be based on "structure sharing" through 
internal pointers that are not visible to the clients. In functional 
languages with garbage collection these pointers are managed 
automatically. In present Ada, the implementor of an applicative data 
structure must manage the structure-sharing pointers explicitly, perhaps 
with the help of controlled types.

I don't know how to extend Ada to make applicative data structures 
easier to implement in Ada.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .