has been the Spy’s meat and potatoes in this space for a few months now. It is the fully modern dialect of Niklaus Wirth’s Modula-2 that he and Telecom engineer Benjamin Kowarsch have developed to address serious software engineering issues of safety, security, reliability, and extensibility. This month we consider the use of Generic templates to reach toward the software engineering grail of reusable code.
Modern programming practice first saw Generics in Modula-3, C++, and Java. The Modula-3 technique was then modified somewhat by the Spy as part of a proposal to the ISO committee for Modula-2 and this became a supplementary standard to that work, subsequently implemented by most vendors.
Generic facilities address
two common situations with a lightweight solution for which using class types and their objects is overkill. These are:
1. the implementation of algorithms whose expression is essentially identical across many the data types on which it is used. The classic example is a sorting algorithm, which, once implemented, can be re-used for a new data type by modifying only the way that comparisons and swops are done.
2. the implementation of data structures whose maintenance code is essentially identical across the many data types that may be stored in it. Examples include linked lists, various tree structures, and so on.
In both cases, rather than implement once, then modify to suit alternate data types, it makes sense to have a facility that allows the code to be expressed in a manner that is generic, that is, with a dummy data type present in the code, and a provision to “refine” this generic code for a specified data type by the expedient of passing to a refining utility a pseudo-parameter naming that data type.
ISO Modula-2 generics
achieved this by employing a parameterized Generic module pair as compilation units, which could be refined any number of times by the compiler, whenever it was presented with a refining module pair that supplied the actual parameters. One wrote, for instance:
GENERIC DEFINITION MODULE Sorts (Item : TYPE; GenCompare : CompareProc);
FROM Comparisons IMPORT
CompareProc = PROCEDURE (Item, Item) : CompareResults;
PROCEDURE Quick (VAR data : ARRAY OF Item);
(* Other procedures and functions would be included as well. *)
and then wrote the corresponding implementation module, where comparisons for the purpose of sorting were done naming the formal “GenCompare” name, whose actual value would be passed in as parameter on refinement. One could also name, say, a “GenSwop” routine and refine that as well, although this is unnecessary, as it could be hidden in the generic implementation and be written to swop using the generic type name. Only type parameters and constant value parameters (which includes specific procedure names) were allowed as formal generic module parameters. Note that the type of a formal parameter could be defined in the generic definition itself as the compiler has access to the entire contents of such a definition, and this is a trivial forward reference.
A refining module pair would have:
DEFINITION MODULE CardQuickSort = Sorts (CARDINAL); END CardStack.
and likewise for the refining implementation, with the identical actual parameter(s) required.
It was up to implementors to determine the mechanics of template refinement, but the semantics were to be as if a new separate library module were created from the template with the substitutions per the module parameters.
we determined that since all that was in view was textual substitution, we might as well be explicit and assume the presence of a utility to handle such substitutions. After all, it could be used for other purposes than template refinement. Thus, we dispense with refining definition and implementation modules, and with module parameters. moreover, since, for instance, comparison can be handled by binding to operators, the sorting example can be simplified. Mo compareProc is needed. Just write the code using the standard comparison operator(s), bind to the operator when defining the ADT, and the correct comparison code will be automatically called.
All items that must be replaced by substitution are enclosed in a double hash. Indeed, R10 specifies a language for templates, illustrated in portions of a template module for static arrays:
DEFINITION MODULE ##ModuleIdent## [ProtoStaticArray];
/* Modula-2 R10 Static Array Type Template */
* All parameters are marked (A) automatic, (M) mandatory or (D) default.
* This template expands the following parameters:
* TemplateVersion (A) — The date and time stamp of this template,
* automatically set by the template engine utility.
* ModuleIdent (A) — The library’s identifier,
* automatically supplied by the GENLIB directive.
* IndexType (M) — The index type must be an ordinal type. Compilation of
* the generated library will fail if it is not an ordinal type.
* ValueType (M) — The value type of the array, THERE IS NO DEFAULT.
* Template expansion will fail if the parameter is omitted.
* LowerBound (D) and UpperBound (D) — If omitted, the values of TMIN (Inde Type and TMAX(IndexType) will be used.
* Placeholder Verification and Defaults
* ———————————————————————— */
/* Define placeholder ADT as an alias of ModuleIdent */
<#DEFINE ADT = @@ModuleIdent@@#>
/* Verify IndexType holds a mixed or uppercase identifier, else fail */
<#VERIFY IndexType [Aa|AA] FAIL#>
/* Verify ValueType holds a mixed or uppercase identifier, else fail */
<#VERIFY ValueType [Aa|AA] FAIL#>
/* If LowerBound is omitted, use TMIN(IndexType) */
<#DEFIF UNDEFINED(LowerBound) : LowerBound = “TMIN(##IndexType##)” #>
/* If UpperBound is omitted, use TMAX(IndexType) */
<#DEFIF UNDEFINED(UpperBound) : LowerBound = “TMAX)(##IndexType##)” #>
CONST isOrdered = TRUE;
CONST componentCount = ##UpperBound## – ##LowerBound## + 1;
TYPE ##ADT## = OPAQUE RECORD
entry : ARRAY componentCount OF ValueType
END; (* ##ADT## *)
TYPE ValueType = ALIAS OF ##ValueType##;
PROCEDURE [:=] assignStructuredValue
( array : ##ADT##; value : ARGLIST componentCount OF ValueType );
PROCEDURE [COPY] copy
( CONST source : ##ADT##; VAR target : ##ADT## );
PROCEDURE [STORE] storeValueAtIndex
( array : ##ADT##;
index : ##IndexType##; value : ##ValueType## );
PROCEDURE [RETRIEVE] valueAtIndex
( array : ##ADT##; index : ##IndexType## );
PROCEDURE [COUNT] count ( array : ##ADT## ) : LONGCARD;
TYPE ForLoopBodyProc = PROCEDURE ( (* index : *) CONST ##IndexType## );
PROCEDURE [FOR] forIterator
( assocArray : ##ADT##;
forLoopBody : ForLoopBodyProc; ascending : BOOLEAN );
PROCEDURE [=] isEqual
( array1, array2 : ##ADT## ) : BOOLEAN;
/* General IO library */
<#EXPAND “StaticArrays” : ModuleIdent = @@ADT@@”IO”; ValueType = @@ValueType@@ GenIO = “TRUE”#>
/* Generate the ADT’s IO Library */
DEFINITION MODULE ##IOLibrary## [ProtoIO] FOR ##ADT##;
PROCEDURE [READ] Read ( file : File; VAR array : ##ADT## );
PROCEDURE [WRITE] Write ( file : File; array : ##ADT## );
PROCEDURE [WRITEF] WriteF
( file : File; fmtStr : ARRAY OF CHAR;
items : VARIADIC OF ##ADT## );
This template is expanded by the M2 R10 template engine utility. Expansion may be invoked within a compiling source file using the GENLIB directive.
GENLIB FooArray FROM GenStaticArrays FOR IndexType = "Barbaz"; ValueType = "Bamboo" END;
and thereafter, the newly generated library may be simply imported into the current or some other scope.
During template expansion, any occurrences of ##ModuleIdent## are replaced by the identifier following GENLIB, and any occurences of ##ValueType## are replaced by the quoted value given for ValueType in the GENLIB directive. Template comments (like this one) are removed during template expansion.
In this instance (and likely in many others) the template itself depends on a blueprint. as it contains bindings. Moreover, this template generate two libraries–one for the data structure itself, and a second for its I/O.
This is just a taste
of what can be done using templates. But, as we said last month with respect to blueprints, it ought to give the reader some idea of how Modula-2 R10 enforces the discipline of planning to assist in producing sound well-thought-out code, and provides the means to re-use tried and true code frameworks with a variety of other data types.
What about OO?
Wirth’s original Modula-2 notation lacked OO. The ISO committee added two object oriented variants in an extension–one garbage collected, the other not. At this point, R10 is a base notation and has no object types. However, this is planned as part of a second phase, likely using the Objective-C philosophy, and for this purpose a few words have been reserved sequestered as probable future reserved words and standard identifiers. We do contend, however, that OO is not the best technique for everything, and at least some tasks often performed using it can be expressed more simply without.
That’s all folks
so for more information consult the repository site. Next month the Spy returns to his usual perambulations about the technical world, complete with observations on related social, economic, and political issues. Stay tuned, and remember you read it here first.
–The Northern Spy
Opinions expressed here are entirely the author’s own, and no endorsement is implied by any community or organization to which he may be attached. Rick Sutcliffe, (a. k. a. The Northern Spy) is professor of Computing Science and Mathematics at Canada’s Trinity Western University. He has been involved as a member or consultant with the boards of several community and organizations, and participated in developing industry standards at the national and international level. He is a co-author of the Modula-2 programming language R10 dialect. He is a long time technology author and has written two textbooks and nine alternate history SF novels, one named best ePublished SF novel for 2003. His columns have appeared in numerous magazines and newspapers (paper and online), and he’s a regular speaker at churches, schools, academic meetings, and conferences. He and his wife Joyce have lived in the Aldergrove/Bradner area of BC since 1972.
Want to discuss this and other Northern Spy columns? Surf on over to ArjayBB. com. Participate and you could win free web hosting from the WebNameHost. net subsidiary of Arjay Web Services. Rick Sutcliffe’s fiction can be purchased in various eBook formats from Fictionwise, and in dead tree form from Amazon’s Booksurge.
URLs for Rick Sutcliffe’s Arjay Enterprises:
The Northern Spy Home Page: http: //www. TheNorthernSpy. com
opundo : http: //opundo. com
Sheaves Christian Resources : http: //sheaves. org
WebNameHost : http: //www. WebNameHost. net
WebNameSource : http: //www. WebNameSource. net
nameman : http: //nameman. net
General URLs for Rick Sutcliffe’s Books:
Author Site: http: //www. arjay. ca
Publisher’s Site: http: //www. writers-exchange. com/Richard-Sutcliffe. html
The Fourth Civilization–Ethics, Society, and Technology (4th 2003 ed. ): http: //www. arjay. bc. ca/EthTech/Text/index. html
Sites for Modula-2 resources
Modula-2 FAQ and ISO-based introductory text: http://www.modula-2.com
R10 Repository and source code: https://bitbucket.org/trijezdci/m2r10/src
The Supplied Blueprint Hierarchy: https://bitbucket.org/trijezdci/m2r10/src/27876b7e71b7e04befe1687e27a3fc4d1eabf7b2/_STANDARD_LIBRARY/TEMPLATES/?at=default
More links, Wiki: http://www.modula-2.net
p1 ISO Modula-2 for the Mac: http://modula2.awiedemann.de/