Recursively defined data types

Many recent programming languages (ALGOL 68 [1], ELI [2], BASEL [3] ), permit construction of data types defined partly in terms of themselves; for example, a. = struct (X: ref a, Y: int). The interpretation of such type expressions poses some interesting problems in semantics: chiefly, when do two such forms describe the same type? Are a and bin a= struct (X: ref a, Y: Int) and b= struct (X: ref b, Y) the same? If the language has uni en types, is a = union (a, struct (X: ref c, Y: int) ) different from a? The answers to these questions for particular languages are often obscure. In some cases a rather complex algorithmic criterion for equality is posited [4] [5] [8]. The present paper describes a view of data types which permits a reasonably natural treatment of these issues.