Why don't imperative languages like C or Go support Haskell-like parametric polymorphism?

Question

Why don't imperative languages support parametric polymorphism as powerful as whats in Haskell and OCaml?

More specifically if I call a function foo(x) that internally calls bar(x) which internally calls baz(x), what prevents the type of parameter x from being inferred all the way down?

Is it possible to design an imperative language (like C or Go) with this behavior or must the language be functional?

Question: Does there exist a type system allowing for parametric polymorphism as powerful as Hindley-Milner, but suited for imperative languages and not functional languages. If such a type system exists what are it's advantages and disadvantages? I'm wondering if it can be done rather than why it hasn't been done.

Answer 1

The real answer is that the designers of those languages chose not to include it.

It's certainly technically possible. As has been said in the comments, Rust does, Java does, C# does, etc. However, there are some difficulties.

The first is in the choice of impelemtation strategy. Polymorphism is easy if you're working with Lambda Calculi and looking only at what reductions work. But when you want actual code that runs on a machine, there are two main strategies, each with their own tradeoffs:

• Monomorphization: For each specialization of your polymorphic function that's used, you make a specialized copy of it in the machine code emitted. This option is great when you're using a language that actually emits machine code, and tends to be fast, since you can optimize the different versions of your code. But, it tends to increase the size of your program.
• Pointers: The main reason you can't just use a function polymorphically is that you might give it arguments of different size, so when it's looking things up on the stack, it doesn't know their offsets. But if you always give it pointers to its arguments, then it can lay things out nicely. This way is simpler, but has slowness from an extra layer of indirection.

As for why the particular languages didn't use it, for C it's mostly historical. It wasn't really a mainstream thing when it was made, and it hasn't made its way into the main language. For Go, the decision has been quite controvertial, but again their main goals were simplicity, concurrency and code whose performance was easy to reason about.

Also, polymorphism breaks type soundness in the presence of mutable variables, which is why Rust only allows polymorphic functions, and ML has the value restriction.

Answer 2

As others have pointed out, there is nothing preventing an imperative language from using something similar to the Hindley-Milner type system and providing parametric polymorphism. I should point out that something very similar can actually be done in C, through use of the _Generic keyword which provides compile-time polymorphism / type inference. In the following program, the "function" foo (actually a macro definition) calls bar and then baz which infer the types all the way down. At that point there is an implementation for each base type we care about.

#include <stdio.h>

#define foo(x) (printf("calling foo\n"), printf("%s\n", bar(x)))
#define bar(x) (printf("calling bar\n"), baz(x))
#define baz(x) _Generic(x, int : "int", char* : "char*", void* : "void*")

int main() {
    foo(42);
    foo("hello");
    foo((void*)0);
    return 0;
}

/* output:
calling foo
calling bar
int
calling foo
calling bar
char*
calling foo
calling bar
void*
*/