From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!mx02.eternal-september.org!feeder.eternal-september.org!aioe.org!.POSTED!not-for-mail From: "Dmitry A. Kazakov" Newsgroups: comp.lang.ada Subject: Re: Languages don't matter. A mathematical refutation Date: Thu, 9 Apr 2015 21:02:28 +0200 Organization: cbb software GmbH Message-ID: <1pjgcrsn42a55.b9xlyrybsns1$.dlg@40tude.net> References: <877fts7fvm.fsf@jester.gateway.sonic.net> <87twwv66pk.fsf@jester.gateway.sonic.net> <32ecaopodr1g.1xqh7ssdpa2ud.dlg@40tude.net> <87pp7j62ta.fsf@jester.gateway.sonic.net> <87pp7hb2xo.fsf@jester.gateway.sonic.net> <5rxvgyes5xg8.1mqq86gacbsb1.dlg@40tude.net> <87lhi5ayuv.fsf@jester.gateway.sonic.net> <87oan0aote.fsf@jester.gateway.sonic.net> <878ue3ff6y.fsf@jester.gateway.sonic.net> Reply-To: mailbox@dmitry-kazakov.de NNTP-Posting-Host: w2sqUGEBZqsVBYNL7Ky3Kg.user.speranza.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Complaints-To: abuse@aioe.org User-Agent: 40tude_Dialog/2.0.15.1 X-Notice: Filtered by postfilter v. 0.8.2 Xref: news.eternal-september.org comp.lang.ada:25497 Date: 2015-04-09T21:02:28+02:00 List-Id: 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