Topic: structural equivalence vs. name equivalence of data types

topics > computer science > data > Group: data type

type checking

data type by name or tags
data type compatibility
interface type
names as abbreviations for descriptions
object and value equivalence
object serialization
problems with type inheritance
sending an object across a network
type conversion


Do objects have the same type when they have the same structure or the same name?

Two data types are structurally equivalent if they have the same public members and define the same interface. This is important for distributed applications where the same type may have different names. A type is a value of a semantic domain. With name equivalence, you can only ask about equivalence within a program. Referential transparency is lost.

Name equivalence simplifies type testing. Frege argued that equivalence was equivalence between names. For example, a=b conveys information, unlike a=a. With name equivalence, a type has exactly one definition.

Structural equivalence is used in Euclid, Russell, School, and Modula-3. Name equivalence occurs in most other programming languages (e.g., C++ and Java).

Sometimes structural equivalence is by accident. Use traits to distinguish. (cbb 2/01)

Subtopic: structure vs. name up

Quote: is Sameness a relation? a relation between objects? or between names of objects?
Quote: database types must be completely, conveniently, and anonymously defined by their structure [»wongL9_2000]
Quote: formalization of XML Schema using tree grammars; named types and structural types; matching and validation [»simeJ1_2003]
Quote: a validated element must match its type, since validation yields sensible values; consequence of pure named typing [»simeJ1_2003]
Quote: XQuery standardization unanimously accepted pure named typing due to its simplification of formal semantics [»simeJ1_2003]

Subtopic: semantic domain up

Quote: in modern type theory, types are values in a suitable semantic domain; type constructors are maps from this domain into itself [»nelsG_1991]

Subtopic: structural equivalence up

Quote: Modula-3 uses structural equivalence for data types even though Modula-2 used name equivalence [»cardL_1991]
Quote: with structural equivalence, types are referentially transparent
Quote: Euclid type names expand into type definitions; two types the same if same expanded definition [»barnDT3_1978]
Quote: argument and parameter signatures match if identical after transformation using renaming, reordering, and deletion [»demeA3_1979]
Quote: two types are structurally equivalent if their definitions are the same when expanded; i.e., constant expressions replaced by their values, type names replaced by their definitions; infinite if recursive
Quote: with structural equivalence, allow a type expression wherever a type is required
Quote: C++ defines layout compatibility rules for structurally equivalent objects; allows explicit conversions for low-level services
Quote: equality of objects with remote parts must also test the remote parts; e.g., variable size objects [»dehnJC4_1998]

Subtopic: type inference up

Quote: all types may be inferred in CPL; allows any data source to be used as long as the inferred type and actual structure are compatible [»wongL9_2000]

Subtopic: subtype with structural equivalence up

Quote: Modula-3 uses a simple, restricted subtype rule, if T <: U, then every value of T is a value of U; arrays and procedures must be basically the same [»cardL_1991]
Quote: a restricted type matches the base type's structure and may be used everywhere the base type is used [»simeJ1_2003]
Quote: a type is a subtype if every value matches the base type; because of named element typing, verify by regular expressions [»simeJ1_2003]

Subtopic: name equivalence up

Quote: type-compatibility in Russell is independent of the type's definition [»demeA_1978]
Quote: a=a vs. a=b indicates that Sameness is a relation between names of objects; only a=a is a priori [»fregG_1892]
Quote: Oberon types include a pointer to the base type's descriptor; name equivalence of types, not structural equivalence; for type tests/guards [»wirtN9_1989]
Quote: the C++ type system uses name equivalence instead of structural equivalence because it is safer and cleaner; everything has exactly one definition [»stroB_1994]

Subtopic: relationship components up

Quote: equality should ignore components that reflect relationships between objects; e.g., the person sitting on a chair object [»dehnJC4_1998]

Subtopic: type identity up

Quote: values may be members of many types, but Modula-3 objects and traced reference values have an allocated type that is tested by TYPECASE
Quote: two type attributes are compatible if they are the same identifier (with compatible type arguments) [»demeA_1978]

Subtopic: type as operations up

Quote: the type of an object is its operations; a type error occurs when an object does not have a method for a message [»rodrNR8_1993]

Subtopic: type properties, traits, modes up

Quote: use properties to distinguish types that have the same operations; e.g., the property 'LIFO' for type 'stack'; simulate with dummy functions [»rodrNR8_1993]
Quote: modify the behavior of an object with traits, dynamic inheritance, or modes; e.g., distinguish open and iconified windows [»taivA9_1996]

Subtopic: problems with name equivalence up

Quote: with name equivalence, a type only has meaning in a particular program; causes problems for distributed systems and persistent data; simple changes can undo pickled representations
Quote: wrong output despite the conversion of Cobol arithmetic into C [»tereAA11_2000]

Related Topics up

Group: type checking   (12 topics, 392 quotes)

Topic: data type by name or tags (29 items)
Topic: data type compatibility (5 items)
Topic: interface type (50 items)
Topic: names as abbreviations for descriptions (35 items)
Topic: object and value equivalence (60 items)
Topic: object serialization (13 items)
Topic: problems with type inheritance (20 items)
Topic: sending an object across a network (11 items)
Topic: type conversion
(33 items)

Updated barberCB 3/06
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.