2 Cyclone for C Programmers
We begin with a quick overview of Cyclone, suitable for those who
already know how to program in C. We'll explain some of the ways
that Cyclone differs from C, and some of the reasons why; you should
come away with enough knowledge to start writing, compiling, and
running your own Cyclone programs. We assume that the Cyclone
compiler is already installed on your system (see
Appendix E or http://www.cs.cornell.edu/projects/cyclone
if you need to install the compiler).
2.1 Getting Started
Here's a Cyclone program that prints the string ``hello,
world.''
#include <stdio.h>
int main() {
printf("hello, world\n");
return 0;
}
It looks rather like a C program---in fact, a C compiler will happily
compile it. The program uses #include to tell the
preprocessor to import some standard definitions, it defines a
distinguished function main that serves as the entry point of
the program, and it uses the familiar printf function to
handle the printing; all of this is just as in C.
To compile the program, put it into a file hello.cyc, and run
the command
cyclone hello.cyc -o hello
This tells the Cyclone compiler (cyclone) to compile the file
hello.cyc; the -o flag tells the compiler to leave
the executable output in the file hello (or, in Windows,
hello.exe). If all goes well you can execute the program by
typing
hello
and it will print
hello, world
It's interesting to compare our program with a version that omits the
return statement:
#include <stdio.h>
int main() {
printf("hello, world\n");
}
A C compiler will compile and run this version. However, it's not
valid Cyclone code: it will be rejected by the Cyclone compiler.
Cyclone requires a definite return: any function with a return
type other than void must explicitly return a value of the
correct type. Since main is declared with return type
int, Cyclone requires that it explicitly return an integer.
Definite return reflects Cyclone's concern with safety. The caller of
the function expects to receive a value of the return type; if the
function does not execute a return statement, the caller will
receive some incorrect value instead. If the returned value is supposed
to be a pointer, the caller might try to dereference it, and
dereferencing an arbitrary address can cause the program to crash. So,
Cyclone requires a return statement (even if the return type is not a
pointer type).
2.2 Pointers
Programs that use pointers properly in C can be both fast and elegant.
But when pointers are used improperly in C, they cause core dumps and
buffer overflows. To prevent this, Cyclone introduces different kinds
of pointers and either (a) puts some restrictions on how you can use pointers
of a given kind or (b) places no restrictions but may insert additional
run-time checks.
Nullable Pointers
The first kind of pointer is indicated with a *, as in C. For
example, if we declare
int x = 3;
int *y = &x;
then y is a pointer to the integer 3 (the contents of
x). The pointer, y, is represented by a memory
address, namely, the address of x. To refer to the contents
of y, you use *y, so, for example, you can increment
the value of x with an assignment like
*y = *y + 1;
This much is just as in C. However, there are some differences in
Cyclone:
-
You can't cast an integer to a pointer. Cyclone prevents this
because it would let you overwrite arbitrary memory locations. In
fact, you can't use (void *)0 as a pointer in Cyclone, even
though this is how C typically defines NULL. Instead,
Cyclone provides NULL as a keyword.
- You can't do pointer arithmetic on a * pointer.
Pointer arithmetic in C can take a pointer out of bounds, so that
when the pointer is eventually dereferenced, it corrupts memory or
causes a crash. (However, pointer arithmetic is possible
using ? pointers.)
- There is one other way to crash a C program using pointers: you
can dereference the null pointer or try to update the null location.
Cyclone prevents this by inserting a null check whenever you
dereference a * pointer (that is, whenever you use the
*, ->, or subscript operation on a pointer.)
These are drastic differences from C, particularly the restriction on
pointer arithmetic. The benefit is that you can't cause a crash using
* pointers in Cyclone.
Fat Pointers
If you need to do pointer arithmetic in Cyclone, you must use a second
kind of pointer, called a fat pointer and indicated by ?
(the question mark). For
example, here is a program that echoes its command-line arguments:
#include <stdio.h>
int main(int argc, char ??argv) {
argc--; argv++; /* skip command name */
if (argc > 0) {
/* print first arg without a preceding space */
printf("%s",*argv);
argc--; argv++;
}
while (argc > 0) {
/* print other args with a preceding space */
printf(" %s",*argv);
argc--; argv++;
}
printf("\n");
return 0;
}
Except for the declaration of argv, which holds the
command-line arguments, the program looks just like you would write it
in C: pointer arithmetic (argv++) is used to move
argv to point to each argument in turn, so it can be printed.
In C, argv would typically be declared with type char
**, a pointer to a pointer to a character, which is thought of as
an array of an array of characters. In Cyclone, argv is
instead declared with type char ??, which is thought of in
the same way: it is a (fat) pointer to a (fat) pointer to characters. The
difference between a * pointer and a ? pointer is
that a ? pointer comes with bounds information and is thus
``fatter'' than a traditional pointer. Each time a
fat pointer is dereferenced or its contents are assigned to,
Cyclone inserts not only a null check but a bounds check. This
guarantees that a ? pointer can never cause a buffer
overflow.
Because of the bounds information contained in ? pointers,
argc is superfluous: you can get the size of argv by
writing argv.size. We've kept argc as an argument
of main for backwards compatibility.
It's worth remarking that you can always cast a * pointer
to a ? pointer (and vice-versa). So, it is possible to do
pointer arithmetic on a value of type *, but only when you
insert the appropriate casts to convert from one pointer type to
another. Note that some of these casts can fail at run-time. For
instance, if you try to cast a fat pointer that points to an empty
sequence of characters to char *, then the cast will fail
since the sequence doesn't contain at least one character.
Never-null pointers
There is one other kind of pointer in Cyclone: the never-null pointer.
A never-null pointer is indicated by @ (the at sign). An
@ pointer is like a * pointer, except that it is
guaranteed not to be NULL. This means that when you dereference an
@ pointer or assign to its contents, a null check is
unnecessary.
@ pointers are useful in Cyclone both for efficiency and as
documentation. This can be seen at work in the standard library,
where many functions take @ pointers as arguments, or return
@ pointers as results. For example, the getc
function that reads a character from a file is declared,
int getc(FILE @);
This says that getc expects to be called with a non-null
pointer to a FILE. Cyclone guarantees that, in fact, when
the getc function is entered, its argument is not null. This
means that getc does not have to test whether it is null, or
decide what to do if it is in fact NULL.
In C, the argument of getc is declared to have type
FILE *, and programmers can call getc with
NULL. So for safety, C's getc ought to check for
NULL. In practice, many C implementations omit the check;
getc(NULL) is an easy way to crash a C program.
In Cyclone, you can still call getc with a possibly-null
FILE pointer (a FILE *). However, Cyclone insists
that you insert a check before the actual call:
FILE *f = fopen("/etc/passwd","r");
int c = getc((FILE @)f);
Here f will be NULL if the file /etc/passwd doesn't
exist or can't be read. So, in Cyclone f must be cast to
FILE @ before the call to getc. The cast causes a
null check. If you try to call getc without the cast,
Cyclone will insert one for you automatically, and warn you that it is
doing so.
If you call getc with a FILE @, of course, no check
is required. For example, stdin is a FILE @ in
Cyclone, so you can simply call getc(stdin). In Cyclone you
will find that many functions return @ pointers, so many of
the pointers you deal with will already be @ pointers, and
neither the caller nor the called function needs to do null
checks---and this is perfectly safe.
Initializing Pointers
Pointers must be initialized before they are used to ensure that random
stack garbage does not get used as a pointer. This requirement goes for
variables that have pointer type, as well for arrays, elements of arrays,
and for fields in structures. Conversely, data that does not have pointer
type need not be initialized before it is used, since doing so cannot result
in a violation of safety. This decision adheres to the philosophy of C, but
diverges from that of traditional type-safe languages like Java and ML.
Other features of pointers
There's much more to Cyclone pointers than we've described here.
In particular, a pointer type can also specify that it points to a
sequence of a particular (statically known) length. For instance, we
can write:
void foo(int @{4} arr);
Here, the parameter arr is a pointer to a sequence of
four integer values. Both the never-null and nullable pointers
support explicit sequence bounds that are tracked statically.
Indeed, both pointer kinds always have length information and
when you write ``int *'' this is just short-hand for
``int *{1}''.
We explain pointers in more detail in
Section 3.
2.3 Regions
Another potential way to crash a program or violate security is
to dereference a dangling pointer---a pointer to storage that
has been deallocated. These are particularly insidious bugs
because the error might not manifest itself immediately.
For example, consider the following C code:
struct Point {int x; int y;};
struct Point *newPoint(int x,int y) {
struct Point result = {x,y};
return &result;
}
void foo(struct Point *p) {
p->y = 1234;
return;
}
void bar() {
struct Point *p = newPoint(1,2);
foo(p);
}
The code has an obvious bug: the function newPoint returns a
pointer to a locally-defined variable (result), even though
the storage for that variable is deallocated upon exit from the
function. That storage may be re-used (e.g., by a subsequent procedure
call) leading to subtle bugs or security problems. For instance, in
the code above, after bar calls newPoint, the storage
for the point is re-used to store information for the activation
record of the call to foo. This includes a copy of the
pointer p and the return address of foo. Therefore,
it may be that p->y actually points to the return address of
foo. The assignment of the integer 1234 to that location could
then result in foo ``returning'' to an arbitrary hunk of code
in memory. Nevertheless, the C type-checker readily
admits the code.
In Cyclone, this code would be rejected by the type-checker to avoid
the kind of problems mentioned above. The reason the code is rejected
is that Cyclone tracks the lifetime of every object and ensures that
a pointer to an object can only be dereferenced if that object
has not been deallocated.
The way that Cyclone achieves this is by assigning each object a
symbolic region that corresponds to the lexical block in which
the object is declared, and each pointer type reflects the region
into which a pointer points. For instance, the variable result
lives within a region that corresponds to the
invocation of the function newPoint. We write the
name of the region explicitly using a back-quote as in `newPoint.
Because result lives in region `newPoint, the
expression &result is a pointer into region
`newPoint. If we like, we can write the type of
&result with the explicit region as ``struct Point *
`newPoint''. Note that the region name comes after the * (or
? or @).
When control flow exits a block, the storage (i.e.,
the region) for that
block is deallocated. Cyclone keeps track of the set of regions that
are allocated and deallocated at every control-flow point and ensures
that you only dereference pointers to allocated regions. For example,
consider the following fragment of (bad) Cyclone code:
1 int f() {
2 int x = 0;
3 int *`f y = &x;
4 L:{ int a = 0;
5 y = &a;
6 }
7 return *y;
8 }
In the function f above, the variables x and
y live within the region `f because they are
declared in the outermost block of the function. The storage for
those variables will live as long as the invocation of the function.
Note that since y is a pointer to x, the type of
y is int * `f reflecting that y points into
region `f.
The variable a does not live in region `f because
it is declared in an inner block, which we have labeled with
L. The storage for the inner block L may be
deallocated upon exit of the block. To be more precise, the
storage for a is deallocated
at line 7 in the code. Thus, it is an error to try to access
this storage in the rest of the computation, as is done on line 7.
Cyclone detects the error because it gives the expression &a the
type int * `L reflecting the fact that the value is
a pointer into region `L. So, the assignment
y = &a fails to type-check because y expects
to hold a pointer into region `f, not region `L.
The restriction, compared to C, is that a pointer's type indicates
one region instead of all regions.
Region Inference
As we will see, Cyclone often figures out the region of a pointer
without the programmer providing the information. This is called region inference. For instance, we can re-write the function
f above without any region annotations, and without
labelling the blocks:
1 int f() {
2 int x = 0;
3 int *y = &x;
4 { int a = 0;
5 y = &a;
6 }
7 return *y;
8 }
and Cyclone can still figure out that y is a pointer into
region `f, and &a is a pointer into a different
(now anonymous) region, so the code should be rejected.
As we will show below, occasionally you will need to put explicit
region annotations into the code to convince the type-checker that
something points into a particular region, or that two things point
into the same region. In addition, it is sometimes useful to put in
the region annotations for documentation purposes, or to make type
errors a little less cryptic.
You need to understand at least four more details about regions to
be an effective Cyclone programmer: the heap region, dynamic
regions, region polymorphism, and default region annotations for
function parameters. The following sections give a brief overview
of these details.
The Heap Region
There is a special region for the heap, written `H, that
holds all of the storage for top-level variables, and for data
allocated via new or malloc. For instance, if we
write the following declarations at the top-level:
struct Point p = {0,1};
struct Point *ptr = &p;
then Cyclone figures out that ptr points into the heap
region. To reflect this explicitly, we can put the region in
the type of ptr if we like:
struct Point p = {0,1};
struct Point *`H ptr = &p;
As another example, the following function heap-allocates a point and
returns it to the caller. We put the regions in here to be explicit:
struct Point *`H good_newPoint(int x,int y) {
struct Point *`H p = malloc(sizeof(struct Point));
p->x = x;
p->y = y;
return p;
}
Alternatively, we can use new to heap-allocate and
initialize the result:
struct Point *`H good_newPoint(int x,int y) {
return new Point{x,y};
}
Dynamic Regions
Storage on the stack is implicitly allocated and recycled when you
enter and leave a block. Storage in the heap is explicitly allocated
via new or malloc, but there is no support in
Cyclone for explicitly freeing an object in the heap. The reason is
that Cyclone cannot accurately track the lifetimes of individual
objects within the heap, so it can't be sure whether dereferencing a
pointer into the heap would cause problems. Instead, a conservative
garbage collector reclaims the data allocated in the heap.
Using a garbage collector to recycle memory is the right thing to do
for most applications. For instance, the Cyclone compiler uses
heap-allocated data and relies upon the collector to recycle most
objects it creates when compiling a program. But a garbage collector
can introduce pauses in the program, and as a general purpose memory
manager, might not be as space- or time-efficient as routines tailored
to an application.
To address these applications, Cyclone provides support for dynamic
regions. A dynamic region is similar to the region associated with
a code block. In particular, when you execute:
region<`r> h {
...
}
this declares a new region `r along with a region handle
h. The handle can be used for dynamically allocating objects within
the region. All of the storage for
the region is deallocated at the point of the closing brace.
Unlike block
regions, the number (and size) of objects that you allocate into
the region is not fixed at compile time. In this respect, dynamic
regions are more like the heap. You can use the rnew(h) and
rmalloc(h,...) operations to allocate objects within a dynamic
region, where h is the handle for the region.
For instance, the following code takes an integer n, creates
a new dynamic region and allocates an array of size
n within the region using rnew.
int k(int n) {
int result;
region<`r> h {
int ?arr = rnew(h) {for i < n : i};
result = process(h, arr);
}
return result;
}
It then passes the
handle for the region and the array to some processing function.
Note that the processing function is free to allocate objects
into the region `r using the supplied handle.
After processing the array, we exit the region which deallocates
the array, and then return the calculated result.
It is worth remarking that the heap is really just a dynamic region
with global scope, and you can use the global variable heap_region
as a handle on the heap. Indeed, new and malloc(...)
are just abbreviations for rnew(heap_region) and
rmalloc(heap_region,...) respectively.
Region Polymorphism
Another key concept you need to understand about regions is called
region polymorphism. This is just a fancy way of saying
that you can write functions in Cyclone that don't care which
specific region a given object lives in, as long as it's still
alive. For example, the function foo from the beginning
of this section is a region-polymorphic function. To make this
clear, let us re-write the function making the regions explicit:
void foo(struct Point *`r p) {
p->y = 1234;
return;
}
The function is parameterized by a region variable `r
and accepts a pointer to a Point that lives in region
`r. Note that `r can be instantiated with
any region you like, including the heap, or a region local to
a function. So, for instance, we can write the following:
void g() {
struct Point p = {0,1};
struct Point *`g ptr1 = &p;
struct Point *`H ptr2 = new Point{2,3};
foo(ptr1);
foo(ptr2);
}
Note that in the first call to foo, we are passing
a pointer into region `g, and in the second call to
foo, we are passing in a pointer into the heap. In
the first call, `r is implicitly instantiated with
`g and in the second call, with `H.
Cyclone automatically inserts region parameters for function
arguments, so you rarely have to write them. For instance,
foo can be written simply as:
void foo(struct Point * p) {
p->y = 1234;
return;
}
As another example, if you write the following:
void h(struct Point * p1, struct Point * p2) {
p1->x += p2->x;
p2->x += p2->y;
}
then Cyclone fills in the region parameters for you by assuming
that the points p1 and p2 can live in any
two regions `r1 and `r2. To make this explicit,
we would write:
void h(struct Point *`r1 p1, struct Point *`r2 p2) {
p1->x += p2->x;
p2->x += p2->y;
}
Now we can call h with pointers into any two regions,
or even two pointers into the same region. This is because
the code is type-correct for all regions `r1 and `r2
Occasionally, you will have to put region parameters in explicitly.
This happens when you need to assert that two pointers point into
the same region. Consider for instance the following function:
void j(struct Point * p1, struct Point * p2) {
p1 = p2;
}
Cyclone will reject the code because it assumes that in general,
p1 and p2 might point into different regions.
That is, Cyclone fills in the missing regions as follows:
void j(struct Point *`r1 p1, struct Point *`r2 p2) {
p1 = p2;
}
Now it is clear that the assignment does not type-check because
the types of p1 and p2 differ. In other words,
`r1 and `r2 might be instantiated with
different regions, in which case the code would be incorrect.
But you can make them the same by putting in the same explicit region
for each pointer. Thus, the following code does type-check:
void j(struct Point *`r1 p1, struct Point *`r1 p2) {
p1 = p2;
}
So, Cyclone assumes that each pointer argument to a function is
in a (potentially) different region unless you specify otherwise.
The reason we chose this as the default is that (a) it is often
the right choice for code, (b) it is the most general type in
the sense that if it does work out, clients will have the most
lattitude in passing arguments from different regions or the
same region to the function.
What about the results? Here, there is no good answer because
the region of the result of a function cannot be easily determined
without looking at the body of the function, which defeats separate
compilation of function definitions from their prototypes. Therefore,
we have arbitrarily chosen the heap as the default region for
function results. Consequently, the following code:
struct Point * good_newPoint(int x,int y) {
return new Point{x,y};
}
type-checks since the new operator returns a pointer
to the heap, and the default region for the return type is the heap.
This explains why the original bad code for allocating a new
point does not type-check:
struct Point *newPoint(int x,int y) {
struct Point result = {x,y};
return &result;
}
The value &result is a pointer into region `newPoint
but the result type of the function needs to be a pointer into
the heap (region `H).
If you want to return a pointer that is not in the heap region,
then you need to put the region in explicitly. For instance,
the following code:
int * id(int *x) {
return x;
}
will not type-check immediately. To see why, let us rewrite the
code with the default region annotations filled in. The argument
is assumed to be in a region `r, and the result is assumed to be
in the heap, so the fully elaborated code is:
int *`H id(int *`r x) {
return x;
}
Now the type-error is manifest. To fix the code, we must put in
explicit regions to connect the argument type with the result type.
For instance, we might write:
int *`r id(int *`r x) {
return x;
}
Region Summary
In summary, each pointer in Cyclone points into a given region
and this region is reflected in the type of the pointer. Cyclone
won't let you dereference a pointer into a deallocated region.
The lexical blocks declared in functions correspond to one
type of region, and simply declaring a variable within that
block allocates storage within the region. The storage is
deallocated upon exit of the block. Dynamic regions are
similar, except that a dynamic number of objects can be allocated
within the region using the region's handle. The heap is a
special region that is garbage collected.
Region polymorphism makes it possible to omit many region
annotations on types. Cyclone assumes that pointers passed
to functions may live in distinct regions, and assumes that
result pointers are in the heap. These assumptions are not
perfect, but (a) programmers can fix the assumptions by providing
explicit region annotations, (b) it permits Cyclone files
to be separately compiled.
The region-based type system of Cyclone is perhaps the most
complicated aspect of the language. In large part, this is
because memory management is a difficult and tricky business.
We have attempted to make stack allocation and region polymorphic
functions simple to use without sacrificing programmer control
over the lifetimes of objects and without having to resort to
garbage collection.
For more information about regions, see
Section 8.
2.4 Tagged Unions and Pattern Matching
It's often necessary to write a function that accepts an argument with
more than one possible type. For example, in
printf("%d",x);
x should be an integer, but in
printf("%s",x);
x should be a pointer to a sequence of characters.
If we call printf("%s",x) with an integer x,
instead of a pointer x, the program will likely crash.
To prevent this, most C compilers treat printf specially:
they examine the first argument and require that the remaining
arguments have the appropriate types. However, a compiler can't check
this if printf isn't called with a literal string:
printf(s,x);
where s is a string variable. This means that in C, programs
that use printf (or scanf, or a number of related
functions) are vulnerable to crashes and corrupted memory. In fact,
it's possible for someone else to crash your program by causing it to
call printf with arguments that don't match the format
string. This is called a format string attack, and it's an
increasingly common exploit.
Cyclone provides tagged unions so that you can safely write
functions that accept an argument with more than one possible type.
Like a C union, a Cyclone tunion is a type that has
several possible cases. Here's a simple example:
tunion t {
Integer(int);
String(const char ?);
};
tunion t x = new Integer(3);
tunion t y = new String("hello, world");
This declares a new type, tunion t, that can hold either an
integer or a string (remember, a string is a char ? in
Cyclone). Integer and String are tags for
the two possibilities. The tags are used to build values of type
tunion t, as in the declarations of x and
y.
Pattern matching is used to determine the tag of a value of
type tunion t, and to extract the underlying value. For
example, here is a function that will print either an integer or a
string:
void print(tunion t a) {
switch (a) {
case &Integer(i): printf("%d",i); return;
case &String(s): printf("%s",s); return;
}
}
The argument a has type tunion t, so it is either
built with tag Integer or tag String. Cyclone
extends switch statements with patterns that
distinguish between the cases. The first case,
case &Integer(i): printf("%d",i); return;
contains a pattern, &Integer(i), that will only match values
that have been built with the Integer tag. The variable
i is bound to the underlying integer, and it can be used in
the body of the case. For example, print(x) will print 3,
since x was initialized by new Integer(3), and
print(y) will print hello, world.
The cases of a tunion can carry any number of values,
including none, and they can be recursive. For example, we can define
a tree datatype as follows.
tunion tree {
Empty;
Leaf(int);
Node(tunion tree, tunion tree);
};
A tree can be empty, or it can be a single (leaf) node holding an
integer, or it can be an internal node with a left and a right
subtree. In other words, tunion tree is the type of possibly
empty binary trees with integer leaves.
Here's a function, sum, that calculates the sum of the leaves
of a tree:
int sum(tunion tree x) {
switch (x) {
case Empty: return 0;
case &Leaf(i): return i;
case &Node(y,z): return sum(y)+sum(z);
}
}
It's written in a straightforward way, with a case for each possible
tag in the type tunion tree. The Empty case is
noticeably different than the other two cases: the pattern does not
use the & character. The reason has to do with how
tunion is implemented. Every value of tunion type
must have the same size; for example, the Node case
recursively calls sum on the subtrees y and
z, without knowing whether they are empty, leaves, or
internal nodes. The only way that it can extract y and
z from x without knowing this is if all possible
cases of tunion tree have the same size.
At the same time, each tag of a tunion can carry a different
number of values, so obviously each can require a different amount of
space. To make it all work, the value-carrying cases of a
tunion are represented as pointers to structures containing a
distinguishing integer plus the values, and the non-value-carrying
cases of a tunion are represented just as distinguishing
integers. Since integers and pointers have the same size in Cyclone,
this achieves the goal.
The data representation is reflected both in how tunion
values are constructed and in the patterns used to take them apart.
Value-carrying cases are built using the new keyword, which
performs a heap allocation and results in a pointer to the new
storage. Non-value-carrying cases don't require any allocation, and
so they don't use new. For example,
new Node(Empty,new Leaf(5))
builds a tree consisting of an internal node with an empty left
subtree, and a right subtree consisting of a single leaf, 5. We use
new for the value-carrying cases, Node and
Leaf, but not for Empty.
In pattern matching, we use the & character to match a
pointer. So in the function sum, since Leaf and
Node are constructed as pointers, the & is required
to match them. Since Empty is not built as a pointer, the
& must not appear.
You might be wondering, ``how does Cyclone tell whether a
tunion comes from a value-carrying case or a
non-value-carrying case?'' In particular, how can Cyclone tell the
integers used for non-value-carrying cases apart from the pointers
used for the other cases? Here's how we do it in our current
implementation: We reserve a space in the low part of memory where we
will never allocate Cyclone objects using new. If a value of
a tunion is an address in this space, then it represents a
tag without values, and if it is an address outside of this space, it
represents a pointer to a structure containing a tag plus the values
that it carries.
You can find out more about patterns in
Section 5; for more about
tunion and memory management, see
Section 8.
2.5 Exceptions
So far we've glossed over what happens when you try to dereference a
null pointer, or assign to an out-of-bounds ? pointer.
We've said that Cyclone inserts checks to make sure the operation is
safe, but what if the checks fail? For safety, it would be sufficient
to halt the program and print an error message---a big improvement
over a core dump, or, worse, a program with corrupted data that keeps
running.
In fact, Cyclone does something a bit more general than halting with
an error message: it throws an exception. The advantage of
exceptions is that they can be caught by the programmer, who
can then take corrective action and perhaps continue with the program.
If the exception is not caught, the program halts and prints an error
message. Consider our earlier example:
FILE *f = fopen("/etc/passwd","r");
int c = getc((FILE @)f);
Suppose that there is no file /etc/passwd; then
fopen will return NULL, and when f is cast to
FILE @, the implied null check will fail. The program will
halt with an error message,
Uncaught exception Null_Exception
Null_Exception is one of a handful of standard exceptions
used in Cyclone. Each exception is like a case of a tunion:
it can carry along some values with it. For example, the standard
exception InvalidArg carries a string. Exceptions can be
handled in try-catch statements, using pattern
matching:
FILE *f = fopen("/etc/passwd","r");
int c;
try {
c = getc((FILE @)f);
}
catch {
case Null_Exception:
printf("Error: can't open /etc/passwd\n");
exit(1);
case &InvalidArg(s):
printf("Error: InvalidArg(%s)\n",s);
exit(1);
}
Here we've ``wrapped'' the call to getc in a
try-catch statement. If f isn't NULL and
the getc succeeds, then execution just continues, ignoring
the catch. But if f is NULL, then the null check
will fail and the exception Null_Exception will be thrown;
execution immediately continues with the catch (the call to
getc never happens). In the catch, the thrown
exception is pattern matched against the cases. Since the thrown
exception is Null_Exception, the first case is executed here.
There is one important difference between an exception and a case of a
tunion: with tunion, all of the cases have to be
declared at once, while a new exception can be declared at any time.
So, exceptions are an extensible tunion, or
xtunion. Here's how to declare a new exception:
xtunion exn {
My_Exception(char ?);
};
The type xtunion exn is the type of exceptions, and this
declaration introduces a new case for the xtunion exn type:
My_Exception, which carries a single value (a string).
Exception values are created just like tunion values---using
new for value-carrying tags only---and are thrown with a
throw statement. For example,
throw new My_Exception("some kind of error");
or
throw Null_Exception;
2.6 Additional Features of Cyclone
Thus far, we have mentioned a number of advanced features of
Cyclone that provide facilities needed to avoid common bugs
or security holes in C.
But there are many other features in Cyclone that are
aimed at making it easier to write code, ranging from convenient
expression forms, to advanced typing constructs. For instance,
like GCC and C99, Cyclone allows you declare variables just
about anywhere, instead of at the top of a block. As another
example, like Java, Cyclone lets you declare variables within
the initializer of a for-statement.
In addition, Cyclone adds advanced typing support in the form of (a)
parametric polymorphism, (b) structural subtyping, (c) some
unification-based, local-type inference. These features are necessary
to type-check or port a number of (potentially) unsafe C idioms,
usually involving ``void*'' or the like. Similarly, tunion
types can be used to code around many of the uses for C's union types
-- another potential source of unsoundness.
In what follows, we give a brief overview of these added features.
2.7 GCC and C99 Additions
GCC and the
ISO C99
standard have some useful new features that we have adopted for
Cyclone. Some of the ones that we currently support are:
We expect to follow the C99 standard fairly closely.
2.8 Tuples
Tuples are like lightweight structs. They need not be declared in
advance, and have member or field names that are implicitly 0, 1, 2,
3, etc. For example, the following code declares x to be a
3-tuple of an integer, a character, and a boolean, initialized with
the values 42, 'z', and true respectively. It then
checks to see whether the third component in the tuple is true
(it is) and if so, increments the first component in the tuple.
$(int,char,bool) x = $(42,'z',true)
if (x[2])
x[0]++;
The above code would be roughly equivalent to writing:
struct {int f0; char f1; bool f2;} x = {42,'z',true};
if (x.f2)
x.f1++;
Thus, tuple types are written $(type1,...,typen), tuple
constructor expressions are written $(exp1,...,expn), and
extracting the ith component of a tuple is written using subscript
notation exp[i-1]. Note that, consistent with the rest of C,
the members start with 0, not 1.
Unlike structs, tuple types are treated equivalent as long as they are
structurally equivalent. As in C, struct types are equivalent only if
they have the same tag or name. (Note that in C, all struct
declarations have a tag, even if the compiler has to gensym one.)
2.9 Creating Arrays
There are about four ways to create arrays in Cyclone. One can always
declare an array and provide an initializer as in C. For instance:
int foo[8] = {1,2,3,4,5,6,7,8};
char s[4] = "bar";
are both examples from C for creating arrays. Note that Cyclone
follows C's conventions here, so that if you declare arrays as above
within a function, then the lifetime of the array coincides with the
activation record of the enclosing scope. In other words, such arrays
will be stack allocated.
To create heap-allocated arrays (or strings) within a Cyclone
function, you should either use ``new'' operator with either an
array initializer or an array comprehension. The following code
demonstrates this:
// foo is a pointer to a heap-allocated array
int *{8}foo = new {1,2,3,4,5,6,7,8};
// s is a checked pointer to a heap-allocated string
char ?s = new "bar";
// a non-null pointer to the first 100 even numbers
int @{100}evens = new {for i < 100 : 2*i};
2.10 Subtyping
Cyclone supports ``extension on the right'' and ``covariant depth on
const'' subtyping for pointers. This simply means that you
can cast a value x from having a type ``pointer to a struct
with 10 fields,'' to ``pointer to a struct having only the first 5
fields.'' For example, if we have the following definitions:
typedef struct Point {float x,y;} *point;
typedef struct CPoint {float x,y; int color;} *cpoint;
float xcoord(point p) {
return p->x;
}
then you can call xcoord with either a point or
cpoint object. You can also cast a pointer to a tuple having 3
fields (e.g., $(int,bool,double)*) to a pointer to a tuple
having only 2 fields (e.g., $(int,bool)*). In other words, you
can forget about the ``tail'' of the object. This allows a degree of
polymorphism that is useful when porting C code. In addition, you can
do ``deep'' casts on pointer fields that are const. (It is
unsafe to allow deep casts on non-const fields.) Also, you can cast
a field from being non-const to being const. You can also cast a
constant-sized array to an equivalent pointer to a struct or tuple.
In short, Cyclone attempts to allow you to cast one type to another as
long as it is safe. Note, however, that these casts must be explicit.
We expect to add more support for subtyping in the future (e.g.,
subtyping on function pointers, bounded subtyping, etc.)
2.11 Let Declarations
Sometimes, it's painful to declare a variable because you have to
write down its type, and Cyclone types can be big when compared
to their C counterparts since they may include bounds information,
regions, etc. Therefore, Cyclone includes additional support for type
inference using let declarations. In particular, you can write:
int foo(int x) {
let y = x+3;
let z = 3.14159;
return (int)(y*z);
}
Here, we declared two variables y and z using ``let.'' When
you use let, you don't have to write down the type of the
variable. Rather, the compiler infers the type from the expression
that initializes the variable. More generally, you can write
``let pattern = exp;'' to destructure a value into a bunch of
variables. For instance, if you pass a tuple to a function, then you
can extract the components as follows:
int sum($(int,int,int) args) {
let $(x,y,z) = args;
return (x+y+z);
}
2.12 Polymorphic Functions
As mentioned above, Cyclone supports a limited amount of subtyping
polymorphism. It also supports a fairly powerful form of parametric
polymorphism. Those of you coming from ML or Haskell will find this
familiar. Those of you coming from C++ will also find it somewhat
familiar. The basic idea is that you can write one function that
abstracts the types of some of the values it manipulates. For
instance, consider the following two functions:
$(string_t,int) swap1($(int,string_t) x) {
return $(x[1], x[0]);
}
$(int,int) swap2($(int,int) x) {
return $(x[1], x[0]);
}
The two functions are quite similar: They both take in a pair (i.e., a
2-tuple) and return a pair with the components swapped. At the
machine-level, the code for these two functions will be exactly the
same, assuming that ints and string_ts (char *) are
represented the same way. So it seems silly to write the code twice.
Normally, a C programmer would replace the definition with simply:
$(void *,void *) swap1($(void *,void *) x) {
return $(x[1], x[0]);
}
(assuming you added tuples to C). But of course, this isn't type-safe
because once I cast the values to void *, then I can't be sure
what type I'm getting out. In Cyclone, you can instead write
something like this:
$(`b,`a) swap($(`a,`b) x) {
return $(x[1],x[0]);
}
The code is the same, but it abstracts what the types are. The types
`a and `b are type variables that can be instantiated
with any word-sized, general-purpose register type. So, for instance,
you can call swap on pairs of integers, pairs of pointers, pairs of an
integer and a pointer, etc.:
let $(x,y) = swap($("hello",3)); // x is 3, y is hello
let $(w,z) = swap($(4,3)); // w is 3, z is 4
Note that when calling a polymorphic function, you need not tell it
what types you're using to instantiate the type variables. Rather,
Cyclone figures this out through unification.
C++ supports similar functionality with templates. However, C++ and
Cyclone differ considerably in their implementation strategies.
First, Cyclone only produces one copy of the code, whereas a C++
template is specialized and duplicated at each type that it is used.
This approach requires that you include definitions of templates in
interfaces and thus defeats separate compilation. However, the
approach used by Cyclone does have its drawbacks: in particular, the
only types that can instantiate type variables are those that can be
treated uniformly. This ensures that we can use the same code for
different types. The general rule is that values of the types that
instantiate a type variable must fit into a machine word and must be
passed in general-purpose (as opposed to floating-point) registers.
Examples of such types include int, pointers, tunion,
and xtunion types. Other types, including char,
short, long long, float, double,
struct, and tuple types violate this rule and thus
values of these types cannot be passed to a function like swap in
place of the type variables. In practice, this means that you tend to
manipulate a lot of pointers in Cyclone code.
The combination of parametric polymorphism and sub-typing means that
you can cover a lot of C idioms where void* or unsafe casts
were used without sacrificing type-safety. We use polymorphism a lot
when coding in Cyclone. For instance, the standard library includes
many container abstractions (lists, sets, queues, etc.) that are all
polymorphic in the element type. This allows us to re-use a lot of
code. In addition, unlike C++, those libraries can be compiled once
and need not be specialized. On the downside, this style of
polymorphism does not allow you to do any type-specific things (e.g.,
overloading or ad-hoc polymorphism.) Someday, we may add support for
this, but in the short run, we're happy not to have it.
2.13 Polymorphic Data Structures
Just as function definitions can be parameterized by types, so can
struct definitions, tunion definitions, and even
typedefs. For instance, the following struct definition
is similar to the one used in the standard library for lists:
struct List<`a> {`a hd; struct List<`a> * tl; };
typedef struct List<`a> *list_t<`a>;
Here, we've declared a struct List parameterized by a type
`a. The hd field contains an element of type `a
and the tl field contains a possibly-null pointer to a
struct List with elements of type `a. We then define
list_t<`a> as an abbreviation for struct List<`a>*. So,
for instance, we can declare both integer and string lists like this:
list_t<int> ilist = new List{1,new List{2,null}};
list_t<string_t> slist = new List{.hd = "foo",
.tl = new List{"bar",null}};
Note that we use ``new'' as in C++ to allocate a new
struct List on the heap and return a pointer to the resulting
(initialized) List object. Note also that the field designator
(``.hd'', ``.tl'') are optional.
Once you have polymorphic data structures, you can write lots of
useful polymorphic code and use it over and over again. For instance,
the standard list library (see lib/list.h) includes functions for
mapping over a list, looking up items in a list, concatenating two
lists, copying lists, sorting lists, etc.
2.14 Abstract and Existential Types
Suppose you want to declare an abstract type for implementing stacks.
In Cyclone, the way this is accomplished is by declaring a struct that
encapsulates the implementation type, and by adding the
``abstract'' qualifier to the struct definition. For instance,
if we write:
abstract struct Queue<`a> { list_t<`a> front, rear; };
then this declares a polymorphic Queue implementation that is
abstract. The definition of the struct is available within the unit
that declares the Queue, but will not be made available to the outside
world. (This will be enforced by a link-time type-checker that we
are currently putting together.) Typically, the provider of the
Queue abstraction would write in an interface file:
extern struct Queue<`a>;
The abstract keyword in the implementation ensures that the definition
does not leak to a client.
Typedefs cannot be made abstract. As in C, typedefs are type
abbreviations and are expanded at compile time. If we chose to make
them (potentially) abstract, then we'd have to enforce a ``boxedness''
restriction, similar to the restrictions on type variables. To
simplify the language, we chose to make structs abstract.
It's also possible to code up ``first-class'' abstract data types
using tunions or xtunions. Individual [x]tunion
constructors can be parameterized by additional type variables that
are local to the type-constructor. (From a type-theoretic point of
view, these are existentially-quantified variables.) Our current
approach is quite similar to the treatment of existential types in
Haskell. Existential types are described in
Section 4.
For an example of the use of existential types, see the fn.h
and fn.cyc files in the standard library, which implement
first-class closures.
2.15 Restrictions
Though Cyclone adds many new features to C, there are also a number
of restrictions that it must enforce to ensure code does not crash.
Here is a list of the major restrictions:
-
Cyclone requires every function to declare a return type (the
implicit int for the return type of a function is removed).
- Cyclone does not permit some of the casts that are allowed in C because
incorrect casts can lead to crashes, and it is not always possible
for us to determine what is safe. In general, you should be
able to cast something from one type to another as long as the
underlying representations are compatible. Note that Cyclone is
very conservative about ``compatible'' because it does not know
the size or alignment constraints of your C compiler.
- Cyclone does not support pointer arithmetic on * or
@ pointers. Pointer arithmetic is not unsafe in itself, but
it can lead to unsafe code when the resulting pointer is assigned or
dereferenced. You can cast the * or @ value to a
? value and then do the pointer arithmetic instead.
- Cyclone inserts a NULL check when a * pointer is
dereferenced and it cannot determine statically that the pointer is
not NULL.
- Cyclone requires any function that is supposed to return a
non-void value to execute a return statement (or throw an
exception) on every possible execution path. This is needed to
ensure that the value returned from the function has the right type,
and is not just a random value left in a register or on the stack.
- Unions in Cyclone can only hold ``bits.'' In particular, they
can hold combinations of chars, ints, shorts, longs, floats,
doubles, structs of bits, or tuples of bits. Pointer types are not
supported. This avoids the situation where an arbitrary bit pattern
is cast to a pointer and then dereferenced. If you want to use
multiple types, then use tagged unions (tunions).
- Cyclone only supports a limited form of malloc which is
baked in. Tuples and structs can be allocated via malloc
but this requires writing explicitly: malloc(sizeof(t))
where t is the type of the value that you are allocating. You
cannot use malloc to allocate an array.
- Cyclone performs a static analysis to ensure that every variable
and every struct field is initialized before it is used. This
prevents a random stack value from being used improperly. The
analysis is somewhat conservative so you may need to initialize
things earlier than you would do in C. For instance, currently,
Cyclone does not support initializing a struct in a procedure
separate from the one that does the allocation.
- Cyclone does not permit gotos from one scope into
another. C warns against this practice, as it can cause crashes;
Cyclone rules it out entirely.
- Cyclone places some limitations on the form of switch statements
that rule out crashes like those caused by unrestricted
goto. Furthermore, Cyclone prevents you from accidentally
falling through from one case to another. To fall through, you must
explicitly use the fallthru keyword. Otherwise, you must
explicitly break, goto, continue,
return, or throw an exception. However, adjacent
cases for a switch statement (with no intervening statement) do
not require an explicit fallthru.
- In the near future, Cyclone will place some restrictions on
linking for safety reasons. In particular, if you import a variable
or function with one type, then it must be exported by another file
with that type. In addition, access to C code will be restricted
based on a notion of security roles.
- Cyclone has some new keywords (let, abstract,
region, etc.) that can no longer be used as identifiers.
- Cyclone prevents you from using pointers to stack-allocated
objects as freely as in C to avoid security holes. The reason is
that each declaration block is placed in a conceptual ``region'' and
the type system tracks the region into which a pointer points.
- Cyclone does not allow you to explicitly free a heap-allocated
object. Instead, you can either use the region mechanism or rely
upon the conservative garbage collector to reclaim the space.
In addition, there are a number of shortcomings of the current
implementation that we hope to correct in the near future. For
instance: