[bitc-dev] The problem with linked lists

[Constantine Plotnikov]

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 
<http://www.coyotos.org/docs/bitc-spec/bitc-spec.html#ansi1999c>], BitC 
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.

Constantine

BTW while we are on unions I would also like to point that one of 
addition in Ada2005 is unchecked union type 
(http://en.wikibooks.org/wiki/Programming:Ada:Types:record#Union). AFAIR 
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
>violation.
>
>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.
>
>shap
>
>_______________________________________________
>bitc-dev mailing list
>bitc-dev at coyotos.org
>http://www.coyotos.org/mailman/listinfo/bitc-dev
>  
>