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.
  • traits with higher-kinded types.
  • structured concurrency based on channels and light-weight processes.

In addition, 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.empty(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 \ {r, 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] \ {r, 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 \ {r, 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 21+.

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

$ java -version

which should print something like:

openjdk version "21" 2023-09-19 LTS
OpenJDK Runtime Environment Temurin-21+35 (build 21+35-LTS)
OpenJDK 64-Bit Server VM Temurin-21+35 (build 21+35-LTS, 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 21+ 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:

Visual Studio Code1

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.

Using nix

Flix can also be installed using the nix package manager. To install for the currently running shell run:

$ nix-shell -p flix

Or alternatively to install globally:

$ nix-env -i flix

Then run flix run in your project directory.

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 Files.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 Files.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 = 
        forM (
            file  <- List.head(args) |> 
                     Option.toOk("Missing argument: filename");
            lines <- Files.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:

TypeSyntaxDescription
Unit()The unit value.
Booltrue, falseA boolean value.
Char'a', 'b', 'c'A character value.
Float320.0f32, 21.42f32, -21.42f32A 32-bit floating point integer.
Float640.0f64, 21.42f64, -21.42f64A 64-bit floating point integer.
Int80i8, 1i8, -1i8, 127i8, -128i8A signed 8-bit integer.
Int160i16, 123i16, -123i16A signed 16-bit integer.
Int320i32, 123i32, -123i32A signed 32-bit integer.
Int640i64, 123i64, -123i64A signed 64-bit integer.
String"hello", "world"A string value.
BigInt0ii, 123ii, -123iiAn arbitrary precision integer.
BigDecimal0.0ff, 123.45ff, -123.45ffAn arbitrary precision decimal.

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 `Int32.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 traits 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:

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:

Operation \ TypeListChainVector
Find First ElementO(1)O(n)O(1)
Find Last ElementO(n)O(n)O(1)
Find Element at IndexO(n)O(n)O(1)
ConsO(1)O(n)O(n)
AppendO(n + m)O(1)O(n + m)

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 trait.

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 hash:

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 three basic types of mutable memory:

We can use these data types 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.empty(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.empty(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.empty(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.fresh(rc, e).
  • Dereferencing a reference Ref.get(e).
  • Assigning to a reference Ref.put(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.fresh(rc, e) operation allocates a reference cell in a region of the heap and returns its location, the Ref.get operation dereferences a location and returns the content of a reference cell, and the assignment Ref.put 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.fresh(rc, e) function. For example:

region rc {
    let c = Ref.fresh(rc, 42);
    println(Ref.get(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 Ref.get function. For example:

region rc {
    let c = Ref.fresh(rc, 42);
    let x = Ref.get(c);
    let y = Ref.get(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.fresh(rc, 0);
    Ref.put(Ref.get(c) + 1, c);
    Ref.put(Ref.get(c) + 1, c);
    Ref.put(Ref.get(c) + 1, c);
    println(Ref.get(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.fresh(rc, 0))

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

def increment(c: Counter[r]): Unit \ r =
    let Counter.Counter(l) = c;
    Ref.put(Ref.get(l) + 1, l)

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.fresh(rc, 42);
    let l2 = l1;
    Ref.put(84, l2);
    println(Ref.get(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.fresh(rc, 42);
    let l2 = Ref.fresh(rc, l1);
    let rs = Ref.get(Ref.get(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.fresh(rc, 1), Ref.fresh(rc, 2));
    Ref.put(123, fst(p))
};

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.fresh(rc, "Lucky"), lstName = Ref.fresh(rc, "Luke") };
    Ref.put("Unlucky", r#fstName)
};

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.empty(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.empty(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.empty(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.

Structs

Flix supports mutable scoped structs. A struct is a sequence of user-defined fields. Fields are immutable by default, but can made mutable by marking them with the mut modifier. Like all mutable memory in Flix, every struct must belong to some region.

Structs are the mutable alternative to extensible records which are immutable.

The fields of a struct are unboxed, i.e. primitive types do not cause indirection. Thus structs are a memory efficient data structure that can be used to implement higher-level mutable data structures, e.g. mutable lists, mutable stacks, mutable queues, and so forth.

Flix supports three operations for working with structs:

  • Creating a struct instance in a region with new Struct @ rc { ... }.
  • Accessing a field of a struct with struct->field.
  • Updating a mutable field of a struct with struct->field = ....

Each operation has an effect in the region of the struct.

Declaring a Struct

We can declare a struct as follows:

struct Person[r] {
    name: String,
    mut age: Int32,
    mut height: Int32
}

Here we declare a struct with three fields: name, age, and height. The name field is immutable, i.e. cannot be changed once the struct instance has been created. The age and heights are mutable and hence can be changed after creation. The Person struct has one type parameter: r which specifies the region that the struct belongs to.

Every struct must have a region type parameter and it must be the last in the type parameter list.

Creating a Struct

We can create an instance of the Person struct as follows:

mod Person {
    pub def mkLuckyLuke(rc: Region[r]): Person[r] \ r =
        new Person @ rc { name = "Lucky Luke", age = 30, height = 185 }
}

The mkPerson function takes one argument: the region capability rc to associate to the struct with.

The syntax:

new Person @ rc { name = "Lucky Luke", age = 30, height = 185 }

specifies that we create a new instance of the Person struct in the region rc. We then specify the values of each field of the struct. All struct fields must be initialized immediately and explicitly.

In addition, the fields must be initialized in their declaration order.

For example, if we write:

new Person @ rc { age = 30, name = "Lucky Luke", height = 185 }

The Flix compiler emits the error:

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

>> Struct fields must be initialized in their declaration order.

Expected: name, age, height
Actual  : age, name, height

11 |         new Person @ rc { age = 30, name = "Lucky Luke", height = 185 }
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
             incorrect order

Reading and Writing Fields

We can read and write fields of a struct using the field access operator ->. For example:

mod Person {
    pub def birthday(p: Person[r]): Unit \ r =
        p->age = p->age + 1;
        if(p->age < 18) {
            p->height = p->height + 10
        } else {
            ()
        }
}

The birthday function takes a Person struct p and mutates its age and height fields.

For example, in the line:

p->age = p->age + 1;

we access the current age as p->age, increment it, and store the result back in the age field.

We must distinguish between the struct field access operator -> and the function arrow   ->  . The former has no space around it, whereas the latter should have space on both sides. In summary:

  • s->f: is a struct field access of field f on struct s.
  • x -> x: is a function from formal parameter x to the variable expression x.

Field Visibility

In Flix, the fields of a struct are only visible from within its companion module. We can think of this as a form of compiler-enforced encapsulation.

For example, if we write:

struct Point[r] {
    x: Int32,
    y: Int32
}

def area(p: Point[r]): Int32 \ r = 
    p->x * p->y

The Flix compiler emits two errors:

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

>> Undefined struct field 'x'.

7 |     p->x * p->y
           ^
           undefined field

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

>> Undefined struct field 'y'.

7 |     p->x * p->y
                  ^
                  undefined field

Instead, we should define the area function inside the companion module:

struct Point[r] {
    x: Int32,
    y: Int32
}

mod Point { // Companion module for Point
    pub def area(p: Point[r]): Int32 \ r = 
        p->x * p->y
}

If we want to provide access to the ields of a struct from outside its companion module, we can introduce explicit getters and setters. For example:

mod Point {
    pub def getX(p: Point[r]): Int32 \ r = p->x
    pub def getY(p: Point[r]): Int32 \ r = p->y
}

Thus access to the fields of struct is tightly controlled.

Immutable and Mutable Fields

In Flix, every field of a struct is either immutable or mutable. A mutable field must be marked with the mut modifier. Otherwise the field is immutable by default, i.e. the value of the field cannot be changed once the struct instance has been created.

For example, we can define a struct to represent a user:

struct User[r] {
    id: Int32,
    mut name: String,
    mut email: String
}

Here the identifier id is immutable and cannot be changed whereas the name and email fields can be changed over the lifetime of the struct instance.

If we try to modify an immutable field:

mod User {
    pub def changeId(u: User[r]): Unit \ r =
        u->id = 0
}

The Flix compiler emits an error:

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

>> Modification of immutable field 'id' on User'.

9 |         u->id = 0
               ^^
               immutable field

Mark the field as 'mut' in the declaration of the struct.

We remark that field immutability is not transitive.

For example, we can define a struct:

struct Book[r] {
    title: String,
    authors: MutList[String, r]
}

where the authors field is immutable.

However, since a MutList can be changed, we can write:

mod Book {
    pub def addAuthor(a: String, b: Book[r]): Unit \ r =
        MutList.push!(a, b->authors)
}

Here we are not changing the field of the struct. We are changing the underlying mutable list.

Recursive and Polymorphic Structs

We can define a struct for a binary search tree that is recursive and polymorphic:

struct Tree[k, v, r] {
    key: k,
    mut value: v,
    mut left: Option[Tree[k, v, r]],
    mut right: Option[Tree[k, v, r]]
}

If we assume that Tree[k, v, r] is sorted, we can define a search function:

mod Tree {
    // A function to search the tree `t` for the given key `k`.
    pub def search(k: k, t: Tree[k, v, r]): Option[v] \ r with Order[k] =
        match (Order.compare(k, t->key)) {
            case Comparison.EqualTo  => Some(t->value)
            case Comparison.LessThan =>
                // Search in the left subtree.
                match t->left {
                    case None            => None
                    case Some(leftTree)  => search(k, leftTree)
                }
            case Comparison.GreaterThan =>
                // Search in the right subtree.
                match t->right {
                    case None            => None
                    case Some(rightTree) => search(k, rightTree)
                }
        }
}

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.empty(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.empty(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.empty(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:

ActionConstruct
Print all elements in a collection.Foreach
Apply an effectful operation to each element in a collection.Foreach
Build a new collection from existing collections.Foreach-Yield
Transform the elements of a collection.Foreach-Yield
Convert a collection of one type into another type.Foreach-Yield
Work with Options and Results.Monadic For-Yield
flatMap through a Monad.Monadic For-Yield
Work with ValidationsApplicative For-Yield

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
}

Matching on Records

The above also works for record types; however, the syntax is slightly different. Let us rewrite the Shape type from before, this time using records.

enum Shape {
    case Circle({ radius = Int32 })
    case Square({ width = Int32 })
    case Rectangle({ height = Int32, width = Int32 })
}

def area(s: Shape): Int32 = match s {
    case Shape.Circle({ radius })           => 3 * (radius * radius)
    case Shape.Square({ width })            => width * width
    case Shape.Rectangle({ height, width }) => height * width
}

In the example above, we implicitly require that each pattern has exactly the specified labels. No more, no less. However, in general, the syntax for record patterns is similar to their types. Thus, we can match on a record that has at least one specific label.

def f(r: { height = Int32 | a }): Int32 = match r {
    case { height | _ } => height
    // The extension has a wildcard pattern since it is unused
}

Note, however, that the pattern also implies a type, thus the following example will not work.

def badTypes(r: { height = Int32 | a }): Int32 = match r {
    case { height } => height
}

Additionally, all cases must have the same type, so this will also not work:

match ??? {
    case { height | _ } => height
    case { height }     => height
}

This may be a contrived example, but it demonstrates a common pitfall, which is easily fixed.

This is because the first case is a polymorphic record with a defined height-label, whereas the second case matches on a closed record that only has the height-label defined.

Additionally, the { label } pattern is actually syntactic sugar for { label = pattern }. Thus, if you are dealing with multiple records, then it may be necessary to use different patterns.

def shadowing(r1: { height = Int32 | a }, r2: { height = Int32 | b }): Int32 =
    match (r1, r2) {
        case ({ height | _ }, { height | _ }) => height + height
        // This does not work because `height = height` is defined twice
    }

However, renaming the variables makes the program type check.

def renaming(r1: { height = Int32 | a }, r2: { height = Int32 | b }): Int32 =
    match (r1, r2) {
        case ({ height = h1 | _ }, { height = h2 | _ }) => h1 + h2
    }

To summarize, here are a few examples of record patterns:

  • { } - the empty record
  • { radius = r } - a record containg only the label radius where the value is bound to r in the scope
  • { radius } - a record containing only the label radius (this is actually syntactic sugar for { radius = radius })
  • { radius | _ } - a record containg at least the label radius
  • { radius | r } - a record containg at least the label radius where the rest of the record is bound to r

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.

Let-pattern-matches work well with records, as they allow you to destructure a record and only use the labels you are interested in:

let { height | _ } = r;
height + height

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 Trait

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

///
/// A trait for immutable data structures that can be iterated.
///
pub trait Iterable[t] {
     ///
    /// The element type of the Iterable.
    ///
    type Elm[t]: Type

    ///
    /// Returns an iterator over `t`.
    ///
    pub def iterator(rc: Region[r], t: t): Iterator[Iterable.Elm[t], r + aef, r] \ (r + aef) where Iterable.Aef[t] ~ aef
}

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 Trait

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

pub trait Collectable[t: Type] {
    ///
    /// The element type of the Collectable.
    ///
    type Elm[t]: Type

    ///
    /// Run an Iterator collecting the results.
    ///
    pub def collect(iter: Iterator[Collectable.Elm[t], ef, r]): t \ (ef + Collectable.Aef[t] +  r)
}

Without going into details, the Collectable trait 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 trait). The forM construct also supports a guard-expression that uses empty (which is provided by the MonadZero trait).

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 trait 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 trait. 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 \ r =
    Channel.send("Meow!", tx)

def woof(tx: Sender[String, r]): Unit \ 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 \ { 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:

Function TypeSyntaxShort Hand
The type of a pure function from a to b.a -> b \ {}a -> b
The type of an effect polymorphic function from a to b with effect ef.a -> b \ efn/a
The type of an effect polymorphic function from a to b with effect ef1 and ef2 (i.e. pure if both ef1 and ef2 are true.)a -> b \ { ef1, ef2 }n/a

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 Trait

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

For example, we can write:

mod Zoo {
    pub trait 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 trait 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 trait 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.

Trait Companions

Every trait declaration also gives rise to a companion module.

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

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

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

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 trait declaration and its companion module. Consequently, Addable.add refers to the trait 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 trait cannot be redefined by instances of the associated trait. Thus we should only put members into the companion namespace when we do not intend to redefine them later.

Traits

Traits, also known as type classes, support abstraction and modularity. The Flix trait system is similar to that of Haskell and Rust, but not identical. Traits in Flix support associated types, associated effects, and higher-kinded types.

We illustrate traits with an example.

We can define equality on Option[Int32] as follows:

def equals(x: Option[Int32], y: Option[Int32]): Bool = 
    match (x, y) {
        case (None, None)         => true
        case (Some(v1), Some(v2)) => v1 == v2
        case _                    => false
    }

We can also define equality on List[Int32] as follows:

def equals(x: List[Int32], y: List[Int32]): Bool = 
    match (x, y) {
        case (Nil, Nil)           => true
        case (v1 :: xs, v2 :: ys) => v1 == v2 and equals(xs, ys)
        case _                    => false
    }

But what if we wanted a common abstraction for data types which support equality?

Here we can use traits. We can define an Equatable trait:

trait Equatable[t] {
    pub def equals(x: t, y: t): Bool
}

which has a single equals trait signature. The trait is polymorphic over the type parameter t which means that we can implement Equatable for both Option[t] and List[t]:

instance Equatable[Option[t]] with Equatable[t] {
    pub def equals(x: Option[t], y: Option[t]): Bool = 
        match (x, y) {
            case (None, None)         => true
            case (Some(v1), Some(v2)) => Equatable.equals(v1, v2)
            case _                    => false
        }
}

Notice that we did not implement Equatable for Option[Int32], but instead for any Option[t] as long as t itself is equatable. Moreover, instead of comparing v1 and v2 directly using ==, we call Equatable.equals on them.

We can also implement Equatable for List[t]:

instance Equatable[List[t]] with Equatable[t] {
    pub def equals(x: List[t], y: List[t]): Bool = 
        use Equatable.equals;
        match (x, y) {
            case (Nil, Nil)           => true
            case (v1 :: xs, v2 :: ys) => equals(v1, v2) and equals(xs, ys)
            case _                    => false
        }
}

Assuming we also implement Equatable for Int32, we can use Equatable to compute whether two Option[Int32] values are equal. But we can also compute if two Option[List[Int32]] values are equal! This demonstrates the power of abstraction: We have implemented instances for Option[t] and List[t] and we can now reuse these instances everywhere.

We can use our newly defined Equatable trait to write polymorphic functions.

For example, we can define a function to compute if an element occurs in a list:

def memberOf(x: t, l: List[t]): Bool with Equatable[t] = 
    match l {
        case Nil     => false
        case y :: ys => Equatable.equals(x, y) or memberOf(x, ys)
    }

We can use memberOf for a list of any type, as the element type implements Equatable.

Note: In the Flix Standard Library the Equatable trait is called Eq. Moreover, the == operator is syntactic sugar for the trait signature Eq.eq.

Sealed Traits

We can declare a trait as sealed to restrict who can implement the trait.

For example:

mod Zoo {
    sealed trait Animal[a] {
        pub def isMammal(x: a): Bool
    }

    instance Animal[Giraffe] {
        pub def isMammal(_: Giraffe): Bool = true
    }

    instance Animal[Penguin] {
        pub def isMammal(_: Penguin): Bool = true
    }

    pub enum Giraffe
    pub enum Penguin
}

Here we can implement instances for Animal and Giraffe because they occur in the same module as the Animal trait. But we cannot implement Animal from outside the Zoo module. If we try:

mod Lake {
    pub enum Swan

    instance Zoo.Animal[Swan] {
        pub def isMammal(_: Swan): Bool = false
    }
}

then Flix reports:

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

>> Class 'Zoo.Animal' is sealed from the module 'Lake'.

21 |     instance Zoo.Animal[Swan] {
                  ^^^^^^^^^^
                  sealed class.

Malformed Traits

A trait is not a C# or Java-style interface. Specifically:

  • every trait must have exactly one type parameter, and
  • every signature must mention that type parameter.

For example, the following trait is incorrect:

trait Animal[a] {
    pub def isMammal(x: a): Bool      // OK     -- mentions a.
    pub def numberOfGiraffes(): Int32 // NOT OK -- does not mention a.
}

If we compile the above trait, Flix reports:

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

>> Unexpected signature 'numberOfGiraffes' which does not mention the type 
>> variable of the trait.

7 |     pub def numberOfGiraffes(): Int32 
                ^^^^^^^^^^^
                unexpected signature.

The problem is that the signature for numberOfGiraffes does not mention the type parameter a.

Complex Instances

A trait instance must be defined on:

  • exactly one type constructor —
  • that is applied to zero or more distinct type variables.

For example, given the Equatable trait from before:

trait Equatable[t] {
    pub def equals(x: t, y: t): Bool
}

We can implement instances for e.g.:

  • Option[a]
  • List[a]
  • (a, b)

but we cannot implement instances for e.g.:

  • Option[Int32]
  • List[String]
  • (a, Bool)
  • Map[Int32, v]

If we try to implement an instance for e.g. List[Int32] Flix reports:

❌ -- Instance Error -------------------------------------------------- 

>> Complex instance type 'List[Int32]' in 'Equatable'.

6 | instance Equatable[List[Int32]] {
             ^^^^^^^^^
             complex instance type

An instance type must be a type constructor applied to zero or more 
distinct type variables.

Overlapping Instances

We cannot implement two instances of of the same trait for overlapping types.

For example, if we try to implement two instances of Equatable for List[t]:

instance Equatable[List[t]] {
    pub def equals(x: List[t], y: List[t]): Bool = ???
}

instance Equatable[List[t]] {
    pub def equals(x: List[t], y: List[t]): Bool = ???
}

then Flix reports:

❌ -- Instance Error -------------------------------------------------- 

>> Overlapping instances for 'Equatable'.

1 | instance Equatable[List[t]] {
              ^^^^^^^^^
              the first instance was declared here.

4 | instance Equatable[List[t]] {
             ^^^^^^^^^
             the second instance was declared here.

Essential Traits

Practical programming in Flix requires knowledge of at least three traits: Eq, Order, and ToString.

The Eq Trait

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

trait 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. When we implement eq we automatically get an implementation of Eq.neq.

The Order Trait

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

trait 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 trait, 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
}

When we implement compare, we automatically get implementations of Order.less, Order.lessThan, Order.greater, Order.greaterEqual, Order.max, and Order.min.

The ToString Trait

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

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

Flix uses the ToString trait 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 traits.

Automatic Derivation

Flix supports automatic derivation of several traits, 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.
  • Coerce - to convert simple data types to their underlying representation.

Derivation of Eq and Order

We can automatically derive instances of the Eq and Order traits 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 trait (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.

Derivation of Coerce

We can automatically derive implementations of the Coerce type class. The Coerce class converts a simple (one-case) data type to its underlying implementation.

enum Shape with Coerce {
    case Circle(Int32)
}

def main(): Unit \ IO =
    let c = Circle(123);
    println("The radius is ${coerce(c)}")

We cannot derive Coerce for an enum with more than one case. For example, if we try:

enum Shape with Coerce {
    case Circle(Int32)
    case Square(Int32)
}

The Flix compiler emits a compiler error:

❌ -- Derivation Error --------------------------------------------------

>> Cannot derive 'Coerce' for the non-singleton enum 'Shape'.

1 | enum Shape with Coerce {
                    ^^^^^^
                    illegal derivation

'Coerce' can only be derived for enums with exactly one case.

Associated Types

An associated type is a type member of a trait that is specified by each trait instance. Associated types are often considered a more natural alternative to multi-parameter type classes.

We illustrate associated types with an example.

We can define a trait for types that can be added:

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

We can implement multiple instances of the Addable trait for types such as floating-point numbers, integers, and strings. For example, here is the instance for Int32:

instance Addable[Int32] {
    pub def add(x: Int32, y: Int32): Int32 = x + y
}

and here is one for String:

instance Addable[String] {
    pub def add(x: String, y: String): String = "${x}${y}"
}

But what if we wanted to add an element to a set?

Intuitively, we would like to write:

instance Addable[Set[a]] with Order[a] {
    pub def add(s: Set[a], x: a): Set[a] = Set.insert(x, s)
}

But the signature of add does not match the signature declared in Addable.

We can overcome this problem and increase the flexibility of Addable with an associated type:

trait Addable[t] {
    type Rhs
    pub def add(x: t, y: Addable.Rhs[t]): t
}

The Addable trait now has an associated type called Rhs. We refer to it as Addable.Rhs[t] as seen in the signature of add. Whenever we declare an instance of Addable, we must specify the associated type.

We can still implement instances for integers and strings, as before. For example:

instance Addable[Int32] {
    type Rhs = Int32
    pub def add(x: Int32, y: Int32): Int32 = x + y
}

But we can also implement an instance that allows adding an element to a set:

instance Addable[Set[a]] with Order[a] {
    type Rhs = a
    pub def add(s: Set[a], x: a): Set[a] = Set.insert(x, s)
}

The important point is that each trait instance specifies the associated type.

We might wonder if we can specify two instances for Set[a]: (a) one for adding an element to a set, as above, and (b) one for adding two sets:

instance Addable[Set[a]] with Order[a] {
    type Rhs = Set[a]
    pub def add(x: Set[a], y: Set[a]): Set[a] = Set.union(x, y)

}

But while each instance is valid on its own, we cannot have both:

❌ -- Instance Error -------------------------------------------------- 

>> Overlapping instances for 'Addable'.

...

If we had such overlapping instances, an expression like Addable.add(Set#{}, Set#{}) would become ambiguous: Are we adding two sets? Or are we adding the empty set to a set?

Example: A ForEach Trait

We can use associated types to define a trait for collections that have a forEach function:

trait ForEach[t] {
    type Elm
    pub def forEach(f: ForEach.Elm[t] -> Unit \ ef, x: t): Unit \ ef
}

Here t is the type of the collection and the associated type Elm is the type of its elements. We can implement several instances for ForEach. For example, we can implement an instance for List[a]:

instance ForEach[List[a]] {
    type Elm = a
    pub def forEach(f: a -> Unit \ ef, x: List[a]): Unit \ ef = List.forEach(f, x)
}

We can also implement an instance for Map[k, v]:

instance ForEach[Map[k, v]] {
    type Elm = (k, v)
    pub def forEach(f: ((k, v)) -> Unit \ ef, x: Map[k, v]): Unit \ ef = 
        Map.forEach(k -> v -> f((k, v)), x)
}

What is interesting and useful is that we can define the element type to be key-value pairs. We need extra parentheses around the argument to f because we want it to take a pair.

We can implement an instance for String where we can iterate through each individual character:

instance ForEach[String] {
    type Elm = Char
    pub def forEach(f: Char -> Unit \ ef, x: String): Unit \ ef = 
        x |> String.toList |> List.forEach(f)
}

Example: A Collection Trait

As another example, we can define a trait for collections:

trait Collection[t] {
    type Elm
    pub def empty(): t
    pub def insert(x: Collection.Elm[t], c: t): t
    pub def toList(c: t): List[Collection.Elm[t]]
}

Here t is the type of the collection and Elm is the type of its elements. Every collection must support three operations: empty, insert, and toList.

We can implement an instance of Collection for Vector[a]:

instance Collection[Vector[a]] {
    type Elm = a
    pub def empty(): Vector[a] = Vector.empty()
    pub def insert(x: a, c: Vector[a]): Vector[a] = Vector.append(c, Vector#{x})
    pub def toList(c: Vector[a]): List[a] = Vector.toList(c)
}

And we can implement an instance of Collection for Set[a]:

instance Collection[Set[a]] with Order[a] {
    type Elm = a
    pub def empty(): Set[a] = Set.empty()
    pub def insert(x: a, c: Set[a]): Set[a] = Set.insert(x, c)
    pub def toList(c: Set[a]): List[a] = Set.toList(c)
}

Equality Constraints

We sometimes want to write polymorphic functions where we restrict an associated type.

For example, returning to the example of the Collection trait, we can write a function where we require that the element type is an Int32. This allows us to write a sum function:

def sum(c: t): Int32 with Collection[t] where Collection.Elm[t] ~ Int32 = 
    Collection.toList(c) |> List.sum

Here the where clause contains a list of type equality constraints. Specifically, the equality constraint Collection.Elm[t] ~ Int32 assert that sum can be used with any type t for which there is an instance of Collection as long as the element type of that instance is equal to Int32. This restriction ensures that the elements of the collection are integers and allows us to call List.sum.

Default Types

We can define a default type for an associated type.

Returning to Addable, we can define the associated type Rhs with t as its default:

trait Addable[t] {
    type Rhs = t  // Associated type with default type.
    pub def add(x: t, y: Addable.Rhs[t]): t
}

Here we specify that if Rhs is not defined by an instance implementation then it defaults to t. The upshot is that we can define an instance for Int32:

instance Addable[Int32] {
    pub def add(x: Int32, y: Int32): Int32 = x + y
}

without having to explicit define type Rhs = Int32.

Associated Effects

We have seen how associated types increase the flexibility of traits by allowing each instance to specify concrete types for the associated types. Associated effects work in the same manner, but concern effects.

We motivate the need for associated effects with a simple example.

We can define a trait for types that can be divded:

trait Dividable[t] {
    pub def div(x: t, y: t): t
}

and we can implement the trait for e.g. Float32 and Int32:

instance Dividable[Float32] {
    pub def div(x: Float32, y: Float32): Float32 = x / y
}

instance Dividable[Int32] {
    pub def div(x: Int32, y: Int32): Int32 = x / y
}

But what about division-by-zero? Assume we want to raise an exception and have it tracked by the type and effect system. We would like to write:

pub eff DivByZero {
    pub def throw(): Void
}

instance Dividable[Int32] {
    pub def div(x: Int32, y: Int32): Int32 \ DivByZero = 
        if (y == 0) do DivByZero.throw() else x / y
}

But unfortunately this does not quite work:

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

>> Mismatched signature 'div' required by 'Dividable'.

14 |     pub def div(x: Int32, y: Int32): Int32 \ DivByZero = 
                 ^^^
...

The problem, as the compiler explains, is that the definition of div in the trait Dividable is declared as pure. Hence we are not allowed to raise an exception. We could change the signature of Dividable.div, but that would be problematic for the Float32 instance, because division-by-zero returns NaN and does not raise an exception.

The solution is to use an associated effect: then the instance for Int32 can specify that a DivByZero exception may be raised whereas the instance for Float32 can be pure. We add an associated effect Aef to Dividable:

trait Dividable[t] {
    type Aef: Eff
    pub def div(x: t, y: t): t \ Dividable.Aef[t]
}

and we re-implement the instances for Float32 and Int32:

instance Dividable[Float32] {
    type Aef = { Pure } // No exception, div-by-zero yields NaN.
    pub def div(x: Float32, y: Float32): Float32 = x / y
}

instance Dividable[Int32] {
    type Aef = { DivByZero }
    pub def div(x: Int32, y: Int32): Int32 \ DivByZero = 
        if (y == 0) do DivByZero.throw() else x / y
}

Associated Effects and Regions

We often want to use associated effects in combination with regions.

Assume we have the ForEach trait from the before:

trait ForEach[t] {
    type Elm
    pub def forEach(f: ForEach.Elm[t] -> Unit \ ef, x: t): Unit \ ef
}

As we have seen, we can implement it for e.g. List[t] but also Map[k, v]. But what if we wanted to implement it for e.g. MutList[t, r] or MutSet[t, r]. We can try:

instance ForEach[MutList[t, r]] {
    type Elm = t
    pub def forEach(f: t -> Unit \ ef, x: MutList[t, r]): Unit \ ef = 
        MutList.forEach(f, x)
}

But Flix reports:

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

>> Unable to unify the effect formulas: 'ef' and 'ef + r'.

9 |         MutList.forEach(f, x)
            ^^^^^^^^^^^^^^^^^^^^^
            mismatched effect formulas.

The problem is that MutList.forEach has an effect in the region r, but the signature of forEach in the trait only permits the ef effect from the function f.

We can solve the problem by extending the ForEach trait with an associated effect:

trait ForEach[t] {
    type Elm
    type Aef: Eff
    pub def forEach(f: ForEach.Elm[t] -> Unit \ ef, x: t): Unit \ ef + ForEach.Aef[t]
}

We must specify that Aef is an effect with the kind annotation Aef: Eff. If we don't specify the kind then it defaults to Type which is not what we want here.

With the updated ForEach trait, we can implement it for both List[t] and MutList[t]:

instance ForEach[List[t]] {
    type Elm = t
    type Aef = { Pure }
    pub def forEach(f: t -> Unit \ ef, x: List[t]): Unit \ ef = List.forEach(f, x)
}

and

instance ForEach[MutList[t, r]] {
    type Elm = t
    type Aef = { r }
    pub def forEach(f: t -> Unit \ ef, x: MutList[t, r]): Unit \ ef + r = 
        MutList.forEach(f, x)
}

Notice how the implementation for List[t] specifies that the associated effect is pure, whereas the implementation for MutList[t, r] specifies that there is a heap effect in region r.

Higher-Kinded Types

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

For example, we can write a trait 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:

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

To use higher-kinded types Flix requires us to provide kind annotations, i.e. we had to write t: Type -> Type to inform Flix that ForEach abstracts over type constructors.

We can implement an instance of the ForEach trait for Option[t]:

instance ForEach[Option] {
    pub def forEach(f: a -> Unit \ ef, o: Option[a]): Unit \ ef = match o {
        case None    => ()
        case Some(x) => f(x)
    }
}

and we can implement an instance for List[t]:

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

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

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 four situations:

  • For type parameters of non-Type kind on enums.
  • For type parameters of non-Type kind on type aliases.
  • For type parameters of non-Type kind on traits.
  • For type members of a non-Type kind in a trait.

The most common scenario where you will need a kind annotation is when you want a type parameter or type member to range over an effect.

Higher-Kinded Types vs. Associated Types

In practice higher-kinded types and associated types can be used to define similar abstractions.

For example, as we have seen, we can define the ForEach trait in two different ways:

With a higher-kinded type:

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

and with an associated type:

trait ForEach[t] {
    type Elm
    pub def forEach(f: ForEach.Elm[t] -> Unit \ ef, x: t): Unit \ ef
}

In the case of ForEach, the definition with an associated type is more flexible, since we can implement an instance for String with associated element type Char. However, higher-kinded types are still useful. For example, the Flix Standard Library defines the Functor trait as:

trait Functor[m : Type -> Type] {
    pub def map(f: a -> b \ ef, x: m[a]): m[b] \ ef
}

Notably the kind of m ensures that every Functor implementation is structure preserving. That is, we know that when we map over e.g. an Option[a] then we get back an Option[b].

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 trait. 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 trait 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 a Java Virtual Machine (JVM)-based programming language, hence:

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

Flix supports most Java features necessary for interoperability:

Thus Flix programs can reuse the Java Class Library. In addition, the Flix package manager has Maven support.

Flix and Java share the same base types, but they have different names, as shown in the table:

Flix TypeJava Type
Boolboolean
Charchar
Float32float
Float64double
Int8byte
Int16short
Int32int
Int64long
StringString

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.

1

Flix requires at least Java 21.

Creating Objects

In Flix, we can create objects using syntax similar to Java.

For example:

import java.io.File

def main(): Unit \ IO = 
    let f = new File("foo.txt");
    println("Hello World!")

Here we import the java.io.File class and instantiate a File object by calling one of its constructors using the new keyword.

The File class has multiple constructors, so we can also write:

import java.io.File

def main(): Unit \ IO = 
    let f1 = new File("foo.txt");
    let f2 = new File("bar", "foo.txt");
    println("Hello World!")

Flix resolves the constructor based on the number of arguments and their types.

As another example, we can write:

import java.io.File
import java.net.URI

def main(): Unit \ IO = 
    let f1 = new File("foo.txt");
    let f2 = new File("bar", "foo.txt");
    let f3 = new File(new URI("file://foo.txt"));
    println("Hello World!")

We can use a renaming import to resolve a clash between a Java name and a Flix module:

import java.lang.{String => JString}

def main(): Unit \ IO = 
    let s = new JString("Hello World");
    println("Hello World!")

Here JString refers to the Java class java.lang.String whereas String refers to the Flix module. Note that internally Flix and Java strings are the same.

Note: Any interaction with Java code always has the IO effect.

Note: In Flix, Java classes must be imported before they can be used. In particular, we cannot write new java.io.File(...).

Calling Object Methods

In Flix, we can call methods on Java objects using syntax similar to Java.

For example:

import java.io.File

def main(): Unit \ IO = 
    let f = new File("foo.txt");
    println(f.getName())

Here we import the java.io.File class, instantiate a File object, and then call the getName method on that object.

Like with constructors, Flix resolves the method based on the number of arguments and their types.

Here is another example:

import java.io.File

def main(): Unit \ IO = 
    let f = new File("foo.txt");
    if (f.exists())
        println("The file ${f.getName()} exists!")
    else
        println("The file ${f.getName()} does not exist!")

And here is a larger example:

import java.io.File
import java.io.FileWriter

def main(): Unit \ IO = 
    let f = new File("foo.txt");
    let w = new FileWriter(f);
    w.append("Hello World\n");
    w.close()

In the above example, we may want to catch the IOException that can be raised:

import java.io.File
import java.io.FileWriter
import java.io.IOException

def main(): Unit \ IO = 
    let f = new File("foo.txt");
    try {
        let w = new FileWriter(f);
        w.append("Hello World\n");
        w.close()
    } catch {
        case ex: IOException => 
            println("Unable to write to file: ${f.getName()}");
            println("The error message was: ${ex.getMessage()}")
    }

Calling Static Methods

In Flix, we can call static methods (i.e. class methods) using syntax similar to Java:

For example:

import java.lang.Math

def main(): Unit \ IO = 
    let n = Math.sin(3.14);
    println(n)

Like with constructors and methods, Flix resolves the static method based on the number of arguments and their types.

Here is another example:

import java.lang.Math

def main(): Unit \ IO = 
    println(Math.abs(-123i32));
    println(Math.abs(-123i64));
    println(Math.abs(-123.456f32));
    println(Math.abs(-123.456f64))

Calling Constructors or Methods with VarArgs

We can call a constructor or method that takes variable arguments using the the special syntax ...{ value1, value2, ...}. For example:

import java.nio.file.Path

def getMyPhoto(): Path \ IO =
    Path.of("Documents", ...{"Images", "me.jpg"})

Here we call the Path.of Java method which requires a single string and then a varargs array of strings.

In the special case where we want to call a constructor or method without any varargs we have to explicitly pass an empty Vector[t]. Moreover, we have to specify the type of the elements. For example:

import java.nio.file.Path

def getDocuments(): Path \ IO =
    Path.of("Documents", (Vector.empty(): Vector[String]))

When Constructor or Method Resolution Fails

In some cases the Flix compiler is unable to determine what Java constructor or method is called.

For example, in the program:

import java.lang.{String => JString}

def f(): String \ IO = 
    let o = ???;
    JString.valueOf(o)

The type of o is unknown, hence Flix cannot know if we want to call String.valueOf(boolean), String.valueOf(char), String.valueOf(double), or one of the other overloaded versions.

The solution is to put a type ascription on the relevant argument:

import java.lang.{String => JString}

def f(): String \ IO = 
    let o = ???;
    JString.valueOf((o: Bool))

The type ascription specifies that o has type Bool which allows method resolution to complete successfully. Note that the extra pair of parenthesis is required.

Calling Java Methods Known to be Pure

Any Flix expression that creates a Java object, calls a Java method, or calls a Java static method has the IO effect. This is to be expected: Java constructors and methods may have arbitrary side-effects.

If we know for certain that a Java constructor or method invocation has no side-effects, we can use an unsafe block to tell Flix to treat that expression as pure.

For example:

import java.lang.Math

def pythagoras(x: Float64, y: Float64): Float64 = // Pure, no IO effect
    unsafe Math.sqrt((Math.pow(x, 2.0) + Math.pow(y, 2.0)))

def main(): Unit \ IO = 
    println(pythagoras(3.0, 4.0))

Here we know for certain that Math.pow and Math.sqrt are pure functions, hence we can put them inside an unsafe block. Thus we are able to type check the Flix pythagoras function as pure, i.e. without the IO effect.

Warning: Do not, under any circumstances, use unsafe on expressions that have side-effects. Doing so breaks the type and effect system which can lead to incorrect compiler optimizations which can change the meaning of your program in subtle or catastrophic ways!

Partial Application of Java Constructors and Methods

Flix supports partial application of Flix functions. However, Java constructors and methods can never be partially applied. This limitation can be overcome introducing an explicit lambda.

For example:

import java.lang.{String => JString}

def main(): Unit \ IO = 
    def replaceAll(s, src, dst) = s.replaceAll(src, dst);
    let f = replaceAll("Hello World");
    let s1 = f("World")("Galaxy");
    let s2 = f("World")("Universe");
    println(s1);
    println(s2)

Here we introduce a Flix function replaceAll which calls String.replaceAll. Since replaceAll is a Flix function, we can partially apply it as shown in the example.

Reading and Writing Fields

Flix supports reading object fields and static (class) fields with standard Java syntax.

Reading Object Fields

We can read an object field as follows:

import java.awt.Point

def area(p: Point): Int32 \ IO = unsafe (p.x * p.y)

Reading Static Fields

We can read a static field as follows:

import java.lang.Math

def area(radius: Float64): Float64 = (unsafe Math.PI) * radius * radius

We import the java.lang.Math class and then we access the static PI field.

We know that the PI field will never change, hence we cast away the effect with unsafe.

Writing Object Fields

Flix supports writing to an object field with the non-standard syntax:

import java_set_field foo.bar.Baz.boolField: Unit \ IO as setField;
let o = ...;
setField(o, false)

Here the import expression creates a function named setField which we call.

Note: We are currently working on a more tolerable syntax.

Writing Static Fields

Flix supports writing to a static field with the non-standard syntax:

import static java_set_field foo.bar.Baz.StaticBoolField: Unit \ IO as setField;
let o = ...;
setField(o, false)

Note: We are currently working on a more tolerable syntax.

Here the import expression creates a function named setField which we call.

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 nested static and non-static inner classes:

For example:

package Foo.Bar;

class OuterClass {
    ...
    class InnerClass {
        ...
    }
    static class StaticInnerClass {
        public static String hello() { return "Hi"; }
    }
}

In Flix, we can access the StaticInnerClass using the import statement:

import Foo.Bar.{OuterClass$StaticInnerClass => Inner}

def main(): Unit \ IO = 
    println(Inner.hello())

A typical example is to access the Map.Entry class:

import java.util.{Map$Entry => Entry}

Note: Flix does not support accessing nested non-static inner classes.

Exceptions

In Flix, we can catch Java exceptions using the try-catch construct. The construct is similar to the one in Java, but the syntax is slightly different.

For example:

import java.io.BufferedReader
import java.io.File
import java.io.FileReader
import java.io.FileNotFoundException
import java.io.IOException

def main(): Unit \ IO = 
    let f = new File("foo.txt");
    try {
        let r = new BufferedReader(new FileReader(f));
        let l = r.readLine();
        println("The first line of the file is: ${l}");
        r.close()
    } catch {
        case _: FileNotFoundException => 
            println("The file does not exist!")
        case ex: IOException => 
            println("The file could not be read!");
            println("The error message was: ${ex.getMessage()}")
    }

Here the calls new FileReader(), r.readLine(), and r.close() can throw IOExceptions. We use a try-catch block to catch these exceptions. We add a special case for the FileNotFoundException exception.

Note: Flix programs should not use exceptions: it is considered bad style. Instead, programs should use the Result[e, t] type. The try-catch construct should only be used on the boundary between Flix and Java code.

Note: Flix does not (yet) support a finally block.

Note: In Flix a function can contain at most one try-catch block.

Boxing and Unboxing

Unlike Java, Flix never performs implicit boxing or unboxing of values.

We believe auto boxing is a design flaw and do not plan to support it. Hence, primitive values must be manually boxed and unboxed.

Boxing

The following example shows how to box a primitive integer:

def f(x: Int32): String \ IO = 
    let i = Box.box(x); // Integer
    i.toString()

Here the call to Box.box(x) returns an Integer object. Since i is an object, we can call toString on it. Boxing is a pure operation, but calling toString has the IO effect.

Unboxing

The following example shows how to unbox two Java Integer objects:

import java.lang.Integer

def sum(x: Integer, y: Integer): Int32 = 
    Box.unbox(x) + Box.unbox(y)

Here the call to Box.unbox returns an Int32 primitive value.

Unboxing is a pure operation.

Java Collections

Flix has support for conversion from and to Java collections.

In the following, we use the following import aliases:

import java.util.{List => JList}
import java.util.{Set => JSet}
import java.util.{Map => JMap}

The following functions are available in the Adaptor module:

Flix to Java

The following functions convert Flix collections to Java collections:

///
/// Lists
///
def toList(ma: m[a]): JList \ IO with Foldable[m]
def toArrayList(ma: m[a]): ArrayList \ IO with Foldable[m]
def toLinkedList(ma: m[a]): LinkedList \ IO with Foldable[m]

///
/// Sets
///
def toSet(ma: m[a]): Set \ IO with Order[a], Foldable[m]
def toTreeSet(ma: m[a]): TreeSet \ IO with Order[a], Foldable[m]

///
/// Maps
///
def toMap(m: Map[k, v]): JMap \ IO with Order[k]
def toTreeMap(m: Map[k, v]): 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 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: JList): List[a]

/// Sets
def fromSet(l: JSet): Set[a] with Order[a]

/// Maps
def fromMap(m: JMap): 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.

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 the ToString trait 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 trait. 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 trait:

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])

but it must be wrapped in parentheses to disambiguate it from other expressions.

It can also be placed on a let-binding parentheses:

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 traits:

trait MyTrait[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 bugs1. 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

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 suppress 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.

1 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 function:

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 trait. 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:

Visual Studio Code Extension

Flix comes with a fully-featured Visual Studio Code Extension:

Visual Studio Code1

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

  • 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 trait.
  • 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 traits. 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-fatjar: builds a jar-file with all dependencies bundled.
  • 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 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 fat JAR-file (bundling all dependencies)

We can compile a project to a single standalone fat JAR-file with the build-fatjar command. The build-fatjar command emits a artifact/project.jar file where all dependencies — both Flix and Maven — are bundled into one single JAR-file.

The JAR-file contains all class files from the build directory together with all class files extract from all Maven dependencies found in the lib directory.

Note: The project must be compiled with build before running build-fatjar.

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

Flix packages are published on GitHub.

Automatically Publishing a Package

Flix can automatically package and publish artifacts on GitHub by following these steps:

  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. Check that the repository field in flix.toml is correct. (e.g. repository = "github:user/repo")
  4. Check that you have a GitHub token which has read and write access to Contents for the relevant repository.
    • If not go to GitHub and navigate to Settings > Developer settings > Personal access tokens and create a new token.
  5. Run check and test to ensure that everything looks alright.
  6. Run release --github-token <TOKEN>. You should see:
Found `flix.toml'. Checking dependencies...
Resolving Flix dependencies...
Downloading Flix dependencies...
Resolving Maven dependencies...
  Running Maven dependency resolver.
Downloading external jar dependencies...
Dependency resolution completed.
Release github:user/repo v1.2.3? [y/N]: y
Building project...
Publishing new release...

 Successfully released v1.2.3
 https://github.com/user/repo/releases/tag/v1.2.3

Tip: See the Museum Project for an example of a package that has been published on GitHub.

Tip: Flix will read the GitHub token from the environment variable GITHUB_TOKEN, if available.

Tip: Flix will also read the GitHub token from the file .GITHUB_TOKEN, if available.

Note: You cannot publish artifacts for empty GitHub repositories.

Warning: Be sure to keep your token safe!

Manually Publishing a Package

A package can also be manually published by following these steps:

  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 correct.
  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.

Warning: You must upload both the package file (foo.fpkg) and the manifest file (flix.toml).

Finding Outdated Packages

We can use the outdated command to check if any Flix packages have updates available.

For example, if we have the following dependency in flix.toml:

[dependencies]
"github:flix/museum"            = "1.0.0"
"github:flix/museum-giftshop"   = "1.0.0"

then we can run outdated command which will produce:

Found `flix.toml`. Checking dependencies...
Resolving Flix dependencies...
  Cached `flix/museum.toml` (v1.0.0).
  Cached `flix/museum-giftshop.toml` (v1.0.0).  
  Cached `flix/museum-entrance.toml` (v1.0.0).  
  Cached `flix/museum-giftshop.toml` (v1.0.0).  
  Cached `flix/museum-restaurant.toml` (v1.0.0).
  Cached `flix/museum-clerk.toml` (v1.0.0).     
  Cached `flix/museum-clerk.toml` (v1.0.0).
Downloading Flix dependencies...
  Cached `flix/museum.fpkg` (v1.0.0).
  Cached `flix/museum-giftshop.fpkg` (v1.0.0).
  Cached `flix/museum-entrance.fpkg` (v1.0.0).
  Cached `flix/museum-giftshop.fpkg` (v1.0.0).
  Cached `flix/museum-restaurant.fpkg` (v1.0.0).
  Cached `flix/museum-clerk.fpkg` (v1.0.0).
  Cached `flix/museum-clerk.fpkg` (v1.0.0).
Resolving Maven dependencies...
  Running Maven dependency resolver.
Downloading external jar dependencies...
Dependency resolution completed.

package                 current    major    minor    patch
flix/museum             1.0.0               1.4.0         
flix/museum-giftshop    1.0.0               1.1.0         

The outdated command tells us that we are using two packages which have updates available:

  • flix/museum can be upgraded from 1.0.0 to 1.4.0.
  • flix/museum-giftshop can be upgraded from 1.0.0 to 1.1.0.

If we want to upgrade a package, we must manually modify flix.toml.

Advanced Features

In this chapter, we discuss some advanced features of Flix, including:

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.

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:

mod 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)

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'

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 trait 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 trait 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 trait 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)
}

Frequently Asked Questions

Does Flix supports constants?

Yes and no. Flix does not support top-level constants. You can, however, declare a pure function which takes zero arguments:

def pi(): Float64 = 3.14f64

The Flix compiler will inline such constants.

If you have an expensive computation that you want to perform once, you should compute it where needed and explicitly pass it around. Flix does not support top-level constants because they violate the principle that no code should be executed before main.

Glossary

Algebraic Data Type. A data type defined using sum and product types, i.e. using enumerated types and tuple types.

Algebraic Effect. A user-defined effect which can be handled. The handler is supplied with the (delimited) continuation of the effect. The continuation can be dropped, resume once, or resumed multiple-times.

Associated Type. A type that belongs to a trait. Each trait instance specifies the specific associated type for that instance. Hence different trait instances can have different associated types.

Associated Effect. An effect that belongs to a trait. Each trait instance specifies the specific associated effect for that instance. Hence different trait instances can have different associated effects.

Checked Cast. A safe cast that the compiler ensures is correct. Cannot fail at runtime.

Effect. Flix supports three types of effects: built-in effects (e.g. IO and NonDet), region-based effects, and user-defined effects.

Effect Cast. A cast that changes the effect of an expression.

Effect Member. See associated effect.

Effect Polymorphic. A function whose effect(s) depend on the effect(s) of its function argument. See also higher-order function.

Effect Handler. An expression which handles a user-defined effect.

Higher-Order Function. A function that takes a function argument or returns a function.

IO Effect. A built-in generic effect which represents any interaction with the outside world.

Pure. A function (or expression) which has no effects.

String Interpolation. A language feature that allows a string to contain expressions.

Tail Call. A function call in tail-position and hence does not require additional stack space.

Trait. An interface that specifies a collection of function signatures and default functions. A trait can be implemented by several data types. Traits in Flix are type classes.

Type Class. See Trait.

Type Cast. A cast that changes the type of an expression.

Type Inference. A language feature that allows the compiler to infer the type of an expression without requiring annotations from the programmer.

Type Match. A language feature that allows a function to inspect (reflect) on a type.

Type Member. See associated type.

Unchecked Cast. An unsafe cast which is not verified by the compiler. Can fail at runtime.

Uninterpretable Effect. An effect that cannot (or should not) be handled, e.g. IO.

Additional Information

More information about the Flix programming language can be found in:

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:

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:

Susan Potter is writing a blog post series on Flix:

Jesse Claven wrote a blog post on logic programming in Flix:

Magnus Madsen wrote a few blog posts on Flix during COVID:

Magnus Madsen did an interview about Flix on the Happy Path Programming podcast:

Videos

A collection of videos about Flix.

Industry Talks

Research Talks

Appendix

The appendix covers technical details such as:

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 (AZ, az, _, !).
    • e.g. String, ALL_UPPER, Shriek!
    • Can be used to name: namespaces, annotations, traits, 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 (AZ, az, _, !).
    • 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, |||, ~~~, $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, mod, null, opaque, pub, redef, ref, region, reify, reifyBool, reifyEff, reifyType, rel, sealed, set, spawn, Static, trait, true, type, use, where, with, discard, object, choose, solve, inject, project

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 (**, *, and /)
  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 <-