Would it be possible to add type inference to the C language?

Question

Let's say, we create a reimplementation of C, with the only difference being that types are inferred. Storage classes and modifiers would still need to be given (const, static, restrict etc), and let's restrict our attention to single file C programs for the moment. Could it be done? What are the major impediments?

Some thoughts on what might cause problems with type inference

• structs with the same field name would need to be disambiguated manually
• same for unions with the same field names

• casts would probably need a "from" annotation, something like

  var i = (uint32_t -> uint64_t) *some_pointer;
  

These problems would require a bit of user annotation, but shouldn't be too burdensome, is there some killer issue that blows this idea out of the water?

Edit: To clarify, I'm not talking about adding generics or parametric polymorphism, just type inference for existing C types.

Edit 2014: Anyone interested in this concept may want to look into Rust

Answer 1

C promotes some types automatically, which complicates things. But to be workable, you need to have a couple additional differences from C as it exists: right now, the standard still supports to some extent legacy K&R C programs, and that requires that unspecified types be handled in particular ways. (See, for example, the rules for function parameters in the absence of prototypes. It also used to be possible to specify functions and variables with no type, and they would be defaulted to (int). (How for variables? Storage class only. static foo;)) All of this legacy type handling would have to be removed before a new implied types mechanism could be added.

Answer 2

GCC 5.1 supports:

• __auto_type extension, analogous C++11 auto

• typeof extension, analogous to C++11 decltype

  /* Same as: double j = 0.5; */
  typeof(1 + 0.5) j = 0.5;
  assert(j == 0.5);
  

  Linux kernel example: How does the typecheck macro from the Linux kernel work?

• _Generic C11 keyword: Syntax and Sample Usage of _Generic in C11

  __auto_type i = 1;
  assert(_Generic((i), int: 1, default: 0));
  

Answer 3

To infer types of polymorphic functions would require dramatic extensions to the C type system. Example

length(p) {
  if (p == NULL) return 0;
  else return 1 + length(p->next);
}

This code has to work on any pointer to a struct (or a union) with a next field. You could check out row polymorphism, but at the very least, your new type system is going to have to be far more expressive than the C type system.

Another pressing problem is the overloaded + operation. What type does it default to? Do you want it overloaded at any numeric type, like Haskell or C++? If so, more big extensions to the type system.

The larger lesson is don't do this. The merits of C (as a language, apart from the many fine APIs available in C) are

• You have total control over the representation of your data.
• Any person inspecting the source code can easily predict time and space costs.

This agenda isn't really compatible with polymorphism, and polymorphism is a primary benefit of type inference. If type inference is what you want, pick one of the many fine languages (F#, Haskell, ML) that support it natively.

Answer 4

It is possible to do some type inference in C. Take a look into this tool: http://cuda.dcc.ufmg.br/psyche-c. You can type part of a program there, and it will reconstruct the missing type declarations. For instance, if we feed it with a variation of Norman's program:

int length(T p) {
  if (p == NULL) return 0;
  else return 1 + length(p->next);
}

Then psyche-c finds these declarations:

#include <stdint.h>
#define NULL ((void*)0)
typedef int bool;
bool false = 0;
bool true = 1;
typedef  struct T {struct T* next;}* T;

This kind of type reconstruction is useful for code completion, for instance.

Answer 5

C has a complicated set of rules regarding type promotion and conversion that people find confusing even when they can actually see the types they're dealing with. I suspect that even if C had type inference, it would be necessary to declare types to prevent ridiculous mistakes every third function.

Answer 6

Some situations where, I think, inferred types could not be used:

• pointers need a definite type
• arrays need a definite type
• function parameters need a type

I think it could work for a few cases, mostly simple local variables.

Even something as simple as calculating a checksum needs a definite type

crc8 = 0x00; /* 8 bits; cf uint8_t crc8 = 0; */
crc32 = 0x00000000; /* 32 bits; cf uint32_t crc32 = 0; */

It could be done, for limited use.