The compiler should help with reliability

A few days ago, I learned about a C-like language with a strong emphasis on safety called Cyclone. As I read the documentation, I found the language very interesting: low-level like C with features inspired by ML and Haskell to improve reliability.

I talked about the language on the French programming channel I frequent. One member had used it and said that the language was good and really helped with common mistakes in C. He also mentioned some problems, such as the lack of threads and weak GDB support. Another member wondered about Cyclone: why invent a new language when you can just use lint to find potential problems. I knew of lint, but I’d never used it. Cyclone claimed that it prevented dangling pointers by including the region in which they exist in the type. I wrote a C program to cause a dangling pointer error, and I was surprised to see lint catch it.

However, I don’t believe that lint is as good as having a language with a strong typing system. Lint can only emit warnings, and the programmer is free to ignore them. On the other hand, if the type system finds an error a refuses to build the program, the programmer has no choice but to address it. Here’s something that lint cannot catch:

#include <stdio.h>

void interleave(void **aggregated,
                void **array1,
                size_t size1,
                void **array2,
                size_t size2) {
    while (size1 && size2) {
        *aggregated++ = *array1++;
        *aggregated++ = *array2++;
        size1--;
        size2--;
    }
    while (size1) {
        *aggregated++ = *array1++;
        size1--;
    }
    while (size2) {
        *aggregated++ = *array2++;
        size2--;
    }
}

int main(void) {
    int xs[4] = {1, 2, 3, 4};
    double ys[4] = {1, 2, 3, 4};
    int zs[8];
    size_t i;

    interleave((void **)zs, (void **)xs, 4, (void **)ys, 4);
    for (i = 0; i < 8; ++i) {
        printf("%d ", zs[i]);
    }
    printf("\n");

    return 0;
}

The interleave function intersperses the first array with the elements of the second one. On line 26, I declare ys to be an array of 4 doubles and in the call to interleave on line 30, I try to interleave those values into an array of ints. This is going to fail of course, but gcc remains silent:

$ gcc -Wall -pedantic interleave.c
$

And of course, when we execute the code, it fails:

$ ./a.out
1 0 2 1072693248 3 0 4 1073741824
$

Does lint catch the error? Nope. It does mention something about zs not being completely defined, but no big “hey you got a type mismatch!”

$ splint interleave.c
Splint 3.1.1 --- 03 Nov 2006

interleave.c: (in function interleave)
[... warnings about using size_t as a boolean... ]

interleave.c:30:16: Passed storage zs not completely defined (*zs is
                       undefined): interleave ((void **)zs, ...)
  Storage derivable from a parameter, return value or global is not defined.
  Use /*@out@*/ to denote passed or returned storage which need not be defined.
  (Use -compdef to inhibit warning)

[... warning about interleave not being static... ]

Finished checking --- 5 code warnings

Since neither the compiler nor lint catch the error, it is the programmer’s responsibility to catch it and fix it. In the current example, with less than 50 lines of code, it’s pretty easy to see the problem. In a larger project however, this could slip by and strike at the worst possible time (thank you Mr. Moore!)

With a language with a stronger typing system, this error could easily be avoided. (The example is in Haskell because, despite my best efforts, it seems I don’t know/understand Cyclone well enough to replicate this simple function. Could anyone help me out?)

interleave :: [a] -> [a] -> [a]
interleave [] ys     = ys
interleave xs []     = xs
interleave (x:xs) (y:ys) = x : y : interleave xs ys

Quick explanation: the interleave function takes two arguments¹, both lists of a’s (denoted by the brackets) and returns a list of a’s. a is a type variable: it means that the parameters can be lists of integers or floats or other lists, etc. The two input lists must be of the same type (because they use the same type variable) and Haskell will raise an error and refuse to compile your code if the types don’t match. This means that if we had a list of Ints and a list of Doubles and we tried to interleave them together like we did in the C example, the compiler will tell us.

Software reliability is very important, and all humans are fallible, regardless of what some coders believe. It’s therefore important that the tools we use help us as much as possible to ensure that our programs are going to behave properly.

¹ Not technically true, but good enough to understand the example.