This is a good summary of the history, but there is one small error.
The sentence "Hoare seems to have independently come up with the idea of sum and product types." is not true.
C.A.R. Hoare has first described his proposals in November 1965, in "Record Handling". This followed after a year the proposal of John McCarthy from October 1964, "Definition of new data types in ALGOL x".
Hoare and McCarthy were colleagues in the committee for designing a successor of ALGOL 60, where both proposals have been discussed and Hoare has taken explicitly the concepts of product types and union types (sum types) from McCarthy.
However, instead of using the "Cartesian" keyword used by McCarthy, Hoare has used the older keywords "record" and "record class", taken from COBOL 60, because "record class" and "Cartesian" really were the same method of deriving a new type. The term "record class" of Hoare was shortened to "class" in SIMULA 67, from where "class" has been taken by all object-oriented programming languages.
The proposal of Hoare was explicitly based on the proposal of McCarthy, on COBOL 60 and on the concept of pointers previously introduced in the languages CPL and Euler. However, like in those 2 languages, Hoare used the term "references" for pointers. The term pointer was used for the first time by IBM one year later, when they have added to PL/I a part of the features proposed by Hoare.
To records (named structures in PL/I), record classes (= product types), unions (sum types) and references (named pointers in PL/I) from his predecessors, Hoare has added a few new concepts, e.g. null pointers, enumerations (named finite sets), the operator "new", constructors and destructors (not named such). Overloaded operators had already been proposed by McCarthy.
> Niklaus Wirth uses “discriminated union” why Pascal doesn’t have sum types.
In the referenced paper (Wirth, 1975, An assessment of the programming language PASCAL, ACM), Wirth refers to the "inspect when" statement of Simula 67, which is structurally identical to type discrimination with (exhaustive) pattern matching; so Simula essentially already had something like "sum types" (unified with inheritance). Wirth implemented the same concept in his later Oberon language (which also supports inheritance and offers a WITH statement similar to Simula's "inspect when"). Also Pascal variant records are similar to sum types (even if Wirth didn't use this term); variant records have an explicit tag field, though Pascal doesn't enforce tag nor exhaustiveness checking. Wirth improved this in Oberon, which can be used to meet both key guarantees of sum types.
Hmm, I always thought of "sum type" as abstract/type theoretic and "tagged/discriminated union" as one possible implementation of the concept for a finite memory model.
This is a good summary of the history, but there is one small error.
The sentence "Hoare seems to have independently come up with the idea of sum and product types." is not true.
C.A.R. Hoare has first described his proposals in November 1965, in "Record Handling". This followed after a year the proposal of John McCarthy from October 1964, "Definition of new data types in ALGOL x".
Hoare and McCarthy were colleagues in the committee for designing a successor of ALGOL 60, where both proposals have been discussed and Hoare has taken explicitly the concepts of product types and union types (sum types) from McCarthy.
However, instead of using the "Cartesian" keyword used by McCarthy, Hoare has used the older keywords "record" and "record class", taken from COBOL 60, because "record class" and "Cartesian" really were the same method of deriving a new type. The term "record class" of Hoare was shortened to "class" in SIMULA 67, from where "class" has been taken by all object-oriented programming languages.
The proposal of Hoare was explicitly based on the proposal of McCarthy, on COBOL 60 and on the concept of pointers previously introduced in the languages CPL and Euler. However, like in those 2 languages, Hoare used the term "references" for pointers. The term pointer was used for the first time by IBM one year later, when they have added to PL/I a part of the features proposed by Hoare.
To records (named structures in PL/I), record classes (= product types), unions (sum types) and references (named pointers in PL/I) from his predecessors, Hoare has added a few new concepts, e.g. null pointers, enumerations (named finite sets), the operator "new", constructors and destructors (not named such). Overloaded operators had already been proposed by McCarthy.
Interesting article, thanks for sharing.
> Niklaus Wirth uses “discriminated union” why Pascal doesn’t have sum types.
In the referenced paper (Wirth, 1975, An assessment of the programming language PASCAL, ACM), Wirth refers to the "inspect when" statement of Simula 67, which is structurally identical to type discrimination with (exhaustive) pattern matching; so Simula essentially already had something like "sum types" (unified with inheritance). Wirth implemented the same concept in his later Oberon language (which also supports inheritance and offers a WITH statement similar to Simula's "inspect when"). Also Pascal variant records are similar to sum types (even if Wirth didn't use this term); variant records have an explicit tag field, though Pascal doesn't enforce tag nor exhaustiveness checking. Wirth improved this in Oberon, which can be used to meet both key guarantees of sum types.
Hmm, I always thought of "sum type" as abstract/type theoretic and "tagged/discriminated union" as one possible implementation of the concept for a finite memory model.
Great article, usually many end up only talking about recent history, while this traces much further back to the origins.
See https://news.ycombinator.com/item?id=45461480