By Rick Sutcliffe
In these last three months the Spy has introduced the fully modern dialect of an existing notation he and Telecom engineer Benjamin Kowarsch have developed to address serious software engineering issues of safety, security, reliability, and extensibility. This month he shows how to leverage Blueprints to enforce the rigour involved in planning code before executing it.
Modula-2 R10 allows the programmer to develop Abstract Data Type (ADT) libraries that include binding to language features such as operations (+ – * and /), various reserved words such as FOR, and syntax such as the accessor [] commonly used in programming notations for random access to array elements.
Each such library must conform to a blueprint In the definition module for each of the separate types and IO libraries that contained bindings, the syntax [Proto..] appears immediately after the name of the module, for instance:
DEFINITION MODULE CARD128 [ProtoCardinal];
This syntax is a reference to a blueprint module that contains a contract or proto-Type, which specifies a minimum set of bindings required for types complying with the blueprint. All modules containing bindings must comply with a blueprint, even if it is to one the programmer devises. Moreover, the blueprints for supplied libraries cannot be altered. The purpose of blueprints is to force on the programmer a strict regimen of planning, thus reducing the likelihood of coding errors.
A blueprint is used to construct valid dependent library model sand is a compilation unit, but has no corresponding implementation, and therefore produces no executable code executable module. Its presence merely enforces on the programmer the requirement that bindings be properly planned. We detail the relevant EBNF :
compilationUnit :
IMPLEMENTATION? programModule | definitionOfModule | blueprint;
definitionModule :
DEFINITION MODULE moduleIdent
( ‘[‘ blueprintToObey ‘]’ )? ( FOR typeToExtend )? ‘;’
importList* definition*
END moduleIdent ‘.’
;
blueprintToObey : blueprintIdent ;
blueprintIdent : Ident ;
blueprint :
BLUEPRINT blueprintIdent
( ‘[‘ blueprintToRefine ‘]’ )? ( FOR blueprintForTypeToExtend )? ‘;’
( REFERENTIAL identList ‘;’ )? moduleTypeSpec ‘;’
( requirement ‘;’ )*
END blueprintIdent ‘.’
blueprintToRefine : blueprintIdent ;
blueprintForTypeToExtend : blueprintIdent ;
The standard library provides a set of blueprint definitions to allow the construction of library defined ADTs with the same semantics as predefined types types defined using type constructor syntax. To require an ADT to conform to a blueprint, the library that defines the ADT must specify the blueprint identifier in the module header of its definition part. A variety of rules are enforced by values given to certain constants, and these are all explained in the documentation (pseudo) module BUILTIN. Blueprints for simple type ADTs descend from and depend on ProtoRoot.
Numeric Blueprints
For instance, for cardinals, we have:
BLUEPRINT ProtoCardinal [ProtoScalar]; (* conforms to ProtoScalar *)
MODULE TYPE = RECORD;
(* Cardinal ADTs must be records to be statically allocatable. *)
(* note that because we do not define TPROERTIES to in crude isSigned, that value is FALSE )
LITERAL = INTEGER;
(* Integer literals are compatible. *)
CONST [TBASE] base : CARDINAL;
(* Radix in which the ADT’s values are encoded, 2 or 10. *)
CONST [TPRECISION] precision : CARDINAL;
(* Maximum number of digits the ADT can encode, 1 to 4000. *)
CONST [TMINEXP] eMin = 0;
(* Cardinal ADTs always have an exponent of zero *)
CONST [TMAXEXP] eMax = 0;
(* Cardinal ADTs always have an exponent of zero *)
PROCEDURE [TMIN] minValue : ProtoCardinal;
PROCEDURE [TMAX] maxValue : ProtoCardinal;
PROCEDURE [SXF] toSXF ( value : ProtoCardinal; VAR sxf : ARRAY OF OCTET );
PROCEDURE [VAL] fromSXF ( sxf : ARRAY OF OCTET; VAR value : ProtoCardinal );
PROCEDURE [ABS] abs ( n : ProtoCardinal ) : ProtoCardinal;
PROCEDURE [ODD] odd ( n : ProtoCardinal ) : BOOLEAN;
PROCEDURE [+] add ( n, m : ProtoCardinal ) : ProtoCardinal;
PROCEDURE [-] subtract ( n, m : ProtoCardinal ) : ProtoCardinal;
PROCEDURE [*] multiply ( n, m : ProtoCardinal ) : ProtoCardinal;
PROCEDURE [DIV] divide ( n, m : ProtoCardinal ) : ProtoCardinal;
PROCEDURE [MOD] modulus ( n, m : ProtoCardinal ) : ProtoCardinal;
PROCEDURE [=] isEqual ( n, m : ProtoCardinal ) : BOOLEAN;
PROCEDURE [] isGreater ( n, m : ProtoCardinal ) : BOOLEAN;
END ProtoCardinal.
ProtoCardinal requires all the bindings it lists, and in turn depends on the broader blueprint ProtoScalar, which requires fewer, and which in turn is a specialization of ProtoNumeric, which is broader still (requiring even fewer bindings for conformance). A separate type module must contain bindings to and from SXF (scalar exchange format) to automatically enable using the type transfer operator :: to and from the type, but those for the built-in types such as CARDINAL are themselves built in.
In order to ensure the semantic compatibility of library defined types with built-in counterparts as well as the integrity of the standard library itself, all standard library blueprint definitions are immutable and their immutability is compiler enforced. Any attempt to use a standard library blueprint that has been modified shall cause a compilation error.
User libraries must either provide their own blueprint definitions or use one of the standard ones for their own custom designed abstract data types, if those ADTs include any bindings. Such user defined blueprints may be derived from the existing standard library blueprint hierarchy using the same syntax as shown above, and indeed, there may be whole structure of such blueprints, each successive one requiring more bindings (and hence being narrower or more specific) with the module defining a specific data type at the bottom of a long chain, and possibly containing other procedures that are not bound to an operator (such as, but not limited to Read, Write, and WriteF for I/O bindings, which are always permitted, though normally placed in a type extension module named TheTypeIO.) Except for bindings to the conversion operator which are always permitted, only bindings required by the blueprint the ADT conforms to may be defined. Anything else in a separate module dependent on a blueprint must be non-bound.
For instance, in the supplied hierarchy, ProtoNumeric is the root blueprint for all numeric proto-types. Bindings not present there may be required in specializations dependent on it.
BLUEPRINT ProtoNumeric [ProtoRoot];
MODULE TYPE = OPAQUE | RECORD;
(* Bindings required for numeric ADTs *)
(* The operations TMIN and TMAX are meaningful only for scalar types,
their bindings may be required by more specialised blueprints. *)
(* The operations SXF and VAL are meaningful only for scalar types
their bindings may be required by more specialised blueprints. *)
(* The operations ABS, NEG and ODD are not common to all numeric types,
their bindings may be required by more specialised blueprints. *)
PROCEDURE [+] add ( op1, op2 : ProtoNumeric ) : ProtoNumeric;
(* function to bind to the + operator for operands of the ADT *)
PROCEDURE [-] subtract ( op1, op2 : ProtoNumeric ) : ProtoNumeric;
(* function to bind to the – operator for operands of the ADT *)
(* The operations *, /, DIV and MOD are not common to all numeric types,
their bindings may be required by more specialized blueprints. *)
(* Bindings to relational operations *)
PROCEDURE [=] isEqual ( op1, op2 : ProtoNumeric ) : BOOLEAN;
(* function to bind to the = operator for operands of the numeric ADT *)
(* The operations < and > are meaningful only for scalar types,
their bindings may be required by more specialised blueprints. *)
END ProtoNumeric.
Blueprint Mechanics
Modula-2 R10 provides more than just a mechanism and a hierarchy for determining the contents of blueprints. Those contents are regulated by the following pseudo-module.
DEFINITION MODULE TPROPERTIES;
TYPE PROPERTY =
( isComputational, isNumber, isScalar, isCountable, isSigned,
isCollection, isIndexed, isRigid, isSet, isMultiSet, isDict, isMultiDict );
TYPE LITERAL =
( charLiteral, unicharLiteral, stringLiteral, unistringLiteral,
wholeNumberLiteral, realNumberLiteral );
(* MACRO *) PROCEDURE TPROPERTY ( T : ; p : PROPERTY ) : BOOLEAN;
(* Replaced by TRUE if type T has property p, otherwise FALSE. *)
(* MACRO *) PROCEDURE TLITERAL ( T : ; L : LITERAL ) : BOOLEAN;
(* Replaced by TRUE if literal L is compatible with type T, otherwise FALSE. *)
(* MACRO *) PROCEDURE TBUILTIN ( T : ) : BOOLEAN;
(* Replaced by TRUE if type T is a built-in type
or an alias or a subrange of a built-in type, otherwise FALSE. *)
(* MACRO *) PROCEDURE TDYN ( T : ) : BOOLEAN;
(* Replaced by TRUE if type T uses dynamic allocation, otherwise FALSE. *)
(* MACRO *) PROCEDURE TREFC ( T : ) : BOOLEAN;
(* Replaced by TRUE if type T is reference counted, otherwise FALSE. *)
(* MACRO *) PROCEDURE TNIL ( T : ) : BOOLEAN;
(* Replaced by TRUE if type T supports storage of NIL as a value,
otherwise FALSE. *)
(* MACRO *) PROCEDURE TBASE ( T : ) : CARDINAL;
(* Replaced by the radix of type T. *)
(* MACRO *) PROCEDURE TPRECISION ( T : ) : CARDINAL;
(* Replaced by the precision of type T.*)
(* MACRO *) PROCEDURE TMINEXP ( T : ) : INTEGER;
(* Replaced by the smallest exponent that can be encoded by type T.
The value is zero for countable types. *)
(* MACRO *) PROCEDURE TMAXEXP ( T : ) : CARDINAL;
(* Replaced by the largest exponent that can be encoded by type T.
The value is zero for countable types. *)
END TPROPERTIES.
Bindable identifiers in TPROPERTIES and CONVERSION are visible to the compiler for use in blueprints and the elements of type TPROPERTIES are visible as ancillary constants. An ancillary constant is a concept that exists only within blueprints. From a library or program view point neither such entities nor the terminology exists. The entities in TPROPERTIES are available to libraries through import like any other entities available from libraries. A blueprint then contains a section such as:
MODULE TYPE = RECORD;
TPROPERTIES = { isComputational, isNumber, isScalar };
LITERAL = REAL;
will gives it the properties so specified in the given set, and these in turn will govern to some extent what bindings must subsequently be provided in that blueprint. Within a blueprint, all of type TPROPERTIES elements are automatically available as ancillary constants. Those listed in the property section are TRUE, those not listed are FALSE.For instance, the presence of isComputational requires numeric operations such as + – * and / to be bound, and that of isScalar requires < to be bound. The logic is:
isSigned -> PROCEDURE [+/-];
NOT isScalar -> PROCEDURE [ indicate proper subset and proper superset, and * indicates set intersection, then the following hierarchy illustrates the relationship among these properties.
(1) S(isComputational) >
S(isNumber) > S(isScalar) > S(isCountable) > S(isSigned)
(2) S(isNumber) * S(isCollection) = EMPTY
(3) S(isCollection) > S(isIndexed) > S(isRigid)
(4) S(isCollection) > S(isSet) > S(isMultiSet)
(5) S(isCollection) > S(isDict) > S(isMultiDict)
(6) S(isCollection) * S(isComputational) > EMPTY
(7) S(isCollection) * S(isOrdered) > EMPTY
(8) S(isIndexed) * S(isSet) = EMPTY
(9) S(isIndexed) * S(isDict) = EMPTY
(10) S(isSet) * S(isDict) = EMPTY
(11) S(isSet) * S(isComputational) = EMPTY
(12) S(isDict) * S(isComputational) = EMPTY
Bindable Operators
For instance,hat the purpose of the STORE reserved word is to define a binding for storing (assigning) a component to a collection using the selector notation [] on the left side of an assignment;
dynArrayItem [n] := value; (* becomes STORE (myDynArray, n, value) *)
the purpose of the RETRIEVE notation is to define a binding to the selector notation [] used in an expression for retrieval and return of a value from a collection such as an array.
dynArrayItem := arrayItem [n];
(* becomes dynArrayItem := RETRIEVE (myDynArray, n) *)
and the purpose of the REMOVE notation is to define a binding for deleting such an item from the collection.
dynArrayItem [n] := NIL; (* becomes REMOVE (myDynArray, n) *)
All three cases are here illustrated using an index n, but the index in collections other than dynamic arrays is likely to be a key value so a key field may be searched.
Some bindings are forbidden and cannot be placed in a blueprint. Types provided by pseudo-module UNSAFE are not convertible. No conversion operator bindings may be defined that convert to or from UNSAFE types. To transfer the value of an UNSAFE type to another type, or to transfer a value to an UNSAFE type, the UNSAFE.CAST operation must be used.
One of the bindables is FOR.
Suppose we define a data structure LinkedList, in a library ADT, where we have:
TYPE
nodePoint = POINTER TO Node;
node =
RECORD
myData : MyDataType;
toPoint, fromPoint : nodePoint;
END;
procType = PROCEDURE (VAR aList : nodePoint);
VAR
listH, listT : nodePoint; (* head and tail pointers *)
PROCEDURE ProcessNode (VAR aList : nodePoint);
BEGIN
(* ProcessStatementSequence *)
END ProcessNode;
and would like to process such lists using a FOR loop
FOR key IN listH DO ProcessNode END;
or, starting at the tail and expressing it more generally
FOR key IN listT– DO StatementSequence END;
where we maintain the list in such a way that the fromPoint of the first item and the toPoint of the last item were NIL. Now, clearly, such a list can be processed in either direction–from last to first or from first to last. In order to perform the processing this way, we need a prototype blueprint, possibly the supplied one for collection, but that requires conferment modules to define the constant bidirectionalForLoop in a line such as:
CONST * supportsBidirectionalForLoop : BOOLEAN;
This is unnecessary in numeric scalar or indexed collections, blueprints, for bidirectionally of FOR loops is implied in such cases, but for a non-indexed collection it is, because the signature of a bidirectional FOR loop binding is different from that of one where directionality is unknown.
In this particular case, to be conformant, we would then place in the ADT module for LinkedList the line:
CONST * supportsBidirectionalForLoop = TRUE;
The logic, illustrating with the two procedure signatures is:
supportsBidirectionalForLoop ->
PROCEDURE [FOR*] bidiForIterator ( a : ADT; statementSeq : ProcType; order : CHAR );
NOT supportsBidirectionalForLoop ->
PROCEDURE [FOR] forIterator ( a : ADT; statementSeq : ProcType );
in order to satisfy the prototype requirement. The implementation of the latter could look like this:
PROCEDURE forIterator ( VAR list : nodePoint; ForLoopBodyProc : ProcType; ascending : BOOLEAN);
BEGIN
IF list # NIL THEN
REPEAT
forLoopBody (list); (* process current node *)
IF ascending THEN
list := list^.toPoint
ELSE
list := list^.from Point
END;
UNTIL list = NIL;
ELSE RETURN
END
END forIterator;
Now, under the hood, a program statement having such a FOR loop could be synthesized by the compiler in two parts as:
PROCEDURE forLoopBody ( VAR list : nodePoint) );
BEGIN
(* ProcessNode or statementSeq as the case may be *)
END forLoopBody;
and second, a specific instance of the forIterator procedure with the forLoopBody as actual parameter in place of the formal parameter ForLoopBodyProc. In a program, all the syntaxes FOR var IN…, FOR var++ IN… and FOR var– IN… would be legitimate.
The syntax is called a pragma or compiler directive. This particular one instructs the compiler to place the code of the procedure wherever it encounters what would otherwise be a call to a separate piece of code. The executable will be larger but faster. An appendix covers some of the other pragmas.
In some structures, descending order would not make sense, and FOR would simply traverse in the manner appropriate for the structure. In that case, the ADT has:
CONST * supportsBidirectionalForLoop = FALSE;
PROCEDURE [FOR] forIterator ( VAR list : nodePoint ; statementSeq : ProcType );
Note that the FOR procedure has a different signature in this case, as the ascending parameter is not only unnecessary, but an error will be generated if one writes FOR var– IN or FOR var++ IN. Indeed, without looking at the implementation code, there is no way to know in what order the ADT will be traversed. To illustrate, suppose we have an ADT Tree and we wish to bind FOR to an in-order traversal, that is, recursively left, parent, right, then assuming:
TYPE
TreeNode =
RECORD
data : MyDataType;
parent, lchild, rChild : TreeNodePoint;
END;
TreeNodePoint = POINTER TO TreeNode;
VAR
tree : TreeNode;
then the implementation would also not require the BOOLEAN parameter, and would have:
PROCEDURE forIterator ( VAR tree : TreeNodePoint ; statementSeq : ProcType );
BEGIN
IF tree # NIL THEN
forIterator (tree^. lchild, statementSeq);
statementSeq (tree);
forIterator (tree^. rChild, statementSeq)
ELSE RETURN
END
END forIterator;
Options for pre-order and post-order could be achieved by creating one procedure for each, and exporting a procedure to select the default and current behaviour for the forIterator procedure. Alternately, if desired, the supportsBidirectionalForLoop constant could be set to TRUE and reverse-order traversals set up as well (right before left).
Access Bindings
Consider a second example of ADT bindings that makes the programmer’s life easier. In previous dialects of Modula-2, brackets were used for random-access to the elements of an array. In R10, the [] is a more general random accessor, and may be bound–when it appears in an l-value as RETRIEVE or when it appears as an r-value as STORE, though the latter can binding only be provided if the constant isMutable is TRUE.
Suppose we extend the above example with the following assumptions:
The Type MyDataType has a field called key, which is a scalar type (so < is bound)
The trees are binary sorted trees using the algorithm "left is less".
Then, we would have, in the blueprint:
PROCEDURE [STORE];
PROCEDURE [RETRIEVE];
meaning that Specializations of this blueprint must always require/supply a binding to STORE and RETRIEVE. Then in the definition module we could supply:
PROCEDURE [RETRIEVE] nodeWithKey ( key : keyType ) : TreeNodePoint;
(* Returns a pointer to the node having the specified value in the key field of the data if found, and NIL if not found*)
PROCEDURE [STORE] replaceOrInsertNode ( nodePoint : TreeNodePoint);
(* Looks for the node whose key field is the same as that of the supplied node, and if found, replaces it. If not fund, inserts it so that the tree remains sorted. *)
We leave the implementation as an exercise for the reader.
This is just a taste of what can be done using blueprints. But 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.
–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/22e8ee99c1cd1fc276771cd743fd195c022a863a/_STANDARD_LIBRARY/BLUEPRINTS/BlueprintHierarchy.txt?at=default
More links, Wiki: http://www.modula-2.net
p1 ISO Modula-2 for the Mac: http://modula2.awiedemann.de/