Doing it better 1999-06-10 b
###

I've just been browsing my collection of Tau-related e-mails...

You started a project in February. Is it the same one that you showed me
running in May?

I appear to have changed my emphasis markedly over the last six months. I
think I should reassure you that the overall plan stands, but I'm
approaching it in a depth-first kind of way, concentrating on the details
of a particular aspect first.

I want to suggest a memory allocation scheme which would solve our
argument about where the heap manager goes. Of course, your argument about
using malloc and not counting it because it is shared is entirely valid,
but I thought you'd like to see another approach. Divide memory into
32-byte pages (or 64-byte?), and make no guarantees about adjacency when
more than one page is allocated. This has the considerable advantage that
a page of memory can be allocated and freed in about 5 cycles, but the
disadvantage that indexing a long array requires a tree walk. I don't
really mind the tree walk, because it's bound to cause a cache-miss
anyway. This is a problem with large arrays, not a failure of the memory
allocation scheme. Other advantages are that pages coincide with cache
lines, and that you can always recover a pointer to a page from a pointer
to somewhere inside that page, simply by clearing a few bits.

I've also reached a provisional solution to my protocol type problems. The
problem was that I was trying to make all type casts free. This is not
possible. Instead, there are two kinds of casts: those that are free and
those that require some resources (time/memory).

You can cast A to A+B for free, but not B to A+B. In terms of inheritance,
this says that a subtype has just one ancestor, just like Java. In terms
of implementation, a typecase statement compiles to a branch table, and if
the tested value happens to be of a smaller type then only the first
entries in the table will ever be used. Similarly, you can cast from ch
x.A+B to ch x.A.

Casting from B to A+B, or from B+A to A+B, requires resources. In terms of
inheritance, multiple inheritance is possible but not free. In terms of
implementation, this cast involves inserting an extra level of
indirection, say a look-up table to change the tag of the sum. Casting ch
x.A+B to ch x.A is similar, but here the indirection is provided by
indirecting through a second branch table, or something. Note that the
message may itself have to be cast in transit.


Similarly, casting from (A+B)*C to (A*C)+(B*C) is free, but casting from
A*(B+C) to (A*B)+(A*C) isn't. This is because the sum tag is stored to the
left of the summand.

Accounting for these resources is still a problem. In the case when you
perform a lookup on the tag, the person who performs the cast is clearly
the one who consumes resources. In the case where you insert an extra
branch table, the resources are only used when the message is sent,
possibly much later and by a different object.

I think the solution may be to associate with every channel its resource
requirements. Then, for example, you could cast ch(100)x.A+B to
ch(101)x.B+A, indicating that the channel has just become more expensive
to use. The type checker would then ensure that the object which sends the
message is aware of the extra expense. Of course, the cast from ch(100)x.A
to ch(101)x.A is free - you can always tell people things are more
expensive than they are.

I intend to make free casts automatic and metered casts explicit in the
high-level language. Two more areas to clear up - metered casts of 1)
recursive pointer structures, and 2) restriction types. Ample opportunity
for catastrophe!

A word on Java. The Acorn Java 1.2 port is too unstable and incomplete for
work on Tau. It doesn't even draw bitmaps where the documentation says it
should (one pixel too low). I'm therefore going to stick to ARM code for
the moment. This will encourage me to keep the ARM code part small, and to
get a useful portable language running soon. ARM code into C is easy, if
necessary.

I see functional Forth as CoVirt without channels. It's a prototype with
potentially divergent 'further work' possibilities.

Alistair