[Olena-patches] 715: Start a draft of Static's documentation.

https://svn.lrde.epita.fr/svn/oln/trunk/static Index: ChangeLog from Roland Levillain &lt;roland(a)lrde.epita.fr&gt; Start a draft of Static's documentation. * doc/README, doc/intro.txt, doc/rules.txt, doc/scool.txt, * doc/algorithms.txt: New. * doc/algorithms.ml: New (prototype of Static's type-checking rules, written in Objective Caml). * stc/scoop.hh: Typos, FIXMEs. doc/README | 20 + doc/algorithms.ml | 567 +++++++++++++++++++++++++++++++++++++++++++++++++++++ doc/algorithms.txt | 271 +++++++++++++++++++++++++ doc/intro.txt | 292 +++++++++++++++++++++++++++ doc/rules.txt | 514 ++++++++++++++++++++++++++++++++++++++++++++++++ doc/scool.txt | 12 + stc/scoop.hh | 11 - 7 files changed, 1685 insertions(+), 2 deletions(-) Index: doc/algorithms.ml --- doc/algorithms.ml (revision 0) +++ doc/algorithms.ml (revision 0) @@ -0,0 +1,567 @@ +(* Prototyping SCOOP's algorithms on virtual types in Objective Caml. *) + + +(*--------. +| Types. | +`--------*) + +module StringType = + struct + type t = string + let compare = String.compare + end +;; + +module StringMap = Map.Make (StringType);; + + +type cxx_type = + (* Static stypes. *) + | Stc_None + | Stc_Not_found + | Stc_Abstract + | Stc_Not_delegated + | Stc_Not_delegated_Abstract + | Stc_Final of cxx_type + + (* C++ types. *) + | Std_Char + | Std_Short + | Std_Int + | Std_Unsigned + | Std_Float + | Scoop_Class of scoop_class + +and vtypes_dict = cxx_type StringMap.t +and scoop_class = { super: cxx_type; vtypes: vtypes_dict } +;; + +(* A helper to create virtual types sets. *) +let rec create_vtypes = function + | [] -> StringMap.empty + | (type_name, type_val)::t -> + StringMap.add type_name type_val (create_vtypes t) +;; + + +(*-----------------. +| Error handling. | +`-----------------*) + +exception Scoop_exception of string;; + +let error = + function s -> raise (Scoop_exception s) +;; + + +(*----------------------. +| Virtual type lookup. | +`----------------------*) + +let find_local (source: cxx_type) (target: string) : cxx_type = + match source with + | Scoop_Class c -> + begin + try + StringMap.find target c.vtypes + with Not_found -> Stc_Not_found + end + | _ -> raise (Scoop_exception "find_local: source is not SCOOP class.") +;; + +let merge2 (local_res : cxx_type) (super_res : cxx_type) : cxx_type = + match local_res, super_res with + + | Stc_Abstract, Stc_Not_found -> Stc_Abstract + | Stc_Not_found, Stc_Not_found -> Stc_Not_found + | Stc_Final t, Stc_Not_found -> Stc_Final t + | t, Stc_Not_found -> t + + | Stc_Not_found, Stc_Abstract -> Stc_Not_found + | Stc_Abstract, Stc_Abstract -> Stc_Abstract + | Stc_Final t, Stc_Abstract -> Stc_Final t + | t, Stc_Abstract -> t + + | Stc_Abstract, Stc_Final u -> error "Final VT redefined abstract" + | Stc_Not_found, Stc_Final u -> Stc_Final u + | Stc_Final t, Stc_Final u -> error "Final VT redefined final." + | t, Stc_Final u -> error "Final VT redefined." + + | Stc_Abstract, u -> error "VT redefined abstract." + | Stc_Not_found, u -> u + | Stc_Final t, u -> Stc_Final t + | t, u -> t + +;; + +(* Another version (rewriting) of merge3. *) +let merge3 (local_res : cxx_type) (super_res : cxx_type) + (delegatee_res : cxx_type) : cxx_type = + match local_res, super_res, delegatee_res with + + (* local_res == stc::not_found. *) + | Stc_Not_found, Stc_Not_found, Stc_Not_found -> Stc_Not_found + | Stc_Not_found, Stc_Not_found, Stc_Abstract -> Stc_Not_found + | Stc_Not_found, Stc_Not_found, Stc_Final v -> Stc_Final v + | Stc_Not_found, Stc_Not_found, v -> v + + | Stc_Not_found, Stc_Abstract, Stc_Not_found -> Stc_Not_found + | Stc_Not_found, Stc_Abstract, Stc_Abstract -> Stc_Abstract + | Stc_Not_found, Stc_Abstract, Stc_Final v -> Stc_Final v + | Stc_Not_found, Stc_Abstract, v -> v + + | Stc_Not_found, Stc_Final u, _ -> Stc_Final u + | Stc_Not_found, u, _ -> u + + (* local_res == stc::not_abstract. *) + | Stc_Abstract, Stc_Not_found, Stc_Not_found -> Stc_Abstract + | Stc_Abstract, Stc_Not_found, Stc_Abstract -> Stc_Abstract + | Stc_Abstract, Stc_Not_found, Stc_Final v -> Stc_Final v + | Stc_Abstract, Stc_Not_found, v -> v + + | Stc_Abstract, Stc_Abstract, Stc_Not_found -> Stc_Abstract + | Stc_Abstract, Stc_Abstract, Stc_Abstract -> Stc_Abstract + | Stc_Abstract, Stc_Abstract, Stc_Final v -> Stc_Final v + | Stc_Abstract, Stc_Abstract, v -> v + + | Stc_Abstract, Stc_Not_delegated_Abstract, _ -> Stc_Not_delegated_Abstract + | Stc_Abstract, Stc_Not_delegated, _ -> Stc_Not_delegated_Abstract + + | Stc_Abstract, Stc_Final u, _ -> error ("Final VT " ^ + "redefined abstract") + | Stc_Abstract, u, _ -> error ("VT redefined " ^ + "abstract.") + + (* local_res == stc::not_delegated. *) + | Stc_Not_delegated, Stc_Not_found, _ -> Stc_Not_delegated + | Stc_Not_delegated, Stc_Abstract, _ -> Stc_Not_delegated_Abstract + | Stc_Not_delegated, Stc_Not_delegated_Abstract, _ -> Stc_Not_delegated_Abstract + + (* local_res == stc::not_delegated_abstract. *) + (* FIXME: Shouldn't we introduce a means to tag a vtype both + as abstract *and* not delegated? (Currently, the rule below + prevents this). *) + | Stc_Not_delegated_Abstract, _, _ -> error ("Local declaration" ^ + " of not delegated" ^ + " and abstract") + + (* local_res == stc::final<T>. *) + | Stc_Final t, Stc_Final u, _ -> error ("Final VT " ^ + "redefined final.") + | Stc_Final t, _, _ -> Stc_Final t + + (* local_res == T. *) + | t, Stc_Final u, _ -> error ("Final VT " ^ + "redefined.") + | t, _, _ -> t + +;; + + +let rec find_rec (source : cxx_type) (target : string) : cxx_type = + match source with + | Stc_None -> Stc_Not_found + | Scoop_Class c -> + begin + let local_res = find_local source target in + + let super_res = find_rec c.super target in + (* FIXME: This might not be efficient, since + find_rec_in_super can be called several times on the + nodes of the delegation branch when going down the + inheritance branch. Of course, the declarative nature + of C++ templates will avoid this cost, but it remains + inelegant, IMHO. *) + + let delegatee = find_rec_in_supers source "delegatee_type" in + let delegatee_res = + if delegatee = Stc_Not_found then + Stc_Not_found + else + find_rec delegatee target in + + merge3 local_res super_res delegatee_res + end + | _ -> error "find_rec: source is not a SCOOP class." + +(* Like find_rec, but only search in the inheritance branch. *) +and find_rec_in_supers (source : cxx_type) (target : string) : cxx_type = + match source with + | Stc_None -> Stc_Not_found + | Scoop_Class c -> + begin + let local_res = find_local source target in + let super_res = find_rec c.super target in + merge2 local_res super_res + end + | _ -> error "find_rec_in_supers: source is not a SCOOP class." +;; + + +let find (source : cxx_type) (target : string) : cxx_type = + match find_rec source target with + | Stc_Abstract -> error "find: VT is abstract." + | Stc_Not_delegated_Abstract -> error "find: VT is abstract." + | Stc_Not_delegated -> Stc_Not_found + | Stc_Final t -> t + | t -> t +;; + + + +(*-----------. +| Examples. | +`-----------*) + +(* ** Virtual type definition + + Ex. + + class A < stc::none = + { + vtype my_type = int; + } +*) +let a = Scoop_Class { super = Stc_None; + vtypes = create_vtypes ["my_type", Std_Int] } in +assert (find a "my_type" = Std_Int);; + + +(* ** Virtual type re-definition. + + Ex. + + class A < stc::none = + { + vtype my_type = int; + } + // Valid. + class B < A = + { + vtype my_type = float; + } + // Valid. + class C < A = + { + vtype my_type = int; + } +*) +let a = Scoop_Class { super = Stc_None; + vtypes = create_vtypes ["my_type", Std_Int] } in +let b = Scoop_Class { super = a; + vtypes = create_vtypes ["my_type", Std_Float] } in +let c = Scoop_Class { super = b; + vtypes = create_vtypes ["my_type", Std_Int] } in +assert (find c "my_type" = Std_Int);; + + +(* ** Virtual type abstract declaration (i.e., deferred definition). + + Ex.: + + class A < stc::none = + { + // my_type is abstract. + vtype my_type = 0; + } + class B < A = + { + vtype my_type = int; + } +*) +let a = Scoop_Class { super = Stc_None; + vtypes = create_vtypes ["my_type", Stc_Abstract] } in +let b = Scoop_Class { super = a; + vtypes = create_vtypes ["my_type", Std_Int] } in +assert (find b "my_type" = Std_Int);; + +(* - A concrete virtual type cannot be redefined as abstract. + + Ex.: + + class A < stc::none = + { + vtype my_type = int; + } + // Invalid. + class B < A = + { + vtype my_type = 0; + } +*) +let a = Scoop_Class { super = Stc_None; + vtypes = create_vtypes ["my_type", Std_Int] } in +let b = Scoop_Class { super = a; + vtypes = create_vtypes ["my_type", Stc_Abstract] } in + try + ignore (find b "my_type") + with Scoop_exception "VT redefined abstract." -> () +;; + + +(* ** Final virtual type + + - A virtual type can be tagged as final. + + Ex.: + + class A < stc::none = + { + final vtype my_type = int; + } +*) +let a = Scoop_Class { super = Stc_None; + vtypes = create_vtypes ["my_type", Stc_Final Std_Int] } +in +assert (find a "my_type" = Std_Int);; + +(* - A virtual type tagged as final in a class cannot be redefined in its + subclasses, either tagged final or not, even if its value is + unchanged. + + Ex.: + + class A < stc::none = + { + final vtype my_type = int; + } + // Invalid. + class B < A = + { + vtype my_type = float; + } + // Invalid. + class C < A = + { + vtype my_type = int; + } + // Invalid. + class D < A = + { + final vtype my_type = int; + } + // Invalid. + class E < A = + { + final vtype my_type = float; + } +*) +let a = Scoop_Class + { super = Stc_None; + vtypes = create_vtypes ["my_type", Stc_Final Std_Int] } in +let b = Scoop_Class + { super = a; + vtypes = create_vtypes ["my_type", Std_Float] } in +let c = Scoop_Class + { super = a; + vtypes = create_vtypes ["my_type", Std_Int] } in +let d = Scoop_Class + { super = a; + vtypes = create_vtypes ["my_type", Stc_Final Std_Int] } in +let e = Scoop_Class + { super = a; + vtypes = create_vtypes ["my_type", Stc_Final Std_Float] } in + + assert (find a "my_type" = Std_Int); + try ignore (find b "my_type") + with Scoop_exception "Final VT redefined." -> (); + try ignore (find c "my_type") + with Scoop_exception "Final VT redefined." -> (); + try ignore (find d "my_type") + with Scoop_exception "Final VT redefined final." -> (); + try ignore (find e "my_type") + with Scoop_exception "Final VT redefined final." -> (); +;; + +(* ** General virtual type lookup + + *** Abstract + + class A < stc::none + { + // my_vtype not defined. + } + + class D < stc::none + { + vtype my_type = 0; + } + + // A + // ^ + // | + // C<>--D + class C < stc::none + { + vtype delegatee_type = D; + } + + // FIXME: What should be the value of ``t''? + // I would say ``stc::not_found'', but I'm not sure (see intro.txt, too). + type t = C#my_type; +*) +let a = Scoop_Class + { super = Stc_None; + vtypes = create_vtypes [] } in +let d = Scoop_Class + { super = Stc_None; + vtypes = create_vtypes ["my_type", Stc_Abstract] } in +let c = Scoop_Class + { super = a; + vtypes = create_vtypes ["delegatee_type", d] } in +assert (find c "my_type" = Stc_Not_found);; + + +(* More examples. + + ** A complex example, with stc::not_delegated. + + A + ^ + | X + B ^ + ^ | + | Y + C<>-� + ^ + | + D + ^ + | + E + + + class A < stc::none | class C < B + { | { + } | vtype delegatee_type = Y; + class B < A | vtype foo = int; + { | vtype baz = not_delegated; + vtype foo = 0; | vtype hop = not_delegated; + } | } + | class D < C + class X < stc::none | { + { | vtype quux = unsigned; + vtype bar = 0; | } + vtype hop = int; | class E < D + } | { + class Y < X | vtype baz = float; + { | } + vtype baz = short; | + vtype bar = char; | + } | +*) +let a = Scoop_Class + { super = Stc_None; + vtypes = create_vtypes [] } in +let b = Scoop_Class + { super = a; + vtypes = create_vtypes ["foo", Stc_Abstract] } in + +let x = Scoop_Class + { super = Stc_None; + vtypes = create_vtypes [("bar", Stc_Abstract); + ("hop", Std_Int)] } in +let y = Scoop_Class + { super = x; + vtypes = create_vtypes [("bar", Std_Char); + ("baz", Std_Short)] } in + +let c = Scoop_Class + { super = b; + vtypes = create_vtypes [("delegatee_type", y); + ("foo", Std_Int); + ("baz", Stc_Not_delegated); + ("hop", Stc_Not_delegated)] } in +let d = Scoop_Class + { super = c; + vtypes = create_vtypes [("quux", Std_Unsigned)] } in +let e = Scoop_Class + { super = d; + vtypes = create_vtypes [("baz", Std_Float)] } in + +assert (find e "foo" = Std_Int); +assert (find e "bar" = Std_Char); +assert (find e "baz" = Std_Float); +assert (find e "quux" = Std_Unsigned); +assert (find e "hop" = Stc_Not_found); +;; + + +(* *** abstract redefined with tag stc::not_delegated. + + class A < stc::none | + { | + vtype foo = 0 | + } | + class B < A | class X < stc::none + { | { + vtype delegatee_type = X; | vtype foo = int; + vtype foo = stc::not_delegated | } + } | + class C < B | + { | + } | +*) +let a = Scoop_Class + { super = Stc_None; + vtypes = create_vtypes ["foo", Stc_Abstract] } in + +let x = Scoop_Class + { super = Stc_None; + vtypes = create_vtypes ["foo", Std_Int] } in + +let b = Scoop_Class + { super = a; + vtypes = create_vtypes [("delegatee_type", x); + ("foo", Stc_Not_delegated)] } in +let c = Scoop_Class + { super = b; + vtypes = create_vtypes [] } in + +(* foo is abstract and tagged ``not delegated'' for B. *) +try ignore (find b "foo") with Scoop_exception "find: VT is abstract." -> (); +(* Likewise for C. *) +try ignore (find c "foo") with Scoop_exception "find: VT is abstract." -> () +;; + + +(* *** abstract redefined with tag stc::not_delegated. + + This is the converse situation from the previous example (foo is + declared abstract in C instead of A). + + class A < stc::none | + { | + } | + class B < A | class X < stc::none + { | { + vtype delegatee_type = X; | vtype foo = int; + vtype foo = stc::not_delegated | } + } | + class C < B | + { | + vtype foo = 0 | + } | +*) +let a = Scoop_Class + { super = Stc_None; + vtypes = create_vtypes [] } in + +let x = Scoop_Class + { super = Stc_None; + vtypes = create_vtypes ["foo", Std_Int] } in + +let b = Scoop_Class + { super = a; + vtypes = create_vtypes [("delegatee_type", x); + ("foo", Stc_Not_delegated)] } in +let c = Scoop_Class + { super = b; + vtypes = create_vtypes ["foo", Stc_Abstract] } in + +(* foo is abstract and tagged ``not delegated'' for B. *) +assert (find b "foo" = Stc_Not_found); +(* Likewise for C. *) +try ignore (find c "foo") with Scoop_exception "find: VT is abstract." -> () +;; Index: doc/algorithms.txt --- doc/algorithms.txt (revision 0) +++ doc/algorithms.txt (revision 0) @@ -0,0 +1,271 @@ +SCOOP 2 - algorithms -*- outline -*- + +These algorithms are expressed in a pseudo-Caml like syntax. + +=========================================================================== +* Bottom-up approach (not finished) + +This implementation doesn't handle stc::not_delegated properly. + +** find_local + +fun find_local (source, target) = + mlc::get_typedef (source, target) + +(get_typedef is a routine from Metalic.) + + +** find + +// FIXME: Handle final. + +fun find (source, target) = + if (source == stc::none) + error ("find: cannot perform lookup on stc::none.") // FIXME: Detail. + else + let local_type = find_local (source, target) in + let delegatee_type = find_local (source, 'delegatee_type') in + + match local_type with + + | stc::abstract -> error ("find: abstract virtual type in leaf class.") + + | stc::no_delegation -> + // Look only in the inheritance branch only. + find_rec (source#super, target) + + | mlc::not_found -> + if (delegatee_type = mlc::not_found) + // Look only in the inheritance branch only. + find_rec (source#super, target) + else + let inheritance_branch_res = find_rec (source#super, target) in + let delegation_branch_res = find_rec (delegatee_type, target) in + merge (inheritance_branch_res, delegation_branch_res) + + | T -> T + + +** find_rec0 + +(Previous version of find_rec.) + +fun find_rec0 (source, target, is_abstract = false) = + let local_type = find_local (source, target) in + + match local_type, source#super, is_abstract with + + | stc::not_delegated, _ , _ -> + error ("find_rec: stc::delegation found in non-leaf class.") + + | mlc::not_found, mlc::none, _ -> stc::not_found + | mlc::not_found, S , _ -> find_rec (S, target, is_abstract) + + | stc::abstract, mlc::none, _ -> stc::abstract + | stc::abstract, S , _ -> find_rec (S, target, true) + + // Final<T> is handled like T (the checks are performed elsewhere). + | stc::final<T>, _, false -> T + | stc::final<T>, _, true -> + error ("find_rec: virtual type redefined abstract.") + + | T, _, false -> T + | T, _, true -> + error ("find_rec: virtual type redefined abstract.") + + +** find_rec + +FIXME: Improve the automaton of the states (abstract, defined, final, +etc.) + +fun find_rec (source, target, res = stc::not_found) = + if (source = mlc::none) + res + else + let local_type = find_local (source, target) in + + match local_type, res with + + | stc::not_delegated, _ -> + error ("find_rec: stc::delegation found in non-leaf class.") + + | mlc::not_found, _ -> find_rec (source#super, target, res) + + // The values below cannot be used to redefine a *final* virtual type. + + | stc::abstract, _ -> find_rec (source#super, target, stc::abstract) + + | T, _ -> T + match res with + | stc::not_found -> find_rec (source#super, target, T) + | stc::abstract -> + // FIXME: Detail + error ("find_rec: virtual type redefined as abstract.") + | _ -> find_rec (source#super, target, T) + + // stc::final<T> is handled like T, with additional checks. + | stc::final<T>, _ -> + match res with + | stc::not_found -> find_rec (source#super, target, T) + | stc::abstract -> + // FIXME: Detail + error ("find_rec: final virtual type redefined as abstract.") + | _ -> error ("find_rec: final virtual type redefined.") + + +FIXME: Write another version where the search is performed top-down +(in both branches). Handling the lookup this way seems to ease the +writing of states and automata. + +** merge + +fun merge (inheritance_branch_res delegation_branch_res) = + match (inheritance_branch_res, delegation_branch_res) + | stc::not_found, stc::not_found -> stc::not_found + | stc::not_found, stc::abstract -> stc::not_found + | stc::not_found, U -> U + + | stc::abstract, stc::not_found -> error () // FIXME: Detail. + | stc::abstract, stc::abstract -> error () // FIXME: Detail. + | stc::abstract, U -> U + + | T, _ -> T + + +Notes: + +- syntax: foo#super returns the type of the super class of foo. + +- syntax: 'foo_type' stands for the SCOOP virtual type named foo_type. + +- stc::none#super is an error, so calling `find (none, ...)' might be + an error ! + + +=========================================================================== +* Top-down approach + + +** find + +FIXME: To be written from algorithms.ml. + +** find_rec + +function find_rec (source, target) = + if (source = mlc::none) + stc::not_found + else + let local_res = find_local (source, target) in + + let super_res = find_rec (source#super, target) in + // FIXME: This might not be efficient, since find_rec can be + // called several times on the nodes of the delegation branch when + // going down the inheritance branch. Of course, the declarative + // nature of C++ templates will avoid this cost, but it remains + // inelegant, IMHO. + + let delegatee = find_rec_in_supers (source, 'delegatee_type') in + let delegatee_res = + if (delegatee = stc::not_found) + stc::not_found + else + find_rec (delegatee, target) in + + merge3 (local_res, super_res, delegatee_res) + + +// Like find_rec, but only search in the inheritance branch. +function find_rec_in_supers (source, target) = + if (source = mlc::none) + stc::not_found + else + let local_res = find_local (source, target) in + let super_res = find_rec (source#super, target) in + merge2 (local_res, super_res) + + +merge2 (local_res, super_res) = + match local_res, super_res with + + | stc::abstract, stc::not_found -> stc::abstract + | mlc::not_found, stc::not_found -> stc::not_found + | T, stc::not_found -> T + | stc::final<T>, stc::not_found -> stc::final<T> + + | mlc::not_found, stc::abstract -> stc::not_found + | stc::abstract, stc::abstract -> stc::abstract + | T, stc::abstract -> T + | stc::final<T>, stc::abstract -> stc::final<T> + + | stc::abstract, U -> error ("VT redefined abstract.") + | mlc::not_found, U -> U + | T, U -> T + | stc::final<T>, U -> stc::final<T> + + | stc::abstract, stc::final<U> -> error ("Final VT redefined abstract") + | mlc::not_found, stc::final<U> -> stc::final<U> + | T, stc::final<U> -> error ("Final VT redefined.") + | stc::final<T>, stc::final<U> -> error ("Final VT redefined final.") + + +merge3 (local_res, super_res, delegatee_res) = + match local_res, super_res, delegatee_res with + + // local_res == stc::not_found. + | mlc::not_found, stc::not_found, stc::not_found -> stc::not_found + | mlc::not_found, stc::not_found, stc::abstract -> stc::not_found + | mlc::not_found, stc::not_found, stc::final<V> -> stc::final<V> + | mlc::not_found, stc::not_found, V -> V + + | mlc::not_found, stc::abstract, stc::not_found -> stc::not_found + | mlc::not_found, stc::abstract, stc::abstract -> stc::abstract + | mlc::not_found, stc::abstract, stc::final<V> -> stc::final<V> + | mlc::not_found, stc::abstract, V -> V + + | mlc::not_found, stc::final<U>, _ -> stc::final<U> + | mlc::not_found, U, _ -> U + + + // local_res == stc::not_abstract. + | stc::abstract, stc::not_found, stc::not_found -> stc::abstract + | stc::abstract, stc::not_found, stc::abstract -> stc::abstract + | stc::abstract, stc::not_found, stc::final<V> -> stc::final<V> + | stc::abstract, stc::not_found, V -> V + + | stc::abstract, stc::abstract, stc::not_found -> stc::abstract + | stc::abstract, stc::abstract, stc::abstract -> stc::abstract + | stc::abstract, stc::abstract, stc::final<V> -> stc::final<V> + | stc::abstract, stc::abstract, V -> V + + | stc::abstract, stc::not_delegated_abstract, _ -> stc::not_delegated_abstract + | stc::abstract, stc::not_delegated, _ -> stc::not_delegated_abstract + + | stc::abstract, stc::final<U>, _ -> error ("Final VT " + "redefined abstract") + | stc::abstract, U, _ -> error ("VT redefined " + "abstract.") + // local_res == stc::not_delegated. + | stc::not_delegated, stc::not_found, _ -> stc::not_delegated + | stc::not_delegated, stc::abstract, _ -> stc::not_delegated_abstract + | stc::not_delegated, stc::not_delegated_abstract, _ -> stc::not_delegated_abstract + + // local_res == stc::not_delegated_abstract. + /* FIXME: Shouldn't we introduce a means to tag a vtype both + as abstract *and* not delegated? (Currently, the rule below + prevents this). */ + | stc::not_delegated_abstract, _, _ -> error ("Local " + "declaration of " + "not delegated " + "and abstract") + + // local_res == stc::final<T>. + | stc::final<T>, stc::final<U>, _ -> error ("Final VT " + "redefined final.") + | stc::final<T>, _, _ -> stc::final<T> + + // local_res == T. + | T, stc::final<U>, _ -> error ("Final VT " + "redefined.") + | T, _, _ -> T Index: doc/rules.txt --- doc/rules.txt (revision 0) +++ doc/rules.txt (revision 0) @@ -0,0 +1,514 @@ +SCOOP 2 -- rules -*- outline -*- + + +* Keywords + +- Keywords added to the language (both SCOOL or C++): + + delegatee_type (FIXME: or stc_delegatee_type?) + abstract (syntax: ``= 0'') + final (syntax: ``final vtype ...'') + stc::not_found (note: different from mlc::not_found) + stc::not_delegated + + stc::not_delegated_abstract (private type, used internally -- + cannot be used by the programmer). + + stc::none (FIXME: What about stc::top ?) + + deferred_type? (FIXME: Which syntax?) + + +* Declaration/definition + +** Class definition + +- A class has almost the same meaning as in C++: an entity gathering + data and operations. C++ (as well as SCOOL) also allows classes to + define types (via typedefs); this ability is part of SCOOP, and is + extended to the notion of virtual types (see the relevant item). + + Ex.: + + class A < stc::none = + { + // A variable. + var pi : float = 3.14; + // A function. + fun sqr : (a : int) -> int + => a * a; + // A (classical) type. + type t = int + // A virtual type. + vtype vt = float; + } + + In the present document, we will mainly deal with virtual type. + +- A class must inherit from another class. When a class has + semantically no superclass, its superclass must be set to stc::none. + A class having no supertype is invalid. + + Ex.: + + // Valid (assuming S is a valid class). + class A < S = + { + // ... + } + + Ex.: + + // Valid. + class A < stc::none = + { + // ... + } + + Ex.: + + // Invalid. + class A = + { + // ... + } + +** Virtual type definition + +- Each class can provide zero, one or more virtual type(s). + + // FIXME: Validity of the definition? What can the user put in RHS? + // What about deferred type? + + Ex.: + + class A < stc::none = + { + vtype my_type = int; + } + + +** Virtual type re-definition + +- Unless declared final (see relevant item), a virtual type of a class + can be redefined in its subclass(es). The new value can be the same + or different for the inital one. The syntax is the same as the one + for defining a virtual type. + + Ex.: + + class A < stc::none = + { + vtype my_type = int; + } + // Valid. + class B < A = + { + vtype my_type = float; + } + // Valid. + class C < A = + { + vtype my_type = int; + } + +FIXME: Restrictions on computed values? (-> deferred vtypes, etc.) + +** Virtual type abstract declaration (i.e., deferred definition) + +- The definition of a virtual type can be deferred, i.e. a virtual + type can be just /declared/. Such a virtual type is said to be + abstract. A non-abstract virtual type is said to be concrete. + + A class containing at least an abstract virtual type + (resp. containing no virtual type) is said abstract + (resp. concrete). + + Ex.: + + class A < stc::none = + { + // my_type is abstract. + vtype my_type = 0; + } + class B < A = + { + vtype my_type = int; + } + +- A concrete virtual type cannot be redefined as abstract. + + Ex.: + + class A < stc::none = + { + vtype my_type = int; + } + // Invalid. + class B < A = + { + vtype my_type = 0; + } + + +** Final virtual type + +- A virtual type can be tagged as final. + + Ex.: + + class A < stc::none = + { + final vtype my_type = int; + } + +- A virtual type tagged as final in a class cannot be redefined in its + subclasses, either tagged final or not, even if its value is + unchanged. + + Ex.: + + class A < stc::none = + { + final vtype my_type = int; + } + // Invalid. + class B < A = + { + vtype my_type = float; + } + // Invalid. + class C < A = + { + vtype my_type = int; + } + // Invalid. + class D < A = + { + final vtype my_type = int; + } + // Invalid. + class E < A = + { + final vtype my_type = float; + } + +- A final type cannot be abstract. + + Ex.: + + // Invalid. + class A < stc::none = + { + final vtype my_type = 0; + } + +FIXME: Is that all concerning abstract and final? + + +** Delegation + +As stated before, any class has a super class in the SCOOP paradigm. +SCOOP also allows a class to have a /delegatee/, i.e., a type it can +use or depend on -- but without fulfilling the ``IS A'' relationship. + +- There is at most one delegatee (having a delegatee is not + mandatory). + +- Delegation is introduced thanks to a special virtual type, + delegatee_type (see below). + +*** Delegatee type + +- The virtual type `delegatee_type' is special: it is not looked up like + the other virtual types (see the lookup section). + + class D < stc::none = + { + } + class A < stc::none = + { + vtype delegatee_type = D; + } + +- A delagatee_type virtual type can be abstract in a class, and given + a concrete definition in a subclass. As for other virtual types, + the fact that it is abstract renders the class abstract. + + Ex.: + + class D < stc::none = + { + } + class A < stc::none = + { + // Deferred definition of delagatee_type. + vtype delegatee_type = 0; + } + class B < A = + { + vtype delegatee_type = D; + } + +- If its no abstract, the value of a delegatee_type virtual type must + be a (SCOOP) class name. + + class A < stc::none = + { + // Invalid. + vtype delegatee_type = int; + } + +- The virtual type `delegatee_type' cannot be tagged as final. + However, if its is actually defined (not just declared) in a class, + the delegatee_type virtual type cannot be subsequently redefined in + any of its subclasses, either with the same value or with another + one. + + + Ex.: + + class D1 < stc::none = + { + } + class D2 < stc::none = + { + } + class A < stc::none = + { + vtype delegatee_type = D1; + } + class B < A = + { + // Invalid. + vtype delegatee_type = D1; + } + class C < A = + { + // Invalid. + vtype delegatee_type = D2; + } + +FIXME: Continue. + + +* Lookup + +The process of retrieving a virtual type given a class (``source'') +and a type name (``target'') is call ``virtual type lookup''. We'll +use a has (or pound) symbol (#) to a virtual type lookup. + + Ex.: + + class A < stc::none = + { + vtype foo = int; + } + + // t contains the value of the virtual type foo from class A. + type t = A#foo; + +** Local lookup + +Recall: The lookup process is recursive: it starts from a class (a +priori concrete). + +This process relies on an `atomic' lookup on each inspected class: +each of them can be queried for a locally defined virtual type. +(FIXME: reference to the local_find algorithm.) + +The result of this local lookup is +- mlc::not_found: meaning there is no delegatee_type; +- another C++ type: this is then the result of the lookup; +- a compile-time error (mlc::assert or mlc::abort), meaning that + something is either wrong in the virtual type definitions or in the + query. + + +** General virtual type lookup + +When looking for a virtual type from a class, the answer can come from +- the class itself, if it directly defines the virtual type; +- one of its super classes (``the inheritance branch''); +- if applicable, its delegatee, or one of its super classes (``the + delegation branch''). + + +So, the lookup is performed in a single or a double (if there is a +delegatee) recursive search up from the class in the inheritance and +the delegation branch (if applicable). + + +Teh first step in the lookup is to find whether a local definition of +the virtual type (i.e., within the ``source'' class) exists. (See item +``Local lookup''). If so, it is returned. + +If (FIXME: Finish this sentence.) + + +FIXME: Do we want to perform the checks of the inheritance and +delegation branch (in that event). + +Then, a delegatee_type is looked for. The result of this search can +be either +- stc::not_found: meaning there is no delegatee_type; +- another C++ type: this is then the result of the lookup; +- a compile-time error (mlc::assert or mlc::abort), meaning that + something is either wrong in the virtual type definitions or in the + query. + +Note: the general lookup procedure (either for delegatee_type or any +other other virtual type) return stc::not_found when it fails to find +the target virtual type, whereas the local lookup return +mlc::not_found. + + + + +FIXME: Continue. + +*** stc::not_delegated + +Cannot appear in a class of the delegation branch (aside from the +junction class). + +*** Abstract + +[...] + +stc::abstract in a delegation branch: + + class A < stc::none + { + // my_vtype not defined. + } + + class D < stc::none + { + vtype my_type = 0; + } + + // A + // ^ + // | + // C<>--D + class C < stc::none + { + vtype delegatee_type = D; + } + + // Gives stc::not_found. + type t = C#my_type; + + +** delagatee_type lookup + +The lookup of delegatee_type is different from the lookup of other +virtual types. While other virtual types are searched for in both the +inheritance and the delegation branch, delegatee_type is only seeked +in the inheritance branch (for infinite recursion reasons). + +FIXME: Continue. + + +*** Abstract + +FIXME: Continue. + +* Examples + + +** A complex example + + A + ^ + | X + B ^ + ^ | + | Y + C<>-� + ^ + | + D + ^ + | + E + + class A < stc::none + { + } + class B < A + { + vtype foo = 0; + } + + class X < stc::none + { + vtype bar = 0; + vtype hop = int; + } + class Y < X + { + vtype bar = char; + vtype baz = short; + } + + class C < B + { + vtype delegatee_type = Y; + vtype foo = int; + vtype baz = not_delegated; + vtype hop = not_delegated; + } + class D < C + { + vtype quux = unsigned; + } + class E < D + { + vtype baz = float; + } + +*** E#bar + + A local_find(A, bar) = mlc::not_found + ^ + | + | X local_find(X, bar) = 0 + | ^ + | | + B | local_find(B, bar) = mlc::not_found + ^ | + | | + | Y local_find(Y, bar) = char + | | + | | + C<>-� local_find(D, bar) = mlc::not_found + ^ + | + D local_find(D, bar) = mlc::not_found + ^ + | + E local_find(E, bar) = mlc::not_found + +*** E#hop + + A local_find(A, bar) = mlc::not_found + ^ + | X + B ^ local_find(B, bar) = mlc::not_found + ^ | + | Y + C<>-� local_find(D, bar) = stc::not_delegated + ^ + | + D local_find(D, hop) = mlc::not_found + ^ + | + E local_find(E, hop) = mlc::not_found + + + +Local Variables: +ispell-local-dictionary: "american" +End: Index: doc/intro.txt --- doc/intro.txt (revision 0) +++ doc/intro.txt (revision 0) @@ -0,0 +1,292 @@ +Static - Equipment for Static Hierarchies and SCOOP 2 -*- outline -*- + +This a very rough, buggy and incomplete draft of explanations on +SCOOP 2. To be improved, fixed, and completed! + + +* On virtual types + +A description of the mechanism of virtual types in SCOOP 2. + +** Rules + +A virtual type is like a typedef in a class scope, with added +possibilities. Like a method (in C++), +- it can be abstract (i.e., only declared, with a postponed + definition, to be given in a concrete subclass); +- it can be altered; +- it is resolved (looked up for) bottom-up. + +SCOOP 2 describes a virtual type pattern where virtual types are +declared and (re-)defined across a class hierarchy (thanks to the +``super'' relationship), but also across a (single) delegation +relationship. + +*** Virtual type name declaration + +The SCOOPed namespace must be equipped for every virtual type name. + +*** Class virtual types. + +- Each class can define any number of virtual types. Some of them + have a special meaning (see below): + + - delegatee_type + - (supertype ?) + + Some ``values'' (i.e., type assigned to the typedef standing for a + vtype) have a special meaning (see below): + + - stc::abstract + - stc::final<T> + - stc::not_found + - stc::not_delegated + +*** Single inheritance + +**** Class definition + A + ^ + | + B + +- A class *must* declare another class as being its superclass. When A + is a superclass of B, B is said to be a direct subclass or direct + derived class of A. Every subclass of B an (indirect) subclass or + (indirect) derived class of A. + + Ex.: + + A < B + { + // ... + } + + When a class has semantically no superclass, its superclass must + be set to stc::none. A class having no supertype is invalid. + + Ex.: + + // Valid. + A < stc::none + { + // ... + } + + // Invalid. + A + { + // ... + } + +- A virtual defined as stc::final<T> in a class cannot be redefined + in any of its derived class(es). + +- A (non final) virtual type defined in a class can be redefined in any + of its subclasses. + +- A vtype can be /declared/ as stc::abstract. Such a definition is + actually a making it a virtual declaration, meaning that an actual + type definition is required in a concrete subclass of the class + where this vtype was declared abstract, for this subclass to be + instantiable. + + To put it in a nutshell: a valid virtual type cannot resolve as + stc::abstract. + +**** Virtual type look-up + +- The process of resolving a vtype involves a source (a class) and a + vtype (a typedef). If both the structures involved and the request + are valid, the result of this operation is + + - a typedef, if the resolution succeeded; + - mlc::not_found. + + Note that a source must be a *concrete* class. + +FIXME: Describe how the look-up works here. + +- A virtual type can resolve as mlc::not_found, if the queried class + doesn't have a value for this vtype (cf. supra). + +*** Single inheritance + single Delegation + + A + ^ + | + C<>--D + +- A class can have a special vtype named `delegatee_type', whose value + refers to another class name. The latter class will be a delegation + of the former class. + +- Prone to discussion: + The `delegatee_type' vtype is not looked up like other vtypes, + instead, only the considered concrete class is queried -- no + superclass is involved in this process. + + Note: in Th�o's implementation of stc/scoop.hh (revision 712 in + the Olena repository), the `delegatee_type' vtype *is* looked up + throughout the super classes of the `from' class. Obviously, this + look-up doesn't occur not in the delegation branch! + +- The rules of the vtype look-up are affected by the presence of a + delegation. The default global rule is: unless defined in the + current class, a vtype if looked in the superclass branch first, then + in the delegation branch. + +FIXME: False. +- The look-up w.r.t. stc::final<T> remains the same, but is performed + in the supertype branch and the delegation branch (if applicable). + +- When the vtype is defined in the class where it is looked for, + this value is returned. + + Exception: if this typedef has value stc::not_delegated, the result + of the look-up is the same as if there was + - no delegation, + - no definition for this vtype in the considered class, + i.e., the result is computed from the superclass branch *only*. + + + When the vtype if not defined in the class, the look-up is done in + parallel, in the superclass branch and in the delegation branch. If + no error has arisen during theses (internal) look-ups, two typedefs + are returned (one for each branch). The final result of the overall + look-up is the result of a merge of the two typedefs, whose rules are + given by the following table. + +FIXME: For Olena 1.0, we'll consider that a vtype in the delegation +branch cannot be stc::abstract. + + +------------------------------+-----------------------------------------+ + | | result of the delegation branch | + | +----------------+----------------+-------+ + | | | stc::abstract | | + | | stc::not_found | (error must | U [2] | + | | | not occur [1]) | | + +-------------+----------------+----------------+----------------+-------+ + | result of | stc::not_found | stc::not_found | stc::not_found | U | + | the look-up +----------------+----------------+----------------+-------+ + | in the | stc::abstract | error | error | U | + | superclass +----------------+----------------+----------------+-------+ + | branch | T [2] | T | T | T | + +-------------+----------------+----------------+----------------+-------+ + + Notes: + [1] The main idea being: delegation is additional material. Note + that we could have chosen the other convention + + FIXME: Should there be error when the inheritance branch + answers stc::not_found and the delegation branch answers + stc::abstract? + + [2] T and U are two types different from stc::not_found and + stc::abstract. + + +* A bit of formalism + +** Types and algorithms signatures + +*** Built-in values + +cxx_type_name // any valid C++ type +cxx_class_name :: cxx_type_name // a C++ class/struct + +*** SCOOP2 values + +vtype_name :: cxx_type_name +scooped_class_name :: cxx_class_name + + +find :: scooped_class_name, vtype_name -> cxx_type_name + + + + + +--------------------------------------------------------------------------- +* Open questions on this document, things to do, etc. + +In all these questions, we assume that A is a superclass of B. +Let A be a superclass of B. + +- Can a vtype defined in A as concrete, be redefined in B as + stc::abstract? (at least not for Olena 1.0). + +- Can a virtual defined as stc::final<T> in a class A cannot be + ``redefined'' as stc::final<T> (i.e., the exact same type) in a + derived classed B? (No.) + +- Can a virtual type be assigned the type stc::not_found? + +- Is there a `exact_type' vtype? If so, does it have to be present in + every class? + + +** Lookup Strategies + +*** Bottom-up, with fork at junction and merge of both results. +Current strategy, half-designed in algorithm.txt. + +*** Top-down from each top class, with merge at junction. +To be tried/written. + + +*** Linear top-down (?) +The walk in the delegation branch is performed between the upper part +(above the junction) and the lower part (below the junction). + +*** Linear bottom-up (?) +The walk in the delegation branch is performed between the lower +part (below the junction) and the upper part (above the junction). + +*** Anything else (?) + + + +** Rule enforcement (virtual types checking) + +*** Ensuring the vtype name is known (i.e., declared in the SCOOPed namespace + +*** Existence of a superclass + +*** Absence/uniqueness of a delegation + +*** Checking Final vtypes + +(In both branches, if applicable.) + +*** Ensuring that the vtype is not abstract + + +** Check algorithm + +// FIXME: To do. + +** Look-up algorithm + + /** Virtual type look-up. + + \a source is the (concrete) class from which the look-up is performed + \a target is the name of the virtual type looked for (without + the `_type' suffix). */ + find :: scooped_class, + find(source, target) + + // FIXME: Write algorithm. + +--------------------------------------------------------------------------- + + + + + +Local Variables: +ispell-local-dictionary: "american" +End: + + LocalWords: typedef SCOOPed namespace delegatee supertype vtype superclass + LocalWords: instantiable vtypes Th�o's stc typedefs ispell american Index: doc/scool.txt --- doc/scool.txt (revision 0) +++ doc/scool.txt (revision 0) @@ -0,0 +1,12 @@ +SCOOL -- summary and extensions -*- outline -*- + + +This document doesn't describe the whole SCOOL language; see + + https://trac.lrde.org/olena/trac.cgi/wiki/SCOOL + +for a detail documentation on the language. Instead, we'll mention +only the traits needed to explain the novelties of SCOOP 2, both +current elements of SCOOL and extensions. + +... \ No newline at end of file Index: doc/README --- doc/README (revision 0) +++ doc/README (revision 0) @@ -0,0 +1,20 @@ +Static - Equipment for Static Hierarchies and SCOOP 2 -*- outline -*- + +(This a rough, buggy and incomplete draft of explanations on SCOOP 2. +To be improved, fixed, and completed!) + + +intro.txt General explanations on SCOOP 2 +scool.txt Short introduction to SCOOL and its extensions +rules.txt More formal rules on SCOOP 2 +algorithms.txt Algorithms used in the SCOOP paradigm. +algorithms.ml Likewise, written in Objective Caml. +static.txt ? +... + + + +Local Variables: +ispell-local-dictionary: "american" +End: + Index: stc/scoop.hh --- stc/scoop.hh (revision 714) +++ stc/scoop.hh (working copy) @@ -81,7 +81,7 @@ /* FIXME: nothing here! \ * \ * mlc::none is not a default value \ - * so that the client should define stoppers \ + * so that the client has to define stoppers \ */ \ }; \ \ @@ -226,7 +226,7 @@ }; \ \ template <typename res1, typename res2> \ - struct helper_get_stm \ + struct helper_get_stm /* FIXME: Insert mlc::abort_<> statement here? */ \ { \ /* error */ \ }; \ @@ -246,6 +246,10 @@ \ \ \ + /* -------------------- */ \ + /* Checking algorithm. */ \ + /* -------------------- */ \ + \ /* \ * check_no_final_inherited \ * \ @@ -459,6 +463,9 @@ \ \ \ + /* ------------------- */ \ + /* Look-up algorithm. */ \ + /* ------------------- */ \ \ /* \ * first_stm(from, target) \