Parametric polymorphism and unboxed representations

October 9, 2013 - Tagged as: en, cpp, java.

This post was written 5 months ago – I just found it in my Github Gist archive and realized it’s not published. I’m publishing it now.

It’s just occurred to me that we can’t have parametric polymorphism for unboxed values, unless that unboxed values share same layout in memory, or you duplicate polymorphic definition for each instance. This may be obvious for most of you but I just realized this while working on a Java project and found it interesting.

I think this is also the reason why we can’t instantiate generics in Java with primitive types.

Here’s an explanation:

Let’s think this C++ code:

struct test2
{
  int a, b;
  test2(int a, int b) : a(a), b(b) {}
};

struct test3
{
  int a, b, c;
  test3(int a, int b, int c) : a(a), b(b), c(c) {}
};

void f2() {}

template<typename T>
T f3(T t)
{
  t.a = 20;
  return t;
}

int main()
{
  test2 t2(1, 2);
  test3 t3(1, 2, 3);
  f3<test2>(t2);
  f3<test3>(t3);
  return 0;
}

The key thing to realize here is that I’m passing parameter by value, ie. values are copied to function stack frame. But this function is still polymorphic on parameter type. This is possible in C++ because for each distinct instance of f3, a specialized code will be generated. To observe this, I put a breakpoint to that f3 function and looked to disassembly output.

        18	T f3(T t)
0x400af6  <+0x0000>         push   rbp
0x400af7  <+0x0001>         mov    rbp,rsp
0x400afa  <+0x0004>         mov    QWORD PTR [rbp-0x10],rdi
        19	{
        20	  t.a = 20;
0x400afe  <+0x0008>         mov    DWORD PTR [rbp-0x10],0x14
        21	  return t;
0x400b05  <+0x000f>         mov    rax,QWORD PTR [rbp-0x10]
        22	}
0x400b09  <+0x0013>         pop    rbp
0x400b0a  <+0x0014>         ret

And this is for second call:

        18	T f3(T t)
0x400b0b  <+0x0000>         push   rbp
0x400b0c  <+0x0001>         mov    rbp,rsp
0x400b0f  <+0x0004>         mov    rdx,rdi
0x400b12  <+0x0007>         mov    eax,esi
0x400b14  <+0x0009>         mov    QWORD PTR [rbp-0x20],rdx
0x400b18  <+0x000d>         mov    DWORD PTR [rbp-0x18],eax
        19	{
        20	  t.a = 20;
0x400b1b  <+0x0010>         mov    DWORD PTR [rbp-0x20],0x14
        21	  return t;
0x400b22  <+0x0017>         mov    rax,QWORD PTR [rbp-0x20]
0x400b26  <+0x001b>         mov    QWORD PTR [rbp-0x10],rax
0x400b2a  <+0x001f>         mov    eax,DWORD PTR [rbp-0x18]
0x400b2d  <+0x0022>         mov    DWORD PTR [rbp-0x8],eax
0x400b30  <+0x0025>         mov    rax,QWORD PTR [rbp-0x10]
0x400b34  <+0x0029>         mov    edx,DWORD PTR [rbp-0x8]
        22	}
0x400b37  <+0x002c>         pop    rbp
0x400b38  <+0x002d>         ret

So what happened here is two new functions is generated from the definition, one with type test2 f3(test2) and one with type test3 f3(test3). This gives a great opportunity, for instance, we can have this function:

#include <iostream>

template<typename T>
T someFun(T arg1, T arg2)
{
  return arg1 + arg2;
}

int main(int argc, const char *argv[])
{
  std::cout << someFun<int>(1, 2) << std::endl;
  std::cout << someFun<float>(1.4, 2) << std::endl;

  return 0;
}

..which is impossible to have in Java, without manually overloading the method definition.

(An off-topic but interesting note: I was expecting SP to be set here, but here it’s not set. I think the reason is that the compiler is clever enough to see there is no recursive calls, so no need to set SP, when I added a dummy function call in the middle of f3, SP is got set)

So in a way, C++ generics are gives us the most general way for parametric polymorphism. For any type you instantiated the template with, it generates a specialized definition. And if that definition is accepted by type checker, you’re fine.

This also why we don’t need a template definition like template <class C : HasY>. Because that HasY information is completely redundant. If specialized code is well-typed, than it’s OK.

This is also one of the reasons why compiling C++ programs takes that long.