C   Libraries

C.1   C Libraries

<arpa/inet.h> <assert.h> <ctype.h> <dirent.h> <errno.h> <fcntl.h> <getopt.h> <grp.h> <math.h> <netdb.h> <netinet/in.h> <netinet/tcp.h> <pwd.h> <signal.h> <stddef.h> <stdio.h> <stdlib.h> <string.h> <strings.h> <sys/mman.h> <sys/resource.h> <sys/select.h> <sys/socket.h> <sys/stat.h> <sys/time.h> <sys/types.h> <sys/wait.h> <time.h> <unistd.h>

    #include <cXXX.h>

    using Std;

C.2   <array.h>

void qsort(cmpfn_t<`a, `r, `r>, `a ?`r x, int len);

qsort(cmp,x,len) sorts the first len elements of array x into ascending order (according to the comparison function cmp) by the QuickSort algorithm. cmp(a,b) should return a number less than, equal to, or greater than 0 according to whether a is less than, equal to, or greater than b. qsort throws Core::InvalidArg("Array::qsort") if len is negative or specifies a segment outside the bounds of x.

qsort is not a stable sort.

void msort(cmpfn_t<`a, , >, `a ?`H x, int len);

msort(cmp,x,len) sorts the first len elements of array x into ascending order (according to the comparison function cmp), by the MergeSort algorithm. msort throws Core::InvalidArg("Array::msort") if len is negative or specifies a segment outside the bounds of x.

msort is a stable sort.

`a ?from_list(List::list_t<`a> l);

from_list(l) returns a heap-allocated array with the same elements as the list l.

List::list_t<`a> to_list(`a ?x);

to_list(x) returns a new heap-allocated list with the same elements as the array x.

`a ?copy(`a ?x);

copy(x) returns a fresh copy of array x, allocated on the heap.

`b ?map(`b(@`H f)(`a), `a ?x);

map(f,x) applies f to each element of x, returning the results in a new heap-allocated array.

`b ?map_c(`b(@`H f)(`c, `a), `c env, `a ?x);

map_c(f,env,x) is like map(f,x) except that f requires a closure env as its first argument.

void imp_map(`a(@`H f)(`a), `a ?x);

imp_map(f,x) replaces each element xi of x with f(xi).

void imp_map_c(`a(@`H f)(`b, `a), `b env, `a ?x);

imp_map_c is a version of imp_map where the function argument requires a closure as its first argument.

xtunion exn {   Array_mismatch };

Array_mismatch is thrown when two arrays don't have the same length.

`c ?map2(`c(@`H f)(`a, `b), `a ?x, `b ?y);

If x has elements x1 through xn, and y has elements y1 through yn, then map2(f,x,y) returns a new heap-allocated array with elements f(x1,y1) through f(xn,yn). If x and y don't have the same number of elements, Array_mismatch is thrown.

void app(`b(@`H f)(`a), `a ?`r x);

app(f,x) applies f to each element of x, discarding the results. Note that f must not return void.

void app_c(`c(@`H f)(`a, `b), `a env, `b ?x);

app_c(f,env,x) is like app(f,x), except that f requires a closure env as its first argument.

void iter(void(@`H f)(`a), `a ?x);

iter(f,x) is like app(f,x), except that f returns void.

void iter_c(void(@`H f)(`b, `a), `b env, `a ?x);

iter_c(f,env,x) is like app_c(f,env,x) except that f returns void.

void app2(`c(@`H f)(`a, `b), `a ?x, `b ?y);

If x has elements x1 through xn, and y has elements y1 through yn, then app2(f,x,y) performs f(x1,y1) through f(xn,yn) and discards the results. If x and y don't have the same number of elements, Array_mismatch is thrown.

void app2_c(`d(@`H f)(`a, `b, `c), `a env, `b ?x, `c ?y);

app2_c is a version of app where the function argument requires a closure as its first argument.

void iter2(void(@`H f)(`a, `b), `a ?x, `b ?y);

iter2 is a version of app2 where the function returns void.

void iter2_c(void(@`H f)(`a, `b, `c), `a env, `b ?x, `c ?y);

iter2_c is a version of app2_c where the function returns void.

`a fold_left(`a(@`H f)(`a, `b), `a accum, `b ?x);

If x has elements x1 through xn, then fold_left(f,accum,x) returns f(f(...(f(x2,f(x1,accum))),xn-1),xn).

`a fold_left_c(`a(@`H f)(`c, `a, `b), `c env, `a accum, `b ?x);

fold_left_c is a version of fold_left where the function argument requires a closure as its first argument.

`b fold_right(`b(@`H f)(`a, `b), `a ?x, `b accum);

If x has elements x1 through xn, then fold_left(f,accum,x) returns f(x1,f(x2,...,f(xn-1,f(xn,a))...)).

`b fold_right_c(`b(@`H f)(`c, `a, `b), `c env, `a ?x, `b accum);

fold_right_c is a version of fold_right where the function argument requires a closure as its first argument.

`a ?rev_copy(`a ?x);

rev_copy(x) returns a new heap-allocated array whose elements are the elements of x in reverse order.

void imp_rev(`a ?x);

imp_rev(x) reverses the elements of array x.

bool forall(bool (@`H pred)(`a), `a ?x);

forall(pred,x) returns true if pred returns true when applied to every element of x, and returns false otherwise.

bool forall_c(bool (@`H pred)(`a, `b), `a env, `b ?x);

forall_c is a version of forall where the predicate argument requires a closure as its first argument.

bool exists(bool (@`H pred)(`a), `a ?x);

exists(pred,x) returns true if pred returns true when applied to some element of x, and returns false otherwise.

bool exists_c(bool (@`H pred)(`a, `b), `a env, `b ?x);

exists_c is a version of exists where the predicate argument requires a closure as its first argument.

$(`a, `b)?zip(`a ?`r1 x, `b ?y);

If x has elements x1 through xn, and y has elements y1 through yn, then zip(x,y) returns a new heap-allocated array with elements $(x1,y1) through $(xn,yn). If x and y don't have the same number of elements, Array_mismatch is thrown.

$(`a ?, `b ?)split($(`a, `b)?x);

If x has elements $(a1,b1) through $(an,bn), then split(x) returns a pair of new heap-allocated arrays with elements a1 through an, and b1 through bn.

bool memq(`a ?l, `a x);

memq(l,x) returns true if x is == an element of array l, and returns false otherwise.

bool mem(int(@`H cmp)(`a, `a), `a ?l, `a x);

mem(cmp,l,x) is like memq(l,x) except that the comparison function cmp is used to determine if x is an element of l. cmp(a,b) should return 0 if a is equal to b, and return a non-zero number otherwise.

`a ?extract(`a ?x, int start, int *len_opt);

extract(x,start,len_opt) returns a new array whose elements are the elements of x beginning at index start, and continuing to the end of x if len_opt is NULL; if len_opt points to an integer n, then n elements are extracted. If n<0 or there are less than n elements in x starting at start, then Core::InvalidArg("Array::extract") is thrown.

C.3   <bitvec.h>

typedef int ?`r bitvec_t<`r>;

bitvec_t is the type of bit vectors.

bitvec_t new_empty(int);

new_empty(n) returns a bit vector containing n bits, all set to 0.

bitvec_t new_full(int);

new_full(n) returns a bit vector containing n bits, all set to 1.

bitvec_t new_copy(bitvec_t );

new_copy(v) returns a copy of bit vector v.

bool get(bitvec_t , int);

get(v,n) returns the nth bit of v.

void set(bitvec_t , int);

set(v,n) sets the nth bit of v to 1.

void clear(bitvec_t , int);

clear(v,n) sets the nth bit of v to 0.

bool get_and_set(bitvec_t , int);

get_and_set(v,n) sets the nth bit of v to 1, and returns its value before the set.

void clear_all(bitvec_t );

clear_all(v) sets every bit in v to 0.

void set_all(bitvec_t );

set_all(v) sets every bit in v to 1.

bool all_set(bitvec_t bvec, int sz);

all_set(v) returns true if every bit in v is set to 1, and returns false otherwise.

void union_two(bitvec_t dest, bitvec_t src1, bitvec_t src2);

union_two(dest,src1,src2) sets dest to be the union of src1 and src2: a bit of dest is 1 if either of the corresponding bits of src1 or src2 is 1, and is 0 otherwise.

void intersect_two(bitvec_t dest, bitvec_t src1, bitvec_t src2);

intersect_two(dest,src1,src2) sets dest to be the intersection of src1 and src2: a bit of dest is 1 if both of the corresponding bits of src1 and src2 are 1, and is 0 otherwise.

void diff_two(bitvec_t dest, bitvec_t src1, bitvec_t src2);

diff_two(dest,src1,src2) sets dest to be the difference of src1 and src2: a bit of dest is 1 if the corresponding bit of src1 is 1, and the corresponding bit of src2 is 0; and is 0 otherwise.

bool compare_two(bitvec_t src1, bitvec_t src2);

compare_two(src1,src2) returns true if src1 and src2 are equal, and returns false otherwise.

C.4   <buffer.h>

typedef struct t @T ;

T is the type of buffers.

T create(unsigned int n);

create(n) returns a fresh buffer, initially empty. n is the initial size of an internal character array that holds the buffer's contents. The internal array grows when more than n character have been stored in the buffer; it shrinks back to the initial size when reset is called. If n is negative, no exception is thrown; a buffer with a small amount of internal storage is returned instead.

mstring_t contents(T );

contents(b) heap allocates and returns a string whose contents are the contents of buffer b.

size_t length(T );

length(b) returns the number of characters in buffer b.

void clear(T );

clear(b) makes b have zero characters. Internal storage is not released.

void reset(T );

reset(b) sets the number of characters in b to zero, and sets the internal storage to the initial string. This means that any storage used to grow the buffer since the last create or reset can be reclaimed by the garbage collector.

void add_char(T , unsigned char);

add_char(b,c) appends character c to the end of b.

void add_substring(T , string_t , int offset, int len);

add_substring(b,s,ofs,len) takes len characters starting at offset ofs in string s and appends them to the end of b. If ofs and len do not specify a valid substring of s, then the function throws InvalidArg("Buffer::add_substring"). Note, the substring specified by offset and len may contain NUL (0) characters; in any case, the entire substring is appended to b, not just the substring up to the first NUL character.

void add_string(T , string_t );

add_string(b,s) appends the string s to the end of b.

void add_buffer(T buf_dest, T buf_source);

add_buffer(b1,b2) appends the current contents of b2 to the end of b1. b2 is not modified.

C.5   <core.h>

typedef const unsigned char ?`r string_t<`r>;

A string_t<`r> is a constant array of characters allocated in region `r.

typedef unsigned char ?`r mstring_t<`r>;

An mstring_t<`r> is a non-const (mutable) array of characters allocated in region `r.

typedef string_t<`r1> @`r2 stringptr_t<`r1,`r2>;

A stringptr_t<`r1,`r2> is used when a ``boxed'' string is needed, for example, you can have a list of string pointers, but not a list of strings.

typedef mstring_t<`r1> @`r2 mstringptr_t<`r1,`r2>;

mstringptr is the mutable version of stringptr_t.

typedef int bool ;

In Cyclone, we use bool as a synonym for int. We also define macros true and false, which are 1 and 0, respectively.

C.6   <dict.h>

typedef struct Dict<`a, `b, `r> @`r dict_t<`a,`b,`r>;

A value of type dict_t<`a,`b,`r> is a dictionary that maps keys of type `a to values of type `b; the dictionary datatypes live in region `r.

xtunion exn {   Present };

Present is thrown when a key is present but not expected.

xtunion exn {   Absent };

Absent is thrown when a key is absent but should be present.

dict_t<`a, `b> empty(int(@`H cmp)(`a, `a));

empty(cmp) returns an empty dictionary, allocated on the heap. cmp should be a comparison function on keys: cmp(k1,k2) should return a number less than, equal to, or greater than 0 according to whether k1 is less than, equal to, or greater than k2 in the ordering on keys.

dict_t<`a, `b, `r> rempty(`r, int(@`H cmp)(`a, `a));

rempty(r,cmp) is like empty(cmp) except that the dictionary is allocated in the region with handle r.

bool is_empty(dict_t d);

is_empty(d) returns true if d is empty, and returns false otherwise.

bool member(dict_t<`a> d, `a k);

member(d,k) returns true if k is mapped to some value in d, and returns false otherwise.

dict_t<`a, `b, `r> insert(dict_t<`a, `b, `r> d, `a k, `b v);

insert(d,k,v) returns a dictionary with the same mappings as d, except that k is mapped to v. The dictionary d is not modified.

dict_t<`a, `b, `r> insert_new(dict_t<`a, `b, `r> d, `a k, `b v);

insert_new(d,k,v) is like insert(d,k,v), except that it throws Present if k is already mapped to some value in d.

dict_t<`a, `b, `r> inserts(dict_t<`a, `b, `r> d, list_t<$(`a, `b)@> l);

inserts(d,l) inserts each key, value pair into d, returning the resulting dictionary.

dict_t<`a, `b> singleton(int(@`H cmp)(`a, `a), `a k, `b v);

singleton(cmp,k,v) returns a new heap-allocated dictionary with a single mapping, from k to v.

dict_t<`a, `b, `r> rsingleton(`r, int(@`H cmp)(`a, `a), `a k, `b v);

rsingleton(r,cmp,k,v) is like singleton(cmp,k,v), except the resulting dictionary is allocated in the region with handle r.

`b lookup(dict_t<`a, `b> d, `a k);

lookup(d,k) returns the value associated with key k in d, or throws Absent if k is not mapped to any value.

Core::opt_t<`b> lookup_opt(dict_t<`a, `b> d, `a k);

lookup_opt(d,k) returns NULL if k is not mapped to any value in d, and returns a non-NULL, heap-allocated option containing the value k is mapped to in d otherwise.

`b *`r rlookup_opt(`r, dict_t<`a, `b> d, `a k);

rlookup_opt(r,d,k) is like lookup_opt(d,k) except that any option returned will be allocated in the region with handle r.

bool lookup_bool(dict_t<`a, `b> d, `a k, `b @ans);

If d maps k to a value, then lookup_bool(d,k,ans) assigns that value to *ans and returns true; otherwise, it returns false.

`c fold(`c(@`H f)(`a, `b, `c), dict_t<`a, `b> d, `c accum);

If d has keys k1 through kn mapping to values v1 through vn, then fold(f,d,accum) returns f(k1,v1,...f(kn,vn,accum)...).

`c fold_c(`c(@`H f)(`d, `a, `b, `c), `d env, dict_t<`a, `b> d, `c accum);

fold_c(f,env,d,accum) is like fold(f,d,accum) except that f takes closure env as its first argument.

void app(`c(@`H f)(`a, `b), dict_t<`a, `b> d);

app(f,d) applies f to every key/value pair in d; the results of the applications are discarded. Note that f cannot return void.

void app_c(`c(@`H f)(`d, `a, `b), `d env, dict_t<`a, `b> d);

app_c(f,env,d) is like app(f,d) except that f takes closure env as its first argument.

void iter(void(@`H f)(`a, `b), dict_t<`a, `b> d);

iter(f,d) is like app(f,d) except that f returns void.

void iter_c(void(@`H f)(`c, `a, `b), `c env, dict_t<`a, `b> d);

iter_c(f,env,d) is like app_c(f,env,d) except that f returns void.

void iter2(void(@f)(`b, `b), dict_t<`a, `b> d1, dict_t<`a, `b> d2);

For every key k in the domain of both d1 and d2, iter2(f,d1,d2) performs f(lookup(d1,k), lookup(d2,k)). If there is any key present in d1 but not d2, then Absent is thrown.

void iter2_c(void(@f)(`c, `b, `b), `c env, dict_t<`a, `b> d1, dict_t<`a, `b> d2);

iter2_c is like iter except that f takes a closure as its first argument.

`c fold2_c(`c(@f)(`d, `a, `b1, `b2, `c), `d env, dict_t<`a, `b1> d1, dict_t<`a, `b2> d2, `c accum);

If k1 through kn are the keys of d1, then fold2_c(f,env,d1,d2,accum) returns f(env,k1,lookup(k1,d1),lookup(k1,d2), ... f(env,kn,lookup(kn,d1),lookup(kn,d2),accum)...). If there is any key present in d1 but not d2, then Absent is thrown.

dict_t<`a, `b, `r> rcopy(`r, dict_t<`a, `b>);

rcopy(r,d) returns a copy of d, newly allocated in the region with handle r.

dict_t<`a, `b> copy(dict_t<`a, `b>);

copy(r,d) returns a copy of d, newly allocated on the heap.

dict_t<`a, `c> map(`c(@`H f)(`b), dict_t<`a, `b> d);

map(f,d) applies f to each value in d, and returns a new dictionary with the results as values: for every binding of a key k to a value v in d, the result binds k to f(v). The returned dictionary is allocated on the heap.

dict_t<`a, `c, `r> rmap(`r, `c(@`H f)(`b), dict_t<`a, `b> d);

rmap(r,f,d) is like map(f,d), except the resulting dictionary is allocated in the region with handle r.

dict_t<`a, `c> map_c(`c(@`H f)(`d, `b), `d env, dict_t<`a, `b> d);

map_c(f,env,d) is like map(f,d) except that f takes env as its first argument.

dict_t<`a, `c, `r> rmap_c(`r, `c(@`H f)(`d, `b), `d env, dict_t<`a, `b> d);

rmap_c(r,f,env,d) is like map_c(f,env,d) except that the resulting dictionary is allocated in the region with handle r.

dict_t<`a, `b, `r> union_two_c(`b(@f)(`c, `a, `b, `b), `c env, dict_t<`a, `b, `r> d1, dict_t<`a, `b> d2);

union_two(f,env,d1,d2) returns a new dictionary with a binding for every key in d1 or d2. If a key appears in both d1 and d2, its value in the result is obtained by applying f to the two values, the key, and env. Note that the resulting dictionary is allocated in the same region as d2. (We don't use union as the name of the function, because union is a keyword in Cyclone.)

dict_t<`a, `b, `r> intersect(`b(@f)(`a, `b, `b), dict_t<`a, `b, `r> d1, dict_t<`a, `b, `r> d2);

intersect(f,d1,d2) returns a new dictionary with a binding for every key in both d1 and d2. For every key appearing in both d1 and d2, its value in the result is obtained by applying f to the key and the two values. Note that the input dictionaries and result must be allocated in the same region.

dict_t<`a, `b, `r> intersect_c(`b(@f)(`c, `a, `b, `b), `c env, dict_t<`a, `b, `r> d1, dict_t<`a, `b, `r> d2);

intersect_c(f,env,d1,d2) is like intersect(f,d1,d2), except that f takes env as its first argument.

bool forall_c(bool (@`H f)(`c, `a, `b), `c env, dict_t<`a, `b> d);

forall_c(f,env,d) returns true if f(env,k,v) returns true for every key k and associated value v in d, and returns false otherwise.

bool forall_intersect(bool (@`H f)(`a, `b, `b), dict_t<`a, `b> d1, dict_t<`a, `b> d2);

forall_intersect(f,d1,d2) returns true if f(k,v1,v2) returns true for every key k appearing in both d1 and d2, where v1 is the value of k in d1, and v2 is the value of k in d2; and it returns false otherwise.

$(`a, `b)@choose(dict_t<`a, `b> d);

choose(d) returns a key/value pair from d; if d is empty, Absent is thrown. The resulting pair is allocated on the heap.

$(`a, `b)@`r rchoose(`r, dict_t<`a, `b> d);

rchoose(r,d) is like choose(d), except the resulting pair is allocated in the region with handle r.

list_t<$(`a, `b)@> to_list(dict_t<`a, `b> d);

to_list(d) returns a list of the key/value pairs in d, allocated on the heap.

list_t<$(`a, `b)@`r, `r> rto_list(`r, dict_t<`a, `b> d);

rto_list(r,d) is like to_list(d), except that the resulting list is allocated in the region with handle r.

dict_t<`a, `b> filter(bool (@`H f)(`a, `b), dict_t<`a, `b> d);

filter(f,d) returns a dictionary that has a binding of k to v for every binding of k to v in d such that f(k,v) returns true. The resulting dictionary is allocated on the heap.

dict_t<`a, `b, `r> rfilter(`r, bool (@`H f)(`a, `b), dict_t<`a, `b> d);

rfilter(r,f,d) is like filter(f,d), except that the resulting dictionary is allocated in the region with handle r.

dict_t<`a, `b> filter_c(bool (@`H f)(`c, `a, `b), `c env, dict_t<`a, `b> d);

filter_c(f,env,d) is like filter(f,d) except that f takes a closure env as its first argument.

dict_t<`a, `b, `r> rfilter_c(`r, bool (@`H f)(`c, `a, `b), `c env, dict_t<`a, `b> d);

rfilter_c(r,f,env,d) is like filter_c(f,env,d), except that the resulting dictionary is allocated in the region with handle r.

dict_t<`a, `b> difference(dict_t<`a, `b> d1, dict_t<`a, `b> d2);

difference(d1,d2) returns a dictionary that has a binding of k to v for every binding of k to v in d1 where k is not in d2. (Note that the values of d2 are not relevant to difference(d1,d2).) The resulting dictionary is allocated on the heap.

dict_t<`a, `b, `r> rdifference(`r, dict_t<`a, `b> d1, dict_t<`a, `b> d2);

rdifference(d1,d2) is like difference(d1,d2), except that the resulting dictionary is allocated in the region with handle r.

dict_t<`a, `b> delete(dict_t<`a, `b>, `a);

delete(d,k) returns a dictionary with the same bindings as d, except that any binding of k is removed. The resulting dictionary is allocated on the heap.

dict_t<`a, `b, `r> rdelete(`r, dict_t<`a, `b>, `a);

rdelete(r,d,k) is like delete(d,k) except that the result is allocated in the region with handle r.

dict_t<`a, `b, `r> rdelete_same(dict_t<`a, `b, `r>, `a);

rdelete_same(d,k) is like delete(d,k), except that the resulting dictionary is allocated in the same region as the input dictionary d. This can be faster than delete(d,k) because it avoids a copy when k is not a member of d.

C.7   <filename.h>

mstring_t concat(string_t , string_t );

Assuming that s1 is a directory name and s2 is a file name, concat(s1,s2) returns a new (heap-allocated) file name for the child s2 of directory s1.

mstring_t chop_extension(string_t );

chop_extension(s) returns a copy of s with any file extension removed. A file extension is a period (`.') followed by a sequence of non-period characters. If s does not have a file extension, chop_extension(s) throws Core::Invalid_argument("chop_extension").

mstring_t dirname(string_t );

dirname(s) returns the directory part of s. For example, if s is "foo/bar/baz", dirname(s) returns "foo/bar".

mstring_t basename(string_t );

basename(s) returns the file part of s. For example, if s is "foo/bar/baz", basename(s) returns "baz".

bool check_suffix(string_t , string_t );

check_suffix(filename,suffix) returns true if filename ends in suffix, and returns false otherwise.

mstring_t gnuify(string_t );

gnuify(s) forces s to follow Unix file name conventions: any Windows separator characters (backslashes) are converted to Unix separator characters (forward slashes).

C.8   <fn.h>

typedef tunion

A value of type fn_t<`arg,`res,`eff> is a function and its closure; `arg is the argument type of the function, `res is the result type, and `eff is the effect.

fn_t<`arg, `res, `e1> make_fn(`res(@`H f)(`env, `arg;`e1+{}), `env x;`e2+{});

make_fn(f,env) builds a closure out of a function and an environment.

fn_t<`arg, `res, `e1> fp2fn(`res(@`H f)(`arg;`e1+{}));

fp2fn(f) converts a function pointer to a closure.

`res apply(fn_t<`arg, `res, `eff> f, `arg x;`eff+{});

apply(f,x) applies closure f to argument x (taking care of the hidden environment in the process).

fn_t<`a, `c, > compose<`a::?,`b::?,`c::?,`e1::?,`e2::?,`e3::?>(fn_t<`a, `b, `e1> g, fn_t<`b, `c, `e2> f;`e1+`e2+`e3+{});

compose(g,f) returns the composition of closures f and g; apply(compose(g,f),x) has the same effect as apply(f,apply(g,x)).

fn_t<`a, fn_t<`b, `c, `e1>, > curry(fn_t<$(`a, `b)@`H, `c, `e1> f);

curry(f) curries a closure that takes a pair as argument: if x points to a pair $(x1,x2), then apply(f,x) has the same effect as apply(apply(curry(f),x1),x2).

fn_t<$(`a, `b)@, `c, > uncurry(fn_t<`a, fn_t<`b, `c, `e1>, `e2> f);

uncurry(f) converts a closure that takes two arguments in sequence into a closure that takes the two arguments as a pair: if x points to a pair $(x1,x2), then apply(uncurry(f),x) has the same effect as apply(apply(f,x1),x2).

List::list_t<`b> map_fn(fn_t<`a, `b, `e> f, List::list_t<`a> x);

map_fn(f,x) maps the closure f on the list x: if x has elements x1 through xn, then map_fn(f,x) returns a new heap-allocated list with elements apply(f,x1) through apply(f,xn).

C.9   <hashtable.h>

typedef struct Table<`a, `b> @table_t<`a,`b>;

A table_t<`a,`b> is a hash table with keys of type `a and values of type `b.

table_t<`a, `b> create(int sz, int(@`H cmp)(`a, `a), int(@`H hash)(`a));

create(sz,cmp,hash) returns a new hash table that starts out with sz buckets. cmp should be a comparison function on keys: cmp(k1,k2) should return a number less than, equal to, or greater than 0 according to whether k1 is less than, equal to, or greater than k2. hash should be a hash function on keys. cmp and hash should satisfy the following property: if cmp(k1,k2) is 0, then hash(k1) must equal hash(k2).

void insert(table_t<`a, `b> t, `a key, `b val);

insert(t,key,val) binds key to value in t.

`b lookup(table_t<`a, `b> t, `a key);

lookup(t,key) returns the value associated with key in t, or throws Not_found if there is no value associate with key in t.

void resize(table_t<`a, `b> t);

resize(t) increases the size (number of buckets) in table t. resize is called automatically by functions like insert when the buckets of a hash table get large, however, it can also be called by the programmer explicitly.

void remove(table_t<`a, `b> t, `a key);

remove(t,key) removes the most recent binding of key from t; the next-most-recent binding of key (if any) is restored. If there is no value associated with key in t, remove returns silently.

int hash_string(string_t s);

hash_string(s) returns a hash of a string s. It is provided as a convenience for making hash tables mapping strings to values.

int hash_stringptr(stringptr_t p);

hash_stringptr(p) returns a hash of a string pointer p.

void iter(void(@`H f)(`a, `b), table_t<`a, `b> t);

iter(f,t) applies f to each key/value pair in t.

void iter_c(void(@`H f)(`a, `b, `c), table_t<`a, `b> t, `c env);

iter_c(f,t,e) calls f(k,v,e) for each key/value pair (k,v).

C.10   <list.h>

struct List<`a,`r> {   `a hd;   struct List<`a, `r> *`r tl; };

A struct List is a memory cell with a head field containing an element and a tail field that points to the rest of the list. Such a structure is traditionally called a cons cell. Note that every element of the list must have the same type `a, and every cons cell in the list must be allocated in the same region `r.

typedef struct List<`a, `r> *`r list_t<`a,`r>;

A list_t is a possibly-NULL pointer to a struct List. Most of the functions in namespace List operate on values of type list_t rather than struct List. Note that a list_t can be empty (NULL) but a struct List cannot.

typedef struct List<`a, `r> @List_t<`a,`r>;

A List_t is a non-NULL pointer to a struct List. This is used much less often than list_t, however it may be useful when you want to emphasize that a list has at least one element.

list_t<`a> list(...`a);

list(x1,...,xn) builds a heap-allocated list with elements x1 through xn.

list_t<`a, `r> rlist(`r, ...`a);

rlist(r, x1,...,xn) builds a list with elements x1 through xn, allocated in the region with handle r.

int length(list_t x);

length(x) returns the number of elements in list x.

`a hd(list_t<`a> x);

hd(x) returns the first element of list x, if there is one, and throws Failure("hd") if x is NULL.

list_t<`a, `r> tl(list_t<`a, `r> x);

tl(x) returns the tail of list x, if there is one, and throws Failure("tl") if x is NULL.

list_t<`a> copy(list_t<`a> x);

copy(x) returns a new heap-allocated copy of list x.

list_t<`a, `r> rcopy(`r, list_t<`a> x);

rcopy(r,x) returns a new copy of list x, allocated in the region with handle r.

list_t<`b> map(`b(@`H f)(`a), list_t<`a> x);

If x has elements x1 through xn, then map(f,x) returns list(f(x1),...,f(xn)).

list_t<`b, `r> rmap(`r, `b(@`H f)(`a), list_t<`a> x);

If x has elements x1 through xn, then rmap(r,f,x) returns rlist(r,f(x1),...,f(xn)).

list_t<`b> map_c(`b(@`H f)(`c, `a), `c env, list_t<`a> x);

map_c is a version of map where the function argument requires a closure as its first argument.

list_t<`b, `r> rmap_c(`r, `b(@`H f)(`c, `a), `c env, list_t<`a> x);

rmap_c is a version of rmap where the function argument requires a closure as its first argument.

xtunion exn {   List_mismatch };

List_mismatch is thrown when two lists don't have the same length.

list_t<`c> map2(`c(@`H f)(`a, `b), list_t<`a> x, list_t<`b> y);

If x has elements x1 through xn, and y has elements y1 through yn, then map2(f,x,y) returns a new heap-allocated list with elements f(x1,y1) through f(xn,yn). If x and y don't have the same number of elements, List_mismatch is thrown.

list_t<`c, `r> rmap2(`r, `c(@`H f)(`a, `b), list_t<`a> x, list_t<`b> y);

rmap2(r,f,x,y) is like map2(f,x,y), except that the resulting list is allocated in the region with handle r.

void app(`b(@`H f)(`a), list_t<`a> x);

app(f,x) applies f to each element of x, discarding the results. Note that f must not return void.

void app_c(`c(@`H f)(`a, `b), `a, list_t<`b> x);

app_c is a version of app where the function argument requires a closure as its first argument.

void app2(`c(@`H f)(`a, `b), list_t<`a> x, list_t<`b> y);

If x has elements x1 through xn, and y has elements y1 through yn, then app2(f,x,y) performs f(x1,y1) through f(xn,yn) and discards the results. If x and y don't have the same number of elements, List_mismatch is thrown.

void app2_c(`d(@`H f)(`a, `b, `c), `a env, list_t<`b> x, list_t<`c> y);

app2_c is a version of app2 where the function argument requires a closure as its first argument.

void iter(void(@`H f)(`a), list_t<`a> x);

iter(f,x) is like app(f,x), except that f returns void.

void iter_c(void(@`H f)(`b, `a), `b env, list_t<`a> x);

iter_c is a version of iter where the function argument requires a closure as its first argument.

void iter2(void(@`H f)(`a, `b), list_t<`a> x, list_t<`b> y);

iter2 is a version of app2 where the function returns void.

void iter2_c(void(@`H f)(`a, `b, `c), `a env, list_t<`b> x, list_t<`c> y);

iter2_c is a version of iter2 where the function argument requires a closure as its first argument.

`a fold_left(`a(@`H f)(`a, `b), `a accum, list_t<`b> x);

If x has elements x1 through xn, then fold_left(f,accum,x) returns f(f(...(f(x2,f(x1,accum))),xn-1),xn).

`a fold_left_c(`a(@`H f)(`c, `a, `b), `c, `a accum, list_t<`b> x);

fold_left_c is a version of fold_left where the function argument requires a closure as its first argument.

`b fold_right(`b(@`H f)(`a, `b), list_t<`a> x, `b accum);

If x has elements x1 through xn, then fold_left(f,accum,x) returns f(x1,f(x2,...,f(xn-1,f(xn,a))...)).

`b fold_right_c(`b(@`H f)(`c, `a, `b), `c, list_t<`a> x, `b accum);

fold_right_c is a version of fold_right where the function argument requires a closure as its first argument.

list_t<`a> revappend(list_t<`a, `r> x, list_t<`a, > y);

If x has elements x1 through xn, revappend(x,y) returns a list that starts with elements xn through x1, then continues with y. Cons cells for the first n elements are newly-allocated on the heap, and y must be allocated on the heap.

list_t<`a, `r> rrevappend(`r, list_t<`a> x, list_t<`a, `r> y);

rrevappend(r,x,y) is like revappend(x,y), except that y must be allocated in the region with handle r, and the result is allocated in the same region.

list_t<`a> rev(list_t<`a> x);

rev(x) returns a new heap-allocated list whose elements are the elements of x in reverse.

list_t<`a, `r> rrev(`r, list_t<`a> x);

rrev(r,x) is like rev(x), except that the result is allocated in the region with handle r.

list_t<`a, `r> imp_rev(list_t<`a, `r> x);

imp_rev(x) imperatively reverses list x (the list is side-effected). Note that imp_rev returns a list. This is because the first cons cell of the result is the last cons cell of the input; a typical use is therefore x = imp_rev(x).

list_t<`a> append(list_t<`a> x, list_t<`a, > y);

If x has elements x1 through xn, append(x,y) returns a list that starts with elements x1 through xn, then continues with y. Cons cells for the first n elements are newly-allocated on the heap, and y must be allocated on the heap.

list_t<`a, `r> rappend(`r, list_t<`a> x, list_t<`a, `r> y);

rappend(r,x,y) is like append(x,y), except that y must be allocated in the region with handle r, and the result is allocated in the same region.

list_t<`a, `r> imp_append(list_t<`a, `r> x, list_t<`a, `r> y);

imp_append(x,y) modifies x to append y to it, destructively. Note that imp_append returns a list. This is because x might be NULL, in which case, imp_append(x,y) returns y; so a typical use would be x = imp_append(x,y).

list_t<`a> flatten(list_t<list_t<`a, >> x);

In flatten(x), x is a list of lists, and the result is a new heap-allocated list with elements from each list in x, in sequence. Note that x must be allocated on the heap.

list_t<`a, `r> rflatten(`r, list_t<list_t<`a, `r>> x);

rflatten(r,x) is like flatten(x), except that the result is allocated in the region with handle r, and each element of x must be allocated in r.

list_t<`a> merge_sort(int(@`H cmp)(`a, `a), list_t<`a> x);

merge_sort(cmp,x) returns a new heap-allocated list whose elements are the elements of x in ascending order (according to the comparison function cmp), by the MergeSort algorithm.

list_t<`a, `r> rmerge_sort(`r, int(@`H cmp)(`a, `a), list_t<`a> x);

rmerge_sort(r,x) is like merge_sort(x), except that the result is allocated in the region with handle r.

list_t<`a, `r> rimp_merge_sort(int(@`H cmp)(`a, `a), list_t<`a, `r> x);

rimp_merge_sort is an imperative version of rmerge_sort: the list is sorted in place. rimp_merge_sort returns a list because the first cons cell of the sorted list might be different from the first cons cell of the input list; a typical use is x = rimp_merge_sort(cmp,x).

list_t<`a> merge(int(@`H cmp)(`a, `a), list_t<`a, > x, list_t<`a, > y);

merge(cmp,x,y) returns the merge of two sorted lists, according to the cmp function.

list_t<`a, `r3> rmerge(`r3, int(@`H cmp)(`a, `a), list_t<`a> a, list_t<`a> b);

rmerge(r,cmp,x,y) is like merge(cmp,x,y), except that x, y, and the result are allocated in the region with handle r.

list_t<`a, `r> imp_merge(int(@`H cmp)(`a, `a), list_t<`a, `r> a, list_t<`a, `r> b);

imp_merge is an imperative version of merge.

xtunion exn {   Nth };

Nth is thrown when nth doesn't have enough elements in the list.

`a nth(list_t<`a> x, int n);

If x has elements x0 through xm, and 0<=n<=m, then nth(x,n) returns xn. If n is out of range, Nth is thrown. Note that the indexing is 0-based.

list_t<`a, `r> nth_tail(list_t<`a, `r> x, int i);

If x has elements x0 through xm, and 0<=n<=m, then nth(x,n) returns the list with elements xn through xm. If n is out of range, Nth is thrown.

bool forall(bool (@`H pred)(`a), list_t<`a> x);

forall(pred,x) returns true if pred returns true when applied to every element of x, and returns false otherwise.

bool forall_c(bool (@`H pred)(`a, `b), `a env, list_t<`b> x);

forall_c is a version of forall where the function argument requires a closure as its first argument.

bool exists(bool (@`H pred)(`a), list_t<`a> x);

exists(pred,x) returns true if pred returns true when applied to some element of x, and returns false otherwise.

bool exists_c(bool (@`H pred)(`a, `b), `a env, list_t<`b> x);

exists_c is a version of exists where the function argument requires a closure as its first argument.

list_t<$(`a, `b)@`H, > zip(list_t<`a> x, list_t<`b> y);

If x has elements x1 through xn, and y has elements y1 through yn, then zip(x,y) returns a new heap-allocated array with elements &$(x1,y1) through &$(xn,yn). If x and y don't have the same number of elements, List_mismatch is thrown.

list_t<$(`a, `b)@`r2, `r1> rzip(`r1 r1, `r2 r2, list_t<`a> x, list_t<`b> y);

rzip(r1,r2,x,y) is like zip(x,y), except that the list returned is allocated in the region with handle r1, and the pairs of that list are allocated in the region with handle r2.

$(list_t<`a>, list_t<`b>)split(list_t<$(`a, `b)@> x);

If x has elements &$(a1,b1) through &$(an,bn), then split(x) returns a pair of new heap-allocated arrays with elements a1 through an, and b1 through bn.

$(list_t<`a>, list_t<`b>, list_t<`c>)split3(list_t<$(`a, `b, `c)@> x);

If x has elements &$(a1,b1,c1) through &$(an,bn,cn), then split(x) returns a triple of new heap-allocated arrays with elements a1 through an, and b1 through bn, and c1 through cn.

$(list_t<`a, `r1>, list_t<`b, `r2>)rsplit(`r1 r1, `r2 r2, list_t<$(`a, `b)@> x);

rsplit(r1,r2,x) is like split(x), except that the first list returned is allocated in the region with handle r1, and the second list returned is allocated in the region with handle r2.

$(list_t<`a, `r3>, list_t<`b, `r4>, list_t<`c, `r5>)rsplit3(`r3 r3, `r4 r4, `r5 r5, list_t<$(`a, `b, `c)@> x);

rsplit(r1,r2,r3,x) is like split3(x), except that the first list returned is allocated in the region with handle r1, the second list returned is allocated in the region with handle r2, and the third list returned is allocated in the region with handle r3.

bool memq(list_t<`a> l, `a x);

memq(l,x) returns true if x is == an element of list l, and returns false otherwise.

bool mem(int(@`H compare)(`a, `a), list_t<`a> l, `a x);

mem(cmp,l,x) is like memq(l,x) except that the comparison function cmp is used to determine if x is an element of l. cmp(a,b) should return 0 if a is equal to b, and return a non-zero number otherwise.

`b assoc(list_t<$(`a, `b)@> l, `a k);

An association list is a list of pairs where the first element of each pair is a key and the second element is a value; the association list is said to map keys to values. assoc(l,k) returns the first value paired with key k in association list l, or throws Core::Not_found if k is not paired with any value in l. assoc uses == to decide if k is a key in l.

`b assoc_cmp(int(@`H cmp)(`a, `c), list_t<$(`a, `b)@> l, `c x);

assoc_cmp(cmp,l,k) is like assoc(l,k) except that the comparison function cmp is used to decide if k is a key in l. cmp should return 0 if two keys are equal, and non-zero otherwise.

bool mem_assoc(list_t<$(`a, `b)@> l, `a x);

mem_assoc(l,k) returns true if k is a key in association list l (according to ==).

list_t<`a, `r> delete(list_t<`a, `r> l, `a x);

delete(l,k) returns the list with the first occurence of x removed from it, if x was in the list; otherwise raises Core::Not_found.

Core::opt_t<`c> check_unique(int(@`H cmp)(`c, `c), list_t<`c> x);

check_unique(cmp,x) checks whether the sorted list x has duplicate elements, according to cmp. If there are any duplicates, one will be returned; otherwise, NULL is returned.

`a ?`H to_array(list_t<`a> x);

to_array(x) returns a new heap-allocated array with the same elements as list x.

`a ?`r rto_array(`r r, list_t<`a> x);

rto_array(r,x) is like to_array(x), except that the resulting array is allocated in the region with handle r.

list_t<`a> from_array(`a ?arr);

from_array(x) returns a new heap-allocated list with the same elements as array x.

list_t<`a, `r2> rfrom_array(`r2 r2, `a ?arr);

rfrom_array(r,x) is like from_array(x), except that the resulting list is allocated in the region with handle r.

int list_cmp(int(@`H cmp)(`a, `a), list_t<`a> l1, list_t<`a> l2);

list_cmp(cmp,l1,l2) is a comparison function on lists, parameterized by a comparison function cmp on list elements.

bool list_prefix(int(@`H cmp)(`a, `a), list_t<`a> l1, list_t<`a> l2);

list_prefix(cmp,l1,l2) returns true if l1 is a prefix of l2, using cmp to compare the elements of l1 and l2.

list_t<`a> filter(bool (@`H f)(`a), list_t<`a> x);

filter(f,x) returns a new heap-allocated list whose elements are the elements of x on which f returns true, in order.

list_t<`a> filter_c(bool (@`H f)(`b, `a), `b env, list_t<`a> x);

filter_c is a version of filter where the function argument requires a closure as its first argument.

list_t<`a, `r> rfilter(`r r, bool (@`H f)(`a), list_t<`a> x);

rfilter_c(r,f,x) is like filter_c(f,x), except that the resulting list is allocated in the region with handle r.

list_t<`a, `r> rfilter_c(`r r, bool (@`H f)(`b, `a), `b env, list_t<`a> x);

rfilter_c is a version of rfilter where the function argument requires a closure as its first argument.

C.11   <pp.h>

typedef struct Doc @doc_t ;

A value of type doc_t is a ``document'' that can be combined with other documents, formatted at different widths, converted to strings or files.

void file_of_doc(doc_t d, int w, FILE @f);

file_of_doc(d,w,f) formats d to width w, and prints the formatted output to f.

string_t string_of_doc(doc_t d, int w);

string_of_doc(d,w) formats d to width w, and returns the formatted output in a heap-allocated string.

$(string_t , list_t<$(int, int, int, string_t )@>)@string_and_links(doc_t d, int w);

string_and_links(d,w) formats d to width w, returns the formatted output in a heap-allocated string, and returns in addition a list of hyperlinks. Each hyperlink has the form $(line,char,length,contents), where line and char give the line and character in the formatted output where the hyperlink starts, length gives the number of characters of the hyperlink, and contents is a string that the hyperlink should point to. The line, char, and length are exactly what is needed to create a hyperlink in a Tk text widget.

doc_t nil_doc();

nil_doc() returns an empty document.

doc_t blank_doc();

blank_doc() returns a document consisting of a single space character.

doc_t line_doc();

line_doc() returns a document consisting of a single line break.

doc_t oline_doc();

oline_doc() returns a document consisting of an optional line break; when the document is formatted, the pretty printer will decide whether to break the line.

doc_t text(string_t<> s);

text(s) returns a document containing exactly the string s.

doc_t textptr(stringptr_t<> p);

textptr(p) returns a documents containing exactly the string pointed to by p.

doc_t hyperlink(string_t<> shrt, string_t<> full);

hyperlink(shrt,full) returns a document that will be formatted as the string shrt linked to the string full.

doc_t nest(int k, doc_t d);

nest(k,d) returns a document that will be formatted like document d, but indented by k spaces.

doc_t cat(...doc_t );

cat(d1, d2, ..., dn) returns a document consisting of document d1 followed by d2, and so on up to dn.

doc_t cats(list_t<doc_t , > doclist);

cats(l) returns a document containing all of the documents in list l, in order.

doc_t cats_arr(doc_t ?`H docs);

cats_arr(a) returns a document containing all of the documents in array a, in order.

doc_t doc_union(doc_t d1, doc_t d2);

doc_union(d1,d2) does ?? FIX.

doc_t tab(doc_t d);

tab(d) returns a document formatted like d but indented by a tab stop.

doc_t seq(string_t<> sep, list_t<doc_t , > l);

seq(sep,l) returns a document consisting of each document of l, in sequence, with string sep between each adjacent element of l.

doc_t ppseq(doc_t (@`H pp)(`a), string_t<> sep, list_t<`a, > l);

ppseq is a more general form of seq: in ppseq(pp,sep,l), l is a list of values to pretty print in sequence, pp is a function that knows how to pretty print a value, and sep is a string to print between each value.

doc_t seql(string_t<> sep, list_t<doc_t , > l0);

seql is like seq, except that the resulting document has line breaks after each separator.

doc_t ppseql(doc_t (@`H pp)(`a), string_t<> sep, list_t<`a, > l);

ppseql is like ppseq, except that the resulting document has line breaks after each separator.

doc_t group(string_t<> start, string_t<> stop, string_t<> sep, list_t<doc_t , > l);

group(start,stop,sep,l) is like cat(text(start), seq(sep,l), text(stop)).

doc_t groupl(string_t<> start, string_t<> stop, string_t<> sep, list_t<doc_t , > l);

groupl is like group but a line break is inserted after each separator.

doc_t egroup(string_t<> start, string_t<> stop, string_t<> sep, list_t<doc_t , > l);

egroup is like group, except that the empty document is returned if the list is empty.

C.12   <queue.h>

typedef struct Queue<`a, `r> @`r queue_t<`a,`r>;

A value of type queue_t<`a,`r> is a first-in, first-out queue of elements of type `a; the queue data structures are allocated in region `r.

bool is_empty(queue_t );

is_empty(q) returns true if q contains no elements, and returns false otherwise.

queue_t create();

create() allocates a new, empty queue on the heap and returns it.

void add(queue_t<`a, >, `a x);

add(q,x) adds x to the end of q (by side effect).

void radd(`r, queue_t<`a, `r>, `a x);

radd(r,q,x) is like add(q,x) except that the queue lives in the region with handle r.

xtunion exn {   Empty };

Empty is an exception raised by take and peek.

`a take(queue_t<`a>);

take(q) removes the element from the front on q and returns it; if q is empty, exception Empty is thrown.

`a peek(queue_t<`a>);

peek(q) returns the element at the front of q, without removing it from q. If q is empty, exception Empty is thrown.

void clear(queue_t<`a>);

clear(q) removes all elements from q.

int length(queue_t<`a>);

length(q) returns the number of elements in q.

void iter(void(@`H f)(`a), queue_t<`a>);

iter(f,q) applies f to each element of q, from first to last. Note that f must return void.

void app(`b(@`H f)(`a), queue_t<`a>);

app(f,q) applies f to each element of q, from first to last. Note that f must return a value of kind M.

C.13   <rope.h>

typedef struct Rope_node @rope_t ;

A value of type rope_t is a character array that can be efficiently concatenated.

rope_t from_string(string_t<>);

from_string(s) returns a rope that has the same characters as string s. Note that s must be heap-allocated.

mstring_t to_string(rope_t );

to_string(r) returns a new, heap-allocated string with the same characters as rope r.

rope_t concat(rope_t , rope_t );

concat(r1,r2) returns a rope whose characters are the characters of r1 followed by the characters of r2.

rope_t concata(rope_t ?`H);

concata(a) returns a rope that contains the concatenation of the characters in the array a of ropes.

rope_t concatl(List::list_t<rope_t >);

concata(l) returns a rope that contains the concatenation of the characters in the list l of ropes.

unsigned int length(rope_t );

length(r) returns the number of characters in the rope r, up to but not including the first NUL character.

int cmp(rope_t , rope_t );

cmp(r1,r2) is a comparison function on ropes: it returns a number less than, equal to, or greater than 0 according to whether the character array of r1 is lexicographically less than, equal to, or greater than the character array of r2.

C.14   <set.h>

typedef struct Set<`a, `r> @`r set_t<`a,`r>;

A value of type set_t<`a,`r> is a set with elements of type `a. The data structures used to implement the set (not the elements of the set!) are in region `r.

set_t<`a> empty(int(@`H cmp)(`a, `a));

empty(cmp) creates an empty set given comparison function cmp. The set is heap-allocated.

set_t<`a, `r> rempty(`r r, int(@`H cmp)(`a, `a));

rempty(r,cmp) creates an empty set in the region with handle r.

set_t<`a> singleton(int(@`H cmp)(`a, `a), `a x);

singleton(cmp,x) creates a set on the heap with a single element, x.

set_t<`a> from_list(int(@`H cmp)(`a, `a), list_t<`a> l);

from_list(cmp,l) creates a set on the heap; the elements of the set are the elements of the list l.

set_t<`a> insert(set_t<`a, > s, `a elt);

insert(s,elt) returns a set containing all the elements of s, plus elt. The set s is not modified.

set_t<`a, `r> rinsert(`r r, set_t<`a, `r> s, `a elt);

rinsert(r,s,elt) is like insert(s,elt), except that it works on sets allocated in the region with handle r.

set_t<`a> union_two(set_t<`a, > s1, set_t<`a, > s2);

union_two(s1,s2) returns a set whose elements are the union of the elements of s1 and s2. (We use the name union_two because union is a keyword in Cyclone.)

set_t<`a> intersect(set_t<`a, > s1, set_t<`a, > s2);

intersect(s1,s2) returns a set whose elements are the intersection of the elements of s1 and s2.

set_t<`a> diff(set_t<`a, > s1, set_t<`a, > s2);

diff(s1,s2) returns a set whose elements are the elements of s1 that are not members of s2.

set_t<`a> delete(set_t<`a, > s, `a elt);

delete(s,elt) returns a set whose elements are the elements of s, minus elt.

int cardinality(set_t s);

cardinality(s) returns the number of elements in the set s.

bool is_empty(set_t s);

is_empty(s) returns true if s has no members, and returns false otherwise.

bool member(set_t<`a> s, `a elt);

member(s,elt) returns true if elt is a member of s, and returns false otherwise.

bool subset(set_t<`a> s1, set_t<`a> s2);

subset(s1,s2) returns true if s1 is a subset of s2, and returns false otherwise.

int setcmp(set_t<`a> s1, set_t<`a> s2);

setcmp(s1,s2) returns a number less than, equal to, or greater than 0 according to whether s1 is less than, equal to, or greater than s2 in the subset order.

bool equals(set_t<`a> s1, set_t<`a> s2);

equals(s1,s2) returns true if s1 equals s2 have the same elements, and returns false otherwise.

list_t<`a, `r> elements(set_t<`a, `r> s);

elements(s) returns a list of the elements of s, in no particular order. Note that the returned list is allocated in the same region as the set s.

`b fold(`b(@`H f)(`a, `b), set_t<`a> s, `b accum);

If s is a set with elements x1 through xn, then fold(f,s,accum) returns f(x1,f(x2,f(...,f(xn,accum)...))).

`b fold_c(`b(@`H f)(`c, `a, `b), `c env, set_t<`a> s, `b accum);

fold_c(f,env,s,accum) is like fold, except that the function f takes an extra (closure) argument, env.

void app(`b(@`H f)(`a), set_t<`a> s);

app(f,s) applies f to each element of s, in no particular order; the result of the application is discared. Notice that f cannot return void; use iter instead of app for that.

void iter(void(@`H f)(`a), set_t<`a> s);

iter(f,s) is like app(f,s), except that f must return void.

void iter_c(void(@`H f)(`c, `a), `c env, set_t<`a> s);

iter_c is a version of iter where the function argument f requires a closure.

xtunion exn {   Absent };

Absent is an exception thrown by the choose function.

`a choose(set_t<`a> s);

choose(s) returns some element of the set s; if the set is empty, choose throws Absent.

C.15   <slowdict.h>

typedef struct Dict<`a, `b> @dict_t<`a,`b>;

A value of type dict_t<`a,`b> is a dictionary that maps keys of type `a to values of type `b.

xtunion exn {   Present };

Present is thrown when a key is present but not expected.

xtunion exn {   Absent };

Absent is thrown when a key is absent but should be present.

dict_t<`a, `b> empty(int(@`H cmp)(`a, `a));

empty(cmp) returns an empty dictionary, allocated on the heap. cmp should be a comparison function on keys: cmp(k1,k2) should return a number less than, equal to, or greater than 0 according to whether k1 is less than, equal to, or greater than k2 in the ordering on keys.

bool is_empty(dict_t d);

is_empty(d) returns true if d is empty, and returns false otherwise.

bool member(dict_t<`a> d, `a k);

member(d,k) returns true if k is mapped to some value in d, and returns false otherwise.

dict_t<`a, `b> insert(dict_t<`a, `b> d, `a k, `b v);

insert(d,k,v) returns a dictionary with the same mappings as d, except that k is mapped to v. The dictionary d is not modified.

dict_t<`a, `b> insert_new(dict_t<`a, `b> d, `a k, `b v);

insert_new(d,k,v) is like insert(d,k,v), except that it throws Present if k is already mapped to some value in d.

dict_t<`a, `b> inserts(dict_t<`a, `b> d, list_t<$(`a, `b)@> l);

inserts(d,l) inserts each key, value pair into d, returning the resulting dictionary.

dict_t<`a, `b> singleton(int(@`H cmp)(`a, `a), `a k, `b v);

singleton(cmp,k,v) returns a new heap-allocated dictionary with a single mapping, from k to v.

`b lookup(dict_t<`a, `b> d, `a k);

lookup(d,k) returns the value associated with key k in d, or throws Absent if k is not mapped to any value.

Core::opt_t<`b> lookup_opt(dict_t<`a, `b> d, `a k);

lookup_opt(d,k) returns NULL if k is not mapped to any value in d, and returns a non-NULL, heap-allocated option containing the value k is mapped to in d otherwise.

dict_t<`a, `b> delete(dict_t<`a, `b> d, `a k);

delete(d,k) returns a dictionary with the same bindings as d, except that any binding of k is removed. The resulting dictionary is allocated on the heap.

dict_t<`a, `b> delete_present(dict_t<`a, `b> d, `a k);

delete_present(d,k) is like delete(d,k), except that Absent is thrown if k has no binding in d.

`c fold(`c(@`H f)(`a, `b, `c), dict_t<`a, `b> d, `c accum);

If d has keys k1 through kn mapping to values v1 through vn, then fold(f,d,accum) returns f(k1,v1,...f(kn,vn,accum)...).

`c fold_c(`c(@`H f)(`d, `a, `b, `c), `d env, dict_t<`a, `b> d, `c accum);

fold_c(f,env,d,accum) is like fold(f,d,accum) except that f takes closure env as its first argument.

void app(`c(@`H f)(`a, `b), dict_t<`a, `b> d);

app(f,d) applies f to every key/value pair in d; the results of the applications are discarded. Note that f cannot return void.

void app_c(`c(@`H f)(`d, `a, `b), `d env, dict_t<`a, `b> d);

app_c(f,env,d) is like app(f,d) except that f takes closure env as its first argument.

void iter(void(@`H f)(`a, `b), dict_t<`a, `b> d);

iter(f,d) is like app(f,d) except that f returns void.

void iter_c(void(@`H f)(`c, `a, `b), `c env, dict_t<`a, `b> d);

iter_c(f,env,d) is like app_c(f,env,d) except that f returns void.

dict_t<`a, `c> map(`c(@`H f)(`b), dict_t<`a, `b> d);

map(f,d) applies f to each value in d, and returns a new dictionary with the results as values: for every binding of a key k to a value v in d, the result binds k to f(v). The returned dictionary is allocated on the heap.

dict_t<`a, `c> map_c(`c(@`H f)(`d, `b), `d env, dict_t<`a, `b> d);

map_c(f,env,d) is like map(f,d) except that f takes a closure env as its first argument.

$(`a, `b)@choose(dict_t<`a, `b> d);

choose(d) returns a key/value pair from d; if d is empty, Absent is thrown. The resulting pair is allocated on the heap.

list_t<$(`a, `b)@> to_list(dict_t<`a, `b> d);

to_list(d) returns a list of the key/value pairs in d, allocated on the heap.

C.16   <xarray.h>

typedef struct Xarray<`a> @xarray_t<`a>;

An xarray_t is an extensible array.

int length(xarray_t<`a>);

length(a) returns the length of extensible array a.

`a get(xarray_t<`a>, int);

get(a,n) returns the nth element of a, or throws Invalid_argument if n is out of range.

void set(xarray_t<`a>, int, `a);

set(a,n,v) sets the nth element of a to v, or throws Invalid_argument if n is out of range.

xarray_t<`a> create(int, `a);

create(n,v) returns a new extensible array with starting size n and default value v.

xarray_t<`a> create_empty();

create_empty() returns a new extensible array with starting size 0.

xarray_t<`a> singleton(int, `a);

singleton(n,v) returns a new extensible array with a single element v.

void add(xarray_t<`a>, `a);

add(a,v) makes the extensible array larger by adding v to the end.

int add_ind(xarray_t<`a>, `a);

add_ind(a,v) makes a larger by adding v to the end, and returns v.

`a ?to_array(xarray_t<`a>);

to_array(a) returns a normal (non-extensible) array with the same elements as a.

xarray_t<`a> from_array(`a ?arr);

from_array(a) returns an extensible array with the same elements as the normal (non-extensible) array a.

xarray_t<`a> append(xarray_t<`a>, xarray_t<`a>);

append(a1,a2) returns a new extensible array whose elements are the elements of a1 followed by a2. The inputs a1 and a2 are not modified.

void app(`b(@`H f)(`a), xarray_t<`a>);

app(f,a) applies f to each element of a, in order from lowest to highest. Note that f returns `a, unlike with iter.

void app_c(`b(@`H f)(`c, `a), `c, xarray_t<`a>);

app_c(f,e,a) applies f to e and each element of a, in order from lowest to highest.

void iter(void(@`H f)(`a), xarray_t<`a>);

iter(f,a) applies f to each element of a, in order from lowest to highest. Note that f returns void, unlike with app.

void iter_c(void(@`H f)(`b, `a), `b, xarray_t<`a>);

iter_c(f,e,a) applies f to e and each element of a, in order from lowest to highest.

xarray_t<`b> map(`b(@`H f)(`a), xarray_t<`a>);

map(f,a) returns a new extensible array whose elements are obtained by applying f to each element of a.

xarray_t<`b> map_c(`b(@`H f)(`c, `a), `c, xarray_t<`a>);

map_c(f,e,a) returns a new extensible array whose elements are obtained by applying f to e and each element of a.

void reuse(xarray_t<`a> xarr);

reuse(a) sets the number of elements of a to zero, but does not free the underlying array.

void delete(xarray_t<`a> xarr, int num);

delete(a,n) deletes the last n elements of a.

void remove(xarray_t<`a> xarr, int i);

remove(a,i) removes the element at position i from a; elements at positions greater than i are moved down one position.