Collection library reference

Implemented by the primary self-hosted BASIL compiler. Algorithms are first-party BASIL in stdlib/lists.bas, stdlib/hash_collections.bas and stdlib/arrays.bas, with additional generic families for deques, queues, heaps, sorted keys, counters, multimaps, bitsets and caches. Collections accept all implemented copyable types: INTEGER, BOOLEAN, DOUBLE, STRING, arrays, nominal records, supported error values, optionals, and nested lists/sets/dictionaries. Types remain static and homogeneous; there is no dynamically typed catch-all value. Arrays, lists, optionals and dictionary values can also own files/sockets/user resource records under explicit ownership rules ; these containers are noncopyable. Resource dictionary Put/Remove/Extract/iteration and checked borrowed Get/SetDefault/Find and bracket reads/writes are supported; resource keys/sets and task/channel capability elements remain unsupported.

Collections grow automatically. Assignment makes independent values; owned elements are copied recursively. Ordinary parameters borrow read-only access, and BYREF borrows exclusive writable access. An ordinary owned return copies a borrowed collection; explicit BORROW returns a checked read-only view tied to one or two declared parameters. Fresh temporary owned results can construct their destination directly. No resource transfer is inferred from last use, and no garbage collector/reference counting is used.

Resource lists support literals, Append, Insert, Reverse, SwapAt, Pop, ExtractAt, RemoveAt, Clear, checked element/field replacement and borrowing. Copying operations, slices and generic operations that require copying an element remain rejected. Pop removes and transfers the last owner; ordinary indexed reads cannot make an independent resource copy.

ToArray takes a BYVAL list and creates a zero-based rank-one array. Copyable inputs remain independent; named resource lists need explicit TAKE. See resource array defaults, borrows and resizing .

Lists

DIM numbers = [3, 1, 2, 1]
DIM names AS LIST OF STRING = []
Append(BYREF names, "Ada")
PRINT IndexOf(numbers, 1)
PRINT CountOf(numbers, 1)
DIM ordered = Sorted(numbers)

FOR EACH number IN ordered
    PRINT number
NEXT

LIST() creates an empty integer list without type context, or the list type supplied by its destination. Nonempty literals infer one element type; [] requires a LIST type context. Literals evaluate elements left to right, accept line breaks/trailing commas, and clean completed elements/list storage if a later expression fails. Mixed element types are rejected.

Sorting compares integers numerically and strings in exact Unicode scalar lexicographic order, independent of locale. Search uses exact equality. Insert/RemoveAt/ExtractAt/Slice validate positions before mutation. RemoveAt destroys the removed owner after compacting; ExtractAt transfers it to the result, with no copies of shifted elements. IndexError has an INTEGER Index field. EmptyCollection is a fieldless typed error. Direct indexing retains its existing fatal bounds policy; the listed checked editing/slicing APIs use recoverable failures. Bracket indexing now accepts negative indices, and bracket slices support strides; see sequence reference for implemented behavior and remaining compatibility limits.

Extend(BYREF items, items) conflicts with exclusive access and is rejected; explicitly copy the source if a snapshot is desired. Checked Reserve/Resize/Truncate/CopyWithin are documented in buffers . Named-function predicates and stable comparator callbacks are documented below. Generic records provide statically specialized user/container types. SPLIT, LINES, CODEPOINTS and JOIN are documented in the string library .

Sets

DIM names AS SET OF STRING = SET()
Insert(BYREF names, "Ada")
Insert(BYREF names, "Grace")
IF Contains(names, "Ada") THEN
    PRINT "Found"
END IF

SET() requires SET type context. Members are unique. LEN, Insert, Contains, Remove, Clear, Keys, Union, Intersection, Difference, SymmetricDifference, assignment/returns and FOR EACH are supported.

Insert returns TRUE for a new member and FALSE for a duplicate. Duplicates keep their position. Remove returns whether a member was removed; removal followed by insertion puts the member last. Keys returns an independent list snapshot in insertion order. Union visits left then unseen right members; intersection/difference preserve left order; symmetric difference visits left-only then right-only members. Whole-set = / == / <> use order-independent value equality.

Dictionaries

DIM ages AS DICT OF STRING TO INTEGER = DICT()
Put(BYREF ages, "Ada", 36)
Put(BYREF ages, "Grace", 85)

FOR EACH name, age IN ages
    PRINT name + ": " + STR(age)
NEXT

DICT() requires DICT type context. Supported operations:

Replacement preserves key position. Remove/reinsert moves the key last. Find distinguishes a missing entry from a present zero or empty string. Optional dictionary values and structural Equal are supported. A list-of-records Entries snapshot remains future work. The supported pair iteration does not depend on an Entries snapshot. See defaults and optionals for checked presence binding, fallback evaluation and error contracts.

Predicate operations

Named functions, callable values and contextual lambdas can supply predicates. A list or set predicate has signature CALLABLE(T) AS BOOLEAN; dictionary predicates use CALLABLE(K,V) AS BOOLEAN. Parameters borrow read-only. Earlier collection arguments select a matching overloaded function. Predicates must be infallible; they can suspend, with ordinary cancellation and cleanup. Lambda captures are independent readonly snapshots of copyable values; resource captures and arbitrary composed predicate error sets remain unsupported. For example, Filter(items,(value) => value>=minimum) captures minimum at construction.

Each visited element is tested once. Sets/dicts visit insertion order. Filter does not mutate its source, retains dictionary keys, and preserves list duplicates. Read-only searches/counts also accept owning resource lists/dictionary values; Filter and FindWhere reject resource results because they would require copying. The source remains protected against invalidating writes/transfers during callback execution, including suspension. Cancellation cleans a partially built result and callback/iteration temporaries. Ordinary fatal-allocation policy still applies.

values=[1,2,3,4]
PRINT Any(values,Even)
PRINT CountWhere(values,Even)
FOR EACH value IN Filter(values,Even)
    PRINT value
NEXT
FUNCTION Even(value AS INTEGER) AS BOOLEAN = value MOD 2=0

Iteration and borrowing

FOR EACH item IN list/set introduces a read-only binding. FOR EACH key, value IN dictionary introduces two; a dictionary may also be traversed by key alone. NEXT may optionally repeat the first binding name. Bindings are scoped to the loop and cannot be reassigned. Rebinding an existing active name is rejected.

Iteration borrows the source for the loop’s duration. Mutation/replacement through the source name, another field of its owning record, or a BYREF call is rejected while this borrow is live. This conservative record-wide exclusion also rejects some disjoint-field writes. String bindings borrow their protected element storage without payload copies. Retaining or returning them creates independent values. Temporary collection results can be iterated; their ownership ends on normal loop completion, function exit or recoverable failure. No hidden snapshot repairs a conflicting mutation.

Generic algorithms and value capabilities

The BASIL library uses generic functions, for example:

FUNCTION First[T](items AS LIST OF T) AS T
    RETURN items[0]
END FUNCTION

DIM readings = [1.5, 2.5]
PRINT First(readings)
DIM names AS DICT OF STRING TO LIST OF STRING = DICT()
Put(BYREF names, "team", ["Ada", "Grace"])
DIM missing = Get(names, "absent", [])

Earlier arguments supply type context for later [] and NONE arguments. Generic specializations are cached by template and concrete type arguments. Ordinary recursion reuses a specialization; a recursive call that continually changes type arguments is rejected. Generic bodies are checked when instantiated. No runtime boxing, shared collection storage, or implicit ownership transfer is introduced. Generic record declarations and explicit bracketed type-argument call syntax remain unimplemented. Result AS annotations and known complete-call destinations can supply generic result constraints; see result context .

Equal(left,right) and same-type = / == compare copyable values structurally. IEEE equality applies recursively: NaN is unequal even within a value compared with itself, and signed zeros are equal. Records/choices/optionals and sequence contents participate; set/dictionary equality ignores insertion order, capacity and tombstones. Resource and callable equality reject. Hash(value) remains a deterministic nonnegative 31-bit INTEGER, with equal signed-zero hashes; it is not cryptographic.

Compare(left,right) returns CompareResult.Less/Equal/Greater/Unordered. NaN is unordered; composite comparison is lexicographic. Default sorting uses a separate total comparison with NaNs last, so a sorting tie does not establish equality. Exact comparison and constructor contracts .

NaN members/keys raise InvalidKeyError before lookup or mutation, including empty collections and composite keys. Dictionary values and list elements may hold NaN. Infinity is valid; signed zeros identify one key. ValidateKey returns zero or the same typed failure. NaN-free types keep infallible specializations without runtime scans; other public key operations compose the error with FAILS LIKE . Get without a fallback additionally reports MissingKey. Existing-key algebra and independent key snapshots preserve validity. A transferred value argument is cleaned if a later key check fails; ownership transfer is not rolled back.

List editing/search/slicing/sorting operations support the implemented copyable element types. Resource containers expose only their documented ownership-safe subset; operations requiring resource copies remain rejected. Sets/dictionaries preserve insertion order for snapshots and iteration. Removing a key releases its owned key/value storage; copying a table with removed slots is safe. Recoverable failures clean up argument temporaries and partially built values. OOM remains fatal. Owned declarations inside conditional/TRY/loop bodies are supported with lexical visibility and per-iteration cleanup. FOR EACH introduces checked read-only borrowed bindings and protects its source root for the loop lifetime.

Runnable examples: nested values and general keys . Validation includes nested ownership, NaN-key rejection, signed-zero key equivalence, arrays and errors as keys, generic recursion, dictionary order-independent equality, malformed/unsafe cases, and repeated successful/failing operations under a 64 MiB address-space limit.

Comparator sorting

Sorted(items, Compare=comparator) returns an independent sorted list; Sort(BYREF items, Compare=comparator) changes the list in place and returns 0. Both are stable: a comparator result of zero preserves original relative order. The comparator takes two read-only elements and returns INTEGER (negative/zero/positive compatibility) or CompareResult. The callback itself must be infallible. An enum Unordered result produces UnorderedComparisonError; callback sorts build before commit, leaving the input intact on that failure. Stable ties preserve original order. Named/positional and overloaded named comparators are checked with their element and inferred result types. Ordinary named functions and lambdas with checked copyable captures are supported; generic named-function references remain unsupported. The default overload avoids callback dispatch and uses NaNs-last total value ordering.

names=["bob","Ada","BOB"]
ordered=Sorted(names,Compare=CompareCaseInsensitive)
Sort(BYREF names,Compare=CompareCaseInsensitive)
FUNCTION Descending(a AS INTEGER,b AS INTEGER) AS CompareResult
    RETURN Compare(b,a)
END FUNCTION

CompareCaseInsensitive returns CompareResult after comparing full Unicode CASEFOLD results. It does not normalize canonically equivalent text or apply language-specific collation. STRING overloads also exist: Sorted(text, Compare=comparator) sorts Unicode code points and returns STRING; strings use the value-returning Sorted form. The default STRING overload uses ordinary value ordering. Combining marks are separate elements, so character sorting is not locale-aware text collation. Empty inputs return empty values. Original strings and other independent copies remain unchanged. Comparator callbacks cannot mutate the collection being sorted through another alias; ordinary checked borrowing still applies. Captures are independent readonly snapshots, not aliases granting mutation of the original collection.