Index: doc/theses/jiada_liang_MMath/relatedwork.tex =================================================================== --- doc/theses/jiada_liang_MMath/relatedwork.tex (revision 290922138f90a1ce344a426acf7a7105710cc2c2) +++ doc/theses/jiada_liang_MMath/relatedwork.tex (revision 41f4e2d6244cadb06a6ec8623208e8b2c9740652) @@ -21,22 +21,132 @@ 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]{\{ invalid but allowed\}}$ +wend := day; $\C{\{ valid\}}$ +day := Mon; +wday := day; $\C{\{ valid\}}$ +@wend := day;@ $\C{\{ invalid but allowed\}}$ +day := wday; $\C{\{ valid\}}$ +day := wend; $\C{\{ valid\}}\CRT$ +\end{pascal} +There should be a static/dynamic range check to verify values. +(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,5 +161,5 @@ \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,10 +880,10 @@ (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,66 +1208,93 @@ % 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,16 +1340,17 @@ > 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,13 +1358,13 @@ > 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,5 +1380,5 @@ > > let _ = for i = 1 to 10 do -> Printf.printf "%d, " i +> printf "%d, " i > done >