5
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Most modern (and many old) imperative languages do, e.g. C#, Java, Swift, Scala, Rust, etc. C is old and hard to change at this point. Go is a bit of a fluke, and it doesn't support parametric polymorphism because Rob Pike didn't want it to. You can find his reasoning elsewhere. $\endgroup$ – Derek Elkins Sep 4 '17 at 17:39
  • 2
    $\begingroup$ @DerekElkins I see an answer here. Also, Rob Pike wanted Go to have a minimal set of features – that's a more neutral point of view. $\endgroup$ – Yuval Filmus Sep 4 '17 at 18:16
  • $\begingroup$ I was expecting a more theoretical and less historical answer; like maybe something about subtype polymorphism or immutability preventing a faster/more powerful type inference system. For example Hindley-Milner supports polymorphic functions but its restrictive (it needs extensions to deal with mutable variables). $\endgroup$ – Zippers Sep 4 '17 at 18:52
  • 1
    $\begingroup$ @Zippers Again, it clearly can be done. I've listed several languages that do so. Also, type systems aren't linearly ordered by "power". $\endgroup$ – Derek Elkins Sep 4 '17 at 20:13
  • $\begingroup$ @DerekElkins What terminology should I use? I'm interested in learning more about type systems. $\endgroup$ – Zippers Sep 4 '17 at 20:59
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "polymorphism breaks type soundness in the presence of immutable variables" -- where can I read more on that? I've been trying to understand why Swift doesn't allow structs to be sub"classed". Beyond implementation issues, I mean. $\endgroup$ – Raphael Sep 4 '17 at 22:39
  • 1
    $\begingroup$ @Raphael that was a typo, it should say mutable variable. A paper on it is here: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5096 $\endgroup$ – jmite Sep 4 '17 at 22:54
  • $\begingroup$ @Raphael The Crystal language has mutability, inheritance, and provides a very expressive type inference system. I have yet to find the name of the algorithm the creators used, but they did name drop The Cartesian Product Algorithm (which deduces types through flow analysis). The algorithms paper does mention that performance can potentially be an issue and discusses inheritance. If anyone knows more details on Crystals inference algorithm, then I'd love to read about it. $\endgroup$ – Zippers Sep 5 '17 at 1:27
  • $\begingroup$ @jmite Is there anything preventing a C-family language from using generics be default? Are there performance implications / scalability problems? $\endgroup$ – Zippers Sep 5 '17 at 19:05
  • $\begingroup$ @Zippers As I said in my answer, there are no inherent barriers. Rust is basically C plus additional type fanciness, and it has polymorphism through monomorphization. But each method has performance implications: monomorphization increases executable size (and thus possibly compilation time), and pointers slows down performance because of extra dereferences. $\endgroup$ – jmite Sep 5 '17 at 20:46
1
$\begingroup$

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*
*/
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.