Appendix C: Bridger Prelude

The prelude is the set of names every Bridger program starts with: three algebraic data types, five traits, and the functions below. It is loaded before the program, and its names are reserved at the top level — a program may not declare a fn, let, ref, type, struct, trait, or relation with one of them, nor a constructor named like one of the prelude’s. A local binding, a parameter, a pattern variable, or a loop variable may shadow any of them, as it may any name in scope. The method names cmp, length, and from are not reserved: a program may declare a function cmp of its own, and a method call still resolves as Appendix D says.

Types and traits

type Option<T>   = None | Some(T);
type Result<T, E> = Ok(T) | Err(E);
type Ordering    = Less | Equal | Greater;

trait Eq {}
trait Print {}
trait Ord     { fn cmp(self, other: Self) -> Ordering; }
trait Len     { fn length(self) -> Int; }
trait From<T> { fn from(x: T) -> Self; }

Eq and Print declare no methods and cannot be implemented: a type is Eq when it admits equality and Print when it can be printed, both decided by its shape (Appendix D). Ord, Len, and From are implemented by impl blocks. The built-in types conform to some of them by rule rather than by impl: Int, String, and Bool are Ord, with cmp comparing integers numerically, strings by code point, and false below true; String and every list type are Len, with length counting a string’s Unicode scalar values or a list’s elements. A program may not write impl Ord for Int or impl Len for [T]; it may implement Len for Int, which has no built-in conformance. Ordering is not itself Ord.

Functions

Each entry gives the signature the type checker assigns and what the function does. A bound on a type parameter is discharged as Appendix D describes.

Printing

print(x: T) -> () and println(x: T) -> (), with T: Print, write the canonical text of x (below) to the output, println followed by a newline. to_string(x: T) -> String, with T: Print, returns that text. All three are effects for the purity judgment: a reference prints as the value it holds, so even to_string reads the store.

Integers

abs(n: Int) -> Int is the absolute value, wrapping like the operators: abs of the least integer is itself. even(n: Int) -> Bool and odd(n: Int) -> Bool test n % 2, so a negative odd number is odd.

Lists and strings

len(xs: T) -> Int, with T: Len, is xs.length(): the number of elements of a list, or of Unicode scalar values of a string, so a character written with a combining mark counts twice. head(xs: [T]) -> Option<T> and tail(xs: [T]) -> Option<[T]> are None on the empty list and otherwise Some of the first element or of the rest, the rest sharing its cells with xs. range(lo: Int, hi: Int) -> [Int] is the list of integers from lo up to but excluding hi, empty when lo >= hi; a range of more than 2^26 elements is stuck. contains(xs: [T], x: T) -> Bool, with T: Eq, is whether some element equals x by the language’s == — structurally for data, by identity for references.

min(a: T, b: T) -> T and max(a: T, b: T) -> T, with T: Ord, return the smaller or larger argument by cmp, and the first argument when the two compare Equal. minimum(xs: [T]) -> Option<T> and maximum(xs: [T]) -> Option<T>, with T: Ord, are None on the empty list and otherwise Some of the least or greatest element, the earliest of equals; they fold min or max over the list from the left, so cmp is called with the best so far as its receiver. Until the objects milestone these five are native and accept only the built-in Ord and Len types; from it they are written in Bridger over the traits, so a program’s own impl Ord or impl Len flows through them.

unwrap_or(o: Option<T>, d: T) -> T is the Some payload, or d. is_some(o: Option<T>) -> Bool is whether o is a Some.

Higher-order functions

map(xs: [A], f: fn(A) -> B) -> [B], filter(xs: [A], p: fn(A) -> Bool) -> [A], and fold(xs: [A], z: B, f: fn(B, A) -> B) -> B visit the list from the left, calling the function once per element. fold computes f(f(f(z, x1), x2), x3)…, so the accumulator is the first argument and the element the second. A return inside a lambda handed to them returns from the lambda. They iterate rather than recurse, so a long list costs no stack and their calls open no frames; the function they are handed opens one per call like any other. In a rule filter or a match guard, the function must be one the purity judgment can follow — a named function, a lambda, or a pure primitive.

Reading input

The readers consume the program’s input, a text read whole before the program runs; input from a terminal is never read, so a program run interactively sees an empty input.

read_int() -> Int skips ASCII whitespace and reads the next token, which must be an integer literal exactly as the lexer reads one: an optional -, then digits with no leading zero and either no grouping or groups of three digits separated by _. +5, 007, 1_0000, and a token with trailing letters are not literals. read_bool() -> Bool reads a token that is exactly true or false. read_line() -> String returns the rest of the current line without its newline, a trailing carriage return dropped; after a token reader has read part of a line, a remainder that is only whitespace is skipped and the next line is returned, and a remainder with content is returned as it stands, its leading whitespace included. Each is stuck when the input has ended or the token is not of the expected form, and the failure leaves the input where it was. read_int_opt() -> Option<Int>, read_bool_opt() -> Option<Bool>, and read_line_opt() -> Option<String> return None in those cases instead, consuming nothing, so a failed read can be followed by read_line to see what was there. Every reader is an effect for the purity judgment.

Printing

The canonical text of a value is what print, println, and to_string produce, and what a test compares against.

• An integer prints in decimal with a leading - when negative; true, false, and () print as written.
• A string at the top level prints raw: print("a\n") writes a and a newline. A string inside another value prints quoted, with " and \ escaped as \" and \\, newline, tab, carriage return, and the null character as \n, \t, \r, and \0, any other control character as \u{…} with its code in lowercase hexadecimal, and every other character as itself.
• A tuple prints as (v, v, …), a list as [v, v, …] and the empty list as [], with one comma and one space between elements.
• A constructor prints as its name, followed by its arguments in parentheses when it has any: Some(1), None, Ok((1, "a")), Less.
• A struct prints as its name and its fields in declaration order, whatever order the literal gave them: Point { x: 1, y: 2 }; a struct with no fields prints as Empty {}.
• A reference prints as ref(v) with the value it currently holds; a reference reached again while printing its own contents prints as ref(…).
• A function, a relation, or a type name has no text: printing one is a static error — a function because it is not Print, a relation or a type name because neither is a value — and a stuck state when the program runs unchecked.

Purity

For the purity judgment of Appendix D, print, println, to_string, and the six readers are effects; every other prelude function is pure, and map, filter, and fold are as pure as the function they are handed. The Bridger-written min, max, minimum, maximum, and len are trusted to terminate, so a filter may call them; the cmp or length they reach is judged like any method, so an impl Ord whose cmp prints, or recurses, makes such a filter impure or non-total.