Changeset 343c8be for doc/theses/jiada_liang_MMath/relatedwork.tex

Timestamp:

Jun 25, 2024, 9:26:16 PM (4 months ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

master

Children:

d5efcb7

Parents:

089b39e1 (diff), d96d4f0 (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:software/cfa/cfa-cc

File:

• doc/theses/jiada_liang_MMath/relatedwork.tex (modified) (7 diffs)

doc/theses/jiada_liang_MMath/relatedwork.tex

@@ -21 +21 @@
 Among theses languages, there are a large set of overlapping features, but each language has its own unique extensions and restrictions.
 
+
 \section{Pascal}
 \label{s:Pascal}
 
-Classic Pascal introduced the \lstinline[language=Pascal]{const} aliasing declaration binding a name to a constant literal/expression.
+Pascal introduced the \lstinline[language=Pascal]{const} aliasing declaration binding a name to a constant literal/expression.
 \begin{pascal}
-const one = 0 + 1;   Vowels = set of (A,E,I,O,U);   NULL = NIL;
-                 PI = 3.14159;   Plus = '+';   Fred = 'Fred';
+const Three = 2 + 1;   NULL = NIL;   PI = 3.14159;   Plus = '+';   Fred = 'Fred';
 \end{pascal}
 As stated, this mechanism is not an enumeration because there is no specific type (pseudo enumeration).
-Hence, there is no notion of a (possibly ordered) set, modulo the \lstinline[language=pascal]{set of} type.
+Hence, there is no notion of a (possibly ordered) set.
 The type of each constant name (enumerator) is inferred from the constant-expression type.
 
-Free Pascal~\cite[\S~3.1.1]{FreePascal} is a modern, object-oriented version of classic Pascal, with a C-style enumeration type.
-Enumerators must be assigned in ascending numerical order with a constant expression and the range can be non-consecutive.
+Pascal introduced the enumeration type characterized by a set of ordered, unscoped identifiers (enumerators), which are not overloadable.\footnote{%
+Pascal is \emph{case-insensitive} so identifiers may appear in multiple forms and still be the same, \eg \lstinline{Mon}, \lstinline{moN}, and \lstinline{MON} (a questionable design decision).}
 \begin{pascal}
-Type EnumType = ( one, two, three, forty @= 40@, fortyone );
+type Week = ( Mon, Tue, Wed, Thu, Fri, Sat, Sun );
 \end{pascal}
-Pseudo-functions @Pred@ and @Succ@ can only be used if the range is consecutive.
+Object initialization and assignment are restricted to the enumerators of this type.
+Enumerators are auto-initialized from left to right, starting at zero, incrementing by 1.
+Enumerators \emph{cannot} be explicitly initialized.
+Pascal provides a predefined type \lstinline[language=Pascal]{Boolean} defined as:
+\begin{pascal}
+type Boolean = ( false, true );
+\end{pascal}
+The enumeration ordering supports the relational operators @=@, @<>@, @<@, @<=@, @>=@, and @>@, provided both operands are the same (sub)type.
+
+The following auto-generated pseudo-functions exist for all enumeration types:
+\begin{cquote}
+\begin{tabular}{@{}ll@{}}
+@succ( T )@     & @succ( Tue ) = Wed@ \\
+@pred( T )@     & @pred( Tue ) =  Mon@ \\
+@ord( T )@      & @ord( Tue ) = 1@
+\end{tabular}
+\end{cquote}
+
+Pascal provides \emph{consecutive} subtyping of an enumeration using subrange type.
+\begin{pascal}
+type Week = ( Mon, Tue, Wed, Thu, Fri, Sat, Sun );
+                                Weekday = @Mon..Fri@;
+                                Weekend = @Sat..Sun@;
+var day : Week;
+          wday : Weekday;
+          wend : Weekend;
+\end{pascal}
+Hence, the ordering of the enumerators is crucial to provide the necessary ranges.
+There is bidirectional assignment between the enumeration and its subranges.
+\begin{pascal}
+day := Sat;
+@wday := day;@                  $\C[1.5in]{\{ check \}}$
+wend := day;                    $\C{\{ maybe check \}}$
+day := Mon;
+wday := day;                    $\C{\{ maybe check \}}$
+@wend := day;@                  $\C{\{ check \}}$
+day := wday;                    $\C{\{ no check \}}$
+day := wend;                    $\C{\{ no check \}}\CRT$
+\end{pascal}
+There should be a static/dynamic range check to verify values assigned to subtypes.
+(Free Pascal does not check and aborts in certain situations, like writing an invalid enumerator.)
+
+An enumeration can be used in the @if@ and @case@ statements or iterating constructs.
+\begin{cquote}
+\setlength{\tabcolsep}{15pt}
+\begin{tabular}{@{}ll@{}}
+\begin{pascal}
+if @day@ = wday then
+        Writeln( day );
+if @day@ <= Fri then
+        Writeln( 'weekday');
+
+
+\end{pascal}
+&
+\begin{pascal}
+case @day@ of
+  Mon..Fri :
+        Writeln( 'weekday');
+  Sat..Sun :
+        Writeln( 'weekend')
+end;
+\end{pascal}
+\end{tabular}
+\end{cquote}
+\begin{cquote}
+\setlength{\tabcolsep}{15pt}
+\begin{tabular}{@{}ll@{}}
+\begin{pascal}
+day := Mon;
+while day <= Sat do begin
+        Write( day, ' ' );
+        day := succ( day );
+end;
+Mon Tue Wed Thu Fri Sat
+\end{pascal}
+&
+\begin{pascal}
+
+for day := Mon to Sat do begin
+        Write( day, ' ' );
+
+end;
+Mon Tue Wed Thu Fri Sat
+\end{pascal}
+\end{tabular}
+\end{cquote}
+Note, subtype @Weekday@ and @Weekend@ cannot be used to define a case or loop range.
+
+An enumeration type can be used as an array dimension and subscript.
+\begin{pascal}
+Lunch : array( @Week@ ) of Time;
+for day in Week loop
+        Lunch( @day@ ) := ... ;       { set lunch time }
+end loop;
+\end{pascal}
+
+Free Pascal~\cite[\S~3.1.1]{FreePascal} is a modern, object-oriented version of Pascal, with a C-style enumeration type.
+Enumerators can be assigned explicit values assigned in ascending numerical order using a constant expression, and the range can be non-consecutive.
+\begin{pascal}
+type Count = ( Zero, One, Two, Ten = 10, Eleven );
+\end{pascal}
+Pseudo-functions @pred@ and @succ@ can only be used if the range is consecutive.
+Enumerating gives extraneous values.
+\begin{pascal}
+for cnt := Zero to Eleven do begin
+        Write( ord( cnt ), ' ' );
+end;
+0 1 2 @3 4 5 6 7 8 9@ 10 11 
+\end{pascal}
+
 The underlying type is an implementation-defined integral-type large enough to hold all enumerated values; it does not have to be the smallest possible type.
 The integral size can be explicitly specified using compiler directive @$PACKENUM@~$N$, where $N$ is the number of bytes, \eg:
@@ -51 +161 @@
 \section{Ada}
 
-An Ada enumeration type is a set of ordered unscoped identifiers (enumerators) bound to \emph{unique} \newterm{literals}.\footnote{%
+An Ada enumeration type is a set of ordered, unscoped identifiers (enumerators) bound to \emph{unique} \newterm{literals}.\footnote{%
 Ada is \emph{case-insensitive} so identifiers may appear in multiple forms and still be the same, \eg \lstinline{Mon}, \lstinline{moN}, and \lstinline{MON} (a questionable design decision).}
 \begin{ada}
@@ -770 +880 @@
 (Note, after an @adt@'s type is know, the enumerator is inferred without qualification, \eg @.I(3)@.)
 
-An enumeration is created when \emph{all} the enumerators are unit-type.
+An enumeration is created when \emph{all} the enumerators are unit-type, which is like a scoped, opaque enumeration.
 \begin{swift}
 enum Week {
         case Mon, Tue, Wed, Thu, Fri, Sat, Sun // unit-type
 };
-var week : Week = Week.Mon;
+var week : Week = @Week.Mon@;
 \end{swift}
 As well, it is possible to type \emph{all} the enumerators with a common type, and set different values for each enumerator;
@@ -1098 +1208 @@
 % https://dev.realworldocaml.org/runtime-memory-layout.html
 
-OCaml provides a variant (union) type, where multiple heterogeneously-typed objects share the same storage.
-The simplest form of the variant type is a list of nullary datatype constructors, which is like an unscoped, opaque enumeration.
-
-OCaml provides a variant (union) type, which is an aggregation of heterogeneous types.
-A basic variant is a list of nullary datatype constructors, which is like an unscoped, opaque enumeration.
+Like Haskell, OCaml @enum@ provides two largely independent mechanisms from a single language feature: an ADT and an enumeration.
+When @enum@ is an ADT, pattern matching is used to discriminate among the variant types.
+\begin{cquote}
+\setlength{\tabcolsep}{20pt}
+\begin{tabular}{@{}l@{\hspace{35pt}}ll@{}}
+\begin{ocaml}
+type s = { i : int; j : int }
+let sv : s = { i = 3; j = 5 }
+@type@ adt =
+        I of int |    $\C[1in]{// int}$
+        F of float |  $\C{// float}$
+        S of s        $\C{// struct}\CRT$
+
+
+\end{ocaml}
+&
+\begin{ocaml}
+let adtprt( adtv : adt ) =
+        @match@ adtv with (* pattern matching *)
+                I i -> printf "%d\n" i |
+                F f -> printf "%g\n" f |
+                S sv -> printf "%d %d\n" sv.i sv.j
+let adtv : adt = I(3)       let _ = adtprt( adtv )
+let adtv : adt = F(3.5)   let _ = adtprt( adtv )
+let adtv : adt = S(sv)    let _ = adtprt( adtv )
+\end{ocaml}
+&
+\begin{ocaml}
+3
+3.5
+3 5
+
+
+
+
+
+\end{ocaml}
+\end{tabular}
+\end{cquote}
+(Note, after an @adtv@'s type is know, the enumerator is inferred without qualification, \eg @I(3)@.)
+The type names are independent from the type value, and mapped to an opaque, ascending, integral tag, starting from 0, supporting relational operators @<@, @<=@, @>@, and @>=@.
+\begin{cquote}
+\setlength{\tabcolsep}{10pt}
+\begin{tabular}{@{}l@{\hspace{25pt}}ll@{}}
+\begin{ocaml}
+let silly( adtv : adt ) =
+        if adtv <= F(3.5) then
+                printf "<= F\n"
+        else if adtv >= S(sv) then
+                printf ">= S\n"
+\end{ocaml}
+&
+\begin{ocaml}
+let adtv : adt = I(3)       let _ = silly( adtv )
+let adtv : adt = F(3.5)   let _ = silly( adtv )
+let adtv : adt = S(sv)    let _ = silly( adtv )
+
+
+\end{ocaml}
+&
+\begin{ocaml}
+<= F
+<= F
+>= S
+
+
+\end{ocaml}
+\end{tabular}
+\end{cquote}
+In the example, type values must be specified (any appropriate values work) but ignored in the relational comparison of the type tag.
+
+An enumeration is created when \emph{all} the enumerators are unit-type, which is like a scoped, opaque enumeration, where only the type tag is used.
 \begin{ocaml}
 type week = Mon | Tue | Wed | Thu | Fri | Sat | Sun
-let day : week @= Mon@                          $\C{(* bind *)}$
-let take_class( d : week ) =
-        @match@ d with                                          $\C{(* matching *)}$
-                Mon | Wed -> Printf.printf "CS442\n" |
-                Tue | Thu -> Printf.printf "CS343\n" |
-                Fri -> Printf.printf "Tutorial\n" |
-                _ -> Printf.printf "Take a break\n"
-let _ = take_class( Mon );
-@CS442@
+let day : week = Mon
 \end{ocaml}
-The only operations are binding and pattern matching (equality), where the variant name is logically the implementation tag stored in the union for discriminating the value in the object storage.
-After compilation, variant names are mapped to an opague ascending intergral type discriminants, starting from 0.
-Here, function @take_class@ has a @week@ parameter, and returns @"CS442"@, if the week value is @Mon@ or @Wed@, @"CS343"@, if the value is @Tue@ or @Thu@, and @"Tutorial"@ for @Fri@.
-The ``@_@'' is a wildcard matching any @week@ value, so the function returns @"Take a break"@ for values @Sat@ or @Sun@, which are not matched by the previous cases.
-Since the variant has no type, it has a \newterm{0-arity constructor}, \ie no parameters.
-Because @week@ is a union of values @Mon@ to @Sun@, it is a \newterm{union type} in turns of the functional-programming paradigm. 
-
-Each variant can have an associated heterogeneous type, with an n-ary constructor for creating a corresponding value.
+Since the type names are opaque, a type-tag value cannot be explicitly set nor can it have a type other than integral.
+
+As seen, a type tag can be used in the @if@ and \lstinline[language=ocaml]{match} statements, where \lstinline[language=ocaml]{match} must be exhaustive or have a default case.
+
+Enumerating is accomplished by deriving from @enumerate@.
+
+Enumeration subtyping is allowed but inheritance is restricted to classes not types.
 \begin{ocaml}
-type colour = Red | Green of @string@ | Blue of @int * float@
+type weekday = Mon | Tue | Wed | Thu | Fri
+type weekend = Sat | Sun
+type week = Weekday of weekday | Weekend of weekend
+let day : week = Weekend Sun
 \end{ocaml}
-A variant with parameter is stored in a memory block, prefixed by an int tag and has its parameters stores as words in the block.
-@colour@ is a summation of a nullary type, a unary product type of @string@, and a cross product of @int@ and @float@.
-(Mathematically, a @Blue@ value is a Cartesian product of the types @int@ type and @float@.)
-Hence, a variant type creates a sum of product of different types.
-\begin{ocaml}
-let c = Red                                                             $\C{(* 0-ary constructor, set tag *)}$
-let _ = match c with Red -> Printf.printf "Red, "
-let c = Green( "abc" )                                  $\C{(* 1-ary constructor, set tag *)}$
-let _ = match c with Green g -> Printf.printf "%s, " g
-let c = Blue( 1, 1.5 )                                  $\C{(* 2-ary constructor, set tag *)}$
-let _ = match c with Blue( i, f ) -> Printf.printf "%d %g\n" i f
-@Red, abc, 1 1.5@
-\end{ocaml}
-
-A variant type can have a recursive definition.
-\begin{ocaml}
-type @stringList@ = Empty | Pair of string * @stringList@
-\end{ocaml}
-which is a recursive sum of product of types, called an \newterm{algebraic data-type}.
-A recursive function is often used to pattern match against a recursive variant type.
-\begin{ocaml}
-let rec @len_of_string_list@( list : stringList ): int =
-        match list with
-                Empty -> 0 |
-                Pair( _ , r ) -> 1 + @len_of_string_list@ r
-\end{ocaml}
-Here, the head of the recursive type is removed and the remainder is processed until the type is empty.
-Each recursion is counted to obtain the number of elements in the type.
-
-Note, the compiler statically guarantees that only the correct kind of type is used in the \lstinline[language=OCaml]{match} statement.
-However, the union tag is dynamically set on binding (and possible reset on assignment), so a \lstinline[language=OCaml]{match} statement is effectively doing RTTI to select the matching case clause.
-
-In summary, an OCaml variant is a singleton value rather than a set of possibly ordered values, and hence, has no notion of enumerabilty.
-Therefore it is not an enumeration, except for the simple opaque (nullary) case.
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -1203 +1340 @@
 > I've marked 3 places with your name to shows places with enum ordering.
 >
+> open Printf
 > type week = Mon | Tue | Wed | Thu | Fri | Sat | Sun
 > let day : week = Mon
 > let take_class( d : week ) =
 >       if d <= Fri then                                (* Gregor *)
->               Printf.printf "week\n"
+>               printf "week\n"
 >       else if d >= Sat then                   (* Gregor *)
->               Printf.printf "weekend\n";
+>               printf "weekend\n";
 >       match d with
->               Mon | Wed -> Printf.printf "CS442\n" |
->               Tue | Thu -> Printf.printf "CS343\n" |
->               Fri -> Printf.printf "Tutorial\n" |
->               _ -> Printf.printf "Take a break\n"
+>               Mon | Wed -> printf "CS442\n" |
+>               Tue | Thu -> printf "CS343\n" |
+>               Fri -> printf "Tutorial\n" |
+>               _ -> printf "Take a break\n"
 >
 > let _ = take_class( Mon ); take_class( Sat );
@@ -1220 +1358 @@
 > type colour = Red | Green of string | Blue of int * float
 > let c = Red
-> let _ = match c with Red -> Printf.printf "Red, "
+> let _ = match c with Red -> printf "Red, "
 > let c = Green( "abc" )
-> let _ = match c with Green g -> Printf.printf "%s, " g
+> let _ = match c with Green g -> printf "%s, " g
 > let c = Blue( 1, 1.5 )
-> let _ = match c with Blue( i, f ) -> Printf.printf "%d %g\n" i f
+> let _ = match c with Blue( i, f ) -> printf "%d %g\n" i f
 >
 > let check_colour(c: colour): string =
 >       if c < Green( "xyz" ) then              (* Gregor *)
->               Printf.printf "green\n";
+>               printf "green\n";
 >       match c with
 >               Red -> "Red" |
@@ -1242 +1380 @@
 >
 > let _ = for i = 1 to 10 do
->       Printf.printf "%d, " i
+>       printf "%d, " i
 > done
 >