DEFINITION MODULE Items; (*============================================================== Version : 1.0 Sat, Mar 4, 1989 C. Lins Compiler : JPI TopSpeed Modula-2 Component: Structure - Generic Item Types INTRODUCTION This module provides the abstract data type, Item, which has the operations of Assignment (:=), (In)Equality (=,#), Comparison (<,<=,=,#,>=,>), Disposal, and iterator support routines. Actual routines providing these facilities must be either imported from the predefined ItemOperations module (for the standard types) or be provided by the programmer. REVISION HISTORY v1.0 Sat, Mar 4, 1989 C. Lins Initial JPI implementation. INTERFACE DESIGN ISSUES The primary issue is to provide generic facilities. In order to represent a generic data type one must have available operations equivalent to the standard operations for assignment (:=), (in)equality comparison (=,#) and for ordered data types, the relational operators (<,=,>). These are the minimum operations that must be available for having a functional data type. The standard Modula-2 facilities for these operations on an opaque type would yield semantics where one would assign and compare the opaque type itself, this typically being a pointer type. Since we wish to allow non-pointer types as legitimate values for an item, using the standard operators would suffice for this purpose. But we also allow wish to allow the use of abstract data structures and dynamically allocated variables as items. In this case the standard operators would operate on the ADDRESS of or the POINTER TO the value of an item instead of the value itself. This is sufficient for (in)equality comparisons, but assignment of pointer types results in sharing of the pointer, not copying of the value. Furthermore, relational comparisons of < or > are meaningless since we only have the ADDRESS of the value, not the value itself, and Modula-2 does not allow these operations on opaque types anyway. REFERENCES [1] K. John Gough, ╥Writing Generic Utilities in Modula-2╙, Journal of Pascal, Ada, and Modula-2, Vol. 5 (3), May/June 1986, pp. 53-62. Proprietary Notices Copyright (C) 1989 Charles A. Lins. All rights reserved. ==============================================================*) FROM Relations IMPORT (*--Type*) Relation, RelOp; (* This module provides support for generic data items. This is accomplished by providing an opaque type, ╥Item╙, representing an arbitrary data type. The advantage of this technique is in allowing the creation of modules that can manipulate generic data structures with a minimum of knowledge about the actual data being manipulated. Thus, a single module is needed to implement specific forms of a data structure. Plus the module need only be concerned with actual implementation issues regarding that structure. For example, there need be only one unbounded stack module, one bounded stack module, etc. If necessary, type-specific modules can be built on top of the generic module. Of course, there are constraints that must be placed on the client module(s) to insure proper usage of a generic item. These are listed below: 1. The actual data type mapped to an Item must be compatible with SYSTEM.ADDRESS. Specifically, the relation SIZE(DataType) <= SIZE(SYSTEM.ADDRESS) must be true. If this condition is not met, (e.g., a record or array structure), then the client module must use a pointer to the actual data. 2. Modula-2 supports only a limited number of the standard operations for opaque types. These are assignment (:=) and the test for (in)equality (=,#). The relational operators <, <=, >, and >= are not supported for opaque types. This restriction means that when a generic module requires relational operators, the client module must provide this facility to the generic module. *) TYPE Item; (*-- The generic data type *) CONST NullItem = Item(NIL); (*-- An empty value for an item *) (*-- CONSTRUCTORS * AssignProc (in Item) out Item Defines a generic function procedure type representing the equivalent semantics as the standard Modula-2 assignment operator. A generic module must have a mechanism for assigning generic items to efficiently implement the standard Assign operation. For all of the simple data types (CHAR, INTEGER, CARDINAL, etc.) the assignment operator suffices to accomplish this goal. But for dynamically created items, using := would result in copying pointers to the actual data. This is undesirable when the intended effect is to make a copy of the data itself. For this reason, this routine template is provided. * DisposeProc (inout Item) Disposal defines a generic procedure type (for which an actual procedure must be provided) that will deallocate any and all dynamically allocated resources that may be associated with a given instance of an Item. Use of this routine will prevent the creation of dangling pointers (a.k.a. garbage) for items created using NEW or ALLOCATE when these items are released by a generic module. * NoAssignProc Defines a procedure ╥constant╙ representing the standard Modula-2 assignment operator, :=, which cannot be used as a procedure type parameter. * NoDisposeProc Defines a procedure ╥constant╙ representing disposal of items statically allocated on the stack. This may be used for primitive data items CHAR, INTEGER, etc. It is more efficient to test for an empty disposal routine rather than forcing the client to provide a disposal routine that does nothing. --*) TYPE AssignProc = PROCEDURE ( Item (*-- in *)) : Item (*-- out *); TYPE DisposeProc = PROCEDURE (VAR Item (*-- inout *)); CONST NoDisposeProc = NULLPROC; CONST NoAssignProc = NULLPROC; (*-- SELECTORS * EqualProc (in Item, in Item) out BOOLEAN A generic function procedure type (for which an actual procedure must be provided) that yields the equivalent semantics as the standard Modula-2 relational operators for simple data types. * NoEqualProc Defines a procedure "constant" representing the standard Modula-2 equality operator, =, which cannot be used as a procedure type parameter. --*) TYPE EqualProc = PROCEDURE ( Item (*-- in *), Item (*-- in *)) : BOOLEAN (*-- out *); CONST NoEqualProc = NULLPROC; (*-- * CompareProc (in Item, in Item) out Relation A generic function procedure type (for which an actual procedure must be provided) that yields the equivalent semantics as the standard Modula-2 comparison operator establishing the ordering relationship for simple data types. A routine of this type attempts to answer the question "What is the ordering relation between the first (or left) operand and the second (or right) operand?" * RelationProc (in Item, in Relation, in Item) out Boolean A generic function procedure type (for which an actual procedure must be provided) that yields the equivalent semantics as the standard Modula-2 ordering relations used in comparisons to evaluate the existence of a given ordering relationship between (compatible) data types. A routine of this type attempts to answer the question "Does the ordering relation between the first (or left) operand and the second (or right) operand match the given relation?" * RelOpProc (in Item ,in RelOp, in Item) out Boolean Same as RelationProc above, except that the full set of relational operators are allowed, e.g., <, <=, =, #, >, and >=. --*) TYPE CompareProc = PROCEDURE ( Item (*-- in *), Item (*-- in *)) : Relation (*-- out *); TYPE RelationProc = PROCEDURE ( Item (*-- in *), Relation (*-- in *), Item (*-- in *)) : BOOLEAN (*-- out *); TYPE RelOpProc = PROCEDURE ( Item (*-- in *), RelOp (*-- in *), Item (*-- in *)) : BOOLEAN (*-- out *); (*-- ITERATORS * AccessProc (in Item) Defines a generic procedure type (for which an actual procedure must be provided) that allows read-only access to a generic item from within the standard iterator operation ╥Traverse╙. * ChangeProc (inout Item) Defines a generic procedure type (for which an actual procedure must be provided) that allows read-write access to a generic item from within the standard iterator operation ╥TravChange╙. * LoopAccessProc (in Item) out Continue Defines a generic procedure type (for which an actual procedure must be provided) that allows read-only access to a generic item from within the standard iterator operation ╥LoopOver╙. The actual routine matching this declaration may control continuation of the iteration through the function result ╥Continue╙. * TRUE continues the iteration * FALSE terminates the iteration These two results account for the renaming of the BOOLEAN function result, clarifying the semantic meaning of the result. * LoopChangeProc (inout Item) outContinue Defines a generic procedure type (for which an actual procedure must be provided) that allows read-write access to a generic item from within the standard iterator operation ╥LoopChange╙. The actual routine matching this declaration may control continuation of the iteration through the function result ╥Continue╙. * TRUE continues the iteration * FALSE terminates the iteration These two results account for the renaming of the BOOLEAN function result, clarifying the semantic meaning of the result. --*) TYPE AccessProc = PROCEDURE ( Item (*-- in *)); TYPE ChangeProc = PROCEDURE (VAR Item (*-- inout *)); TYPE Continue = BOOLEAN; TYPE LoopAccessProc = PROCEDURE ( Item (*-- in *)) : Continue (*-- out *); TYPE LoopChangeProc = PROCEDURE (VAR Item (*-- inout *)) : Continue (*-- out *); END Items.