Re: Ada GC

Henry Baker <hbaker@netcom.com> wrote:
>It's no harder to formally specify what it means to 'have GC' than it
>is to specify what it means to be 'real-time'. ...


Kevin Weise <kweise@pluto.colsa.com> wrote:
>I admit I haven't read the specifications and definitions of all new
>languages for the past twenty years. But I have *never* seen a language
>specification that did this, except for certain assemblers that told you
>how many machine cycles each instruction required to execute...


rfg@monkeys.com (Ronald F. Guilmette) writes:
>Check the C++ language standard... library section.


>(Certainly of the STL library operations have time complexity requirements
>in the draft standard.)


Actually that struck me as a mistake. Fortunately from what I saw,
they were only asymptotic complexity specifications. Presumably an
actual implementation would supply the constants. Even then, this is
too ill-defined to be a binding part of the language standard. It is
a useful guideline for high quality implementations.


If this indeed becomes part of the official standard, it would be nice
to answer questions such as:


Is an implementation that uses virtual memory conforming? Would this
answer change if the page replacement algorithm were not constant
time? (It might not be because some of the kernel data structure
updates might depend on the size of the address space. Of course this
is in the noise compared to the disk access.)


Assuming a VM based implementation can be conforming, then it must be
the case that very large constants (e.g. 10**5 times the meory access
time) are allowed for retrieving the next element from a list, for
example. Thus I should also be allowed to spuriously traverse all of
memory on a 16 bit machine as part of this operation, since that takes
less than 10**5 memory accesses. How about on a machine with 32 bit
addresses? 64 bit addresses? 2**64 is still a constant.


(I admit to only having read tiny pieces of the draft standard. If it
contains a clarification of these issues, I'd appreciate a pointer.)


Hans-J. Boehm
(boehm@parc.xerox.com)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.