A  Porting C code to Cyclone

A.1  Semi-Automatic Porting

1.   #include <stdio.h>
2. 
3.   void foo(char *s) {
4.     printf(s);
5.   }
6. 
7.   int main(int argc, char **argv) {
8.     argv++;
9.     for (argc--; argc >= 0; argc--, argv++)
10.      foo(*argv);
11.  }

  cyclone -port foo.cyc > rewrites.txt

  foo.cyc(5:14-5:15): insert `?' for `*'
  foo.cyc(9:24-9:25): insert `?' for `*'
  foo.cyc(9:25-9:26): insert `?' for `*'

  rewrite -port foo.cyc > rewrites.txt

#include <stdio.h>

__cyclone_port_on__;

void foo(char ?s) { 
  printf(s);
}

int main(int argc, char ??argv) {
  argv++;
  for (argc--; argc >= 0; argc--, argv++) 
    foo(*argv);
}
__cyclone_port_off__;

A.2  Manually Translating C to Cyclone

• Change pointer types to fat pointer types where necessary.
• Use comprehensions to heap-allocate arrays.
• Use tagged unions for unions with pointers.
• Initialize variables.
• Put breaks or fallthrus in switch cases.
• Replace one temporary with multiple temporaries.
• Connect argument and result pointers with the same region.
• Insert type information to direct the type-checker.
• Copy ``const'' code or values to make it non-const.
• Get rid of calls to free, calloc, etc.
• Use polymorphism or tagged unions to get rid of void*.
• Rewrite the bodies of vararg functions.
• Use exceptions instead of setjmp.

Change pointer types to fat pointer types where necessary.

Ideally, you should examine the code and use thin pointers (e.g., int* or better int*@notnull) wherever possible as these require fewer run-time checks and less storage. However, recall that thin pointers do not support pointer arithmetic. In those situations, you'll need to use fat pointers (e.g., int*@fat which can also be written as int?). A particularly simple strategy when porting C code is to just change all pointers to fat pointers. The code is then more likely to compile, but will have greater overhead. After changing to use all fat pointers, you may wish to profile or reexamine your code and figure out where you can profitably use thin pointers.

Use comprehensions to heap-allocate arrays.

Cyclone provides limited support for malloc and separated initialization but this really only works for bits-only objects. To heap- or region-allocate and initialize an array that might contain pointers, use new or rnew in conjunction with array comprehensions. For example, to copy a vector of integers s, one might write:

  int *@fat t = new {for i < numelts(s) : s[i]};

Use tagged unions for unions with pointers.

Cyclone only lets you read members of unions that contain ``bits'' (i.e., ints; chars; shorts; floats; doubles; or tuples, structs, unions, or arrays of bits.) So if you have a C union with a pointer type in it, you'll have to code around it. One way is to simply use a @tagged union. Note that this adds hidden tag and associated checks to ensure safety.

Initialize variables.

Top-level variables must be initialized in Cyclone, and in many situations, local variables must be initialized. Sometimes, this will force you to change the type of the variable so that you can construct an appropriate initial value. For instance, suppose you have the following declarations at top-level:

struct DICT; 
struct DICT *@notnull new_dict();
struct DICT *@notnull d;
void init() {
  d = new_dict();
}

Here, we have an abstract type for dictionaries (struct Dict), a constructor function (new_dict()) which returns a pointer to a new dictionary, and a top-level variable (d) which is meant to hold a pointer to a dictionary. The init function ensures that d is initialized. However, Cyclone would complain that d is not initialized because init may not be called, or it may only be called after d is already used. Furthermore, the only way to initialize d is to call the constructor, and such an expression is not a valid top-level initializer. The solution is to declare d as a ``possibly-null'' pointer to a dictionary and initialize it with NULL:

struct DICT; 
struct DICT *nonnull new_dict();
struct DICT *d;
void init() {
  d = new_dict();
}

Of course, now whenever you use d, either you or the compiler will have to check that it is not NULL.

Put breaks or fallthrus in switch cases.

Cyclone requires that you either break, return, continue, throw an exception, or explicitly fallthru in each case of a switch.

Replace one temporary with multiple temporaries.

Consider the following code:

void foo(char * x, char * y) {
  char * temp;
  temp = x;
  bar(temp);
  temp = y;
  bar(temp);
}

When compiled, Cyclone generates an error message like this:

type mismatch: char *@zeroterm #0  != char *@zeroterm #1 

The problem is that Cyclone thinks that x and y might point into different regions (which it named #0 and #1 respectively), and the variable temp is assigned both the value of x and the value of y. Thus, there is no single region that we can say temp points into. The solution in this case is to use two different temporaries for the two different purposes:

void foo(char * x, char * y) {
  char * temp1;
  char * temp2;
  temp1 = x;
  bar(temp1);
  temp2 = y;
  bar(temp2);
}

Now Cyclone can figure out that temp1 is a pointer into the region #0 whereas temp2 is a pointer into region #1.

Connect argument and result pointers with the same region.

Remember that Cyclone assumes that pointer inputs to a function might point into distinct regions, and that output pointers, by default point into the heap. Obviously, this won't always be the case. Consider the following code:

int *foo(int *x, int *y, int b) {
  if (b)
    return x;
  else
    return y;
}

Cyclone complains when we compile this code:

returns value of type int *#0  but requires int *
        #0 and `H failed to unify. 
returns value of type int *#1  but requires int *
        #1 and `H failed to unify. 

The problem is that neither x nor y is a pointer into the heap. You can fix this problem by putting in explicit regions to connect the arguments and the result. For instance, we might write:

int *`r foo(int *`r x, int *`r y, int b) {
  if (b)
    return x;
  else
    return y;
}

and then the code will compile. Of course, any caller to this function must now ensure that the arguments are in the same region.

Insert type information to direct the type-checker.

Cyclone is usually good about inferring types. But sometimes, it has too many options and picks the wrong type. A good example is the following:

void foo(int b) {
  printf("b is %s", b ? "true" : "false");
} 

When compiled, Cyclone warns:

(2:39-2:40): implicit cast to shorter array

The problem is that the string "true" is assigned the type const char ?{5} whereas the string "false" is assigned the type const char ?{6}. (Remember that string constants have an implicit 0 at the end.) The type-checker needs to find a single type for both since we don't know whether b will come out true or false and conditional expressions require the same type for either case. There are at least two ways that the types of the strings can be promoted to a unifying type. One way is to promote both to char? which would be ideal. Unfortunately, Cyclone has chosen another way, and promoted the longer string ("false") to a shorter string type, namely const char ?{5}. This makes the two types the same, but is not at all what we want, for when the procedure is called with false, the routine will print

b is fals

Fortunately, the warning indicates that there might be a problem. The solution in this case is to explicitly cast at least one of the two values to const char ?:

void foo(int b) {
  printf("b is %s", b ? ((const char ?)"true") : "false");
} 

Alternatively, you can declare a temp with the right type and use it:

void foo(int b) {
  const char ? t = b ? "true" : "false"
  printf("b is %s", t);
} 

The point is that by giving Cyclone more type information, you can get it to do the right sorts of promotions.

Copy ``const'' code or values to make it non-const.

Cyclone takes const seriously. C does not. Occasionally, this will bite you, but more often than not, it will save you from a core dump. For instance, the following code will seg fault on most machines:

void foo() {
  char ?x = "howdy"
  x[0] = 'a';
}

The problem is that the string "howdy" will be placed in the read-only text segment, and thus trying to write to it will cause a fault. Fortunately, Cyclone complains that you're trying to initialize a non-const variable with a const value so this problem doesn't occur in Cyclone. If you really want to initialize x with this value, then you'll need to copy the string, say using the dup function from the string library:

void foo() {
  char ?x = strdup("howdy");
  x[0] = 'a';
}

Now consider the following call to the strtoul code in the standard library:

extern unsigned long strtoul(const char ?`r n, 
                             const char ?`r*`r2 endptr,
                             int base);
unsigned long foo() {
  char ?x = strdup("howdy");
  char ?*e = NULL;
  return strtoul(x,e,0);
}

Here, the problem is that we're passing non-const values to the library function, even though it demands const values. Usually, that's okay, as const char ? is a super-type of char ?. But in this case, we're passing as the endptr a pointer to a char ?, and it is not the case that const char ?* is a super-type of char ?*. In this case, you have two options: Either make x and e const, or copy the code for strtoul and make a version that doesn't have const in the prototype.

Get rid of calls to free, calloc etc.

There are many standard functions that Cyclone can't support and still maintain type-safety. An obvious one is free() which releases memory. Let the garbage collector free the object for you, or use region-allocation if you're scared of the collector. Other operations, such as memset, memcpy, and realloc are supported, but in a limited fashion in order to preserve type safety.

Use polymorphism or tagged unions to get rid of void*.

Often you'll find C code that uses void* to simulate polymorphism. A typical example is something like swap:

void swap(void **x, void **y) {
  void *t = x;
  x = y;
  y = t;
}

In Cyclone, this code should type-check but you won't be able to use it in many cases. The reason is that while void* is a super-type of just about any pointer type, it's not the case that void** is a super-type of a pointer to a pointer type. In this case, the solution is to use Cyclone's polymorphism:

void swap(`a *x, `a *y) {
  `a t = x;
  x = y;
  y = t;
}

Now the code can (safely) be called with any two (compatible) pointer types. This trick works well as long as you only need to ``cast up'' from a fixed type to an abstract one. It doesn't work when you need to ``cast down'' again. For example, consider the following:

int foo(int x, void *y) {
  if (x)
   return *((int *)y);
  else {
    printf("%s\n",(char *)y);
    return -1;
  }
}

The coder intends for y to either be an int pointer or a string, depending upon the value of x. If x is true, then y is supposed to be an int pointer, and otherwise, it's supposed to be a string. In either case, you have to put in a cast from void* to the appropriate type, and obviously, there's nothing preventing someone from passing in bogus cominations of x and y. The solution in Cylcone is to use a tagged union to represent the dependency and get rid of the variable x:

@tagged union IntOrString { 
  int Int;
  const char *@fat String;
};
typedef union IntOrString i_or_s;
int foo(i_or_s y) {
  switch (y) {
  case {.Int = i}:  return i;
  case {.String = s}:  
    printf("%s\n",s);
    return -1;
  }
}

Rewrite the bodies of vararg functions.

See the section on varargs for more details.

Use exceptions instead of setjmp.

Many uses of setjmp/longjmp can be replaced with a try-block and a throw. Of course, you can't do this for things like a user-level threads package, but rather, only for those situations where you're trying to ``pop-out'' of a deeply nested set of function calls.

A.3  Interfacing to C

  extern "C" double acos(double);

extern "C" {
  double acos(double);
  float  acosf(float);
  double acosh(double);
  float  acoshf(float);
  double asin(double);
}

extern "C include" {
  char peek(unsigned int i) {
    return *((char *)i);
  }

  void poke(unsigned int i, char c) {
    *((char *)i) = c;
  }
} export {
  peek, poke;
}