Changeset d1ef1b0

Timestamp:

Aug 6, 2016, 3:37:44 PM (8 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

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

Children:

752dc70

Parents:

a2f920f

Message:

Finished traits subsection of Comp II draft

File:

• doc/aaron_comp_II/comp_II.tex (modified) (3 diffs)

doc/aaron_comp_II/comp_II.tex

@@ -135 +135 @@
 For instance, ©twice© could have been defined as below, using the \CFA syntax for operator overloading:
 \begin{lstlisting}
-forall(otype S | { S ?+?(S, S); })
+forall(otype S | { ®S ?+?(S, S);® })
 S twice(S x) { return x + x; }  // (2)
 \end{lstlisting} 
@@ -149 +149 @@
 \CFA provides \emph{traits} as a means to name a group of type assertions, as in the example below:
 \begin{lstlisting}
-trait has_magnitude(otype T) {
+®trait has_magnitude(otype T)® {
     bool ?<?(T, T);        // comparison operator for T
     T -?(T);               // negation operator for T
@@ -168 +168 @@
 \end{lstlisting}
 
-Semantically, a trait is merely a named list of type assertions, but they can be used in many of the same situations where an interface in Java or an abstract base class in \CC would be used.
+Semantically, a trait is simply a named list of type assertions, but one can be used for many of the same purposes that an interface in Java or an abstract base class in \CC would be used for.
 Unlike Java interfaces or \CC base classes, \CFA types do not explicitly state any inheritance relationship to traits they satisfy; this can be considered a form of structural inheritance, similar to interface implementation in Go, as opposed to the nominal inheritance model of Java and \CC. 
-% TODO talk about modelling of nominal inheritance with structural inheritance, possibility of investigating some resolver algorithms that require nominal
+Nominal inheritance can be simulated with traits using marker variables or functions:
+\begin{lstlisting}
+trait nominal(otype T) {
+    ®T is_nominal;®
+};
+
+int is_nominal;  // int now satisfies the nominal trait
+{
+    char is_nominal; // char satisfies the nominal trait
+}
+// char no longer satisfies the nominal trait here  
+\end{lstlisting}
+
+Traits, however, are significantly more powerful than nominal-inheritance interfaces; firstly, due to the scoping rules of the declarations which satisfy a trait's type assertions, a type may not satisfy a trait everywhere that the type is declared, as with ©char© and the ©nominal© trait above. 
+Secondly, traits may be used to declare a relationship between multiple types, a property which may be difficult or impossible to represent in nominal-inheritance type systems:
+\begin{lstlisting}
+trait pointer_like(®otype Ptr, otype El®) {
+    lvalue El *?(Ptr); // Ptr can be dereferenced into a modifiable value of type El
+}
+
+struct list {
+    int value;
+    list *next;  // may omit "struct" on type names in \CFA
+};
+
+typedef list* list_iterator;
+
+lvalue int *?( list_iterator it ) {
+    return it->value;
+}
+\end{lstlisting}
+
+In the example above, ©list_iterator, int© satisfies ©pointer_like© by the given function, and ©list_iterator, list© also satisfies ©pointer_like© by the default pointer dereference operator. 
+While a nominal-inheritance system with associated types could model one of those two relationships by making ©El© an associated type of ©Ptr© in the ©pointer_like© implementation, few such systems could model both relationships simultaneously.
+
+The flexibility of \CFA's implicit trait satisfaction mechanism provides user programmers with a great deal of power, but also blocks some optimization approaches for expression resolution. 
+The ability of types to begin to or cease to satisfy traits when declarations go into or out of scope makes caching of trait satisfaction judgements difficult, and the ability of traits to take multiple type parameters could lead to a combinatorial explosion of work in any attempt to pre-compute trait satisfaction relationships. 
+On the other hand, the addition of a nominal inheritance mechanism to \CFA's type system or replacement of \CFA's trait satisfaction system with a more object-oriented inheritance model and investigation of possible expression resolution optimizations for such a system may be an interesting avenue of further research.
 
 \subsection{Name Overloading}