Doing it better 1999-02-08 ### You've got me thinking about my Diploma project again. You seem to have a slightly negative feeling about it, which is easily explicable, but I think it deserves more faith. It works, after all, and has no subroutines or stack. It is also designed for big programs. These are all things which we'd otherwise have to worry about all over again. As for putting too much functionality in the bottom layer (heap, channels): I didn't put the VM there, did I? Anyway. New ideas: ___ The problem with killing channels, and half of the problems with synchronising them, can be solved by killing a channel every time a message is sent down it. To expect a reply, you have to send a new channel as part of the message. To get this theoretically tidy arrangement and still retain efficient memory allocation, we should consider the memory-for-a-channel resource as an abstract datatype, which can be cast into a new channel very cheaply, and which arrives as part of the message it carries. (Plus point: you can use it to make a channel to a different place, which you couldn't do before.) ___ We have two components (channels and nodes) which are essentially different and both necessary (discuss: see later), and we also have the requirement for a place to put efficient VM code and the memory it needs. Previously I put the code and memory in the nodes, to make objects, and had very dumb channels. Could we put the code in the channels, to make filters, and have dumb routers at the nodes? Don't know. Another solution is to have dumb channels and dumb nodes and invent a third species which contains code and memory and is attached to precisely one channel. The third option has advantages, such as the ease of scheduling and killing a rogue process and the tractability of the synchronisation constraints at the nodes, and disadvantages, such as the need to include routing information and to spend time decoding it. Can you think of good primitive nodes (e.g. fork/meet and choose/join)? ___ It is easy to construct a typing scheme for data (the stuff which arrives down a channel). Such a scheme would be a formal, checkable specification both of the correctness of protocols and of their security (using tokens, for example). I wish to propose a scheme in three stages: first a simple but useless scheme which doesn't allow channels to be sent in messages, then a recursive and useful one which does, then a parameterised one. The simple scheme defines a type to be a base type (such as signed 32-bit integer, or string, or member of enumeration) or a product type (such as an A and another A and a B, where A and B are simpler types) or a sum type (such as an A or a B, where A and B are simpler types). So far so familiar. We also include a parallel type (an A and a B in separate messages in no particular order, where A and B are simpler types), which is not so familiar. Note that all of these constructors are associative and polyadic, but that product types are not commutative. We also insist that every type include the error type, which could be content-less or could be a string or could be a list of strings (a trace) or many other things, and which we can design later. The recursive scheme augments the simple scheme with a (monadic) channel constructor, which differs from the others in that it can be applied recursively. (For example, we can define an A to be an A-channel or an error, but we can't define an A to be an A or an error. This distinction is sensible because a bound on the memory occupied by a type is much more useful than a bound on the number of messages in a protocol.) If you receive an A-channel in a message, then you can send an A down it in another message. You can implement parallel types using channels (A and B in parallel becomes an (A-channel and B-channel or error)-channel), but it is probably worth having the primitive for efficiency. The parameterised scheme allows you recursively to define new type constructors, which can't be recursive. For example, you could define an A-stream to be an A and an (A-stream-channel or error)-channel or an error. This then lets you define int-streams, string-streams and error-streams, but you can't define an A to be an A-stream. This example illustrates that the constructors can be defined recursively (via a channel), but not used recursively. Constructors defined in this way add no power to the type-scheme (they are just a notational convenience), whereas defining new recursive constructors would allow the definition of types which included infinite messages. This type scheme is a subset of that offered by ML. ML does provide the more complicated recursive constructors, and type-checking is decideable, statically, in ML. Our type scheme is more restrictive on individual messages (it permits only finite messages without pointers), but just as powerful for protocols (it permits infinite branching sequences of finite messages). It is also decideable statically. There are horrible cases when type-checking takes unbounded time, but even if we don't want to punish programmers by making them wait we can always revert to run-time checking of individual messages, or to a scheme which accepts any channel nested more than 10 messages deep in the protocol (with a warning). A really nice feature is that all of the normal rules for type-checking inheritance-based object-oriented programs drop out of the above scheme. An object must accept a more general protocol than the one actually used (it must be a super-type of that expected by the caller) and return channels with a simpler protocol (the return types must be sub-types of those expected by the caller). ___ The type-checking scheme overlaps with the "memory is an abstract datatype" idea. When you allocate memory for a particular type of channel, how much memory should you provide? (Aside: the object which allocates the memory is the one which expects to receive the message - think about it!) The short answer is 'enough for the first message', under which scheme the memory would be freed on receipt, and reallocated for any reply. The unworkable answer is 'enough for all of the messages which could exist at the same time in the worst case', under which scheme the following type would require an infinite message buffer: an A is an A-channel and an A-channel or an error. A compromise scheme is to allocate enough memory for a reply down one of the channels in the message, in the worst case. I suggest we pass this problem on to the programmer. That way 1) the programmer will be aware of the efficiency issues, and 2) we can always solve the problem later with a higher-level language. Explicitly, there should be a monadic constructor called memory-for, as in memory-for-A, which is allowed to be used recursively, as in the following which defines the infinite empty protocol: A is an A-channel and memory-for-A or an error. Under this scheme, the memory required for a message is the maximum of the memory for the message itself (counting one pointer for any memory-for terms) and the sum of the requirements for A in any memory-for-A terms. We also have to consider the possibility that heap blocks require a header, for example for a GC flag and/or a reference count, in which case memory-for-A would be sent as a pointer and an offset. ___ I included a cryptic "discuss" above. The discussion is on the question of whether an object should support an infinite number of channels (as in my Diploma project) or a pre-declared finite number. In the latter case, a channel would consume no resources that could not be made part of the two objects it connects, and this would be a good argument not to put the processing elements in the channels. In the former case, we need to do per-channel memory allocation, so the argument doesn't apply. The former case is nice because it makes it much easier and more efficient to write daemons. A daemon would respond in the same way to messages received down any of its channels, and it is quite sufficient for it to know about just one of them at a time. The latter case is nice because it makes exhaustive analysis of the synchronisation constraints possible, and because (if we go for that option) it is easier to design a set of primitive router nodes with finite arity than with infinite arity. ___ I think that covers it. Alistair