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?

Improve this question

4 Answers 4

Reset to default
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.

Improve this answer
13
  • 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
    Commented Apr 16, 2022 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
    Commented Apr 16, 2022 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
    Commented Apr 16, 2022 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
    Commented Apr 16, 2022 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
    Commented Apr 16, 2022 at 20:05
18

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.

Improve this answer
8
  • Was ML statically typed? I don't know anything about that language.
    – dave
    Commented Apr 16, 2022 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
    Commented Apr 16, 2022 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
    Commented Apr 18, 2022 at 3: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 bitbucket.org/jeremy-pereira/lambdacalculus/src/master
    – JeremyP
    Commented Apr 19, 2022 at 8: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
    Commented Apr 20, 2022 at 10:36
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.

Improve this answer
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.

Improve this answer
9
  • I just checked on KDF9 Whetstone Algol -- it too insists on the specification part being present.
    – dave
    Commented Apr 16, 2022 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
    Commented Apr 16, 2022 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
    Commented Apr 16, 2022 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
    Commented Apr 17, 2022 at 1: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
    Commented Apr 17, 2022 at 9:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .