Re: Languages don't matter. A mathematical refutation

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

On Thu, 09 Apr 2015 21:40:06 +0300, Niklas Holsti wrote:

> On 15-04-09 17:35 , Dmitry A. Kazakov wrote:
>> On Thu, 09 Apr 2015 15:14:59 +0200, G.B. wrote:
>>
>>> Now, WRT storage management, assume a bounded container.
>>> The implementation may pre-allocate the maximum number of
>>> objects.(*) Given that, why should it not be possible at all,
>>> in no case, to guarantee a known complexity of storage
>>> management? A bounded vector, say, could specify its
>>> storage management needs, on condition that ... Much like
>>> a hash table package would state that
>>>
>>>     "As long as the number of slots is as least N/M,
>>>      finding an object will take no more than f(M, N, g(Hash))."
>>
>> Which is elementary incomputable, as it contains the future tense and thus
>> cannot be a part of any contract.
> 
> It is quite possible to extend the semantics of a programming language 
> with a predefined global (or task-specific) variable "elapsed execution 
> time", and the above contract can be stated as a constraint on the 
> difference between the pre- and post-values of this variable.

I had impression that Georg wished to compare the complexity [of free block
search?] after cleaning the garbage with the complexity without cleaning.
No time measurements can help that, obviously. And "will take" is not
"took". Furthermore, it is not a proper contract anyway, as it cannot be
verified *before* a program run. The [proper] contract must apply to all
possible runs (all program states).

> In fact, Ada.Execution_Time provides such variables. The Time_Remaining 
> function could be used to express the above constraint.
> 
>>> Like everything that actually handles program data, GC does
>>> influence the program's behavior, e.g. by taking time.
>>
>> That is not the program behavior. The behavior is only things related to
>> the program logic = functional things.
> 
> This is niggling about words, but for real-time systems the execution 
> time of computations is certainly an important property of the program, 
> whether it is called "behaviour" or not.

It is a constraint.

My point was that it is a lesser problem, IMO, when GC violates constraints
such as time and space constraints in an unpredictable manner. The bigger
problem is that it may violate [proper] behavior because of issues with
finalization and references order (weak, strong, the things Randy said
about designing memory management).

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