Changeset 41f4e2d
- Timestamp:
- Jun 25, 2024, 12:05:53 PM (4 months ago)
- Branches:
- master
- Children:
- f3b67b6
- Parents:
- 29092213
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/jiada_liang_MMath/relatedwork.tex
r29092213 r41f4e2d 21 21 Among theses languages, there are a large set of overlapping features, but each language has its own unique extensions and restrictions. 22 22 23 23 24 \section{Pascal} 24 25 \label{s:Pascal} 25 26 26 ClassicPascal introduced the \lstinline[language=Pascal]{const} aliasing declaration binding a name to a constant literal/expression.27 Pascal introduced the \lstinline[language=Pascal]{const} aliasing declaration binding a name to a constant literal/expression. 27 28 \begin{pascal} 28 const one = 0 + 1; Vowels = set of (A,E,I,O,U); NULL = NIL; 29 PI = 3.14159; Plus = '+'; Fred = 'Fred'; 29 const Three = 2 + 1; NULL = NIL; PI = 3.14159; Plus = '+'; Fred = 'Fred'; 30 30 \end{pascal} 31 31 As stated, this mechanism is not an enumeration because there is no specific type (pseudo enumeration). 32 Hence, there is no notion of a (possibly ordered) set , modulo the \lstinline[language=pascal]{set of} type.32 Hence, there is no notion of a (possibly ordered) set. 33 33 The type of each constant name (enumerator) is inferred from the constant-expression type. 34 34 35 Free Pascal~\cite[\S~3.1.1]{FreePascal} is a modern, object-oriented version of classic Pascal, with a C-style enumeration type. 36 Enumerators must be assigned in ascending numerical order with a constant expression and the range can be non-consecutive. 35 Pascal introduced the enumeration type characterized by a set of ordered, unscoped identifiers (enumerators), which are not overloadable.\footnote{% 36 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).} 37 37 \begin{pascal} 38 Type EnumType = ( one, two, three, forty @= 40@, fortyone);38 type Week = ( Mon, Tue, Wed, Thu, Fri, Sat, Sun ); 39 39 \end{pascal} 40 Pseudo-functions @Pred@ and @Succ@ can only be used if the range is consecutive. 40 Object initialization and assignment are restricted to the enumerators of this type. 41 Enumerators are auto-initialized from left to right, starting at zero, incrementing by 1. 42 Enumerators \emph{cannot} be explicitly initialized. 43 Pascal provides a predefined type \lstinline[language=Pascal]{Boolean} defined as: 44 \begin{pascal} 45 type Boolean = ( false, true ); 46 \end{pascal} 47 The enumeration ordering supports the relational operators @=@, @<>@, @<@, @<=@, @>=@, and @>@, provided both operands are the same (sub)type. 48 49 The following auto-generated pseudo-functions exist for all enumeration types: 50 \begin{cquote} 51 \begin{tabular}{@{}ll@{}} 52 @succ( T )@ & @succ( Tue ) = Wed@ \\ 53 @pred( T )@ & @pred( Tue ) = Mon@ \\ 54 @ord( T )@ & @ord( Tue ) = 1@ 55 \end{tabular} 56 \end{cquote} 57 58 Pascal provides \emph{consecutive} subtyping of an enumeration using subrange type. 59 \begin{pascal} 60 type Week = ( Mon, Tue, Wed, Thu, Fri, Sat, Sun ); 61 Weekday = @Mon..Fri@; 62 Weekend = @Sat..Sun@; 63 var day : Week; 64 wday : Weekday; 65 wend : Weekend; 66 \end{pascal} 67 Hence, the ordering of the enumerators is crucial to provide the necessary ranges. 68 There is bidirectional assignment between the enumeration and its subranges. 69 \begin{pascal} 70 day := Sat; 71 @wday := day;@ $\C[1.5in]{\{ invalid but allowed\}}$ 72 wend := day; $\C{\{ valid\}}$ 73 day := Mon; 74 wday := day; $\C{\{ valid\}}$ 75 @wend := day;@ $\C{\{ invalid but allowed\}}$ 76 day := wday; $\C{\{ valid\}}$ 77 day := wend; $\C{\{ valid\}}\CRT$ 78 \end{pascal} 79 There should be a static/dynamic range check to verify values. 80 (Free Pascal does not check and aborts in certain situations, like writing an invalid enumerator.) 81 82 An enumeration can be used in the @if@ and @case@ statements or iterating constructs. 83 \begin{cquote} 84 \setlength{\tabcolsep}{15pt} 85 \begin{tabular}{@{}ll@{}} 86 \begin{pascal} 87 if @day@ = wday then 88 Writeln( day ); 89 if @day@ <= Fri then 90 Writeln( 'weekday'); 91 92 93 \end{pascal} 94 & 95 \begin{pascal} 96 case @day@ of 97 Mon..Fri : 98 Writeln( 'weekday'); 99 Sat..Sun : 100 Writeln( 'weekend') 101 end; 102 \end{pascal} 103 \end{tabular} 104 \end{cquote} 105 \begin{cquote} 106 \setlength{\tabcolsep}{15pt} 107 \begin{tabular}{@{}ll@{}} 108 \begin{pascal} 109 day := Mon; 110 while day <= Sat do begin 111 Write( day, ' ' ); 112 day := succ( day ); 113 end; 114 Mon Tue Wed Thu Fri Sat 115 \end{pascal} 116 & 117 \begin{pascal} 118 119 for day := Mon to Sat do begin 120 Write( day, ' ' ); 121 122 end; 123 Mon Tue Wed Thu Fri Sat 124 \end{pascal} 125 \end{tabular} 126 \end{cquote} 127 Note, subtype @Weekday@ and @Weekend@ cannot be used to define a case or loop range. 128 129 An enumeration type can be used as an array dimension and subscript. 130 \begin{pascal} 131 Lunch : array( @Week@ ) of Time; 132 for day in Week loop 133 Lunch( @day@ ) := ... ; { set lunch time } 134 end loop; 135 \end{pascal} 136 137 Free Pascal~\cite[\S~3.1.1]{FreePascal} is a modern, object-oriented version of Pascal, with a C-style enumeration type. 138 Enumerators can be assigned explicit values assigned in ascending numerical order using a constant expression, and the range can be non-consecutive. 139 \begin{pascal} 140 type Count = ( Zero, One, Two, Ten = 10, Eleven ); 141 \end{pascal} 142 Pseudo-functions @pred@ and @succ@ can only be used if the range is consecutive. 143 Enumerating gives extraneous values. 144 \begin{pascal} 145 for cnt := Zero to Eleven do begin 146 Write( ord( cnt ), ' ' ); 147 end; 148 0 1 2 @3 4 5 6 7 8 9@ 10 11 149 \end{pascal} 150 41 151 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. 42 152 The integral size can be explicitly specified using compiler directive @$PACKENUM@~$N$, where $N$ is the number of bytes, \eg: … … 51 161 \section{Ada} 52 162 53 An Ada enumeration type is a set of ordered unscoped identifiers (enumerators) bound to \emph{unique} \newterm{literals}.\footnote{%163 An Ada enumeration type is a set of ordered, unscoped identifiers (enumerators) bound to \emph{unique} \newterm{literals}.\footnote{% 54 164 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).} 55 165 \begin{ada} … … 770 880 (Note, after an @adt@'s type is know, the enumerator is inferred without qualification, \eg @.I(3)@.) 771 881 772 An enumeration is created when \emph{all} the enumerators are unit-type .882 An enumeration is created when \emph{all} the enumerators are unit-type, which is like a scoped, opaque enumeration. 773 883 \begin{swift} 774 884 enum Week { 775 885 case Mon, Tue, Wed, Thu, Fri, Sat, Sun // unit-type 776 886 }; 777 var week : Week = Week.Mon;887 var week : Week = @Week.Mon@; 778 888 \end{swift} 779 889 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 1099 1209 1100 OCaml provides a variant (union) type, where multiple heterogeneously-typed objects share the same storage. 1101 The simplest form of the variant type is a list of nullary datatype constructors, which is like an unscoped, opaque enumeration. 1102 1103 OCaml provides a variant (union) type, which is an aggregation of heterogeneous types. 1104 A basic variant is a list of nullary datatype constructors, which is like an unscoped, opaque enumeration. 1210 Like Haskell, OCaml @enum@ provides two largely independent mechanisms from a single language feature: an ADT and an enumeration. 1211 When @enum@ is an ADT, pattern matching is used to discriminate among the variant types. 1212 \begin{cquote} 1213 \setlength{\tabcolsep}{20pt} 1214 \begin{tabular}{@{}l@{\hspace{35pt}}ll@{}} 1215 \begin{ocaml} 1216 type s = { i : int; j : int } 1217 let sv : s = { i = 3; j = 5 } 1218 @type@ adt = 1219 I of int | $\C[1in]{// int}$ 1220 F of float | $\C{// float}$ 1221 S of s $\C{// struct}\CRT$ 1222 1223 1224 \end{ocaml} 1225 & 1226 \begin{ocaml} 1227 let adtprt( adtv : adt ) = 1228 @match@ adtv with (* pattern matching *) 1229 I i -> printf "%d\n" i | 1230 F f -> printf "%g\n" f | 1231 S sv -> printf "%d %d\n" sv.i sv.j 1232 let adtv : adt = I(3) let _ = adtprt( adtv ) 1233 let adtv : adt = F(3.5) let _ = adtprt( adtv ) 1234 let adtv : adt = S(sv) let _ = adtprt( adtv ) 1235 \end{ocaml} 1236 & 1237 \begin{ocaml} 1238 3 1239 3.5 1240 3 5 1241 1242 1243 1244 1245 1246 \end{ocaml} 1247 \end{tabular} 1248 \end{cquote} 1249 (Note, after an @adtv@'s type is know, the enumerator is inferred without qualification, \eg @I(3)@.) 1250 The type names are independent from the type value, and mapped to an opaque, ascending, integral tag, starting from 0, supporting relational operators @<@, @<=@, @>@, and @>=@. 1251 \begin{cquote} 1252 \setlength{\tabcolsep}{10pt} 1253 \begin{tabular}{@{}l@{\hspace{25pt}}ll@{}} 1254 \begin{ocaml} 1255 let silly( adtv : adt ) = 1256 if adtv <= F(3.5) then 1257 printf "<= F\n" 1258 else if adtv >= S(sv) then 1259 printf ">= S\n" 1260 \end{ocaml} 1261 & 1262 \begin{ocaml} 1263 let adtv : adt = I(3) let _ = silly( adtv ) 1264 let adtv : adt = F(3.5) let _ = silly( adtv ) 1265 let adtv : adt = S(sv) let _ = silly( adtv ) 1266 1267 1268 \end{ocaml} 1269 & 1270 \begin{ocaml} 1271 <= F 1272 <= F 1273 >= S 1274 1275 1276 \end{ocaml} 1277 \end{tabular} 1278 \end{cquote} 1279 In the example, type values must be specified (any appropriate values work) but ignored in the relational comparison of the type tag. 1280 1281 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. 1105 1282 \begin{ocaml} 1106 1283 type week = Mon | Tue | Wed | Thu | Fri | Sat | Sun 1107 let day : week @= Mon@ $\C{(* bind *)}$ 1108 let take_class( d : week ) = 1109 @match@ d with $\C{(* matching *)}$ 1110 Mon | Wed -> Printf.printf "CS442\n" | 1111 Tue | Thu -> Printf.printf "CS343\n" | 1112 Fri -> Printf.printf "Tutorial\n" | 1113 _ -> Printf.printf "Take a break\n" 1114 let _ = take_class( Mon ); 1115 @CS442@ 1284 let day : week = Mon 1116 1285 \end{ocaml} 1117 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. 1118 After compilation, variant names are mapped to an opague ascending intergral type discriminants, starting from 0. 1119 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@. 1120 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. 1121 Since the variant has no type, it has a \newterm{0-arity constructor}, \ie no parameters. 1122 Because @week@ is a union of values @Mon@ to @Sun@, it is a \newterm{union type} in turns of the functional-programming paradigm. 1123 1124 Each variant can have an associated heterogeneous type, with an n-ary constructor for creating a corresponding value. 1286 Since the type names are opaque, a type-tag value cannot be explicitly set nor can it have a type other than integral. 1287 1288 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. 1289 1290 Enumerating is accomplished by deriving from @enumerate@. 1291 1292 Enumeration subtyping is allowed but inheritance is restricted to classes not types. 1125 1293 \begin{ocaml} 1126 type colour = Red | Green of @string@ | Blue of @int * float@ 1294 type weekday = Mon | Tue | Wed | Thu | Fri 1295 type weekend = Sat | Sun 1296 type week = Weekday of weekday | Weekend of weekend 1297 let day : week = Weekend Sun 1127 1298 \end{ocaml} 1128 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.1129 @colour@ is a summation of a nullary type, a unary product type of @string@, and a cross product of @int@ and @float@.1130 (Mathematically, a @Blue@ value is a Cartesian product of the types @int@ type and @float@.)1131 Hence, a variant type creates a sum of product of different types.1132 \begin{ocaml}1133 let c = Red $\C{(* 0-ary constructor, set tag *)}$1134 let _ = match c with Red -> Printf.printf "Red, "1135 let c = Green( "abc" ) $\C{(* 1-ary constructor, set tag *)}$1136 let _ = match c with Green g -> Printf.printf "%s, " g1137 let c = Blue( 1, 1.5 ) $\C{(* 2-ary constructor, set tag *)}$1138 let _ = match c with Blue( i, f ) -> Printf.printf "%d %g\n" i f1139 @Red, abc, 1 1.5@1140 \end{ocaml}1141 1142 A variant type can have a recursive definition.1143 \begin{ocaml}1144 type @stringList@ = Empty | Pair of string * @stringList@1145 \end{ocaml}1146 which is a recursive sum of product of types, called an \newterm{algebraic data-type}.1147 A recursive function is often used to pattern match against a recursive variant type.1148 \begin{ocaml}1149 let rec @len_of_string_list@( list : stringList ): int =1150 match list with1151 Empty -> 0 |1152 Pair( _ , r ) -> 1 + @len_of_string_list@ r1153 \end{ocaml}1154 Here, the head of the recursive type is removed and the remainder is processed until the type is empty.1155 Each recursion is counted to obtain the number of elements in the type.1156 1157 Note, the compiler statically guarantees that only the correct kind of type is used in the \lstinline[language=OCaml]{match} statement.1158 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.1159 1160 In summary, an OCaml variant is a singleton value rather than a set of possibly ordered values, and hence, has no notion of enumerabilty.1161 Therefore it is not an enumeration, except for the simple opaque (nullary) case.1162 1299 1163 1300 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% … … 1203 1340 > I've marked 3 places with your name to shows places with enum ordering. 1204 1341 > 1342 > open Printf 1205 1343 > type week = Mon | Tue | Wed | Thu | Fri | Sat | Sun 1206 1344 > let day : week = Mon 1207 1345 > let take_class( d : week ) = 1208 1346 > if d <= Fri then (* Gregor *) 1209 > Printf.printf "week\n"1347 > printf "week\n" 1210 1348 > else if d >= Sat then (* Gregor *) 1211 > Printf.printf "weekend\n";1349 > printf "weekend\n"; 1212 1350 > match d with 1213 > Mon | Wed -> Printf.printf "CS442\n" |1214 > Tue | Thu -> Printf.printf "CS343\n" |1215 > Fri -> Printf.printf "Tutorial\n" |1216 > _ -> Printf.printf "Take a break\n"1351 > Mon | Wed -> printf "CS442\n" | 1352 > Tue | Thu -> printf "CS343\n" | 1353 > Fri -> printf "Tutorial\n" | 1354 > _ -> printf "Take a break\n" 1217 1355 > 1218 1356 > let _ = take_class( Mon ); take_class( Sat ); … … 1220 1358 > type colour = Red | Green of string | Blue of int * float 1221 1359 > let c = Red 1222 > let _ = match c with Red -> Printf.printf "Red, "1360 > let _ = match c with Red -> printf "Red, " 1223 1361 > let c = Green( "abc" ) 1224 > let _ = match c with Green g -> Printf.printf "%s, " g1362 > let _ = match c with Green g -> printf "%s, " g 1225 1363 > let c = Blue( 1, 1.5 ) 1226 > let _ = match c with Blue( i, f ) -> Printf.printf "%d %g\n" i f1364 > let _ = match c with Blue( i, f ) -> printf "%d %g\n" i f 1227 1365 > 1228 1366 > let check_colour(c: colour): string = 1229 1367 > if c < Green( "xyz" ) then (* Gregor *) 1230 > Printf.printf "green\n";1368 > printf "green\n"; 1231 1369 > match c with 1232 1370 > Red -> "Red" | … … 1242 1380 > 1243 1381 > let _ = for i = 1 to 10 do 1244 > Printf.printf "%d, " i1382 > printf "%d, " i 1245 1383 > done 1246 1384 >
Note: See TracChangeset
for help on using the changeset viewer.