[bitc-dev] The problem with linked lists
cap at isg.axmor.com
Thu Mar 10 11:08:00 EST 2005
This is reenforces the question that bugs me for some time. Is BitC too
high-level for OS development?
BitC is C-incomplete. I.e. not every valid C program without assembly
snippets can be rewritten as BitC program. And think that the statement
"Like C [1
provides full control over data structure representation, which is
necessary for high-performance systems programming" should be removed
from the specification unless BitC changes. It does not sound true for
me right now.
I originally expected it to be of level of C++, C, or Ada. However it is
more close to C#, Java or ML now. At least with respect to memory
managment. There are implicit memory allocation primitives, but no
memory deallocation primitives. Spec never says "garbage collector"
however it looks like it is assumed in some form.
I think that there is a choice for memory safety. It can be enforced or
it can be proved. As I undertand, BitC has originally chosen path of
enfocement. Maybe it is a good point to think about proving branch.
BTW while we are on unions I would also like to point that one of
addition in Ada2005 is unchecked union type
they have discovered that it is really hard to interface to other
language(s) without them. Possibly BitC will face the same problem later.
Jonathan S. Shapiro wrote:
>The union safety problem is especially disturbing for a different
>reason: it precludes linked lists (and similar structures) that are
>threaded through their respective objects.
>Consider a mutable union containing a doubly linked list element. The
>union can be mutated as a whole. If the type tag of the union changes
>this can create a safety problem because neighboring link elements no
>longer point to a link element.
>However, there is a higher-level problem here. Imagine that we re-assign
>the union to a new value having the same tag. Note that all of the
>linked list pointers are now validly typed, but they aren't in a linked
>list here. There is no type violation, but there is an invariant
>This raises two problems:
>1. Can we avoid the need for such constructs? I'm not sure.
>2. If not, do we now need to introduce a notion of construction,
>destruction, and overloading of assignment? I would like to avoid this.
>We are going to proceed by pushing hard on (1) to see what happens. We
>currently see exactly one critical data structure in Coyotos for which
>this presents a problem, and there is an alternative implementation.
>bitc-dev mailing list
>bitc-dev at coyotos.org
More information about the bitc-dev