Rename Array -> List in all code and docs

30 files changed, 1164 insertions, 1164 deletions

diff --git a/src/stdlib/README.md b/src/stdlib/README.md
index 1c72d3d3..671d330a 100644
--- a/src/stdlib/README.md
+++ b/src/stdlib/README.md
@@ -16,7 +16,7 @@ some common functionality.
 ## Core Data Types
 
 - Datatypes (type definitions): [datatypes.h](datatypes.h), [datatypes.c](datatypes.c)
-- Arrays: [arrays.h](arrays.h), [arrays.c](arrays.c)
+- Lists: [lists.h](lists.h), [lists.c](lists.c)
 - Bools: [bools.h](bools.h), [bools.c](bools.c)
 - Bytes: [bytes.h](bytes.h), [bytes.c](bytes.c)
 - C Strings: [c_strings.h](c_strings.h), [c_strings.c](c_strings.c)
diff --git a/src/stdlib/arrays.c b/src/stdlib/arrays.c
deleted file mode 100644
index c8b82cf4..00000000
--- a/src/stdlib/arrays.c
+++ /dev/null
@@ -1,813 +0,0 @@
-// Functions that operate on arrays
-
-#include <gc.h>
-#include <stdbool.h>
-#include <stdint.h>
-#include <sys/param.h>
-
-#include "arrays.h"
-#include "integers.h"
-#include "math.h"
-#include "metamethods.h"
-#include "optionals.h"
-#include "tables.h"
-#include "text.h"
-#include "util.h"
-
-// Use inline version of siphash code:
-#include "siphash.h"
-#include "siphash-internals.h"
-
-PUREFUNC static INLINE int64_t get_padded_item_size(const TypeInfo_t *info)
-{
-    int64_t size = info->ArrayInfo.item->size;
-    if (info->ArrayInfo.item->align > 1 && size % info->ArrayInfo.item->align)
-        errx(1, "Item size is not padded!");
-    return size;
-}
-
-// Replace the array's .data pointer with a new pointer to a copy of the
-// data that is compacted and has a stride of exactly `padded_item_size`
-public void Array$compact(Array_t *arr, int64_t padded_item_size)
-{
-    void *copy = NULL;
-    if (arr->length > 0) {
-        copy = arr->atomic ? GC_MALLOC_ATOMIC((size_t)arr->length * (size_t)padded_item_size)
-            : GC_MALLOC((size_t)arr->length * (size_t)padded_item_size);
-        if ((int64_t)arr->stride == padded_item_size) {
-            memcpy(copy, arr->data, (size_t)arr->length * (size_t)padded_item_size);
-        } else {
-            for (int64_t i = 0; i < arr->length; i++)
-                memcpy(copy + i*padded_item_size, arr->data + arr->stride*i, (size_t)padded_item_size);
-        }
-    }
-    *arr = (Array_t){
-        .data=copy,
-        .length=arr->length,
-        .stride=padded_item_size,
-        .atomic=arr->atomic,
-    };
-}
-
-public void Array$insert(Array_t *arr, const void *item, Int_t int_index, int64_t padded_item_size)
-{
-    int64_t index = Int64$from_int(int_index, false);
-    if (index <= 0) index = arr->length + index + 1;
-
-    if (index < 1) index = 1;
-    else if (index > (int64_t)arr->length + 1)
-        fail("Invalid insertion index ", index, " for an array with length ", (int64_t)arr->length);
-
-    if (!arr->data) {
-        arr->free = 4;
-        arr->data = arr->atomic ? GC_MALLOC_ATOMIC((size_t)arr->free * (size_t)padded_item_size)
-            : GC_MALLOC((size_t)arr->free * (size_t)padded_item_size);
-        arr->stride = padded_item_size;
-    } else if (arr->free < 1 || arr->data_refcount != 0 || (int64_t)arr->stride != padded_item_size) {
-        // Resize policy: +50% growth (clamped between 8 and ARRAY_MAX_FREE_ENTRIES)
-        arr->free = MIN(ARRAY_MAX_FREE_ENTRIES, MAX(8, arr->length)/2);
-        void *copy = arr->atomic ? GC_MALLOC_ATOMIC((size_t)(arr->length + arr->free) * (size_t)padded_item_size)
-            : GC_MALLOC((size_t)(arr->length + arr->free) * (size_t)padded_item_size);
-        for (int64_t i = 0; i < index-1; i++)
-            memcpy(copy + i*padded_item_size, arr->data + arr->stride*i, (size_t)padded_item_size);
-        for (int64_t i = index-1; i < (int64_t)arr->length; i++)
-            memcpy(copy + (i+1)*padded_item_size, arr->data + arr->stride*i, (size_t)padded_item_size);
-        arr->data = copy;
-        arr->data_refcount = 0;
-        arr->stride = padded_item_size;
-    } else {
-        if (index != arr->length+1)
-            memmove(
-                arr->data + index*padded_item_size,
-                arr->data + (index-1)*padded_item_size,
-                (size_t)((arr->length - index + 1)*padded_item_size));
-    }
-    assert(arr->free > 0);
-    --arr->free;
-    ++arr->length;
-    memcpy((void*)arr->data + (index-1)*padded_item_size, item, (size_t)padded_item_size);
-}
-
-public void Array$insert_all(Array_t *arr, Array_t to_insert, Int_t int_index, int64_t padded_item_size)
-{
-    int64_t index = Int64$from_int(int_index, false);
-    if (to_insert.length == 0)
-        return;
-
-    if (!arr->data) {
-        *arr = to_insert;
-        ARRAY_INCREF(*arr);
-        return;
-    }
-
-    if (index < 1) index = arr->length + index + 1;
-
-    if (index < 1) index = 1;
-    else if (index > (int64_t)arr->length + 1)
-        fail("Invalid insertion index ", index, " for an array with length ", (int64_t)arr->length);
-
-    if ((int64_t)arr->free >= (int64_t)to_insert.length // Adequate free space
-        && arr->data_refcount == 0 // Not aliased memory
-        && (int64_t)arr->stride == padded_item_size) { // Contiguous array
-        // If we can fit this within the array's preallocated free space, do that:
-        arr->free -= to_insert.length;
-        arr->length += to_insert.length;
-        if (index != arr->length+1)
-            memmove((void*)arr->data + index*padded_item_size,
-                    arr->data + (index-1)*padded_item_size,
-                    (size_t)((arr->length - index + to_insert.length-1)*padded_item_size));
-        for (int64_t i = 0; i < to_insert.length; i++)
-            memcpy((void*)arr->data + (index-1 + i)*padded_item_size,
-                   to_insert.data + i*to_insert.stride, (size_t)padded_item_size);
-    } else {
-        // Otherwise, allocate a new chunk of memory for the array and populate it:
-        int64_t new_len = arr->length + to_insert.length;
-        arr->free = MIN(ARRAY_MAX_FREE_ENTRIES, MAX(8, new_len/4));
-        void *data = arr->atomic ? GC_MALLOC_ATOMIC((size_t)((new_len + arr->free) * padded_item_size))
-            : GC_MALLOC((size_t)((new_len + arr->free) * padded_item_size));
-        void *p = data;
-
-        // Copy first chunk of `arr` if needed:
-        if (index > 1) {
-            if (arr->stride == padded_item_size) {
-                memcpy(p, arr->data, (size_t)((index-1)*padded_item_size));
-                p += (index-1)*padded_item_size;
-            } else {
-                for (int64_t i = 0; i < index-1; i++) {
-                    memcpy(p, arr->data + arr->stride*i, (size_t)padded_item_size);
-                    p += padded_item_size;
-                }
-            }
-        }
-
-        // Copy `to_insert`
-        if (to_insert.stride == padded_item_size) {
-            memcpy(p, to_insert.data, (size_t)(to_insert.length*padded_item_size));
-            p += to_insert.length*padded_item_size;
-        } else {
-            for (int64_t i = 0; i < index-1; i++) {
-                memcpy(p, to_insert.data + to_insert.stride*i, (size_t)padded_item_size);
-                p += padded_item_size;
-            }
-        }
-
-        // Copy last chunk of `arr` if needed:
-        if (index < arr->length + 1) {
-            if (arr->stride == padded_item_size) {
-                memcpy(p, arr->data + padded_item_size*(index-1), (size_t)((arr->length - index + 1)*padded_item_size));
-                p += (arr->length - index + 1)*padded_item_size;
-            } else {
-                for (int64_t i = index-1; i < arr->length-1; i++) {
-                    memcpy(p, arr->data + arr->stride*i, (size_t)padded_item_size);
-                    p += padded_item_size;
-                }
-            }
-        }
-        arr->length = new_len;
-        arr->stride = padded_item_size;
-        arr->data = data;
-        arr->data_refcount = 0;
-    }
-}
-
-public void Array$remove_at(Array_t *arr, Int_t int_index, Int_t int_count, int64_t padded_item_size)
-{
-    int64_t index = Int64$from_int(int_index, false);
-    if (index < 1) index = arr->length + index + 1;
-
-    int64_t count = Int64$from_int(int_count, false);
-    if (index < 1 || index > (int64_t)arr->length || count < 1) return;
-
-    if (count > arr->length - index + 1)
-        count = (arr->length - index) + 1;
-
-    if (index == 1) {
-        arr->data += arr->stride * count;
-    } else if (index + count > arr->length) {
-        arr->free += count;
-    } else if (arr->data_refcount != 0 || (int64_t)arr->stride != padded_item_size) {
-        void *copy = arr->atomic ? GC_MALLOC_ATOMIC((size_t)((arr->length-1) * padded_item_size))
-            : GC_MALLOC((size_t)((arr->length-1) * padded_item_size));
-        for (int64_t src = 1, dest = 1; src <= (int64_t)arr->length; src++) {
-            if (src < index || src >= index + count) {
-                memcpy(copy + (dest - 1)*padded_item_size, arr->data + arr->stride*(src - 1), (size_t)padded_item_size);
-                ++dest;
-            }
-        }
-        arr->data = copy;
-        arr->free = 0;
-        arr->data_refcount = 0;
-    } else {
-        memmove((void*)arr->data + (index-1)*padded_item_size, arr->data + (index-1 + count)*padded_item_size,
-                (size_t)((arr->length - index + count - 1)*padded_item_size));
-        arr->free += count;
-    }
-    arr->length -= count;
-    if (arr->length == 0) arr->data = NULL;
-}
-
-public void Array$remove_item(Array_t *arr, void *item, Int_t max_removals, const TypeInfo_t *type)
-{
-    int64_t padded_item_size = get_padded_item_size(type);
-    const Int_t ZERO = (Int_t){.small=(0<<2)|1};
-    const Int_t ONE = (Int_t){.small=(1<<2)|1};
-    const TypeInfo_t *item_type = type->ArrayInfo.item;
-    for (int64_t i = 0; i < arr->length; ) {
-        if (max_removals.small == ZERO.small) // zero
-            break;
-
-        if (generic_equal(item, arr->data + i*arr->stride, item_type)) {
-            Array$remove_at(arr, I(i+1), ONE, padded_item_size);
-            max_removals = Int$minus(max_removals, ONE);
-        } else {
-            i++;
-        }
-    }
-}
-
-public OptionalInt_t Array$find(Array_t arr, void *item, const TypeInfo_t *type)
-{
-    const TypeInfo_t *item_type = type->ArrayInfo.item;
-    for (int64_t i = 0; i < arr.length; i++) {
-        if (generic_equal(item, arr.data + i*arr.stride, item_type))
-            return I(i+1);
-    }
-    return NONE_INT;
-}
-
-public OptionalInt_t Array$first(Array_t arr, Closure_t predicate)
-{
-    bool (*is_good)(void*, void*) = (void*)predicate.fn;
-    for (int64_t i = 0; i < arr.length; i++) {
-        if (is_good(arr.data + i*arr.stride, predicate.userdata))
-            return I(i+1);
-    }
-    return NONE_INT;
-}
-
-static Closure_t _sort_comparison = {.fn=NULL};
-
-int _compare_closure(const void *a, const void *b)
-{
-    typedef int (*comparison_t)(const void*, const void*, void*);
-    return ((comparison_t)_sort_comparison.fn)(a, b, _sort_comparison.userdata);
-}
-
-public void Array$sort(Array_t *arr, Closure_t comparison, int64_t padded_item_size)
-{
-    if (arr->data_refcount != 0 || (int64_t)arr->stride != padded_item_size)
-        Array$compact(arr, padded_item_size);
-
-    _sort_comparison = comparison;
-    qsort(arr->data, (size_t)arr->length, (size_t)padded_item_size, _compare_closure);
-}
-
-public Array_t Array$sorted(Array_t arr, Closure_t comparison, int64_t padded_item_size)
-{
-    Array$compact(&arr, padded_item_size);
-    _sort_comparison = comparison;
-    qsort(arr.data, (size_t)arr.length, (size_t)padded_item_size, _compare_closure);
-    return arr;
-}
-
-#if defined(__FreeBSD__) || defined(__OpenBSD__) || defined(__NetBSD__) || defined(__APPLE__)
-static ssize_t getrandom(void *buf, size_t buflen, unsigned int flags) {
-    (void)flags;
-    arc4random_buf(buf, buflen);
-    return buflen;
-}
-#elif defined(__linux__)
-// Use getrandom()
-#   include <sys/random.h>
-#else
-    #error "Unsupported platform for secure random number generation"
-#endif
-
-static int64_t _default_random_int64(int64_t min, int64_t max, void *userdata)
-{
-    (void)userdata;
-    if (min > max) fail("Random minimum value (", min, ") is larger than the maximum value (", max, ")");
-    if (min == max) return min;
-    uint64_t range = (uint64_t)max - (uint64_t)min + 1;
-    uint64_t min_r = -range % range;
-    uint64_t r;
-    for (;;) {
-        getrandom(&r, sizeof(r), 0);
-        if (r >= min_r) break;
-    }
-    return (int64_t)((uint64_t)min + (r % range));
-}
-
-public void Array$shuffle(Array_t *arr, OptionalClosure_t random_int64, int64_t padded_item_size)
-{
-    if (arr->data_refcount != 0 || (int64_t)arr->stride != padded_item_size)
-        Array$compact(arr, padded_item_size);
-
-    typedef int64_t (*rng_fn_t)(int64_t, int64_t, void*);
-    rng_fn_t rng_fn = random_int64.fn ? (rng_fn_t)random_int64.fn : _default_random_int64;
-    char tmp[padded_item_size];
-    for (int64_t i = arr->length-1; i > 1; i--) {
-        int64_t j = rng_fn(0, i, random_int64.userdata);
-        if unlikely (j < 0 || j > arr->length-1)
-            fail("The provided random number function returned an invalid value: ", j, " (not between 0 and ", i, ")");
-        memcpy(tmp, arr->data + i*padded_item_size, (size_t)padded_item_size);
-        memcpy((void*)arr->data + i*padded_item_size, arr->data + j*padded_item_size, (size_t)padded_item_size);
-        memcpy((void*)arr->data + j*padded_item_size, tmp, (size_t)padded_item_size);
-    }
-}
-
-public Array_t Array$shuffled(Array_t arr, Closure_t random_int64, int64_t padded_item_size)
-{
-    Array$compact(&arr, padded_item_size);
-    Array$shuffle(&arr, random_int64, padded_item_size);
-    return arr;
-}
-
-public void *Array$random(Array_t arr, OptionalClosure_t random_int64)
-{
-    if (arr.length == 0)
-        return NULL; // fail("Cannot get a random item from an empty array!");
-
-    typedef int64_t (*rng_fn_t)(int64_t, int64_t, void*);
-    rng_fn_t rng_fn = random_int64.fn ? (rng_fn_t)random_int64.fn : _default_random_int64;
-    int64_t index = rng_fn(0, arr.length-1, random_int64.userdata);
-    if unlikely (index < 0 || index > arr.length-1)
-        fail("The provided random number function returned an invalid value: ", index, " (not between 0 and ", (int64_t)arr.length, ")");
-    return arr.data + arr.stride*index;
-}
-
-public Table_t Array$counts(Array_t arr, const TypeInfo_t *type)
-{
-    Table_t counts = {};
-    const TypeInfo_t count_type = *Table$info(type->ArrayInfo.item, &Int$info);
-    for (int64_t i = 0; i < arr.length; i++) {
-        void *key = arr.data + i*arr.stride;
-        int64_t *count = Table$get(counts, key, &count_type);
-        int64_t val = count ? *count + 1 : 1;
-        Table$set(&counts, key, &val, &count_type);
-    }
-    return counts;
-}
-
-static double _default_random_num(void *userdata)
-{
-    (void)userdata;
-    union {
-        Num_t num;
-        uint64_t bits;
-    } r = {.bits=0}, one = {.num=1.0};
-    getrandom((uint8_t*)&r, sizeof(r), 0);
-
-    // Set r.num to 1.<random-bits>
-    r.bits &= ~(0xFFFULL << 52);
-    r.bits |= (one.bits & (0xFFFULL << 52));
-    return r.num - 1.0;
-}
-
-public Array_t Array$sample(Array_t arr, Int_t int_n, Array_t weights, OptionalClosure_t random_num, int64_t padded_item_size)
-{
-    int64_t n = Int64$from_int(int_n, false);
-    if (n < 0)
-        fail("Cannot select a negative number of values");
-
-    if (n == 0)
-        return (Array_t){};
-
-    if (arr.length == 0)
-        fail("There are no elements in this array!");
-
-    if (weights.length != arr.length)
-        fail("Array has ", (int64_t)arr.length, " elements, but there are ", (int64_t)weights.length, " weights given");
-
-    double total = 0.0;
-    for (int64_t i = 0; i < weights.length && i < arr.length; i++) {
-        double weight = *(double*)(weights.data + weights.stride*i);
-        if (isinf(weight))
-            fail("Infinite weight!");
-        else if (isnan(weight))
-            fail("NaN weight!");
-        else if (weight < 0.0)
-            fail("Negative weight!");
-        else
-            total += weight;
-    }
-
-    if (isinf(total))
-        fail("Sample weights have overflowed to infinity");
-
-    if (total == 0.0)
-        fail("None of the given weights are nonzero");
-
-    double inverse_average = (double)arr.length / total;
-
-    struct {
-        int64_t alias;
-        double odds;
-    } aliases[arr.length];
-
-    for (int64_t i = 0; i < arr.length; i++) {
-        double weight = i >= weights.length ? 0.0 : *(double*)(weights.data + weights.stride*i);
-        aliases[i].odds = weight * inverse_average;
-        aliases[i].alias = -1;
-    }
-
-    int64_t small = 0;
-    for (int64_t big = 0; big < arr.length; big++) {
-        while (aliases[big].odds >= 1.0) {
-            while (small < arr.length && (aliases[small].odds >= 1.0 || aliases[small].alias != -1))
-                ++small;
-
-            if (small >= arr.length) {
-                aliases[big].odds = 1.0;
-                aliases[big].alias = big;
-                break;
-            }
-
-            aliases[small].alias = big;
-            aliases[big].odds = (aliases[small].odds + aliases[big].odds) - 1.0;
-        }
-        if (big < small) small = big;
-    }
-
-    for (int64_t i = small; i < arr.length; i++)
-        if (aliases[i].alias == -1)
-            aliases[i].alias = i;
-
-    typedef double (*rng_fn_t)(void*);
-    rng_fn_t rng_fn = random_num.fn ? (rng_fn_t)random_num.fn : _default_random_num;
-
-    Array_t selected = {
-        .data=arr.atomic ? GC_MALLOC_ATOMIC((size_t)(n * padded_item_size)) : GC_MALLOC((size_t)(n * padded_item_size)),
-        .length=n,
-        .stride=padded_item_size, .atomic=arr.atomic};
-    for (int64_t i = 0; i < n; i++) {
-        double r = rng_fn(random_num.userdata);
-        if unlikely (r < 0.0 || r >= 1.0)
-            fail("The random number function returned a value not between 0.0 (inclusive) and 1.0 (exclusive): ", r);
-        r *= (double)arr.length;
-        int64_t index = (int64_t)r;
-        assert(index >= 0 && index < arr.length);
-        if ((r - (double)index) > aliases[index].odds)
-            index = aliases[index].alias;
-        memcpy(selected.data + i*selected.stride, arr.data + index*arr.stride, (size_t)padded_item_size);
-    }
-    return selected;
-}
-
-public Array_t Array$from(Array_t array, Int_t first)
-{
-    return Array$slice(array, first, I_small(-1));
-}
-
-public Array_t Array$to(Array_t array, Int_t last)
-{
-    return Array$slice(array, I_small(1), last);
-}
-
-public Array_t Array$by(Array_t array, Int_t int_stride, int64_t padded_item_size)
-{
-    int64_t stride = Int64$from_int(int_stride, false);
-    // In the unlikely event that the stride value would be too large to fit in
-    // a 15-bit integer, fall back to creating a copy of the array:
-    if (unlikely(array.stride*stride < ARRAY_MIN_STRIDE || array.stride*stride > ARRAY_MAX_STRIDE)) {
-        void *copy = NULL;
-        int64_t len = (stride < 0 ? array.length / -stride : array.length / stride) + ((array.length % stride) != 0);
-        if (len > 0) {
-            copy = array.atomic ? GC_MALLOC_ATOMIC((size_t)(len * padded_item_size)) : GC_MALLOC((size_t)(len * padded_item_size));
-            void *start = (stride < 0 ? array.data + (array.stride * (array.length - 1)) : array.data);
-            for (int64_t i = 0; i < len; i++)
-                memcpy(copy + i*padded_item_size, start + array.stride*stride*i, (size_t)padded_item_size);
-        }
-        return (Array_t){
-            .data=copy,
-            .length=len,
-            .stride=padded_item_size,
-            .atomic=array.atomic,
-        };
-    }
-
-    if (stride == 0)
-        return (Array_t){.atomic=array.atomic};
-
-    return (Array_t){
-        .atomic=array.atomic,
-        .data=(stride < 0 ? array.data + (array.stride * (array.length - 1)) : array.data),
-        .length=(stride < 0 ? array.length / -stride : array.length / stride) + ((array.length % stride) != 0),
-        .stride=array.stride * stride,
-        .data_refcount=array.data_refcount,
-    };
-}
-
-public Array_t Array$slice(Array_t array, Int_t int_first, Int_t int_last)
-
-{
-    int64_t first = Int64$from_int(int_first, false);
-    if (first < 0)
-        first = array.length + first + 1;
-
-    int64_t last = Int64$from_int(int_last, false);
-    if (last < 0)
-        last = array.length + last + 1;
-
-    if (last > array.length)
-        last = array.length;
-
-    if (first < 1 || first > array.length || last == 0)
-        return (Array_t){.atomic=array.atomic};
-
-    return (Array_t){
-        .atomic=array.atomic,
-        .data=array.data + array.stride*(first-1),
-        .length=last - first + 1,
-        .stride=array.stride,
-        .data_refcount=array.data_refcount,
-    };
-}
-
-public Array_t Array$reversed(Array_t array, int64_t padded_item_size)
-{
-    // Just in case negating the stride gives a value that doesn't fit into a
-    // 15-bit integer, fall back to Array$by()'s more general method of copying
-    // the array. This should only happen if array.stride is MIN_STRIDE to
-    // begin with (very unlikely).
-    if (unlikely(-array.stride < ARRAY_MIN_STRIDE || -array.stride > ARRAY_MAX_STRIDE))
-        return Array$by(array, I(-1), padded_item_size);
-
-    Array_t reversed = array;
-    reversed.stride = -array.stride;
-    reversed.data = array.data + (array.length-1)*array.stride;
-    return reversed;
-}
-
-public Array_t Array$concat(Array_t x, Array_t y, int64_t padded_item_size)
-{
-    void *data = x.atomic ? GC_MALLOC_ATOMIC((size_t)(padded_item_size*(x.length + y.length)))
-        : GC_MALLOC((size_t)(padded_item_size*(x.length + y.length)));
-    if (x.stride == padded_item_size) {
-        memcpy(data, x.data, (size_t)(padded_item_size*x.length));
-    } else {
-        for (int64_t i = 0; i < x.length; i++)
-            memcpy(data + i*padded_item_size, x.data + i*padded_item_size, (size_t)padded_item_size);
-    }
-
-    void *dest = data + padded_item_size*x.length;
-    if (y.stride == padded_item_size) {
-        memcpy(dest, y.data, (size_t)(padded_item_size*y.length));
-    } else {
-        for (int64_t i = 0; i < y.length; i++)
-            memcpy(dest + i*padded_item_size, y.data + i*y.stride, (size_t)padded_item_size);
-    }
-
-    return (Array_t){
-        .data=data,
-        .length=x.length + y.length,
-        .stride=padded_item_size,
-        .atomic=x.atomic,
-    };
-}
-
-public bool Array$has(Array_t array, void *item, const TypeInfo_t *type)
-{
-    const TypeInfo_t *item_type = type->ArrayInfo.item;
-    for (int64_t i = 0; i < array.length; i++) {
-        if (generic_equal(array.data + i*array.stride, item, item_type))
-            return true;
-    }
-    return false;
-}
-
-public void Array$clear(Array_t *array)
-{
-    *array = (Array_t){.data=0, .length=0};
-}
-
-public int32_t Array$compare(const void *vx, const void *vy, const TypeInfo_t *type)
-{
-    const Array_t *x = (Array_t*)vx, *y = (Array_t*)vy;
-    // Early out for arrays with the same data, e.g. two copies of the same array:
-    if (x->data == y->data && x->stride == y->stride)
-        return (x->length > y->length) - (x->length < y->length);
-
-    const TypeInfo_t *item = type->ArrayInfo.item;
-    if (item->tag == PointerInfo || !item->metamethods.compare) { // data comparison
-        int64_t item_padded_size = type->ArrayInfo.item->size;
-        if (type->ArrayInfo.item->align > 1 && item_padded_size % type->ArrayInfo.item->align)
-            errx(1, "Item size is not padded!");
-
-        if ((int64_t)x->stride == item_padded_size && (int64_t)y->stride == item_padded_size && item->size == item_padded_size) {
-            int32_t cmp = (int32_t)memcmp(x->data, y->data, (size_t)(MIN(x->length, y->length)*item_padded_size));
-            if (cmp != 0) return cmp;
-        } else {
-            for (int32_t i = 0, len = MIN(x->length, y->length); i < len; i++) {
-                int32_t cmp = (int32_t)memcmp(x->data+ x->stride*i, y->data + y->stride*i, (size_t)(item->size));
-                if (cmp != 0) return cmp;
-            }
-        }
-    } else {
-        for (int32_t i = 0, len = MIN(x->length, y->length); i < len; i++) {
-            int32_t cmp = generic_compare(x->data + x->stride*i, y->data + y->stride*i, item);
-            if (cmp != 0) return cmp;
-        }
-    }
-    return (x->length > y->length) - (x->length < y->length);
-}
-
-public bool Array$equal(const void *x, const void *y, const TypeInfo_t *type)
-{
-    return x == y || (((Array_t*)x)->length == ((Array_t*)y)->length && Array$compare(x, y, type) == 0);
-}
-
-public Text_t Array$as_text(const void *obj, bool colorize, const TypeInfo_t *type)
-{
-    Array_t *arr = (Array_t*)obj;
-    if (!arr)
-        return Text$concat(Text("["), generic_as_text(NULL, false, type->ArrayInfo.item), Text("]"));
-
-    const TypeInfo_t *item_type = type->ArrayInfo.item;
-    Text_t text = Text("[");
-    for (int64_t i = 0; i < arr->length; i++) {
-        if (i > 0)
-            text = Text$concat(text, Text(", "));
-        Text_t item_text = generic_as_text(arr->data + i*arr->stride, colorize, item_type);
-        text = Text$concat(text, item_text);
-    }
-    text = Text$concat(text, Text("]"));
-    return text;
-}
-
-public uint64_t Array$hash(const void *obj, const TypeInfo_t *type)
-{
-    const Array_t *arr = (Array_t*)obj;
-    const TypeInfo_t *item = type->ArrayInfo.item;
-    siphash sh;
-    siphashinit(&sh, sizeof(uint64_t[arr->length]));
-    if (item->tag == PointerInfo || (!item->metamethods.hash && item->size == sizeof(void*))) { // Raw data hash
-        for (int64_t i = 0; i < arr->length; i++)
-            siphashadd64bits(&sh, (uint64_t)(arr->data + i*arr->stride));
-    } else {
-        for (int64_t i = 0; i < arr->length; i++) {
-            uint64_t item_hash = generic_hash(arr->data + i*arr->stride, item);
-            siphashadd64bits(&sh, item_hash);
-        }
-    }
-    return siphashfinish_last_part(&sh, 0);
-}
-
-static void siftdown(Array_t *heap, int64_t startpos, int64_t pos, Closure_t comparison, int64_t padded_item_size)
-{
-    assert(pos > 0 && pos < heap->length);
-    char newitem[padded_item_size];
-    memcpy(newitem, heap->data + heap->stride*pos, (size_t)(padded_item_size));
-    while (pos > startpos) {
-        int64_t parentpos = (pos - 1) >> 1;
-        typedef int32_t (*cmp_fn_t)(void*, void*, void*);
-        int32_t cmp = ((cmp_fn_t)comparison.fn)(newitem, heap->data + heap->stride*parentpos, comparison.userdata);
-        if (cmp >= 0)
-            break;
-
-        memcpy(heap->data + heap->stride*pos, heap->data + heap->stride*parentpos, (size_t)(padded_item_size));
-        pos = parentpos;
-    }
-    memcpy(heap->data + heap->stride*pos, newitem, (size_t)(padded_item_size));
-}
-
-static void siftup(Array_t *heap, int64_t pos, Closure_t comparison, int64_t padded_item_size)
-{
-    int64_t endpos = heap->length;
-    int64_t startpos = pos;
-    assert(pos < endpos);
-
-    char old_top[padded_item_size];
-    memcpy(old_top, heap->data + heap->stride*pos, (size_t)(padded_item_size));
-    // Bubble up the smallest leaf node
-    int64_t limit = endpos >> 1;
-    while (pos < limit) {
-        int64_t childpos = 2*pos + 1; // Smaller of the two child nodes
-        if (childpos + 1 < endpos) {
-            typedef int32_t (*cmp_fn_t)(void*, void*, void*);
-            int32_t cmp = ((cmp_fn_t)comparison.fn)(
-                heap->data + heap->stride*childpos,
-                heap->data + heap->stride*(childpos + 1),
-                comparison.userdata);
-            childpos += (cmp >= 0);
-        }
-
-        // Move the child node up:
-        memcpy(heap->data + heap->stride*pos, heap->data + heap->stride*childpos, (size_t)(padded_item_size));
-        pos = childpos;
-    }
-    memcpy(heap->data + heap->stride*pos, old_top, (size_t)(padded_item_size));
-    // Shift the node's parents down:
-    siftdown(heap, startpos, pos, comparison, padded_item_size);
-}
-
-public void Array$heap_push(Array_t *heap, const void *item, Closure_t comparison, int64_t padded_item_size)
-{
-    Array$insert(heap, item, I(0), padded_item_size);
-
-    if (heap->length > 1) {
-        if (heap->data_refcount != 0)
-            Array$compact(heap, padded_item_size);
-        siftdown(heap, 0, heap->length-1, comparison, padded_item_size);
-    }
-}
-
-public void Array$heap_pop(Array_t *heap, Closure_t comparison, int64_t padded_item_size)
-{
-    if (heap->length == 0)
-        fail("Attempt to pop from an empty array");
-
-    if (heap->length == 1) {
-        *heap = (Array_t){};
-    } else if (heap->length == 2) {
-        heap->data += heap->stride;
-        --heap->length;
-    } else {
-        if (heap->data_refcount != 0)
-            Array$compact(heap, padded_item_size);
-        memcpy(heap->data, heap->data + heap->stride*(heap->length-1), (size_t)(padded_item_size));
-        --heap->length;
-        siftup(heap, 0, comparison, padded_item_size);
-    }
-}
-
-public void Array$heapify(Array_t *heap, Closure_t comparison, int64_t padded_item_size)
-{
-    if (heap->data_refcount != 0)
-        Array$compact(heap, padded_item_size);
-
-    // It's necessary to bump the refcount because the user's comparison
-    // function could do stuff that modifies the heap's data.
-    ARRAY_INCREF(*heap);
-    int64_t i, n = heap->length;
-    for (i = (n >> 1) - 1 ; i >= 0 ; i--)
-        siftup(heap, i, comparison, padded_item_size);
-    ARRAY_DECREF(*heap);
-}
-
-public Int_t Array$binary_search(Array_t array, void *target, Closure_t comparison)
-{
-    typedef int32_t (*cmp_fn_t)(void*, void*, void*);
-    int64_t lo = 0, hi = array.length-1;
-    while (lo <= hi) {
-        int64_t mid = (lo + hi) / 2;
-        int32_t cmp = ((cmp_fn_t)comparison.fn)(
-            array.data + array.stride*mid, target, comparison.userdata);
-        if (cmp == 0)
-            return I(mid+1);
-        else if (cmp < 0)
-            lo = mid + 1;
-        else if (cmp > 0)
-            hi = mid - 1;
-    }
-    return I(lo+1); // Return the index where the target would be inserted
-}
-
-public PUREFUNC bool Array$is_none(const void *obj, const TypeInfo_t*)
-{
-    return ((Array_t*)obj)->length < 0;
-}
-
-public void Array$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type)
-{
-    Array_t arr = *(Array_t*)obj;
-    int64_t len = arr.length;
-    Int64$serialize(&len, out, pointers, &Int64$info);
-    auto item_serialize = type->ArrayInfo.item->metamethods.serialize;
-    if (item_serialize) {
-        for (int64_t i = 0; i < len; i++)
-            item_serialize(arr.data + i*arr.stride, out, pointers, type->ArrayInfo.item);
-    } else if (arr.stride == type->ArrayInfo.item->size) {
-        fwrite(arr.data, (size_t)type->ArrayInfo.item->size, (size_t)len, out);
-    } else {
-        for (int64_t i = 0; i < len; i++)
-            fwrite(arr.data + i*arr.stride, (size_t)type->ArrayInfo.item->size, 1, out);
-    }
-}
-
-public void Array$deserialize(FILE *in, void *obj, Array_t *pointers, const TypeInfo_t *type)
-{
-    int64_t len = -1;
-    Int64$deserialize(in, &len, pointers, &Int64$info);
-    int64_t padded_size = type->ArrayInfo.item->size;
-    if (type->ArrayInfo.item->align > 0 && padded_size % type->ArrayInfo.item->align > 0)
-        padded_size += type->ArrayInfo.item->align - (padded_size % type->ArrayInfo.item->align);
-    Array_t arr = {
-        .length=len,
-        .data=GC_MALLOC((size_t)(len*padded_size)),
-        .stride=padded_size,
-    };
-    auto item_deserialize = type->ArrayInfo.item->metamethods.deserialize;
-    if (item_deserialize) {
-        for (int64_t i = 0; i < len; i++)
-            item_deserialize(in, arr.data + i*arr.stride, pointers, type->ArrayInfo.item);
-    } else if (arr.stride == type->ArrayInfo.item->size) {
-        fread(arr.data, (size_t)type->ArrayInfo.item->size, (size_t)len, in);
-    } else {
-        for (int64_t i = 0; i < len; i++)
-            fread(arr.data + i*arr.stride, (size_t)type->ArrayInfo.item->size, 1, in);
-    }
-    *(Array_t*)obj = arr;
-}
-
-// vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0
diff --git a/src/stdlib/arrays.h b/src/stdlib/arrays.h
deleted file mode 100644
index 9f5f3d00..00000000
--- a/src/stdlib/arrays.h
+++ /dev/null
@@ -1,137 +0,0 @@
-#pragma once
-
-// Functions that operate on arrays
-
-#include <stdbool.h>
-
-#include "datatypes.h"
-#include "integers.h"
-#include "types.h"
-#include "util.h"
-
-// Convert negative indices to back-indexed without branching: index0 = index + (index < 0)*(len+1)) - 1
-#define Array_get(item_type, arr_expr, index_expr, start, end) *({ \
-    const Array_t arr = arr_expr; int64_t index = index_expr; \
-    int64_t off = index + (index < 0) * (arr.length + 1) - 1; \
-    if (unlikely(off < 0 || off >= arr.length)) \
-        fail_source(__SOURCE_FILE__, start, end, "Invalid array index: ", index, " (array has length ", (int64_t)arr.length, ")\n"); \
-    (item_type*)(arr.data + arr.stride * off);})
-#define Array_get_unchecked(type, x, i) *({ const Array_t arr = x; int64_t index = i; \
-                                          int64_t off = index + (index < 0) * (arr.length + 1) - 1; \
-                                          (type*)(arr.data + arr.stride * off);})
-#define Array_lvalue(item_type, arr_expr, index_expr, start, end) *({ \
-    Array_t *arr = arr_expr; int64_t index = index_expr; \
-    int64_t off = index + (index < 0) * (arr->length + 1) - 1; \
-    if (unlikely(off < 0 || off >= arr->length)) \
-        fail_source(__SOURCE_FILE__, start, end, "Invalid array index: ", index, " (array has length ", (int64_t)arr->length, ")\n"); \
-    if (arr->data_refcount > 0) \
-        Array$compact(arr, sizeof(item_type)); \
-    (item_type*)(arr->data + arr->stride * off); })
-#define Array_lvalue_unchecked(item_type, arr_expr, index_expr) *({ \
-    Array_t *arr = arr_expr; int64_t index = index_expr; \
-    int64_t off = index + (index < 0) * (arr->length + 1) - 1; \
-    if (arr->data_refcount > 0) \
-        Array$compact(arr, sizeof(item_type)); \
-    (item_type*)(arr->data + arr->stride * off); })
-#define Array_set(item_type, arr, index, value, start, end) \
-    Array_lvalue(item_type, arr_expr, index, start, end) = value
-#define is_atomic(x) _Generic(x, bool: true, int8_t: true, int16_t: true, int32_t: true, int64_t: true, float: true, double: true, default: false)
-#define TypedArray(t, ...) ({ t items[] = {__VA_ARGS__}; \
-                         (Array_t){.length=sizeof(items)/sizeof(items[0]), \
-                         .stride=(int64_t)&items[1] - (int64_t)&items[0], \
-                         .data=memcpy(GC_MALLOC(sizeof(items)), items, sizeof(items)), \
-                         .atomic=0, \
-                         .data_refcount=0}; })
-#define TypedArrayN(t, N, ...) ({ t items[N] = {__VA_ARGS__}; \
-                         (Array_t){.length=N, \
-                         .stride=(int64_t)&items[1] - (int64_t)&items[0], \
-                         .data=memcpy(GC_MALLOC(sizeof(items)), items, sizeof(items)), \
-                         .atomic=0, \
-                         .data_refcount=0}; })
-#define Array(x, ...) ({ __typeof(x) items[] = {x, __VA_ARGS__}; \
-                         (Array_t){.length=sizeof(items)/sizeof(items[0]), \
-                         .stride=(int64_t)&items[1] - (int64_t)&items[0], \
-                         .data=memcpy(is_atomic(x) ? GC_MALLOC_ATOMIC(sizeof(items)) : GC_MALLOC(sizeof(items)), items, sizeof(items)), \
-                         .atomic=is_atomic(x), \
-                         .data_refcount=0}; })
-// Array refcounts use a saturating add, where once it's at the max value, it stays there.
-#define ARRAY_INCREF(arr) (arr).data_refcount += ((arr).data_refcount < ARRAY_MAX_DATA_REFCOUNT)
-#define ARRAY_DECREF(arr) (arr).data_refcount -= ((arr).data_refcount < ARRAY_MAX_DATA_REFCOUNT)
-#define ARRAY_COPY(arr) ({ ARRAY_INCREF(arr); arr; })
-
-#define Array$insert_value(arr, item_expr, index, padded_item_size) Array$insert(arr, (__typeof(item_expr)[1]){item_expr}, index, padded_item_size)
-void Array$insert(Array_t *arr, const void *item, Int_t index, int64_t padded_item_size);
-void Array$insert_all(Array_t *arr, Array_t to_insert, Int_t index, int64_t padded_item_size);
-void Array$remove_at(Array_t *arr, Int_t index, Int_t count, int64_t padded_item_size);
-void Array$remove_item(Array_t *arr, void *item, Int_t max_removals, const TypeInfo_t *type);
-#define Array$remove_item_value(arr, item_expr, max, type) Array$remove_item(arr, (__typeof(item_expr)[1]){item_expr}, max, type)
-
-#define Array$pop(arr_expr, index_expr, item_type, nonnone_var, nonnone_expr, none_expr) ({ \
-    Array_t *arr = arr_expr; \
-    Int_t index = index_expr; \
-    int64_t index64 = Int64$from_int(index, false); \
-    int64_t off = index64 + (index64 < 0) * (arr->length + 1) - 1; \
-    (off >= 0 && off < arr->length) ? ({ \
-        item_type nonnone_var = *(item_type*)(arr->data + off*arr->stride); \
-        Array$remove_at(arr, index, I_small(1), sizeof(item_type)); \
-        nonnone_expr; \
-    }) : none_expr; })
-
-OptionalInt_t Array$find(Array_t arr, void *item, const TypeInfo_t *type);
-#define Array$find_value(arr, item_expr, type) ({ __typeof(item_expr) item = item_expr; Array$find(arr, &item, type); })
-OptionalInt_t Array$first(Array_t arr, Closure_t predicate);
-void Array$sort(Array_t *arr, Closure_t comparison, int64_t padded_item_size);
-Array_t Array$sorted(Array_t arr, Closure_t comparison, int64_t padded_item_size);
-void Array$shuffle(Array_t *arr, OptionalClosure_t random_int64, int64_t padded_item_size);
-Array_t Array$shuffled(Array_t arr, OptionalClosure_t random_int64, int64_t padded_item_size);
-void *Array$random(Array_t arr, OptionalClosure_t random_int64);
-#define Array$random_value(arr, random_int64, t) ({ Array_t _arr = arr; if (_arr.length == 0) fail("Cannot get a random value from an empty array!"); *(t*)Array$random(_arr, random_int64); })
-Array_t Array$sample(Array_t arr, Int_t n, Array_t weights, Closure_t random_num, int64_t padded_item_size);
-Table_t Array$counts(Array_t arr, const TypeInfo_t *type);
-void Array$clear(Array_t *array);
-void Array$compact(Array_t *arr, int64_t padded_item_size);
-PUREFUNC bool Array$has(Array_t array, void *item, const TypeInfo_t *type);
-#define Array$has_value(arr, item_expr, type) ({ __typeof(item_expr) item = item_expr; Array$has(arr, &item, type); })
-PUREFUNC Array_t Array$from(Array_t array, Int_t first);
-PUREFUNC Array_t Array$to(Array_t array, Int_t last);
-PUREFUNC Array_t Array$by(Array_t array, Int_t stride, int64_t padded_item_size);
-PUREFUNC Array_t Array$slice(Array_t array, Int_t int_first, Int_t int_last);
-PUREFUNC Array_t Array$reversed(Array_t array, int64_t padded_item_size);
-Array_t Array$concat(Array_t x, Array_t y, int64_t padded_item_size);
-PUREFUNC uint64_t Array$hash(const void *arr, const TypeInfo_t *type);
-PUREFUNC int32_t Array$compare(const void *x, const void *y, const TypeInfo_t *type);
-PUREFUNC bool Array$equal(const void *x, const void *y, const TypeInfo_t *type);
-PUREFUNC bool Array$is_none(const void *obj, const TypeInfo_t*);
-Text_t Array$as_text(const void *arr, bool colorize, const TypeInfo_t *type);
-void Array$heapify(Array_t *heap, Closure_t comparison, int64_t padded_item_size);
-void Array$heap_push(Array_t *heap, const void *item, Closure_t comparison, int64_t padded_item_size);
-#define Array$heap_push_value(heap, _value, comparison, padded_item_size) ({ __typeof(_value) value = _value; Array$heap_push(heap, &value, comparison, padded_item_size); })
-void Array$heap_pop(Array_t *heap, Closure_t comparison, int64_t padded_item_size);
-#define Array$heap_pop_value(heap, comparison, type, nonnone_var, nonnone_expr, none_expr) \
-    ({ Array_t *_heap = heap; \
-     (_heap->length > 0) ? ({ \
-         type nonnone_var = *(type*)_heap->data; \
-         Array$heap_pop(_heap, comparison, sizeof(type)); \
-         nonnone_expr; \
-     }) : none_expr; })
-Int_t Array$binary_search(Array_t array, void *target, Closure_t comparison);
-#define Array$binary_search_value(array, target, comparison) \
-    ({ __typeof(target) _target = target; Array$binary_search(array, &_target, comparison); })
-void Array$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type);
-void Array$deserialize(FILE *in, void *obj, Array_t *pointers, const TypeInfo_t *type);
-
-#define Array$metamethods { \
-    .as_text=Array$as_text, \
-    .compare=Array$compare, \
-    .equal=Array$equal, \
-    .hash=Array$hash, \
-    .is_none=Array$is_none, \
-    .serialize=Array$serialize, \
-    .deserialize=Array$deserialize, \
-}
-
-#define Array$info(item_info) &((TypeInfo_t){.size=sizeof(Array_t), .align=__alignof__(Array_t), \
-                                .tag=ArrayInfo, .ArrayInfo.item=item_info, \
-                                .metamethods=Array$metamethods})
-
-// vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0
diff --git a/src/stdlib/c_strings.c b/src/stdlib/c_strings.c
index 9d0f2819..dc777a7c 100644
--- a/src/stdlib/c_strings.c
+++ b/src/stdlib/c_strings.c
@@ -59,7 +59,7 @@ static void CString$serialize(const void *obj, FILE *out, Table_t *pointers, con
     fwrite(str, sizeof(char), (size_t)len, out);
 }
 
-static void CString$deserialize(FILE *in, void *out, Array_t *pointers, const TypeInfo_t *)
+static void CString$deserialize(FILE *in, void *out, List_t *pointers, const TypeInfo_t *)
 {
     int64_t len = -1;
     Int64$deserialize(in, &len, pointers, &Int64$info);
diff --git a/src/stdlib/datatypes.h b/src/stdlib/datatypes.h
index 6f3b7676..950c9457 100644
--- a/src/stdlib/datatypes.h
+++ b/src/stdlib/datatypes.h
@@ -1,22 +1,22 @@
 #pragma once
 
-// Common datastructures (arrays, tables, closures)
+// Common datastructures (lists, tables, closures)
 
 #include <gmp.h>
 #include <stdbool.h>
 #include <stdint.h>
 #include <time.h>
 
-#define ARRAY_LENGTH_BITS 42
-#define ARRAY_FREE_BITS 6
-#define ARRAY_REFCOUNT_BITS 3
-#define ARRAY_STRIDE_BITS 12
+#define LIST_LENGTH_BITS 42
+#define LIST_FREE_BITS 6
+#define LIST_REFCOUNT_BITS 3
+#define LIST_STRIDE_BITS 12
 
 #define MAX_FOR_N_BITS(N) ((1<<(N))-1)
-#define ARRAY_MAX_STRIDE MAX_FOR_N_BITS(ARRAY_STRIDE_BITS-1)
-#define ARRAY_MIN_STRIDE (~MAX_FOR_N_BITS(ARRAY_STRIDE_BITS-1))
-#define ARRAY_MAX_DATA_REFCOUNT MAX_FOR_N_BITS(ARRAY_REFCOUNT_BITS)
-#define ARRAY_MAX_FREE_ENTRIES MAX_FOR_N_BITS(ARRAY_FREE_BITS)
+#define LIST_MAX_STRIDE MAX_FOR_N_BITS(LIST_STRIDE_BITS-1)
+#define LIST_MIN_STRIDE (~MAX_FOR_N_BITS(LIST_STRIDE_BITS-1))
+#define LIST_MAX_DATA_REFCOUNT MAX_FOR_N_BITS(LIST_REFCOUNT_BITS)
+#define LIST_MAX_FREE_ENTRIES MAX_FOR_N_BITS(LIST_FREE_BITS)
 
 #define Num_t double
 #define Num32_t float
@@ -37,16 +37,16 @@ typedef union {
 
 typedef struct {
     void *data;
-    // All of the following fields add up to 64 bits, which means that array
+    // All of the following fields add up to 64 bits, which means that list
     // structs can be passed in two 64-bit registers. C will handle doing the
     // bit arithmetic to extract the necessary values, which is cheaper than
     // spilling onto the stack and needing to retrieve data from the stack.
-    int64_t length:ARRAY_LENGTH_BITS;
-    uint8_t free:ARRAY_FREE_BITS;
+    int64_t length:LIST_LENGTH_BITS;
+    uint8_t free:LIST_FREE_BITS;
     bool atomic:1;
-    uint8_t data_refcount:ARRAY_REFCOUNT_BITS;
-    int16_t stride:ARRAY_STRIDE_BITS;
-} Array_t;
+    uint8_t data_refcount:LIST_REFCOUNT_BITS;
+    int16_t stride:LIST_STRIDE_BITS;
+} List_t;
 
 typedef struct {
     uint32_t occupied:1, index:31;
@@ -63,7 +63,7 @@ typedef struct {
 } bucket_info_t;
 
 typedef struct table_s {
-    Array_t entries;
+    List_t entries;
     uint64_t hash;
     bucket_info_t *bucket_info;
     struct table_s *fallback;
@@ -101,12 +101,12 @@ typedef struct {
 
 typedef struct {
     PathType_t type;
-    Array_t components;
+    List_t components;
 } Path_t;
 #define OptionalPath_t Path_t
 
 #define OptionalBool_t uint8_t
-#define OptionalArray_t Array_t
+#define OptionalList_t List_t
 #define OptionalTable_t Table_t
 #define OptionalText_t Text_t
 #define OptionalClosure_t Closure_t
diff --git a/src/stdlib/enums.c b/src/stdlib/enums.c
index b66a1711..bcf47d8e 100644
--- a/src/stdlib/enums.c
+++ b/src/stdlib/enums.c
@@ -3,7 +3,7 @@
 #include <stdint.h>
 #include <string.h>
 
-#include "arrays.h"
+#include "lists.h"
 #include "bools.h"
 #include "functiontype.h"
 #include "integers.h"
@@ -102,7 +102,7 @@ public void Enum$serialize(const void *obj, FILE *out, Table_t *pointers, const
     }
 }
 
-public void Enum$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type)
+public void Enum$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type)
 {
     int32_t tag = 0;
     Int32$deserialize(in, &tag, pointers, &Int32$info);
diff --git a/src/stdlib/enums.h b/src/stdlib/enums.h
index b5427711..8345c527 100644
--- a/src/stdlib/enums.h
+++ b/src/stdlib/enums.h
@@ -13,7 +13,7 @@ PUREFUNC bool Enum$equal(const void *x, const void *y, const TypeInfo_t *type);
 PUREFUNC Text_t Enum$as_text(const void *obj, bool colorize, const TypeInfo_t *type);
 PUREFUNC bool Enum$is_none(const void *obj, const TypeInfo_t *type);
 void Enum$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type);
-void Enum$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type);
+void Enum$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type);
 
 #define Enum$metamethods { \
     .as_text=Enum$as_text, \
diff --git a/src/stdlib/integers.c b/src/stdlib/integers.c
index 8086239d..7943caee 100644
--- a/src/stdlib/integers.c
+++ b/src/stdlib/integers.c
@@ -9,7 +9,7 @@
 #include <stdio.h>
 #include <stdlib.h>
 
-#include "arrays.h"
+#include "lists.h"
 #include "datatypes.h"
 #include "integers.h"
 #include "optionals.h"
@@ -480,7 +480,7 @@ static void Int$serialize(const void *obj, FILE *out, Table_t *pointers, const T
     }
 }
 
-static void Int$deserialize(FILE *in, void *obj, Array_t *pointers, const TypeInfo_t*)
+static void Int$deserialize(FILE *in, void *obj, List_t *pointers, const TypeInfo_t*)
 {
     if (fgetc(in) == 0) {
         int64_t i = 0;
@@ -519,7 +519,7 @@ public void Int64$serialize(const void *obj, FILE *out, Table_t*, const TypeInfo
     fputc((uint8_t)z, out);
 }
 
-public void Int64$deserialize(FILE *in, void *outval, Array_t*, const TypeInfo_t*)
+public void Int64$deserialize(FILE *in, void *outval, List_t*, const TypeInfo_t*)
 {
     uint64_t z = 0;
     for(size_t shift = 0; ; shift += 7) {
@@ -541,7 +541,7 @@ public void Int32$serialize(const void *obj, FILE *out, Table_t*, const TypeInfo
     fputc((uint8_t)z, out);
 }
 
-public void Int32$deserialize(FILE *in, void *outval, Array_t*, const TypeInfo_t*)
+public void Int32$deserialize(FILE *in, void *outval, List_t*, const TypeInfo_t*)
 {
     uint32_t z = 0;
     for(size_t shift = 0; ; shift += 7) {
@@ -580,14 +580,14 @@ public void Int32$deserialize(FILE *in, void *outval, Array_t*, const TypeInfo_t
         Int_t as_int = Int$from_int64((int64_t)i); \
         return Int$octal(as_int, digits_int, prefix); \
     } \
-    public Array_t KindOfInt ## $bits(c_type x) { \
-        Array_t bit_array = (Array_t){.data=GC_MALLOC_ATOMIC(sizeof(bool[8*sizeof(c_type)])), .atomic=1, .stride=sizeof(bool), .length=8*sizeof(c_type)}; \
-        bool *bits = bit_array.data + sizeof(c_type)*8; \
+    public List_t KindOfInt ## $bits(c_type x) { \
+        List_t bit_list = (List_t){.data=GC_MALLOC_ATOMIC(sizeof(bool[8*sizeof(c_type)])), .atomic=1, .stride=sizeof(bool), .length=8*sizeof(c_type)}; \
+        bool *bits = bit_list.data + sizeof(c_type)*8; \
         for (size_t i = 0; i < 8*sizeof(c_type); i++) { \
             *(bits--) = x & 1; \
             x >>= 1; \
         } \
-        return bit_array; \
+        return bit_list; \
     } \
     typedef struct { \
         Optional##KindOfInt##_t current, last; \
diff --git a/src/stdlib/integers.h b/src/stdlib/integers.h
index 43fc2217..8988e7c8 100644
--- a/src/stdlib/integers.h
+++ b/src/stdlib/integers.h
@@ -29,7 +29,7 @@
     Text_t type_name ## $format(c_type i, Int_t digits); \
     Text_t type_name ## $hex(c_type i, Int_t digits, bool uppercase, bool prefix); \
     Text_t type_name ## $octal(c_type i, Int_t digits, bool prefix); \
-    Array_t type_name ## $bits(c_type x); \
+    List_t type_name ## $bits(c_type x); \
     Closure_t type_name ## $to(c_type first, c_type last, Optional ## type_name ## _t step); \
     Closure_t type_name ## $onward(c_type first, c_type step); \
     PUREFUNC Optional ## type_name ## _t type_name ## $parse(Text_t text); \
@@ -84,9 +84,9 @@ DEFINE_INT_TYPE(int8_t,  Int8)
 #define Int8$abs(...) I8(abs(__VA_ARGS__))
 
 void Int64$serialize(const void *obj, FILE *out, Table_t*, const TypeInfo_t*);
-void Int64$deserialize(FILE *in, void *outval, Array_t*, const TypeInfo_t*);
+void Int64$deserialize(FILE *in, void *outval, List_t*, const TypeInfo_t*);
 void Int32$serialize(const void *obj, FILE *out, Table_t*, const TypeInfo_t*);
-void Int32$deserialize(FILE *in, void *outval, Array_t*, const TypeInfo_t*);
+void Int32$deserialize(FILE *in, void *outval, List_t*, const TypeInfo_t*);
 
 Text_t Int$as_text(const void *i, bool colorize, const TypeInfo_t *type);
 Text_t Int$value_as_text(Int_t i);
diff --git a/src/stdlib/lists.c b/src/stdlib/lists.c
new file mode 100644
index 00000000..69ac7026
--- /dev/null
+++ b/src/stdlib/lists.c
@@ -0,0 +1,813 @@
+// Functions that operate on lists
+
+#include <gc.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <sys/param.h>
+
+#include "lists.h"
+#include "integers.h"
+#include "math.h"
+#include "metamethods.h"
+#include "optionals.h"
+#include "tables.h"
+#include "text.h"
+#include "util.h"
+
+// Use inline version of siphash code:
+#include "siphash.h"
+#include "siphash-internals.h"
+
+PUREFUNC static INLINE int64_t get_padded_item_size(const TypeInfo_t *info)
+{
+    int64_t size = info->ListInfo.item->size;
+    if (info->ListInfo.item->align > 1 && size % info->ListInfo.item->align)
+        errx(1, "Item size is not padded!");
+    return size;
+}
+
+// Replace the list's .data pointer with a new pointer to a copy of the
+// data that is compacted and has a stride of exactly `padded_item_size`
+public void List$compact(List_t *list, int64_t padded_item_size)
+{
+    void *copy = NULL;
+    if (list->length > 0) {
+        copy = list->atomic ? GC_MALLOC_ATOMIC((size_t)list->length * (size_t)padded_item_size)
+            : GC_MALLOC((size_t)list->length * (size_t)padded_item_size);
+        if ((int64_t)list->stride == padded_item_size) {
+            memcpy(copy, list->data, (size_t)list->length * (size_t)padded_item_size);
+        } else {
+            for (int64_t i = 0; i < list->length; i++)
+                memcpy(copy + i*padded_item_size, list->data + list->stride*i, (size_t)padded_item_size);
+        }
+    }
+    *list = (List_t){
+        .data=copy,
+        .length=list->length,
+        .stride=padded_item_size,
+        .atomic=list->atomic,
+    };
+}
+
+public void List$insert(List_t *list, const void *item, Int_t int_index, int64_t padded_item_size)
+{
+    int64_t index = Int64$from_int(int_index, false);
+    if (index <= 0) index = list->length + index + 1;
+
+    if (index < 1) index = 1;
+    else if (index > (int64_t)list->length + 1)
+        fail("Invalid insertion index ", index, " for a list with length ", (int64_t)list->length);
+
+    if (!list->data) {
+        list->free = 4;
+        list->data = list->atomic ? GC_MALLOC_ATOMIC((size_t)list->free * (size_t)padded_item_size)
+            : GC_MALLOC((size_t)list->free * (size_t)padded_item_size);
+        list->stride = padded_item_size;
+    } else if (list->free < 1 || list->data_refcount != 0 || (int64_t)list->stride != padded_item_size) {
+        // Resize policy: +50% growth (clamped between 8 and LIST_MAX_FREE_ENTRIES)
+        list->free = MIN(LIST_MAX_FREE_ENTRIES, MAX(8, list->length)/2);
+        void *copy = list->atomic ? GC_MALLOC_ATOMIC((size_t)(list->length + list->free) * (size_t)padded_item_size)
+            : GC_MALLOC((size_t)(list->length + list->free) * (size_t)padded_item_size);
+        for (int64_t i = 0; i < index-1; i++)
+            memcpy(copy + i*padded_item_size, list->data + list->stride*i, (size_t)padded_item_size);
+        for (int64_t i = index-1; i < (int64_t)list->length; i++)
+            memcpy(copy + (i+1)*padded_item_size, list->data + list->stride*i, (size_t)padded_item_size);
+        list->data = copy;
+        list->data_refcount = 0;
+        list->stride = padded_item_size;
+    } else {
+        if (index != list->length+1)
+            memmove(
+                list->data + index*padded_item_size,
+                list->data + (index-1)*padded_item_size,
+                (size_t)((list->length - index + 1)*padded_item_size));
+    }
+    assert(list->free > 0);
+    --list->free;
+    ++list->length;
+    memcpy((void*)list->data + (index-1)*padded_item_size, item, (size_t)padded_item_size);
+}
+
+public void List$insert_all(List_t *list, List_t to_insert, Int_t int_index, int64_t padded_item_size)
+{
+    int64_t index = Int64$from_int(int_index, false);
+    if (to_insert.length == 0)
+        return;
+
+    if (!list->data) {
+        *list = to_insert;
+        LIST_INCREF(*list);
+        return;
+    }
+
+    if (index < 1) index = list->length + index + 1;
+
+    if (index < 1) index = 1;
+    else if (index > (int64_t)list->length + 1)
+        fail("Invalid insertion index ", index, " for a list with length ", (int64_t)list->length);
+
+    if ((int64_t)list->free >= (int64_t)to_insert.length // Adequate free space
+        && list->data_refcount == 0 // Not aliased memory
+        && (int64_t)list->stride == padded_item_size) { // Contiguous list
+        // If we can fit this within the list's preallocated free space, do that:
+        list->free -= to_insert.length;
+        list->length += to_insert.length;
+        if (index != list->length+1)
+            memmove((void*)list->data + index*padded_item_size,
+                    list->data + (index-1)*padded_item_size,
+                    (size_t)((list->length - index + to_insert.length-1)*padded_item_size));
+        for (int64_t i = 0; i < to_insert.length; i++)
+            memcpy((void*)list->data + (index-1 + i)*padded_item_size,
+                   to_insert.data + i*to_insert.stride, (size_t)padded_item_size);
+    } else {
+        // Otherwise, allocate a new chunk of memory for the list and populate it:
+        int64_t new_len = list->length + to_insert.length;
+        list->free = MIN(LIST_MAX_FREE_ENTRIES, MAX(8, new_len/4));
+        void *data = list->atomic ? GC_MALLOC_ATOMIC((size_t)((new_len + list->free) * padded_item_size))
+            : GC_MALLOC((size_t)((new_len + list->free) * padded_item_size));
+        void *p = data;
+
+        // Copy first chunk of `list` if needed:
+        if (index > 1) {
+            if (list->stride == padded_item_size) {
+                memcpy(p, list->data, (size_t)((index-1)*padded_item_size));
+                p += (index-1)*padded_item_size;
+            } else {
+                for (int64_t i = 0; i < index-1; i++) {
+                    memcpy(p, list->data + list->stride*i, (size_t)padded_item_size);
+                    p += padded_item_size;
+                }
+            }
+        }
+
+        // Copy `to_insert`
+        if (to_insert.stride == padded_item_size) {
+            memcpy(p, to_insert.data, (size_t)(to_insert.length*padded_item_size));
+            p += to_insert.length*padded_item_size;
+        } else {
+            for (int64_t i = 0; i < index-1; i++) {
+                memcpy(p, to_insert.data + to_insert.stride*i, (size_t)padded_item_size);
+                p += padded_item_size;
+            }
+        }
+
+        // Copy last chunk of `list` if needed:
+        if (index < list->length + 1) {
+            if (list->stride == padded_item_size) {
+                memcpy(p, list->data + padded_item_size*(index-1), (size_t)((list->length - index + 1)*padded_item_size));
+                p += (list->length - index + 1)*padded_item_size;
+            } else {
+                for (int64_t i = index-1; i < list->length-1; i++) {
+                    memcpy(p, list->data + list->stride*i, (size_t)padded_item_size);
+                    p += padded_item_size;
+                }
+            }
+        }
+        list->length = new_len;
+        list->stride = padded_item_size;
+        list->data = data;
+        list->data_refcount = 0;
+    }
+}
+
+public void List$remove_at(List_t *list, Int_t int_index, Int_t int_count, int64_t padded_item_size)
+{
+    int64_t index = Int64$from_int(int_index, false);
+    if (index < 1) index = list->length + index + 1;
+
+    int64_t count = Int64$from_int(int_count, false);
+    if (index < 1 || index > (int64_t)list->length || count < 1) return;
+
+    if (count > list->length - index + 1)
+        count = (list->length - index) + 1;
+
+    if (index == 1) {
+        list->data += list->stride * count;
+    } else if (index + count > list->length) {
+        list->free += count;
+    } else if (list->data_refcount != 0 || (int64_t)list->stride != padded_item_size) {
+        void *copy = list->atomic ? GC_MALLOC_ATOMIC((size_t)((list->length-1) * padded_item_size))
+            : GC_MALLOC((size_t)((list->length-1) * padded_item_size));
+        for (int64_t src = 1, dest = 1; src <= (int64_t)list->length; src++) {
+            if (src < index || src >= index + count) {
+                memcpy(copy + (dest - 1)*padded_item_size, list->data + list->stride*(src - 1), (size_t)padded_item_size);
+                ++dest;
+            }
+        }
+        list->data = copy;
+        list->free = 0;
+        list->data_refcount = 0;
+    } else {
+        memmove((void*)list->data + (index-1)*padded_item_size, list->data + (index-1 + count)*padded_item_size,
+                (size_t)((list->length - index + count - 1)*padded_item_size));
+        list->free += count;
+    }
+    list->length -= count;
+    if (list->length == 0) list->data = NULL;
+}
+
+public void List$remove_item(List_t *list, void *item, Int_t max_removals, const TypeInfo_t *type)
+{
+    int64_t padded_item_size = get_padded_item_size(type);
+    const Int_t ZERO = (Int_t){.small=(0<<2)|1};
+    const Int_t ONE = (Int_t){.small=(1<<2)|1};
+    const TypeInfo_t *item_type = type->ListInfo.item;
+    for (int64_t i = 0; i < list->length; ) {
+        if (max_removals.small == ZERO.small) // zero
+            break;
+
+        if (generic_equal(item, list->data + i*list->stride, item_type)) {
+            List$remove_at(list, I(i+1), ONE, padded_item_size);
+            max_removals = Int$minus(max_removals, ONE);
+        } else {
+            i++;
+        }
+    }
+}
+
+public OptionalInt_t List$find(List_t list, void *item, const TypeInfo_t *type)
+{
+    const TypeInfo_t *item_type = type->ListInfo.item;
+    for (int64_t i = 0; i < list.length; i++) {
+        if (generic_equal(item, list.data + i*list.stride, item_type))
+            return I(i+1);
+    }
+    return NONE_INT;
+}
+
+public OptionalInt_t List$first(List_t list, Closure_t predicate)
+{
+    bool (*is_good)(void*, void*) = (void*)predicate.fn;
+    for (int64_t i = 0; i < list.length; i++) {
+        if (is_good(list.data + i*list.stride, predicate.userdata))
+            return I(i+1);
+    }
+    return NONE_INT;
+}
+
+static Closure_t _sort_comparison = {.fn=NULL};
+
+int _compare_closure(const void *a, const void *b)
+{
+    typedef int (*comparison_t)(const void*, const void*, void*);
+    return ((comparison_t)_sort_comparison.fn)(a, b, _sort_comparison.userdata);
+}
+
+public void List$sort(List_t *list, Closure_t comparison, int64_t padded_item_size)
+{
+    if (list->data_refcount != 0 || (int64_t)list->stride != padded_item_size)
+        List$compact(list, padded_item_size);
+
+    _sort_comparison = comparison;
+    qsort(list->data, (size_t)list->length, (size_t)padded_item_size, _compare_closure);
+}
+
+public List_t List$sorted(List_t list, Closure_t comparison, int64_t padded_item_size)
+{
+    List$compact(&list, padded_item_size);
+    _sort_comparison = comparison;
+    qsort(list.data, (size_t)list.length, (size_t)padded_item_size, _compare_closure);
+    return list;
+}
+
+#if defined(__FreeBSD__) || defined(__OpenBSD__) || defined(__NetBSD__) || defined(__APPLE__)
+static ssize_t getrandom(void *buf, size_t buflen, unsigned int flags) {
+    (void)flags;
+    arc4random_buf(buf, buflen);
+    return buflen;
+}
+#elif defined(__linux__)
+// Use getrandom()
+#   include <sys/random.h>
+#else
+    #error "Unsupported platform for secure random number generation"
+#endif
+
+static int64_t _default_random_int64(int64_t min, int64_t max, void *userdata)
+{
+    (void)userdata;
+    if (min > max) fail("Random minimum value (", min, ") is larger than the maximum value (", max, ")");
+    if (min == max) return min;
+    uint64_t range = (uint64_t)max - (uint64_t)min + 1;
+    uint64_t min_r = -range % range;
+    uint64_t r;
+    for (;;) {
+        getrandom(&r, sizeof(r), 0);
+        if (r >= min_r) break;
+    }
+    return (int64_t)((uint64_t)min + (r % range));
+}
+
+public void List$shuffle(List_t *list, OptionalClosure_t random_int64, int64_t padded_item_size)
+{
+    if (list->data_refcount != 0 || (int64_t)list->stride != padded_item_size)
+        List$compact(list, padded_item_size);
+
+    typedef int64_t (*rng_fn_t)(int64_t, int64_t, void*);
+    rng_fn_t rng_fn = random_int64.fn ? (rng_fn_t)random_int64.fn : _default_random_int64;
+    char tmp[padded_item_size];
+    for (int64_t i = list->length-1; i > 1; i--) {
+        int64_t j = rng_fn(0, i, random_int64.userdata);
+        if unlikely (j < 0 || j > list->length-1)
+            fail("The provided random number function returned an invalid value: ", j, " (not between 0 and ", i, ")");
+        memcpy(tmp, list->data + i*padded_item_size, (size_t)padded_item_size);
+        memcpy((void*)list->data + i*padded_item_size, list->data + j*padded_item_size, (size_t)padded_item_size);
+        memcpy((void*)list->data + j*padded_item_size, tmp, (size_t)padded_item_size);
+    }
+}
+
+public List_t List$shuffled(List_t list, Closure_t random_int64, int64_t padded_item_size)
+{
+    List$compact(&list, padded_item_size);
+    List$shuffle(&list, random_int64, padded_item_size);
+    return list;
+}
+
+public void *List$random(List_t list, OptionalClosure_t random_int64)
+{
+    if (list.length == 0)
+        return NULL; // fail("Cannot get a random item from an empty list!");
+
+    typedef int64_t (*rng_fn_t)(int64_t, int64_t, void*);
+    rng_fn_t rng_fn = random_int64.fn ? (rng_fn_t)random_int64.fn : _default_random_int64;
+    int64_t index = rng_fn(0, list.length-1, random_int64.userdata);
+    if unlikely (index < 0 || index > list.length-1)
+        fail("The provided random number function returned an invalid value: ", index, " (not between 0 and ", (int64_t)list.length, ")");
+    return list.data + list.stride*index;
+}
+
+public Table_t List$counts(List_t list, const TypeInfo_t *type)
+{
+    Table_t counts = {};
+    const TypeInfo_t count_type = *Table$info(type->ListInfo.item, &Int$info);
+    for (int64_t i = 0; i < list.length; i++) {
+        void *key = list.data + i*list.stride;
+        int64_t *count = Table$get(counts, key, &count_type);
+        int64_t val = count ? *count + 1 : 1;
+        Table$set(&counts, key, &val, &count_type);
+    }
+    return counts;
+}
+
+static double _default_random_num(void *userdata)
+{
+    (void)userdata;
+    union {
+        Num_t num;
+        uint64_t bits;
+    } r = {.bits=0}, one = {.num=1.0};
+    getrandom((uint8_t*)&r, sizeof(r), 0);
+
+    // Set r.num to 1.<random-bits>
+    r.bits &= ~(0xFFFULL << 52);
+    r.bits |= (one.bits & (0xFFFULL << 52));
+    return r.num - 1.0;
+}
+
+public List_t List$sample(List_t list, Int_t int_n, List_t weights, OptionalClosure_t random_num, int64_t padded_item_size)
+{
+    int64_t n = Int64$from_int(int_n, false);
+    if (n < 0)
+        fail("Cannot select a negative number of values");
+
+    if (n == 0)
+        return (List_t){};
+
+    if (list.length == 0)
+        fail("There are no elements in this list!");
+
+    if (weights.length != list.length)
+        fail("List has ", (int64_t)list.length, " elements, but there are ", (int64_t)weights.length, " weights given");
+
+    double total = 0.0;
+    for (int64_t i = 0; i < weights.length && i < list.length; i++) {
+        double weight = *(double*)(weights.data + weights.stride*i);
+        if (isinf(weight))
+            fail("Infinite weight!");
+        else if (isnan(weight))
+            fail("NaN weight!");
+        else if (weight < 0.0)
+            fail("Negative weight!");
+        else
+            total += weight;
+    }
+
+    if (isinf(total))
+        fail("Sample weights have overflowed to infinity");
+
+    if (total == 0.0)
+        fail("None of the given weights are nonzero");
+
+    double inverse_average = (double)list.length / total;
+
+    struct {
+        int64_t alias;
+        double odds;
+    } aliases[list.length];
+
+    for (int64_t i = 0; i < list.length; i++) {
+        double weight = i >= weights.length ? 0.0 : *(double*)(weights.data + weights.stride*i);
+        aliases[i].odds = weight * inverse_average;
+        aliases[i].alias = -1;
+    }
+
+    int64_t small = 0;
+    for (int64_t big = 0; big < list.length; big++) {
+        while (aliases[big].odds >= 1.0) {
+            while (small < list.length && (aliases[small].odds >= 1.0 || aliases[small].alias != -1))
+                ++small;
+
+            if (small >= list.length) {
+                aliases[big].odds = 1.0;
+                aliases[big].alias = big;
+                break;
+            }
+
+            aliases[small].alias = big;
+            aliases[big].odds = (aliases[small].odds + aliases[big].odds) - 1.0;
+        }
+        if (big < small) small = big;
+    }
+
+    for (int64_t i = small; i < list.length; i++)
+        if (aliases[i].alias == -1)
+            aliases[i].alias = i;
+
+    typedef double (*rng_fn_t)(void*);
+    rng_fn_t rng_fn = random_num.fn ? (rng_fn_t)random_num.fn : _default_random_num;
+
+    List_t selected = {
+        .data=list.atomic ? GC_MALLOC_ATOMIC((size_t)(n * padded_item_size)) : GC_MALLOC((size_t)(n * padded_item_size)),
+        .length=n,
+        .stride=padded_item_size, .atomic=list.atomic};
+    for (int64_t i = 0; i < n; i++) {
+        double r = rng_fn(random_num.userdata);
+        if unlikely (r < 0.0 || r >= 1.0)
+            fail("The random number function returned a value not between 0.0 (inclusive) and 1.0 (exclusive): ", r);
+        r *= (double)list.length;
+        int64_t index = (int64_t)r;
+        assert(index >= 0 && index < list.length);
+        if ((r - (double)index) > aliases[index].odds)
+            index = aliases[index].alias;
+        memcpy(selected.data + i*selected.stride, list.data + index*list.stride, (size_t)padded_item_size);
+    }
+    return selected;
+}
+
+public List_t List$from(List_t list, Int_t first)
+{
+    return List$slice(list, first, I_small(-1));
+}
+
+public List_t List$to(List_t list, Int_t last)
+{
+    return List$slice(list, I_small(1), last);
+}
+
+public List_t List$by(List_t list, Int_t int_stride, int64_t padded_item_size)
+{
+    int64_t stride = Int64$from_int(int_stride, false);
+    // In the unlikely event that the stride value would be too large to fit in
+    // a 15-bit integer, fall back to creating a copy of the list:
+    if (unlikely(list.stride*stride < LIST_MIN_STRIDE || list.stride*stride > LIST_MAX_STRIDE)) {
+        void *copy = NULL;
+        int64_t len = (stride < 0 ? list.length / -stride : list.length / stride) + ((list.length % stride) != 0);
+        if (len > 0) {
+            copy = list.atomic ? GC_MALLOC_ATOMIC((size_t)(len * padded_item_size)) : GC_MALLOC((size_t)(len * padded_item_size));
+            void *start = (stride < 0 ? list.data + (list.stride * (list.length - 1)) : list.data);
+            for (int64_t i = 0; i < len; i++)
+                memcpy(copy + i*padded_item_size, start + list.stride*stride*i, (size_t)padded_item_size);
+        }
+        return (List_t){
+            .data=copy,
+            .length=len,
+            .stride=padded_item_size,
+            .atomic=list.atomic,
+        };
+    }
+
+    if (stride == 0)
+        return (List_t){.atomic=list.atomic};
+
+    return (List_t){
+        .atomic=list.atomic,
+        .data=(stride < 0 ? list.data + (list.stride * (list.length - 1)) : list.data),
+        .length=(stride < 0 ? list.length / -stride : list.length / stride) + ((list.length % stride) != 0),
+        .stride=list.stride * stride,
+        .data_refcount=list.data_refcount,
+    };
+}
+
+public List_t List$slice(List_t list, Int_t int_first, Int_t int_last)
+
+{
+    int64_t first = Int64$from_int(int_first, false);
+    if (first < 0)
+        first = list.length + first + 1;
+
+    int64_t last = Int64$from_int(int_last, false);
+    if (last < 0)
+        last = list.length + last + 1;
+
+    if (last > list.length)
+        last = list.length;
+
+    if (first < 1 || first > list.length || last == 0)
+        return (List_t){.atomic=list.atomic};
+
+    return (List_t){
+        .atomic=list.atomic,
+        .data=list.data + list.stride*(first-1),
+        .length=last - first + 1,
+        .stride=list.stride,
+        .data_refcount=list.data_refcount,
+    };
+}
+
+public List_t List$reversed(List_t list, int64_t padded_item_size)
+{
+    // Just in case negating the stride gives a value that doesn't fit into a
+    // 15-bit integer, fall back to List$by()'s more general method of copying
+    // the list. This should only happen if list.stride is MIN_STRIDE to
+    // begin with (very unlikely).
+    if (unlikely(-list.stride < LIST_MIN_STRIDE || -list.stride > LIST_MAX_STRIDE))
+        return List$by(list, I(-1), padded_item_size);
+
+    List_t reversed = list;
+    reversed.stride = -list.stride;
+    reversed.data = list.data + (list.length-1)*list.stride;
+    return reversed;
+}
+
+public List_t List$concat(List_t x, List_t y, int64_t padded_item_size)
+{
+    void *data = x.atomic ? GC_MALLOC_ATOMIC((size_t)(padded_item_size*(x.length + y.length)))
+        : GC_MALLOC((size_t)(padded_item_size*(x.length + y.length)));
+    if (x.stride == padded_item_size) {
+        memcpy(data, x.data, (size_t)(padded_item_size*x.length));
+    } else {
+        for (int64_t i = 0; i < x.length; i++)
+            memcpy(data + i*padded_item_size, x.data + i*padded_item_size, (size_t)padded_item_size);
+    }
+
+    void *dest = data + padded_item_size*x.length;
+    if (y.stride == padded_item_size) {
+        memcpy(dest, y.data, (size_t)(padded_item_size*y.length));
+    } else {
+        for (int64_t i = 0; i < y.length; i++)
+            memcpy(dest + i*padded_item_size, y.data + i*y.stride, (size_t)padded_item_size);
+    }
+
+    return (List_t){
+        .data=data,
+        .length=x.length + y.length,
+        .stride=padded_item_size,
+        .atomic=x.atomic,
+    };
+}
+
+public bool List$has(List_t list, void *item, const TypeInfo_t *type)
+{
+    const TypeInfo_t *item_type = type->ListInfo.item;
+    for (int64_t i = 0; i < list.length; i++) {
+        if (generic_equal(list.data + i*list.stride, item, item_type))
+            return true;
+    }
+    return false;
+}
+
+public void List$clear(List_t *list)
+{
+    *list = (List_t){.data=0, .length=0};
+}
+
+public int32_t List$compare(const void *vx, const void *vy, const TypeInfo_t *type)
+{
+    const List_t *x = (List_t*)vx, *y = (List_t*)vy;
+    // Early out for lists with the same data, e.g. two copies of the same list:
+    if (x->data == y->data && x->stride == y->stride)
+        return (x->length > y->length) - (x->length < y->length);
+
+    const TypeInfo_t *item = type->ListInfo.item;
+    if (item->tag == PointerInfo || !item->metamethods.compare) { // data comparison
+        int64_t item_padded_size = type->ListInfo.item->size;
+        if (type->ListInfo.item->align > 1 && item_padded_size % type->ListInfo.item->align)
+            errx(1, "Item size is not padded!");
+
+        if ((int64_t)x->stride == item_padded_size && (int64_t)y->stride == item_padded_size && item->size == item_padded_size) {
+            int32_t cmp = (int32_t)memcmp(x->data, y->data, (size_t)(MIN(x->length, y->length)*item_padded_size));
+            if (cmp != 0) return cmp;
+        } else {
+            for (int32_t i = 0, len = MIN(x->length, y->length); i < len; i++) {
+                int32_t cmp = (int32_t)memcmp(x->data+ x->stride*i, y->data + y->stride*i, (size_t)(item->size));
+                if (cmp != 0) return cmp;
+            }
+        }
+    } else {
+        for (int32_t i = 0, len = MIN(x->length, y->length); i < len; i++) {
+            int32_t cmp = generic_compare(x->data + x->stride*i, y->data + y->stride*i, item);
+            if (cmp != 0) return cmp;
+        }
+    }
+    return (x->length > y->length) - (x->length < y->length);
+}
+
+public bool List$equal(const void *x, const void *y, const TypeInfo_t *type)
+{
+    return x == y || (((List_t*)x)->length == ((List_t*)y)->length && List$compare(x, y, type) == 0);
+}
+
+public Text_t List$as_text(const void *obj, bool colorize, const TypeInfo_t *type)
+{
+    List_t *list = (List_t*)obj;
+    if (!list)
+        return Text$concat(Text("["), generic_as_text(NULL, false, type->ListInfo.item), Text("]"));
+
+    const TypeInfo_t *item_type = type->ListInfo.item;
+    Text_t text = Text("[");
+    for (int64_t i = 0; i < list->length; i++) {
+        if (i > 0)
+            text = Text$concat(text, Text(", "));
+        Text_t item_text = generic_as_text(list->data + i*list->stride, colorize, item_type);
+        text = Text$concat(text, item_text);
+    }
+    text = Text$concat(text, Text("]"));
+    return text;
+}
+
+public uint64_t List$hash(const void *obj, const TypeInfo_t *type)
+{
+    const List_t *list = (List_t*)obj;
+    const TypeInfo_t *item = type->ListInfo.item;
+    siphash sh;
+    siphashinit(&sh, sizeof(uint64_t[list->length]));
+    if (item->tag == PointerInfo || (!item->metamethods.hash && item->size == sizeof(void*))) { // Raw data hash
+        for (int64_t i = 0; i < list->length; i++)
+            siphashadd64bits(&sh, (uint64_t)(list->data + i*list->stride));
+    } else {
+        for (int64_t i = 0; i < list->length; i++) {
+            uint64_t item_hash = generic_hash(list->data + i*list->stride, item);
+            siphashadd64bits(&sh, item_hash);
+        }
+    }
+    return siphashfinish_last_part(&sh, 0);
+}
+
+static void siftdown(List_t *heap, int64_t startpos, int64_t pos, Closure_t comparison, int64_t padded_item_size)
+{
+    assert(pos > 0 && pos < heap->length);
+    char newitem[padded_item_size];
+    memcpy(newitem, heap->data + heap->stride*pos, (size_t)(padded_item_size));
+    while (pos > startpos) {
+        int64_t parentpos = (pos - 1) >> 1;
+        typedef int32_t (*cmp_fn_t)(void*, void*, void*);
+        int32_t cmp = ((cmp_fn_t)comparison.fn)(newitem, heap->data + heap->stride*parentpos, comparison.userdata);
+        if (cmp >= 0)
+            break;
+
+        memcpy(heap->data + heap->stride*pos, heap->data + heap->stride*parentpos, (size_t)(padded_item_size));
+        pos = parentpos;
+    }
+    memcpy(heap->data + heap->stride*pos, newitem, (size_t)(padded_item_size));
+}
+
+static void siftup(List_t *heap, int64_t pos, Closure_t comparison, int64_t padded_item_size)
+{
+    int64_t endpos = heap->length;
+    int64_t startpos = pos;
+    assert(pos < endpos);
+
+    char old_top[padded_item_size];
+    memcpy(old_top, heap->data + heap->stride*pos, (size_t)(padded_item_size));
+    // Bubble up the smallest leaf node
+    int64_t limit = endpos >> 1;
+    while (pos < limit) {
+        int64_t childpos = 2*pos + 1; // Smaller of the two child nodes
+        if (childpos + 1 < endpos) {
+            typedef int32_t (*cmp_fn_t)(void*, void*, void*);
+            int32_t cmp = ((cmp_fn_t)comparison.fn)(
+                heap->data + heap->stride*childpos,
+                heap->data + heap->stride*(childpos + 1),
+                comparison.userdata);
+            childpos += (cmp >= 0);
+        }
+
+        // Move the child node up:
+        memcpy(heap->data + heap->stride*pos, heap->data + heap->stride*childpos, (size_t)(padded_item_size));
+        pos = childpos;
+    }
+    memcpy(heap->data + heap->stride*pos, old_top, (size_t)(padded_item_size));
+    // Shift the node's parents down:
+    siftdown(heap, startpos, pos, comparison, padded_item_size);
+}
+
+public void List$heap_push(List_t *heap, const void *item, Closure_t comparison, int64_t padded_item_size)
+{
+    List$insert(heap, item, I(0), padded_item_size);
+
+    if (heap->length > 1) {
+        if (heap->data_refcount != 0)
+            List$compact(heap, padded_item_size);
+        siftdown(heap, 0, heap->length-1, comparison, padded_item_size);
+    }
+}
+
+public void List$heap_pop(List_t *heap, Closure_t comparison, int64_t padded_item_size)
+{
+    if (heap->length == 0)
+        fail("Attempt to pop from an empty list");
+
+    if (heap->length == 1) {
+        *heap = (List_t){};
+    } else if (heap->length == 2) {
+        heap->data += heap->stride;
+        --heap->length;
+    } else {
+        if (heap->data_refcount != 0)
+            List$compact(heap, padded_item_size);
+        memcpy(heap->data, heap->data + heap->stride*(heap->length-1), (size_t)(padded_item_size));
+        --heap->length;
+        siftup(heap, 0, comparison, padded_item_size);
+    }
+}
+
+public void List$heapify(List_t *heap, Closure_t comparison, int64_t padded_item_size)
+{
+    if (heap->data_refcount != 0)
+        List$compact(heap, padded_item_size);
+
+    // It's necessary to bump the refcount because the user's comparison
+    // function could do stuff that modifies the heap's data.
+    LIST_INCREF(*heap);
+    int64_t i, n = heap->length;
+    for (i = (n >> 1) - 1 ; i >= 0 ; i--)
+        siftup(heap, i, comparison, padded_item_size);
+    LIST_DECREF(*heap);
+}
+
+public Int_t List$binary_search(List_t list, void *target, Closure_t comparison)
+{
+    typedef int32_t (*cmp_fn_t)(void*, void*, void*);
+    int64_t lo = 0, hi = list.length-1;
+    while (lo <= hi) {
+        int64_t mid = (lo + hi) / 2;
+        int32_t cmp = ((cmp_fn_t)comparison.fn)(
+            list.data + list.stride*mid, target, comparison.userdata);
+        if (cmp == 0)
+            return I(mid+1);
+        else if (cmp < 0)
+            lo = mid + 1;
+        else if (cmp > 0)
+            hi = mid - 1;
+    }
+    return I(lo+1); // Return the index where the target would be inserted
+}
+
+public PUREFUNC bool List$is_none(const void *obj, const TypeInfo_t*)
+{
+    return ((List_t*)obj)->length < 0;
+}
+
+public void List$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type)
+{
+    List_t list = *(List_t*)obj;
+    int64_t len = list.length;
+    Int64$serialize(&len, out, pointers, &Int64$info);
+    auto item_serialize = type->ListInfo.item->metamethods.serialize;
+    if (item_serialize) {
+        for (int64_t i = 0; i < len; i++)
+            item_serialize(list.data + i*list.stride, out, pointers, type->ListInfo.item);
+    } else if (list.stride == type->ListInfo.item->size) {
+        fwrite(list.data, (size_t)type->ListInfo.item->size, (size_t)len, out);
+    } else {
+        for (int64_t i = 0; i < len; i++)
+            fwrite(list.data + i*list.stride, (size_t)type->ListInfo.item->size, 1, out);
+    }
+}
+
+public void List$deserialize(FILE *in, void *obj, List_t *pointers, const TypeInfo_t *type)
+{
+    int64_t len = -1;
+    Int64$deserialize(in, &len, pointers, &Int64$info);
+    int64_t padded_size = type->ListInfo.item->size;
+    if (type->ListInfo.item->align > 0 && padded_size % type->ListInfo.item->align > 0)
+        padded_size += type->ListInfo.item->align - (padded_size % type->ListInfo.item->align);
+    List_t list = {
+        .length=len,
+        .data=GC_MALLOC((size_t)(len*padded_size)),
+        .stride=padded_size,
+    };
+    auto item_deserialize = type->ListInfo.item->metamethods.deserialize;
+    if (item_deserialize) {
+        for (int64_t i = 0; i < len; i++)
+            item_deserialize(in, list.data + i*list.stride, pointers, type->ListInfo.item);
+    } else if (list.stride == type->ListInfo.item->size) {
+        fread(list.data, (size_t)type->ListInfo.item->size, (size_t)len, in);
+    } else {
+        for (int64_t i = 0; i < len; i++)
+            fread(list.data + i*list.stride, (size_t)type->ListInfo.item->size, 1, in);
+    }
+    *(List_t*)obj = list;
+}
+
+// vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0
diff --git a/src/stdlib/lists.h b/src/stdlib/lists.h
new file mode 100644
index 00000000..a2853e48
--- /dev/null
+++ b/src/stdlib/lists.h
@@ -0,0 +1,137 @@
+#pragma once
+
+// Functions that operate on lists
+
+#include <stdbool.h>
+
+#include "datatypes.h"
+#include "integers.h"
+#include "types.h"
+#include "util.h"
+
+// Convert negative indices to back-indexed without branching: index0 = index + (index < 0)*(len+1)) - 1
+#define List_get(item_type, arr_expr, index_expr, start, end) *({ \
+    const List_t list = arr_expr; int64_t index = index_expr; \
+    int64_t off = index + (index < 0) * (list.length + 1) - 1; \
+    if (unlikely(off < 0 || off >= list.length)) \
+        fail_source(__SOURCE_FILE__, start, end, "Invalid list index: ", index, " (list has length ", (int64_t)list.length, ")\n"); \
+    (item_type*)(list.data + list.stride * off);})
+#define List_get_unchecked(type, x, i) *({ const List_t list = x; int64_t index = i; \
+                                          int64_t off = index + (index < 0) * (list.length + 1) - 1; \
+                                          (type*)(list.data + list.stride * off);})
+#define List_lvalue(item_type, arr_expr, index_expr, start, end) *({ \
+    List_t *list = arr_expr; int64_t index = index_expr; \
+    int64_t off = index + (index < 0) * (list->length + 1) - 1; \
+    if (unlikely(off < 0 || off >= list->length)) \
+        fail_source(__SOURCE_FILE__, start, end, "Invalid list index: ", index, " (list has length ", (int64_t)list->length, ")\n"); \
+    if (list->data_refcount > 0) \
+        List$compact(list, sizeof(item_type)); \
+    (item_type*)(list->data + list->stride * off); })
+#define List_lvalue_unchecked(item_type, arr_expr, index_expr) *({ \
+    List_t *list = arr_expr; int64_t index = index_expr; \
+    int64_t off = index + (index < 0) * (list->length + 1) - 1; \
+    if (list->data_refcount > 0) \
+        List$compact(list, sizeof(item_type)); \
+    (item_type*)(list->data + list->stride * off); })
+#define List_set(item_type, list, index, value, start, end) \
+    List_lvalue(item_type, arr_expr, index, start, end) = value
+#define is_atomic(x) _Generic(x, bool: true, int8_t: true, int16_t: true, int32_t: true, int64_t: true, float: true, double: true, default: false)
+#define TypedList(t, ...) ({ t items[] = {__VA_ARGS__}; \
+                         (List_t){.length=sizeof(items)/sizeof(items[0]), \
+                         .stride=(int64_t)&items[1] - (int64_t)&items[0], \
+                         .data=memcpy(GC_MALLOC(sizeof(items)), items, sizeof(items)), \
+                         .atomic=0, \
+                         .data_refcount=0}; })
+#define TypedListN(t, N, ...) ({ t items[N] = {__VA_ARGS__}; \
+                         (List_t){.length=N, \
+                         .stride=(int64_t)&items[1] - (int64_t)&items[0], \
+                         .data=memcpy(GC_MALLOC(sizeof(items)), items, sizeof(items)), \
+                         .atomic=0, \
+                         .data_refcount=0}; })
+#define List(x, ...) ({ __typeof(x) items[] = {x, __VA_ARGS__}; \
+                         (List_t){.length=sizeof(items)/sizeof(items[0]), \
+                         .stride=(int64_t)&items[1] - (int64_t)&items[0], \
+                         .data=memcpy(is_atomic(x) ? GC_MALLOC_ATOMIC(sizeof(items)) : GC_MALLOC(sizeof(items)), items, sizeof(items)), \
+                         .atomic=is_atomic(x), \
+                         .data_refcount=0}; })
+// List refcounts use a saturating add, where once it's at the max value, it stays there.
+#define LIST_INCREF(list) (list).data_refcount += ((list).data_refcount < LIST_MAX_DATA_REFCOUNT)
+#define LIST_DECREF(list) (list).data_refcount -= ((list).data_refcount < LIST_MAX_DATA_REFCOUNT)
+#define LIST_COPY(list) ({ LIST_INCREF(list); list; })
+
+#define List$insert_value(list, item_expr, index, padded_item_size) List$insert(list, (__typeof(item_expr)[1]){item_expr}, index, padded_item_size)
+void List$insert(List_t *list, const void *item, Int_t index, int64_t padded_item_size);
+void List$insert_all(List_t *list, List_t to_insert, Int_t index, int64_t padded_item_size);
+void List$remove_at(List_t *list, Int_t index, Int_t count, int64_t padded_item_size);
+void List$remove_item(List_t *list, void *item, Int_t max_removals, const TypeInfo_t *type);
+#define List$remove_item_value(list, item_expr, max, type) List$remove_item(list, (__typeof(item_expr)[1]){item_expr}, max, type)
+
+#define List$pop(arr_expr, index_expr, item_type, nonnone_var, nonnone_expr, none_expr) ({ \
+    List_t *list = arr_expr; \
+    Int_t index = index_expr; \
+    int64_t index64 = Int64$from_int(index, false); \
+    int64_t off = index64 + (index64 < 0) * (list->length + 1) - 1; \
+    (off >= 0 && off < list->length) ? ({ \
+        item_type nonnone_var = *(item_type*)(list->data + off*list->stride); \
+        List$remove_at(list, index, I_small(1), sizeof(item_type)); \
+        nonnone_expr; \
+    }) : none_expr; })
+
+OptionalInt_t List$find(List_t list, void *item, const TypeInfo_t *type);
+#define List$find_value(list, item_expr, type) ({ __typeof(item_expr) item = item_expr; List$find(list, &item, type); })
+OptionalInt_t List$first(List_t list, Closure_t predicate);
+void List$sort(List_t *list, Closure_t comparison, int64_t padded_item_size);
+List_t List$sorted(List_t list, Closure_t comparison, int64_t padded_item_size);
+void List$shuffle(List_t *list, OptionalClosure_t random_int64, int64_t padded_item_size);
+List_t List$shuffled(List_t list, OptionalClosure_t random_int64, int64_t padded_item_size);
+void *List$random(List_t list, OptionalClosure_t random_int64);
+#define List$random_value(list, random_int64, t) ({ List_t _arr = list; if (_arr.length == 0) fail("Cannot get a random value from an empty list!"); *(t*)List$random(_arr, random_int64); })
+List_t List$sample(List_t list, Int_t n, List_t weights, Closure_t random_num, int64_t padded_item_size);
+Table_t List$counts(List_t list, const TypeInfo_t *type);
+void List$clear(List_t *list);
+void List$compact(List_t *list, int64_t padded_item_size);
+PUREFUNC bool List$has(List_t list, void *item, const TypeInfo_t *type);
+#define List$has_value(list, item_expr, type) ({ __typeof(item_expr) item = item_expr; List$has(list, &item, type); })
+PUREFUNC List_t List$from(List_t list, Int_t first);
+PUREFUNC List_t List$to(List_t list, Int_t last);
+PUREFUNC List_t List$by(List_t list, Int_t stride, int64_t padded_item_size);
+PUREFUNC List_t List$slice(List_t list, Int_t int_first, Int_t int_last);
+PUREFUNC List_t List$reversed(List_t list, int64_t padded_item_size);
+List_t List$concat(List_t x, List_t y, int64_t padded_item_size);
+PUREFUNC uint64_t List$hash(const void *list, const TypeInfo_t *type);
+PUREFUNC int32_t List$compare(const void *x, const void *y, const TypeInfo_t *type);
+PUREFUNC bool List$equal(const void *x, const void *y, const TypeInfo_t *type);
+PUREFUNC bool List$is_none(const void *obj, const TypeInfo_t*);
+Text_t List$as_text(const void *list, bool colorize, const TypeInfo_t *type);
+void List$heapify(List_t *heap, Closure_t comparison, int64_t padded_item_size);
+void List$heap_push(List_t *heap, const void *item, Closure_t comparison, int64_t padded_item_size);
+#define List$heap_push_value(heap, _value, comparison, padded_item_size) ({ __typeof(_value) value = _value; List$heap_push(heap, &value, comparison, padded_item_size); })
+void List$heap_pop(List_t *heap, Closure_t comparison, int64_t padded_item_size);
+#define List$heap_pop_value(heap, comparison, type, nonnone_var, nonnone_expr, none_expr) \
+    ({ List_t *_heap = heap; \
+     (_heap->length > 0) ? ({ \
+         type nonnone_var = *(type*)_heap->data; \
+         List$heap_pop(_heap, comparison, sizeof(type)); \
+         nonnone_expr; \
+     }) : none_expr; })
+Int_t List$binary_search(List_t list, void *target, Closure_t comparison);
+#define List$binary_search_value(list, target, comparison) \
+    ({ __typeof(target) _target = target; List$binary_search(list, &_target, comparison); })
+void List$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type);
+void List$deserialize(FILE *in, void *obj, List_t *pointers, const TypeInfo_t *type);
+
+#define List$metamethods { \
+    .as_text=List$as_text, \
+    .compare=List$compare, \
+    .equal=List$equal, \
+    .hash=List$hash, \
+    .is_none=List$is_none, \
+    .serialize=List$serialize, \
+    .deserialize=List$deserialize, \
+}
+
+#define List$info(item_info) &((TypeInfo_t){.size=sizeof(List_t), .align=__alignof__(List_t), \
+                                .tag=ListInfo, .ListInfo.item=item_info, \
+                                .metamethods=List$metamethods})
+
+// vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0
diff --git a/src/stdlib/metamethods.c b/src/stdlib/metamethods.c
index a7622e0b..6ee52222 100644
--- a/src/stdlib/metamethods.c
+++ b/src/stdlib/metamethods.c
@@ -3,7 +3,7 @@
 #include <stdint.h>
 #include <string.h>
 
-#include "arrays.h"
+#include "lists.h"
 #include "bools.h"
 #include "bytes.h"
 #include "functiontype.h"
@@ -61,7 +61,7 @@ public void _serialize(const void *obj, FILE *out, Table_t *pointers, const Type
     fwrite(obj, (size_t)type->size, 1, out);
 }
 
-public Array_t generic_serialize(const void *x, const TypeInfo_t *type)
+public List_t generic_serialize(const void *x, const TypeInfo_t *type)
 {
     char *buf = NULL;
     size_t size = 0;
@@ -69,7 +69,7 @@ public Array_t generic_serialize(const void *x, const TypeInfo_t *type)
     Table_t pointers = {};
     _serialize(x, stream, &pointers, type);
     fclose(stream);
-    Array_t bytes = {
+    List_t bytes = {
         .data=GC_MALLOC_ATOMIC(size),
         .length=(int64_t)size,
         .stride=1,
@@ -80,7 +80,7 @@ public Array_t generic_serialize(const void *x, const TypeInfo_t *type)
     return bytes;
 }
 
-public void _deserialize(FILE *input, void *outval, Array_t *pointers, const TypeInfo_t *type)
+public void _deserialize(FILE *input, void *outval, List_t *pointers, const TypeInfo_t *type)
 {
     if (type->metamethods.deserialize) {
         type->metamethods.deserialize(input, outval, pointers, type);
@@ -90,13 +90,13 @@ public void _deserialize(FILE *input, void *outval, Array_t *pointers, const Typ
     fread(outval, (size_t)type->size, 1, input);
 }
 
-public void generic_deserialize(Array_t bytes, void *outval, const TypeInfo_t *type)
+public void generic_deserialize(List_t bytes, void *outval, const TypeInfo_t *type)
 {
     if (bytes.stride != 1)
-        Array$compact(&bytes, 1);
+        List$compact(&bytes, 1);
 
     FILE *input = fmemopen(bytes.data, (size_t)bytes.length, "r");
-    Array_t pointers = {};
+    List_t pointers = {};
     _deserialize(input, outval, &pointers, type);
     fclose(input);
 }
@@ -115,7 +115,7 @@ public void cannot_serialize(const void*, FILE*, Table_t*, const TypeInfo_t *typ
 }
 
 __attribute__((noreturn))
-public void cannot_deserialize(FILE*, void*, Array_t*, const TypeInfo_t *type)
+public void cannot_deserialize(FILE*, void*, List_t*, const TypeInfo_t *type)
 {
     Text_t typestr = generic_as_text(NULL, false, type);
     fail("Values of type ", typestr, " cannot be serialized or deserialized!");
diff --git a/src/stdlib/metamethods.h b/src/stdlib/metamethods.h
index a75fcf7f..ca0a1e7e 100644
--- a/src/stdlib/metamethods.h
+++ b/src/stdlib/metamethods.h
@@ -12,11 +12,11 @@ PUREFUNC int32_t generic_compare(const void *x, const void *y, const TypeInfo_t
 PUREFUNC bool generic_equal(const void *x, const void *y, const TypeInfo_t *type);
 Text_t generic_as_text(const void *obj, bool colorize, const TypeInfo_t *type);
 void _serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type);
-Array_t generic_serialize(const void *x, const TypeInfo_t *type);
-void _deserialize(FILE *input, void *outval, Array_t *pointers, const TypeInfo_t *type);
-void generic_deserialize(Array_t bytes, void *outval, const TypeInfo_t *type);
+List_t generic_serialize(const void *x, const TypeInfo_t *type);
+void _deserialize(FILE *input, void *outval, List_t *pointers, const TypeInfo_t *type);
+void generic_deserialize(List_t bytes, void *outval, const TypeInfo_t *type);
 int generic_print(const void *obj, bool colorize, const TypeInfo_t *type);
 void cannot_serialize(const void*, FILE*, Table_t*, const TypeInfo_t *type);
-void cannot_deserialize(FILE*, void*, Array_t*, const TypeInfo_t *type);
+void cannot_deserialize(FILE*, void*, List_t*, const TypeInfo_t *type);
 
 // vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0
diff --git a/src/stdlib/nums.c b/src/stdlib/nums.c
index ca8dcc4e..9edb8751 100644
--- a/src/stdlib/nums.c
+++ b/src/stdlib/nums.c
@@ -7,7 +7,7 @@
 #include <stdint.h>
 #include <stdlib.h>
 
-#include "arrays.h"
+#include "lists.h"
 #include "nums.h"
 #include "string.h"
 #include "text.h"
diff --git a/src/stdlib/optionals.c b/src/stdlib/optionals.c
index d3309029..f33b471d 100644
--- a/src/stdlib/optionals.c
+++ b/src/stdlib/optionals.c
@@ -61,7 +61,7 @@ public void Optional$serialize(const void *obj, FILE *out, Table_t *pointers, co
         _serialize(obj, out, pointers, type->OptionalInfo.type);
 }
 
-public void Optional$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type)
+public void Optional$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type)
 {
     bool has_value = (bool)fgetc(in);
     const TypeInfo_t *nonnull = type->OptionalInfo.type;
@@ -71,8 +71,8 @@ public void Optional$deserialize(FILE *in, void *outval, Array_t *pointers, cons
     } else {
         if (nonnull->tag == TextInfo)
             *(Text_t*)outval = NONE_TEXT;
-        else if (nonnull->tag == ArrayInfo)
-            *(Array_t*)outval = (Array_t){.length=-1};
+        else if (nonnull->tag == ListInfo)
+            *(List_t*)outval = (List_t){.length=-1};
         else if (nonnull->tag == TableInfo)
             *(Table_t*)outval = (Table_t){.entries={.length=-1}};
         else if (nonnull == &Num$info)
diff --git a/src/stdlib/optionals.h b/src/stdlib/optionals.h
index 8d25c5f1..2ffd5a50 100644
--- a/src/stdlib/optionals.h
+++ b/src/stdlib/optionals.h
@@ -10,7 +10,7 @@
 #include "types.h"
 #include "util.h"
 
-#define NONE_ARRAY ((Array_t){.length=-1})
+#define NONE_LIST ((List_t){.length=-1})
 #define NONE_BOOL ((OptionalBool_t)2)
 #define NONE_INT ((OptionalInt_t){.small=0})
 #define NONE_TABLE ((OptionalTable_t){.entries.length=-1})
@@ -24,7 +24,7 @@ PUREFUNC int32_t Optional$compare(const void *x, const void *y, const TypeInfo_t
 PUREFUNC bool Optional$equal(const void *x, const void *y, const TypeInfo_t *type);
 Text_t Optional$as_text(const void *obj, bool colorize, const TypeInfo_t *type);
 void Optional$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type);
-void Optional$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type);
+void Optional$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type);
 
 #define Optional$metamethods { \
     .hash=Optional$hash, \
diff --git a/src/stdlib/paths.c b/src/stdlib/paths.c
index 7a5346f5..cad0e0ff 100644
--- a/src/stdlib/paths.c
+++ b/src/stdlib/paths.c
@@ -17,7 +17,7 @@
 #include <unistd.h>
 #include <unistr.h>
 
-#include "arrays.h"
+#include "lists.h"
 #include "enums.h"
 #include "files.h"
 #include "integers.h"
@@ -37,16 +37,16 @@ static const Path_t HOME_PATH = {.type.$tag=PATH_HOME},
              ROOT_PATH = {.type.$tag=PATH_ABSOLUTE},
              CURDIR_PATH = {.type.$tag=PATH_RELATIVE};
 
-static void clean_components(Array_t *components)
+static void clean_components(List_t *components)
 {
     for (int64_t i = 0; i < components->length; ) {
         Text_t *component = (Text_t*)(components->data + i*components->stride);
         if (component->length == 0 || Text$equal_values(*component, Text("."))) {
-            Array$remove_at(components, I(i+1), I(1), sizeof(Text_t));
+            List$remove_at(components, I(i+1), I(1), sizeof(Text_t));
         } else if (i > 0 && Text$equal_values(*component, Text(".."))) {
             Text_t *prev = (Text_t*)(components->data + (i-1)*components->stride);
             if (!Text$equal_values(*prev, Text(".."))) {
-                Array$remove_at(components, I(i), I(2), sizeof(Text_t));
+                List$remove_at(components, I(i), I(2), sizeof(Text_t));
                 i -= 1;
             } else {
                 i += 1;
@@ -86,10 +86,10 @@ public Path_t Path$from_str(const char *str)
                        && result.components.length > 1
                        && !Text$equal_values(Text(".."), *(Text_t*)(result.components.data + result.components.stride*(result.components.length-1)))) {
                 // Pop off /foo/baz/.. -> /foo
-                Array$remove_at(&result.components, I(result.components.length), I(1), sizeof(Text_t));
+                List$remove_at(&result.components, I(result.components.length), I(1), sizeof(Text_t));
             } else { 
                 Text_t component = Text$from_strn(str, component_len);
-                Array$insert_value(&result.components, component, I(0), sizeof(Text_t));
+                List$insert_value(&result.components, component, I(0), sizeof(Text_t));
             }
             str += component_len;
         }
@@ -107,7 +107,7 @@ public Path_t Path$expand_home(Path_t path)
 {
     if (path.type.$tag == PATH_HOME) {
         Path_t pwd = Path$from_str(getenv("HOME"));
-        Array_t components = Array$concat(pwd.components, path.components, sizeof(Text_t));
+        List_t components = List$concat(pwd.components, path.components, sizeof(Text_t));
         assert(components.length == path.components.length + pwd.components.length);
         clean_components(&components);
         path = (Path_t){.type.$tag=PATH_ABSOLUTE, .components=components};
@@ -119,11 +119,11 @@ public Path_t Path$_concat(int n, Path_t items[n])
 {
     assert(n > 0);
     Path_t result = items[0];
-    ARRAY_INCREF(result.components);
+    LIST_INCREF(result.components);
     for (int i = 1; i < n; i++) {
         if (items[i].type.$tag != PATH_RELATIVE)
             fail("Cannot concatenate an absolute or home-based path onto another path: (", items[i], ")");
-        Array$insert_all(&result.components, items[i].components, I(0), sizeof(Text_t));
+        List$insert_all(&result.components, items[i].components, I(0), sizeof(Text_t));
     }
     clean_components(&result.components);
     return result;
@@ -134,8 +134,8 @@ public Path_t Path$resolved(Path_t path, Path_t relative_to)
     if (path.type.$tag == PATH_RELATIVE && !(relative_to.type.$tag == PATH_RELATIVE && relative_to.components.length == 0)) {
         Path_t result = {.type.$tag=relative_to.type.$tag};
         result.components = relative_to.components;
-        ARRAY_INCREF(result.components);
-        Array$insert_all(&result.components, path.components, I(0), sizeof(Text_t));
+        LIST_INCREF(result.components);
+        List$insert_all(&result.components, path.components, I(0), sizeof(Text_t));
         clean_components(&result.components);
         return result;
     }
@@ -157,11 +157,11 @@ public Path_t Path$relative_to(Path_t path, Path_t relative_to)
     }
 
     for (int64_t i = shared; i < relative_to.components.length; i++)
-        Array$insert_value(&result.components, Text(".."), I(1), sizeof(Text_t));
+        List$insert_value(&result.components, Text(".."), I(1), sizeof(Text_t));
 
     for (int64_t i = shared; i < path.components.length; i++) {
         Text_t *p = (Text_t*)(path.components.data + i*path.components.stride);
-        Array$insert(&result.components, p, I(0), sizeof(Text_t));
+        List$insert(&result.components, p, I(0), sizeof(Text_t));
     }
     //clean_components(&result.components);
     return result;
@@ -278,7 +278,7 @@ public OptionalInt64_t Path$changed(Path_t path, bool follow_symlinks)
     return (OptionalInt64_t){.value=(int64_t)sb.st_ctime};
 }
 
-static void _write(Path_t path, Array_t bytes, int mode, int permissions)
+static void _write(Path_t path, List_t bytes, int mode, int permissions)
 {
     path = Path$expand_home(path);
     const char *path_str = Path$as_c_string(path);
@@ -287,7 +287,7 @@ static void _write(Path_t path, Array_t bytes, int mode, int permissions)
         fail("Could not write to file: ", path_str, "\n", strerror(errno));
 
     if (bytes.stride != 1)
-        Array$compact(&bytes, 1);
+        List$compact(&bytes, 1);
     ssize_t written = write(fd, bytes.data, (size_t)bytes.length);
     if (written != (ssize_t)bytes.length)
         fail("Could not write to file: ", path_str, "\n", strerror(errno));
@@ -296,36 +296,36 @@ static void _write(Path_t path, Array_t bytes, int mode, int permissions)
 
 public void Path$write(Path_t path, Text_t text, int permissions)
 {
-    Array_t bytes = Text$utf8_bytes(text);
+    List_t bytes = Text$utf8_bytes(text);
     _write(path, bytes, O_WRONLY | O_CREAT | O_TRUNC, permissions);
 }
 
-public void Path$write_bytes(Path_t path, Array_t bytes, int permissions)
+public void Path$write_bytes(Path_t path, List_t bytes, int permissions)
 {
     _write(path, bytes, O_WRONLY | O_CREAT | O_TRUNC, permissions);
 }
 
 public void Path$append(Path_t path, Text_t text, int permissions)
 {
-    Array_t bytes = Text$utf8_bytes(text);
+    List_t bytes = Text$utf8_bytes(text);
     _write(path, bytes, O_WRONLY | O_APPEND | O_CREAT, permissions);
 }
 
-public void Path$append_bytes(Path_t path, Array_t bytes, int permissions)
+public void Path$append_bytes(Path_t path, List_t bytes, int permissions)
 {
     _write(path, bytes, O_WRONLY | O_APPEND | O_CREAT, permissions);
 }
 
-public OptionalArray_t Path$read_bytes(Path_t path, OptionalInt_t count)
+public OptionalList_t Path$read_bytes(Path_t path, OptionalInt_t count)
 {
     path = Path$expand_home(path);
     int fd = open(Path$as_c_string(path), O_RDONLY);
     if (fd == -1)
-        return NONE_ARRAY;
+        return NONE_LIST;
 
     struct stat sb;
     if (fstat(fd, &sb) != 0)
-        return NONE_ARRAY;
+        return NONE_LIST;
 
     int64_t const target_count = count.small ? Int64$from_int(count, false) : INT64_MAX;
     if (target_count < 0)
@@ -340,7 +340,7 @@ public OptionalArray_t Path$read_bytes(Path_t path, OptionalInt_t count)
         if (count.small && (int64_t)sb.st_size < target_count)
             fail("Could not read ", target_count, " bytes from ", path, " (only got ", (uint64_t)sb.st_size, ")");
         int64_t len = count.small ? target_count : (int64_t)sb.st_size;
-        return (Array_t){.data=content, .atomic=1, .stride=1, .length=len};
+        return (List_t){.data=content, .atomic=1, .stride=1, .length=len};
     } else {
         size_t capacity = 256, len = 0;
         char *content = GC_MALLOC_ATOMIC(capacity);
@@ -351,7 +351,7 @@ public OptionalArray_t Path$read_bytes(Path_t path, OptionalInt_t count)
             ssize_t just_read = read(fd, chunk, to_read);
             if (just_read < 0) {
                 close(fd);
-                return NONE_ARRAY;
+                return NONE_LIST;
             } else if (just_read == 0) {
                 if (errno == EAGAIN || errno == EINTR)
                     continue;
@@ -369,13 +369,13 @@ public OptionalArray_t Path$read_bytes(Path_t path, OptionalInt_t count)
         close(fd);
         if (count.small != 0 && (int64_t)len < target_count)
             fail("Could not read ", target_count, " bytes from ", path, " (only got ", (uint64_t)len, ")");
-        return (Array_t){.data=content, .atomic=1, .stride=1, .length=len};
+        return (List_t){.data=content, .atomic=1, .stride=1, .length=len};
     }
 }
 
 public OptionalText_t Path$read(Path_t path)
 {
-    Array_t bytes = Path$read_bytes(path, NONE_INT);
+    List_t bytes = Path$read_bytes(path, NONE_INT);
     if (bytes.length < 0) return NONE_TEXT;
     return Text$from_bytes(bytes);
 }
@@ -471,11 +471,11 @@ public void Path$create_directory(Path_t path, int permissions)
         fail("Could not create directory: ", c_path, " (", strerror(errno), ")");
 }
 
-static Array_t _filtered_children(Path_t path, bool include_hidden, mode_t filter)
+static List_t _filtered_children(Path_t path, bool include_hidden, mode_t filter)
 {
     path = Path$expand_home(path);
     struct dirent *dir;
-    Array_t children = {};
+    List_t children = {};
     const char *path_str = Path$as_c_string(path);
     size_t path_len = strlen(path_str);
     DIR *d = opendir(path_str);
@@ -499,23 +499,23 @@ static Array_t _filtered_children(Path_t path, bool include_hidden, mode_t filte
             continue;
 
         Path_t child = Path$from_str(child_str);
-        Array$insert(&children, &child, I(0), sizeof(Path_t));
+        List$insert(&children, &child, I(0), sizeof(Path_t));
     }
     closedir(d);
     return children;
 }
 
-public Array_t Path$children(Path_t path, bool include_hidden)
+public List_t Path$children(Path_t path, bool include_hidden)
 {
     return _filtered_children(path, include_hidden, (mode_t)-1);
 }
 
-public Array_t Path$files(Path_t path, bool include_hidden)
+public List_t Path$files(Path_t path, bool include_hidden)
 {
     return _filtered_children(path, include_hidden, S_IFREG);
 }
 
-public Array_t Path$subdirectories(Path_t path, bool include_hidden)
+public List_t Path$subdirectories(Path_t path, bool include_hidden)
 {
     return _filtered_children(path, include_hidden, S_IFDIR);
 }
@@ -535,7 +535,7 @@ public Path_t Path$unique_directory(Path_t path)
     return Path$from_str(created);
 }
 
-public Path_t Path$write_unique_bytes(Path_t path, Array_t bytes)
+public Path_t Path$write_unique_bytes(Path_t path, List_t bytes)
 {
     path = Path$expand_home(path);
     const char *path_str = Path$as_c_string(path);
@@ -555,7 +555,7 @@ public Path_t Path$write_unique_bytes(Path_t path, Array_t bytes)
         fail("Could not write to unique file: ", buf, "\n", strerror(errno));
 
     if (bytes.stride != 1)
-        Array$compact(&bytes, 1);
+        List$compact(&bytes, 1);
 
     ssize_t written = write(fd, bytes.data, (size_t)bytes.length);
     if (written != (ssize_t)bytes.length)
@@ -575,11 +575,11 @@ public Path_t Path$parent(Path_t path)
         return path;
     } else if (path.components.length > 0 && !Text$equal_values(*(Text_t*)(path.components.data + path.components.stride*(path.components.length-1)),
                                                          Text(".."))) {
-        return (Path_t){.type.$tag=path.type.$tag, .components=Array$slice(path.components, I(1), I(-2))};
+        return (Path_t){.type.$tag=path.type.$tag, .components=List$slice(path.components, I(1), I(-2))};
     } else {
         Path_t result = {.type.$tag=path.type.$tag, .components=path.components};
-        ARRAY_INCREF(result.components);
-        Array$insert_value(&result.components, Text(".."), I(0), sizeof(Text_t));
+        LIST_INCREF(result.components);
+        List$insert_value(&result.components, Text(".."), I(0), sizeof(Text_t));
         return result;
     }
 }
@@ -610,8 +610,8 @@ public Path_t Path$with_component(Path_t path, Text_t component)
         .type.$tag=path.type.$tag,
         .components=path.components,
     };
-    ARRAY_INCREF(result.components);
-    Array$insert(&result.components, &component, I(0), sizeof(Text_t));
+    LIST_INCREF(result.components);
+    List$insert(&result.components, &component, I(0), sizeof(Text_t));
     clean_components(&result.components);
     return result;
 }
@@ -625,9 +625,9 @@ public Path_t Path$with_extension(Path_t path, Text_t extension, bool replace)
         .type.$tag=path.type.$tag,
         .components=path.components,
     };
-    ARRAY_INCREF(result.components);
+    LIST_INCREF(result.components);
     Text_t last = *(Text_t*)(path.components.data + path.components.stride*(path.components.length-1));
-    Array$remove_at(&result.components, I(-1), I(1), sizeof(Text_t));
+    List$remove_at(&result.components, I(-1), I(1), sizeof(Text_t));
     if (replace) {
         const char *base = Text$as_c_string(last);
         const char *dot = strchr(base + 1, '.');
@@ -636,7 +636,7 @@ public Path_t Path$with_extension(Path_t path, Text_t extension, bool replace)
     }
 
     last = Text$concat(last, extension);
-    Array$insert(&result.components, &last, I(0), sizeof(Text_t));
+    List$insert(&result.components, &last, I(0), sizeof(Text_t));
     return result;
 }
 
@@ -685,21 +685,21 @@ public OptionalClosure_t Path$by_line(Path_t path)
     return (Closure_t){.fn=(void*)_next_line, .userdata=wrapper};
 }
 
-public Array_t Path$glob(Path_t path)
+public List_t Path$glob(Path_t path)
 {
     glob_t glob_result;
     int status = glob(Path$as_c_string(path), GLOB_BRACE | GLOB_TILDE, NULL, &glob_result);
     if (status != 0 && status != GLOB_NOMATCH)
         fail("Failed to perform globbing");
 
-    Array_t glob_files = {};
+    List_t glob_files = {};
     for (size_t i = 0; i < glob_result.gl_pathc; i++) {
         size_t len = strlen(glob_result.gl_pathv[i]);
         if ((len >= 2 && glob_result.gl_pathv[i][len-1] == '.' && glob_result.gl_pathv[i][len-2] == '/')
             || (len >= 2 && glob_result.gl_pathv[i][len-1] == '.' && glob_result.gl_pathv[i][len-2] == '.' && glob_result.gl_pathv[i][len-3] == '/'))
             continue;
         Path_t p = Path$from_str(glob_result.gl_pathv[i]);
-        Array$insert(&glob_files, &p, I(0), sizeof(Path_t));
+        List$insert(&glob_files, &p, I(0), sizeof(Path_t));
     }
     return glob_files;
 }
@@ -730,7 +730,7 @@ public PUREFUNC int32_t Path$compare(const void *va, const void *vb, const TypeI
     Path_t *a = (Path_t*)va, *b = (Path_t*)vb;
     int diff = ((int)a->type.$tag - (int)b->type.$tag);
     if (diff != 0) return diff;
-    return Array$compare(&a->components, &b->components, Array$info(&Text$info));
+    return List$compare(&a->components, &b->components, List$info(&Text$info));
 }
 
 public PUREFUNC bool Path$equal(const void *va, const void *vb, const TypeInfo_t *type)
@@ -738,13 +738,13 @@ public PUREFUNC bool Path$equal(const void *va, const void *vb, const TypeInfo_t
     (void)type;
     Path_t *a = (Path_t*)va, *b = (Path_t*)vb;
     if (a->type.$tag != b->type.$tag) return false;
-    return Array$equal(&a->components, &b->components, Array$info(&Text$info));
+    return List$equal(&a->components, &b->components, List$info(&Text$info));
 }
 
 public PUREFUNC bool Path$equal_values(Path_t a, Path_t b)
 {
     if (a.type.$tag != b.type.$tag) return false;
-    return Array$equal(&a.components, &b.components, Array$info(&Text$info));
+    return List$equal(&a.components, &b.components, List$info(&Text$info));
 }
 
 public int Path$print(FILE *f, Path_t path)
@@ -809,15 +809,15 @@ public void Path$serialize(const void *obj, FILE *out, Table_t *pointers, const
     (void)type;
     Path_t *path = (Path_t*)obj;
     fputc((int)path->type.$tag, out);
-    Array$serialize(&path->components, out, pointers, Array$info(&Text$info));
+    List$serialize(&path->components, out, pointers, List$info(&Text$info));
 }
 
-public void Path$deserialize(FILE *in, void *obj, Array_t *pointers, const TypeInfo_t *type)
+public void Path$deserialize(FILE *in, void *obj, List_t *pointers, const TypeInfo_t *type)
 {
     (void)type;
     Path_t path = {};
     path.type.$tag = fgetc(in);
-    Array$deserialize(in, &path.components, pointers, Array$info(&Text$info));
+    List$deserialize(in, &path.components, pointers, List$info(&Text$info));
     *(Path_t*)obj = path;
 }
 
diff --git a/src/stdlib/paths.h b/src/stdlib/paths.h
index 9be81bdf..31d676b7 100644
--- a/src/stdlib/paths.h
+++ b/src/stdlib/paths.h
@@ -32,22 +32,22 @@ OptionalInt64_t Path$modified(Path_t path, bool follow_symlinks);
 OptionalInt64_t Path$accessed(Path_t path, bool follow_symlinks);
 OptionalInt64_t Path$changed(Path_t path, bool follow_symlinks);
 void Path$write(Path_t path, Text_t text, int permissions);
-void Path$write_bytes(Path_t path, Array_t bytes, int permissions);
+void Path$write_bytes(Path_t path, List_t bytes, int permissions);
 void Path$append(Path_t path, Text_t text, int permissions);
-void Path$append_bytes(Path_t path, Array_t bytes, int permissions);
+void Path$append_bytes(Path_t path, List_t bytes, int permissions);
 OptionalText_t Path$read(Path_t path);
-OptionalArray_t Path$read_bytes(Path_t path, OptionalInt_t limit);
+OptionalList_t Path$read_bytes(Path_t path, OptionalInt_t limit);
 void Path$set_owner(Path_t path, OptionalText_t owner, OptionalText_t group, bool follow_symlinks);
 OptionalText_t Path$owner(Path_t path, bool follow_symlinks);
 OptionalText_t Path$group(Path_t path, bool follow_symlinks);
 void Path$remove(Path_t path, bool ignore_missing);
 void Path$create_directory(Path_t path, int permissions);
-Array_t Path$children(Path_t path, bool include_hidden);
-Array_t Path$files(Path_t path, bool include_hidden);
-Array_t Path$subdirectories(Path_t path, bool include_hidden);
+List_t Path$children(Path_t path, bool include_hidden);
+List_t Path$files(Path_t path, bool include_hidden);
+List_t Path$subdirectories(Path_t path, bool include_hidden);
 Path_t Path$unique_directory(Path_t path);
 Path_t Path$write_unique(Path_t path, Text_t text);
-Path_t Path$write_unique_bytes(Path_t path, Array_t bytes);
+Path_t Path$write_unique_bytes(Path_t path, List_t bytes);
 Path_t Path$parent(Path_t path);
 Text_t Path$base_name(Path_t path);
 Text_t Path$extension(Path_t path, bool full);
@@ -55,7 +55,7 @@ Path_t Path$with_component(Path_t path, Text_t component);
 Path_t Path$with_extension(Path_t path, Text_t extension, bool replace);
 Path_t Path$current_dir(void);
 Closure_t Path$by_line(Path_t path);
-Array_t Path$glob(Path_t path);
+List_t Path$glob(Path_t path);
 
 uint64_t Path$hash(const void *obj, const TypeInfo_t*);
 int32_t Path$compare(const void *a, const void *b, const TypeInfo_t *type);
@@ -64,7 +64,7 @@ bool Path$equal_values(Path_t a, Path_t b);
 Text_t Path$as_text(const void *obj, bool color, const TypeInfo_t *type);
 bool Path$is_none(const void *obj, const TypeInfo_t *type);
 void Path$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type);
-void Path$deserialize(FILE *in, void *obj, Array_t *pointers, const TypeInfo_t *type);
+void Path$deserialize(FILE *in, void *obj, List_t *pointers, const TypeInfo_t *type);
 
 extern const TypeInfo_t Path$info;
 extern const TypeInfo_t PathType$info;
diff --git a/src/stdlib/pointers.c b/src/stdlib/pointers.c
index 76e882ec..b674ac6f 100644
--- a/src/stdlib/pointers.c
+++ b/src/stdlib/pointers.c
@@ -104,7 +104,7 @@ public void Pointer$serialize(const void *obj, FILE *out, Table_t *pointers, con
         _serialize(ptr, out, pointers, type->PointerInfo.pointed);
 }
 
-public void Pointer$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type)
+public void Pointer$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type)
 {
     int64_t id = 0;
     Int64$deserialize(in, &id, pointers, &Int64$info);
@@ -112,7 +112,7 @@ public void Pointer$deserialize(FILE *in, void *outval, Array_t *pointers, const
 
     if (id > pointers->length) {
         void *obj = GC_MALLOC((size_t)type->PointerInfo.pointed->size);
-        Array$insert(pointers, &obj, I(0), sizeof(void*));
+        List$insert(pointers, &obj, I(0), sizeof(void*));
         _deserialize(in, obj, pointers, type->PointerInfo.pointed);
         *(void**)outval = obj;
     } else {
diff --git a/src/stdlib/pointers.h b/src/stdlib/pointers.h
index 165a5184..b818452e 100644
--- a/src/stdlib/pointers.h
+++ b/src/stdlib/pointers.h
@@ -14,7 +14,7 @@ PUREFUNC int32_t Pointer$compare(const void *x, const void *y, const TypeInfo_t
 PUREFUNC bool Pointer$equal(const void *x, const void *y, const TypeInfo_t *type);
 PUREFUNC bool Pointer$is_none(const void *x, const TypeInfo_t*);
 void Pointer$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type);
-void Pointer$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type);
+void Pointer$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type);
 
 #define Null(t) (t*)NULL
 #define POINTER_TYPE(_sigil, _pointed) (&(TypeInfo_t){\
diff --git a/src/stdlib/stdlib.c b/src/stdlib/stdlib.c
index 8d3a8081..e8cfe06a 100644
--- a/src/stdlib/stdlib.c
+++ b/src/stdlib/stdlib.c
@@ -158,8 +158,8 @@ static bool parse_single_arg(const TypeInfo_t *info, char *arg, void *dest)
 
         Text_t t = generic_as_text(NULL, false, info);
         print_err("Unsupported multi-argument struct type for argument parsing: ", t);
-    } else if (info->tag == ArrayInfo) {
-        print_err("Array arguments must be specified as `--flag ...` not `--flag=...`");
+    } else if (info->tag == ListInfo) {
+        print_err("List arguments must be specified as `--flag ...` not `--flag=...`");
     } else if (info->tag == TableInfo) {
         print_err("Table arguments must be specified as `--flag ...` not `--flag=...`");
     } else {
@@ -168,13 +168,13 @@ static bool parse_single_arg(const TypeInfo_t *info, char *arg, void *dest)
     }
 }
 
-static Array_t parse_array(const TypeInfo_t *item_info, int n, char *args[])
+static List_t parse_list(const TypeInfo_t *item_info, int n, char *args[])
 {
     int64_t padded_size = item_info->size;
     if ((padded_size % item_info->align) > 0)
         padded_size = padded_size + item_info->align - (padded_size % item_info->align);
 
-    Array_t items = {
+    List_t items = {
         .stride=padded_size,
         .length=n,
         .data=GC_MALLOC((size_t)(padded_size*n)),
@@ -199,7 +199,7 @@ static Table_t parse_table(const TypeInfo_t *table, int n, char *args[])
     if ((padded_size % key->align) > 0)
         padded_size = padded_size + key->align - (padded_size % key->align);
 
-    Array_t entries = {
+    List_t entries = {
         .stride=padded_size,
         .length=n,
         .data=GC_MALLOC((size_t)(padded_size*n)),
@@ -262,7 +262,7 @@ public void _tomo_parse_args(int argc, char *argv[], Text_t usage, Text_t help,
                 char after_name = argv[i][2+strlen(spec[s].name)];
                 if (after_name == '\0') { // --foo val
                     used_args[i] = true;
-                    if (non_opt_type->tag == ArrayInfo) {
+                    if (non_opt_type->tag == ListInfo) {
                         int num_args = 0;
                         while (i + 1 + num_args < argc) {
                             if (argv[i+1+num_args][0] == '-')
@@ -271,7 +271,7 @@ public void _tomo_parse_args(int argc, char *argv[], Text_t usage, Text_t help,
                             num_args += 1;
                         }
                         populated_args[s] = true;
-                        *(OptionalArray_t*)spec[s].dest = parse_array(non_opt_type->ArrayInfo.item, num_args, &argv[i+1]);
+                        *(OptionalList_t*)spec[s].dest = parse_list(non_opt_type->ListInfo.item, num_args, &argv[i+1]);
                     } else if (non_opt_type->tag == TableInfo) {
                         int num_args = 0;
                         while (i + 1 + num_args < argc) {
@@ -322,7 +322,7 @@ public void _tomo_parse_args(int argc, char *argv[], Text_t usage, Text_t help,
                     while (non_opt_type->tag == OptionalInfo)
                         non_opt_type = non_opt_type->OptionalInfo.type;
 
-                    if (non_opt_type->tag == ArrayInfo) {
+                    if (non_opt_type->tag == ListInfo) {
                         if (f[1]) print_err("No value provided for ", flag, "\n", usage);
                         int num_args = 0;
                         while (i + 1 + num_args < argc) {
@@ -332,7 +332,7 @@ public void _tomo_parse_args(int argc, char *argv[], Text_t usage, Text_t help,
                             num_args += 1;
                         }
                         populated_args[s] = true;
-                        *(OptionalArray_t*)spec[s].dest = parse_array(non_opt_type->ArrayInfo.item, num_args, &argv[i+1]);
+                        *(OptionalList_t*)spec[s].dest = parse_list(non_opt_type->ListInfo.item, num_args, &argv[i+1]);
                     } else if (non_opt_type->tag == TableInfo) {
                         int num_args = 0;
                         while (i + 1 + num_args < argc) {
@@ -398,7 +398,7 @@ public void _tomo_parse_args(int argc, char *argv[], Text_t usage, Text_t help,
         if (non_opt_type == &Bool$info)
             goto next_non_bool_flag;
 
-        if (non_opt_type->tag == ArrayInfo) {
+        if (non_opt_type->tag == ListInfo) {
             int num_args = 0;
             while (i + num_args < argc) {
                 if (!ignore_dashes && argv[i+num_args][0] == '-')
@@ -407,7 +407,7 @@ public void _tomo_parse_args(int argc, char *argv[], Text_t usage, Text_t help,
                 num_args += 1;
             }
             populated_args[s] = true;
-            *(OptionalArray_t*)spec[s].dest = parse_array(non_opt_type->ArrayInfo.item, num_args, &argv[i]);
+            *(OptionalList_t*)spec[s].dest = parse_list(non_opt_type->ListInfo.item, num_args, &argv[i]);
         } else if (non_opt_type->tag == TableInfo) {
             int num_args = 0;
             while (i + num_args < argc) {
@@ -428,8 +428,8 @@ public void _tomo_parse_args(int argc, char *argv[], Text_t usage, Text_t help,
 
     for (int s = 0; s < spec_len; s++) {
         if (!populated_args[s] && spec[s].required) {
-            if (spec[s].type->tag == ArrayInfo)
-                *(OptionalArray_t*)spec[s].dest = (Array_t){};
+            if (spec[s].type->tag == ListInfo)
+                *(OptionalList_t*)spec[s].dest = (List_t){};
             else if (spec[s].type->tag == TableInfo)
                 *(OptionalTable_t*)spec[s].dest = (Table_t){};
             else
diff --git a/src/stdlib/structs.c b/src/stdlib/structs.c
index 53b0e0a4..9a14779e 100644
--- a/src/stdlib/structs.c
+++ b/src/stdlib/structs.c
@@ -3,7 +3,7 @@
 #include <stdint.h>
 #include <string.h>
 
-#include "arrays.h"
+#include "lists.h"
 #include "bools.h"
 #include "functiontype.h"
 #include "metamethods.h"
@@ -211,7 +211,7 @@ public void Struct$serialize(const void *obj, FILE *out, Table_t *pointers, cons
     }
 }
 
-public void Struct$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type)
+public void Struct$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type)
 {
     ptrdiff_t byte_offset = 0;
     ptrdiff_t bit_offset = 0;
diff --git a/src/stdlib/structs.h b/src/stdlib/structs.h
index bab702cd..c9c6c40a 100644
--- a/src/stdlib/structs.h
+++ b/src/stdlib/structs.h
@@ -15,7 +15,7 @@ PUREFUNC bool PackedData$equal(const void *x, const void *y, const TypeInfo_t *t
 PUREFUNC Text_t Struct$as_text(const void *obj, bool colorize, const TypeInfo_t *type);
 PUREFUNC bool Struct$is_none(const void *obj, const TypeInfo_t *type);
 void Struct$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type);
-void Struct$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type);
+void Struct$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type);
 
 #define Struct$metamethods { \
     .hash=Struct$hash, \
diff --git a/src/stdlib/tables.c b/src/stdlib/tables.c
index d59bc113..3cb2e742 100644
--- a/src/stdlib/tables.c
+++ b/src/stdlib/tables.c
@@ -16,7 +16,7 @@
 #include <string.h>
 #include <sys/param.h>
 
-#include "arrays.h"
+#include "lists.h"
 #include "c_strings.h"
 #include "datatypes.h"
 #include "memory.h"
@@ -97,7 +97,7 @@ static INLINE void hshow(const Table_t *t)
 static void maybe_copy_on_write(Table_t *t, const TypeInfo_t *type)
 {
     if (t->entries.data_refcount != 0)
-        Array$compact(&t->entries, (int64_t)entry_size(type));
+        List$compact(&t->entries, (int64_t)entry_size(type));
 
     if (t->bucket_info && t->bucket_info->data_refcount != 0) {
         size_t size = sizeof(bucket_info_t) + sizeof(bucket_t[t->bucket_info->count]);
@@ -273,7 +273,7 @@ public void *Table$reserve(Table_t *t, const void *key, const void *value, const
         memcpy(buf + value_offset(type), value, (size_t)value_size);
     else
         memset(buf + value_offset(type), 0, (size_t)value_size);
-    Array$insert(&t->entries, buf, I(0), (int64_t)entry_size(type));
+    List$insert(&t->entries, buf, I(0), (int64_t)entry_size(type));
 
     int64_t entry_index = t->entries.length-1;
     void *entry = GET_ENTRY(*t, entry_index);
@@ -343,7 +343,7 @@ public void Table$remove(Table_t *t, const void *key, const TypeInfo_t *type)
     // instead of O(N)
     int64_t last_entry = t->entries.length-1;
     if (bucket->index != last_entry) {
-        hdebug("Removing key/value from the middle of the entries array\n");
+        hdebug("Removing key/value from the middle of the entries list\n");
 
         // Find the bucket that points to the last entry's index:
         uint64_t i = HASH_KEY(*t, GET_ENTRY(*t, last_entry));
@@ -353,7 +353,7 @@ public void Table$remove(Table_t *t, const void *key, const TypeInfo_t *type)
         // where the removed entry currently sits):
         t->bucket_info->buckets[i].index = bucket->index;
 
-        // Clobber the entry being removed (in the middle of the array) with
+        // Clobber the entry being removed (in the middle of the list) with
         // the last entry:
         memcpy(GET_ENTRY(*t, bucket->index), GET_ENTRY(*t, last_entry), entry_size(type));
     }
@@ -361,7 +361,7 @@ public void Table$remove(Table_t *t, const void *key, const TypeInfo_t *type)
     // Last entry is being removed, so clear it out to be safe:
     memset(GET_ENTRY(*t, last_entry), 0, entry_size(type));
 
-    Array$remove_at(&t->entries, I(t->entries.length), I(1), (int64_t)entry_size(type));
+    List$remove_at(&t->entries, I(t->entries.length), I(1), (int64_t)entry_size(type));
 
     int64_t bucket_to_clear;
     if (prev) { // Middle (or end) of a chain
@@ -399,7 +399,7 @@ public void Table$clear(Table_t *t)
 public Table_t Table$sorted(Table_t t, const TypeInfo_t *type)
 {
     Closure_t cmp = (Closure_t){.fn=generic_compare, .userdata=(void*)type->TableInfo.key};
-    Array_t entries = Array$sorted(t.entries, cmp, (int64_t)entry_size(type));
+    List_t entries = List$sorted(t.entries, cmp, (int64_t)entry_size(type));
     return Table$from_entries(entries, type);
 }
 
@@ -445,10 +445,10 @@ PUREFUNC public int32_t Table$compare(const void *vx, const void *vy, const Type
 
     // Table comparison rules:
     // - If two tables have different keys, then compare as if comparing a
-    // sorted array of the keys of the two tables:
+    // sorted list of the keys of the two tables:
     //    `x.keys.sorted() <> y.keys.sorted()`
-    // - Otherwise, compare as if comparing arrays of values for the sorted key
-    // arrays:
+    // - Otherwise, compare as if comparing lists of values for the sorted key
+    // lists:
     //    `[x[k] for k in x.keys.sorted()] <> [y[k] for k in y.keys.sorted()]`
     // 
     // We can do this in _linear_ time if we find the smallest `k` such that
@@ -612,7 +612,7 @@ public Text_t Table$as_text(const void *obj, bool colorize, const TypeInfo_t *ty
     return text;
 }
 
-public Table_t Table$from_entries(Array_t entries, const TypeInfo_t *type)
+public Table_t Table$from_entries(List_t entries, const TypeInfo_t *type)
 {
     assert(type->tag == TableInfo);
     if (entries.length == 0)
@@ -776,7 +776,7 @@ public void Table$serialize(const void *obj, FILE *out, Table_t *pointers, const
 #pragma GCC diagnostic push
 #pragma GCC diagnostic ignored "-Wstack-protector"
 #endif
-public void Table$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type)
+public void Table$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type)
 {
     int64_t len;
     Int64$deserialize(in, &len, pointers, &Int$info);
diff --git a/src/stdlib/tables.h b/src/stdlib/tables.h
index 979da5e7..35673eaf 100644
--- a/src/stdlib/tables.h
+++ b/src/stdlib/tables.h
@@ -6,14 +6,14 @@
 #include <stdbool.h>
 #include <string.h>
 
-#include "arrays.h"
+#include "lists.h"
 #include "datatypes.h"
 #include "types.h"
 #include "util.h"
 
 #define Table(key_t, val_t, key_info, value_info, fb, N, ...)  ({ \
     struct { key_t k; val_t v; } ents[N] = {__VA_ARGS__}; \
-    Table_t table = Table$from_entries((Array_t){ \
+    Table_t table = Table$from_entries((List_t){ \
                        .data=memcpy(GC_MALLOC(sizeof(ents)), ents, sizeof(ents)), \
                        .length=sizeof(ents)/sizeof(ents[0]), \
                        .stride=(void*)&ents[1] - (void*)&ents[0], \
@@ -22,14 +22,14 @@
     table; })
 #define Set(item_t, item_info, N, ...)  ({ \
     item_t ents[N] = {__VA_ARGS__}; \
-    Table_t set = Table$from_entries((Array_t){ \
+    Table_t set = Table$from_entries((List_t){ \
                        .data=memcpy(GC_MALLOC(sizeof(ents)), ents, sizeof(ents)), \
                        .length=sizeof(ents)/sizeof(ents[0]), \
                        .stride=(void*)&ents[1] - (void*)&ents[0], \
                        }, Set$info(item_info)); \
     set; })
 
-Table_t Table$from_entries(Array_t entries, const TypeInfo_t *type);
+Table_t Table$from_entries(List_t entries, const TypeInfo_t *type);
 void *Table$get(Table_t t, const void *key, const TypeInfo_t *type);
 #define Table$get_optional(table_expr, key_t, val_t, key_expr, nonnull_var, nonnull_expr, null_expr, info_expr) ({ \
     const Table_t t = table_expr; const key_t k = key_expr; \
@@ -71,7 +71,7 @@ PUREFUNC bool Table$is_superset_of(Table_t a, Table_t b, bool strict, const Type
 void Table$clear(Table_t *t);
 Table_t Table$sorted(Table_t t, const TypeInfo_t *type);
 void Table$mark_copy_on_write(Table_t *t);
-#define TABLE_INCREF(t) ({ ARRAY_INCREF((t).entries); if ((t).bucket_info) (t).bucket_info->data_refcount += ((t).bucket_info->data_refcount < TABLE_MAX_DATA_REFCOUNT); })
+#define TABLE_INCREF(t) ({ LIST_INCREF((t).entries); if ((t).bucket_info) (t).bucket_info->data_refcount += ((t).bucket_info->data_refcount < TABLE_MAX_DATA_REFCOUNT); })
 #define TABLE_COPY(t) ({ TABLE_INCREF(t); t; })
 PUREFUNC int32_t Table$compare(const void *x, const void *y, const TypeInfo_t *type);
 PUREFUNC bool Table$equal(const void *x, const void *y, const TypeInfo_t *type);
@@ -86,7 +86,7 @@ void Table$str_set(Table_t *t, const char *key, const void *value);
 void *Table$str_reserve(Table_t *t, const char *key, const void *value);
 void Table$str_remove(Table_t *t, const char *key);
 void Table$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type);
-void Table$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type);
+void Table$deserialize(FILE *in, void *outval, List_t *pointers, const TypeInfo_t *type);
 
 #define Table$length(t) ((t).entries.length)
 
diff --git a/src/stdlib/text.c b/src/stdlib/text.c
index b3e9cebb..3346bf4b 100644
--- a/src/stdlib/text.c
+++ b/src/stdlib/text.c
@@ -27,7 +27,7 @@
 // is basically what Zalgo text is).
 //
 // There are a lot of benefits to storing unicode text with one grapheme
-// cluster per index in a densely packed array instead of storing the text as
+// cluster per index in a densely packed list instead of storing the text as
 // variable-width UTF8-encoded bytes. It lets us have one canonical length for
 // the text that can be precomputed and is meaningful to users. It lets us
 // quickly get the Nth "letter" in the text. Substring slicing is fast.
@@ -38,7 +38,7 @@
 // Graphemes, aka NFG). A synthetic grapheme is a negative 32-bit signed
 // integer that represents a multi-codepoint grapheme cluster that has been
 // encountered during the program's runtime. These clusters are stored in a
-// lookup array and hash map so that we can rapidly convert between the
+// lookup list and hash map so that we can rapidly convert between the
 // synthetic grapheme integer ID and the unicode codepoints associated with it.
 // Essentially, it's like we create a supplement to the unicode standard with
 // things that would be nice if they had their own codepoint so things worked
@@ -49,7 +49,7 @@
 // WITH ACUTE This would be stored as: (int32_t[]){0x48, 0xE9} Example 2:
 // U+0048, U+0065, U+0309 AKA: LATIN CAPITAL LETTER H, LATIN SMALL LETTER E,
 // COMBINING VERTICAL LINE BELOW This would be stored as: (int32_t[]){0x48, -2}
-// Where -2 is used as a lookup in an array that holds the actual unicode
+// Where -2 is used as a lookup in a list that holds the actual unicode
 // codepoints: (ucs4_t[]){0x65, 0x0309}
 
 #include <assert.h>
@@ -68,7 +68,7 @@
 #include <unistring/version.h>
 #include <uniwidth.h>
 
-#include "arrays.h"
+#include "lists.h"
 #include "integers.h"
 #include "tables.h"
 #include "text.h"
@@ -86,7 +86,7 @@ typedef struct {
 // Synthetic grapheme clusters (clusters of more than one codepoint):
 static Table_t grapheme_ids_by_codepoints = {}; // ucs4_t* length-prefixed codepoints -> int32_t ID
 
-// This will hold a dynamically growing array of synthetic graphemes:
+// This will hold a dynamically growing list of synthetic graphemes:
 static synthetic_grapheme_t *synthetic_graphemes = NULL;
 static int32_t synthetic_grapheme_capacity = 0;
 static int32_t num_synthetic_graphemes = 0;
@@ -733,7 +733,7 @@ Text_t text_from_u32(ucs4_t *codepoints, int64_t num_codepoints, bool normalize)
 
     // Intentionally overallocate here: allocate assuming each codepoint is a
     // grapheme cluster. If that's not true, we'll have extra space at the end
-    // of the array, but the length will still be calculated correctly.
+    // of the list, but the length will still be calculated correctly.
     int32_t *graphemes = GC_MALLOC_ATOMIC(sizeof(int32_t[num_codepoints]));
     struct Text_s ret = {
         .tag=TEXT_GRAPHEMES,
@@ -1067,10 +1067,10 @@ public Text_t Text$translate(Text_t text, Table_t translations)
     TextIter_t text_state = NEW_TEXT_ITER_STATE(text);
     Text_t result = EMPTY_TEXT;
     int64_t span_start = 0;
-    Array_t replacement_array = translations.entries;
+    List_t replacement_list = translations.entries;
     for (int64_t i = 0; i < text.length; ) {
-        for (int64_t r = 0; r < replacement_array.length; r++) {
-            struct { Text_t target, replacement; } *entry = replacement_array.data + r*replacement_array.stride;
+        for (int64_t r = 0; r < replacement_list.length; r++) {
+            struct { Text_t target, replacement; } *entry = replacement_list.data + r*replacement_list.stride;
             TextIter_t target_state = NEW_TEXT_ITER_STATE(entry->target);
             if (_matches(&text_state, &target_state, i)) {
                 if (i > span_start)
@@ -1122,36 +1122,36 @@ public bool Text$has(Text_t text, Text_t target)
     return false;
 }
 
-public Array_t Text$split(Text_t text, Text_t delimiters)
+public List_t Text$split(Text_t text, Text_t delimiters)
 {
     if (delimiters.length == 0)
         return Text$clusters(text);
 
     TextIter_t text_state = NEW_TEXT_ITER_STATE(text), delim_state = NEW_TEXT_ITER_STATE(delimiters);
-    Array_t splits = {};
+    List_t splits = {};
     for (int64_t i = 0; i < text.length; ) {
         int64_t span_len = 0;
         while (i + span_len < text.length && !_matches(&text_state, &delim_state, i + span_len)) {
             span_len += 1;
         }
         Text_t slice = Text$slice(text, I(i+1), I(i+span_len));
-        Array$insert(&splits, &slice, I(0), sizeof(slice));
+        List$insert(&splits, &slice, I(0), sizeof(slice));
         i += span_len + delimiters.length;
         if (i == text.length) {
             Text_t empty = Text("");
-            Array$insert(&splits, &empty, I(0), sizeof(empty));
+            List$insert(&splits, &empty, I(0), sizeof(empty));
         }
     }
     return splits;
 }
 
-public Array_t Text$split_any(Text_t text, Text_t delimiters)
+public List_t Text$split_any(Text_t text, Text_t delimiters)
 {
     if (delimiters.length == 0)
-        return Array(text);
+        return List(text);
 
     TextIter_t text_state = NEW_TEXT_ITER_STATE(text), delim_state = NEW_TEXT_ITER_STATE(delimiters);
-    Array_t splits = {};
+    List_t splits = {};
     for (int64_t i = 0; i < text.length; ) {
         int64_t span_len = 0;
         while (i + span_len < text.length && !_has_grapheme(&delim_state, Text$get_grapheme_fast(&text_state, i + span_len))) {
@@ -1159,14 +1159,14 @@ public Array_t Text$split_any(Text_t text, Text_t delimiters)
         }
         bool trailing_delim = i + span_len < text.length;
         Text_t slice = Text$slice(text, I(i+1), I(i+span_len));
-        Array$insert(&splits, &slice, I(0), sizeof(slice));
+        List$insert(&splits, &slice, I(0), sizeof(slice));
         i += span_len + 1;
         while (i < text.length && _has_grapheme(&delim_state, Text$get_grapheme_fast(&text_state, i))) {
             i += 1;
         }
         if (i >= text.length && trailing_delim) {
             Text_t empty = Text("");
-            Array$insert(&splits, &empty, I(0), sizeof(empty));
+            List$insert(&splits, &empty, I(0), sizeof(empty));
         }
     }
     return splits;
@@ -1303,7 +1303,7 @@ PUREFUNC public bool Text$equal_ignoring_case(Text_t a, Text_t b, Text_t languag
 public Text_t Text$upper(Text_t text, Text_t language)
 {
     if (text.length == 0) return text;
-    Array_t codepoints = Text$utf32_codepoints(text);
+    List_t codepoints = Text$utf32_codepoints(text);
     const char *uc_language = Text$as_c_string(language);
     ucs4_t buf[128]; 
     size_t out_len = sizeof(buf)/sizeof(buf[0]);
@@ -1316,7 +1316,7 @@ public Text_t Text$upper(Text_t text, Text_t language)
 public Text_t Text$lower(Text_t text, Text_t language)
 {
     if (text.length == 0) return text;
-    Array_t codepoints = Text$utf32_codepoints(text);
+    List_t codepoints = Text$utf32_codepoints(text);
     const char *uc_language = Text$as_c_string(language);
     ucs4_t buf[128]; 
     size_t out_len = sizeof(buf)/sizeof(buf[0]);
@@ -1329,7 +1329,7 @@ public Text_t Text$lower(Text_t text, Text_t language)
 public Text_t Text$title(Text_t text, Text_t language)
 {
     if (text.length == 0) return text;
-    Array_t codepoints = Text$utf32_codepoints(text);
+    List_t codepoints = Text$utf32_codepoints(text);
     const char *uc_language = Text$as_c_string(language);
     ucs4_t buf[128]; 
     size_t out_len = sizeof(buf)/sizeof(buf[0]);
@@ -1451,7 +1451,7 @@ public Text_t Text$as_text(const void *vtext, bool colorize, const TypeInfo_t *i
     return as_text;
 }
 
-public Text_t Text$join(Text_t glue, Array_t pieces)
+public Text_t Text$join(Text_t glue, List_t pieces)
 {
     if (pieces.length == 0) return EMPTY_TEXT;
 
@@ -1478,38 +1478,38 @@ public Text_t Text$format(const char *fmt, ...)
     return ret;
 }
 
-public Array_t Text$clusters(Text_t text)
+public List_t Text$clusters(Text_t text)
 {
-    Array_t clusters = {};
+    List_t clusters = {};
     for (int64_t i = 1; i <= text.length; i++) {
         Text_t cluster = Text$slice(text, I(i), I(i));
-        Array$insert(&clusters, &cluster, I_small(0), sizeof(Text_t));
+        List$insert(&clusters, &cluster, I_small(0), sizeof(Text_t));
     }
     return clusters;
 }
 
-public Array_t Text$utf32_codepoints(Text_t text)
+public List_t Text$utf32_codepoints(Text_t text)
 {
-    Array_t codepoints = {.atomic=1};
+    List_t codepoints = {.atomic=1};
     TextIter_t state = NEW_TEXT_ITER_STATE(text);
     for (int64_t i = 0; i < text.length; i++) {
         int32_t grapheme = Text$get_grapheme_fast(&state, i);
         if (grapheme < 0) {
             for (int64_t c = 0; c < NUM_GRAPHEME_CODEPOINTS(grapheme); c++) {
                 ucs4_t subg = GRAPHEME_CODEPOINTS(grapheme)[c];
-                Array$insert(&codepoints, &subg, I_small(0), sizeof(ucs4_t));
+                List$insert(&codepoints, &subg, I_small(0), sizeof(ucs4_t));
             }
         } else {
-            Array$insert(&codepoints, &grapheme, I_small(0), sizeof(ucs4_t));
+            List$insert(&codepoints, &grapheme, I_small(0), sizeof(ucs4_t));
         }
     }
     return codepoints;
 }
 
-public Array_t Text$utf8_bytes(Text_t text)
+public List_t Text$utf8_bytes(Text_t text)
 {
     const char *str = Text$as_c_string(text);
-    return (Array_t){.length=strlen(str), .stride=1, .atomic=1, .data=(void*)str};
+    return (List_t){.length=strlen(str), .stride=1, .atomic=1, .data=(void*)str};
 }
 
 static INLINE const char *codepoint_name(ucs4_t c)
@@ -1523,9 +1523,9 @@ static INLINE const char *codepoint_name(ucs4_t c)
     return name;
 }
 
-public Array_t Text$codepoint_names(Text_t text)
+public List_t Text$codepoint_names(Text_t text)
 {
-    Array_t names = {};
+    List_t names = {};
     TextIter_t state = NEW_TEXT_ITER_STATE(text);
     for (int64_t i = 0; i < text.length; i++) {
         int32_t grapheme = Text$get_grapheme_fast(&state, i);
@@ -1533,65 +1533,65 @@ public Array_t Text$codepoint_names(Text_t text)
             for (int64_t c = 0; c < NUM_GRAPHEME_CODEPOINTS(grapheme); c++) {
                 const char *name = codepoint_name(GRAPHEME_CODEPOINTS(grapheme)[c]);
                 Text_t name_text = Text$from_str(name);
-                Array$insert(&names, &name_text, I_small(0), sizeof(Text_t));
+                List$insert(&names, &name_text, I_small(0), sizeof(Text_t));
             }
         } else {
             const char *name = codepoint_name((ucs4_t)grapheme);
             Text_t name_text = Text$from_str(name);
-            Array$insert(&names, &name_text, I_small(0), sizeof(Text_t));
+            List$insert(&names, &name_text, I_small(0), sizeof(Text_t));
         }
     }
     return names;
 }
 
-public Text_t Text$from_codepoints(Array_t codepoints)
+public Text_t Text$from_codepoints(List_t codepoints)
 {
     if (codepoints.stride != sizeof(int32_t))
-        Array$compact(&codepoints, sizeof(int32_t));
+        List$compact(&codepoints, sizeof(int32_t));
 
     return text_from_u32(codepoints.data, codepoints.length, true);
 }
 
-public OptionalText_t Text$from_codepoint_names(Array_t codepoint_names)
+public OptionalText_t Text$from_codepoint_names(List_t codepoint_names)
 {
-    Array_t codepoints = {};
+    List_t codepoints = {};
     for (int64_t i = 0; i < codepoint_names.length; i++) {
         Text_t *name = ((Text_t*)(codepoint_names.data + i*codepoint_names.stride));
         const char *name_str = Text$as_c_string(*name);
         ucs4_t codepoint = unicode_name_character(name_str);
         if (codepoint == UNINAME_INVALID)
             return NONE_TEXT;
-        Array$insert(&codepoints, &codepoint, I_small(0), sizeof(ucs4_t));
+        List$insert(&codepoints, &codepoint, I_small(0), sizeof(ucs4_t));
     }
     return Text$from_codepoints(codepoints);
 }
 
-public OptionalText_t Text$from_bytes(Array_t bytes)
+public OptionalText_t Text$from_bytes(List_t bytes)
 {
     if (bytes.stride != sizeof(int8_t))
-        Array$compact(&bytes, sizeof(int8_t));
+        List$compact(&bytes, sizeof(int8_t));
 
     return Text$from_strn(bytes.data, (size_t)bytes.length);
 }
 
-public Array_t Text$lines(Text_t text)
+public List_t Text$lines(Text_t text)
 {
-    Array_t lines = {};
+    List_t lines = {};
     TextIter_t state = NEW_TEXT_ITER_STATE(text);
     for (int64_t i = 0, line_start = 0; i < text.length; i++) {
         int32_t grapheme = Text$get_grapheme_fast(&state, i);
         if (grapheme == '\r' && Text$get_grapheme_fast(&state, i + 1) == '\n') { // CRLF
             Text_t line = Text$slice(text, I(line_start+1), I(i));
-            Array$insert(&lines, &line, I_small(0), sizeof(Text_t));
+            List$insert(&lines, &line, I_small(0), sizeof(Text_t));
             i += 1; // skip one extra for CR
             line_start = i + 1;
         } else if (grapheme == '\n') { // newline
             Text_t line = Text$slice(text, I(line_start+1), I(i));
-            Array$insert(&lines, &line, I_small(0), sizeof(Text_t));
+            List$insert(&lines, &line, I_small(0), sizeof(Text_t));
             line_start = i + 1;
         } else if (i == text.length-1 && line_start != i) { // last line
             Text_t line = Text$slice(text, I(line_start+1), I(i+1));
-            Array$insert(&lines, &line, I_small(0), sizeof(Text_t));
+            List$insert(&lines, &line, I_small(0), sizeof(Text_t));
         }
     }
     return lines;
@@ -1645,7 +1645,7 @@ public void Text$serialize(const void *obj, FILE *out, Table_t *pointers, const
     fwrite(str, sizeof(char), (size_t)len, out);
 }
 
-public void Text$deserialize(FILE *in, void *out, Array_t *pointers, const TypeInfo_t *)
+public void Text$deserialize(FILE *in, void *out, List_t *pointers, const TypeInfo_t *)
 {
     int64_t len = -1;
     Int64$deserialize(in, &len, pointers, &Int64$info);
diff --git a/src/stdlib/text.h b/src/stdlib/text.h
index 662c6e5f..604cea44 100644
--- a/src/stdlib/text.h
+++ b/src/stdlib/text.h
@@ -55,24 +55,24 @@ Text_t Text$without_suffix(Text_t text, Text_t suffix);
 Text_t Text$replace(Text_t text, Text_t target, Text_t replacement);
 Text_t Text$translate(Text_t text, Table_t translations);
 bool Text$has(Text_t text, Text_t target);
-Array_t Text$split(Text_t text, Text_t delimiter);
-Array_t Text$split_any(Text_t text, Text_t delimiters);
+List_t Text$split(Text_t text, Text_t delimiter);
+List_t Text$split_any(Text_t text, Text_t delimiters);
 Closure_t Text$by_split(Text_t text, Text_t delimiter);
 Closure_t Text$by_split_any(Text_t text, Text_t delimiters);
 Text_t Text$trim(Text_t text, Text_t to_trim, bool left, bool right);
 char *Text$as_c_string(Text_t text);
 __attribute__((format(printf, 1, 2)))
 public Text_t Text$format(const char *fmt, ...);
-Array_t Text$clusters(Text_t text);
-Array_t Text$utf32_codepoints(Text_t text);
-Array_t Text$utf8_bytes(Text_t text);
-Array_t Text$codepoint_names(Text_t text);
-Text_t Text$from_codepoints(Array_t codepoints);
-OptionalText_t Text$from_codepoint_names(Array_t codepoint_names);
-OptionalText_t Text$from_bytes(Array_t bytes);
-Array_t Text$lines(Text_t text);
+List_t Text$clusters(Text_t text);
+List_t Text$utf32_codepoints(Text_t text);
+List_t Text$utf8_bytes(Text_t text);
+List_t Text$codepoint_names(Text_t text);
+Text_t Text$from_codepoints(List_t codepoints);
+OptionalText_t Text$from_codepoint_names(List_t codepoint_names);
+OptionalText_t Text$from_bytes(List_t bytes);
+List_t Text$lines(Text_t text);
 Closure_t Text$by_line(Text_t text);
-Text_t Text$join(Text_t glue, Array_t pieces);
+Text_t Text$join(Text_t glue, List_t pieces);
 Text_t Text$repeat(Text_t text, Int_t count);
 Int_t Text$width(Text_t text, Text_t language);
 Text_t Text$left_pad(Text_t text, Int_t width, Text_t padding, Text_t language);
@@ -81,7 +81,7 @@ Text_t Text$middle_pad(Text_t text, Int_t width, Text_t padding, Text_t language
 int32_t Text$get_grapheme_fast(TextIter_t *state, int64_t index);
 uint32_t Text$get_main_grapheme_fast(TextIter_t *state, int64_t index);
 void Text$serialize(const void *obj, FILE *out, Table_t *, const TypeInfo_t *);
-void Text$deserialize(FILE *in, void *out, Array_t *, const TypeInfo_t *);
+void Text$deserialize(FILE *in, void *out, List_t *, const TypeInfo_t *);
 
 MACROLIKE int32_t Text$get_grapheme(Text_t text, int64_t index)
 {
diff --git a/src/stdlib/tomo.h b/src/stdlib/tomo.h
index b5642ec5..2d8d9908 100644
--- a/src/stdlib/tomo.h
+++ b/src/stdlib/tomo.h
@@ -7,7 +7,7 @@
 #include <stdint.h>
 #include <sys/param.h>
 
-#include "arrays.h"
+#include "lists.h"
 #include "bools.h"
 #include "bytes.h"
 #include "c_strings.h"
diff --git a/src/stdlib/types.c b/src/stdlib/types.c
index 8ced9051..0f51d6ea 100644
--- a/src/stdlib/types.c
+++ b/src/stdlib/types.c
@@ -6,7 +6,7 @@
 #include <sys/param.h>
 
 #include "util.h"
-#include "arrays.h"
+#include "lists.h"
 #include "pointers.h"
 #include "tables.h"
 #include "text.h"
diff --git a/src/stdlib/types.h b/src/stdlib/types.h
index 786e92d4..ddece7c9 100644
--- a/src/stdlib/types.h
+++ b/src/stdlib/types.h
@@ -17,7 +17,7 @@ typedef struct {
     Text_t (*as_text)(const void*, bool, const TypeInfo_t*);
     bool (*is_none)(const void*, const TypeInfo_t*);
     void (*serialize)(const void*, FILE*, Table_t*, const TypeInfo_t*);
-    void (*deserialize)(FILE*, void*, Array_t*, const TypeInfo_t*);
+    void (*deserialize)(FILE*, void*, List_t*, const TypeInfo_t*);
 } metamethods_t;
 
 typedef struct {
@@ -29,7 +29,7 @@ struct TypeInfo_s {
     int64_t size, align;
     metamethods_t metamethods;
     struct { // Anonymous tagged union for convenience 
-        enum { OpaqueInfo, StructInfo, EnumInfo, PointerInfo, TextInfo, ArrayInfo, TableInfo, FunctionInfo,
+        enum { OpaqueInfo, StructInfo, EnumInfo, PointerInfo, TextInfo, ListInfo, TableInfo, FunctionInfo,
             OptionalInfo, TypeInfoInfo } tag;
         union {
             struct {} OpaqueInfo;
@@ -42,7 +42,7 @@ struct TypeInfo_s {
             } TextInfo;
             struct {
                 const TypeInfo_t *item;
-            } ArrayInfo;
+            } ListInfo;
             struct {
                 const TypeInfo_t *key, *value;
             } TableInfo;