Least upper bound fixes.

docs/language/dartLangSpec.tex

 \documentclass{article}
 \usepackage{epsfig}
 \usepackage{dart}
 \usepackage{bnf}
 \usepackage{hyperref}
 \newcommand{\code}[1]{{\sf #1}}
 \title{Dart Programming Language  Specification \\
-{\large Draft Version 0.70}}
+{\large Draft Version 0.71}}
 \author{The Dart Team}
 \begin{document}
 \maketitle
 
 \tableofcontents
 
 \newpage
 
 \pagestyle{myheadings}
 \markright{{\bf Draft}  Dart Programming Language Specification {\bf Draft}}
@@ skipping 483 matching lines @@
 \ref{try}: \ON{} with no \CATCH{} implies \DYNAMIC{}, not \cd{Object}.
 
 \ref{return}: Added warning if \RETURN{} without expression mixed with \RETURN{} with an expression.
 
 \ref{exports}: Ensure that exports treat \code{dart:} libs specially, like imports do.
 
 \ref{typePromotion}: Added notion of type promotion.
 
 \ref{typedef}: Banned all recursion in typedefs.
 
+\subsubsection{Changes Since Version 0.7}
+
+\ref{leastUpperBounds}:  Extended LUBs to all types.
+
+
 
 \section{Notation}
 \label{notation}
 
 We distinguish between normative and non-normative text. Normative text defines the rules of Dart. It is given in this font. At this time, non-normative text includes:
 \begin{itemize}
 \item[Rationale] Discussion of the motivation for language design decisions appears in italics. \rationale{Distinguishing normative from non-normative helps clarify what part of the text is binding and what part is merely expository.}
 \item[Commentary] Comments such as  ``\commentary{The careful reader will have noticed that the name Dart has four characters}'' serve to illustrate or clarify the specification, but are redundant with the normative text.  \commentary{The difference between commentary and rationale can be subtle.} \rationale{ Commentary is more general than rationale, and may include illustrative examples or clarifications. }
 \item[Open questions] (\Q{in this font}). Open questions are points that are unsettled in the mind of the author(s) of the specification; expect them (the questions, not the authors; precision is important in a specification) to be eliminated in the final specification. \Q{Should the text at the end of the previous bullet be rationale or commentary?}
 \end{itemize}
@@ skipping 684 matching lines @@
 a class that is explicitly declared with the  \ABSTRACT{}  modifier, either by means of a class declaration or via a type alias (\ref{typedef}) for a mixin application (\ref{mixinApplication}). A {\em concrete class} is a class that is not abstract.
 %, or a class that declares at least one abstract method  (\ref{abstractInstanceMembers}).
 
 \rationale{
 %The abstract modifier for classes is intended to be used in scenarios where an abstract class $A$ inherits from another abstract class $B$. In such a situation, it may be that A$ $itself does not declare any abstract methods. In the absence of an abstract modifier on the class, the class would be interpreted as a concrete class. However, w
 We want different behavior for concrete classes and abstract classes. If $A$ is intended to be abstract, we want the static checker to warn about any attempt to instantiate $A$, and we do not want the checker to complain about unimplemented methods in $A$. In contrast, if $A$ is intended to be concrete, the checker should warn about all unimplemented methods, but allow clients to instantiate it freely.
 }
 
 The {\em interface of class $C$} is an implicit interface that declares instance members that correspond to the instance members declared by $C$, and whose direct superinterfaces are the direct superinterfaces of $C$ (\ref{superinterfaces}). When a class name appears as a type, that name denotes the interface of the class.
 
+% making an exception for the setters generated for final fields is tempting but problematic.
+% If a super type defines a setter, it will be overridden yet have no impact on the interface.
+% Maybe the final field hides the setter in scope?
+% I think the original rules were best.
+
  It is a compile-time error if a class declares two members of the same name.
  %, except that a getter and a setter may be declared with the same name provided both are instance members or both are static members.
 It is a compile-time error if a class has an instance member and a static member  with the same name. 
 % It is a compile-time error if a generic (\ref{generics}) class declares a member with the same name as one of its type parameters.
 
 \commentary{Here are simple examples, that illustrate the difference between ``has a member'' and ``declares a member''. For example, \code{B} {\em declares} one member named \code{f}, but {\em has} two such members. The rules of inheritance determine what members a class has.
 }
 
 \begin{dartCode}
 \CLASS{} A \{
@@ skipping 223 matching lines @@
 %\VOID{} \SET{} $v=(T$ $x)$
 
 %whose execution sets the value of $v$ to the incoming argument $x$.
 
 %A non-final instance variable declaration  of the form \code{\VAR{} $v$;} or the form  \code{\VAR{} $v$ = $e$;}   always induces an implicit setter function with signature 
 
 %\SET{} $v=(x)$
 
 %whose execution sets the value of $v$ to the incoming argument $x$.
 
+% It is a compile-time error/warning if a a class $C$ declares a final instance variable $v$ and $C$ inherits a setter $v=$.
+
 
 \subsection{Constructors}
 \label{constructors}
 
 A {\em constructor} is a special function that is used in instance creation expressions (\ref{instanceCreation}) to produce objects. Constructors may be generative (\ref{generativeConstructors}) or they may be factories (\ref{factories}). 
 
 A {\em constructor name} always begins with the name of its immediately enclosing class, and may optionally be followed by a dot and an identifier $id$. It is a compile-time error if $id$ is the name of a member  declared in the immediately enclosing class. It is a compile-time error if the name of a  constructor is not a constructor name. 
 
 
 % In what scope do constructors go? The simple names of named constructors go  in the static scope of the class. Unnamed ones go nowhere, but we use the class name to refer to them; the class name could also in the static scope of the class as well to prevent weird errors, or we could ban it explicitly and avoiding duplication. Similarly, the instance scope could contain the constructor names and class name, or we could have special rules to prevent collisions between instance members and constructors or the class.
@@ skipping 650 matching lines @@
 \item $m^\prime$ has the same name as $m$.
 \item $m^\prime$ is accessible to $K$.  
 \item $A$ is a direct superinterface of $J$ and either
   \begin{itemize}
   \item $m^\prime$ is a member of $A$ or 
   \item $m^\prime$ is a member of $inherited(A, K)$.
   \end{itemize}
 \end{itemize}
 
 
-Let $I$ be the implicit interface of a class $C$ declared in library $L$.  $I$ {\em inherits} all members of $inherited(I, L)$ and $I$ {\em overrides} $m^\prime$ if  $m^\prime \in overrides(I, L)$.
+Let $I$ be the implicit interface of a class $C$ declared in library $L$.  $I$ {\em inherits} all members of $inherited(I, L)$ and $I$ {\em overrides} $m^\prime$ if  $m^\prime \in overrides(I, L)$. It is a static warning if $m$ is a method and $m^\prime$ is a getter, or if $m$ is a getter and $m^\prime$ is a method.
 
 
 %Let $I = S_0$ be the implicit interface of a class $C$ declared in library $L$, and let $\{S_1 \ldots S_k\}$ be the set of all superinterfaces of $I$. 
 
 %Let $I$ be the implicit interface of a class $C$.  $I$ inherits any instance members of its superinterfaces that are not overridden by members declared in $C$. 
 
 % tighten definition? do we need chain as for classes?  Definition for interface override?
 
 However, if the above rules would cause multiple members $m_1, \ldots,  m_k$ with the same name $n$ to be inherited (because identically named members existed in several superinterfaces) then at most one member is inherited. 
 
-%If some but not all of the $m_i, 1 \le i \le k$ are getters, or if some but not all of the $m_i$ are setters, none of the $m_i$ are inherited, and a static warning is issued.
+If some but not all of the $m_i, 1 \le i \le k$ are getters none of the $m_i$ are inherited, and a static warning is issued.
 
 Otherwise, if the static types $T_1, \ldots,  T_k$ of the members $m_1, \ldots,  m_k$  are not identical, then there must be a member $m_x$ such that $T_x <: T_i, 1 \le x \le k$ for all  $i  \in 1..k$, or a static type warning occurs. The member that is inherited  is $m_x$, if it exists; otherwise:
 \begin{itemize}
 \item Let $numberOfPositionals(f)$ denote the number of positional parameters of a function $f$, and let $numberOfRequiredParams(f)$ denote the number of required parameters of a function $f$. Furthermore, let $s$ denote the set of all named parameters of the $m_1, \ldots,  m_k$.  Then let 
 
 $h = max(numberOfPositionals(m_i)), $
 
 $r = min(numberOfRequiredParams(m_i)), i \in 1..k$. 
 
 If $r \le h$ then $I$ has a method named $n$, with $r$ required parameters of type \DYNAMIC{}, $h$  positional parameters of type \DYNAMIC{}, named parameters $s$ of type  \DYNAMIC{} and  return type  \DYNAMIC{}.  
 \item Otherwise none of the members $m_1, \ldots,  m_k$ is inherited.
 \end{itemize}
 
 \commentary{The only situation where the runtime would be concerned with this would be during reflection, if a mirror attempted to obtain the signature of an interface member. 
 }
 
 \rationale{
 The current solution is a tad complex, but is robust in the face of type annotation changes.  Alternatives: (a) No member is inherited in case of conflict. (b) The first m is selected (based on order of superinterface list) (c) Inherited member chosen at random. 
 
 (a) means that the presence of an inherited member of an interface varies depending on type signatures.  (b) is sensitive to irrelevant details of the declaration and (c) is liable to give unpredictable results between implementations or even between different compilation sessions.
 }
 
+% Need warnings if overrider conflicts with overriddee either because signatures are incompatible or because done is a method and one is a getter or setter.
+
 \section{Mixins}
 \label{mixins} 
 
 
 A mixin describes the difference between a class and its superclass. A mixin is always derived from an existing class declaration. 
 
 It is a compile-time error if a declared or derived mixin refers to \SUPER{}. It is a compile-time error if a declared or derived mixin explicitly declares a constructor. It is a compile-time error if a mixin is derived from a class whose superclass is not \code{Object}.
 
 \rationale{
 These restrictions are temporary.  We expect to remove them in later versions of Dart.
@@ skipping 1573 matching lines @@
 {\bf assignmentOperator:}`=' ;
       compoundAssignmentOperator
     .
 \end{grammar}
 
 Evaluation of an assignment $a$ of the form $v$ \code{=} $e$ proceeds as follows:
 
 
 If there is neither a local variable declaration with name $v$ nor a setter declaration with name $v=$ in the lexical scope enclosing $a$, then:
 \begin{itemize}
- \item If  $a$ occurs inside a top level or static function (be it function, method, getter,  or setter) or variable initializer, evaluation of $a$ causes $e$ to be evaluated, after which a \code{NoSuchMethodError} is thrown. \item Otherwise, the assignment is equivalent to the assignment \code{ \THIS{}.$v$ = $e$}. 
+ \item If  $a$ occurs inside a top level or static function (be it function, method, getter,  or setter) or variable initializer, evaluation of $a$ causes $e$ to be evaluated, after which a \code{NoSuchMethodError} is thrown. 
+ \item Otherwise, the assignment is equivalent to the assignment \code{ \THIS{}.$v$ = $e$}. 
  \end{itemize}
  
  Otherwise,  let $d$ be the innermost declaration whose name is $v$, if it exists.
 
-If $d$ is the declaration of a local variable, the expression $e$ is evaluated to an object $o$. Then, the variable $v$ is bound to $o$. The value of the assignment expression is $o$.  
+If $d$ is the declaration of a local variable, the expression $e$ is evaluated to an object $o$. Then, the variable $v$ is bound to $o$. 
+% unless $v$ is \FINAL{}, in which case a \code{NoSuchMethodError} is thrown (even if there is a noSuchMethod). 
+The value of the assignment expression is $o$.  
 
 If $d$ is the declaration of a library variable, the expression $e$ is evaluated to an object $o$. Then the setter $v=$ is invoked with its formal parameter bound to $o$. The value of the assignment expression is $o$.  
 
 Otherwise, if $d$ is the declaration of a static variable in class $C$, then the assignment is equivalent to the assignment \code{$C.v$ = $e$}.
 
 Otherwise, the assignment is equivalent to the assignment \code{ \THIS{}.$v$ = $e$}. 
 
 In checked mode, it is a dynamic type error if $o$ is not \NULL{} and the interface of the class of $o$ is not a subtype of the actual type (\ref{actualTypeOfADeclaration}) of $v$.
 
 It is a static type warning if the static type of $e$ may not be assigned to the static type of $v$. The static type of the expression $v$ \code{=} $e$ is the static type of $e$.
@@ skipping 2187 matching lines @@
 
 \begin{itemize}
 \item  $[A_1, \ldots, A_n/U_1, \ldots, U_n]T$ if $d$ depends on type parameters $U_1, \ldots, U_n$, and $A_i$ is the value of $U_i, 1 \le i \le n$.
 \item $T$ otherwise.
 \end{itemize}
 
 \subsubsection{Least Upper Bounds}
 \label{leastUpperBounds}
 
 Given two interfaces $I$ and $J$, let $S_I$ be the set of superinterfaces of $I$,  let $S_J$ be the set of superinterfaces of $J$ and let $S =  (I \cup S_I) \cap (J \cup S_J)$.  Furthermore, we define $S_n = \{T | T \in S  \wedge depth(T) =n\}$ for any finite $n$ %, and $k=max(depth(T_1), \ldots, depth(T_m)), T_i \in S, i \in 1..m$, 
 where $depth(T)$ is the number of steps in the longest inheritance path from $T$ to \code{Object}. Let $q$ be the largest number such that $S_q$ has cardinality one. The least upper bound of $I$ and $J$ is the sole element of  $S_q$.

[Johnni Winther, 2013/10/23 07:46:05]

This part doesn't handle type arguments and therefore fails to ensure the
(natural) invariant: T << S => lub(T, S). For instance lub(List<int>,List<num>)
is Object and not List<num>.

[Johnni Winther, 2013/10/24 11:34:49]

The missing handling of generic types actually cause a warning in our API. In
the implementation HttpClient we have code like this:

(isSecure ? SecureSocket.connect(...) : Socket.connect(...)).then(...)

Socket.connect returns a Future<Socket> and SecureSocket.connect returns a
Future<SecureSocket> and since the least upper bound is Object we get a warning
on the call to 'then'.

I propose that we either 1) add the invariant rule on the side, i.e. that if T
<< S then lub(T,S) = S, or 2) (the more elaborate) use the algorithm above on
declarations instead of types (finding Future as the most specific common
declaration of Future<Socket> and Future<SecureSocket>) and on each type
variable use the invariant to find the type argument or, if that fails, use
dynamic as type argument (in this case finding Socket as the type argument).

 
-% void, dynamic, type variables need to be figured into this.
+The least upper bound of \DYNAMIC{} and any type $T$ is \DYNAMIC{}.

[Johnni Winther, 2013/10/23 07:46:05]

Maybe this should be the opposite to follow the invariant from above.

[Johnni Winther, 2013/10/24 14:05:01]

I need to flip a bit in my head: any type _is_ more specific than dynamic! Sorry
for the noise.

+The least upper bound of \VOID{} and any type $T \ne \DYNAMIC{}$ is \VOID{}.

[Johnni Winther, 2013/10/23 07:46:05]

By the definition of << on function types we could say that T << void for any T,
and use the invariant. This would then change lub(void,dynamic) to void which I
think is better anyway. For instance:

void m1() {}
m2() {}

int a = b ? m1() : m2(); // Warning void is not assignable to int.

[Johnni Winther, 2013/10/24 14:05:01]

Again. Noise. (Though a better warning in this example...)

+Let $U$ be a type variable with upper bound $B$. The least upper bound of $U$ and a type $T$ is the least upper bound of $B$ and $T$. 

[Johnni Winther, 2013/10/23 07:46:05]

This rules follows the invariant!

[Johnni Winther, 2013/10/23 12:21:55]

Looking closer at this, this is actually not well-defined for the least upper
bound of two type variables. Consider this:

class C<A, B extends A, C extends A, D extends C> {}

Do we have (always try left first)
  lub(B,D) = lub(A,D) = lub(Object,D) = Object
or (always try right first)
  lub(B,D) = lub(B,C) = lub(B,A) = lub(B,Object) = Object
or (use an oracle (try left,right,right,right))
  lub(B,D) = lub(A,D) = lub(A,C) = lub(A,A) = A
or (use another oracle (try right,right,right,left))
  lub(B,D) = lub(B,C) = lub(B,A) = lub(A,A) = A
or (use a dumb oracle (try right,left,left))
  lub(B,D) = lub(B,C) = lub(A,C) = lub(Object,C) = Object
or ... ?

 
- 
+The least upper bound relation is symmetric and reflexive.
+
+% Function types

[Johnni Winther, 2013/10/23 07:46:05]

These rules follows the invariant!

+
+The least upper bound of a function type and an interface type $T$ is the least upper bound of \cd{Function} and $T$.
+Let $F$ and $G$ be function types. If $F$ and $G$ differ in their number of required parameters, then the least upper bound of $F$ and $G$ is \cd{Function}.  Otherwise:
+\begin{itemize}
+\item If $F= (T_1 \ldots T_r, [T_{r+1}, \ldots, T_n]) \longrightarrow T_0$ and $G= (S_1 \ldots S_r, [S_{r+1}, \ldots, S_k]) \longrightarrow S_0$ where $k \le n$ then the least upper bound of $F$ and $G$ is $(L_1 \ldots L_r, [L_{r+1}, \ldots, L_k]) \longrightarrow L_0$ where $L_i$ is the least upper bound of $T_i$ and $S_i, i \in 0..k$.
+\item If $F= (T_1 \ldots T_r, [T_{r+1}, \ldots, T_n]) \longrightarrow T_0$ and $G= (S_1 \ldots S_r, \{ \ldots \}) \longrightarrow S_0$ then the least upper bound of $F$ and $G$ is $(L_1 \ldots L_r) \longrightarrow L_0$ where $L_i$ is the least upper bound of $T_i$ and $S_i, i \in 0..r$.
+\item If $F= (T_1 \ldots T_r, \{T_{r+1}$  $p_{r+1}, \ldots, T_f$ $p_f\}) \longrightarrow T_0$ and $G= (S_1 \ldots S_r, \{ S_{r+1}$  $q_{r+1}, \ldots, S_g$ $q_g\}) \longrightarrow S_0$ then let $\{x_m, \ldots x_n\}  = \{p_{r+1}, \ldots, p_f\} \cap \{q_{r+1}, \ldots, q_g\}$ and let $X_j$ be the least upper bound of the types of $x_j$ in $F$ and $G, j \in m..n$. Then
+the least upper bound of $F$ and $G$ is $(L_1 \ldots L_r, \{ X_m$ $x_m, \ldots, X_n$ $x_n\}) \longrightarrow L_0$ where $L_i$ is the least upper bound of $T_i$ and $S_i, i \in 0..r$ 
+\end{itemize}
+
 
 \section{Reference}
 \label{reference}
 
 \subsection{Lexical Rules}
 \label{lexicalRules}
 
 Dart source text is represented as a sequence of Unicode code points.  This sequence is first converted into a sequence of tokens according to the lexical rules given in this specification.  At any point in the tokenization process, the longest possible token is recognized.
 
 \subsubsection{Reserved Words} 
@@ skipping 108 matching lines @@
 \item The names of compile time constant variables never use lower case letters. If they consist of multiple words, those words are separated by underscores. Examples: PI,  I\_AM\_A\_CONSTANT.
 \item The names of functions (including getters, setters, methods and local or library functions) and non-constant variables begin with a lowercase letter. If the name consists of multiple words, each  word (except the first) begins with an uppercase letter.  No other uppercase letters are used. Examples: camlCase, dart4TheWorld
 \item The names of types (including classes and type aliases) begin with an upper case letter.  If the name consists of multiple words, each  word  begins with an uppercase letter.  No other uppercase letters are used. Examples: CamlCase, Dart4TheWorld.
 \item The names of type variables are short (preferably single letter). Examples: T, S, K, V , E.
 \item The names of libraries or library prefixes never use upper case letters. If they consist of multiple words, those words are separated by underscores. Example: my\_favorite\_library.
 \end{itemize}
 }
 
 
 \end{document}