22

To belatedly celebrate the release of Go 1.18, I ask the question: what was the first programming language with support for generics?

For concreteness (to prevent anyone trying to weasel out with ‘what is generics anyway’), the central examples should meet the following criteria:

  • the language should be statically-typed, with variables given an unchangeable concrete type like number, string, etc. (dynamically-typed languages are disqualified);
  • despite the above, it should be possible to declare in user code a function or a data type referring to an abstract type, to be specified at use site (parametric polymorphism);
  • such a declaration should be parsed into a syntax tree; the compiler should be able to identify at least syntax errors before such an instantiation (textual substitution macros are disqualified).

What was the first language with this feature?

user3840170
  • 23,072
  • 4
  • 91
  • 150

4 Answers4

22

That was Algol-60.

The example given here is effectively a generic function.

It is unclear from the Algol-58 report if it intended to allow generic functions.

It states:

The values assigned to, or computable by, the actual input parameters must be compatible with type declarations concerning the corresponding formal parameters which appear in the procedure.
For actual output parameters, only type declarations duplicating given type declarations for the corresponding formal parameters may be made.
Array declarations concerning actual parameters must duplicate, in corresponding subscript positions, array declarations referring to the corresponding formal parameters.

Thus it appears that the types of formal parameters had to be declared, and it is Algol-60 rather than Algol-58 which actually satisfies the criteria of the question.

If you consider single-expression "functions", taking an example from the Algol-58 report,

I(Z) :=Z + 3 × y

satisfying your criteria, then the answer may be Algol-58 or even FORTRAN, depending on the year in which a similar construct appeared in FORTRAN.

Leo B.
  • 19,082
  • 5
  • 49
  • 141
  • 1
    For the curious, the relevant part of the Algol 60 report is reproduced in my earlier question on the specification-parts of procedures. – dave Apr 16 '22 at 13:55
  • Algol 60, as defined in the Revised Report, had relatively well-known problems for the implementer, from "too much genericity" -- e.g. the impossibility of knowing at the call site, in the absence of a parameter specification on the procedure declaration, whether the 42 in foo(42) was eventually going to be used as an integer or a label. – dave Apr 16 '22 at 14:31
  • "or even FORTRAN, depending on the year in which a similar construct appeared in FORTRAN" But modern Fortran still doesn't have generic programming of the kind that would fulfil the OP's criteria 1 2 3, so I'd be surprised if one of the old FORTRAN standards supported this? – veryreverie Apr 16 '22 at 14:54
  • The Algol-60 example you provide allows a single function body to be used with parameters of any type, producing errors if the parameters are incompatible with the operations inside the function.Q: does Algol-60 have a way to have different function bodies depending on types, like “numeric”, integer, single or double, strings. – Krazy Glew Apr 16 '22 at 18:39
  • The language does not; but this does not prevent the implementation from so doing. You can often but not always deduce a lot about the required nature of the arguments from the body of the procedure (numeric, boolean, array, string, label -- not all of these are 'types' in Algol 60) and thus I would guess enforce compile-time conformance. The language has no separate compilation facilities, so 'all' information is available. – dave Apr 16 '22 at 20:05
  • @KrazyGlew No, and Algol-60 did not have function overloading either. – Leo B. Apr 17 '22 at 02:19
  • @LeoB: lacking function overloading or even type predicates to handle different types in the same function in different code paths would IMHO disqualify Algol-60’s approach from being called “generic” comparable to Ada’s approach. Unless of course they actually used to term “generic”. – Krazy Glew Apr 17 '22 at 13:48
  • FWIW, Whetstone Algol doesn't detect type misatches until runtime -- see this list. (Doesn't mean it couldn't if it wanted - you'd have to read Randell&Russell to answer that - but I suppose that fits its brief of being a fast compiler for small jobs and for the development phase of a program). – dave Apr 17 '22 at 15:01
  • @KrazyGlew Function overloading is orthogonal to generics. As far as the same source code of a function served different combinations of argument types, requiring separate instantiations by the compiler, it can be considered a generic function, regardless of the terminology. A rose by any other name would smell as sweet. – Leo B. Apr 18 '22 at 21:30
  • @LeoB but “generics“ with multiple independent function bodies are better for SW maintenance, separate compilation, etc. Maybe just terminology, but I was surprised by your usage. Generics in Ada and C++ are very useful for large projects, but Algol-60s is not. Maybe “Generous with overloading = good”, but “generics without overloading is not as good.” – Krazy Glew Apr 18 '22 at 21:54
  • @LeoB: if “generic” means just “parameter types specified later”, then any dynamic programming language like LISP is generic - and LISP in 1958 is older than Algol-60. For Algol-60 to have priority you may require the language to support strong types with an escape hatch, so that a function body errors can be detected at compile or link time rather than run time. The term “generic programming” seems to be 1988 Musser and Stepanov, and is applied retroactively. Ada used the term “generic”. – Krazy Glew Apr 18 '22 at 22:10
  • @KrazyGlew Algol-60 is considered a strictly typed language; syntax errors in function bodies were detected at compile time. I've verified that by introducing a syntax error in the function body and removing its invocations. It did not compile. My answer satisfies the requirements as given in the question. – Leo B. Apr 18 '22 at 22:34
17

For completeness: Full parametric polymorphism ("type variables") was invented 1934 by Haskell Curry 1934 in form of the so-called Combinatory Logic, and 1940 by Alonzo Church in form of the typed lambda calculus, and both turn out to be equivalent, and also equivalent to computability in the Turing-Machine sense.

While these are not programming languages in the same way a Turing Machine is not a computer, they form the core of the ML family of functional programming languages. The original ML was developed by Robin Milner and others in the early 1970s.

But just like you can "program" a Turing machine with pencil and paper, you could also "program" in the original calculi (and manually construct the syntax tree, if so desired).

(Now you need to decide if "earliest" should apply to the invention, or to the first implementation).

Also, if you interpret the "parametric" in parametric polymorphism as "needs type variables that act as parameters" (which is the way it was first defined by Strachey in 1967), then I am not sure if Algol call-by-name qualifies.

dirkt
  • 27,321
  • 3
  • 72
  • 113
  • Was ML statically typed? I don't know anything about that language. – dave Apr 16 '22 at 14:39
  • 9
    @another-dave ML is the veritable poster child of a statically typed language... including static (compile-time) type inference using Hindley-Milner. Unlike Lisp, which is based on the untyped lambda-calculus. – dirkt Apr 16 '22 at 15:26
  • You can program just fine in lambda calculus. In pure lambda calculus the principle is to determine a normal form and return that. The normal form can be given an interpretation. A neuman machine can be given a precise mathematical definition and then one can prove theorems about it just as you can for lambda calculus. Typically lambda is better for proofs in algebra and neuman is better for implementation in hard ware. But there have even been hardware Lisp machines. – Ponder Stibbons Apr 18 '22 at 03:55
  • 1
    @PonderStibbons Yes you can program in the Lambda Calculus but it is not optimised for speed. For example, you do arithmetic by repeatedly adding and subtracting one to/from numbers. If you've got Swift installed, there's a lambda calculator implementation here https://bitbucket.org/jeremy-pereira/lambdacalculus/src/master/ – JeremyP Apr 19 '22 at 08:27
  • @JeremyP how you do arithmetic in lambda calculus depends on how you encode the numbers. You can for example encode the numbers in a version of binary, and then it is fine for speed. The example of addition by counting up and down is just an inefficient but simple encoding used for impractical examples to show the principles. Just like in any language, the data structures affect the optimal algorithms. You could multiply by repeated counting in C too, if you did not want to have the answer this century. – Ponder Stibbons Apr 20 '22 at 10:36
  • @PonderStibbons Why would you want to use anything except Church Numerals to encode numbers in Lambda Calculus? – JeremyP Apr 22 '22 at 07:54
  • @JeremyP Efficiency. e.g. You can represent 42 as a set of two sets (((), (), (), ()), ((), ())) >- (x, y) -> len(x) * 10 + len(y) -> 40 + 2. You can represent positional numbers in any base, that way. Certainly a lot more compact than the Church numbers. The arithmetic algorithms are more complex, but also faster. Some LISP implementations have actually used this method (e.g. Paul Graham's Arc). – RETRAC Apr 23 '22 at 19:55
  • @RETRAC Efficiency is not a consideration in the Lambda Calculus. It's a mathematical model designed to make reasoning about computing easier. You can program in Lambda Calculus but it would be incredibly difficult to do anything non trivial. – JeremyP Apr 25 '22 at 07:59
9

CLU was contemporaneous with ML, with ML coming out in 1973 and CLU starting being developed in 1973 and released in 1975. Its paramaterized types were generics in the sense of C++, Ada and Go, unlike ML which does full program type inference, and is the more direct ancestor to the generics in those languages.

prosfilaes
  • 193
  • 6
8

You have to be very careful about the term generics - it can mean different things depending on context.

The link given by @LeoB is an interesting one. Not sure how many Algol60 compilers implemented it. The ones on the ICL1900s definitely didn't - they would moan if you didn't declare the argument types. Would have been pretty weird with Jensen's device anyway.

In Ada (appx 1979) and python, generics are the same as templates in C++/Java/C#. I think the golang ones are this type.

In VHDL (appx 1987), generics allow the entities to be parameterized during component initialization: a bit like providing arguments to a subroutine.

cup
  • 2,525
  • 1
  • 9
  • 21
  • I just checked on KDF9 Whetstone Algol -- it too insists on the specification part being present. – dave Apr 16 '22 at 13:56
  • 2
    Ada generics are similar to those in Java and C# in that generic bodies can be fully type checked at compile time. Unlike totally cool generics in C++ which use duck typing at instantiation time to provide amazing flexibility (and limit the amount of type checking available when compiling the body). Nevertheless: Ada generics are also very powerful because the native type system allows things like enforced tag unions, unions with fields which depend on a record parameter (e.g. array sizes), and tasks as fields of records. These things interact nicely & powerfully especially with generics! – davidbak Apr 16 '22 at 17:48
  • 3
    @davidbak C# generics are actually very different from Java. They may share more in common with C++ than you think. – PC Luddite Apr 16 '22 at 22:03
  • If you say so. Though they're implemented differently from Java - the VM understands generics directly vs. through erasure (with its problems) - I still believe C# and Java generics are much closer to each other then C#'s are to C++ templates, from the POV of what code you need to have available before you can strongly type the body. Point me please to a description somewhere of why this is wrong, thanks! – davidbak Apr 17 '22 at 01:35
  • 2
    @PCLuddite C# generics do not share much with C++ templates. C# generics are compiled once, after which the IL serves as a fixed “template” (for lack of a better word) from which specific types are generated by filling in the holes. All reference-type-only specializations even share the exact same code and only specific Type instances are created. Things like specialization or deriving from type parameters are impossible. C++ templates can be at best pre-compiled to abstract syntax trees and compiled on a case by case basis, sharing essentially nothing between different specializations. – WimC Apr 17 '22 at 09:17
  • The Algo-60 answer saved the question; otherwise we would have to admit the C generics that were synthesized by clever use of the preprocessor. – Joshua Apr 18 '22 at 02:09
  • @WimC: Are you sure about the inability of C++ to use the same code for all reference types? The documentation for even my ancient compiler says it can do so at link time by deduplicating identical function bodies. – Joshua Apr 18 '22 at 02:12
  • @Joshua For C++ templates that may be possible in some very specific cases. For C# generics it is a requirement. – WimC Apr 18 '22 at 06:14
  • @Joshua C++ compilers generally do not do automatic type erasure, which is a main cause of size bloat with templates. – jamesdlin Apr 18 '22 at 16:59