Introduction to Flix

Flix is a principled functional, logic, and imperative programming language developed at Aarhus University and by a community of open source contributors in collaboration with researchers from the University of Waterloo, from the University of Tubingen, and from the University of Copenhagen.

Flix is inspired by OCaml and Haskell with ideas from Rust and Scala. Flix looks like Scala, but its type system is based on Hindley-Milner which supports complete type inference. Flix aims to offer a unique combination of features that no other programming language offers, including:

• algebraic data types and pattern matching.
• type classes with higher-kinded types.
• structured concurrency based on channels and light-weight processes.

In addtion, Flix has several new powerful and unique features:

• A polymorphic type and effect system with region-based local mutation.
• Datalog constraints as first-class program values.
• Function overloading based on purity reflection.

Flix compiles to efficient JVM bytecode, runs on the Java Virtual Machine, and supports full tail call elimination. Flix has interoperability with Java and can use JVM classes and methods. Hence the entire Java ecosystem is available from within Flix.

Flix aims to have world-class Visual Studio Code support. The Flix Visual Studio Code extension uses the real Flix compiler hence there is always a 1:1 correspondence between the Flix language and what is reported in the editor. The advantages are many: (a) diagnostics are always exact, (b) code navigation "just works", and (c) refactorings are always correct.

Look'n Feel

Here are a few programs to illustrate the look and feel of Flix:

This program illustrates the use of algebraic data types and pattern matching:

/// An algebraic data type for shapes.
enum Shape {
    case Circle(Int32),          // circle radius
    case Square(Int32),          // side length
    case Rectangle(Int32, Int32) // height and width
}

/// Computes the area of the given shape using
/// pattern matching and basic arithmetic.
def area(s: Shape): Int32 = match s {
    case Shape.Circle(r)       => 3 * (r * r)
    case Shape.Square(w)       => w * w
    case Shape.Rectangle(h, w) => h * w
}

// Computes the area of a 2 by 4.
def main(): Unit \ IO =
    area(Shape.Rectangle(2, 4)) |> println

Here is an example that uses polymorphic records:

/// Returns the area of the polymorphic record `r`.
/// Note that the use of the type variable `a` permits the record `r`
/// to have labels other than `x` and `y`.
def polyArea[a : RecordRow](r: {x = Int32, y = Int32 | a}): Int32 = r.x * r.y

/// Computes the area of various rectangle records.
/// Note that some records have additional labels.
def polyAreas(): List[Int32] =
    polyArea({x = 1, y = 2}) ::
    polyArea({x = 2, y = 3, z = 4}) :: Nil

def main(): Unit \ IO =
    polyAreas() |> println

Here is an example that uses region-based local mutation:

///
/// We can define pure functions that use
/// internal mutability (impurity) with regions.
/// Regions encapsulate mutability to its declared scope.
///
def deduplicate(l: List[a]): List[a] with Order[a] =
    /// Declare a new region `rc`.
    region rc {

        /// Create a new `MutSet` at region `r`.
        /// This will be used to keep track of
        /// unique elements in `l`.
        let s = MutSet.new(rc);

        /// The lambda used in the call to `filter`
        /// would be impure without a region.
        List.filter(x -> {
            if (MutSet.memberOf(x, s))
                false // `x` has already been seen.
            else {
                MutSet.add!(x, s);
                true
            }
        }, l)
    }

Here is an example that uses first-class Datalog constraints:

def reachable(edges: List[(Int32, Int32)], src: Int32, dst: Int32): Bool =
    let db = inject edges into Edge;
    let pr = #{
        Path(x, y) :- Edge(x, y).
        Path(x, z) :- Path(x, y), Edge(y, z).
        Reachable() :- Path(src, dst).
    };
    let result = query db, pr select () from Reachable();
    not Vector.isEmpty(result)

And finally here is an example that uses structured concurrency with channels and processes:

/// A function that sends every element of a list
def sendAll(l: List[Int32], tx: Sender[Int32, r]): Unit \ IO =
    match l {
        case Nil     => ()
        case x :: xs => Channel.send(x, tx); sendAll(xs, tx)
    }

/// A function that receives n elements
/// and collects them into a list.
def recvN(n: Int32, rx: Receiver[Int32, r]): List[Int32] \ IO =
    match n {
        case 0 => Nil
        case _ => Channel.recv(rx) :: recvN(n - 1, rx)
    }

/// A function that calls receive and sends the result on d.
def wait(rx: Receiver[Int32, r], n: Int32, tx: Sender[List[Int32], r]): Unit \ IO =
    Channel.send(recvN(n, rx), tx);
    ()

/// Spawn a process for send and wait, and print the result.
def main(): Unit \ IO = region rc {
    let l = 1 :: 2 :: 3 :: Nil;
    let (tx1, rx1) = Channel.buffered(rc, 100);
    let (tx2, rx2) = Channel.buffered(rc, 100);
    spawn sendAll(l, tx1) @ rc;
    spawn wait(rx1, List.length(l), tx2) @ rc;
    println(Channel.recv(rx2))
}

Additional examples can be found in these pages and in the examples folder on GitHub.

Getting Started

Getting started with Flix is straightforward. All you need is Java version 11+.

You can check if Java is installed and its version by typing:

$ java -version

which should print something like:

openjdk version "18.0.2.1" 2022-08-18
OpenJDK Runtime Environment Temurin-18.0.2.1+1 (build 18.0.2.1+1)
OpenJDK 64-Bit Server VM Temurin-18.0.2.1+1 (build 18.0.2.1+1, mixed mode, sharing)

If Java is not installed or your version is too old, a newer version can be downloaded from Adoptium.

Once you have Java 11+ installed there are two ways to proceed:

• You can use the Flix VSCode extension (highly recommended) or
• You can run the Flix compiler from the command line.

Using Flix from Visual Studio Code (VSCode)

Flix comes with a fully-featured VSCode plugin. Follow these steps to get started:

1. Create a new empty folder (e.g. my-flix-project).
2. Open VSCode and choose File -> Open Folder.
3. Create a new file called Main.flix in the folder.
4. VSCode will ask you want to search the marketplace for extensions. Say "Yes".
5. The Flix extension will be downloaded and installed. Once done, it will ask if you want to download the Flix compiler. Say "Yes" again.
6. When you see "Starting Flix" followed by "Flix Ready!" everything should be ready.

A screenshot of the Flix Visual Studio Code extension in action:

Using Flix from the Command Line

Flix can also be used from the command line. Follow these steps:

1. Create a new empty folder (e.g. my-flix-project).
2. Download the latest flix.jar from https://github.com/flix/flix/releases/latest and put it into the folder.
3. Enter the created directory (e.g. cd my-flix-project) and run java -jar flix.jar init to create an empty Flix project.
4. Run java -jar flix.jar run to compile and run the project.

Troubleshooting

The most common reasons for Flix not working are (a) the java command not being on your PATH, (b) the JAVA_HOME environmental variable not being set or being set incorrectly, or (c) having the wrong version of Java installed. To debug these issues, ensure that:

• The command java -version prints the right Java version.
• The JAVA_HOME environmental variable is correctly set.
  • On Windows, you can print the variable by typing echo %JAVA_HOME%.
  • On Mac and Linux, you can print the variable by typing echo $JAVA_HOME.

If you are still stuck, you can ask for help on Gitter.

Hello World

We can now see the famous Hello World program in src/Main.flix file:

def main(): Unit \ IO = 
    println("Hello World!")

That's it!

You will immediately notice a few things are different from other programming languages:

• The main function has no formal parameters, in particular it does not take an arguments array. Instead the command line arguments are available by calling the Environment.getArgs functions.
• The return type of the main function is Unit.
• The main function has the IO effect since it prints to the terminal.

Next Steps

We are now ready write our first real program!

We will write a simple variant of the venerable wordcount (wc) program from UNIX. We shall not be concerned with efficiency, but we will carefully check all error cases.

Create a new folder (e.g. wc), set up an empty Flix project and put the following code into src/Main.flix:

def main(): Unit \ IO = 
    let args = Environment.getArgs();
    match args {
        case Nil => println("Missing argument: filename")
        case file :: _ => 
            match File.readLines(file) {
                case Err(_) => 
                    println("Unable to read: ${file}")
                case Ok(lines) => 
                    let totalLines = List.length(lines);
                    let totalWords = List.sumWith(numberOfWords, lines);
                    println("Lines: ${totalLines}, Words: ${totalWords}")
            }
    }

def numberOfWords(s: String): Int32 = 
    s |> String.words |> List.length

The program works as follows:

1. We use Environment.getArgs() to get the program arguments. We expect a list with at least one element; the name of the file to count lines and words in. We use pattern matching on args to extract the file name and report an error if the list is empty.
2. We use File.readLines to read all lines of the file. This operation may fail (e.g. if the file does not exist) and hence it returns a Result. We use pattern matching on the result and print an error message if we could not read the file.
3. Otherwise we have a List[String] from which we can easily compute the number of lines and using the helper function numberOfWords, we can also easily compute the total number of words. Finally, we print these two numbers.

We can compile and run the program as follows:

$ java -jar flix.jar build    
$ java -jar flix.jar build-jar
$ java -jar artifact/wc.jar src/Main.flix
Lines: 17, Words: 62

The above program gets the job done, but it is a bit verbose. A more readable version is:

def main(): Unit \ IO = 
    let args = Environment.getArgs();
    let result = 
        for (
            file  <- List.head(args) |> 
                     Option.toOk("Missing argument: filename");
            lines <- File.readLines(file) |> 
                     Result.mapErr(_ -> "Unable to read: ${file}")
        ) yield {
            let totalLines = List.length(lines);
            let totalWords = List.sumWith(numberOfWords, lines);
            (totalLines, totalWords)
        };
    match result {
        case Ok((lines, words)) => println("Lines: ${lines}, Words: ${words}")
        case Err(message)       => println(message)
    }

def numberOfWords(s: String): Int32 = 
    s |> String.words |> List.length

which takes advantages of the monadic for-yield construct.

Data Types

Flix comes with a collection of built-in data types, such as booleans, floats and integers, and compound types, such as tuples and records. Moreover, the standard library defines types such as Option[a], Result[e, t], List[a], Set[a], and Map[k, v].

In addition to these types, Flix allows programmers to define their own types, including enumerated types, recursive types, and polymorphic types.

Flix also supports type aliases (new types).

Primitive Types

Flix supports the primitive types:

Float64 and Int32 values can be written without suffix, i.e. 123.0f64 can simply be written as 123.0 and 123i32 can be written as 123.

Built-in Literals

Flix has built-in syntactic sugar for lists, sets, and maps.

List Literals

A list literal is written using the infix :: constructor. For example:

1 :: 2 :: 3 :: Nil

which is syntactic sugar for:

Cons(1, Cons(2, Cons(3, Nil)))

Alternatively, the same list can also be written as:

List#{1, 2, 3}

Set Literals

A set literal is written using the notation Set#{v1, v2, ...}. For example:

Set#{1, 2, 3}

which is syntactic sugar for:

Set.insert(3, Set.insert(2, Set.insert(1, Set.empty())))

Note that the elements are inserted from left to right, thus 1 is inserted first.

Map Literals

A map literal is written using the notion Map#{k1 => v1, k2 => v2, ...}. For example:

Map#{1 => "Hello", 2 => "World"}

which is syntactic sugar for:

Map.insert(2, "World", Map.insert(1, "Hello", Map.empty()))

Note that similar to sets above, the entries are inserted left to right. In particular, if multiple entries share the same key, the rightmost one overwrites the previous values.

Tuples

A tuple is a product of values. The form of a tuple is (exp1, ..., expn).

For example, here is a 2-tuple (a pair) of an Int32 and a Bool:

(123, true)

The type of the tuple is (Int32, Bool).

We can destructure a tuple using pattern matching. For example:

let t = ("Lucky", "Luke", 42, true); // 4-tuple
let (fstName, lstName, age, male) = t;
lstName

evaluates to the string "Luke".

The Flix Prelude defines the fst and snd functions:

let t = (1, 2);
let x = fst(t); // x = 1
let y = snd(t)  // y = 2

which are useful when working with 2-tuples (i.e. pairs). For example:

let l = (1, 1) :: (2, 2) :: Nil; // has type List[(Int32, Int32)]
List.map(fst, l)                 // has type List[Int32]

which evaluates to the list:

1 :: 2 :: Nil

Enums

Enumerated Types

Enumerated types are used to define a type that has a finite (enumerated) set of values. Enumerated types are useful for things such as modeling compass directions, the cards in a deck, and the days in a week.

For example, here is an enumeration of the days in a week:

enum Weekday {
    case Monday,
    case Tuesday,
    case Wednesday,
    case Thursday,
    case Friday,
    case Saturday,
    case Sunday
}

Here Monday, Tuesday and so on are referred to as the constructors of the enum.

We can refer to a weekday as Monday or Weekday.Monday. The latter is required if we have multiple enums in scope with similarly named constructors.

We can use pattern matching to destruct an enum value. For example:

enum Animal {
    case Cat,
    case Dog,
    case Giraffe
}

def isTall(a: Animal): Bool = match a {
    case Animal.Cat        => false
    case Animal.Dog        => false
    case Animal.Giraffe    => true
}

The function isTall takes a value of type Animal and performs a pattern match on it. If the value is Giraffe the function returns true. Otherwise it returns false.

Flix guarantees that pattern matches are exhaustive, i.e. that all cases have been covered. It is a compile-time error if a pattern match is non-exhaustive. A pattern match can always be made exhaustive by adding a default case as the last case. A default case is written with an underscore case _ => ???.

Recursive Types

Recursive types are used to define types that are self-referential.

For example, we can define a binary tree of integers as follows:

enum Tree {
    case Leaf(Int32),
    case Node(Tree, Tree)
}

A tree is either a Leaf with an Int32 value or an internal Node with a left and a right sub-tree. Note that the definition of Tree refers to itself.

We can write a function, using pattern matching, to compute the sum of all integers in such a tree:

def sum(t: Tree): Int32 = match t {
    case Tree.Leaf(x)    => x
    case Tree.Node(l, r) => sum(l) + sum(r)
}

The sum function pattern matches on a tree value. If the tree is a leaf its value is simply returned. Otherwise the function recurses on both subtrees and adds their results.

Polymorphic Types

Polymorphic types are types parameterized by other types. For example, we can write:

enum Bottle[a] {
    case Empty,
    case Full(a)
}

def isEmpty(b: Bottle[a]): Bool = match b {
    case Bottle.Empty   => true
    case Bottle.Full(_) => false
}

Here the Bottle type is parameterized by the type parameter a. In Flix, type parameters, like ordinary parameters are always written in lowercase. The Bottle type has two cases: either the bottle is empty (and contains no value) or it is full (and contains one value of type a). The isEmpty function takes a bottle, type parameterized by a, and determines if the bottle is empty.

The careful reader might have noticed that Bottle is equivalent to the more well-known Option type.

In general, polymorphic types can have more than one type argument. For example, the standard library implement of the Result has two type parameters:

enum Result[e, t] {
    case Ok(t),
    case Err(e)
}

Shorthand Enum Syntax

A typical enum may look like:

enum Weekday {
    case Monday,
    case Tuesday,
    case Wednesday,
    case Thursday,
    case Friday,
    case Saturday,
    case Sunday
}

The same enum can also be declared as:

enum Weekday {
    case Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday
}

This shorthand syntax is always available, but should only be used for simple enums.

Singleton Enum Syntax

An enum with a single case:

enum USD {
  case USD(Int32)
}

can be shortened to:

enum USD(Int32)

Type Aliases

Type aliases introduces a short-hand name for a type. For example:

///
/// A type alias for a map from keys of type `k`
/// to values of type `Result[String, v]`
///
type alias M[k, v] = Map[k, Result[String, v]]

def foo(): M[Bool, Int32] = Map#{true => Ok(123)}

A type alias does not define a new distinct type. Rather a type alias is simply a syntactic short-hand for a (usually complex) type.

The Flix compiler expands type aliases before type checking. Consequently, type errors are always reported with respect to the actual underlying types.

Note: A type alias cannot be recursively defined in terms of itself. The Flix compiler will detect and report such recursive cycles.

Functions

Functions and higher-order functions are the key building block of a functional programming language.

In Flix, top-level functions are defined with the def keyword. For example:

def add(x: Int32, y: Int32): Int32 = x + y + 1

A definition consists of the function name followed by an argument list, the return type, and the function body. Although Flix supports type inference, top-level function definitions must declare the type of their arguments and their return type.

In Flix, all function arguments and local variables must be used. If a function argument is not used it must be prefixed with an underscore to explicitly mark it as unused.

First-Class and Higher-Order Functions

A higher-order function is a function that takes a parameter which is itself a function. For example:

def twice(f: Int32 -> Int32, x: Int32): Int32 = f(f(x))

Here the twice function takes two arguments, a function f and an integer x, and applies f to x two times.

We can pass a lambda expression to the twice function:

twice(x -> x + 1, 42)

which evaluates to 44 since 42 is incremented twice.

We can also define a higher-order function that requires a function which takes two arguments:

def twice(f: (Int32, Int32) -> Int32, x: Int32): Int32 =
    f(f(x, x), f(x, x))

which can be called as follows:

twice((x, y) -> x + y, 42)

We can call a higher-order function with a top-level function as follows:

def inc(x: Int32): Int32 = x + 1

def twice(f: Int32 -> Int32, x: Int32): Int32 = f(f(x))

twice(inc, 42)

Function Type Syntax

Depending on the number of arguments to a function, the syntax for the function type differs:

Unit -> Int32                // For nullary functions
Int32 -> Int32               // For unary functions
(Int32, Int32, ...) -> Int32 // For the rest

Function Composition

Flix supports several operators for function composition and pipelining:

let f = x -> x + 1;
let g = x -> x * 2;
let h = f >> g;     // equivalent to x -> g(f(x))

Here >> is forward function composition.

We can also write function applications using the pipeline operator:

List.range(1, 100) |>
List.filter(x -> x mod 2 == 0) |>
List.map(x -> x * x) |>
println;

Here x |> f is equivalent to the function application f(x).

Curried by Default

Functions are curried by default. A curried function can be called with fewer arguments than it declares returning a new function that takes the remainder of the arguments. For example:

def sum(x: Int32, y: Int32): Int32 = x + y

def main(): Unit \ IO =
    let inc = sum(1);
    inc(42) |> println

Here the sum function takes two arguments, x and y, but it is only called with one argument inside main. This call returns a new function which is similar to sum, except that in this function x is always bound to 1. Hence when inc is called with 42 it returns 43.

Currying is useful in many programming patterns. For example, consider the List.map function. This function takes two arguments, a function of type a -> b and a list of type List[a], and returns a List[b] obtained by applying the function to every element of the list. Now, if we combine currying with the pipeline operator |> we are able to write:

def main(): Unit \ IO =
    List.range(1, 100) |>
    List.map(x -> x + 1) |>
    println

Here the call to List.map passes the function x -> x + 1 which returns a new function that expects a list argument. This list argument is then supplied by the pipeline operator |> which, in this case, expects a list and a function that takes a list.

Pipelines

Flix supports the pipeline operator |> which is simply a prefix version of function application (i.e. the argument appears before the function).

The pipeline operator can often be used to make functional code more readable. For example:

let l = 1 :: 2 :: 3 :: Nil;
l |>
List.map(x -> x * 2) |>
List.filter(x -> x < 4) |>
List.count(x -> x > 1)

Here is another example:

"Hello World" |> String.toUpperCase |> println

Operators

Flix has a number of built-in unary and infix operators. In addition Flix supports infix function application by enclosing the function name in backticks. For example:

123 `sum` 456

is equivalent to the normal function call:

sum(123, 456)

In addition, a function named with an operator name (some combination of +, -, *, <, >, =, !, &, |, ^, and $) can also be used infix. For example:

def <*>(x: Int32, y: Int32): Int32 = ???

can be used as follows:

1 <*> 2

Pure, Impure, and Effect Polymorphic Functions

In Flix every function is pure, impure, or effect polymorphic.

The Flix type and effect system ensures that a pure function always returns the same result when given the same arguments and that it cannot have (observable) side effects.

In Flix every function definition is implicitly marked as Pure. For example, the function definition:

def add(x: Int32, y: Int32): Int32 = x + y

is actually equivalent to:

def add(x: Int32, y: Int32): Int32 \ {} = x + y

Note the annotation for Pure is \ {}.

A function that prints to the console is Impure and must be marked with \ IO:

def addAndPrint(x: Int32, y: Int32): Int32 \ IO =
    let r = x + y;
    println(r);
    r

since the type signature of the library function println specifies that it is Impure.

The purity (or impurity) of a higher-order function may depend on the purity of its argument(s). For example, whether List.map is pure or impure depends on whether function we map is pure or impure. Fortunately Flix can model such behavior using effect polymorphism. For example:

def map(f: a -> b \ ef, l: List[a]): List[b] \ ef = ???

Here the signature of map captures that if the function argument f has type a -> b with effect ef then the effect of map itself is ef. This means that if map is called with a pure (resp. impure) function argument then the overall expression is pure (resp. impure). For example:

List.map(x -> x + 123, l)    // pure
List.map(x -> println(x), l) // impure

Design Note

The Flix standard library enforces several program invariants using purity. For example, in Flix, the Eq and Order type classes require that their operations are pure. This ensures that collections, such as lists, sets, and maps, do not leak internal implementation details.

Immutable Data

The bread-and-butter of functional programming is immutable data types.

We have already seen several examples of immutable data types:

• Primitive Types
• Tuple Types
• Enumerated, Recursive, and Polymorphic Types

In addition, The Flix standard library offers several immutable data types:

• List[t] : An immutable singly-linked list of elements of type t.
• Chain[t] : An immutable chain of elements of type t with fast append.
• Vector[t] : An immutable sequence of elements of type t with fast lookup.
• Set[t] : An immutable set of elements of type t.
• Map[k, v] : An immutable map of keys of type k to values of type v.

Other immutable data types include:

• Option[t] : A type that is either None or Some(t).
• Result[e, t] : A type that is either Ok(t) or Err(e).
• Nel[t] : An immutable non-empty singly-linked list of elements of type t.
• Nec[t] : An immutable non-empty sequence of elements of type t that supports fast append.
• MultiMap[k, v] : An immutable map of keys of type k to sets of values of type v.

Lists

A list is either the empty list, written as Nil, or a cons cell, written as x :: xs where x is the head element and xs is the tail of the list. The List type is polymorphic so you can have a list of integers, written as List[Int32], or a list of strings written as List[String].

We write the empty list as follows:

Nil

We can construct a list of strings with the strings "Hello" and "World" as follows:

"Hello" :: "World" :: Nil

Given a list there are many useful operations we can perform on it.

For example, we can compute the length of a list as follows:

List.length(1 :: 2 :: 3 :: Nil)

We can also reverse the order of elements in a list:

List.reverse(1 :: 2 :: 3 :: Nil)

We can append two lists using the List.append function as follows:

let xs = (1 :: 2 :: 3 :: Nil);
let ys = (4 :: 5 :: 6 :: Nil);
List.append(xs, ys)

Or, alternatively, we can use the built-in append operator ::: as follows:

let xs = (1 :: 2 :: 3 :: Nil);
let ys = (4 :: 5 :: 6 :: Nil);
xs ::: ys

Flix has an extensive collection of functions to operate on lists.

Here are some of the most common:

List.count(x -> x == 1, 1 :: 2 :: 3 :: Nil);
List.filter(x -> x == 1, 1 :: 2 :: 3 :: Nil);
List.map(x -> x + 1, 1 :: 2 :: 3 :: Nil);
List.foldLeft((x, y) -> x + y, 0, 1 :: 2 :: 3 :: Nil)

And here are some more exotic functions:

List.intersperse("X", "a" :: "b" :: "c" :: Nil)

which inserts "X" between every element in the list.

let l1 = "X" :: "Y" :: Nil;
let l2 = ("a" :: "b" :: Nil) :: ("c" :: "d" :: Nil) :: Nil;
List.intercalate(l1, l2)

which inserts the list l1 between every element in the list l2.

We can write our own recursive functions to operate on lists.

For example, here is an implementation of the map function:

///
/// Returns the result of applying `f` to every element in `l`.
/// That is, the result is of the form: `f(x1) :: f(x2) :: ...`.
///
pub def map(f: a -> b \ ef, l: List[a]): List[b] \ ef = match l {
    case Nil     => Nil
    case x :: xs => f(x) :: map(f, xs)
}

Chains and Vectors

In addition to immutable Lists, Flix also supports immutable Chains and Vectors.

The following table illustrates the performance trade-offs between lists, chains, and vectors:

When to use List, Chain, or Vector?:

• The List data structure should be the default choice as it is simple and well-known.
• The Vector data structure is an excellent choice when the size of a collection is fixed and/or when fast random access is required.
• The Chain data structure is more rarely used, but shines when fast appends are required.

Chains

A Chain[t] is an immutable linked sequence of elements.

The Chain[t] data type is defined as:

enum Chain[t] {
    case Empty
    case One(t)
    case Chain(Chain[t], Chain[t])
}

The data structure supports O(1) append because we can construct a new chain from two existing chains using the Chain constructor (or more appropriately using Chain.append).

We can build chains using Chain.empty, Chain.singleton, Chain.cons, and Chain.append.

For example, we can write:

let c = Chain.cons(1, Chain.empty());
println(c)

which prints Chain#{1} when compiled and executed.

Vectors

A Vector[t] is an immutable fixed-length sequence of contiguous elements of type t.

Flix has support for Vector literals. For example, we can write:

Vector#{1, 2, 3}

which creates a vector of length three with the elements: 1, 2, and 3.

Vectors support fast random access with the Vector.get operation:

let v = Vector#{1, 2, 3};
println(Vector.get(2, v))

which prints 3 when compiled and executed.

Warning: Indexing into a vector beyond its bounds will panic the program.

Vectors support many operations. For example, we can map a function over a vector:

let v = Vector#{1, 2, 3};
Vector.map(x -> x + 1, v)

evaluates to Vector#{2, 3, 4}.

Sets and Maps

Flix has excellent support for (immutable) Sets and Map based on balanced trees; hence the elements of a Set and the keys of Map must implement the Order type class.

Tip: The Flix Set and Map data structures will automatically parallelize certain operations. Such operations are marked with @ParallelWhenPure in the API docs.

Sets

The empty set is written as:

Set#{}

which is equivalent to Set.empty(). A set literal is written as:

Set#{1, 2, 3}

We can insert into a set using Set.insert (which returns a new set):

let s1 = Set#{1, 2, 3};
let s2 = Set.insert(4, s1);

We can determine if a set contains an element using Set.memberOf:

let s = Set#{1, 2, 3};
Set.memberOf(2, s)

We can merge two sets using Set.union:

let s1 = Set#{1, 2, 3};
let s2 = Set#{3, 4, 5};
let sr = Set.union(s1, s2);

Since Sets are SemiGroups, we can also use the ++ operator and write s1 ++ s2.

Maps

The empty map is written as:

Map#{}

which is equivalent to Map.empty(). A map literal is written as:

Map#{"a" => 1, "b" => 2, "c" => 3}

We can insert into a map using Map.insert (which returns a new map):

let m1 = Map#{"a" => 1, "b" => 2, "c" => 3};
let m2 = Map.insert("d", 4, m1);

We can lookup the value associated with a key using Map.get:

let m = Map#{"a" => 1, "b" => 2, "c" => 3};
Map.get("b", m) 

The Map.get function returns an Option[v].

We can merge two maps using one of Map.unionWith and Map.unionWithKey functions.

Records

Flix supports row polymorphic extensible records.

Flix records are immutable (but may contain mutable reference cells).

Record Literals

A record literal is written with curly braces:

{ x = 1, y = 2 }

which has the record type { x = Int32, y = Int32 }.

The order of labels in a record does not matter. Hence the above record is equivalent to:

{ y = 2, x = 1 }

which has type { y = Int32, x = Int32 }. This type is equivalent to { x = Int32, y = Int32 }. In other words, the order of labels within a record type does not matter.

Label Access

We can access the label of a record using a dot:

let p = { x = 1, y = 2 };
p.x + p.y

The type system ensures that we cannot access a label that does not exist.

Records are immutable. Once constructed, the values of the record labels cannot be changed.

Label Update

While records are immutable, we can construct a new record with an updated label value:

let p1 = { x = 1, y = 2 };
let p2 = { x = 3 | p1 };
p1.x + p2.x

The expression { x = 3 | p1 } updates the record p1 with a new value of its x label. Note that updating a label requires that the label exists on the record. A record cannot be updated with a new label, but it can be extended with a new label, as we shall see later.

Record Extension

We can add a new label to an existing record as follows:

let p1 = { x = 1, y = 2 };
let p2 = { +z = 3 | p1 };
p1.x + p1.y + p2.z

Here the expression { +z = 3 | p1 } extends the record p1 with a new label z such that the result has three labels: x, y, and z all of which are of Int32 type.

Record Restriction

Similarly to record extension, we can also remove a label from a record:

let p1 = { x = 1, y = 2 };
let p2 = { -y | p1 };

Here the record p2 has the same labels as p1 except that the y label has been removed.

Row Polymorphism: Open and Closed Records

A function may specify that it requires a record with two labels:

def f(r: {x = Int32, y = Int32}): Int32 = r.x + r.y

We can call this function with the records { x = 1, y = 2 } and { y = 2, x = 1 }, but we cannot call it with the record { x = 1, y = 2, z = 3 } since the signature of f demands a record with exactly two labels: x and y. We say that the record r is closed.

We can lift this restriction by using row polymorphism:

def g(r: {x = Int32, y = Int32 | s}): Int32 = r.x + r.y

We can call this function with any record as long as it has x and y labels which are of type Int32. We say that the record type of r is open.

Named Parameters with Records

When a function has multiple parameters that share the same type, it is easy to get confused about the right argument order. For example, what does String.contains("Hello","Hello World") return? What does String.contains("Hello World", "Hello") return?

A common solution to this problem is to use named parameters. Flix supports a form of named parameters building on records. For example, we can write a function translate to translate from one language to another as follows:

def translate(from: {from = Language}, to: {to = Language}, text: String): String = ???

We can call this function as follows:

translate({from = English}, {to = French}, "Where is the library?")

Since such verbosity gets tedious, we can also use the syntactic sugar:

translate(from = English, to = French, "Where is the library?")

which is equivalent to the above.

Mutable Data

Flix is a functional-first programming language that encourages but does not demand, the use of immutable data structures. While immutable data structures should be the default, Flix has rich support for imperative programming with destructive updates to mutable data.

Flix uses its effect system to separate pure and impure code. In particular, Flix uses the region concept to track the use of mutable memory. That is, all mutable memory belongs to some statically-scoped region.

Flix has two basic types of mutable memory:

• References
• Arrays

We can use references and arrays to build higher-level mutable data structures. For example, the Flix Standard Library offers collections such as MutList, MutDeque, MutSet, and MutMap. As a rule, these higher-level data structures should be preferred over lower-level references and arrays.

We begin this chapter with a discussion of regions.

Regions

Flix supports scoped mutable memory. In Flix, all mutable memory belongs to a region that is tied to its lexical scope. When execution leaves the lexical scope of a region, all memory in that region becomes unreachable.

Regions are useful because they enable us to implement pure functions that internally use mutation. We will illustrate this powerful idea with several real-world examples, but let us first discuss how to use a region:

We introduce a new region scope with the region construct:

region rc { // region starts.
  ...       // the region handle `rc` is in scope.
}           // region ends and all data associated with `rc` is no longer in scope.

We can use regions to implement a pure sort function that internally uses mutation:

def sort(l: List[a]): List[a] with Order[a] =
    region rc {
        let arr = List.toArray(rc, l);
        Array.sort!(arr);
        Array.toList(arr)
    }

Here we introduce a region named rc. We use the function List.toArray to convert the list l to a mutable array arr associated with the region rc. We then sort arr using Array.sort! which uses an efficient in-place sorting algorithm. Finally, we convert the sorted array back to a list and return it. The sort function is pure, even though it internally uses mutation.

As another example, we can implement a toString function for List[a] which is pure but internally uses a mutable StringBuilder:

def toString(l: List[a]): String with ToString[a] =
    region rc {
        let sb = StringBuilder.new(rc);
        List.forEach(x -> StringBuilder.appendString!("${x} :: ", sb), l);
        StringBuilder.appendString!("Nil", sb);
        StringBuilder.toString(sb)
    } // scope of rc ends, the entire expression is pure.

The programming pattern is the same: We open a new region, allocate a StringBuilder in the region, fill the builder with strings, and convert it into one string.

We can use regions to implement certain functional operations more efficiently. For example, here is a fast implementation of List.flatMap:

def flatMap(f: a -> List[b] \ ef, l: List[a]): List[b] \ ef =
    region rc {
        let ml = MutList.new(rc);
        l |> List.forEach(x -> MutList.append!(f(x), ml));
        MutList.toList(ml)
    }

Regions are Values

A region (or region handle) is a value that can be passed as a function argument. This is useful, for example, when we want to write a reusable function that allocates and returns a mutable data structure.

For example, here is the List.toMutDeque function:

def toMutDeque(rc: Region[r], l: List[a]): MutDeque[a, rc] \ rc =
    let d = MutDeque.new(rc);
    forEach(x -> MutDeque.pushBack(x, d), l);
    d

The function takes a region handle rc, allocates a new mutable deque (MutDeq) in the given region, inserts all elements of the list l in the deque, and returns it.

Regions are Scoped

Regions and all memory associated with them cannot outlive their lexical scope.

Consider the following program:

def main(): Unit \ IO = 
    let escaped = region rc {
        Array#{1, 2, 3} @ rc
    };
    println(escaped)

Here we allocate the Array#{1, 2, 3} in the region rc and try to return it outside of its enclosing scope. The Flix compiler detects such escape violations and reports an error:

❌ -- Type Error ----------------------------

>> The region variable 'rc' escapes its scope.

2 |>     let escaped = region rc {
3 |>         Array#{1, 2, 3} @ rc
4 |>     };

region variable escapes.

References

Flix supports mutable scoped references. A reference is a box whose value can change over time. The three key reference operations are:

• Creating a new reference ref e @ rc.
• Dereferencing a reference deref e.
• Assigning to a reference e := e.

In Flix, the type of a reference is Ref[t, r] where t is the type of the element and r is its region. Like all mutable memory in Flix, every reference must belong to some region. Reading from and writing to a reference are effectful operations. For example, reading the value of a reference Ref[t, r] has effect r.

The ref e @ rc operation allocates a reference cell in a region of the heap and returns its location, the deref operation dereferences a location and returns the content of a reference cell, and the assigment := operation changes the value of a reference cell. Informally, a reference cell can be thought of as an "object" with a single field that can be changed.

Allocating References

A reference cell is allocated with the ref e @ rc syntax. For example:

region rc {
    let c = ref 42 @ rc;
    println(deref c)
}

Here we introduce a region named rc. Inside the region, we create a reference cell called c with the value 42 which we then dereference and print.

Dereferencing References

A reference cell is accessed (dereferenced) with the deref e syntax. For example:

region rc {
    let c = ref 42 @ rc;
    let x = deref c;
    let y = deref c;
    println(x + y)
}

Here the program prints 42 + 42 = 84.

Assignment

We can update the value of a reference cell. For example:

region rc {
    let c = ref 0 @ rc;
    c := (deref c) + 1;
    c := (deref c) + 1;
    c := (deref c) + 1;
    println(deref c)
}

Here the program creates a reference cell c with the value 0. We dereference the cell and increment its value three times. Hence the program prints 3.

Example: A Simple Counter

We can use references to implement a simple counter:

enum Counter[r: Region] { // The Region here is a type-kind
    case Counter(Ref[Int32, r])
}

def newCounter(rc: Region[r]): Counter[r] \ r = Counter.Counter(ref 0 @ rc)

def getCount(c: Counter[r]): Int32 \ r =
    let Counter.Counter(l) = c;
    deref l

def increment(c: Counter[r]): Unit \ r =
    let Counter.Counter(l) = c;
    l := (deref l) + 1

def main(): Unit \ IO =
    region rc {
        let c = newCounter(rc);
        increment(c);
        increment(c);
        increment(c);
        getCount(c) |> println
    }

Here the Counter data type has a region type parameter. This is required since the counter internally uses a reference that requires a region. Hence Counters are also scoped. Note that the newCounter function requires a region handle to create a new Counter. Moreover, note that the functions getCount and increment both have the r effect.

Aliasing and References to References

References naturally support aliasing since that is their purpose. For example:

region rc {
    let l1 = ref 42 @ rc;
    let l2 = l1;
    l2 := 84;
    println(deref l1)
}

Prints 84 because the reference cell that l1 points to is modified through the alias l2.

References can also point to references as the following example illustrates:

region rc {
    let l1 = ref 42 @ rc;
    let l2 = ref l1 @ rc;
    let rs = deref (deref l2);
    println(rs)
}

Here the type of l2 is Ref[Ref[Int32, rc], rc].

Mutable Tuples and Records

Flix tuples and records are immutable. However, tuples and records may contain mutable references.

For example, here is a pair that contains two mutable references:

region rc {
    let p = (ref 1 @ rc, ref 2 @ rc);
    fst(p) := 123
};

The type of the pair is (Ref[Int32, rc], Ref[Int32, rc]). The assignment does not change the pair but instead changes the value of the reference cell in the first component.

Similarly, here is a record that contains two mutable references:

region rc {
    let r = { fstName = ref "Lucky" @ rc, lstName = ref "Luke" @ rc };
    r.fstName := "Unlucky"
};

The type of the record is { fstName = Ref[String, rc], lstName = Ref[String, rc] }. Again, the assignment does not change the record, but instead changes the value of the reference cell corresponding to the fstName label.

Arrays

Flix supports mutable scoped arrays. An array is a fixed-length mutable sequence of elements that share the same type. Arrays are laid out consecutively in memory. Arrays are mutable; hence their elements can change over time. However, once created, the length of an array cannot be changed.

In Flix, the type of an array is Array[t, r] where t is the type of its elements and r is its region. Like all mutable memory in Flix, every array must belong to some region. Reading from and writing to arrays are effectful operations. For example, reading an element from an array of type Array[t, r] has the effect r. Likewise, creating an array in a region is also an effectful operation.

Arrays are always unboxed. For example, an array of type Array[Int32, r] is represented as a sequence of primitive 32-bit integers, i.e., in JVM terminology, the array is represented as int[]. Flix will never box primitive integers as java.lang.Integer objects but still permits primitives in generic collections and functions. The same is true for other types of primitives and arrays of primitives.

Arrays are low-level data structures typically used to implement higher-level data structures. Therefore, unless implementing such data structures, we recommend that arrays are used sparingly. Instead, we recommend using the MutList, MutDeque, MutSet, and MutMap data structures.

Hint: Use MutList if you need a growable mutable sequence of elements.

Array Literals

The syntax of an array literal is of the form Array#{e1, e2, e3, ...} @ r where e1, e2, and so forth are element expressions, and r is the region expression. For example:

region rc {
    let fruits = Array#{"Apple", "Pear", "Mango"} @ rc;
    println(Array.toString(fruits))
}

Here we introduce a region named rc. Inside the region, we create an array of fruits that contain the three strings "Apple", "Pear", and "Mango". The type of fruits is Array[String, rc]. For more information about regions, we refer to the chapter on Regions.

Running the program prints Array#{"Apple", "Pear", "Mango"}.

Allocating Arrays

We can allocate an array of size n filled with the same element using the Array.repeat function. For example:

region rc {
    let arr = Array.repeat(rc, 1_000, 42);
    println(Array.toString(arr))
}

Here we create an array arr of length 1_000 where each array element has the value 42. Note that we must pass the region rc as an argument to Array.repeat because the function must know to which region the returned array should belong.

We can also create an array filled with all integers from zero to ninety-nine:

region rc {
    let arr = Array.range(rc, 0, 100);
    println(Array.toString(arr))
}

Moreover, we can convert most data structures to arrays. For example:

region rc {
    let fruitList = List#{"Apple", "Pear", "Mango"};
    let fruitArray = List.toArray(rc, fruitList);
}

Note that we must pass the region rc as an argument to List.toArray since the function must know to which region the returned array should belong.

Allocating Arrays with Uninitialized Elements

We can use the Array.new function to create an array of a given length where the content of the array is uninitialized. For example:

region rc {
    let arr: Array[String, rc] = Array.new(rc, 100);
    // ... initialize `arr` here ...
}

Here we create an array of length 100 of type Array[String, rc]. We use an explicit type annotation : Array[String, rc] to inform Flix of the expected type of the array.

Warning: It is dangerous to use arrays that have uninitialized elements.

What are the elements of an uninitialized array? Flix follows Java (and the JVM) which defines a default value for every primitive-- and reference type. So, for example, the default values for Bool and Int32 are false and 0, respectively. The default value for reference types are null. So be careful! Flix does not have a null value, but one can be indirectly introduced by reading from improperly initialized arrays which can lead to NullPointerExceptions.

Reading from and Writing to Arrays

We can retrieve or update the element at a specific position in an array using Array.get and Array.put, respectively. For example:

region rc {
    let strings = Array.new(rc, 2);
    Array.put("Hello", 0, strings);
    Array.put("World", 1, strings);
    let s1 = Array.get(0, strings);
    let s2 = Array.get(1, strings);
    println("${s1} ${s2}")
}

Here we create an empty array of length of two. We then store the string "Hello" at position zero and the string "World" at position one. Next, we retrieve the two strings, and print them. Thus the program, when compiled and run, prints Hello World.

We can also write part of the program in a more fluent-style using the !> pipeline operator:

let strings = 
    Array.new(rc, 2) !>
    Array.put("Hello", 0) !>
    Array.put("World", 1);

Slicing Arrays

We can slice arrays using Array.slice. A slice of an array is a new (shallow) copy of a sub-range of the original array. For example

region rc {
    let fruits = Array#{"Apple", "Pear", "Mango"} @ rc;
    let result = Array.slice(rc, start = 1, end = 2, fruits);
    println(Array.toString(result))
}

which prints Array#{"Pear"} when run.

Taking the Length of an Array

We can compute the length of an array using the Array.length function. For example

region rc {
    let fruits = Array#{"Apple", "Pear", "Mango"} @ rc;
    println(Array.length(fruits))
}

which prints 3 when run.

Note: We advise against indexed-based iteration through arrays. Instead, we recommend to use functions such as Array.count, Array.forEach, and Array.transform!.

Additional Array Operations

The Array module offers an extensive collection of functions for working with arrays. For example, Array.append, Array.copyOfRange, Array.findLeft, Array.findRight, Array.sortWith!, and Array.sortBy! to name a few. In total, the module offers more than 100 functions ready for use.

Mutable Collections

The Flix standard library supports many immutable collections, including options, lists, chains, sets, and maps. We strongly encourage their use.

In addition, the Flix standard library also offers several mutable collections:

• MutList[t, r] : a contiguous growable/shrinkable array of elements of type t.
• MutSet[t, r] : a mutable set of elements of type t.
• MutMap[k, v, r] : a mutable map of keys of type k to values of type v.
• MutDeque[t, r] : a mutable double-ended queue of elements of type t.

Recall that in Flix all mutable memory, including mutable collections, belongs to a region.

Here is an example of how to use MutList[t]:

def main(): Unit \ IO = 
    region rc {
        let fruits = MutList.new(rc);
        MutList.push!("Apple", fruits);
        MutList.push!("Pear", fruits);
        MutList.push!("Mango", fruits);
        MutList.forEach(println, fruits)
    }

which prints Apple, Pear, and Mango. Here the MutList[String, rc] automatically expands (and shrinks) as elements are pushed (or popped) from it.

We can write the above program in a more fluent-style using the !> pipeline operator:

def main(): Unit \ IO = 
    region rc {
        let fruits = 
            MutList.new(rc) !> 
            MutList.push!("Apple") !> 
            MutList.push!("Pear") !>
            MutList.push!("Mango");
        MutList.forEach(println, fruits)
    }

We can split the above program into several functions as follows:

def main(): Unit \ IO = 
    region rc {
        let fruits = sweetFruits(rc);
        printFruits(fruits)
    }

def sweetFruits(rc: Region[r]): MutList[String, r] \ r = 
    MutList.new(rc) !> 
    MutList.push!("Apple") !> 
    MutList.push!("Pear") !>
    MutList.push!("Mango")

def printFruits(fruits: MutList[String, r]): Unit \ {r, IO} = 
    MutList.forEach(println, fruits)

Here the main function introduces a new region rc. We pass this region to sweetFruits which creates and returns a new mutable list of fruits. Note that sweetFruits has the effect r since it allocates mutable memory using rc. The printFruits takes a mutable list of fruits and prints them. Note that this function has effect r since it reads from mutable memory in r and it has effect IO since it prints to the terminal.

Control Structures

Flix — being a functional programming language — has few control-structures. Most control is simply function application. The Flix control structures are:

• If-Then-Else: A traditional if-then-else expression.
• Pattern Matching: A functional construct for taking apart algebraic data types.
• Foreach: An imperative construct for iteration through collections.
• Foreach-Yield: An imperative construct for building new collections from existing collections.
• Monadic For-Yield: A functional construct for monadic operations, similar to Scala's for-comprehensions and Haskell's do-notation.
• Applicative For-Yield: A functional construct for applicative operations, similar to Haskell's applicative do-notation.

What's the difference between foreach, foreach-yield, monadic forM, and applicative forA?:

The following table gives some uses cases for each construct:

Note: Flix does not have traditional while or for-loops. Instead, we recommend the use recursion and/or one of the above constructs.

If-then-else

Flix supports the usual if-then-else expression:

if (1 == 1) "Hello" else "World"

which evaluates to Hello.

But if guards are also supported in other parts of the language.

Guarded Pattern Matches

We can use an if-guard in a pattern match:

def isSquare(s: Shape): Bool = match s {
    case Rectangle(h, w) if h == w => true
    case _                         => false
}

Guarded Datalog Rules

We can use an if-guard in a Datalog rule:

Path(x, z) :- Path(x, y), Edge(y, z), if x != z.

Pattern Matching

Matching on Enums

Flix supports pattern matching on algebraic data types.

For example, if we have an algebraic data type that models shapes:

enum Shape {
    case Circle(Int32)
    case Square(Int32)
    case Rectangle(Int32, Int32)
}

Then we can write a function to compute the area of a Shape using pattern matching:

def area(s: Shape): Int32 = match s {
    case Shape.Circle(r)       => 3 * (r * r)
    case Shape.Square(w)       => w * w
    case Shape.Rectangle(h, w) => h * w
}

Let Pattern Match

In addition to the pattern match construct, a let-binding can be used to destruct a value. For example:

let (x, y, z) = (1, 2, 3)

Binds the variables x, y, and z to the values 1, 2, and 3, respectively.

Any exhaustive pattern may be used in a let-binding. For example:

let (x, Foo(y, z)) = (1, Foo(2, 3))

is legal provided that the Foo constructor belongs to a type where it is the only constructor.

The following let-bindings are illegal because they are not exhaustive:

let (1, 2, z) = ...
let Some(x) = ...

The Flix compiler will reject such non-exhaustive patterns.

Match Lambdas

Pattern matches can also be used with lambda expressions. For example:

List.map(match (x, y) -> x + y, (1, 1) :: (2, 2) :: Nil)

is equivalent to:

List.map(w -> match w { case (x, y) => x + y }, (1, 1) :: (2, 2) :: Nil)

As for let-bindings, such pattern matches must be exhaustive.

Note the difference between the two lambda expressions:

let f = (x, y, z) -> x + y + z + 42i32
let g = match (x, y, z) -> x + y + z + 42i32

Here f is a function that expects three Int32 arguments, whereas g is a function that expects one three tuple (Int32, Int32, Int32) argument.

Foreach

Flix supports a traditional foreach construct that enables imperative iteration through collections.

We typically use the foreach construct when we want to iterate through one or more collections and execute an effectful operation for each of their elements.

For example, the program:

def main(): Unit \ IO = 
    let fruits = List#{"Apple", "Pear", "Mango"};
    foreach(fruit <- fruits) 
        println(fruit)

Prints the strings Apple, Pear, and Mango.

We can also iterate through multiple collections:

def main(): Unit \ IO = 
    let fruits = List#{"Apple", "Pear", "Mango"};
    let creams = List#{"Vanilla", "Stracciatella"};
    foreach(fruit <- fruits) 
        foreach(cream <- creams)
            println("Would you like some ${fruit} with ${cream} icecream?")

The same loop can also be written:

def main(): Unit \ IO = 
    let fruits = List#{"Apple", "Pear", "Mango"};
    let creams = List#{"Vanilla", "Stracciatella"};
    foreach(fruit <- fruits; cream <- creams) 
        println("Would you like some ${fruit} with ${cream} icecream?")

We can also write loops with a filter. For example:

def main(): Unit \ IO = 
    let fruits = List#{"Apple", "Pear", "Mango"};
    let creams = List#{"Vanilla", "Stracciatella"};
    foreach(fruit <- fruits; if isExcotic(fruit); cream <- creams) 
        println("Would you like some ${fruit} with ${cream} icecream?")

def isExcotic(fruit: String): Bool = match fruit {
    case "Mango" => true
    case _       => false
}

Adding Optional Braces for Visual Clarity

We can sometimes improve the visual clarity of a foreach expression by adding braces:

foreach(fruit <- fruits) {
    foreach(cream <- creams) {
        println("Would you like some ${fruit} with ${cream} icecream?")
    }
}

The braces have no impact on the meaning of the foreach loop; they are purely stylistic.

The Iterable Type Class

We can use the foreach syntax to iterate through any collection type that implements the Iterable type class. In particular, the Iterable class defines a single signature:

///
/// A type class for immutable data structures that can be iterated.
///
pub class Iterable[t: Type -> Type] {
    ///
    /// Returns an iterator over `t`.
    ///
    pub def iterator(rc: Region[r], t: t[a]): Iterator[a, r, r] \ r
}

Note: Flix expects the expression body of a foreach to have type Unit. If you want to return a value from the loop body, you should use the foreach-yield construct.

Foreach-Yield

Flix supports a special foreach-yield construct which is used to build collections from other collections. The foreach-yield construct is related to the foreach construct, but should not be confused with it. The foreach construct is for effectful iteration through collections whereas the foreach-yield construct is for building new collections.

We can use the foreach-yield construct to build a new collection from existing collections. For example:

def main(): Unit \ IO = 
    let fruits = List#{"Apple", "Pear", "Mango"};
    let creams = List#{"Vanilla", "Stracciatella"};
    let result: Set[(String, String)] =
        foreach(fruit <- fruits; cream <- creams)
            yield (fruit, cream);
    println(result)

Here we construct a Set[(String, String)] from two List[String]. The type of the resulting collection is typically inferred, but in this case we have placed an explicit type annotation on the result local variable to specify it.

We can use the foreach-yield construct with several different types of collections. For example:

def main(): Unit \ IO = 
    let c1 = Some(1);
    let c2 = Set#{1, 2, 3};
    let c3 = List#{1, 2, 3};
    let result: Set[Int32] =
        foreach(x <- c1; y <- c2; z <- c3)
            yield x + y + z;
    println(result)

Here we iterate through three collections c1, c2, and c3 and return a set of the sums of their pairwise combinations.

The Collectable Type Class

The workhorse behind the foreach-yield construct is the Iterable type class (discussed in the previous section) and the Collectable type class.

pub class Collectable[m: Type -> Type] {
    ///
    /// Run an Iterator collecting the results.
    ///
    pub def collect(iter: Iterator[a, r]): m[a] \ r with Order[a]
}

Without going into details, the Collectable type class is implemented by all kinds of collections that can be constructed from an iterator. Notably, this includes the List, Chain, and Set data types.

Note: We cannot collect into a non-empty chain (Nec) or non-empty list (Nel) since we cannot guarantee that an Iterator is non-empty.

Note: The foreach-yield construct can only collect into immutable collections. If we want to build a mutable collection, we should explicitly introduce its region, allocate the mutable collection, and add each element using a regular foreach-loop.

Monadic For-Yield

Flix supports a monadic forM-yield construct similar to Scala's for-comprehensions and Haskell's do notation. The forM construct is syntactic sugar for uses of point and flatMap (which are provided by the Monad type class). The forM construct also supports a guard-expression that uses empty (which is provided by the MonadZero type class).

For example, the monadic forM expression:

let l1 = 1 :: 2 :: Nil;
let l2 = 1 :: 2 :: Nil;
forM (x <- l1; y <- l2)
    yield (x, y)

evaluates to the list:

(1, 1) :: (1, 2) :: (2, 1) :: (2, 2) :: Nil

Using Guard Expressions

We can use guard expressions in forM expressions. For example, the program:

let l1 = 1 :: 2 :: Nil;
let l2 = 1 :: 2 :: Nil;
forM (x <- l1; y <- l2; if x < y)
    yield (x, y)

evaluates to the list:

(1, 2) :: Nil

Working with Options and Results

We can also use forM to work with the Option data type. For example:

def divide(x: Int32, y: Int32): Option[Int32] = 
    if (y == 0) None else Some(x / y)

def f(): Option[Int32] = 
    forM (
        x <- divide(5, 2);
        y <- divide(x, 8);
        z <- divide(9, y)
    ) yield x + y + z

Here the function f returns None since x = 5 / 2 = 2 and 2 / 8 = 0 hence the last division fails.

Similarly, we can use forM to work with the Result[e, t] data type. For example:

def main(): Result[String, Unit] \ IO = 
    println("Please enter your first name, last name, and age:");
    forM (
        fstName <- Console.readLine();
        lstName <- Console.readLine();
        ageLine <- Console.readLine();
        ageNum  <- Int32.parse(10, ageLine)
    ) yield {
        println("Hello ${lstName}, ${fstName}.");
        println("You are ${ageNum} years old!")
    }

Here main prompts the user to enter their first name, last name, and age. Each call to Console.readLine returns a Result[String, String] value which is either an error or the input string. Thus the local variables fstName, lstName, and ageLine are Strings. We parse ageLine into an Int32 using Int32.parse, which returns a Result[String, Int32] value. If every operation is successful then we print a greeting and return Ok(()) (i.e., Ok of Unit). Otherwise, we return an Err(msg) value.

Working with Other Monads

We can use forM with other types of Monads, including Chain and Nels (non-empty lists). For example, we can write:

let l1 = Nel(1, 2 :: Nil);
let l2 = Nel(1, 2 :: Nil);
forM (x <- l1; y <- l2)
    yield (x, y)

which evaluates to the non-empty list:

Nel((1, 1), (1, 2) :: (2, 1) :: (2, 2) :: Nil)

Note: We cannot use an if-guard with non-empty lists because such an if-guard requires an instance of the MonadZero type class which is not implemented by non-empty list (since such a list cannot be empty).

Desugaring

The forM expression is syntactic sugar for uses of Monad.flatMap, Applicative.point, and MonadZero.empty.

For example, the expression:

let l1 = 1 :: 2 :: Nil;
let l2 = 1 :: 2 :: Nil;
forM (x <- l1; y <- l2; if x < y)
    yield (x, y)

is de-sugared to:

Monad.flatMap(x -> 
    Monad.flatMap(y -> 
        if (x < y)
            Applicative.point((x, y))
        else 
            MonadZero.empty(), 
    l2), 
l1);

Applicative For-Yield

In addition to the monadic forM expression, Flix supports an applicative forA expression that builds on the Applicative type class. The forA construct makes it simple to write error-handling code which uses the Validation[e, t] data type.

Working with Validations

We can use the forA expression to validate user input while collecting all errors.

enum Connection(String, String)

enum InvalidInput {
    case InvalidUserName,
    case InvalidPassword
}

def validateUser(s: String): Validation[InvalidInput, String] =
    if (8 <= String.length(s) and String.forAll(Char.isLetter, s))
        Validation.Success(s)
    else 
        Validation.Failure(Nec.singleton(InvalidInput.InvalidUserName))

def validatePass(s: String): Validation[InvalidInput, String] =
    if (12 <= String.length(s) and String.length(s) <= 20)
        Validation.Success(s)
    else 
        Validation.Failure(Nec.singleton(InvalidInput.InvalidPassword))

def connect(u: String, p: String): Validation[InvalidInput, Connection] = 
    forA (
        user <- validateUser(u);
        pass <- validatePass(p)
    ) yield Connection.Connection(user, pass)

The expression:

connect("Lucky Luke", "Ratata")

evaluates to:

Failure(Nec#{InvalidUserName, InvalidPassword})

which contains both input validation errors. On the other hand, the expression:

connect("luckyluke", "password12356789")

evaluates to:

Success(Connection(luckyluke, password12356789))

Applicatives are Independent Computations

We can write a monadic forM expression where the result of one monadic operation is used as the input to another monadic operation. For example:

forM(x <- Some(123);  y <- Some(x)) 
    yield (x, y)

Here the value of y depends on x. That is, the computation of x and y are not independent.

If we try to same with the applicative forA expression:

forA(x <- Some(123); y <- Some(x))
    yield (x, y)

then the Flix compiler emits a compiler error:

❌ -- Resolution Error --------------

>> Undefined name 'x'.

10 |         y <- Some(x)
                       ^
                       name not found

because the computations of x and y are independent and hence the value of x is not in scope when we define the value of y.

Desugaring

The forA expression is syntactic sugar for uses of Functor.map and Applicative.ap.

For example, the expression:

let o1 = Some(21);
let o2 = Some(42);
forA(x <- o1; y <- o2) 
    yield x + y;

is de-sugared to:

Applicative.ap(Functor.map(x -> y -> x + y, o1), o2)

Structured Concurrency

Flix supports CSP-style concurrency with channels and processes inspired by Go and Rust.

Spawning Processes

We can spawn a process with the spawn keyword:

def main(): Unit \ IO = region rc {
    spawn println("Hello from thread") @ rc;
    println("Hello from main")
}

Spawned processes are always associated with a region; the region will not exit until all the processes associated with it have completed:

def slowPrint(delay: Int32, message: String): Unit \ IO =
    Thread.sleep(Time/Duration.fromSeconds(delay));
    println(message)

def main(): Unit \ IO = 
    region r1 {
        region r2 {
            spawn slowPrint(2, "Hello from r1") @ r1;
            spawn slowPrint(1, "Hello from r2") @ r2
        };
        println("r2 is now complete")
    };
    println("r1 is now complete")

This means that Flix supports structured concurrency; spawned processes have clearly defined entry and exit points.

Communicating with Channels

To communicate between processes we use channels. A channel allows two or more processes to exchange data by sending immutable messages to each other.

A channel comes in one of two variants: buffered or unbuffered. Channels are always associated with a region.

A buffered channel has a size, set at creation time, and can hold that many messages. If a process attempts to put a message into a buffered channel that is full, then the process is blocked until space becomes available. If, on the other hand, a process attempts to get a message from an empty channel, the process is blocked until a message is put into the channel.

An unbuffered channel works like a buffered channel of size zero; for a get and a put to happen both processes must rendezvous (block) until the message is passed from sender to receiver.

Here is an example of sending and receiving a message over a channel:

def main(): Int32 \ IO = region rc {
    let (tx, rx) = Channel.unbuffered(rc);
    spawn Channel.send(42, tx) @ rc;
    Channel.recv(rx)
}

Here the main function creates an unbuffered channel which returns Sender tx and a Receiver rx channels, spawns the send function, and waits for a message from the channel.

As the example shows, a channel consists of two end points: the Sender and the Receiver. As one would expect, messages can only be send using the Sender, and only received using the Receiver.

Selecting on Channels

We can use the select expression to receive a message from a collection of channels. For example:

def meow(tx: Sender[String, r]): Unit \ { Write(r) } = 
    Channel.send("Meow!", tx)

def woof(tx: Sender[String, r]): Unit \ { Read(r), Write(r) } = 
    Channel.send("Woof!", tx)

def main(): Unit \ IO = region rc {
    let (tx1, rx1) = Channel.buffered(rc, 1);
    let (tx2, rx2) = Channel.buffered(rc, 1);
    spawn meow(tx1) @ rc;
    spawn woof(tx2) @ rc;
    select {
        case m <- recv(rx1) => m
        case m <- recv(rx2) => m
    } |> println
}

Many important concurrency patterns such as producer-consumer and load balancers can be expressed using the select expression.

Selecting with Default

In some cases, we do not want to block until a message arrives, potentially waiting forever. Instead, we want to take some alternative action if no message is readily available. We can achieve this with a default case as shown below:

def main(): String = region rc {
    let (_, rx1) = Channel.buffered(rc, 1);
    let (_, rx2) = Channel.buffered(rc, 1);
    select {
        case _ <- recv(rx1) => "one"
        case _ <- recv(rx2) => "two"
        case _             => "default"
    }
}

Here a message is never sent to r1 nor r2. The select expression tries all cases, and if no channel is ready, it immediately selects the default case. Hence using a default case prevents the select expression from blocking forever.

Selecting with Timeouts

As an alternative to a default case, we can use tickers and timers to wait for pre-defined periods of time inside a select expression.

For example, here is a program that has a slow function that takes a minute to send a message on a channel, but the select expression relies on Channel.timeout to only wait 5 seconds before giving up:

def slow(tx: Sender[String, r]): Unit \ { Write(r), IO} =
    Thread.sleep(Time/Duration.fromSeconds(60));
    Channel.send("I am very slow", tx)

def main(): Unit \ IO = region rc {
    let (tx, rx) = Channel.buffered(rc, 1);
    spawn slow(tx) @ rc;
    let timeout = Channel.timeout(rc, Time/Duration.fromSeconds(5));
    select {
        case m <- recv(rx)       => m
        case _ <- recv(timeout)  => "timeout"
    } |> println
}

This program prints the string "timeout" after five seconds.

Parallelism

We have seen how the spawn expression allows us to evaluate an expression in a new thread:

region rc {
    spawn (1 + 2) @ rc
}

This allows us to write concurrent and parallel programs using structured concurrency. The downside is that we must manually coordinate communication between threads using channels. If we want parallelism, but not concurrency, a more light-weight approach is to use the par-yield expression:

par (x <- e1; y <- e2; z <- e3)
    yield x + y + z

which evaluates e1, e2, and e3 in parallel and binds their results to x, y, and z.

We can use par-yield to write a parallel List.map function:

def parMap(f: a -> b, l: List[a]): List[b] = match l {
    case Nil     => Nil
    case x :: xs =>
        par (r <- f(x); rs <- parMap(f, xs))
            yield r :: rs
}

This function will evaluate f(x) and parMap(f, xs) in parallel.

Note: The par-yield construct only works with pure expressions.

If you want to run effectful operations in parallel, you must use explicit regions and threads.

Effect System

The Flix type and effect system separates pure and impure expressions. A pure expression is guaranteed to be referentially transparent. A pure function always returns the same value when given the same argument(s) and cannot have any (observable) side-effects.

For example, the following expression is of type Int32 and is pure (marked with \ {}):

1 + 2 : Int32 \ {}

whereas the following expression is impure (marked with \ IO):

println("Hello World") : Unit \ IO

A higher-order function can specify that a function argument must be pure, impure, or that it is effect polymorphic.

For example, the definition of Set.exists requires that its function argument f is pure:

// The syntax a -> Bool is short-hand for a -> Bool \ {}
def exists(f: a -> Bool, s: Set[a]): Bool = ???

The requirement that f must be pure ensures that implementation details do not leak. For example, since f is pure it cannot be used to determine in what order the elements of the set are traversed. If f was impure such details could leak, e.g. by passing a function that also prints the current element, revealing the internal element order inside the set.

The type and effect system is sound, but not complete. That is, if a function is pure then it cannot cause an effect, whereas if a function is impure then it may, but does not necessarily, cause an effect. For example, the following expression is impure even though it cannot produce an effect at run-time:

if (1 == 2) println("Hello World!") else ()

A higher-order function can also be effect polymorphic: its effect(s) can depend on its argument(s).

For example, the standard library definition of List.map is effect polymorphic:

def map(f: a -> b \ ef, xs: List[a]): List[b] \ ef

The List.map function takes a function f from elements of type a to b with effect ef. The effect of the function itself is ef. Consequently, if List.map is invoked with a pure function then the entire expression is pure whereas if it is invoked with an impure function then the entire expression is impure.

A higher-order function that takes multiple function arguments may combine their effects.

For example, the standard library definition of forward function composition >> is pure if both its function arguments are pure:

def >>(f: a -> b \ ef1, g: b -> c \ ef2): a -> c \ { ef1, ef2 } = x -> g(f(x))

The type and effect signature can be understood as follows: The >> function takes two function arguments: f with effect ef1 and g with effect ef2. The effect of >> is effect polymorphic in the conjunction of ef1 and ef2. If both are pure (their effect is true) then the overall expression is pure (true). Otherwise it is impure.

The type and effect system allows arbitrary boolean expressions to control the purity of function arguments.

For example, it is possible to express a higher-order function h that accepts two function arguments f and g of which at most one is impure:

def h(f: a -> b \ ef1, g: b -> c \ { (not ef1) or ef2 }): Unit

Note that here ef1 and ef2 are arbitrary boolean variables which are not directly associated with the effect of f or g (like it was the case in the simpler example above). In general, the possible effects for argument functions and the to-be-defined function are described by arbitrary boolean expressions. Here the possible effects of g (whether it can be pure or impure) are specified by the boolean not ef1 or ef2. For a specific combination of pure and impure to be accepted, there must be an assignment of the boolean variables ef1 and ef2 to true and false such that the boolean expressions for pure arguments evaluate to true and those for impure arguments evaluate to false.

If in this example h is called with a function argument f which is impure, then the variable ef1 must be false and thus the second argument must be pure (because not ef1 or ef2 will always be true, no matter how we choose ef2). Conversely, if f is pure, then ef1 must be true and g may be pure (ef2 = true) or impure (ef2 = false). It is a compile-time error to call h with two impure functions.

The type and effect system can be used to ensure that statement expressions are useful, i.e. that if an expression or function is evaluated and its result is discarded then it must have a side-effect. For example, compiling the program fragment below:

List.map(x -> x + 1, 1 :: 2 :: Nil);
123

causes a compiler error:

-- Redundancy Error -------------------------------------------------- ???

>> Useless expression: It has no side-effect(s) and its result is discarded.

2 |     List.map(x -> x + 1, 1 :: 2 :: Nil);
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
useless expression.


Possible fixes:

(1)  Use the result computed by the expression.
(2)  Remove the expression statement.
(3)  Introduce a let-binding with a wildcard name.

because it is non-sensical to evaluate the pure expression List.map(x -> 2 * x, 1 :: 2 :: Nil) and then to discard its result. Most likely the programmer wanted to use the result (or alternatively the expression is redundant and could be deleted). Consequently, Flix rejects such programs.

In summary, Flix function types are of the form:

Modules

Flix supports hierarchical modules as known from many other programming languages.

Declaring and Using Modules

We declare modules using the mod keyword followed by the namespace and name of the module.

For example, we can declare a module:

mod Math {
    pub def sum(x: Int32, y: Int32): Int32 = x + y
}

Here we have declared a module called Math with a function called sum inside it. We can refer to the sum function, from outside of its module, using its fully-qualified name:

def main(): Unit \ IO = 
    let result = Math.sum(123, 456);
    println(result)

Alternatively, we can bring the sum function into local scope with use:

def main(): Unit \ IO = 
    use Math.sum;
    let result = sum(123, 456);
    println(result)

Using Multiple Declarations from a Module

If we have multiple declarations in a module:

mod Math {
    pub def sum(x: Int32, y: Int32): Int32 = x + y
    pub def mul(x: Int32, y: Int32): Int32 = x * y
}

We can, of course, use each declaration:

use Math.sum;
use Math.mul;

def main(): Unit \ IO =
    mul(42, 84) |> sum(21) |> println

but a shorter way is to group the uses together into one:

use Math.{sum, mul};

def main(): Unit \ IO =
    mul(42, 84) |> sum(21) |> println

Note: Flix does not support wildcard uses since they can lead to subtle bugs.

Avoiding Name Clashes with Renaming

We can use renaming to avoid name clashes between identically named declarations.

For example, if we have two modules:

mod A {
    pub def concat(x: String, y: String): String = x + y
}

mod B {
    pub def concat(xs: List[Int32], ys: List[Int32]): List[Int32] = xs ::: ys
}

We can then use each concat function under a unique name. For example:

use A.{concat => concatStrings}
use B.{concat => concatLists}

def main(): Unit \ IO =
    concatStrings("Hello", " World!") |> println

While this feature is powerful, in many cases using a fully-qualified might be more appropriate.

Modules and Enums

We can define an enum inside a module. For example:

mod Zoo {
    pub enum Animal {
        case Cat,
        case Dog,
        case Fox
    }
}

Here the Zoo module contains an enum type named Animal which has three cases: Cat, Dog, and Fox.

We can access the type and the cases using their fully-qualified names:

def says(a: Zoo.Animal): String = match a {
    case Zoo.Animal.Cat => "Meow"
    case Zoo.Animal.Dog => "Woof"
    case Zoo.Animal.Fox => "Roar"
}

def main(): Unit \ IO = 
    println("A cat says ${says(Zoo.Animal.Cat)}!")

Alternatively, we can use both the Animal type and its cases:

use Zoo.Animal
use Zoo.Animal.Cat
use Zoo.Animal.Dog
use Zoo.Animal.Fox

def says(a: Animal): String = match a {
    case Animal.Cat => "Meow"
    case Animal.Dog => "Woof"
    case Animal.Fox => "Roar"
}

def main(): Unit \ IO = 
    println("A cat says ${says(Cat)}!")

Note that use Zoo.Animal brings the Animal type into scope, whereas use Zoo.Animal.Cat brings the Cat case into scope.

Modules and Type Classes

We can also define a type class inside a module. The mechanism is similar to enums inside modules.

For example, we can write:

mod Zoo {
    pub class Speakable[t] {
        pub def say(x: t): String
    }
}

enum Animal with ToString {
    case Cat,
    case Dog,
    case Fox
}

instance Zoo.Speakable[Animal] {
    pub def say(a: Animal): String = match a {
        case Cat => "Meow"
        case Dog => "Woof"
        case Fox => "Roar"
    }
}

We can use fully-qualified names to write:

def speak(x: t): Unit \ IO with Zoo.Speakable[t], ToString[t] = 
    println("A ${x} says ${Zoo.Speakable.say(x)}!")

def main(): Unit \ IO = 
    speak(Animal.Cat)

Or we can use the Zoo.Speakable type class and the Zoo.Speakable.say function:

use Zoo.Speakable
use Zoo.Speakable.say

def speak(x: t): Unit \ IO with Speakable[t], ToString[t] = 
    println("A ${x} says ${say(x)}!")

Declaring Modules

As we have already seen, modules can be declared using the mod keyword:

mod Museum {
    // ... members ...
}

We can nest modules inside other modules:

mod Museum {
    mod Entrance {
        pub def buyTicket(): Unit \ IO = 
            println("Museum.Entrance.buyTicket() was called.")
    }

    mod Restaurant {
        pub def buyMeal(): Unit \ IO = 
            println("Museum.Restaurant.buyMeal() was called.")
    }

    mod Giftshop {
        pub def buyGift(): Unit \ IO = 
            println("Museum.Giftshop.buyGift() was called.")
    }
}

We can call these methods as follows:

def main(): Unit \ IO = 
    Museum.Entrance.buyTicket();
    Museum.Restaurant.buyMeal();
    Museum.Giftshop.buyGift()

Or alternatively as follows:

use Museum.Entrance.buyTicket;
use Museum.Restaurant.buyMeal;
use Museum.Giftshop.buyGift;
def main(): Unit \ IO = 
    buyTicket();
    buyMeal();
    buyGift()

Accessibility

A module member m declared in module A is accessible from another module B if:

• the member m is declared as public (pub).
• the module B is a sub-module of A.

For example, the following is allowed:

mod A {
    mod B {
       pub def g(): Unit \ IO = A.f() // OK
    }

    def f(): Unit \ IO = println("A.f() was called.")
}

Here f is private to the module A. However, since B is a sub-module of A can access f from inside B. On the other hand, the following is not allowed:

mod A {
    mod B {
       def g(): Unit \ IO = println("A.B.g() was called.")
    }

    pub def f(): Unit \ IO = A.B.g() // NOT OK
}

because g is private to B.

Using Modules

As we have already seen, the use construct brings members of a module into local scope.

For example, given the program:

mod A {
    mod B {
        pub enum Color {
            case Red, Green, Blue
        }

        pub type alias Hue = Color 

        pub def isWarm(c: Color): Bool = 
            match c {
                case Color.Red    => true
                case Color.Green  => false
                case Color.Blue   => false
            }

    }
}

All of the following uses are meaningful:

use A.B.Color 
use A.B.Color.{Red, Green, Blue}
use A.B.Hue
use A.B.isWarm 

All Kinds of Uses

Flix supports several kinds of uses, including:

• A qualified use of a name: use A.B.Color.
• A qualified use of multiple names: use A.B.Color.{Red, Green, Blue}.
• A qualified use with rename: use A.B.Color => AColor.
• A qualified use with multiple renames: use A.B.Color.{Red => R, Green => G, Blue => B}.

Note: Flix does not support wildcard.

Where can Uses Occur?

Flix supports uses in two places:

• Inside modules.
• Inside functions.

For example:

mod A {
    use Chain
    use Chain.Empty
    use Chain.Chain
    use Int32.max

    pub def maxValue(c: Chain[Int32]): Int32 = 
        match c {
            case Empty       => 0
            case One(x)      => x
            case Chain(x, y) => max(maxValue(x), maxValue(y))
        }
}

which can also be written as:

mod A {
    use Chain

    pub def maxValue(c: Chain[Int32]): Int32 = 
        use Chain.Empty;
        use Chain.Chain;
        use Int32.max;
        match c {
            case Empty       => 0
            case One(x)      => x
            case Chain(x, y) => max(maxValue(x), maxValue(y))
        }
}

Note the use of semicolons when inside an expression.

Default Uses

In Flix, a few built-in constructors are always in scope:

• List.Nil and List.Cons.
• Result.Ok and Result.Err.

Companion Modules

In Flix every enum and type class declaration is associated with a companion module.

Enum Companions

When we declare an enum, its type and cases are automatically available inside its companion module. For example, we can write:

enum Color {
    case Red,
    case Green,
    case Blue
}

mod Color {
    pub def isWarm(c: Color): Bool = match c {
        case Red    => true
        case Green  => false
        case Blue   => false
    }
}

Here the Color type and the Red, Green, and Blue cases are automatically in scope within the companion Color module.

Type Class Companions

Every type class declaration also gives rise to a companion module.

For example, we can define a type class Addable for types whose elements can be added:

class Addable[t] {
    pub def add(x: t, y: t): t
}

The Addable type class implicitly introduces a companion module Addable. We typically use the companion module to store functionality that is related to the type class.

For example, we could have:

mod Addable {
    pub def add3(x: t, y: t, z: t): t with Addable[t] = add(add(x, y), z)
}

When accessing a member of Addable, Flix will automatically look in both the class declaration and its companion namespace. Consequently, Addable.add refers to the type class member add whereas Addable.add3 refers to the function inside the Addable module. Note that the add signature is in the scope of the Addable module.

We should be aware that functions defined in the companion module of a type class cannot be overridden by instances of the associated type class. Thus we should only put members into the companion namespace when we do not intend to override them later.

Type Classes

Type classes are one of the ways to support a high level of genericity in functional programming. Flix's type classes largely follow the style of those of Haskell, with some additional principles.

Essentials

The function isSingleton naively determines whether a list has exactly one element. However, it only works with lists. Although checking the length of a collection like this is possible for all standard collections, we have to implement a separate isSingleton function for each of them.

def isSingleton(l: List[a]): Bool =
    List.length(l) == 1

We can generalize this behavior by using a type class constraint. Rather than requiring the argument to be a list, we use a type variable a and constrain it with to the type class Length, which means that the function Length.length can be applied to the argument.

def isSingleton(l: a): Bool with Length[a] =
    Length.length(l) == 1

The type class declaration Length specifies what can be done with its members. In this case, there is only one function: Length.length, which takes the member type as an argument and returns an integer. The law nonnegative is also defined as part of the class. Laws will be further explored below.

pub class Length[a] {
    pub def length(x: a): Int32

    law nonnegative: forall(x: a) . Length.length(x) >= 0
}

If we try to use the new isSingleton function, we will see that it fails to compile:

isSingleton(1 :: 2 :: Nil)

While we know that a list has a length, we haven't told this to the compiler. To do this, we introduce an instance of the type class for the generic type List[a].

instance Length[List[a]] {
    pub def length(x: List[a]): Int32 = List.length(x)
}

This instance simply states that in order to get the length of the list, we just use the List.length function from the standard library. With this instance around, the call to the isSingleton function will compile. However, you may have noticed that our implementation is inefficient. While comparing the length to 1 is a correct solution generally, for lists specifically the solution has a greater runtime complexity than necessary. In order to preserve the general solution while allowing for optimizations where needed, we can use a default implementation in the type class and an override implementation in the instance.

pub class Length[a] {

    pub def length(x: a): Int32

    pub def isSingleton(x: a): Bool = length(x) == 1

    law nonnegative: forall(x: a) . Length.length(x) >= 0

    law singletonMeansOne: forall(x: a) . Length.length(x) == 1 <==> Length.isSingleton(x)
}

instance Length[List[a]] {
    pub def length(x: List[a]): Int32 = List.length(x)
    override pub def isSingleton(x: List[a]): Bool = match x {
        case _ :: Nil => true
        case _ => false
    }
}

We have added the isSingleton function to the Length type class, with a default implementation that works in general. (We also added a new law singletonMeansOne; see section Laws.) We have added an efficient override implementation of isSingleton to the Length instance for List[a]. The advantage of the default implementation is that if there's no special behavior needed for a type, the default is assumed. The function does not have to be implemented.

instance Length[String] {
    pub def length(x: String): Int32 = String.length(x)
}

The instance Length[String] simply uses the default implementation of the isSingleton function.

Laws

In addition to the functions forming part of their contract, type classes have laws that govern how the functions may be implemented.

pub class Length[a] {
    pub def length(x: a): Int32

    law nonnegative: forall(x: a) . Length.length(x) >= 0
}

The nonnegative law asserts that the length of something can never be negative.

Planned Feature

We plan to implement a quickcheck framework to verify that these laws hold. For now, however, they only serve as a form of documentation.

Type Constraints

We've seen type constraints on on function definitions, but constraints can appear on on instances and type classes themselves as well.

pub class TreeSize[a] {
    /// Returns the number of nodes in the object graph of this object
    pub def size(x: a): Int32

    law positive: forall(x: a) . size(x) > 0
}

instance TreeSize[Int32] {
    pub def size(x: Int32): Int32 = 1
}

instance TreeSize[List[a]] with TreeSize[a] {
    pub def size(x: List[a]): Int32 = {
        // one node for each cons cell, one for the nil, and nodes for each node's value
        List.Length(x) + 1 + List.foldLeft((acc, y) -> acc + TreeSize.size(y), 0, x)
    }
}

Sealed Classes

In general, a user can add an instance of a class for any type they define. In some cases, however, it is useful to restrict membership in a class to a finite list of types, defined by the author of the class. This is the purpose of a sealed class, for which instances outside the class's namespace are not permitted.

sealed class Primitive[a]

instance Primitive[Bool]
instance Primitive[Int32]
instance Primitive[Float64]
// ... and so on

Essential Classes

Practical programming in Flix requires knowledge of three type classes: Eq, Order, and ToString.

The Eq Class

The Eq class captures when two values of a specific type are equal:

class Eq[a] {

    ///
    /// Returns `true` if and only if `x` is equal to `y`.
    ///
    pub def eq(x: a, y: a): Bool

    // ... additional members omitted ...
}

To implement Eq, we only have to implement the eq function.

The Order Class

The Order class captures when one value is smaller or equal to another value of the same type:

class Order[a] with Eq[a] {

    ///
    /// Returns `Comparison.LessThan` if `x` < `y`, 
    /// `Equal` if `x` == `y` or 
    /// `Comparison.GreaterThan` if `x` > `y`.
    ///
    pub def compare(x: a, y: a): Comparison

    // ... additional members omitted ...
}

To implement the Order class, we must implement the compare function which returns value of type Comparison. The Comparison data type is defined as:

enum Comparison {
    case LessThan
    case EqualTo
    case GreaterThan
}

The ToString Class

The ToString class is used to obtain a string representation of a specific value:

class ToString[a] {
    ///
    /// Returns a string representation of the given `x`.
    ///
    pub def toString(x: a): String
}

Flix uses the ToString type class in string interpolations.

For example, the interpolated string

"Good morning ${name}, it is ${hour} a clock."

is actually syntactic sugar for the expression:

"Good morning " + ToString.toString(name) + ", it is " 
                + ToString.toString(hour) + " a clock."

In the following subsection, we discuss how to automatically derive implementations of the Eq, Order, and ToString type classes.

Automatic Derivation

Flix supports automatic derivation of several type classes, including:

• Eq — to derive structural equality on the values of a type.
• Order — to derive a total ordering on the values of a type.
• ToString — to derive a human-readable string representation on the values of a type.
• Sendable — to enable the values of an (immutable) type to be sent over a channel.

Derivation of Eq and Order

We can automatically derive instances of the Eq and Order type classes using the with clause in the enum declaration. For example:

enum Shape with Eq, Order {
    case Circle(Int32)
    case Square(Int32)
    case Rectangle(Int32, Int32)
}

The derived implementations are structural and rely on the order of the case declarations:

def main(): Unit \ IO = 
    println(Circle(123) == Circle(123)); // prints `true`.
    println(Circle(123) != Square(123)); // prints `true`.
    println(Circle(123) <= Circle(123)); // prints `true`.
    println(Circle(456) <= Square(123))  // prints `true`.

Note: Automatic derivation of Eq and Order requires that the inner types of the enum implement Eq and Order themselves.

Derivation of ToString

We can also automatically derive ToString instances:

enum Shape with ToString {
    case Circle(Int32)
    case Square(Int32)
    case Rectangle(Int32, Int32)
}

Then we can take advantage of string interpolation and write:

def main(): Unit \ IO = 
    let c = Circle(123);
    let s = Square(123);
    let r = Rectangle(123, 456);
    println("A ${c}, ${s}, and ${r} walk into a bar.")

which prints:

A Circle(123), Square(123), and Rectangle(123, 456) walk into a bar.

Derivation of Sendable

We can automatically derive implementations of the Sendable type class (which allow values of a specific type to be sent over a channel). For example:

enum Shape with Sendable, ToString {
    case Circle(Int32)
}

def main(): Unit \ IO = 
    region rc {
        let (tx, rx) = Channel.buffered(rc, 10);
        Channel.send(Circle(123), tx); // OK, since Shape is Sendable.
        println(Channel.recv(rx))
    }

We cannot derive Sendable for types that rely on scoped mutable memory. For example, if we try:

enum Shape[r: Region] with Sendable {
    case Circle(Array[Int32, r])
}

The Flix compiler emits a compiler error:

❌ -- Safety Error --------------------------------------

>> Cannot derive 'Sendable' for type Shape[b27587945]

Because it takes a type parameter of kind 'Region'.

1 | enum Shape[r: Region] with Sendable {
                               ^^^^^^^^
                               unable to derive Sendable.

This is because mutable data is not safe to share between threads.

Higher-Kinded Types

Flix supports higher-kinded types, hence type class can abstract over type constructors.

For example, we can write a type class that capture iteration over any collection of the shape t[a] where t is a type constructor of kind Type -> Type and a is the element type of kind Type:

class ForEach[t: Type -> Type] {
    pub def forEach(f: a -> Unit \ ef, x: t[a]): Unit \ ef
}

Note that to use higher-kinded types Flix requires us to provide the kind annotation (i.e. we had to write t: Type -> Type to inform Flix that ForEach abstracts over type constructors.)

We can implement instances of the ForEach type class for type constructors such as Option, and List, Set. For example:

instance ForEach[List] {
    pub def forEach(f: a -> Unit \ ef, l: List[a]): Unit \ ef = match l {
        case Nil     => ()
        case x :: xs => f(x); ForEach.forEach(f, xs)
    }
}

Note: Flix does not have a ForEach type class, but instead has the much more powerful and versatile Foldable type class.

The Flix Kinds

Flix supports the following kinds:

• Type: The kind of Flix types.
  • e.g. Int32, String, and List[Int32].
• RecordRow: The kind of rows used in records
  • e.g. in {x = Int32, y = Int32 | r} the type variable r has kind RecordRow.
• SchemaRow: The kind of rows used in first-class Datalog constraints
  • e.g. in #{P(Int32, Int32) | r} the type variable r has kind SchemaRow.

Flix can usually infer kinds. For example, we can write:

def sum(r: {x = t, y = t | r}): t with Add[t] = r.x + r.y

and have the kinds of t: Type and r: RecordRow automatically inferred.

We can also explicitly specify them as follows:

def sum[t: Type, r: RecordRow](r: {x = t, y = t | r}): t with Add[t] = r.x + r.y

but this style is not considered idiomatic.

Flix requires explicit kind annotations in two situations:

• For non-Type kinds on enum type parameters.
• For non-Type kinds on type classes.

In other words, if you are only using types of kind Type, no annotations are necessary. But if you want an enum declaration or type class to abstract over a non-Type kind then you must explicitly write its kind.

Laziness

Flix uses eager evaluation in most circumstances, but allows the programmer to opt-in to lazy evaluation when appropriate with the lazy keyword:

let x: Lazy[Int32] = lazy (1 + 2);

The expression won't be evaluated until it's forced:

let y: Int32 = force x;

Note: The lazy construct requires the expression it's given to be pure.

Note: Forcing a lazy value that's already been evaluated won't evaluate it for a second time.

Lazy data structures

Laziness can be used to create lazy data structures which are evaluated as they're used. This even allows us to create infinite data structures.

Here for example, is a data structure which implements an infinitely long stream of integers which increase by one each time:

namespace IntStream {

    enum IntStream { case SCons(Int32, Lazy[IntStream]) }

    pub def from(x: Int32): IntStream =
        IntStream.SCons(x, lazy from(x + 1))
}

Given this, we can implement functions such as map and take:

    pub def take(n: Int32, s: IntStream): List[Int32] =
        match n {
            case 0 => Nil
            case _ => match s {
                case SCons(h, t) => h :: take(n - 1, force t)
            }
        }

    pub def map(f: Int32 -> Int32, s: IntStream): IntStream =
        match s {
            case SCons(h, t) => IntStream.SCons(f(h), lazy map(f, force t))
        }

So, for example:

IntStream.from(42) |> IntStream.map(x -> x + 10) |> IntStream.take(10)

Will return:

52 :: 53 :: 54 :: 55 :: 56 :: 57 :: 58 :: 59 :: 60 :: 61 :: Nil

Flix provides DelayList and DelayMap data structures which already implement this functionality and more:

DelayList.from(42) |> DelayList.map(x -> x + 10) |> DelayList.take(10)

Fixpoints

A unique feature of Flix is its built-in support for fixpoint computations on constraint on relations and constraint on lattices.

We assume that the reader is already familiar with Datalog and focus on the Flix specific features.

Using Flix to Solve Constraints on Relations

We can use Flix to solve a fixpoint computation inside a function.

For example, given a set of edges s, a src node, and dst node, compute if there is a path from src to dst. We can elegantly solve this problem as follows:

def isConnected(s: Set[(Int32, Int32)], src: Int32, dst: Int32): Bool =
    let rules = #{
        Path(x, y) :- Edge(x, y).
        Path(x, z) :- Path(x, y), Edge(y, z).
    };
    let edges = inject s into Edge;
    let paths = query edges, rules select true from Path(src, dst);
    not (paths |> Vector.isEmpty)

def main(): Unit \ IO =
    let s = Set#{(1, 2), (2, 3), (3, 4), (4, 5)};
    let src = 1;
    let dst = 5;
    if (isConnected(s, src, dst)) {
        println("Found a path between ${src} and ${dst}!")
    } else {
        println("Did not find a path between ${src} and ${dst}!")
    }

The isConnected function behaves like any other function: We can call it with a set of edges (Int32-pairs), an Int32 source node, and an Int32 destination node. What is interesting about isConnected is that its implementation uses a small Datalog program to solve the task at hand.

In the isConnected function, the local variable rules holds a Datalog program fragment that consists of two rules which define the Path relation. Note that the predicate symbols, Edge and Path do not have to be explicitly introduced; they are simply used. The local variable edges holds a collection of edge facts that are obtained by taking all the tuples in the set s and turning them into Edge facts. Next, the local variable paths holds the result of computing the fixpoint of the facts and rules (edges and rules) and selecting the Boolean true if there is a Path(src, dst) fact. Note that here src and dst are the lexically-bound function parameters. Thus, paths is either an empty array (no paths were found) or a one-element array (a path was found), and we simply return this fact.

Flix is strongly typed. Any attempt to use predicate symbol with terms of the wrong type (or with the wrong arity) is caught by the type checker. Note also that Flix supports type inference, hence we did not have to declare the type of Edge nor of Path.

Programming with First-class Constraints

A unique feature of Flix is its support for first-class constraints. A first-class constraint is a value that can be constructed, passed around, composed with other constraints, and ultimately solved. The solution to a constraint system is another constraint system which can be further composed. For example:

def getParents(): #{ ParentOf(String, String) | r } = #{
    ParentOf("Pompey", "Strabo").
    ParentOf("Gnaeus", "Pompey").
    ParentOf("Pompeia", "Pompey").
    ParentOf("Sextus", "Pompey").
}

def getAdoptions(): #{ AdoptedBy(String, String) | r } = #{
    AdoptedBy("Augustus", "Caesar").
    AdoptedBy("Tiberius", "Augustus").
}

def withAncestors(): #{ ParentOf(String, String),
                        AncestorOf(String, String) | r } = #{
        AncestorOf(x, y) :- ParentOf(x, y).
        AncestorOf(x, z) :- AncestorOf(x, y), AncestorOf(y, z).
}

def withAdoptions(): #{ AdoptedBy(String, String),
                        AncestorOf(String, String) | r } = #{
    AncestorOf(x, y) :- AdoptedBy(x, y).
}

def main(): Unit \ IO =
    let c = false;
    if (c) {
        query getParents(), getAdoptions(), withAncestors()
            select (x, y) from AncestorOf(x, y) |> println
    } else {
        query getParents(), getAdoptions(), withAncestors(), withAdoptions()
            select (x, y) from AncestorOf(x, y) |> println
    }

The program uses three predicate symbols: ParentOf, AncestorOf, and AdoptedBy. The getParentsfunction returns a collection of facts that represent biological parents, whereas the getAdoptions function returns a collection of facts that represent adoptions. The withAncestors function returns two constraints that populate the AncestorOf relation using the ParentOf relation. The withAdoptions function returns a constraint that populates the ParentOf relation using the AdoptedBy relation.

In the main function the local variable c controls whether we query a Datalog program that only considers biological parents or if we include adoptions.

As can be seen, the types the functions are row-polymorphic. For example, the signature of getParents is def getParents(): #{ ParentOf | r } where r is row polymorphic type variable that represent the rest of the predicates that the result of the function can be composed with.

Design Note

The row polymorphic types are best understood as an over-approximation of the predicates that may occur in a constraint system. For example, if a constraint system has type #{ A(String), B(Int32, Int32) } that doesn't necessarily mean that it will contain facts or rules that use the predicate symbols A or B, but it does guarantee that it will not contain any fact or rule that refer to a predicate symbol C.

Polymorphic First-class Constraints

Another unique feature of Flix is its support for first-class polymorphic constraints. That is, constraints where one or more constraints are polymorphic in their term types. For example:

def edgesWithNumbers(): #{ LabelledEdge(String, Int32 , String) | r } = #{
    LabelledEdge("a", 1, "b").
    LabelledEdge("b", 1, "c").
    LabelledEdge("c", 2, "d").
}

def edgesWithColor(): #{ LabelledEdge(String, String, String) | r } = #{
    LabelledEdge("a", "red", "b").
    LabelledEdge("b", "red", "c").
    LabelledEdge("c", "blu", "d").
}

def closure(): #{ LabelledEdge(String, l, String),
                  LabelledPath(String, l, String) } with Order[l] = #{
    LabelledPath(x, l, y) :- LabelledEdge(x, l, y).
    LabelledPath(x, l, z) :- LabelledPath(x, l, y), LabelledPath(y, l, z).
}

def main(): Unit \ IO =
    query edgesWithNumbers(), closure()
        select (x, l, z) from LabelledPath(x, l, z) |> println;
    query edgesWithColor(), closure()
        select (x, l, z) from LabelledPath(x, l, z) |> println

Here we use two predicate symbols: LabelledEdge and LabelledPath. Each predicate has a type parameter named l and is polymorphic in the "label" type associated with the edge/path. Note how edgesWithNumbers returns a collection of edge facts where the labels are integers, whereas edgesWithColor returns a collection of facts where the labels are strings. The closure function is polymorphic and returns two rules that compute the transitive closure of edges that have the same label.

The Flix type system ensures that we cannot accidentally mix edges (or paths) with different types of labels.

Injecting Facts into Datalog

Flix provides a flexible mechanism that allows functional data structures (such as lists, sets, and maps) to be converted into Datalog facts.

For example, given a Flix list of pairs we can convert it to a collection of Datalog facts:

let l = (1, 2) :: (2, 3) :: Nil;
let p = inject l into Edge;

where l has type List[(Int32, Int32)]. The inject expression converts l into a Datalog constraint set p of type #{ Edge(Int32, Int32) | ... }.

The inject expression works with any type that implements the Foldable type class. Consequently, it can be used with lists, sets, maps, and so forth.

The inject expression can operate on multiple collections simultaneously. For example:

let names = "Lucky Luke" :: "Luke Skywalker" :: Nil;
let jedis = "Luke Skywalker" :: Nil;
let p = inject names, jedis into Name, Jedi;

where p has type #{ Name(String), Jedi(String) | ... }.

Pipelines of Fixpoint Computations

The solution (i.e. fixpoint) of a constraint system is another constraint system. We can use this to construct pipelines of fixpoint computations, i.e. to feed the result of one fixpoint computation into another fixpoint computation. For example:

def main(): Unit \ IO =
    let f1 = #{
        ColorEdge(1, "blue", 2).
        ColorEdge(2, "blue", 3).
        ColorEdge(3, "red", 4).
    };
    let r1 = #{
        ColorPath(x, c, y) :- ColorEdge(x, c, y).
        ColorPath(x, c, z) :- ColorPath(x, c, y), ColorEdge(y, c, z).
    };
    let r2 = #{
        ColorlessPath(x, y) :- ColorPath(x, _, y).
    };
    let m = solve f1, r1 project ColorPath;
    query m, r2 select (x, y) from ColorlessPath(x, y) |> println

The program uses three predicates: ColorEdge, ColorPath, and ColorlessPath. Our goal is to compute the transitive closure of the colored edges and then afterwards construct a graph where the edges have no color.

The program first computes the fixpoint of f1 and r1 and injects out the ColorPath fact. The result is stored in m. Next, the program queries m and r2, and selects all ColorlessPath facts.

Stratified Negation

Flix supports stratified negation which allow restricted use of negation in rule bodies. For example:

def main(): Unit \ IO =
    let movies = #{
        Movie("The Hateful Eight").
        Movie("Interstellar").
    };
    let actors = #{
        StarringIn("The Hateful Eight", "Samuel L. Jackson").
        StarringIn("The Hateful Eight", "Kurt Russel").
        StarringIn("The Hateful Eight", "Quentin Tarantino").
        StarringIn("Interstellar", "Matthew McConaughey").
        StarringIn("Interstellar", "Anne Hathaway").
    };
    let directors = #{
        DirectedBy("The Hateful Eight", "Quentin Tarantino").
        DirectedBy("Interstellar", "Christopher Nolan").
    };
    let rule = #{
        MovieWithoutDirector(title) :-
            Movie(title),
            DirectedBy(title, name),
            not StarringIn(title, name).
    };
    query movies, actors, directors, rule
        select title from MovieWithoutDirector(title) |> println

The program defines three local variables that contain information about movies, actors, and directors. The local variable rule contains a rule that captures all movies where the director does not star in the movie. Note the use negation in this rule. The query returns an array with the string "Interstellar" because Christopher Nolan did not star in that movie.

Note: Flix enforces that programs are stratified, i.e. a program must not have recursive dependencies on which there is use of negation. If there is, the Flix compiler rejects the program.

Local Predicates

Flix supports an abstract mechanism called local predicates. A local predicate, like a local variable, is not visible to the outside.

To understand local predicates, consider the following example: We can a write a function that returns a Datalog program value which computes whether a graph has a cycle:

def cyclic(): #{Edge(Int32, Int32), Path(Int32, Int32), Cyclic()} = #{
    Path(x, y) :- Edge(x, y).
    Path(x, z) :- Path(x, y), Edge(y, z).
    Cyclic() :- Path(x, x).
}

def main(): Unit \ IO = 
    let db = #{
        Edge(1, 2).
        Edge(2, 3).
        Edge(3, 1).
    };
    query db, cyclic() select true from Cyclic() |> println

Here the cyclic function returns a Datalog program value which consists of three rules that compute the transitive closure of a graph of edges and whether there is path from a vertex to itself. We use the cyclic function inside main to determine if a small graph, given by db, has a cyclic. The program prints Vector#{true} when compiled and run.

Returning to cyclic, we see that its type is:

def cyclic(): #{Edge(Int32, Int32), Path(Int32, Int32), Cyclic()} = ...

This is sensible because the Datalog program value uses the predicate symbols Edge, Path and Cyclic with their given types. However, if we think more about it, we can realize that the Path predicate is really local to the computation: We are not meant to see it from the outside; it is an implementation detail! What we really want is that Edge(Int32, Int32) should be an input and Cyclic() should be an output. More importantly, Path(Int32, Int32) should not be visible from the outside nor part of the type. We can achieve this with predicate abstraction:

def cyclic(): #{Edge(Int32, Int32), Cyclic()} = 
    #(Edge, Cyclic) -> #{
        Path(x, y) :- Edge(x, y).
        Path(x, z) :- Path(x, y), Edge(y, z).
        Cyclic() :- Path(x, x).
    }

Here we use the syntax #(Edge, Cyclic) -> v to specific that only the predicates Edge and Cyclic from within v should be visible to the outside. Thus we can omit Path(Int32, Int32) from the return type of cyclic. Moreover, the Datalog program value no longer contains a Path predicate symbol that can be referenced. We can evidence this by observing that the program:

def main(): Unit \ IO = 
    let db = #{
        Edge(1, 2).
        Edge(2, 3).
        Edge(3, 1).
    };
    query db, cyclic() select (x, y) from Path(x, y) |> println

prints the empty vector Vector#{} since Path has been made local by the predicate abstraction.

Functional Predicates

We sometimes run into a situation where we would like to use a logic predicate, but not to exhaustively enumerate all of its tuples.

For example, we can image a situation where we want a predicate PrimeInRange(from, to, prime) which holds if prime is a prime number in the range [from; to]. While we can imagine such a predicate, it is not feasible to compute with. Instead, what we often want, is that we want to treat PrimeInRange as a functional, i.e. a function that given from and to as input produces a set of primes as output. To make matters concrete, we might want to write the rule:

R(p) :- P(x), Q(y), PrimeInRange(x, y, p).

but without having to evaluate PrimeInRange for every x, y, and p.

We can achieve this as follows. We write a function:

def primesInRange(b: Int32, e: Int32): Vector[Int32] = 
    Vector.range(b, e) |> Vector.filter(isPrime)

The key is that primesInRange is a function which returns a vector of tuples (in this case single elements), given a begin b and end index e. Thus primesInRange can efficiently compute the tuples we are interested in. To use it in our rule, we write:

R(p) :- P(b), Q(e), let p = primesInRange(b, e).

where b and e are clearly identified as the input of primesInRange and p as its output. Specifically, Flix requires that b and e are positively bound (i.e. bound by a non-negative body atom-- in this case P and Q.) In this case, primesInRanges returns a vector of Int32s, but in general a functional may return a vector of tuples.

Note: An important limitation in the current implementation is that the variables in the LHS of a functional predicate must not be rebound. That is, if the functional predicate is of the form let (a, b) = f(x, y) then a and b must not be rebound in the rule.

Using Flix to Solve Constraints on Lattices

Flix supports not only constraints on relations, but also constraints on lattices. To create such constraints, we must first define the lattice operations (the partial order, the least upper bound, and so on) as functions, associate them with a type, and then declare the predicate symbols that have lattice semantics.

We begin with the definition of the Sign data type:

enum Sign {
    case Top,
    case Neg,
    case Zer,
    case Pos,
    case Bot
}

We need to define the usual Eq, Order, and ToString instances for this new type. Note that the order instance is unrelated to the partial order instance we will later define, and is simply used to sort elements for pretty printing etc.

instance Eq[Sign] {
    pub def eq(x: Sign, y: Sign): Bool = match (x, y) {
        case (Bot, Bot) => true
        case (Neg, Neg) => true
        case (Zer, Zer) => true
        case (Pos, Pos) => true
        case (Top, Top) => true
        case _          => false
    }
}

instance Order[Sign] {
    pub def compare(x: Sign, y: Sign): Comparison =
        let num = w -> match w {
            case Bot => 0
            case Neg => 1
            case Zer => 2
            case Pos => 3
            case Top => 4
        };
        num(x) <=> num(y)
}

instance ToString[Sign] {
    pub def toString(x: Sign): String = match x {
        case Bot => "Bot"
        case Neg => "Neg"
        case Zer => "Zer"
        case Pos => "Pos"
        case Top => "Top"
    }
}

With these type class instances in place, we can now define the lattice operations on Sign.

We define the bottom element and the partial order:

instance LowerBound[Sign] {
    pub def minValue(): Sign = Bot
}

instance PartialOrder[Sign] {
    pub def lessEqual(x: Sign, y: Sign): Bool =
        match (x, y) {
            case (Bot, _)   => true
            case (Neg, Neg) => true
            case (Zer, Zer) => true
            case (Pos, Pos) => true
            case (_, Top)   => true
            case _          => false
        }
}

Next, we define the least upper bound and greatest lower bound:

instance JoinLattice[Sign] {
    pub def leastUpperBound(x: Sign, y: Sign): Sign =
        match (x, y) {
            case (Bot, _)   => y
            case (_, Bot)   => x
            case (Neg, Neg) => Neg
            case (Zer, Zer) => Zer
            case (Pos, Pos) => Pos
            case _          => Top
        }
}

instance MeetLattice[Sign] {
    pub def greatestLowerBound(x: Sign, y: Sign): Sign =
        match (x, y) {
            case (Top, _)   => y
            case (_, Top)   => x
            case (Neg, Neg) => Neg
            case (Zer, Zer) => Zer
            case (Pos, Pos) => Pos
            case _          => Bot
        }
}

With all of these definitions we are ready to write Datalog constraints with lattice semantics. But before we proceed, let us also write a single monotone function:

def sum(x: Sign, y: Sign): Sign = match (x, y) {
    case (Bot, _)   => Bot
    case (_, Bot)   => Bot
    case (Neg, Zer) => Neg
    case (Zer, Neg) => Neg
    case (Zer, Zer) => Zer
    case (Zer, Pos) => Pos
    case (Pos, Zer) => Pos
    case (Pos, Pos) => Pos
    case _          => Top
}

We can now finally put everything to use:

pub def main(): Unit \ IO =
    let p = #{
        LocalVar("x"; Pos).
        LocalVar("y"; Zer).
        LocalVar("z"; Neg).
        AddStm("r1", "x", "y").
        AddStm("r2", "x", "y").
        AddStm("r2", "y", "z").
        LocalVar(r; sum(v1, v2)) :-
            AddStm(r, x, y), LocalVar(x; v1), LocalVar(y; v2).
    };
    query p select (r, v) from LocalVar(r; v) |> println

Note the careful use of ; to designate lattice semantics.

Using Lattice Semantics to Compute Shortest Paths

We can also use lattice semantics to compute shortest paths.

The key is to define our own new data type D which is simple an Int32 with forms a lattice with the reverse order of the integers (e.g. the smallest element is Int32.maxValue()).

pub enum D with Eq, Order, ToString {
    case D(Int32)
}

instance PartialOrder[D] {
    pub def lessEqual(x: D, y: D): Bool = 
        let D(n1) = x;
        let D(n2) = y;
        n1 >= n2        // Note: Order reversed.
}

instance LowerBound[D] {
    // Note: Because the order is reversed, the largest value is the smallest.
    pub def minValue(): D = D(Int32.maxValue())
}

instance UpperBound[D] {
    // Note: Because the order is reversed, the smallest value is the largest.
    pub def maxValue(): D = D(Int32.minValue())
}

instance JoinLattice[D] {
    pub def leastUpperBound(x: D, y: D): D = 
        let D(n1) = x;
        let D(n2) = y;
        D(Int32.min(n1, n2))        // Note: Order reversed.
}

instance MeetLattice[D] {
    pub def greatestLowerBound(x: D, y: D): D = 
        let D(n1) = x;
        let D(n2) = y;
        D(Int32.max(n1, n2))        // Note: Order reversed.
}

def shortestPath(g: Set[(t, Int32, t)], o: t): Map[t, D] with Order[t] =
    let db = inject g into Edge;
    let pr = #{
        Dist(o; D(0)).
        Dist(y; add(d1 , D(d2))) :- Dist(x; d1), Edge(x, d2, y).
    };
    query db, pr select (x , d) from Dist(x; d) |> Vector.toMap

def add(x: D, y: D): D = 
    let D(n1) = x;
    let D(n2) = y;
    D(n1 + n2)

def main(): Unit \ IO = 
    let g = Set#{
        ("Aarhus", 200, "Flensburg"),
        ("Flensburg", 150, "Hamburg")
    };
    println(shortestPath(g, "Aarhus"))

Flix actually comes with a type like D built-in. It's called Down and simply reverses the order on the underlying type. We can use it and write the program as:

def shortestPaths(g: Set[(t, Int32, t)], o: t): Map[t, Down[Int32]] with Order[t] =
    let db = inject g into Edge;
    let pr = #{
        Dist(o; Down(0)).
        Dist(y; add(d1 , Down(d2))) :- Dist(x; d1), Edge(x, d2, y).
    };
    query db, pr select (x , d) from Dist(x; d) |> Vector.toMap

def add(x: Down[Int32], y: Down[Int32]): Down[Int32] = 
    let Down(n1) = x;
    let Down(n2) = y;
    Down(n1 + n2)

def main(): Unit \ IO = 
    let g = Set#{
        ("Aarhus", 200, "Flensburg"),
        ("Flensburg", 150, "Hamburg")
    };
    println(shortestPaths(g, "Aarhus"))

Interoperability with Java

Flix is Java Virtual Machine (JVM)-based programming language, hence:

• Flix programs compile to efficient JVM bytecode.
• Flix programs run on any Java Virtual Machine¹.
• Flix programs can call Java code.

Flix supports most Java features necessary for interoperability:

• Creating objects from existing classes
• Calling methods on classes and objects
• Reading and writing fields on objects
• Anonymous extension of classes and interfaces
• Nested and inner classes

Thus Flix programs can reuse Java Class Library and have access to the Java ecosystem.

Flix and Java share the same base types, in particular:

In Flix primitive types are always unboxed. Hence, to call a Java method that expects a java.lang.Integer, if you have a Flix Int32, it must be boxed by calling java.lang.Integer.valueOf.

Design Note: Unlike other programming languages that target the JVM, Flix does not aim to embed the Java type system within Flix. Instead, Flix sacrifices some convenience to stay true to its design goals. In particular, the Flix type system does not support sub-typing. Consequently, unlike in Java, a sub-type cannot be used where its super-type is expected. For example, java.lang.String is incompatible with java.lang.Object. Fortunately, this limitation can be overcome by using upcasts.

Creating Objects

We can import the constructor of a Java class as a Flix function and use it to construct new objects.

For example:

import new java.io.File(String): ##java.io.File \ IO as newFile;
newFile("HelloWorld.txt")

Here we import the constructor of the java.io.File class and give it the local name newFile. The newFile function takes a string argument and returns a fresh Java File object. Constructing a fresh object is impure, hence main is marked as having the IO effect.

When we import a constructor, we must specify the types of its formal parameters. This is required because Java supports constructor overloading (i.e. a class may have multiple constructors only distinguished by their formal parameters.)

For example, the java.io.File class has another constructor that takes two arguments: one for the parent pathname and one for the child pathname. We can use this constructor as follows:

import new java.io.File(String, String): ##java.io.File \ IO as newFile;
newFile("foo", "HelloWorld.txt")

Here the import describes that the constructor expects two String arguments.

Invoking Object Methods

We can use the import mechanism to invoke methods on objects.

For example:

import new java.io.File(String): ##java.io.File \ IO as newFile;
import java.io.File.exists(): Bool \ IO as fileExists;
let f = newFile("HelloWorld.txt");
fileExists(f)

Here we import the java.io.File.exists method under the name fileExists.

If the Java method name is a legal Flix name and we want to reuse it, we can also import the method without an as clause. For example:

import new java.io.File(String): ##java.io.File \ IO as newFile;
import java.io.File.exists(): Bool \ IO;
let f = newFile("HelloWorld.txt");
exists(f)

Here we import the method under the name exists.

When a Java method is imported, we must annotate it with its effect. Most commonly, a Java method has a side-effect (such as deleting a file), and hence must be annotated with the IO effect.

In rare cases where a method is pure, we can import it as such by writing the empty effect set: {}. For example:

import java.lang.String.startsWith(String): Bool \ {};
startsWith("Hello World", "Hello")

And as another example:

import java.lang.String.charAt(Int32): Char \ {};
charAt("Hello World", 2)

Type signatures should use Flix type names and not Java type names for primitive types. For example, if a Java method takes a Double its signature should use the Flix type Float64. Similarly, if a Java method takes a Boolean its signature should use the Flix type Bool. This goes for return types, too.

Invoking Static Methods

We can invoke a static method by writing the static keyword after import:

import static java.lang.String.valueOf(Bool): String \ {};
valueOf(true)

Reading and Writing Fields

We can read and write fields by importing functions that serve as "getters" and "setters".

Assume we have the class:

class TestClass {
    boolean boolField = true;
}

Then here is how we can access the boolField:

import new flix.test.TestClass(): ##flix.test.TestClass \ IO as newObject;
import get flix.test.TestClass.boolField: Bool \ IO as getField;
let o = newObject();
getField(o)

Here we import the (default, empty) constructor of TestClass as newObject. Next, we import the field boolField as the function getField. We use newObject to construct a fresh object and we call getField on it to obtain the value of o.boolField.

Writing a field of an object is similar:

import new flix.test.TestClass(): ##flix.test.TestClass \ IO as newObject;
import get flix.test.TestClass.boolField: Bool \ IO as getField;
import set flix.test.TestClass.boolField: Unit \ IO as setField;
let o = newObject();
setField(o, false);
getField(o)

Here we import both a "getter" and "setter" for the boolField field.

Reading and Writing Static Fields

Reading or writing static fields is similar to reading or writing object fields. For example:

import static get java.lang.Integer.MIN_VALUE: Int32 \ IO as getMinValue;
getMinValue()

The only difference is to write the static keyword to indicate that the reference is to a static field.

Classes and Interfaces

Flix allows us to create objects that extend a Java class or implements a Java interface.

This feature is conceptually similar to Java's Anonymous Classes: We can define an (unnamed class) which implements an interface or extends a class and create an object of that class. All in one expression.

For example, we can create an object that implements the java.lang.Runnable interface:

import java.lang.Runnable

def newRunnable(): Runnable \ IO = new Runnable {
    def run(_this: Runnable): Unit \ IO = 
        println("I am running!")
}

Every time we call newRunnable we get a fresh object that implements java.lang.Runnable.

Note: The implicit this argument is always passed as the first argument in a new expression.

As another example, we can create an object that implements the java.io.Closeable interface:

import java.io.Closeable

def newClosable(): Closeable \ IO = new Closeable {
    def close(_this: Closeable): Unit \ IO = 
        println("I am closing!")
}

We can also extend classes. For example, we can create a java.lang.Object where we override the hashCode and toString methods:

def newObject(): Object \ IO = new Object {
    def hashCode(_this: Object): Int32 = 42
    def toString(_this: Object): String = "Hello World!"
}

Nested and Inner Classes

Java supports two different types of nested class: static nested classes and inner classes:

class OuterClass {
    ...
    class InnerClass {
        ...
    }
    static class StaticNestedClass {
        ...
    }
}

Although these appear superficially similar, they provide very different functionality.

Flix supports static nested classes, but does not yet support inner classes. To reference a static nested class, use a $ instead of . in the class name, for example java.util.Locale$Builder.

Exceptions

In Flix, all error handling should be done using the Result[e, t] type. However, for interoperability with Java, Flix also has a classic try-catch mechanism.

For example, we can write:

///
/// Returns `true` if the given file `f` exists.
///
pub def exists(f: String): Result[String, Bool] \ IO =
    try {
        import new java.io.File(String): ##java.io.File \ IO as newFile;
        import java.io.File.exists(): Bool \ IO;
        Ok(exists(newFile(f)))
    } catch {
        case ex: ##java.io.IOException =>
            import java.lang.Throwable.getMessage(): String \ IO;
            Err(getMessage(ex))
    }

Here we import the File constructor as newFile and the File.exists method as exists. We then call the methods and catch the IOException.

Note: Flix programs should not rely on the exception mechanism. Instead, we should guard all call to Java code that might throw exceptions close to their call site and turn these exceptions into Results.

Structured Concurrency and Exceptions

Flix supports structured concurrency. This means that (1) threads cannot outlive the lifetime of their region and (2) that exceptions thrown in sub-threads are propagated to the thread of the region.

For example, given the program:

def main(): Unit \ IO = 
    region rc {
        spawn f() @ rc;
        spawn g() @ rc
    };
    println("Done")

where f and g are some functions. If f or g were to throw an unhandled exception then that exception would be caught and rethrown inside the main thread. This means that we cannot successfully leave the scope of rc unless f and g terminated and did not throw any unhandled exceptions.

Java Collections

Flix has support for conversion to and from Java collections.

Flix to Java

The following functions convert Flix collections to Java collections:

///
/// Lists
///
def toList(ma: m[a]): ##java.util.List \ IO with Foldable[m]
def toArrayList(ma: m[a]): ##java.util.ArrayList \ IO with Foldable[m]
def toLinkedList(ma: m[a]): ##java.util.LinkedList \ IO with Foldable[m]

///
/// Sets
///
def toSet(ma: m[a]): ##java.util.Set \ IO with Order[a], Foldable[m]
def toTreeSet(ma: m[a]): ##java.util.TreeSet \ IO with Order[a], Foldable[m]

///
/// Maps
///
def toMap(m: Map[k, v]): ##java.util.Map \ IO with Order[k]
def toTreeMap(m: Map[k, v]): ##java.util.TreeMap \ IO with Order[k] 

Each function constructs a new collection and copies all its elements into it. Hence each operation takes at least linear time. The upshot is that the result is a normal Java collection (which can be modified).

Java to Flix

The following functions convert Java collections to Flix collections:

/// Lists
def fromList(l: ##java.util.List): List[a]

/// Sets
def fromSet(l: ##java.util.Set): Set[a] with Order[a]

/// Maps
def fromMap(m: ##java.util.Map): Map[k, v] with Order[k]

Each function constructs a new Flix collection from a Java Collection. Hence each operation takes at least linear time. Note that for Set and Map, the Flix collections use the Order[a] instance defined on a. This may not be the same ordering as used by Java. Thus one has to be careful.

Wrapping Flix Collections

TBD.

Primitive Values

Warning: Converting Flix and/or Java collections with primitive values requires extra care. In particular, values must be manually boxed or unboxed before any conversion.

Everyday Programming

In this chapter we cover some everyday programming features:

• The signature of the main function.
• How to print to standard out and standard error.
• How to use string interpolation.
• How to use anonymous and named holes for incomplete programs.
• How to use type ascriptions to explicitly provide some types to the compiler.

The Main Function

The entry point of any Flix program is the main function which must have the signature:

def main(): Unit \ IO

That is, the main function:

1. must return Unit, and
2. must be marked as effectful (i.e. have the effect annotation \ IO).

The signature of main does not specify any arguments, but the command line arguments passed to the program can be accessed by calling Environment.getArgs():

def main(): Unit \ IO =
    let args = Environment.getArgs();
    ...

Flix requires main to have the IO effect. If main was pure there would be no reason to run the program. Typically the effectful requirement is satisfied because main prints to the console or has another side-effect.

Printing to Standard Out

The Flix Prelude defines the println function which prints to standard out. For example:

println("Hello World")

The println function can print any value whose type implements ToString type class and consequently can be converted to a String. For example:

let o = Some(123);
let l = 1 :: 2 :: 3 :: Nil;
println(o);
println(l)

The println function is rightfully effectful, hence it cannot be called from a pure function. To debug a pure function, use the builtin debugging facilities.

The Console Module

The Console module defines additional functions for reading from or writing to the terminal:

mod Console {
    def print(x: a): Unit \ IO with ToString[a]
    def println(x: a): Unit \ IO with ToString[a]
    def readLine(): Result[String, String] \ IO Impure
}

String Interpolation

Flix strings support interpolation. Inside a string, the form "${e}" evaluates e to a value and converts it to a string using the ToString type class. For example:

let fstName = "Lucky";
let lstName = "Luke";
"Hello Mr. ${lstName}. Do you feel ${fstName}, punk?"

String interpolation works for any type that implements a ToString instance. For example:

let i = 123;
let o = Some(123);
let l = 1 :: 2 :: 3 :: Nil;
"i = ${i}, o = ${o}, l = ${l}"

String interpolations may contain arbitrary expressions. For example:

let x = 1;
let y = 2;
"${x + y + 1}"

String interpolation is the preferred way to concatenate two strings:

let x = "Hello";
let y = "World";
"${x}${y}" // equivalent to x + y

String interpolation is the preferred way to convert a value to a string:

let o = Some(123);
"${o}"

which is equivalent to an explicit use of the toString function from the ToString type class:

ToString.toString(o)

String interpolators may nest, but this is discouraged.

Tail Recursion

In Flix, and in functional programming in general, iteration is expressed through recursion.

For example, if we want to determine if a list contains an element, we can write a recursive function:

def memberOf(x: a, l: List[a]): Bool with Eq[a] = 
    match l {
        case Nil     => false
        case y :: ys => if (x == y) true else memberOf(x, ys)
    }

The memberOf function pattern matches on the list l. If it is empty then it returns false. Otherwise, we have an element y and the rest of the list is ys. If x == y then we have found the element and we return true. Otherwise we recurse on the rest of the list ys.

The recursive call to memberOf is in tail position, i.e. it is the last thing to happen in the memberOf function. This has two important benefits: (a) the Flix compiler is able to rewrite memberOf to use an ordinary loop (which is more efficient than a function call) and more importantly (b) a call to memberOf cannot overflow the stack, because the call stack never increases in height.

Tip: Flix has support for full tail call elimination which means that recursive calls in tail position never increase the stack height and hence cannot cause the stack to overflow!

We remark that Flix has full tail call elimination, not just tail call optimization. This means that the following program compiles and runs successfully:

def isOdd(n: Int32): Bool =
    if (n == 0) false else isEvn(n - 1)

def isEvn(n: Int32): Bool =
    if (n == 0) true else isOdd(n - 1)

def main(): Unit \ IO =
    isOdd(12345) |> println

which is not the case in many other programming languages.

Non-Tail Calls and StackOverflows

While the Flix compiler guarantees that tail calls cannot overflow the stack, the same is not true for function calls in non-tail positions.

For example, the following implementation of the factorial function overflows the call stack:

def factorial(n: Int32): Int32 = match n {
    case 0 => 1
    case _ => n * factorial(n - 1)
}

as this program shows:

def main(): Unit \ IO = 
    println(factorial(1_000_000))

which when compiled and run produces:

java : Exception in thread "main" java.lang.StackOverflowError
	at Cont%Int32.unwind(Cont%Int32)
	at Def%factorial.invoke(Unknown Source)
	at Cont%Int32.unwind(Cont%Int32)
	at Def%factorial.invoke(Unknown Source)
	at Cont%Int32.unwind(Cont%Int32)
    ... many more frames ...

A well-known technique is to rewrite factorial to use an accumulator:

def factorial(n: Int32): Int32 = 
    def visit(x, acc) = match x {
        case 0 => acc
        case _ => visit(x - 1, x * acc)
    };
    visit(n, 1)

Here the visit function is tail recursive, hence it cannot overflow the stack.

Anonymous and Named Holes

During development, Flix encourages the use of holes for incomplete code. For example:

def sum(x: Int32, y: Int32): Int32 = ???

The triple question marks ??? represents an anonymous hole and can be used wherever an expression is expected. In the above code, ??? represents a missing function body, but it can also be used inside an expression. For example:

def length(l: List[a]): Int32 = match l {
    case Nil     => 0
    case x :: xs => ???
}

When a program has multiple holes, it can be useful to name them. For example:

def length(l: List[a]): Int32 = match l {
    case Nil     => ?base
    case x :: xs => ?step
}

Flix requires that each named hole has a unique name.

Variable Holes and Auto-Completion

Flix has support for a special variable hole which enables type-driven auto-completion suggestions. For example, in the program:

def main(): Unit \ IO = 
    let s: String = "Hello World";
    let n: Int32 = s?;
    println("The length of ${s} is ${n}!")

If we place the cursor on s? and ask for auto-completion suggestions, Flix will suggest:

• String.length(s: String): Int32
• String.countSubstring(substr: {substr: String}, s: String): Int32
• String.levenshtein(s: String, t: String): Int32
• ...

since these are functions that can convert a String to an Int32.

As another example, in the program:

def main(): Unit \ IO = 
    let l: List[Int32] = List.range(1, 10);
    let n: Int32 = l?;
    println("The value of `n` is ${n + 0}.")

If we place the cursor on l?, Flix will suggest:

• List.product(l: List[Int32]): Int32
• List.sum(l: List[Int32]): Int32
• List.fold(l: List[Int32]): Int32
• List.length(l: List[Int32]): Int32
• List.count(f: a -> Bool \ ef, l: List[a]): a \ ef
• ...

since these are functions that can convert a List[Int32] to an Int32.

Type Ascriptions

While Flix supports local type inference, it can sometimes be useful to annotate an expression or a let-binding with its type. We call such annotations type ascriptions. A type ascription cannot change the type of an expression nor can it be used to violate type safety.

A type ascription can be placed after an expression:

("Hello" :: "World" :: Nil) : List[String]

and it can also be placed on a let-binding:

let l: List[String] = "Hello" :: "World" :: Nil

Kind Ascriptions

Flix also supports kind ascriptions. Where a type ascription specifies the type of an expression, a kind ascription specifies the kind of a type.

We can use kind ascriptions on type parameters. For example:

def fst1[a: Type, b: Type](p: (a, b)): a = let (x, _) = p; x

Here we have specified that the kind of the two type parameters a and b is Type. We will typically never have to specify such kinds since they can inferred.

We can also provide kind ascriptions on algebraic data types:

enum A[t: Type] {
    case A(t, t)
}

and on type classes:

class MyClass[t: Type] {
    // ...
}

We typically only use kind ascriptions for higher-kinded types.

Redundancy

The Flix compiler aggressively rejects programs that contain unused elements. The idea is to help programmers avoid subtle bugs¹. While this can take some time getting used to, we believe the trade-off is worth it.

Specifically, the Flix compiler will ensure that a program does not have:

• Unused local variables: local variables that are declared, but never used.
• Shadowed local variables: local variables that shadow other local variables.
• Useless expressions: pure expressions whose values are discarded.
• Must use values: expressions whose values are unused but their type is marked as @MustUse.

Unused Local Variables

Flix rejects programs with unused variables.

For example, the following program is rejected:

def main(): Unit \ IO =
    let x = 123;
    let y = 456;
    println("The sum is ${x + x}")

with the message:

❌ -- Redundancy Error -------------------------------------------------- Main.flix

>> Unused local variable 'y'. The variable is not referenced within its scope.

3 |     let y = 456;
            ^
            unused local variable.

Unused local variables can be prefixed by an underscore _ to supress the error. For example, if we replace y by _y the above program compiles:

def main(): Unit \ IO =
    let x = 123;
    let _y = 456; // OK
    println("The sum is ${x + x}")

Shadowed Local Variables

Flix rejects programs with shadowed variables.

For example, the following program is rejected:

def main(): Unit \ IO = 
    let x = 123;
    let x = 456;
    println("The value of x is ${x}.")

with the message:

❌ -- Redundancy Error -------------------------------------------------- Main.flix

>> Shadowed variable 'x'.

3 |     let x = 456;
            ^
            shadowing variable.

The shadowed variable was declared here:

2 |     let x = 123;
            ^
            shadowed variable.

Useless Expressions

Flix rejects programs with pure expressions whose results are discarded.

For example, the following program is rejected:

def main(): Unit \ IO =
    123 + 456;
    println("Hello World!")

with the message:

❌ -- Redundancy Error -------------------------------------------------- Main.flix

>> Useless expression: It has no side-effect(s) and its result is discarded.

2 |     123 + 456;
        ^^^^^^^^^
        useless expression.

The expression has type 'Int32'

An expression that has no side-effect and whose result is unused is suspicious, since it could just be removed from the program without changing its meaning.

Must Use Values

Flix rejects programs with expressions whose values are discarded but where their type is marked with the @MustUse annotation. Function types, and the Result and Validation types from the Flix Standard Library are marked as @MustUse.

For example, the following program is rejected:

def main(): Unit \ IO =
    File.creationTime("foo.txt");
    println("Hello World!")

with the message:

❌ -- Redundancy Error -------------------------------------------------- Main.flix

>> Unused value but its type is marked as @MustUse.

2 |     File.creationTime("foo.txt");
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        unused value.

The expression has type 'Result[String, Int64]'

Even though File.creationTime has a side-effects, we should probably be using the result Result[String, Int64]. At least to ensure that the operation was successful.

If the result of an impure expression is truly not needed, then the discard expression can be used:

def main(): Unit \ IO =
    discard File.creationTime("foo.txt");
    println("Hello World!")

which permits a @MustUse value to be thrown away as long as the expression is non-pure.

¹ See e.g. Using Redundancies to Find Errors.

Debugging

When debugging, it is often helpful to output the value of an expression or variable.

We might try something like:

def sum(x: Int32, y: Int32): Int32 = 
    println(x);
    println(y);
    x + y

Unfortunately this does not work:

❌ -- Type Error -------------------------------------------------- Main.flix

>> Impure function declared as pure.

1 | def sum(x: Int32, y: Int32): Int32 = 
        ^^^
        impure function.

The problem is that printing is inherently an effectful operation and hence we cannot use it to debug our pure functions! We could make our sum function have the IO effect, but that is rarely what we want. Fortunately, Flix has a built-in debugging facility that allows us to do print-line debugging.

The debug Function

Flix has a debug function with the same signature as the identity fuction:

def debug(x: a): a

The debug "function" isn't really a function; rather its internal compiler magic that allows you to print any value while fooling the type and effect system into believing that it is still pure. Using the debug function this program:

def sum(x: Int32, y: Int32): Int32 = 
    debug(x);
    debug(y);
    x + y

Now compiles and runs.

The debug function returns its argument. Hence its convenient to use in many situations.

For example, we can write:

def sum(x: Int32, y: Int32): Int32 = debug(x + y)

to print the value of x + y and return it.

We can also use it inside e.g. a for-yield expression:

for(i <- List.range(0, 10);
    j <- debug(List.range(i, 10)))
    yield (i, j)

Or in a pipeline:

List.range(1, 100) |>
List.map(x -> debug(x + 1)) |>
List.filter(x -> debug(x > 5))

Debug Format

The debug expression (and its variants) do not use the ToString type class. Instead they print the internal Flix representation of the given value.

For example, the expression:

debug(1 :: 2 :: Nil)

prints:

Cons(1, Cons(2, Nil))

We can also print values that do not have a ToString instance:

debug(x -> x + 123)

prints:

Int32 -> Int32

We can always obtain the ToString representation by using an interpolated string. For example:

debug("${x}")

Debug Variants

The debug function comes in three variants:

• debug: Prints its argument.
• debug!: Prints its argument and source location.
• debug!!: Prints its argument, source location, and source code.

The following program:

def main(): Unit = 
    debug("A message");
    debug!("Another message");
    debug!!("A third message");
    ()

prints:

"A message"
[C:\tmp\flix\Main.flix:3] "Another message"
[C:\tmp\flix\Main.flix:4] A third message = "A third message"

The third debug!! variant is intended to be used in situations like:

let x = 123;
let y = 456;
debug!!(x + y)

where it prints:

[C:\tmp\flix\Main.flix:3] x + y = 579

Note: The debug expression should not be used in production code.

Warning: The Flix compiler treats the debug expression as pure, hence under certain circumstances the compiler may reorder or entirely remove a use of debug.

Tools

This chapter covers the tooling which Flix ships with, including:

• A fully-featured Visual Studio Code extension.
• A package manager.
• A built-in test framework.

Visual Studio Code Extension

Flix comes with a fully-featured Visual Studio Code Extension:

The Flix extension uses the real Flix compiler hence all information (e.g. error messages) are always 1:1 with the real Flix programming language.

Flix also comes with an (optional) Visual Studio Code color theme called "Flixify Dark".

Features

• Semantic Syntax Highlighting

  • Code highlighting for *.flix files. This work best with the official vscode theme.

• Diagnostics

  • Compiler error messages.

• Auto-complete

  • Auto-complete as you type.
  • Auto-completion is context aware.
  • Type-directed completion of program holes.

• Snippets

  • Auto-complete common code constructs.

• Inlay Hints

  • Shows inline type information.

• Type and Effect Hovers

  • Hover over any expression to see its type and effect.
  • Hover over any local variable or formal parameter to see its type.
  • Hover over any function to see its type signature and documentation.

• Jump to Definition

  • Jump to the definition of any function.
  • Jump to the definition of any local variable or formal parameter.
  • Jump to the definition of any enum case.

• Find References

  • Find all references to a function.
  • Find all references to a local variable or formal parameter.
  • Find all references to an enum case.
  • Find all implementations of a type class.

• Symbols

  • List all document symbols.
  • List all workspace symbols.

• Rename

  • Rename local variables or formal parameters.
  • Rename functions.

• Code Lenses

  • Run main from within the editor.
  • Run tests from within the editor.

• Highlight

  • Highlights semantically related symbols.

• Semantic Tokens

  • Additional code highlighting hints provided by the compiler.

Known Limitations

• There is a known issue with PowerShell and using file names that contain special characters. We recommend that Flix source files are given only ASCII names.

• The extension assumes that you are working in "Workspace Mode", i.e. you must have a folder open which contains your Flix source code.

• Upon startup, the Flix compiler has to load the entire Flix standard library into its caches which takes a few seconds.

Test Framework

Flix comes with a simple built-in test framework.

A test is a Flix function marked with the @Test annotation. That's it.

A test function can return any value. If it returns a Bool then true is interpreted as success and false as failure. Any non-Boolean value is interpreted as success.

The Assert.eq function can be used to test for equality between two values that implement the Eq and ToString type classes. The advantage of Assert.eq (over ==) is that it will print the two values if they are unequal. The Assert.eq function should not be used outside of unit tests.

Here is an example:

def add(x: Int32, y: Int32): Int32 = x + y

@Test
def testAdd01(): Bool = 0 == add(0, 0)

@Test
def testAdd02(): Bool = Assert.eq(1, add(0, 1))

@Test
def testAdd03(): Bool = Assert.eq(2, add(1, 1))

@Test
def testAdd04(): Bool = Assert.eq(4, add(1, 2))

@Test @Skip
def testAdd05(): Bool = Assert.eq(8, add(2, 3))

Running the tests (e.g. with the command test) yields:

Running 5 tests...

   PASS  testAdd01 237,3us
   PASS  testAdd02 21,1us
   PASS  testAdd03 10,3us
   FAIL  testAdd04 (Assertion Error)
   SKIP  testAdd05 (SKIPPED)

--------------------------------------------------------------------------------

   FAIL  testAdd04
    Assertion Error
      Expected: 4
      Actual:   3

    dev.flix.runtime.HoleError: Hole '?Assert.assertEq' at Assert.flix:32:13    
        at Assert.Def%eq%174731.invoke(Unknown Source)
        at Cont%Bool.unwind(Cont%Bool)
        at Ns.m_testAdd04(Unknown Source)
        at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:77)
        at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
        at java.base/java.lang.reflect.Method.invoke(Method.java:568)
        at ca.uwaterloo.flix.language.phase.jvm.JvmBackend$.$anonfun$link$1(JvmBackend.scala:286)
        at ca.uwaterloo.flix.language.phase.jvm.JvmBackend$.$anonfun$getCompiledDefs$2(JvmBackend.scala:259)
        at ca.uwaterloo.flix.tools.Tester$TestRunner.runTest(Tester.scala:182)
        at ca.uwaterloo.flix.tools.Tester$TestRunner.$anonfun$run$7(Tester.scala:153)
        at ca.uwaterloo.flix.tools.Tester$TestRunner.$anonfun$run$7$adapted(Tester.scala:152)
        at scala.collection.immutable.Vector.foreach(Vector.scala:1856)
        at ca.uwaterloo.flix.tools.Tester$TestRunner.run(Tester.scala:152)

--------------------------------------------------------------------------------

Passed: 3, Failed: 1. Skipped: 1. Elapsed: 3,0ms.

Build and Package Management

Flix comes with a build system and package manager. The build system makes it simple to compile a Flix program to a collection of Java classes and to build a fat JAR. The package manager makes it possible to create Flix packages, publish them on GitHub, and depend on them via a manifest file. The package manager also makes it possible to depend on Java JAR-artifacts published on Maven.

The Flix build system supports the following commands:

• init: creates a new Flix project in the current directory.
• check: checks the current project for compiler errors.
• build: builds the current project (i.e. emits Java bytecode).
• build-jar: builds a jar-file from the current project.
• build-pkg: builds a fpkg-file from the current project.
• run: runs main in current project.
• test: runs all tests in the current project.

All commands can be executed from the command line, from the REPL, and from VSCode.

All commands, except build-pkg work without a manifest file. To build, package, and publish a Flix project, a flix.toml manifest is required. The init command will create an empty skeleton flix.toml manifest, if not already present.

Project Structure

Flix scans for source files in the paths *.flix, src/**.flix,, and test/**.flix.

Flix scans for Flix packages and JARs in the paths lib/**.fpkg and lib/**.jhar.

Build Management

We now discuss the build commands. Each command can be executed from the command line, from the REPL, and from VSCode.

Creating a New Project

We can create a new project, inside a directory, with the init command.

This will create the default Flix project structure:

.
├── flix.toml
├── LICENSE.md
├── README.md
├── src
│   └── Main.flix
└── test
    └── TestMain.flix

2 directories, 6 files

The most relevant files are flix.toml, src/Main.flix and test/TestMain.flix.

The flix.toml manifest file is discussed in the next section.

Tip: The init command is safe to use; it will only create files that do not already exist.

Checking a Project

We can check a project for compiler errors with the check command. During development, the check command is preferable to the build command because it skips code generation (and hence is significantly faster).

Building a Project

We can compile a project with the build command. Running the build command will compile the entire project and emit bytecode, i.e. compiled Java classes, to the build directory.

Flix has no clean command. Deleting the build directory serves the same purpose.

Building a JAR-file

We can compile a project to a fat JAR-file with the build-jar command. The build-jar command emits a artifact/project.jar file. If there is main function, we can run it:

$ java -jar artifact/project.jar

The JAR-file contains all class files from the build directory. The built JAR may depend on external JARs, if the project, or one of its dependencies, depends on JAR-files.

Note: The project must be compiled with build before running build-jar.

Building a Flix Project

We can bundle a project into a Flix package file (fpkg) with the build-pkg command. Running the build-pkg command emits a artifact/project.fpkg file.

A Flix package file (fpkg) is essentially zip-file of the project source code. A Flix package, together with its flix.toml manifest, can be published on GitHub.

Running a Project

We do not have to build a JAR-file to run a project, we can simply use the run command which will compile and run the main entry point.

Testing a Project

We can use the test command to run all test cases in a project. Flix will collect all functions marked with @Test, execute them, and print a summary of the results:

Running 1 tests...

   PASS  test01 1,1ms

Passed: 1, Failed: 0. Skipped: 0. Elapsed: 3,9ms.

Package Management

Every non-trivial Flix project should have a flix.toml manifest. The manifest contains information about the project and its dependencies.

A minimal manifest is of the form:

[package]
name        = "hello-library"
description = "A simple library"
version     = "0.1.0"
flix        = "0.35.0"
license     = "Apache-2.0"
authors     = ["John Doe <john@example.com>"]

Note: The flix field is not yet used, but it will be used in the future.

Adding Flix Dependencies

We can add dependencies on other Flix packages to the manifest:

[dependencies]
"github:flix/museum"              = "1.4.0"
"github:magnus-madsen/helloworld" = "1.3.0"

Note: Flix requires version numbers to follow SemVer.

Adding Maven Dependencies

We can also add dependencies on Maven packages to the manifest:

[mvn-dependencies]
"org.junit.jupiter:junit-jupiter-api" = "5.9.2"

Understanding Dependency Resolution

Flix dependency resolution works as follows:

1. Flix reads flix.toml and computes the transitive set of Flix package dependencies.
2. Flix downloads all of these Flix packages.
3. Flix inspects each package for its Maven dependencies and downloads these.

We illustrate with an example. Assume we have a Flix package with:

[dependencies]
"github:flix/museum"              = "1.4.0"

Running Flix produces:

Found `flix.toml'. Checking dependencies...
Resolving Flix dependencies...
  Downloading `flix/museum.toml` (v1.4.0)... OK.
  Downloading `flix/museum-entrance.toml` (v1.2.0)... OK.
  Downloading `flix/museum-giftshop.toml` (v1.1.0)... OK.
  Downloading `flix/museum-restaurant.toml` (v1.1.0)... OK.
  Downloading `flix/museum-clerk.toml` (v1.1.0)... OK.
  Cached `flix/museum-clerk.toml` (v1.1.0).
Downloading Flix dependencies...
  Downloading `flix/museum.fpkg` (v1.4.0)... OK.
  Downloading `flix/museum-entrance.fpkg` (v1.2.0)... OK.
  Downloading `flix/museum-giftshop.fpkg` (v1.1.0)... OK.
  Downloading `flix/museum-restaurant.fpkg` (v1.1.0)... OK.
  Downloading `flix/museum-clerk.fpkg` (v1.1.0)... OK.
  Cached `flix/museum-clerk.fpkg` (v1.1.0).
Resolving Maven dependencies...
  Adding `org.apache.commons:commons-lang3' (3.12.0).
  Running Maven dependency resolver.
Dependency resolution completed.

This happens because flix/museum has the following dependency tree:

• flix/museum depends on:
  • flix/museum-entrance which depends on:
    • flix/museum-clerk
  • flix/museum-giftshop which depends on:
    • flix/museum-clerk
  • flix/museum-restaurant which depends on
    • org.apache.commons:commons-lang3

Publishing a Package on GitHub

Creating and publish a package on GitHub is straightforward:

1. Check that you have a flix.toml manifest (if not create one with init).
2. Check that the version field in flix.toml is correct.
3. Run check and test to ensure that everything looks alright.
4. Run build-pkg. Check that the artifact directory is populated.
5. Go to the repository on GitHub:
   1. Click "Releases".
   2. Click "Draft new release".
   3. Enter a tag of the form v1.2.3 (i.e. use SemVer).
   4. Upload the package.fpkg and flix.toml from the artifact directory.

Tip: See the Museum Project for an example of a package that has been published on GitHub.

Advanced Features

In this chapter, we discuss some advanced features of Flix, including:

• Checked Casts and Unchecked Casts
• The bug! and unreachable! functions
• Type Match
• Purity Reflection

Checked Type and Effect Casts

The Flix type and effect system – by design – does not support sub-typing nor sub-effecting. To work around these limitations, which are rare in practice, Flix has two safe upcast constructs:

• A checked type cast: checked_cast(exp), and
• A checked effect cast checked_ecast(exp).

Note: The checked_cast and checked_ecast expressions are guaranteed to be safe. The Flix compiler will check at compile-time that every checked cast cannot go wrong.

Checked Type Casts

The following program:

def main(): Unit =
    let s = "Hello World";
    let o: ##java.lang.Object = s;
    ()

does not compile:

❌ -- Type Error --------------------------------------------------

>> Expected type: 'Object' but found type: 'String'.

4 |     let o: ##java.lang.Object = s;
                                    ^
                                    expression has unexpected type.

because in Flix the String type is not a subtype of Object.

We can use a checked type cast to safely upcast from String to Object:

def main(): Unit =
    let s = "Hello World";
    let o: ##java.lang.Object = checked_cast(s);
    ()

We can use the checked_cast construct to safely upcast any Java type to one of its super-types:

let _: ##java.lang.Object       = checked_cast("Hello World");
let _: ##java.lang.CharSequence = checked_cast("Hello World");
let _: ##java.io.Serializable   = checked_cast("Hello World");
let _: ##java.lang.Object       = checked_cast(null);
let _: ##java.lang.String       = checked_cast(null);

Checked Effect Casts

The following program:

def hof(f: Int32 -> Int32 \ IO): Int32 \ IO = f(42)

def main(): Int32 \ IO =
    hof(x -> x + 1)

does not compile:

❌ -- Type Error --------------------------------------------------

>> Expected argument of type 'Int32 -> Int32 \ IO', but got 'Int32 -> Int32'.

4 |     hof(x -> x + 1)
            ^^^^^^^^^^
            expected: 'Int32 -> Int32 & Impure \ IO'

The function 'hof' expects its 1st argument to be of type 'Int32 -> Int32 \ IO'.

Expected: Int32 -> Int32 & Impure \ IO
  Actual: Int32 -> Int32

because in Flix a pure function is not a subtype of an impure function. Specifically, the hof requires a function with the IO effect, but we are passing in a pure function.

We can use a checked effect cast to safely upcast upcast a pure expression to an impure expression:

def main(): Int32 \ IO =
    hof(x -> checked_ecast(x + 1))

The checked_ecast construct allows us to pretend that x + 1 has the IO effect.

Note: In Flix – as a general rule – higher-order functions should not require their function arguments to have a specific effect. Instead they should be effect polymorphic.

Function Types

Neither the checked_cast nor the checked_ecast constructs work on function types.

For example, the following does not work:

let f: Unit -> ##java.lang.Object = checked_cast(() -> "Hello World")

because it tries to cast the function type Unit -> String to String -> Object.

Instead, we should write:

let f: Unit -> ##java.lang.Object = (() -> checked_cast("Hello World"))

because it directly casts String to Object.

Unchecked Type and Effect Casts

Flix also supports unchecked type and effect casts.

Unchecked Type Casts

An unchecked type cast instructs the compiler that an expression has a specific type.

Warning️️: Type casts are very dangerous and should be used with utmost caution!

Flix programmers should normally never need to use an unchecked type cast.

Example: Safe Cast to a Super-Type

The expression below casts a String to an Object:

unchecked_cast("Hello World" as ##java.lang.Object)

Note: It is safer to use the checked_cast expression.

Example: Safe Cast from Null to an Object-Type

The expression below casts the null value (of type Null) to String:

unchecked_cast(null as ##java.lang.String)

Note: It is safer to use the checked_cast expression.

Example: Unsafe Type Cast

The expression below contains an illegal cast and triggers a ClassCastException at runtime:

unchecked_cast((123, 456) as ##java.lang.Integer)

Effect Casts

An unchecked effect cast instructs the compiler that an expression has a specific effect.

Warning️️: Effect casts are extremely dangerous and should be used with extreme caution!

Flix programmers should normally never need to use an unchecked effect cast.

Example: Unsafe Effect Cast

We can pretend an impure expression is pure:

def main(): Unit = 
    unchecked_cast(println("Hello World") as _ \ {})

Here we call println which has the IO effect and then we explicitly, and unsafely, cast away the effect, pretending that the expression is pure.

Warning: Never cast effectful expressions to pure. You have been warned.

bug! and unreachable!

Flix supports two special "functions": bug! and unreachable! that can be used to indicate when an internal program invariant is broken and execute should abort. For example:

match o {
    case Some(x) => ...
    case None    => bug!("The value of `o` cannot be empty.")
}

As another example:

match k {
    case n if n == 0 => ...
    case n if n >= 0 => ...
    case n if n <= 0 => ...
    case n           =>  unreachable!()
}

Use of bug! and unreachable! should be avoided whenever possible.

Type Match

Flix supports a type match construct that enables compile-time pattern matching on the type of a polymorphic value.

For example, we can write a function that inspects the type of its argument:

def inspect(x: a): String = typematch x {
    case _: Int32   => "x is an Int32"
    case _: String  => "x is a String"
    case _: _       => "x is neither an Int32 nor a String"
}

def main(): Unit \ IO = 
    println(inspect(12345));
    println(inspect("abc"));
    println(inspect(false))

Here the inspect function pattern matches on the type of the formal parameter x using the typematch construct. For example, if the type of x is an Int32 then the function returns the string "x is an Int32" and so forth.

The typematch construct is eliminated at compile-time, hence there is no runtime cost.

As the example shows, the typematch construct always requires a default case. This is because Flix has infinitely many types, and a typematch cannot cover all of them.

A type match can also inspect more complex types, as the following example shows:

def inspect(x: a): String = typematch x {
    case _: List[Int32]   => "x is a list of integers"
    case _: List[String]  => "x is a list of strings"
    case _: _             => "x is something else"
}

def main(): Unit \ IO = 
    println(inspect(1 :: 2 :: 3 :: Nil));
    println(inspect("abc" :: "def" :: Nil));
    println(inspect(false))

We can also bind values with type match, as the following example shows:

def inspect(x: a): String = typematch x {
    case i: Int32   => "${i * i}"
    case s: String  => String.toUpperCase(s)
    case _: _ 		=> "-"
}

def main(): Unit \ IO = 
    println(inspect(12345));
    println(inspect("abc"));
    println(inspect(false))

Warning: While type match is a powerful meta-programming construct, it should be sparingly and with great care.

A typical legitimate use case for type match is when we want to work around limitations imposed by the JVM. For example, the Flix Standard Library use type match to implement the Array.copyOfRange function as shown below:

def copyOfRange(_: Region[r2], b: Int32, e: Int32, a: Array[a, r1]): ... =
typematch a {
    case arr: Array[Int16, r1] =>
        import static java.util.Arrays.copyOfRange(Array[Int16, r1], Int32, Int32): ...
    ...
    case arr: Array[Int32, r1] =>
        import static java.util.Arrays.copyOfRange(Array[Int32, r1], Int32, Int32): ...
    ...
    // ... additional cases ...
}

Here type match allows us to call the right overloaded version of java.util.Arrays.copyOfRange. Thus Flix programmers can use our version of copyOfRange (i.e., Array.copyOfRange) while underneath the hood, we always call the most efficient Java version.

Purity Reflection

Note: This is an advanced feature and should only be used by experts.

Purity reflection enables higher-order functions to inspect the purity of their function arguments.

This allows us to write functions that use selective lazy and/or parallel evaluation.

For example, here is the implementation of Set.count:

@ParallelWhenPure
pub def count(f: a -> Bool \ ef, s: Set[a]): Int32 \ ef =
    typematch f {
        case g: a -> Bool \ {} =>
            let h = (k, _) -> g(k);
            let Set(t) = s;
            RedBlackTree.parCount(threads() - 1, h, t)
        case g: a -> Bool \ ef => foldLeft((b, k) -> if (g(k)) b + 1 else b, 0, s)
        case _: _ => unreachable!()
    }

Here the typematch construct is used to reflect on the purity of f:

• If f is pure then we evaluate Set.count in parallel over the elements of the set.
• If f is effectful then we use an ordinary (single-threaded) fold.

The advantage is that we get parallelism for free – if f is pure.

Type-Level Programming

Note: This feature is experimental. Do not use in production.

This section assumes prior familiarity with type-level programming and phantom types.

Type-Level Booleans

A unique Flix feature is its support for type-level Boolean formulas. This means true and false are types, but also that formulas such as x and (not y) are types. A type-level Boolean formulas has kind Bool. Two type-level Boolean formulas are equal if the formulas are equivalent (i.e. have the same truth tables). For example, the two types true and x or not x are the same type.

While type-level Boolean formulas are not as expressive as general refinement types or dependent types they support complete type inference and parametric polymorphism. This means that they are very ergonomic to work with.

We can use type-level Boolean formulas to statically enforce program invariants.

We illustrate with a few examples:

Humans and Vampires

///
/// We can use a phantom type-level Boolean to model whether a person is alive 
/// or is undead (i.e. a vampire).
///
enum Person[_isAlive: Bool] {
    /// A person has a name, an age, and is modelled as a record.
    case P({name = String, age = Int32})
}

/// 
/// We interpret the Boolean `true` is alive and the Boolean `false` as undead
/// (i.e. a vampire).
///
type alias Alive  = true
type alias Undead = false

///
/// A person who is born is alive. 
///
def born(name: String): Person[Alive] =
    Person.P({name = name, age = 0})

///
/// A person who is alive and is bitten becomes a vampire.
///
/// Note that the type system enforces that an already undead (i.e. a vampire) 
/// cannot be bitten again. 
///
def bite(p: Person[Alive]): Person[Undead] = match p {
    /// The implementation is not important; it simply restructs the person.
    case Person.P(r) => Person.P(r)
}

///
/// Two persons can be married, but only if they are both alive or both undead.
///
/// (The church does not yet recognize human-vampire marriages.)
///
/// Note that the type system enforces that both arguments have the same type.
///
def marry(_p1: Person[isAlive], _p2: Person[isAlive]): Unit = ()

///
/// We can implement a more sophisticated version of born.
/// 
/// If two persons have a child then that child is a vampire if one of them is.
///
/// Note that here we use the type-level computation `isAlive1 and isAlive2` 
/// to compute whether the result is alive or undead.
///
def offspring(p1: Person[isAlive1], p2: Person[isAlive2]): Person[isAlive1 and isAlive2] = 
    match (p1, p2) {
        case (Person.P(r1), Person.P(r2)) => 
            Person.P({name = "Spawn of ${r1.name} and ${r2.name}", age = 0})
}

///
/// A person can age-- no matter if they are alive or undead.
///
/// Note that this function preserves the `isAlive` parameter. That is, if a 
/// person is alive they stay alive.
///
def birthday(p: Person[isAlive]): Person[isAlive] = match p {
    case Person.P(r) => Person.P({name = r.name, age = r.age + 1})
}

We can now illustrate how the type system enforces certain invariants.

For example, the type system ensures that person cannot be bitten twice:

let p = birthday(bite(born("Dracula")));
bite(p);

If we compile this program then the Flix compiler emits a compiler error:

❌ -- Type Error -------------------------------------------------- 

>> Expected argument of type 'Person[true]', but got 'Person[false]'.

69 |     bite(p);
              ^
              expected: 'Person[true]'

The function 'bite' expects its 1st argument to be of type 'Person[true]'.

Here we have to recall that true means Alive and false means Undead.

Common Problems

• ToString is not defined on 'a'
• Records and Complex Instances
• Expected kind 'Bool or Effect' here, but kind 'Type' is used

ToString is not defined on 'a'

Given the program:

def main(): Unit \ IO = 
    let l = Nil;
    println(l)

The Flix compiler reports:

❌ -- Type Error ---------------------

>> ToString is not defined on a. [...]

3 |     println(l)
        ^^^^^^^^^^
        missing ToString instance

The issue is that the empty list has the polymorphic type: List[a] for any a. This means that Flix cannot select the appropriate ToString type class instance.

The solution is to specify the type of the empty list. For example, we can write:

def main(): Unit \ IO = 
    let l: List[Int32] = Nil;
    println(l)

which solves the problem because Flix can find an instance of ToString type class for the concrete type List[Int32].

Records and Complex Instances

Given the program:

instance Eq[{fstName = String, lstName = String}]

The Flix compiler reports:

❌ -- Instance Error --------------------------------------------------

>> Complex instance type '{ fstName = String, lstName = String }' in 'Eq'.

1 | instance Eq[{fstName = String, lstName = String}]
             ^^
             complex instance type

This is because, at least for the moment, it is not possible type define type class instances on records (or Datalog schema rows). This may change in the future. Until then, it is necessary to wrap the record in an algebraic data type. For example:

enum Person({fstName = String, lstName = String})

and then we can implement Eq for the Person type:

instance Eq[Person] {
    pub def eq(x: Person, y: Person): Bool = 
        let Person(r1) = x;
        let Person(r2) = y;
        r1.fstName == r2.fstName and r1.lstName == r2.lstName
}

Expected kind 'Bool or Effect' here, but kind 'Type' is used

Given the program:

enum A[a, b, ef] {
    case A(a -> b \ ef)
}

The Flix compiler reports:

❌ -- Kind Error -----------------------------------------------

>> Expected kind 'Bool or Effect' here, but kind 'Type' is used.

2 |     case A(a -> b \ ef)
                        ^^
                        unexpected kind.

Expected kind: Bool or Effect
Actual kind:   Type

This is because Flix assumes every un-annotated type variable to have kind Type. However, in the above case a and b should have kind Type, but ef should have kind Bool. We can make this explicit like so:

enum A[a: Type, b: Type, ef: Bool] {
    case A(a -> b \ ef)
}

Glossary

Effect Polymorphic. A function whose effect(s) depend on the effect(s) of its function argument. See also higher-order function.

Higher-Order Function. A function that takes a function argument or returns a function.

Additional Information

More information about the Flix programming language can be found in:

• The research literature written by programming language researchers.
• A series of blog posts written by the community.

Getting Help

If you have a question or comment we are happy to help you out on our Gitter channel:

https://gitter.im/flix/Lobby

Reporting a Bug

If you encounter a bug, you can report it here:

https://github.com/flix/flix/issues

but first you may wish to talk to us on Gitter.

Research Literature

The following research papers cover specific aspects of Flix:

• The Principles of the Flix Programming Language
• Flix: A Meta Programming Language for Datalog
• Relational Nullable Types with Boolean Unification
• Fixpoints for the Masses: Programming with First-Class Datalog Constraints
• Polymorphic Types and Effects with Boolean Unification
• Implicit Parameters for Logic Programming
• Safe and Sound Program Analysis with Flix
• Tail Call Elimination and Data Representation for Functional Languages on the Java Virtual Machine
• From Datalog to Flix: A Declarative Language for Fixed Points on Lattices
• Programming a Dataflow Analysis in Flix

Blog Posts

A few people are writing about various aspects of Flix on their blogs:

Paul Butcher is writing a blog post series on Flix:

• An introduction to Datalog in Flix: Part 1
• An introduction to Datalog in Flix: Part 2
• An introduction to Datalog in Flix: Part 3
• An introduction to Datalog in Flix: Part 4

Susan Potter is writing a blog post series on Flix:

• Getting Started with Flix, Part 0

Magnus Madsen wrote a few blog posts on Flix during COVID:

• In Defense of Programming Languages
• Taming Impurity with Polymorphic Effects
• Naming Functional and Destructive Operations
• Redundancies as Compile-Time Errors
• Design Flaws in Flix

Magnus Madsen did an interview about Flix on the Happy Path Programming podcast:

• Episode 54 Flix: Designing a principled programming language with Magnus Madsen

Appendix

The appendix covers technical details such as:

• Legal Identifiers
• Operator Precedence

Identifiers

Flix has several types of identifiers:

• Uppercase name: An identifier that starts with an uppercase letter followed by any number of uppercase and lowercase letters, underscore, and exclamation mark (A…Z, a…z, _, !).
  • e.g. String, ALL_UPPER, Shriek!
  • Can be used to name: namespaces, annotations, type classes, effects, predicates (within datalog), tags (within enums), types
• Lowercase name: An identifier that starts with aa lowercase letter followed by any number of uppercase and lowercase letters, underscore, and exclamation mark (A…Z, a…z, _, !).
  • e.g. anIdentifier, x, this_and_that
  • Can be used to name: annotations, attributes (within datalog), functions, labels (within records), variables
• Greek name: An identifier consisting of any combination of letters from the Greek alphabet (the unicode range U+0370 to U+03FF).
  • e.g. Χαίρετε, αναγνωριστικό
  • Can be used to name: functions, variables
• Math name: An identifier consisting of any combination of math symbols (the unicode range U+2190 to U+22FF).
  • e.g. ⊆, √, ⊙
  • Can be used to name: functions, variables
• Operator name: An identifier of minimum length 2 consisting of any combination of +, -, *, <, >, =, !, &, |, ^, and $.
  • e.g. >==>, <*>
  • Can be used to name: functions

Note that greek letters, math symbols, and operator letters cannot be combined within a single identifier.

Reserved Identifiers

The following are reserved by Flix and cannot be redefined within user code:

!=, **, .., ::, :=, <-, <=, ==, =>, >=, or, &&&, <+>, <<<, <=>, >>>, ???, ^^^, and, mod, not, rem, |||, ~~~, $DEFAULT$, *, +, -, /, :, <, >, @, Absent, Bool, Impure, Nil, Predicate, Present, Pure, Read, RecordRow, Region, SchemaRow, Type, Write, alias, case, catch, chan, class, def, deref, else, enum, false, fix, force, if, import, inline, instance, into, lat, law, lawful, lazy, let, match, namespace, null, opaque, override, pub, ref, region, reify, reifyBool, reifyEff, reifyType, rel, sealed, set, spawn, Static, true, type, use, where, with, discard, object

Precedence

1. Unary operators (+, -, ~~~, and not)
2. User-defined operators (including operators defined in the standard library such as |>)
3. Functions applied infix with backticks
4. Composition (<+>)
5. Multiplicative (**, *, /, mod, and rem)
6. Additive (+ and -)
7. Shift (<<< and >>>)
8. Comparison (<=, >=, <, and >)
9. Equality (==, !=, and <==>)
10. Bitwise And (&&&)
11. Bitwise Xor (^^^)
12. Bitwise Or (|||)
13. Logical and
14. Logical or
15. Channel <-