Changeset 0720e049 for doc/proposals

Timestamp:

Aug 11, 2017, 10:33:37 AM (8 years ago)

Author:

Rob Schluntz <rschlunt@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc

Children:

54cd58b0

Parents:

3d4b23fa (diff), 59a75cb (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:/u/cforall/software/cfa/cfa-cc

Location:

doc/proposals

Files:

• concurrency/text/concurrency.tex (modified) (17 diffs)
• concurrency/version (modified) (1 diff)
• tagged-struct.txt (deleted)
• virtual.txt (modified) (4 diffs)

doc/proposals/concurrency/text/concurrency.tex

@@ -4 +4 @@
 % ======================================================================
 % ======================================================================
-Several tool can be used to solve concurrency challenges. Since many of these challenges appear with the use of mutable shared-state, some languages and libraries simply disallow mutable shared-state (Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, Akka (Scala)~\cite{Akka}). In these paradigms, interaction among concurrent objects relies on message passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms that closely relate to networking concepts (channels\cit for example). However, in languages that use routine calls as their core abstraction-mechanism, these approaches force a clear distinction between concurrent and non-concurrent paradigms (i.e., message passing versus routine call). This distinction in turn means that, in order to be effective, programmers need to learn two sets of designs patterns. While this distinction can be hidden away in library code, effective use of the librairy still has to take both paradigms into account. 
-
-Approaches based on shared memory are more closely related to non-concurrent paradigms since they often rely on basic constructs like routine calls and shared objects. At the lowest level, concurrent paradigms are implemented as atomic operations and locks. Many such mechanisms have been proposed, including semaphores~\cite{Dijkstra68b} and path expressions~\cite{Campbell74}. However, for productivity reasons it is desireable to have a higher-level construct be the core concurrency paradigm~\cite{HPP:Study}. 
-
-An approach that is worth mentionning because it is gaining in popularity is transactionnal memory~\cite{Dice10}[Check citation]. While this approach is even pursued by system languages like \CC\cit, the performance and feature set is currently too restrictive to be the main concurrency paradigm for general purpose language, which is why it was rejected as the core paradigm for concurrency in \CFA. 
+Several tool can be used to solve concurrency challenges. Since many of these challenges appear with the use of mutable shared-state, some languages and libraries simply disallow mutable shared-state (Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, Akka (Scala)~\cite{Akka}). In these paradigms, interaction among concurrent objects relies on message passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms that closely relate to networking concepts (channels\cit for example). However, in languages that use routine calls as their core abstraction-mechanism, these approaches force a clear distinction between concurrent and non-concurrent paradigms (i.e., message passing versus routine call). This distinction in turn means that, in order to be effective, programmers need to learn two sets of designs patterns. While this distinction can be hidden away in library code, effective use of the librairy still has to take both paradigms into account.
+
+Approaches based on shared memory are more closely related to non-concurrent paradigms since they often rely on basic constructs like routine calls and shared objects. At the lowest level, concurrent paradigms are implemented as atomic operations and locks. Many such mechanisms have been proposed, including semaphores~\cite{Dijkstra68b} and path expressions~\cite{Campbell74}. However, for productivity reasons it is desireable to have a higher-level construct be the core concurrency paradigm~\cite{HPP:Study}.
+
+An approach that is worth mentionning because it is gaining in popularity is transactionnal memory~\cite{Dice10}[Check citation]. While this approach is even pursued by system languages like \CC\cit, the performance and feature set is currently too restrictive to be the main concurrency paradigm for general purpose language, which is why it was rejected as the core paradigm for concurrency in \CFA.
 
 One of the most natural, elegant, and efficient mechanisms for synchronization and communication, especially for shared memory systems, is the \emph{monitor}. Monitors were first proposed by Brinch Hansen~\cite{Hansen73} and later described and extended by C.A.R.~Hoare~\cite{Hoare74}. Many programming languages---e.g., Concurrent Pascal~\cite{ConcurrentPascal}, Mesa~\cite{Mesa}, Modula~\cite{Modula-2}, Turing~\cite{Turing:old}, Modula-3~\cite{Modula-3}, NeWS~\cite{NeWS}, Emerald~\cite{Emerald}, \uC~\cite{Buhr92a} and Java~\cite{Java}---provide monitors as explicit language constructs. In addition, operating-system kernels and device drivers have a monitor-like structure, although they often use lower-level primitives such as semaphores or locks to simulate monitors. For these reasons, this project proposes monitors as the core concurrency-construct.
@@ -101 +101 @@
         }
 \end{cfacode}
-The multi-acquisition monitor lock allows a monitor lock to be acquired by both \code{bar} or \code{baz} and acquired again in \code{foo}. In the calls to \code{bar} and \code{baz} the monitors are acquired in opposite order. 
+The multi-acquisition monitor lock allows a monitor lock to be acquired by both \code{bar} or \code{baz} and acquired again in \code{foo}. In the calls to \code{bar} and \code{baz} the monitors are acquired in opposite order.
 
 However, such use leads the lock acquiring order problem. In the example above, the user uses implicit ordering in the case of function \code{foo} but explicit ordering in the case of \code{bar} and \code{baz}. This subtle mistake means that calling these routines concurrently may lead to deadlock and is therefore undefined behavior. As shown on several occasion\cit, solving this problem requires:
@@ -169 +169 @@
 \end{tabular}
 \end{center}
-Notice how the counter is used without any explicit synchronisation and yet supports thread-safe semantics for both reading and writting. 
+Notice how the counter is used without any explicit synchronisation and yet supports thread-safe semantics for both reading and writting.
 
 % ======================================================================
@@ -178 +178 @@
 Depending on the choice of semantics for when monitor locks are acquired, interaction between monitors and \CFA's concept of polymorphism can be complex to support. However, it is shown that entry-point locking solves most of the issues.
 
-First of all, interaction between \code{otype} polymorphism and monitors is impossible since monitors do not support copying. Therefore, the main question is how to support \code{dtype} polymorphism. Since a monitor's main purpose is to ensure mutual exclusion when accessing shared data, this implies that mutual exclusion is only required for routines that do in fact access shared data. However, since \code{dtype} polymorphism always handles incomplete types (by definition), no \code{dtype} polymorphic routine can access shared data since the data requires knowledge about the type. Therefore, the only concern when combining \code{dtype} polymorphism and monitors is to protect access to routines. 
-
-Before looking into complex control flow, it is important to present the difference between the two acquiring options : \gls{callsite-locking} and \gls{entry-point-locking}, i.e. acquiring the monitors before making a mutex routine call or as the first instruction of the mutex routine call. For example:
+First of all, interaction between \code{otype} polymorphism and monitors is impossible since monitors do not support copying. Therefore, the main question is how to support \code{dtype} polymorphism. Since a monitor's main purpose is to ensure mutual exclusion when accessing shared data, this implies that mutual exclusion is only required for routines that do in fact access shared data. However, since \code{dtype} polymorphism always handles incomplete types (by definition), no \code{dtype} polymorphic routine can access shared data since the data requires knowledge about the type. Therefore, the only concern when combining \code{dtype} polymorphism and monitors is to protect access to routines.
+
+Before looking into complex control-flow, it is important to present the difference between the two acquiring options : callsite and entry-point locking, i.e. acquiring the monitors before making a mutex routine call or as the first operation of the mutex routine-call. For example:
 \begin{center}
 \setlength\tabcolsep{1.5pt}
@@ -245 +245 @@
 \end{center}
 
-\Gls{callsite-locking} is inefficient, since any \code{dtype} routine may have to obtain some lock before calling a routine, depending on whether or not the type passed is a monitor. However, with \gls{entry-point-locking} calling a monitor routine becomes exactly the same as calling it from anywhere else. Note that the \code{mutex} keyword relies on the resolver rather than another form of language, which mean that in cases where a generic monitor routine is actually desired, writing a mutex routine is possible with the proper trait. This is possible because monitors are designed in terms a trait. For example:
+\Gls{callsite-locking} is inefficient, since any \code{dtype} routine may have to obtain some lock before calling a routine, depending on whether or not the type passed is a monitor. However, with \gls{entry-point-locking} calling a monitor routine becomes exactly the same as calling it from anywhere else.
+
+Note the \code{mutex} keyword relies on the resolver, which means that in cases where a generic monitor routine is actually desired, writing a mutex routine is possible with the proper trait. This is possible because monitors are designed in terms a trait. For example:
 \begin{cfacode}
 //Incorrect
 //T is not a monitor
 forall(dtype T)
-void foo(T * mutex t); 
+void foo(T * mutex t);
 
 //Correct
-//this function only works on monitors 
+//this function only works on monitors
 //(any monitor)
 forall(dtype T | is_monitor(T))
-void bar(T * mutex t)); 
+void bar(T * mutex t));
 \end{cfacode}
 
@@ -267 +269 @@
 In addition to mutual exclusion, the monitors at the core of \CFA's concurrency can also be used to achieve synchronisation. With monitors, this is generally achieved with internal or external scheduling as in\cit. Since internal scheduling of single monitors is mostly a solved problem, this proposal concentraits on extending internal scheduling to multiple monitors at once. Indeed, like the \gls{group-acquire} semantics, internal scheduling extends to multiple monitors at once in a way that is natural to the user but requires additional complexity on the implementation side.
 
-First, Here is a simple example of such a technique:
+First, here is a simple example of such a technique:
 
 \begin{cfacode}
@@ -289 +291 @@
 \end{cfacode}
 
-There are two details to note here. First, there \code{signal} is a delayed operation, it only unblocks the waiting thread when it reaches the end of the critical section. This is needed to respect mutual-exclusion. Second, in \CFA, \code{condition} have no particular need to be stored inside a monitor, beyond any software engineering reasons. Here routine \code{foo} waits for the \code{signal} from \code{bar} before making further progress, effectively ensuring a basic ordering. 
+There are two details to note here. First, there \code{signal} is a delayed operation, it only unblocks the waiting thread when it reaches the end of the critical section. This is needed to respect mutual-exclusion. Second, in \CFA, \code{condition} have no particular need to be stored inside a monitor, beyond any software engineering reasons. Here routine \code{foo} waits for the \code{signal} from \code{bar} before making further progress, effectively ensuring a basic ordering.
 
 An important aspect to take into account here is that \CFA does not allow barging, which means that once function \code{bar} releases the monitor, foo is guaranteed to resume immediately after (unless some other thread waited on the same condition). This guarantees offers the benefit of not having to loop arount waits in order to guarantee that a condition is still met. The main reason \CFA offers this guarantee is that users can easily introduce barging if it becomes a necessity but adding barging prevention or barging avoidance is more involved without language support. Supporting barging prevention as well as extending internal scheduling to multiple monitors is the main source of complexity in the design of \CFA concurrency.
@@ -317 +319 @@
 \end{pseudo}
 \end{multicols}
-
-The previous example shows the simple case of having two threads (one for each column) and a single monitor A. One thread acquires before waiting (atomically blocking and releasing A) and the other acquires before signalling. There is an important thing to note here, both \code{wait} and \code{signal} must be called with the proper monitor(s) already acquired. This restriction is hidden on the user side in \uC, as it is a logical requirement for barging prevention. 
+The example shows the simple case of having two threads (one for each column) and a single monitor A. One thread acquires before waiting (atomically blocking and releasing A) and the other acquires before signalling. There is an important thing to note here, both \code{wait} and \code{signal} must be called with the proper monitor(s) already acquired. This restriction is hidden on the user side in \uC, as it is a logical requirement for barging prevention.
 
 A direct extension of the previous example is the \gls{group-acquire} version:
@@ -337 +338 @@
 \end{pseudo}
 \end{multicols}
-
 This version uses \gls{group-acquire} (denoted using the \& symbol), but the presence of multiple monitors does not add a particularly new meaning. Synchronization happens between the two threads in exactly the same way and order. The only difference is that mutual exclusion covers more monitors. On the implementation side, handling multiple monitors does add a degree of complexity as the next few examples demonstrate.
 
@@ -397 +397 @@
 \end{center}
 
-It is particularly important to pay attention to code sections 8 and 3, which are where the existing semantics of internal scheduling need to be extended for multiple monitors. The root of the problem is that \gls{group-acquire} is used in a context where one of the monitors is already acquired and is why it is important to define the behaviour of the previous pseudo-code. When the signaller thread reaches the location where it should "release A \& B" (line 17), it must actually transfer ownership of monitor B to the waiting thread. This ownership trasnfer is required in order to prevent barging. Since the signalling thread still needs the monitor A, simply waking up the waiting thread is not an option because it would violate mutual exclusion. We are therefore left with three options:
+It is particularly important to pay attention to code sections 8 and 3, which are where the existing semantics of internal scheduling need to be extended for multiple monitors. The root of the problem is that \gls{group-acquire} is used in a context where one of the monitors is already acquired and is why it is important to define the behaviour of the previous pseudo-code. When the signaller thread reaches the location where it should "release A \& B" (line 16), it must actually transfer ownership of monitor B to the waiting thread. This ownership trasnfer is required in order to prevent barging. Since the signalling thread still needs the monitor A, simply waking up the waiting thread is not an option because it would violate mutual exclusion. There are three options:
 
 \subsubsection{Delaying signals}
-The first more obvious solution to solve the problem of multi-monitor scheduling is to keep ownership of all locks until the last lock is ready to be transferred. It can be argued that that moment is the correct time to transfer ownership when the last lock is no longer needed is what fits most closely to the behaviour of single monitor scheduling. This solution has the main benefit of transferring ownership of groups of monitors, which simplifies the semantics from mutiple objects to a single groupd of object. Effectively making the existing single monitor semantic viable by simply changing monitors to monitor collections.
+The first more obvious solution to solve the problem of multi-monitor scheduling is to keep ownership of all locks until the last lock is ready to be transferred. It can be argued that that moment is the correct time to transfer ownership when the last lock is no longer needed because this semantics fits most closely to the behaviour of single monitor scheduling. This solution has the main benefit of transferring ownership of groups of monitors, which simplifies the semantics from mutiple objects to a single group of object, effectively making the existing single monitor semantic viable by simply changing monitors to monitor collections.
 \begin{multicols}{2}
 Waiter
@@ -424 +424 @@
 \end{pseudo}
 \end{multicols}
-However, this solution can become much more complicated depending on what is executed while secretly holding B. Indeed, nothing prevents a user from signalling monitor A on a different condition variable:
+However, this solution can become much more complicated depending on what is executed while secretly holding B (at line 10). Indeed, nothing prevents a user from signalling monitor A on a different condition variable:
 \newpage
 \begin{multicols}{2}
@@ -459 +459 @@
 \end{multicols}
 
-The goal in this solution is to avoid the need to transfer ownership of a subset of the condition monitors. However, this goal is unreacheable in the previous example. Depending on the order of signals (line 12 and 15) two cases can happen. Note that ordering is not determined by a race condition but by whether signalled threads are enqueued in FIFO or FILO order. However, regardless of the answer, users can move line 15 before line 11 and get the reverse effect.
-
-\paragraph{Case 1: thread 1 will go first.} In this case, the problem is that monitor A needs to be passed to thread 2 when thread 1 is done with it. 
-\paragraph{Case 2: thread 2 will go first.} In this case, the problem is that monitor B needs to be passed to thread 1. This can be done directly or using thread 2 as an intermediate. 
+The goal in this solution is to avoid the need to transfer ownership of a subset of the condition monitors. However, this goal is unreacheable in the previous example. Depending on the order of signals (line 12 and 15) two cases can happen.
+
+\paragraph{Case 1: thread 1 goes first.} In this case, the problem is that monitor A needs to be passed to thread 2 when thread 1 is done with it.
+\paragraph{Case 2: thread 2 goes first.} In this case, the problem is that monitor B needs to be passed to thread 1, which can be done directly or using thread 2 as an intermediate.
 \\
 
+Note that ordering is not determined by a race condition but by whether signalled threads are enqueued in FIFO or FILO order. However, regardless of the answer, users can move line 15 before line 11 and get the reverse effect.
+
 In both cases however, the threads need to be able to distinguish on a per monitor basis which ones need to be released and which ones need to be transferred. Which means monitors cannot be handled as a single homogenous group.
 
 \subsubsection{Dependency graphs}
-In the Listing 1 pseudo-code, there is a solution which would statisfy both barging prevention and mutual exclusion. If ownership of both monitors is transferred to the waiter when the signaller releases A and then the waiter transfers back ownership of A when it releases it then the problem is solved. Dynamically finding the correct order is therefore the second possible solution. The problem it encounters is that it effectively boils down to resolving a dependency graph of ownership requirements. Here even the simplest of code snippets requires two transfers and it seems to increase in a manner closer to polynomial. For example the following code which is just a direct extension to three monitors requires at least three ownership transfer and has multiple solutions: 
+In the Listing 1 pseudo-code, there is a solution which statisfies both barging prevention and mutual exclusion. If ownership of both monitors is transferred to the waiter when the signaller releases A and then the waiter transfers back ownership of A when it releases it then the problem is solved. Dynamically finding the correct order is therefore the second possible solution. The problem it encounters is that it effectively boils down to resolving a dependency graph of ownership requirements. Here even the simplest of code snippets requires two transfers and it seems to increase in a manner closer to polynomial. For example, the following code, which is just a direct extension to three monitors, requires at least three ownership transfer and has multiple solutions:
 
 \begin{multicols}{2}
@@ -496 +498 @@
 
 \subsubsection{Partial signalling}
-Finally, the solution that was chosen for \CFA is to use partial signalling. Consider the following case:
+Finally, the solution that is chosen for \CFA is to use partial signalling. Consider the following case:
 
 \begin{multicols}{2}
@@ -518 +520 @@
 \end{pseudo}
 \end{multicols}
-
-The partial signalling solution transfers ownership of monitor B at lines 10 but does not wake the waiting thread since it is still using monitor A. Only when it reaches line 11 does it actually wakeup the waiting thread. This solution has the benefit that complexity is encapsulated in to only two actions, passing monitors to the next owner when they should be release and conditionnaly waking threads if all conditions are met. Contrary to the other solutions, this solution quickly hits an upper bound on complexity of implementation.
+The partial signalling solution transfers ownership of monitor B at lines 10 but does not wake the waiting thread since it is still using monitor A. Only when it reaches line 11 does it actually wakeup the waiting thread. This solution has the benefit that complexity is encapsulated into only two actions, passing monitors to the next owner when they should be release and conditionnaly waking threads if all conditions are met. Contrary to the other solutions, this solution quickly hits an upper bound on complexity of implementation.
 
 % ======================================================================
@@ -526 +527 @@
 % ======================================================================
 % ======================================================================
-An important note is that, until now, signalling a monitor was a delayed operation. The ownership of the monitor is transferred only when the monitor would have otherwise been released, not at the point of the \code{signal} statement. However, in some cases, it may be more convenient for users to immediately transfer ownership to the thread that is waiting for cooperation. This is achieved using the \code{signal_block} routine\footnote{name to be discussed}.
+An important note is that, until now, signalling a monitor was a delayed operation. The ownership of the monitor is transferred only when the monitor would have otherwise been released, not at the point of the \code{signal} statement. However, in some cases, it may be more convenient for users to immediately transfer ownership to the thread that is waiting for cooperation, which is achieved using the \code{signal_block} routine\footnote{name to be discussed}.
 
 For example here is an example highlighting the difference in behaviour:
@@ -625 +626 @@
         bool inUse;
 public:
-        void P() { 
-                if(inUse) wait(c); 
+        void P() {
+                if(inUse) wait(c);
                 inUse = true;
         }
-        void V() { 
-                inUse = false;          
-                signal(c); 
+        void V() {
+                inUse = false;
+                signal(c);
         }
 }
@@ -639 +640 @@
         bool inUse;
 public:
-        void P() { 
-                if(inUse) _Accept(V); 
+        void P() {
+                if(inUse) _Accept(V);
                 inUse = true;
         }
-        void g() { 
+        void g() {
                 inUse = false;
 

doc/proposals/concurrency/version

@@ -1 @@
-0.9.119
+0.9.122

doc/proposals/virtual.txt

@@ -1 +1 @@
 Proposal for virtual functionality
+
+There are two types of virtual inheritance in this proposal, relaxed
+(implicit) and strict (explicit). Relaxed is the simpler case that uses the
+existing trait system with the addition of trait references and vtables.
+Strict adds some constraints and requires some additional notation but allows
+for down-casting.
+
+Relaxed Virtual Inheritance:
 
 Imagine the following code :
@@ -20 +28 @@
 void draw(line*);
 
-While all the members of this simple UI support drawing creating a UI that easily
-supports both these UI requires some tedious boiler-plate code :
+While all the members of this simple UI support drawing, creating a UI that
+easily supports both these UI requires some tedious boiler-plate code:
 
 enum type_t { text, line };
@@ -41 +49 @@
 }
 
-While this code will work as indented, adding any new widgets or any new widget behaviors
-requires changing existing code to add the desired functionality. To ease this maintenance
-effort required CFA introduces the concept of dynamic types, in a manner similar to C++.
-
-A simple usage of dynamic type with the previous example would look like :
-
-drawable* objects[10];
+While this code will work as implemented, adding any new widgets or any new
+widget behaviors requires changing existing code to add the desired
+functionality. To ease this maintenance effort required CFA introduces the
+concept of trait references.
+
+Using trait references to implement the above gives the following :
+
+trait drawable objects[10];
 fill_objects(objects);
 
 while(running) {
-      for(drawable* object : objects) {
+      for(drawable object : objects) {
             draw(object);
       }
 }
 
-However, this is not currently do-able in the current CFA and furthermore is not
-possible to implement statically. Therefore we need to add a new feature to handle
-having dynamic types like this (That is types that are found dynamically not types
-that change dynamically).
-
-C++ uses inheritance and virtual functions to find the
-desired type dynamically. CFA takes inspiration from this solution.
-
-What we really want to do is express the fact that calling draw() on a object
-should find the dynamic type of the parameter before calling the routine, much like the
-hand written example given above. We can express this by adding the virtual keyword on
-the parameter of the constraints on our trait:
+The keyword trait is optional (by the same rules as the struct keyword). This
+is not currently supported in CFA and the lookup is not possible to implement
+statically. Therefore we need to add a new feature to handle having dynamic
+lookups like this.
+
+What we really want to do is express the fact that calling draw() on a trait
+reference should find the underlying type of the given parameter and find how
+it implements the routine, as in the example with the enumeration and union.
+
+For instance specifying that the drawable trait reference looks up the type
+of the first argument to find the implementation would be :
 
 trait drawable(otype T) {
@@ -73 +81 @@
 };
 
-This expresses the idea that drawable is similar to an abstract base class in C++ and
-also gives meaning to trying to take a pointer of drawable. That is anything that can
-be cast to a drawable pointer has the necessary information to call the draw routine on
-that type. Before that drawable was only a abstract type while now it also points to a
-piece of storage which specify which behavior the object will have at run time.
-
-This storage needs to be allocate somewhere. C++ just adds an invisible pointer at
-the beginning of the struct but we can do something more explicit for users, actually
-have a visible special field :
-
-struct text {
-      char* text;
-      vtable drawable;
-};
-
-struct line{
-      vtable drawable;
-      vec2 start;
-      vec2 end;
-};
-
-With these semantics, adding a "vtable drawable" means that text pointers and line pointers are now
-convertible to drawable pointers. This conversion will not necessarily be a type only change however, indeed,
-the drawable pointer will point to the field "vtable drawable" not the head of the struct. However, since all
-the types are known at compile time, converting pointers becomes a simple offset operations.
-
-The vtable field contains a pointer to a vtable which contains all the information needed for the caller
-to find the function pointer of the desired behavior.
-
-One of the limitations of this design is that it does not support double dispatching, which
-concretely means traits cannot have routines with more than one virtual parameter. This design
-would have many ambiguities if it did support multiple virtual parameter. A futher limitation is 
-that traits over more than one type cannot have vtables meaningfully defined for them, as the 
-particular vtable to use would be a function of the other type(s) the trait is defined over.
-
-It is worth noting that the function pointers in these vtables are bound at object construction, rather than 
-function call-site, as in Cforall's existing polymorphic functions. As such, it is possible that two objects 
-with the same static type would have a different vtable (consider what happens if draw(line*) is overridden 
-between the definitions of two line objects). Given that the virtual drawable* erases static types though, 
-this should not be confusing in practice. A more distressing possibility is that of creating an object that 
-outlives the scope of one of the functions in its vtable. This is certainly a possible bug, but it is of a 
-type that C programmers are familiar with, and should be able to avoid by the usual methods.
-
-Extensibility.
-
-One of the obvious critics of this implementation is that it lacks extensibility for classes
-that cannot be modified (ex: Linux C headers). However this solution can be extended to
-allow more extensibility by adding "Fat pointers".
-
-Indeed, users could already "solve" this issue by writing their own fat pointers as such:
-
-trait MyContext(otype T) {
-      void* get_stack(virtual T*)
-};
-
-void* get_stack(ucontext_t *context);
-
-struct fat_ucontext_t {
-      vtable MyContext;
-      ucontext_t *context;
-}
-
-//Tedious forwarding routine
-void* get_stack(fat_ucontext_t *ptr) {
-      return get_stack(ptr->context);
-}
-
-However, users would have to write all the virtual methods they want to override and make
-them all simply forward to the existing method that takes the corresponding POCO(Plain Old C Object).
-
-The alternative we propose is to use language level fat pointers :
-
-trait MyContext(otype T) {
-      void* get_stack(virtual T*)
-};
-
-void* get_stack(ucontext_t *context);
-
-//The type vptr(ucontext_t) all
-vptr(ucontext_t) context;
-
-These behave exactly as the previous example but all the forwarding routines are automatically generated.
-
-Bikeshedding.
-
-It may be desirable to add fewer new keywords than discussed in this proposal; it is possible that "virtual" 
-could replace both "vtable" and "vptr" above with unambiguous contextual meaning. However, for purposes of 
-clarity in the design discussion it is beneficial to keep the keywords for separate concepts distinct.
-
+This could be implied in simple cases like this one (single parameter on the
+trait and single generic parameter on the function). In more complex cases it
+would have to be explicitly given, or a strong convention would have to be
+enforced (e.g. implementation of trait functions is always drawn from the
+first polymorphic parameter).
+
+Once a function in a trait has been marked as virtual it defines a new
+function that takes in that trait's reference and then dynamically calls the
+underlying type implementation. Hence a trait reference becomes a kind of
+abstract type, cannot be directly instantiated but can still be used.
+
+One of the limitations of this design is that it does not support double
+dispatching, which concretely means traits cannot have routines with more than
+one virtual parameter. The program must have a single table to look up the
+function on. Using trait references with traits with more than one parameter
+is also restricted, initially forbidden, see extension.
+
+Extension: Multi-parameter Virtual Traits:
+
+This implementation can be extended to traits with multiple parameters if
+one is called out as being the virtual trait. For example :
+
+trait iterator(otype T, dtype Item) {
+        Maybe(Item) next(virtual T *);
+}
+
+iterator(int) generators[10];
+
+Which creates a collection of iterators that produce integers, regardless of
+how those iterators are implemented. This may require a note that this trait
+is virtual on T and not Item, but noting it on the functions may be enough.
+
+
+Strict Virtual Inheritance:
+
+One powerful feature relaxed virtual does not support is the idea of down
+casting. Once something has been converted into a trait reference there is
+very little we can do to recover and of the type information, only the trait's
+required function implementations are kept.
+
+To allow down casting strict virtual requires that all traits and structures
+involved be organized into a tree. Each trait or struct must have a unique
+position on this tree (no multiple inheritance).
+
+This is declared as follows :
+
+trait error(otype T) virtual {
+        const char * msg(T *);
+}
+
+trait io_error(otype T) virtual error {
+        FILE * src(T *);
+}
+
+struct eof_error virtual io_error {
+        FILE * fd;
+};
+
+So the trait error is the head of a new tree and io_error is a child of it.
+
+Also the parent trait is implicitly part of the assertions of the children,
+so all children implement the same operations as the parent. By the unique
+path down the tree, we can also uniquely order them so that a prefix of a
+child's vtable has the same format as its parent's.
+
+This gives us an important extra feature, runtime checking of the parent-child
+relationship with a C++ dynamic_cast like operation. Allowing checked
+conversions from trait references to more particular references, which works
+if the underlying type is, or is a child of, the new trait type.
+
+Extension: Multiple Parents
+
+Although each trait/struct must have a unique position on each tree, it could
+have positions on multiple trees. All this requires is the ability to give
+multiple parents, as here :
+
+trait region(otype T) virtual drawable, collider;
+
+The restriction being, the parents must come from different trees. This
+object (and all of its children) can be cast to either tree. This is handled
+by generating a separate vtable for each tree the structure is in.
+
+Extension: Multi-parameter Strict Virtual
+
+If a trait has multiple parameters then one must be called out to be the one
+we generate separate vtables for, as in :
+
+trait example(otype T, otype U) virtual(T) ...
+
+This can generate a separate vtable for each U for which all the T+U
+implementations are provided. These are then separate nodes in the tree (or
+the root of different trees) as if each was created individually. Providing a
+single unique instance of these nodes would be the most difficult aspect of
+this extension, possibly intractable, though with sufficient hoisting and
+link-once duplication it may be possible.
+
+Example:
+
+trait argument(otype T) virtual {
+        char short_name(virtual T *);
+        bool is_set(virtual T *);
+};
+
+trait value_argument(otype T, otype U) virtual(T) argument {
+        U get_value(virtual T *);
+};
+
+Extension: Structural Inheritance
+
+Currently traits must be the internal nodes and structs the leaf nodes.
+Structs could be made internal nodes as well, in which case the child structs
+would likely structurally inherit the fields of their parents.
+
+
+Storing the Virtual Lookup Table (vtable):
+
+We have so far been silent on how the vtable is created, stored and accessed.
+
+Creation happens at compile time. Function pointers are found by using the
+same best match rules as elsewhere (additional rules for defaults from the
+parent may or may not be required). For strict virtual this must happen at the
+global scope and forbidding static functions, to ensure that a single unique
+vtable is created. Similarly, there may have to be stricter matching rules
+for the functions that go into the vtable, possibly requiring an exact match.
+Relaxed virtual could relax both restrictions, if we allow different vtable
+at different conversion (struct to trait reference) sites. If it is allowed
+local functions being bound to a vtable could cause issues when they go out
+of scope, however this should follow the lifetime rules most C programs
+already follow implicitly.
+
+Most vtables should be stored statically, the only exception being some of
+the relaxed vtables that could have local function pointers. These may be able
+to be stack allocated. All vtables should be immutable and require no manual
+cleanup.
+
+Access has two main options:
+
+The first is through the use of fat pointers, or a tuple of pointers. When the
+object is converted to a trait reference, the pointers to its vtables are
+stored along side it.
+
+This allows for compatibility with existing structures (such as those imported
+from C) and is the default storage method unless a different one is given.
+
+The other is by inlining the vtable pointer as "intrusive vtables". This adds
+a field to the structure to the vtable. The trait reference then has a single
+pointer to this field, the vtable includes an offset to find the beginning of
+the structure again.
+
+This is used if you specify a vtable field in the structure. If given in the
+trait the vtable pointer in the trait reference can then become a single
+pointer to the vtable field and use that to recover the original object
+pointer as well as retrieve all operations.
+
+trait drawable(otype T) {
+        vtable drawable;
+};
+
+struct line {
+        vtable drawable;
+        vec2 start;
+        vec2 end;
+};
+
+This inline code allows trait references to be converted to plain pointers
+(although they still must be called specially). The vtable field may just be
+an opaque block of memory or it may allow user access to the vtable. If so
+then there should be some way to retrieve the type of the vtable, which will be
+autogenerated and often unique.
+
+
+Keyword Usage:
+
+It may be desirable to add fewer new keywords than discussed in this proposal.
+It is possible that "virtual" could replace both "vtable" above with
+unambiguous contextual meaning. However, for purposes of clarity in the design
+discussion it is beneficial to keep the keywords for separate concepts distinct.
+
+
+Trait References and Operations:
+
+sizeof(drawable) will return the size of the trait object itself. However :
+
+line a_line;
+drawable widget = a_line;
+sizeof(widget);
+
+Will instead return the sizeof the underlying object, although the trait must
+require that its implementation is sized for there to be a meaningful value
+to return. You may also get the size of the trait reference with
+
+sizeof(&widget);
+
+Calling free on a trait reference will free the memory for the object. It will
+leave the vtables alone, as those are (always?) statically allocated.