Introduction to Flix
Flix is a principled functional, logic, and imperative programming language developed at Aarhus University and by a community of open source contributors in collaboration with researchers from the University of Waterloo, from the University of Tubingen, and from the University of Copenhagen.
Flix is inspired by OCaml and Haskell with ideas from Rust and Scala. Flix looks like Scala, but its type system is based on Hindley-Milner which supports complete type inference. Flix aims to offer a unique combination of features that no other programming language offers, including:
- algebraic data types and pattern matching.
- type classes with higher-kinded types.
- structured concurrency based on channels and light-weight processes.
In addtion, Flix has several new powerful and unique features:
- A polymorphic type and effect system with region-based local mutation.
- Datalog constraints as first-class program values.
- Function overloading based on purity reflection.
Flix compiles to efficient JVM bytecode, runs on the Java Virtual Machine, and supports full tail call elimination. Flix has interoperability with Java and can use JVM classes and methods. Hence the entire Java ecosystem is available from within Flix.
Flix aims to have world-class Visual Studio Code support. The Flix Visual Studio Code extension uses the real Flix compiler hence there is always a 1:1 correspondence between the Flix language and what is reported in the editor. The advantages are many: (a) diagnostics are always exact, (b) code navigation "just works", and (c) refactorings are always correct.
Look'n Feel
Here are a few programs to illustrate the look and feel of Flix:
This program illustrates the use of algebraic data types and pattern matching:
/// An algebraic data type for shapes.
enum Shape {
case Circle(Int32), // circle radius
case Square(Int32), // side length
case Rectangle(Int32, Int32) // height and width
}
/// Computes the area of the given shape using
/// pattern matching and basic arithmetic.
def area(s: Shape): Int32 = match s {
case Shape.Circle(r) => 3 * (r * r)
case Shape.Square(w) => w * w
case Shape.Rectangle(h, w) => h * w
}
// Computes the area of a 2 by 4.
def main(): Unit \ IO =
area(Shape.Rectangle(2, 4)) |> println
Here is an example that uses polymorphic records:
/// Returns the area of the polymorphic record `r`.
/// Note that the use of the type variable `a` permits the record `r`
/// to have labels other than `x` and `y`.
def polyArea[a : RecordRow](r: {x = Int32, y = Int32 | a}): Int32 = r.x * r.y
/// Computes the area of various rectangle records.
/// Note that some records have additional labels.
def polyAreas(): List[Int32] =
polyArea({x = 1, y = 2}) ::
polyArea({x = 2, y = 3, z = 4}) :: Nil
def main(): Unit \ IO =
polyAreas() |> println
Here is an example that uses region-based local mutation:
///
/// We can define pure functions that use
/// internal mutability (impurity) with regions.
/// Regions encapsulate mutability to its declared scope.
///
def deduplicate(l: List[a]): List[a] with Order[a] =
/// Declare a new region `rc`.
region rc {
/// Create a new `MutSet` at region `r`.
/// This will be used to keep track of
/// unique elements in `l`.
let s = MutSet.new(rc);
/// The lambda used in the call to `filter`
/// would be impure without a region.
List.filter(x -> {
if (MutSet.memberOf(x, s))
false // `x` has already been seen.
else {
MutSet.add!(x, s);
true
}
}, l)
}
Here is an example that uses first-class Datalog constraints:
def reachable(edges: List[(Int32, Int32)], src: Int32, dst: Int32): Bool =
let db = inject edges into Edge;
let pr = #{
Path(x, y) :- Edge(x, y).
Path(x, z) :- Path(x, y), Edge(y, z).
Reachable() :- Path(src, dst).
};
let result = query db, pr select () from Reachable();
not Vector.isEmpty(result)
And finally here is an example that uses structured concurrency with channels and processes:
/// A function that sends every element of a list
def sendAll(l: List[Int32], tx: Sender[Int32, r]): Unit \ IO =
match l {
case Nil => ()
case x :: xs => Channel.send(x, tx); sendAll(xs, tx)
}
/// A function that receives n elements
/// and collects them into a list.
def recvN(n: Int32, rx: Receiver[Int32, r]): List[Int32] \ IO =
match n {
case 0 => Nil
case _ => Channel.recv(rx) :: recvN(n - 1, rx)
}
/// A function that calls receive and sends the result on d.
def wait(rx: Receiver[Int32, r], n: Int32, tx: Sender[List[Int32], r]): Unit \ IO =
Channel.send(recvN(n, rx), tx);
()
/// Spawn a process for send and wait, and print the result.
def main(): Unit \ IO = region rc {
let l = 1 :: 2 :: 3 :: Nil;
let (tx1, rx1) = Channel.buffered(rc, 100);
let (tx2, rx2) = Channel.buffered(rc, 100);
spawn sendAll(l, tx1) @ rc;
spawn wait(rx1, List.length(l), tx2) @ rc;
println(Channel.recv(rx2))
}
Additional examples can be found in these pages and in the examples folder on GitHub.
Getting Started
Getting started with Flix is straightforward. All you need is Java version 11+.
You can check if Java is installed and its version by typing:
$ java -version
which should print something like:
openjdk version "18.0.2.1" 2022-08-18
OpenJDK Runtime Environment Temurin-18.0.2.1+1 (build 18.0.2.1+1)
OpenJDK 64-Bit Server VM Temurin-18.0.2.1+1 (build 18.0.2.1+1, mixed mode, sharing)
If Java is not installed or your version is too old, a newer version can be downloaded from Adoptium.
Once you have Java 11+ installed there are two ways to proceed:
- You can use the Flix VSCode extension (highly recommended) or
- You can run the Flix compiler from the command line.
Using Flix from Visual Studio Code (VSCode)
Flix comes with a fully-featured VSCode plugin. Follow these steps to get started:
- Create a new empty folder (e.g.
my-flix-project
).- Open VSCode and choose
File -> Open Folder
.- Create a new file called
Main.flix
in the folder.- VSCode will ask you want to search the marketplace for extensions. Say "Yes".
- The Flix extension will be downloaded and installed. Once done, it will ask if you want to download the Flix compiler. Say "Yes" again.
- When you see "Starting Flix" followed by "Flix Ready!" everything should be ready.
A screenshot of the Flix Visual Studio Code extension in action:
Using Flix from the Command Line
Flix can also be used from the command line. Follow these steps:
- Create a new empty folder (e.g.
my-flix-project
).- Download the latest
flix.jar
from https://github.com/flix/flix/releases/latest and put it into the folder.- Enter the created directory (e.g.
cd my-flix-project
) and runjava -jar flix.jar init
to create an empty Flix project.- Run
java -jar flix.jar run
to compile and run the project.
Troubleshooting
The most common reasons for Flix not working are (a) the java
command not
being on your PATH
, (b) the JAVA_HOME
environmental variable not being set
or being set incorrectly, or (c) having the wrong version of Java installed. To
debug these issues, ensure that:
- The command
java -version
prints the right Java version. - The
JAVA_HOME
environmental variable is correctly set.- On Windows, you can print the variable by typing
echo %JAVA_HOME%
. - On Mac and Linux, you can print the variable by typing
echo $JAVA_HOME
.
- On Windows, you can print the variable by typing
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 theEnvironment.getArgs
functions. - The return type of the
main
function isUnit
. - The
main
function has theIO
effect since it prints to the terminal.
Next Steps
We are now ready write our first real program!
We will write a simple variant of the venerable wordcount (wc
) program from
UNIX. We shall not be concerned with efficiency, but we will carefully check all
error cases.
Create a new folder (e.g. wc
), set up an empty Flix project and put the following code into src/Main.flix
:
def main(): Unit \ IO =
let args = Environment.getArgs();
match args {
case Nil => println("Missing argument: filename")
case file :: _ =>
match File.readLines(file) {
case Err(_) =>
println("Unable to read: ${file}")
case Ok(lines) =>
let totalLines = List.length(lines);
let totalWords = List.sumWith(numberOfWords, lines);
println("Lines: ${totalLines}, Words: ${totalWords}")
}
}
def numberOfWords(s: String): Int32 =
s |> String.words |> List.length
The program works as follows:
- 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 onargs
to extract the file name and report an error if the list is empty. - We use
File.readLines
to read all lines of the file. This operation may fail (e.g. if the file does not exist) and hence it returns aResult
. We use pattern matching on the result and print an error message if we could not read the file. - Otherwise we have a
List[String]
from which we can easily compute the number of lines and using the helper functionnumberOfWords
, we can also easily compute the total number of words. Finally, we print these two numbers.
We can compile and run the program as follows:
$ java -jar flix.jar build
$ java -jar flix.jar build-jar
$ java -jar artifact/wc.jar src/Main.flix
Lines: 17, Words: 62
The above program gets the job done, but it is a bit verbose. A more readable version is:
def main(): Unit \ IO =
let args = Environment.getArgs();
let result =
for (
file <- List.head(args) |>
Option.toOk("Missing argument: filename");
lines <- File.readLines(file) |>
Result.mapErr(_ -> "Unable to read: ${file}")
) yield {
let totalLines = List.length(lines);
let totalWords = List.sumWith(numberOfWords, lines);
(totalLines, totalWords)
};
match result {
case Ok((lines, words)) => println("Lines: ${lines}, Words: ${words}")
case Err(message) => println(message)
}
def numberOfWords(s: String): Int32 =
s |> String.words |> List.length
which takes advantages of the monadic for-yield construct.
Data Types
Flix comes with a collection of built-in data types,
such as booleans, floats and integers, and
compound types, such as tuples and records.
Moreover, the standard library defines types such as
Option[a]
, Result[e, t]
, List[a]
, Set[a]
,
and Map[k, v]
.
In addition to these types, Flix allows programmers to define their own types, including enumerated types, recursive types, and polymorphic types.
Flix also supports type aliases (new types).
Primitive Types
Flix supports the primitive types:
Type | Syntax | Description |
---|---|---|
Unit | () | The unit value. |
Bool | true , false | A boolean value. |
Char | 'a' , 'b' , 'c' | A character value. |
Float32 | 0.0f32 , 21.42f32 , -21.42f32 | A 32-bit floating point integer. |
Float64 | 0.0f64 , 21.42f64 , -21.42f64 | A 64-bit floating point integer. |
Int8 | 0i8 , 1i8 , -1i8 , 127i8 , -128i8 | A signed 8-bit integer. |
Int16 | 0i16 , 123i16 , -123i16 | A signed 16-bit integer. |
Int32 | 0i32 , 123i32 , -123i32 | A signed 32-bit integer. |
Int64 | 0i64 , 123i64 , -123i64 | A signed 64-bit integer. |
String | "hello" , "world" | A string value. |
BigInt | 0ii , 123ii , -123ii | An arbitrary precision integer. |
BigDecimal | 0.0ff , 123.45ff , -123.45ff | An 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 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
andOrder
type classes require that their operations are pure. This ensures that collections, such as lists, sets, and maps, do not leak internal implementation details.
Immutable Data
The bread-and-butter of functional programming is immutable data types.
We have already seen several examples of immutable data types:
In addition, The Flix standard library offers several immutable data types:
List[t]
: An immutable singly-linked list of elements of typet
.Chain[t]
: An immutable chain of elements of typet
with fast append.Vector[t]
: An immutable sequence of elements of typet
with fast lookup.Set[t]
: An immutable set of elements of typet
.Map[k, v]
: An immutable map of keys of typek
to values of typev
.
Other immutable data types include:
Option[t]
: A type that is eitherNone
orSome(t)
.Result[e, t]
: A type that is eitherOk(t)
orErr(e)
.Nel[t]
: An immutable non-empty singly-linked list of elements of typet
.Nec[t]
: An immutable non-empty sequence of elements of typet
that supports fast append.MultiMap[k, v]
: An immutable map of keys of typek
to sets of values of typev
.
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 List
s, Flix also supports immutable Chain
s and
Vector
s.
The following table illustrates the performance trade-offs between lists, chains, and vectors:
Operation \ Type | List | Chain | Vector |
---|---|---|---|
Find First Element | O(1) | O(n) | O(1) |
Find Last Element | O(n) | O(n) | O(1) |
Find Element at Index | O(n) | O(n) | O(1) |
Cons | O(1) | O(n) | O(n) |
Append | O(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) Set
s and Map
based on balanced
trees; hence the elements of a Set
and the keys of Map
must implement the
Order
type class.
Tip: The Flix
Set
andMap
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 Set
s are SemiGroup
s, we can also use the ++
operator and write s1 ++ s2
.
Maps
The empty map is written as:
Map#{}
which is equivalent to Map.empty()
. A map literal is written as:
Map#{"a" => 1, "b" => 2, "c" => 3}
We can insert into a map using Map.insert
(which returns a new map):
let m1 = Map#{"a" => 1, "b" => 2, "c" => 3};
let m2 = Map.insert("d", 4, m1);
We can lookup the value associated with a key using Map.get
:
let m = Map#{"a" => 1, "b" => 2, "c" => 3};
Map.get("b", m)
The Map.get
function returns an Option[v]
.
We can merge two maps using one of Map.unionWith
and Map.unionWithKey
functions.
Records
Flix supports row polymorphic extensible records.
Flix records are immutable (but may contain mutable reference cells).
Record Literals
A record literal is written with curly braces:
{ x = 1, y = 2 }
which has the record type
{ x = Int32, y = Int32 }
.
The order of labels in a record does not matter. Hence the above record is equivalent to:
{ y = 2, x = 1 }
which has type { y = Int32, x = Int32 }
. This type is equivalent to { x = Int32, y = Int32 }
. In other words, the order of labels within a record type
does not matter.
Label Access
We can access the label of a record using a dot:
let p = { x = 1, y = 2 };
p.x + p.y
The type system ensures that we cannot access a label that does not exist.
Records are immutable. Once constructed, the values of the record labels cannot be changed.
Label Update
While records are immutable, we can construct a new record with an updated label value:
let p1 = { x = 1, y = 2 };
let p2 = { x = 3 | p1 };
p1.x + p2.x
The expression { x = 3 | p1 }
updates the record p1
with a new value of its
x
label. Note that updating a label requires that the label exists on the
record. A record cannot be updated with a new label, but it can be extended
with a new label, as we shall see later.
Record Extension
We can add a new label to an existing record as follows:
let p1 = { x = 1, y = 2 };
let p2 = { +z = 3 | p1 };
p1.x + p1.y + p2.z
Here the expression { +z = 3 | p1 }
extends the record p1
with a new label
z
such that the result has three labels: x
, y
, and z
all of which are of
Int32
type.
Record Restriction
Similarly to record extension, we can also remove a label from a record:
let p1 = { x = 1, y = 2 };
let p2 = { -y | p1 };
Here the record p2
has the same labels as p1
except that the y
label has
been removed.
Row Polymorphism: Open and Closed Records
A function may specify that it requires a record with two labels:
def f(r: {x = Int32, y = Int32}): Int32 = r.x + r.y
We can call this function with the records { x = 1, y = 2 }
and { y = 2, x = 1 }
, but we cannot call it with the record { x = 1, y = 2, z = 3 }
since
the signature of f
demands a record with exactly two labels: x
and y
. We
say that the record r
is closed.
We can lift this restriction by using row polymorphism:
def g(r: {x = Int32, y = Int32 | s}): Int32 = r.x + r.y
We can call this function with any record as long as it has x
and y
labels
which are of type Int32
. We say that the record type of r
is open.
Named Parameters with Records
When a function has multiple parameters that share the same type, it is easy to
get confused about the right argument order. For example, what does
String.contains("Hello","Hello World")
return? What does
String.contains("Hello World", "Hello")
return?
A common solution to this problem is to use named parameters. Flix supports a form of named parameters building on records. For example, we can write a function translate to translate from one language to another as follows:
def translate(from: {from = Language}, to: {to = Language}, text: String): String = ???
We can call this function as follows:
translate({from = English}, {to = French}, "Where is the library?")
Since such verbosity gets tedious, we can also use the syntactic sugar:
translate(from = English, to = French, "Where is the library?")
which is equivalent to the above.
Mutable Data
Flix is a functional-first programming language that encourages but does not demand, the use of immutable data structures. While immutable data structures should be the default, Flix has rich support for imperative programming with destructive updates to mutable data.
Flix uses its effect system to separate pure and impure code. In particular, Flix uses the region concept to track the use of mutable memory. That is, all mutable memory belongs to some statically-scoped region.
Flix has two basic types of mutable memory:
We can use references and arrays to build higher-level mutable data structures.
For example, the Flix Standard Library offers collections such as MutList
,
MutDeque
, MutSet
, and MutMap
. As a rule, these higher-level data
structures should be preferred over lower-level references and arrays.
We begin this chapter with a discussion of regions.
Regions
Flix supports scoped mutable memory. In Flix, all mutable memory belongs to a region that is tied to its lexical scope. When execution leaves the lexical scope of a region, all memory in that region becomes unreachable.
Regions are useful because they enable us to implement pure functions that internally use mutation. We will illustrate this powerful idea with several real-world examples, but let us first discuss how to use a region:
We introduce a new region scope with the region
construct:
region rc { // region starts.
... // the region handle `rc` is in scope.
} // region ends and all data associated with `rc` is no longer in scope.
We can use regions to implement a pure sort
function that internally uses mutation:
def sort(l: List[a]): List[a] with Order[a] =
region rc {
let arr = List.toArray(rc, l);
Array.sort!(arr);
Array.toList(arr)
}
Here we introduce a region named rc
. We use the function List.toArray
to
convert the list l
to a mutable array arr
associated with the region rc
.
We then sort arr
using Array.sort!
which uses an efficient in-place sorting
algorithm. Finally, we convert the sorted array back to a list and return it.
The sort
function is pure, even though it internally uses mutation.
As another example, we can implement a toString
function for List[a]
which
is pure but internally uses a mutable StringBuilder
:
def toString(l: List[a]): String with ToString[a] =
region rc {
let sb = StringBuilder.new(rc);
List.forEach(x -> StringBuilder.appendString!("${x} :: ", sb), l);
StringBuilder.appendString!("Nil", sb);
StringBuilder.toString(sb)
} // scope of rc ends, the entire expression is pure.
The programming pattern is the same: We open a new region, allocate a
StringBuilder
in the region, fill the builder with strings, and convert it
into one string.
We can use regions to implement certain functional operations more
efficiently. For example, here is a fast implementation of List.flatMap
:
def flatMap(f: a -> List[b] \ ef, l: List[a]): List[b] \ ef =
region rc {
let ml = MutList.new(rc);
l |> List.forEach(x -> MutList.append!(f(x), ml));
MutList.toList(ml)
}
Regions are Values
A region (or region handle) is a value that can be passed as a function argument. This is useful, for example, when we want to write a reusable function that allocates and returns a mutable data structure.
For example, here is the List.toMutDeque
function:
def toMutDeque(rc: Region[r], l: List[a]): MutDeque[a, rc] \ rc =
let d = MutDeque.new(rc);
forEach(x -> MutDeque.pushBack(x, d), l);
d
The function takes a region handle rc
, allocates a new mutable deque
(MutDeq
) in the given region, inserts all elements of the list l
in the
deque, and returns it.
Regions are Scoped
Regions and all memory associated with them cannot outlive their lexical scope.
Consider the following program:
def main(): Unit \ IO =
let escaped = region rc {
Array#{1, 2, 3} @ rc
};
println(escaped)
Here we allocate the Array#{1, 2, 3}
in the region rc
and try to return it
outside of its enclosing scope. The Flix compiler detects such escape violations
and reports an error:
❌ -- Type Error ----------------------------
>> The region variable 'rc' escapes its scope.
2 |> let escaped = region rc {
3 |> Array#{1, 2, 3} @ rc
4 |> };
region variable escapes.
References
Flix supports mutable scoped references. A reference is a box whose value can change over time. The three key reference operations are:
- Creating a new reference
ref e @ rc
. - Dereferencing a reference
deref e
. - Assigning to a reference
e := e
.
In Flix, the type of a reference is Ref[t, r]
where t
is the type of the
element and r
is its region. Like all mutable memory in Flix, every reference
must belong to some region. Reading from and writing to a reference are
effectful operations. For example, reading the value of a reference Ref[t, r]
has effect r
.
The ref e @ rc
operation allocates a reference cell in a region of the heap
and returns its location, the deref
operation dereferences a location and
returns the content of a reference cell, and the assigment :=
operation
changes the value of a reference cell. Informally, a reference cell can be
thought of as an "object" with a single field that can be changed.
Allocating References
A reference cell is allocated with the ref e @ rc
syntax. For example:
region rc {
let c = ref 42 @ rc;
println(deref c)
}
Here we introduce a region named rc
. Inside the region, we create a reference
cell called c
with the value 42
which we then dereference and print.
Dereferencing References
A reference cell is accessed (dereferenced) with the deref e
syntax. For example:
region rc {
let c = ref 42 @ rc;
let x = deref c;
let y = deref c;
println(x + y)
}
Here the program prints 42 + 42 = 84
.
Assignment
We can update the value of a reference cell. For example:
region rc {
let c = ref 0 @ rc;
c := (deref c) + 1;
c := (deref c) + 1;
c := (deref c) + 1;
println(deref c)
}
Here the program creates a reference cell c
with the value 0
. We dereference
the cell and increment its value three times. Hence the program prints 3
.
Example: A Simple Counter
We can use references to implement a simple counter:
enum Counter[r: Region] { // The Region here is a type-kind
case Counter(Ref[Int32, r])
}
def newCounter(rc: Region[r]): Counter[r] \ r = Counter.Counter(ref 0 @ rc)
def getCount(c: Counter[r]): Int32 \ r =
let Counter.Counter(l) = c;
deref l
def increment(c: Counter[r]): Unit \ r =
let Counter.Counter(l) = c;
l := (deref l) + 1
def main(): Unit \ IO =
region rc {
let c = newCounter(rc);
increment(c);
increment(c);
increment(c);
getCount(c) |> println
}
Here the Counter
data type has a region type parameter. This is required since
the counter internally uses a reference that requires a region. Hence Counter
s
are also scoped. Note that the newCounter
function requires a region handle to
create a new Counter
. Moreover, note that the functions getCount
and
increment
both have the r
effect.
Aliasing and References to References
References naturally support aliasing since that is their purpose. For example:
region rc {
let l1 = ref 42 @ rc;
let l2 = l1;
l2 := 84;
println(deref l1)
}
Prints 84
because the reference cell that l1
points to is modified through
the alias l2
.
References can also point to references as the following example illustrates:
region rc {
let l1 = ref 42 @ rc;
let l2 = ref l1 @ rc;
let rs = deref (deref l2);
println(rs)
}
Here the type of l2
is Ref[Ref[Int32, rc], rc]
.
Mutable Tuples and Records
Flix tuples and records are immutable. However, tuples and records may contain mutable references.
For example, here is a pair that contains two mutable references:
region rc {
let p = (ref 1 @ rc, ref 2 @ rc);
fst(p) := 123
};
The type of the pair is (Ref[Int32, rc], Ref[Int32, rc])
. The assignment does
not change the pair but instead changes the value of the reference cell in the
first component.
Similarly, here is a record that contains two mutable references:
region rc {
let r = { fstName = ref "Lucky" @ rc, lstName = ref "Luke" @ rc };
r.fstName := "Unlucky"
};
The type of the record is { fstName = Ref[String, rc], lstName = Ref[String, rc] }
. Again, the assignment does not change the record, but instead changes
the value of the reference cell corresponding to the fstName
label.
Arrays
Flix supports mutable scoped arrays. An array is a fixed-length mutable sequence of elements that share the same type. Arrays are laid out consecutively in memory. Arrays are mutable; hence their elements can change over time. However, once created, the length of an array cannot be changed.
In Flix, the type of an array is Array[t, r]
where t
is the type of its
elements and r
is its region. Like all mutable memory in Flix, every array
must belong to some region. Reading from and writing to arrays are effectful
operations. For example, reading an element from an array of type Array[t, r]
has the effect r
. Likewise, creating an array in a region is also an effectful
operation.
Arrays are always unboxed. For example, an array of type Array[Int32, r]
is
represented as a sequence of primitive 32-bit integers, i.e., in JVM
terminology, the array is represented as int[]
. Flix will never box primitive
integers as java.lang.Integer
objects but still permits primitives in generic
collections and functions. The same is true for other types of primitives and
arrays of primitives.
Arrays are low-level data structures typically used to implement higher-level
data structures. Therefore, unless implementing such data structures, we
recommend that arrays are used sparingly. Instead, we recommend using the
MutList
, MutDeque
, MutSet
, and MutMap
data structures.
Hint: Use
MutList
if you need a growable mutable sequence of elements.
Array Literals
The syntax of an array literal is of the form Array#{e1, e2, e3, ...} @ r
where e1
, e2
, and so forth are element expressions, and r
is the region
expression. For example:
region rc {
let fruits = Array#{"Apple", "Pear", "Mango"} @ rc;
println(Array.toString(fruits))
}
Here we introduce a region named rc
. Inside the region, we create an array of
fruits
that contain the three strings "Apple"
, "Pear"
, and "Mango"
. The
type of fruits
is Array[String, rc]
. For more information about regions, we
refer to the chapter on Regions.
Running the program prints Array#{"Apple", "Pear", "Mango"}
.
Allocating Arrays
We can allocate an array of size n
filled with the same element using the
Array.repeat
function. For example:
region rc {
let arr = Array.repeat(rc, 1_000, 42);
println(Array.toString(arr))
}
Here we create an array arr
of length 1_000
where each array element has the
value 42
. Note that we must pass the region rc
as an argument to
Array.repeat
because the function must know to which region the returned array
should belong.
We can also create an array filled with all integers from zero to ninety-nine:
region rc {
let arr = Array.range(rc, 0, 100);
println(Array.toString(arr))
}
Moreover, we can convert most data structures to arrays. For example:
region rc {
let fruitList = List#{"Apple", "Pear", "Mango"};
let fruitArray = List.toArray(rc, fruitList);
}
Note that we must pass the region rc
as an argument to List.toArray
since
the function must know to which region the returned array should belong.
Allocating Arrays with Uninitialized Elements
We can use the Array.new
function to create an array of a given length where
the content of the array is uninitialized. For example:
region rc {
let arr: Array[String, rc] = Array.new(rc, 100);
// ... initialize `arr` here ...
}
Here we create an array of length 100
of type Array[String, rc]
. We use an
explicit type annotation : Array[String, rc]
to inform Flix of the expected
type of the array.
Warning: It is dangerous to use arrays that have uninitialized elements.
What are the elements of an uninitialized array? Flix follows Java (and the JVM)
which defines a default value for every primitive-- and reference type. So,
for example, the default values for Bool
and Int32
are false
and 0
,
respectively. The default value for reference types are null
. So be careful!
Flix does not have a null
value, but one can be indirectly introduced by
reading from improperly initialized arrays which can lead to
NullPointerException
s.
Reading from and Writing to Arrays
We can retrieve or update the element at a specific position in an array using
Array.get
and Array.put
, respectively. For example:
region rc {
let strings = Array.new(rc, 2);
Array.put("Hello", 0, strings);
Array.put("World", 1, strings);
let s1 = Array.get(0, strings);
let s2 = Array.get(1, strings);
println("${s1} ${s2}")
}
Here we create an empty array of length of two. We then store the string
"Hello"
at position zero and the string "World"
at position one. Next, we
retrieve the two strings, and print them. Thus the program, when compiled and
run, prints Hello World
.
We can also write part of the program in a more fluent-style using the !>
pipeline operator:
let strings =
Array.new(rc, 2) !>
Array.put("Hello", 0) !>
Array.put("World", 1);
Slicing Arrays
We can slice arrays using Array.slice
. A slice of an array is a new (shallow)
copy of a sub-range of the original array. For example
region rc {
let fruits = Array#{"Apple", "Pear", "Mango"} @ rc;
let result = Array.slice(rc, start = 1, end = 2, fruits);
println(Array.toString(result))
}
which prints Array#{"Pear"}
when run.
Taking the Length of an Array
We can compute the length of an array using the Array.length
function. For
example
region rc {
let fruits = Array#{"Apple", "Pear", "Mango"} @ rc;
println(Array.length(fruits))
}
which prints 3
when run.
Note: We advise against indexed-based iteration through arrays. Instead, we recommend to use functions such as
Array.count
,Array.forEach
, andArray.transform!
.
Additional Array Operations
The Array
module offers an extensive collection of functions for working with
arrays. For example, Array.append
, Array.copyOfRange
, Array.findLeft
,
Array.findRight
, Array.sortWith!
, and Array.sortBy!
to name a few. In
total, the module offers more than 100 functions ready for use.
Mutable Collections
The Flix standard library supports many immutable collections, including options, lists, chains, sets, and maps. We strongly encourage their use.
In addition, the Flix standard library also offers several mutable collections:
MutList[t, r]
: a contiguous growable/shrinkable array of elements of typet
.MutSet[t, r]
: a mutable set of elements of typet
.MutMap[k, v, r]
: a mutable map of keys of typek
to values of typev
.MutDeque[t, r]
: a mutable double-ended queue of elements of typet
.
Recall that in Flix all mutable memory, including mutable collections, belongs to a region.
Here is an example of how to use MutList[t]
:
def main(): Unit \ IO =
region rc {
let fruits = MutList.new(rc);
MutList.push!("Apple", fruits);
MutList.push!("Pear", fruits);
MutList.push!("Mango", fruits);
MutList.forEach(println, fruits)
}
which prints Apple
, Pear
, and Mango
. Here the MutList[String, rc]
automatically expands (and shrinks) as elements are pushed (or popped) from it.
We can write the above program in a more fluent-style using the !>
pipeline
operator:
def main(): Unit \ IO =
region rc {
let fruits =
MutList.new(rc) !>
MutList.push!("Apple") !>
MutList.push!("Pear") !>
MutList.push!("Mango");
MutList.forEach(println, fruits)
}
We can split the above program into several functions as follows:
def main(): Unit \ IO =
region rc {
let fruits = sweetFruits(rc);
printFruits(fruits)
}
def sweetFruits(rc: Region[r]): MutList[String, r] \ r =
MutList.new(rc) !>
MutList.push!("Apple") !>
MutList.push!("Pear") !>
MutList.push!("Mango")
def printFruits(fruits: MutList[String, r]): Unit \ {r, IO} =
MutList.forEach(println, fruits)
Here the main
function introduces a new region rc
. We pass this region to
sweetFruits
which creates and returns a new mutable list of fruits. Note that
sweetFruits
has the effect r
since it allocates mutable memory using rc
.
The printFruits
takes a mutable list of fruits and prints them. Note that this
function has effect r
since it reads from mutable memory in r
and it has
effect IO
since it prints to the terminal.
Control Structures
Flix — being a functional programming language — has few control-structures. Most control is simply function application. The Flix control structures are:
- If-Then-Else: A traditional if-then-else expression.
- Pattern Matching: A functional construct for taking apart algebraic data types.
- Foreach: An imperative construct for iteration through collections.
- Foreach-Yield: An imperative construct for building new collections from existing collections.
- Monadic For-Yield: A functional construct for
monadic operations, similar to Scala's
for
-comprehensions and Haskell'sdo
-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:
Action | Construct |
---|---|
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 Option s and Result s. | Monadic For-Yield |
flatMap through a Monad . | Monadic For-Yield |
Work with Validation s | Applicative For-Yield |
Note: Flix does not have traditional
while
orfor
-loops. Instead, we recommend the use recursion and/or one of the above constructs.
If-then-else
Flix supports the usual if-then-else expression:
if (1 == 1) "Hello" else "World"
which evaluates to Hello
.
But if
guards are also supported in other parts of the language.
Guarded Pattern Matches
We can use an if
-guard in a pattern match:
def isSquare(s: Shape): Bool = match s {
case Rectangle(h, w) if h == w => true
case _ => false
}
Guarded Datalog Rules
We can use an if
-guard in a Datalog rule:
Path(x, z) :- Path(x, y), Edge(y, z), if x != z.
Pattern Matching
Matching on Enums
Flix supports pattern matching on algebraic data types.
For example, if we have an algebraic data type that models shapes:
enum Shape {
case Circle(Int32)
case Square(Int32)
case Rectangle(Int32, Int32)
}
Then we can write a function to compute the area of a Shape
using pattern
matching:
def area(s: Shape): Int32 = match s {
case Shape.Circle(r) => 3 * (r * r)
case Shape.Square(w) => w * w
case Shape.Rectangle(h, w) => h * w
}
Let Pattern Match
In addition to the pattern match
construct, a let-binding can be used to
destruct a value. For example:
let (x, y, z) = (1, 2, 3)
Binds the variables x
, y
, and z
to the values 1
, 2
, and 3
,
respectively.
Any exhaustive pattern may be used in a let-binding. For example:
let (x, Foo(y, z)) = (1, Foo(2, 3))
is legal provided that the Foo
constructor belongs to a type where it is the
only constructor.
The following let-bindings are illegal because they are not exhaustive:
let (1, 2, z) = ...
let Some(x) = ...
The Flix compiler will reject such non-exhaustive patterns.
Match Lambdas
Pattern matches can also be used with lambda expressions. For example:
List.map(match (x, y) -> x + y, (1, 1) :: (2, 2) :: Nil)
is equivalent to:
List.map(w -> match w { case (x, y) => x + y }, (1, 1) :: (2, 2) :: Nil)
As for let-bindings, such pattern matches must be exhaustive.
Note the difference between the two lambda expressions:
let f = (x, y, z) -> x + y + z + 42i32
let g = match (x, y, z) -> x + y + z + 42i32
Here f
is a function that expects three Int32
arguments, whereas g
is a
function that expects one three tuple (Int32, Int32, Int32)
argument.
Foreach
Flix supports a traditional foreach construct that enables imperative iteration through collections.
We typically use the foreach construct when we want to iterate through one or more collections and execute an effectful operation for each of their elements.
For example, the program:
def main(): Unit \ IO =
let fruits = List#{"Apple", "Pear", "Mango"};
foreach(fruit <- fruits)
println(fruit)
Prints the strings Apple
, Pear
, and Mango
.
We can also iterate through multiple collections:
def main(): Unit \ IO =
let fruits = List#{"Apple", "Pear", "Mango"};
let creams = List#{"Vanilla", "Stracciatella"};
foreach(fruit <- fruits)
foreach(cream <- creams)
println("Would you like some ${fruit} with ${cream} icecream?")
The same loop can also be written:
def main(): Unit \ IO =
let fruits = List#{"Apple", "Pear", "Mango"};
let creams = List#{"Vanilla", "Stracciatella"};
foreach(fruit <- fruits; cream <- creams)
println("Would you like some ${fruit} with ${cream} icecream?")
We can also write loops with a filter. For example:
def main(): Unit \ IO =
let fruits = List#{"Apple", "Pear", "Mango"};
let creams = List#{"Vanilla", "Stracciatella"};
foreach(fruit <- fruits; if isExcotic(fruit); cream <- creams)
println("Would you like some ${fruit} with ${cream} icecream?")
def isExcotic(fruit: String): Bool = match fruit {
case "Mango" => true
case _ => false
}
Adding Optional Braces for Visual Clarity
We can sometimes improve the visual clarity of a foreach
expression by adding
braces:
foreach(fruit <- fruits) {
foreach(cream <- creams) {
println("Would you like some ${fruit} with ${cream} icecream?")
}
}
The braces have no impact on the meaning of the foreach
loop; they are purely
stylistic.
The Iterable Type Class
We can use the foreach
syntax to iterate through any collection type that
implements the Iterable
type class. In particular, the Iterable
class
defines a single signature:
///
/// A type class for immutable data structures that can be iterated.
///
pub class Iterable[t: Type -> Type] {
///
/// Returns an iterator over `t`.
///
pub def iterator(rc: Region[r], t: t[a]): Iterator[a, r, r] \ r
}
Note: Flix expects the expression body of a
foreach
to have typeUnit
. If you want to return a value from the loop body, you should use theforeach-yield
construct.
Foreach-Yield
Flix supports a special foreach-yield
construct which is used to build
collections from other collections. The foreach-yield
construct is related to
the foreach
construct, but should not be confused with it. The foreach
construct is for effectful iteration through collections whereas the
foreach-yield
construct is for building new collections.
We can use the foreach-yield
construct to build a new collection from existing
collections. For example:
def main(): Unit \ IO =
let fruits = List#{"Apple", "Pear", "Mango"};
let creams = List#{"Vanilla", "Stracciatella"};
let result: Set[(String, String)] =
foreach(fruit <- fruits; cream <- creams)
yield (fruit, cream);
println(result)
Here we construct a Set[(String, String)]
from two List[String]
. The type of
the resulting collection is typically inferred, but in this case we have placed
an explicit type annotation on the result
local variable to specify it.
We can use the foreach-yield
construct with several different types of
collections. For example:
def main(): Unit \ IO =
let c1 = Some(1);
let c2 = Set#{1, 2, 3};
let c3 = List#{1, 2, 3};
let result: Set[Int32] =
foreach(x <- c1; y <- c2; z <- c3)
yield x + y + z;
println(result)
Here we iterate through three collections c1
, c2
, and c3
and return a set
of the sums of their pairwise combinations.
The Collectable Type Class
The workhorse behind the foreach-yield
construct is the Iterable
type class
(discussed in the previous section) and the Collectable
type class.
pub class Collectable[m: Type -> Type] {
///
/// Run an Iterator collecting the results.
///
pub def collect(iter: Iterator[a, r]): m[a] \ r with Order[a]
}
Without going into details, the Collectable
type class is implemented by all
kinds of collections that can be constructed from an iterator. Notably, this
includes the List
, Chain
, and Set
data types.
Note: We cannot collect into a non-empty chain (
Nec
) or non-empty list (Nel
) since we cannot guarantee that anIterator
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 regularforeach
-loop.
Monadic For-Yield
Flix supports a monadic forM-yield construct similar to Scala's
for-comprehensions and Haskell's do notation. The forM construct is syntactic
sugar for uses of point
and flatMap
(which are provided by the Monad
type
class). The forM construct also supports a guard-expression that uses
empty
(which is provided by the MonadZero
type class).
For example, the monadic forM
expression:
let l1 = 1 :: 2 :: Nil;
let l2 = 1 :: 2 :: Nil;
forM (x <- l1; y <- l2)
yield (x, y)
evaluates to the list:
(1, 1) :: (1, 2) :: (2, 1) :: (2, 2) :: Nil
Using Guard Expressions
We can use guard expressions in forM
expressions. For example, the program:
let l1 = 1 :: 2 :: Nil;
let l2 = 1 :: 2 :: Nil;
forM (x <- l1; y <- l2; if x < y)
yield (x, y)
evaluates to the list:
(1, 2) :: Nil
Working with Options and Results
We can also use forM
to work with the Option
data type. For example:
def divide(x: Int32, y: Int32): Option[Int32] =
if (y == 0) None else Some(x / y)
def f(): Option[Int32] =
forM (
x <- divide(5, 2);
y <- divide(x, 8);
z <- divide(9, y)
) yield x + y + z
Here the function f
returns None
since x = 5 / 2 = 2
and 2 / 8 = 0
hence
the last division fails.
Similarly, we can use forM
to work with the Result[e, t]
data type. For
example:
def main(): Result[String, Unit] \ IO =
println("Please enter your first name, last name, and age:");
forM (
fstName <- Console.readLine();
lstName <- Console.readLine();
ageLine <- Console.readLine();
ageNum <- Int32.parse(10, ageLine)
) yield {
println("Hello ${lstName}, ${fstName}.");
println("You are ${ageNum} years old!")
}
Here main
prompts the user to enter their first name, last name, and age. Each
call to Console.readLine
returns a Result[String, String]
value which is
either an error or the input string. Thus the local variables fstName
,
lstName
, and ageLine
are String
s. 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 Monad
s, including Chain
and Nel
s
(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 anif
-guard requires an instance of theMonadZero
type class which is not implemented by non-empty list (since such a list cannot be empty).
Desugaring
The forM
expression is syntactic sugar for uses of Monad.flatMap
,
Applicative.point
, and MonadZero.empty
.
For example, the expression:
let l1 = 1 :: 2 :: Nil;
let l2 = 1 :: 2 :: Nil;
forM (x <- l1; y <- l2; if x < y)
yield (x, y)
is de-sugared to:
Monad.flatMap(x ->
Monad.flatMap(y ->
if (x < y)
Applicative.point((x, y))
else
MonadZero.empty(),
l2),
l1);
Applicative For-Yield
In addition to the monadic forM
expression, Flix supports an applicative
forA
expression that builds on the Applicative
type class. The forA
construct makes it simple to write error-handling code which uses the
Validation[e, t]
data type.
Working with Validations
We can use the forA
expression to validate user input while collecting all
errors.
enum Connection(String, String)
enum InvalidInput {
case InvalidUserName,
case InvalidPassword
}
def validateUser(s: String): Validation[InvalidInput, String] =
if (8 <= String.length(s) and String.forAll(Char.isLetter, s))
Validation.Success(s)
else
Validation.Failure(Nec.singleton(InvalidInput.InvalidUserName))
def validatePass(s: String): Validation[InvalidInput, String] =
if (12 <= String.length(s) and String.length(s) <= 20)
Validation.Success(s)
else
Validation.Failure(Nec.singleton(InvalidInput.InvalidPassword))
def connect(u: String, p: String): Validation[InvalidInput, Connection] =
forA (
user <- validateUser(u);
pass <- validatePass(p)
) yield Connection.Connection(user, pass)
The expression:
connect("Lucky Luke", "Ratata")
evaluates to:
Failure(Nec#{InvalidUserName, InvalidPassword})
which contains both input validation errors. On the other hand, the expression:
connect("luckyluke", "password12356789")
evaluates to:
Success(Connection(luckyluke, password12356789))
Applicatives are Independent Computations
We can write a monadic forM
expression where the result of one monadic
operation is used as the input to another monadic operation. For example:
forM(x <- Some(123); y <- Some(x))
yield (x, y)
Here the value of y
depends on x
. That is, the computation of x
and y
are not independent.
If we try to same with the applicative forA
expression:
forA(x <- Some(123); y <- Some(x))
yield (x, y)
then the Flix compiler emits a compiler error:
❌ -- Resolution Error --------------
>> Undefined name 'x'.
10 | y <- Some(x)
^
name not found
because the computations of x
and y
are independent and hence the value of
x
is not in scope when we define the value of y
.
Desugaring
The forA
expression is syntactic sugar for uses of Functor.map
and
Applicative.ap
.
For example, the expression:
let o1 = Some(21);
let o2 = Some(42);
forA(x <- o1; y <- o2)
yield x + y;
is de-sugared to:
Applicative.ap(Functor.map(x -> y -> x + y, o1), o2)
Structured Concurrency
Flix supports CSP-style concurrency with channels and processes inspired by Go and Rust.
Spawning Processes
We can spawn a process with the spawn
keyword:
def main(): Unit \ IO = region rc {
spawn println("Hello from thread") @ rc;
println("Hello from main")
}
Spawned processes are always associated with a region; the region will not exit until all the processes associated with it have completed:
def slowPrint(delay: Int32, message: String): Unit \ IO =
Thread.sleep(Time/Duration.fromSeconds(delay));
println(message)
def main(): Unit \ IO =
region r1 {
region r2 {
spawn slowPrint(2, "Hello from r1") @ r1;
spawn slowPrint(1, "Hello from r2") @ r2
};
println("r2 is now complete")
};
println("r1 is now complete")
This means that Flix supports structured concurrency; spawned processes have clearly defined entry and exit points.
Communicating with Channels
To communicate between processes we use channels. A channel allows two or more processes to exchange data by sending immutable messages to each other.
A channel comes in one of two variants: buffered or unbuffered. Channels are always associated with a region.
A buffered channel has a size, set at creation time, and can hold that many messages. If a process attempts to put a message into a buffered channel that is full, then the process is blocked until space becomes available. If, on the other hand, a process attempts to get a message from an empty channel, the process is blocked until a message is put into the channel.
An unbuffered channel works like a buffered channel of size zero; for a get and a put to happen both processes must rendezvous (block) until the message is passed from sender to receiver.
Here is an example of sending and receiving a message over a channel:
def main(): Int32 \ IO = region rc {
let (tx, rx) = Channel.unbuffered(rc);
spawn Channel.send(42, tx) @ rc;
Channel.recv(rx)
}
Here the main
function creates an unbuffered
channel which returns Sender
tx
and a Receiver
rx
channels,
spawns the send
function, and waits
for a message from the channel.
As the example shows, a channel consists of two end points:
the Sender and the Receiver. As one would expect,
messages can only be send using the Sender
, and only
received using the Receiver
.
Selecting on Channels
We can use the select
expression to receive a
message from a collection of channels.
For example:
def meow(tx: Sender[String, r]): Unit \ { Write(r) } =
Channel.send("Meow!", tx)
def woof(tx: Sender[String, r]): Unit \ { Read(r), Write(r) } =
Channel.send("Woof!", tx)
def main(): Unit \ IO = region rc {
let (tx1, rx1) = Channel.buffered(rc, 1);
let (tx2, rx2) = Channel.buffered(rc, 1);
spawn meow(tx1) @ rc;
spawn woof(tx2) @ rc;
select {
case m <- recv(rx1) => m
case m <- recv(rx2) => m
} |> println
}
Many important concurrency patterns such as
producer-consumer and load balancers can be expressed
using the select
expression.
Selecting with Default
In some cases, we do not want to block until a message arrives, potentially waiting forever. Instead, we want to take some alternative action if no message is readily available. We can achieve this with a default case as shown below:
def main(): String = region rc {
let (_, rx1) = Channel.buffered(rc, 1);
let (_, rx2) = Channel.buffered(rc, 1);
select {
case _ <- recv(rx1) => "one"
case _ <- recv(rx2) => "two"
case _ => "default"
}
}
Here a message is never sent to r1
nor r2
.
The select
expression tries all cases, and if no
channel is ready, it immediately selects the default
case.
Hence using a default case prevents the select
expression from blocking forever.
Selecting with Timeouts
As an alternative to a default case, we can use
tickers and timers to wait for pre-defined
periods of time inside a select
expression.
For example, here is a program that has a slow
function that takes a minute to send a message on
a channel, but the select
expression relies on
Channel.timeout
to only wait 5
seconds before
giving up:
def slow(tx: Sender[String, r]): Unit \ { Write(r), IO} =
Thread.sleep(Time/Duration.fromSeconds(60));
Channel.send("I am very slow", tx)
def main(): Unit \ IO = region rc {
let (tx, rx) = Channel.buffered(rc, 1);
spawn slow(tx) @ rc;
let timeout = Channel.timeout(rc, Time/Duration.fromSeconds(5));
select {
case m <- recv(rx) => m
case _ <- recv(timeout) => "timeout"
} |> println
}
This program prints the string "timeout"
after five
seconds.
Parallelism
We have seen how the spawn
expression allows us to evaluate an expression in a
new thread:
region rc {
spawn (1 + 2) @ rc
}
This allows us to write concurrent and parallel programs using structured
concurrency. The downside is that we must manually coordinate communication
between threads using channels.
If we want parallelism, but not concurrency, a more light-weight approach
is to use the par-yield
expression:
par (x <- e1; y <- e2; z <- e3)
yield x + y + z
which evaluates e1
, e2
, and e3
in parallel and binds their results to x
, y
, and z
.
We can use par-yield
to write a parallel List.map
function:
def parMap(f: a -> b, l: List[a]): List[b] = match l {
case Nil => Nil
case x :: xs =>
par (r <- f(x); rs <- parMap(f, xs))
yield r :: rs
}
This function will evaluate f(x)
and parMap(f, xs)
in parallel.
Note: The
par-yield
construct only works with pure expressions.
If you want to run effectful operations in parallel, you must use explicit regions and threads.
Effect System
The Flix type and effect system separates pure and impure expressions. A pure expression is guaranteed to be referentially transparent. A pure function always returns the same value when given the same argument(s) and cannot have any (observable) side-effects.
For example, the following expression is of type
Int32
and is pure (marked with \ {}
):
1 + 2 : Int32 \ {}
whereas the following expression is impure (marked with \ IO
):
println("Hello World") : Unit \ IO
A higher-order function can specify that a function argument must be pure, impure, or that it is effect polymorphic.
For example, the definition of Set.exists
requires
that its function argument f
is pure:
// The syntax a -> Bool is short-hand for a -> Bool \ {}
def exists(f: a -> Bool, s: Set[a]): Bool = ???
The requirement that f
must be pure ensures that
implementation details do not leak.
For example, since f
is pure it cannot be used to
determine in what order the elements of the set are
traversed.
If f
was impure such details could leak, e.g. by
passing a function that also prints the current
element, revealing the internal element order inside
the set.
The type and effect system is sound, but not complete. That is, if a function is pure then it cannot cause an effect, whereas if a function is impure then it may, but does not necessarily, cause an effect. For example, the following expression is impure even though it cannot produce an effect at run-time:
if (1 == 2) println("Hello World!") else ()
A higher-order function can also be effect polymorphic: its effect(s) can depend on its argument(s).
For example, the standard library definition of
List.map
is effect polymorphic:
def map(f: a -> b \ ef, xs: List[a]): List[b] \ ef
The List.map
function takes a function f
from
elements of type a
to b
with effect ef
.
The effect of the function itself is ef
.
Consequently, if List.map
is invoked with a pure
function then the entire expression is pure whereas
if it is invoked with an impure function then the
entire expression is impure.
A higher-order function that takes multiple function arguments may combine their effects.
For example, the standard library definition of
forward function composition >>
is pure if both its
function arguments are pure:
def >>(f: a -> b \ ef1, g: b -> c \ ef2): a -> c \ { ef1, ef2 } = x -> g(f(x))
The type and effect signature can be understood as
follows: The >>
function takes two function
arguments: f
with effect ef1
and g
with
effect ef2
.
The effect of >>
is effect polymorphic in the
conjunction of ef1
and ef2
.
If both are pure (their effect is true
) then the
overall expression is pure (true
).
Otherwise it is impure.
The type and effect system allows arbitrary boolean expressions to control the purity of function arguments.
For example, it is possible to express a higher-order
function h
that accepts two function arguments f
and g
of which at most one is impure:
def h(f: a -> b \ ef1, g: b -> c \ { (not ef1) or ef2 }): Unit
Note that here ef1
and ef2
are arbitrary boolean
variables which are not directly associated with the
effect of f
or g
(like it was the case in the
simpler example above).
In general, the possible effects for argument
functions and the to-be-defined function are described
by arbitrary boolean expressions.
Here the possible effects of g
(whether it can be
pure or impure) are specified by the boolean
not ef1 or ef2
.
For a specific combination of pure and impure to be
accepted, there must be an assignment of the boolean
variables ef1
and ef2
to true and false such that
the boolean expressions for pure arguments evaluate
to true
and those for impure arguments evaluate to
false
.
If in this example h
is called with a function
argument f
which is impure, then the variable ef1
must be false and thus the second argument must be
pure (because not ef1 or ef2
will always be true,
no matter how we choose ef2
).
Conversely, if f
is pure, then ef1
must be true
and g
may be pure (ef2 = true
) or impure
(ef2 = false
).
It is a compile-time error to call h
with two impure
functions.
The type and effect system can be used to ensure that statement expressions are useful, i.e. that if an expression or function is evaluated and its result is discarded then it must have a side-effect. For example, compiling the program fragment below:
List.map(x -> x + 1, 1 :: 2 :: Nil);
123
causes a compiler error:
-- Redundancy Error -------------------------------------------------- ???
>> Useless expression: It has no side-effect(s) and its result is discarded.
2 | List.map(x -> x + 1, 1 :: 2 :: Nil);
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
useless expression.
Possible fixes:
(1) Use the result computed by the expression.
(2) Remove the expression statement.
(3) Introduce a let-binding with a wildcard name.
because it is non-sensical to evaluate the pure
expression
List.map(x -> 2 * x, 1 :: 2 :: Nil)
and then to
discard its result.
Most likely the programmer wanted to use the result
(or alternatively the expression is redundant and
could be deleted).
Consequently, Flix rejects such programs.
In summary, Flix function types are of the form:
Function Type | Syntax | Short 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 \ ef | n/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 use
s together into one:
use Math.{sum, mul};
def main(): Unit \ IO =
mul(42, 84) |> sum(21) |> println
Note: Flix does not support wildcard uses since they can lead to subtle bugs.
Avoiding Name Clashes with Renaming
We can use renaming to avoid name clashes between identically named declarations.
For example, if we have two modules:
mod A {
pub def concat(x: String, y: String): String = x + y
}
mod B {
pub def concat(xs: List[Int32], ys: List[Int32]): List[Int32] = xs ::: ys
}
We can then use
each concat
function under a unique name. For example:
use A.{concat => concatStrings}
use B.{concat => concatLists}
def main(): Unit \ IO =
concatStrings("Hello", " World!") |> println
While this feature is powerful, in many cases using a fully-qualified might be more appropriate.
Modules and Enums
We can define an enum inside a module. For example:
mod Zoo {
pub enum Animal {
case Cat,
case Dog,
case Fox
}
}
Here the Zoo
module contains an enum type named Animal
which has three
cases: Cat
, Dog
, and Fox
.
We can access the type and the cases using their fully-qualified names:
def says(a: Zoo.Animal): String = match a {
case Zoo.Animal.Cat => "Meow"
case Zoo.Animal.Dog => "Woof"
case Zoo.Animal.Fox => "Roar"
}
def main(): Unit \ IO =
println("A cat says ${says(Zoo.Animal.Cat)}!")
Alternatively, we can use
both the Animal
type and its cases:
use Zoo.Animal
use Zoo.Animal.Cat
use Zoo.Animal.Dog
use Zoo.Animal.Fox
def says(a: Animal): String = match a {
case Animal.Cat => "Meow"
case Animal.Dog => "Woof"
case Animal.Fox => "Roar"
}
def main(): Unit \ IO =
println("A cat says ${says(Cat)}!")
Note that use Zoo.Animal
brings the Animal
type into scope, whereas use Zoo.Animal.Cat
brings the Cat
case into scope.
Modules and Type Classes
We can also define a type class inside a module. The mechanism is similar to enums inside modules.
For example, we can write:
mod Zoo {
pub class Speakable[t] {
pub def say(x: t): String
}
}
enum Animal with ToString {
case Cat,
case Dog,
case Fox
}
instance Zoo.Speakable[Animal] {
pub def say(a: Animal): String = match a {
case Cat => "Meow"
case Dog => "Woof"
case Fox => "Roar"
}
}
We can use fully-qualified names to write:
def speak(x: t): Unit \ IO with Zoo.Speakable[t], ToString[t] =
println("A ${x} says ${Zoo.Speakable.say(x)}!")
def main(): Unit \ IO =
speak(Animal.Cat)
Or we can use
the Zoo.Speakable
type class and the Zoo.Speakable.say
function:
use Zoo.Speakable
use Zoo.Speakable.say
def speak(x: t): Unit \ IO with Speakable[t], ToString[t] =
println("A ${x} says ${say(x)}!")
Declaring Modules
As we have already seen, modules can be declared using the mod
keyword:
mod Museum {
// ... members ...
}
We can nest modules inside other modules:
mod Museum {
mod Entrance {
pub def buyTicket(): Unit \ IO =
println("Museum.Entrance.buyTicket() was called.")
}
mod Restaurant {
pub def buyMeal(): Unit \ IO =
println("Museum.Restaurant.buyMeal() was called.")
}
mod Giftshop {
pub def buyGift(): Unit \ IO =
println("Museum.Giftshop.buyGift() was called.")
}
}
We can call these methods as follows:
def main(): Unit \ IO =
Museum.Entrance.buyTicket();
Museum.Restaurant.buyMeal();
Museum.Giftshop.buyGift()
Or alternatively as follows:
use Museum.Entrance.buyTicket;
use Museum.Restaurant.buyMeal;
use Museum.Giftshop.buyGift;
def main(): Unit \ IO =
buyTicket();
buyMeal();
buyGift()
Accessibility
A module member m
declared in module A
is accessible from another module B
if:
- the member
m
is declared as public (pub
). - the module
B
is a sub-module ofA
.
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 use
s 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
andList.Cons
.Result.Ok
andResult.Err
.
Companion Modules
In Flix every enum and type class declaration is associated with a companion module.
Enum Companions
When we declare an enum, its type and cases are automatically available inside its companion module. For example, we can write:
enum Color {
case Red,
case Green,
case Blue
}
mod Color {
pub def isWarm(c: Color): Bool = match c {
case Red => true
case Green => false
case Blue => false
}
}
Here the Color
type and the Red
, Green
, and Blue
cases are automatically
in scope within the companion Color
module.
Type Class Companions
Every type class declaration also gives rise to a companion module.
For example, we can define a type class Addable
for types whose elements can be added:
class Addable[t] {
pub def add(x: t, y: t): t
}
The Addable
type class implicitly introduces a companion module Addable
. We
typically use the companion module to store functionality that is related to the
type class.
For example, we could have:
mod Addable {
pub def add3(x: t, y: t, z: t): t with Addable[t] = add(add(x, y), z)
}
When accessing a member of Addable
, Flix will automatically look in both the
class declaration and its companion namespace. Consequently, Addable.add
refers to the type class member add
whereas Addable.add3
refers to the
function inside the Addable
module. Note that the add
signature is in the
scope of the Addable
module.
We should be aware that functions defined in the companion module of a type class cannot be overridden by instances of the associated type class. Thus we should only put members into the companion namespace when we do not intend to override them later.
Type Classes
Type classes are one of the ways to support a high level of genericity in functional programming. Flix's type classes largely follow the style of those of Haskell, with some additional principles.
Essentials
The function isSingleton
naively determines whether
a list has exactly one element.
However, it only works with lists.
Although checking the length of a collection like
this is possible for all standard collections, we
have to implement a separate isSingleton
function
for each of them.
def isSingleton(l: List[a]): Bool =
List.length(l) == 1
We can generalize this behavior by using a type class
constraint.
Rather than requiring the argument to be a list, we
use a type variable a
and constrain it with to the
type class Length
, which means that the function
Length.length
can be applied to the argument.
def isSingleton(l: a): Bool with Length[a] =
Length.length(l) == 1
The type class declaration Length
specifies what
can be done with its members.
In this case, there is only one function:
Length.length
, which takes the member type as an
argument and returns an integer.
The law nonnegative
is also defined as part of the
class.
Laws will be further explored below.
pub class Length[a] {
pub def length(x: a): Int32
law nonnegative: forall(x: a) . Length.length(x) >= 0
}
If we try to use the new isSingleton
function, we
will see that it fails to compile:
isSingleton(1 :: 2 :: Nil)
While we know that a list has a length, we haven't
told this to the compiler.
To do this, we introduce an instance
of the type
class for the generic type List[a]
.
instance Length[List[a]] {
pub def length(x: List[a]): Int32 = List.length(x)
}
This instance simply states that in order to get the
length of the list, we just use the List.length
function from the standard library.
With this instance around, the call to the
isSingleton
function will compile.
However, you may have noticed that our implementation
is inefficient.
While comparing the length to 1 is a correct solution
generally, for lists specifically the solution has a
greater runtime complexity than necessary.
In order to preserve the general solution while
allowing for optimizations where needed, we can use a
default implementation in the type class and an
override implementation in the instance.
pub class Length[a] {
pub def length(x: a): Int32
pub def isSingleton(x: a): Bool = length(x) == 1
law nonnegative: forall(x: a) . Length.length(x) >= 0
law singletonMeansOne: forall(x: a) . Length.length(x) == 1 <==> Length.isSingleton(x)
}
instance Length[List[a]] {
pub def length(x: List[a]): Int32 = List.length(x)
override pub def isSingleton(x: List[a]): Bool = match x {
case _ :: Nil => true
case _ => false
}
}
We have added the isSingleton
function to the
Length
type class, with a default implementation
that works in general.
(We also added a new law singletonMeansOne
; see
section Laws.)
We have added an efficient override
implementation
of isSingleton
to the Length
instance for
List[a]
.
The advantage of the default implementation is that
if there's no special behavior needed for a type, the
default is assumed.
The function does not have to be implemented.
instance Length[String] {
pub def length(x: String): Int32 = String.length(x)
}
The instance Length[String]
simply uses the default
implementation of the isSingleton
function.
Laws
In addition to the functions forming part of their contract, type classes have laws that govern how the functions may be implemented.
pub class Length[a] {
pub def length(x: a): Int32
law nonnegative: forall(x: a) . Length.length(x) >= 0
}
The nonnegative
law asserts that the length of
something can never be negative.
Planned Feature
We plan to implement a quickcheck framework to verify that these laws hold. For now, however, they only serve as a form of documentation.
Type Constraints
We've seen type constraints on on function definitions, but constraints can appear on on instances and type classes themselves as well.
pub class TreeSize[a] {
/// Returns the number of nodes in the object graph of this object
pub def size(x: a): Int32
law positive: forall(x: a) . size(x) > 0
}
instance TreeSize[Int32] {
pub def size(x: Int32): Int32 = 1
}
instance TreeSize[List[a]] with TreeSize[a] {
pub def size(x: List[a]): Int32 = {
// one node for each cons cell, one for the nil, and nodes for each node's value
List.Length(x) + 1 + List.foldLeft((acc, y) -> acc + TreeSize.size(y), 0, x)
}
}
Sealed Classes
In general, a user can add an instance of a class for
any type they define.
In some cases, however, it is useful to restrict
membership in a class to a finite list of types,
defined by the author of the class.
This is the purpose of a sealed
class, for which
instances outside the class's namespace are not
permitted.
sealed class Primitive[a]
instance Primitive[Bool]
instance Primitive[Int32]
instance Primitive[Float64]
// ... and so on
Essential Classes
Practical programming in Flix requires knowledge of three type classes: Eq
,
Order
, and ToString
.
The Eq Class
The Eq
class captures when two values of a specific type are equal:
class Eq[a] {
///
/// Returns `true` if and only if `x` is equal to `y`.
///
pub def eq(x: a, y: a): Bool
// ... additional members omitted ...
}
To implement Eq
, we only have to implement the eq
function.
The Order Class
The Order
class captures when one value is smaller or equal to another value
of the same type:
class Order[a] with Eq[a] {
///
/// Returns `Comparison.LessThan` if `x` < `y`,
/// `Equal` if `x` == `y` or
/// `Comparison.GreaterThan` if `x` > `y`.
///
pub def compare(x: a, y: a): Comparison
// ... additional members omitted ...
}
To implement the Order
class, we must implement the compare
function which
returns value of type Comparison
. The Comparison
data type is defined as:
enum Comparison {
case LessThan
case EqualTo
case GreaterThan
}
The ToString Class
The ToString
class is used to obtain a string representation of a specific value:
class ToString[a] {
///
/// Returns a string representation of the given `x`.
///
pub def toString(x: a): String
}
Flix uses the ToString
type class in string interpolations.
For example, the interpolated string
"Good morning ${name}, it is ${hour} a clock."
is actually syntactic sugar for the expression:
"Good morning " + ToString.toString(name) + ", it is "
+ ToString.toString(hour) + " a clock."
In the following subsection, we discuss how to automatically derive
implementations of the Eq
, Order
, and ToString
type classes.
Automatic Derivation
Flix supports automatic derivation of several type classes, including:
Eq
— to derive structural equality on the values of a type.Order
— to derive a total ordering on the values of a type.ToString
— to derive a human-readable string representation on the values of a type.Sendable
— to enable the values of an (immutable) type to be sent over a channel.
Derivation of Eq and Order
We can automatically derive instances of the Eq
and Order
type classes using
the with
clause in the enum
declaration. For example:
enum Shape with Eq, Order {
case Circle(Int32)
case Square(Int32)
case Rectangle(Int32, Int32)
}
The derived implementations are structural and rely on the order of the case declarations:
def main(): Unit \ IO =
println(Circle(123) == Circle(123)); // prints `true`.
println(Circle(123) != Square(123)); // prints `true`.
println(Circle(123) <= Circle(123)); // prints `true`.
println(Circle(456) <= Square(123)) // prints `true`.
Note: Automatic derivation of
Eq
andOrder
requires that the inner types of theenum
implementEq
andOrder
themselves.
Derivation of ToString
We can also automatically derive ToString
instances:
enum Shape with ToString {
case Circle(Int32)
case Square(Int32)
case Rectangle(Int32, Int32)
}
Then we can take advantage of string interpolation and write:
def main(): Unit \ IO =
let c = Circle(123);
let s = Square(123);
let r = Rectangle(123, 456);
println("A ${c}, ${s}, and ${r} walk into a bar.")
which prints:
A Circle(123), Square(123), and Rectangle(123, 456) walk into a bar.
Derivation of Sendable
We can automatically derive implementations of the Sendable
type class (which
allow values of a specific type to be sent over a channel). For example:
enum Shape with Sendable, ToString {
case Circle(Int32)
}
def main(): Unit \ IO =
region rc {
let (tx, rx) = Channel.buffered(rc, 10);
Channel.send(Circle(123), tx); // OK, since Shape is Sendable.
println(Channel.recv(rx))
}
We cannot derive Sendable
for types that rely on scoped mutable memory. For
example, if we try:
enum Shape[r: Region] with Sendable {
case Circle(Array[Int32, r])
}
The Flix compiler emits a compiler error:
❌ -- Safety Error --------------------------------------
>> Cannot derive 'Sendable' for type Shape[b27587945]
Because it takes a type parameter of kind 'Region'.
1 | enum Shape[r: Region] with Sendable {
^^^^^^^^
unable to derive Sendable.
This is because mutable data is not safe to share between threads.
Higher-Kinded Types
Flix supports higher-kinded types, hence type class can abstract over type constructors.
For example, we can write a type class that capture iteration over any
collection of the shape t[a]
where t
is a type constructor of kind
Type -> Type
and a
is the element type of kind Type
:
class ForEach[t: Type -> Type] {
pub def forEach(f: a -> Unit \ ef, x: t[a]): Unit \ ef
}
Note that to use higher-kinded types Flix requires us to provide the kind
annotation (i.e. we had to write t: Type -> Type
to inform Flix that ForEach
abstracts over type constructors.)
We can implement instances of the ForEach
type class for type constructors
such as Option
, and List
, Set
. For example:
instance ForEach[List] {
pub def forEach(f: a -> Unit \ ef, l: List[a]): Unit \ ef = match l {
case Nil => ()
case x :: xs => f(x); ForEach.forEach(f, xs)
}
}
Note: Flix does not have a
ForEach
type class, but instead has the much more powerful and versatileFoldable
type class.
The Flix Kinds
Flix supports the following kinds:
Type
: The kind of Flix types.- e.g.
Int32
,String
, andList[Int32]
.
- e.g.
RecordRow
: The kind of rows used in records- e.g. in
{x = Int32, y = Int32 | r}
the type variabler
has kindRecordRow
.
- e.g. in
SchemaRow
: The kind of rows used in first-class Datalog constraints- e.g. in
#{P(Int32, Int32) | r}
the type variabler
has kindSchemaRow
.
- e.g. in
Flix can usually infer kinds. For example, we can write:
def sum(r: {x = t, y = t | r}): t with Add[t] = r.x + r.y
and have the kinds of t: Type
and r: RecordRow
automatically inferred.
We can also explicitly specify them as follows:
def sum[t: Type, r: RecordRow](r: {x = t, y = t | r}): t with Add[t] = r.x + r.y
but this style is not considered idiomatic.
Flix requires explicit kind annotations in two situations:
- For non-Type kinds on enum type parameters.
- For non-Type kinds on type classes.
In other words, if you are only using types of kind Type
, no annotations are
necessary. But if you want an enum declaration or type class to abstract over a
non-Type kind then you must explicitly write its kind.
Laziness
Flix uses eager evaluation in most circumstances, but allows the programmer to opt-in to lazy evaluation when appropriate with the lazy
keyword:
let x: Lazy[Int32] = lazy (1 + 2);
The expression won't be evaluated until it's forced:
let y: Int32 = force x;
Note: The
lazy
construct requires the expression it's given to be pure.
Note: Forcing a lazy value that's already been evaluated won't evaluate it for a second time.
Lazy data structures
Laziness can be used to create lazy data structures which are evaluated as they're used. This even allows us to create infinite data structures.
Here for example, is a data structure which implements an infinitely long stream of integers which increase by one each time:
namespace IntStream {
enum IntStream { case SCons(Int32, Lazy[IntStream]) }
pub def from(x: Int32): IntStream =
IntStream.SCons(x, lazy from(x + 1))
}
Given this, we can implement functions such as map
and take
:
pub def take(n: Int32, s: IntStream): List[Int32] =
match n {
case 0 => Nil
case _ => match s {
case SCons(h, t) => h :: take(n - 1, force t)
}
}
pub def map(f: Int32 -> Int32, s: IntStream): IntStream =
match s {
case SCons(h, t) => IntStream.SCons(f(h), lazy map(f, force t))
}
So, for example:
IntStream.from(42) |> IntStream.map(x -> x + 10) |> IntStream.take(10)
Will return:
52 :: 53 :: 54 :: 55 :: 56 :: 57 :: 58 :: 59 :: 60 :: 61 :: Nil
Flix provides DelayList
and DelayMap
data structures which already implement this functionality and more:
DelayList.from(42) |> DelayList.map(x -> x + 10) |> DelayList.take(10)
Fixpoints
A unique feature of Flix is its built-in support for fixpoint computations on constraint on relations and constraint on lattices.
We assume that the reader is already familiar with Datalog and focus on the Flix specific features.
Using Flix to Solve Constraints on Relations
We can use Flix to solve a fixpoint computation inside a function.
For example, given a set of edges s
, a src
node,
and dst
node, compute if there is a path from src
to dst
.
We can elegantly solve this problem as follows:
def isConnected(s: Set[(Int32, Int32)], src: Int32, dst: Int32): Bool =
let rules = #{
Path(x, y) :- Edge(x, y).
Path(x, z) :- Path(x, y), Edge(y, z).
};
let edges = inject s into Edge;
let paths = query edges, rules select true from Path(src, dst);
not (paths |> Vector.isEmpty)
def main(): Unit \ IO =
let s = Set#{(1, 2), (2, 3), (3, 4), (4, 5)};
let src = 1;
let dst = 5;
if (isConnected(s, src, dst)) {
println("Found a path between ${src} and ${dst}!")
} else {
println("Did not find a path between ${src} and ${dst}!")
}
The isConnected
function behaves like any other
function: We can call it with a set of edges
(Int32
-pairs), an Int32
source node, and
an Int32
destination node.
What is interesting about isConnected
is that its
implementation uses a small Datalog program to solve
the task at hand.
In the isConnected
function, the local variable
rules
holds a Datalog program fragment that
consists of two rules which define the Path
relation.
Note that the predicate symbols, Edge
and Path
do
not have to be explicitly introduced; they are simply
used.
The local variable edges
holds a collection of edge
facts that are obtained by taking all the tuples in
the set s
and turning them into Edge
facts.
Next, the local variable paths
holds the result of
computing the fixpoint of the facts and rules
(edges
and rules
) and selecting the Boolean
true
if there is a Path(src, dst)
fact.
Note that here src
and dst
are the
lexically-bound function parameters.
Thus, paths
is either an empty array (no paths were
found) or a one-element array (a path was found), and
we simply return this fact.
Flix is strongly typed.
Any attempt to use predicate symbol with terms of the
wrong type (or with the wrong arity) is caught by the
type checker.
Note also that Flix supports type inference, hence we
did not have to declare the type of Edge
nor of
Path
.
Programming with First-class Constraints
A unique feature of Flix is its support for first-class constraints. A first-class constraint is a value that can be constructed, passed around, composed with other constraints, and ultimately solved. The solution to a constraint system is another constraint system which can be further composed. For example:
def getParents(): #{ ParentOf(String, String) | r } = #{
ParentOf("Pompey", "Strabo").
ParentOf("Gnaeus", "Pompey").
ParentOf("Pompeia", "Pompey").
ParentOf("Sextus", "Pompey").
}
def getAdoptions(): #{ AdoptedBy(String, String) | r } = #{
AdoptedBy("Augustus", "Caesar").
AdoptedBy("Tiberius", "Augustus").
}
def withAncestors(): #{ ParentOf(String, String),
AncestorOf(String, String) | r } = #{
AncestorOf(x, y) :- ParentOf(x, y).
AncestorOf(x, z) :- AncestorOf(x, y), AncestorOf(y, z).
}
def withAdoptions(): #{ AdoptedBy(String, String),
AncestorOf(String, String) | r } = #{
AncestorOf(x, y) :- AdoptedBy(x, y).
}
def main(): Unit \ IO =
let c = false;
if (c) {
query getParents(), getAdoptions(), withAncestors()
select (x, y) from AncestorOf(x, y) |> println
} else {
query getParents(), getAdoptions(), withAncestors(), withAdoptions()
select (x, y) from AncestorOf(x, y) |> println
}
The program uses three predicate symbols: ParentOf
,
AncestorOf
, and AdoptedBy
.
The getParents
function 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 symbolsA
orB
, but it does guarantee that it will not contain any fact or rule that refer to a predicate symbolC
.
Polymorphic First-class Constraints
Another unique feature of Flix is its support for first-class polymorphic constraints. That is, constraints where one or more constraints are polymorphic in their term types. For example:
def edgesWithNumbers(): #{ LabelledEdge(String, Int32 , String) | r } = #{
LabelledEdge("a", 1, "b").
LabelledEdge("b", 1, "c").
LabelledEdge("c", 2, "d").
}
def edgesWithColor(): #{ LabelledEdge(String, String, String) | r } = #{
LabelledEdge("a", "red", "b").
LabelledEdge("b", "red", "c").
LabelledEdge("c", "blu", "d").
}
def closure(): #{ LabelledEdge(String, l, String),
LabelledPath(String, l, String) } with Order[l] = #{
LabelledPath(x, l, y) :- LabelledEdge(x, l, y).
LabelledPath(x, l, z) :- LabelledPath(x, l, y), LabelledPath(y, l, z).
}
def main(): Unit \ IO =
query edgesWithNumbers(), closure()
select (x, l, z) from LabelledPath(x, l, z) |> println;
query edgesWithColor(), closure()
select (x, l, z) from LabelledPath(x, l, z) |> println
Here we use two predicate symbols: LabelledEdge
and
LabelledPath
.
Each predicate has a type parameter named l
and is
polymorphic in the "label" type associated with the
edge/path.
Note how edgesWithNumbers
returns a collection of
edge facts where the labels are integers, whereas
edgesWithColor
returns a collection of facts where
the labels are strings.
The closure
function is polymorphic and returns two
rules that compute the transitive closure of edges
that have the same label.
The Flix type system ensures that we cannot accidentally mix edges (or paths) with different types of labels.
Injecting Facts into Datalog
Flix provides a flexible mechanism that allows functional data structures (such as lists, sets, and maps) to be converted into Datalog facts.
For example, given a Flix list of pairs we can convert it to a collection of Datalog facts:
let l = (1, 2) :: (2, 3) :: Nil;
let p = inject l into Edge;
where l
has type List[(Int32, Int32)]
.
The inject
expression converts l
into a Datalog
constraint set p
of type
#{ Edge(Int32, Int32) | ... }
.
The inject
expression works with any type that
implements the Foldable
type class.
Consequently, it can be used with lists, sets, maps,
and so forth.
The inject
expression can operate on multiple
collections simultaneously.
For example:
let names = "Lucky Luke" :: "Luke Skywalker" :: Nil;
let jedis = "Luke Skywalker" :: Nil;
let p = inject names, jedis into Name, Jedi;
where p
has type
#{ Name(String), Jedi(String) | ... }
.
Pipelines of Fixpoint Computations
The solution (i.e. fixpoint) of a constraint system is another constraint system. We can use this to construct pipelines of fixpoint computations, i.e. to feed the result of one fixpoint computation into another fixpoint computation. For example:
def main(): Unit \ IO =
let f1 = #{
ColorEdge(1, "blue", 2).
ColorEdge(2, "blue", 3).
ColorEdge(3, "red", 4).
};
let r1 = #{
ColorPath(x, c, y) :- ColorEdge(x, c, y).
ColorPath(x, c, z) :- ColorPath(x, c, y), ColorEdge(y, c, z).
};
let r2 = #{
ColorlessPath(x, y) :- ColorPath(x, _, y).
};
let m = solve f1, r1 project ColorPath;
query m, r2 select (x, y) from ColorlessPath(x, y) |> println
The program uses three predicates: ColorEdge
,
ColorPath
, and ColorlessPath
.
Our goal is to compute the transitive closure of the
colored edges and then afterwards construct a graph
where the edges have no color.
The program first computes the fixpoint of f1
and
r1
and injects out the ColorPath
fact.
The result is stored in m
. Next, the program
queries m
and r2
, and selects all ColorlessPath
facts.
Stratified Negation
Flix supports stratified negation which allow restricted use of negation in rule bodies. For example:
def main(): Unit \ IO =
let movies = #{
Movie("The Hateful Eight").
Movie("Interstellar").
};
let actors = #{
StarringIn("The Hateful Eight", "Samuel L. Jackson").
StarringIn("The Hateful Eight", "Kurt Russel").
StarringIn("The Hateful Eight", "Quentin Tarantino").
StarringIn("Interstellar", "Matthew McConaughey").
StarringIn("Interstellar", "Anne Hathaway").
};
let directors = #{
DirectedBy("The Hateful Eight", "Quentin Tarantino").
DirectedBy("Interstellar", "Christopher Nolan").
};
let rule = #{
MovieWithoutDirector(title) :-
Movie(title),
DirectedBy(title, name),
not StarringIn(title, name).
};
query movies, actors, directors, rule
select title from MovieWithoutDirector(title) |> println
The program defines three local variables that
contain information about movies, actors, and
directors.
The local variable rule
contains a rule that
captures all movies where the director does not star
in the movie.
Note the use negation in this rule.
The query returns an array with the string
"Interstellar"
because Christopher Nolan did not
star in that movie.
Note: Flix enforces that programs are stratified, i.e. a program must not have recursive dependencies on which there is use of negation. If there is, the Flix compiler rejects the program.
Local Predicates
Flix supports an abstract mechanism called local predicates. A local predicate, like a local variable, is not visible to the outside.
To understand local predicates, consider the following example: We can a write a function that returns a Datalog program value which computes whether a graph has a cycle:
def cyclic(): #{Edge(Int32, Int32), Path(Int32, Int32), Cyclic()} = #{
Path(x, y) :- Edge(x, y).
Path(x, z) :- Path(x, y), Edge(y, z).
Cyclic() :- Path(x, x).
}
def main(): Unit \ IO =
let db = #{
Edge(1, 2).
Edge(2, 3).
Edge(3, 1).
};
query db, cyclic() select true from Cyclic() |> println
Here the cyclic
function returns a Datalog program value which consists of
three rules that compute the transitive closure of a graph of edges and whether
there is path from a vertex to itself. We use the cyclic
function inside
main
to determine if a small graph, given by db
, has a cyclic. The program
prints Vector#{true}
when compiled and run.
Returning to cyclic
, we see that its type is:
def cyclic(): #{Edge(Int32, Int32), Path(Int32, Int32), Cyclic()} = ...
This is sensible because the Datalog program value uses the predicate symbols
Edge
, Path
and Cyclic
with their given types. However, if we think more
about it, we can realize that the Path
predicate is really local to the
computation: We are not meant to see it from the outside; it is an
implementation detail! What we really want is that Edge(Int32, Int32)
should
be an input and Cyclic()
should be an output. More importantly,
Path(Int32, Int32)
should not be visible from the outside nor part of the
type. We can achieve this with predicate abstraction:
def cyclic(): #{Edge(Int32, Int32), Cyclic()} =
#(Edge, Cyclic) -> #{
Path(x, y) :- Edge(x, y).
Path(x, z) :- Path(x, y), Edge(y, z).
Cyclic() :- Path(x, x).
}
Here we use the syntax #(Edge, Cyclic) -> v
to specific that only the
predicates Edge
and Cyclic
from within v
should be visible to the outside.
Thus we can omit Path(Int32, Int32)
from the return type of cyclic
.
Moreover, the Datalog program value no longer contains a Path
predicate symbol
that can be referenced. We can evidence this by observing that the program:
def main(): Unit \ IO =
let db = #{
Edge(1, 2).
Edge(2, 3).
Edge(3, 1).
};
query db, cyclic() select (x, y) from Path(x, y) |> println
prints the empty vector Vector#{}
since Path
has been made local by the predicate
abstraction.
Functional Predicates
We sometimes run into a situation where we would like to use a logic predicate, but not to exhaustively enumerate all of its tuples.
For example, we can image a situation where we want a predicate
PrimeInRange(from, to, prime)
which holds if prime
is a prime number in the
range [from; to]
. While we can imagine such a predicate, it is not feasible to
compute with. Instead, what we often want, is that we want to treat
PrimeInRange
as a functional, i.e. a function that given from
and to
as input produces a set of primes as output. To make matters concrete, we
might want to write the rule:
R(p) :- P(x), Q(y), PrimeInRange(x, y, p).
but without having to evaluate PrimeInRange
for every x
, y
, and p
.
We can achieve this as follows. We write a function:
def primesInRange(b: Int32, e: Int32): Vector[Int32] =
Vector.range(b, e) |> Vector.filter(isPrime)
The key is that primesInRange
is a function which returns a vector of tuples
(in this case single elements), given a begin b
and end index e
. Thus
primesInRange
can efficiently compute the tuples we are interested in. To use
it in our rule, we write:
R(p) :- P(b), Q(e), let p = primesInRange(b, e).
where b
and e
are clearly identified as the input of primesInRange
and p
as its output. Specifically, Flix requires that b
and e
are positively bound
(i.e. bound by a non-negative body atom-- in this case P
and Q
.) In this
case, primesInRanges
returns a vector of Int32
s, 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)
thena
andb
must not be rebound in the rule.
Using Flix to Solve Constraints on Lattices
Flix supports not only constraints on relations, but also constraints on lattices. To create such constraints, we must first define the lattice operations (the partial order, the least upper bound, and so on) as functions, associate them with a type, and then declare the predicate symbols that have lattice semantics.
We begin with the definition of the Sign
data type:
enum Sign {
case Top,
case Neg,
case Zer,
case Pos,
case Bot
}
We need to define the usual Eq
, Order
, and
ToString
instances for this new type.
Note that the order instance is unrelated to the
partial order instance we will later define, and is
simply used to sort elements for pretty printing etc.
instance Eq[Sign] {
pub def eq(x: Sign, y: Sign): Bool = match (x, y) {
case (Bot, Bot) => true
case (Neg, Neg) => true
case (Zer, Zer) => true
case (Pos, Pos) => true
case (Top, Top) => true
case _ => false
}
}
instance Order[Sign] {
pub def compare(x: Sign, y: Sign): Comparison =
let num = w -> match w {
case Bot => 0
case Neg => 1
case Zer => 2
case Pos => 3
case Top => 4
};
num(x) <=> num(y)
}
instance ToString[Sign] {
pub def toString(x: Sign): String = match x {
case Bot => "Bot"
case Neg => "Neg"
case Zer => "Zer"
case Pos => "Pos"
case Top => "Top"
}
}
With these type class instances in place, we can now
define the lattice operations on Sign
.
We define the bottom element and the partial order:
instance LowerBound[Sign] {
pub def minValue(): Sign = Bot
}
instance PartialOrder[Sign] {
pub def lessEqual(x: Sign, y: Sign): Bool =
match (x, y) {
case (Bot, _) => true
case (Neg, Neg) => true
case (Zer, Zer) => true
case (Pos, Pos) => true
case (_, Top) => true
case _ => false
}
}
Next, we define the least upper bound and greatest lower bound:
instance JoinLattice[Sign] {
pub def leastUpperBound(x: Sign, y: Sign): Sign =
match (x, y) {
case (Bot, _) => y
case (_, Bot) => x
case (Neg, Neg) => Neg
case (Zer, Zer) => Zer
case (Pos, Pos) => Pos
case _ => Top
}
}
instance MeetLattice[Sign] {
pub def greatestLowerBound(x: Sign, y: Sign): Sign =
match (x, y) {
case (Top, _) => y
case (_, Top) => x
case (Neg, Neg) => Neg
case (Zer, Zer) => Zer
case (Pos, Pos) => Pos
case _ => Bot
}
}
With all of these definitions we are ready to write Datalog constraints with lattice semantics. But before we proceed, let us also write a single monotone function:
def sum(x: Sign, y: Sign): Sign = match (x, y) {
case (Bot, _) => Bot
case (_, Bot) => Bot
case (Neg, Zer) => Neg
case (Zer, Neg) => Neg
case (Zer, Zer) => Zer
case (Zer, Pos) => Pos
case (Pos, Zer) => Pos
case (Pos, Pos) => Pos
case _ => Top
}
We can now finally put everything to use:
pub def main(): Unit \ IO =
let p = #{
LocalVar("x"; Pos).
LocalVar("y"; Zer).
LocalVar("z"; Neg).
AddStm("r1", "x", "y").
AddStm("r2", "x", "y").
AddStm("r2", "y", "z").
LocalVar(r; sum(v1, v2)) :-
AddStm(r, x, y), LocalVar(x; v1), LocalVar(y; v2).
};
query p select (r, v) from LocalVar(r; v) |> println
Note the careful use of ;
to designate lattice
semantics.
Using Lattice Semantics to Compute Shortest Paths
We can also use lattice semantics to compute shortest paths.
The key is to define our own new data type D
which is simple an Int32
with
forms a lattice with the reverse order of the integers (e.g. the smallest
element is Int32.maxValue()
).
pub enum D with Eq, Order, ToString {
case D(Int32)
}
instance PartialOrder[D] {
pub def lessEqual(x: D, y: D): Bool =
let D(n1) = x;
let D(n2) = y;
n1 >= n2 // Note: Order reversed.
}
instance LowerBound[D] {
// Note: Because the order is reversed, the largest value is the smallest.
pub def minValue(): D = D(Int32.maxValue())
}
instance UpperBound[D] {
// Note: Because the order is reversed, the smallest value is the largest.
pub def maxValue(): D = D(Int32.minValue())
}
instance JoinLattice[D] {
pub def leastUpperBound(x: D, y: D): D =
let D(n1) = x;
let D(n2) = y;
D(Int32.min(n1, n2)) // Note: Order reversed.
}
instance MeetLattice[D] {
pub def greatestLowerBound(x: D, y: D): D =
let D(n1) = x;
let D(n2) = y;
D(Int32.max(n1, n2)) // Note: Order reversed.
}
def shortestPath(g: Set[(t, Int32, t)], o: t): Map[t, D] with Order[t] =
let db = inject g into Edge;
let pr = #{
Dist(o; D(0)).
Dist(y; add(d1 , D(d2))) :- Dist(x; d1), Edge(x, d2, y).
};
query db, pr select (x , d) from Dist(x; d) |> Vector.toMap
def add(x: D, y: D): D =
let D(n1) = x;
let D(n2) = y;
D(n1 + n2)
def main(): Unit \ IO =
let g = Set#{
("Aarhus", 200, "Flensburg"),
("Flensburg", 150, "Hamburg")
};
println(shortestPath(g, "Aarhus"))
Flix actually comes with a type like D
built-in. It's called Down
and simply
reverses the order on the underlying type. We can use it and write the program
as:
def shortestPaths(g: Set[(t, Int32, t)], o: t): Map[t, Down[Int32]] with Order[t] =
let db = inject g into Edge;
let pr = #{
Dist(o; Down(0)).
Dist(y; add(d1 , Down(d2))) :- Dist(x; d1), Edge(x, d2, y).
};
query db, pr select (x , d) from Dist(x; d) |> Vector.toMap
def add(x: Down[Int32], y: Down[Int32]): Down[Int32] =
let Down(n1) = x;
let Down(n2) = y;
Down(n1 + n2)
def main(): Unit \ IO =
let g = Set#{
("Aarhus", 200, "Flensburg"),
("Flensburg", 150, "Hamburg")
};
println(shortestPaths(g, "Aarhus"))
Interoperability with Java
Flix is Java Virtual Machine (JVM)-based programming language, hence:
- Flix programs compile to efficient JVM bytecode.
- Flix programs run on any Java Virtual Machine1.
- Flix programs can call Java code.
Flix supports most Java features necessary for interoperability:
- Creating objects from existing classes
- Calling methods on classes and objects
- Reading and writing fields on objects
- Anonymous extension of classes and interfaces
- Nested and inner classes
Thus Flix programs can reuse Java Class Library and have access to the Java ecosystem.
Flix and Java share the same base types, in particular:
Flix Type | Java Type |
---|---|
Bool | boolean |
Char | char |
Float32 | float |
Float64 | double |
Int8 | byte |
Int16 | short |
Int32 | int |
Int64 | long |
String | String |
In Flix primitive types are always unboxed.
Hence, to call a Java method that expects a java.lang.Integer
,
if you have a Flix Int32
, it must be boxed by calling java.lang.Integer.valueOf
.
Design Note: Unlike other programming languages that target the JVM, Flix does not aim to embed the Java type system within Flix. Instead, Flix sacrifices some convenience to stay true to its design goals. In particular, the Flix type system does not support sub-typing. Consequently, unlike in Java, a sub-type cannot be used where its super-type is expected. For example,
java.lang.String
is incompatible withjava.lang.Object
. Fortunately, this limitation can be overcome by using upcasts.
Flix currently targets Java 11. Once Project Loom is released, we will target that version.
Creating Objects
We can import the constructor of a Java class as a Flix function and use it to construct new objects.
For example:
import new java.io.File(String): ##java.io.File \ IO as newFile;
newFile("HelloWorld.txt")
Here we import the constructor of the java.io.File
class and give it the local name newFile
.
The newFile
function takes a string argument and
returns a fresh Java File
object.
Constructing a fresh object is impure, hence main
is marked as having the IO
effect.
When we import a constructor, we must specify the types of its formal parameters. This is required because Java supports constructor overloading (i.e. a class may have multiple constructors only distinguished by their formal parameters.)
For example, the java.io.File
class has another
constructor that takes two arguments: one for the parent
pathname and one for the child pathname.
We can use this constructor as follows:
import new java.io.File(String, String): ##java.io.File \ IO as newFile;
newFile("foo", "HelloWorld.txt")
Here the import describes that the constructor expects two
String
arguments.
Invoking Object Methods
We can use the import mechanism to invoke methods on objects.
For example:
import new java.io.File(String): ##java.io.File \ IO as newFile;
import java.io.File.exists(): Bool \ IO as fileExists;
let f = newFile("HelloWorld.txt");
fileExists(f)
Here we import the java.io.File.exists
method under the name fileExists
.
If the Java method name is a legal Flix name and we want to reuse it,
we can also import the method without an as
clause. For example:
import new java.io.File(String): ##java.io.File \ IO as newFile;
import java.io.File.exists(): Bool \ IO;
let f = newFile("HelloWorld.txt");
exists(f)
Here we import the method under the name exists
.
When a Java method is imported, we must annotate it with its effect.
Most commonly, a Java method has a side-effect (such as deleting a file),
and hence must be annotated with the IO
effect.
In rare cases where a method is pure, we can import it as such by
writing the empty effect set: {}
. For example:
import java.lang.String.startsWith(String): Bool \ {};
startsWith("Hello World", "Hello")
And as another example:
import java.lang.String.charAt(Int32): Char \ {};
charAt("Hello World", 2)
Type signatures should use Flix type names and not
Java type names for primitive types.
For example, if a Java method takes a Double
its
signature should use the Flix type Float64
.
Similarly, if a Java method takes a Boolean
its
signature should use the Flix type Bool
.
This goes for return types, too.
Invoking Static Methods
We can invoke a static method by writing the
static
keyword after import:
import static java.lang.String.valueOf(Bool): String \ {};
valueOf(true)
Reading and Writing Fields
We can read and write fields by importing functions that serve as "getters" and "setters".
Assume we have the class:
class TestClass {
boolean boolField = true;
}
Then here is how we can access the boolField
:
import new flix.test.TestClass(): ##flix.test.TestClass \ IO as newObject;
import get flix.test.TestClass.boolField: Bool \ IO as getField;
let o = newObject();
getField(o)
Here we import the (default, empty) constructor of TestClass
as newObject
.
Next, we import the field boolField
as the function getField
. We use
newObject
to construct a fresh object and we call getField
on it to
obtain the value of o.boolField
.
Writing a field of an object is similar:
import new flix.test.TestClass(): ##flix.test.TestClass \ IO as newObject;
import get flix.test.TestClass.boolField: Bool \ IO as getField;
import set flix.test.TestClass.boolField: Unit \ IO as setField;
let o = newObject();
setField(o, false);
getField(o)
Here we import both a "getter" and "setter" for the boolField
field.
Reading and Writing Static Fields
Reading or writing static fields is similar to reading or writing object fields. For example:
import static get java.lang.Integer.MIN_VALUE: Int32 \ IO as getMinValue;
getMinValue()
The only difference is to write the
static
keyword to indicate that the reference is to
a static field.
Classes and Interfaces
Flix allows us to create objects that extend a Java class or implements a Java interface.
This feature is conceptually similar to Java's Anonymous Classes: We can define an (unnamed class) which implements an interface or extends a class and create an object of that class. All in one expression.
For example, we can create an object that implements the java.lang.Runnable
interface:
import java.lang.Runnable
def newRunnable(): Runnable \ IO = new Runnable {
def run(_this: Runnable): Unit \ IO =
println("I am running!")
}
Every time we call newRunnable
we get a fresh object that implements java.lang.Runnable
.
Note: The implicit
this
argument is always passed as the first argument in a new expression.
As another example, we can create an object that implements the java.io.Closeable
interface:
import java.io.Closeable
def newClosable(): Closeable \ IO = new Closeable {
def close(_this: Closeable): Unit \ IO =
println("I am closing!")
}
We can also extend classes. For example, we can create a
java.lang.Object
where we override the hashCode
and toString
methods:
def newObject(): Object \ IO = new Object {
def hashCode(_this: Object): Int32 = 42
def toString(_this: Object): String = "Hello World!"
}
Nested and Inner Classes
Java supports two different types of nested class: static nested classes and inner classes:
class OuterClass {
...
class InnerClass {
...
}
static class StaticNestedClass {
...
}
}
Although these appear superficially similar, they provide very different functionality.
Flix supports static nested classes, but does not yet support inner classes. To reference a static nested class, use a $
instead of .
in the class name, for example java.util.Locale$Builder
.
Exceptions
In Flix, all error handling should be done using the Result[e, t]
type.
However, for interoperability with Java, Flix also has a classic try-catch
mechanism.
For example, we can write:
///
/// Returns `true` if the given file `f` exists.
///
pub def exists(f: String): Result[String, Bool] \ IO =
try {
import new java.io.File(String): ##java.io.File \ IO as newFile;
import java.io.File.exists(): Bool \ IO;
Ok(exists(newFile(f)))
} catch {
case ex: ##java.io.IOException =>
import java.lang.Throwable.getMessage(): String \ IO;
Err(getMessage(ex))
}
Here we import the File
constructor as newFile
and the File.exists
method
as exists
. We then call the methods and catch the IOException
.
Note: Flix programs should not rely on the exception mechanism. Instead, we should guard all call to Java code that might throw exceptions close to their call site and turn these exceptions into
Result
s.
Structured Concurrency and Exceptions
Flix supports structured concurrency. This means that (1) threads cannot outlive the lifetime of their region and (2) that exceptions thrown in sub-threads are propagated to the thread of the region.
For example, given the program:
def main(): Unit \ IO =
region rc {
spawn f() @ rc;
spawn g() @ rc
};
println("Done")
where f
and g
are some functions. If f
or g
were to throw an unhandled
exception then that exception would be caught and rethrown inside the main
thread. This means that we cannot successfully leave the scope of rc
unless
f
and g
terminated and did not throw any unhandled exceptions.
Java Collections
Flix has support for conversion to and from Java collections.
Flix to Java
The following functions convert Flix collections to Java collections:
///
/// Lists
///
def toList(ma: m[a]): ##java.util.List \ IO with Foldable[m]
def toArrayList(ma: m[a]): ##java.util.ArrayList \ IO with Foldable[m]
def toLinkedList(ma: m[a]): ##java.util.LinkedList \ IO with Foldable[m]
///
/// Sets
///
def toSet(ma: m[a]): ##java.util.Set \ IO with Order[a], Foldable[m]
def toTreeSet(ma: m[a]): ##java.util.TreeSet \ IO with Order[a], Foldable[m]
///
/// Maps
///
def toMap(m: Map[k, v]): ##java.util.Map \ IO with Order[k]
def toTreeMap(m: Map[k, v]): ##java.util.TreeMap \ IO with Order[k]
Each function constructs a new collection and copies all its elements into it. Hence each operation takes at least linear time. The upshot is that the result is a normal Java collection (which can be modified).
Java to Flix
The following functions convert Java collections to Flix collections:
/// Lists
def fromList(l: ##java.util.List): List[a]
/// Sets
def fromSet(l: ##java.util.Set): Set[a] with Order[a]
/// Maps
def fromMap(m: ##java.util.Map): Map[k, v] with Order[k]
Each function constructs a new Flix collection from a Java Collection. Hence
each operation takes at least linear time. Note that for Set
and Map
, the
Flix collections use the Order[a]
instance defined on a
. This may not be the
same ordering as used by Java. Thus one has to be careful.
Wrapping Flix Collections
TBD.
Primitive Values
Warning: Converting Flix and/or Java collections with primitive values requires extra care. In particular, values must be manually boxed or unboxed before any conversion.
Everyday Programming
In this chapter we cover some everyday programming features:
- The signature of the
main
function. - How to print to standard out and standard error.
- How to use string interpolation.
- How to use anonymous and named holes for incomplete programs.
- How to use type ascriptions to explicitly provide some types to the compiler.
The Main Function
The entry point of any Flix program is the main
function which must have the
signature:
def main(): Unit \ IO
That is, the main
function:
- must return
Unit
, and - must be marked as effectful (i.e. have the effect annotation
\ IO
).
The signature of main
does not specify any arguments, but the command line
arguments passed to the program can be accessed by calling
Environment.getArgs()
:
def main(): Unit \ IO =
let args = Environment.getArgs();
...
Flix requires main
to have the IO
effect. If main was pure there would be no
reason to run the program. Typically the effectful requirement is satisfied
because main
prints to the console or has another side-effect.
Printing to Standard Out
The Flix Prelude defines the println
function which prints to standard out.
For example:
println("Hello World")
The println
function can print any value whose type implements ToString
type
class and consequently can be converted to a String
. For example:
let o = Some(123);
let l = 1 :: 2 :: 3 :: Nil;
println(o);
println(l)
The println
function is rightfully effectful, hence it cannot be called from a
pure function. To debug a pure function, use the builtin debugging
facilities.
The Console Module
The Console
module defines additional functions for reading from or writing to
the terminal:
mod Console {
def print(x: a): Unit \ IO with ToString[a]
def println(x: a): Unit \ IO with ToString[a]
def readLine(): Result[String, String] \ IO Impure
}
String Interpolation
Flix strings support interpolation. Inside a string, the form "${e}"
evaluates
e
to a value and converts it to a string using the ToString
type class. For
example:
let fstName = "Lucky";
let lstName = "Luke";
"Hello Mr. ${lstName}. Do you feel ${fstName}, punk?"
String interpolation works for any type that implements a ToString
instance.
For example:
let i = 123;
let o = Some(123);
let l = 1 :: 2 :: 3 :: Nil;
"i = ${i}, o = ${o}, l = ${l}"
String interpolations may contain arbitrary expressions. For example:
let x = 1;
let y = 2;
"${x + y + 1}"
String interpolation is the preferred way to concatenate two strings:
let x = "Hello";
let y = "World";
"${x}${y}" // equivalent to x + y
String interpolation is the preferred way to convert a value to a string:
let o = Some(123);
"${o}"
which is equivalent to an explicit use of the toString
function from the
ToString
type class:
ToString.toString(o)
String interpolators may nest, but this is discouraged.
Tail Recursion
In Flix, and in functional programming in general, iteration is expressed through recursion.
For example, if we want to determine if a list contains an element, we can write a recursive function:
def memberOf(x: a, l: List[a]): Bool with Eq[a] =
match l {
case Nil => false
case y :: ys => if (x == y) true else memberOf(x, ys)
}
The memberOf
function pattern matches on the list l
. If it is empty then it
returns false
. Otherwise, we have an element y
and the rest of the list is
ys
. If x == y
then we have found the element and we return true
. Otherwise
we recurse on the rest of the list ys
.
The recursive call to memberOf
is in tail position, i.e. it is the last
thing to happen in the memberOf
function. This has two important benefits: (a)
the Flix compiler is able to rewrite memberOf
to use an ordinary loop (which
is more efficient than a function call) and more importantly (b) a call to
memberOf
cannot overflow the stack, because the call stack never increases
in height.
Tip: Flix has support for full tail call elimination which means that recursive calls in tail position never increase the stack height and hence cannot cause the stack to overflow!
We remark that Flix has full tail call elimination, not just tail call optimization. This means that the following program compiles and runs successfully:
def isOdd(n: Int32): Bool =
if (n == 0) false else isEvn(n - 1)
def isEvn(n: Int32): Bool =
if (n == 0) true else isOdd(n - 1)
def main(): Unit \ IO =
isOdd(12345) |> println
which is not the case in many other programming languages.
Non-Tail Calls and StackOverflows
While the Flix compiler guarantees that tail calls cannot overflow the stack, the same is not true for function calls in non-tail positions.
For example, the following implementation of the factorial function overflows the call stack:
def factorial(n: Int32): Int32 = match n {
case 0 => 1
case _ => n * factorial(n - 1)
}
as this program shows:
def main(): Unit \ IO =
println(factorial(1_000_000))
which when compiled and run produces:
java : Exception in thread "main" java.lang.StackOverflowError
at Cont%Int32.unwind(Cont%Int32)
at Def%factorial.invoke(Unknown Source)
at Cont%Int32.unwind(Cont%Int32)
at Def%factorial.invoke(Unknown Source)
at Cont%Int32.unwind(Cont%Int32)
... many more frames ...
A well-known technique is to rewrite factorial
to use an accumulator:
def factorial(n: Int32): Int32 =
def visit(x, acc) = match x {
case 0 => acc
case _ => visit(x - 1, x * acc)
};
visit(n, 1)
Here the visit
function is tail recursive, hence it cannot overflow the stack.
Anonymous and Named Holes
During development, Flix encourages the use of holes for incomplete code. For example:
def sum(x: Int32, y: Int32): Int32 = ???
The triple question marks ???
represents an anonymous hole and can be used
wherever an expression is expected. In the above code, ???
represents a
missing function body, but it can also be used inside an expression. For
example:
def length(l: List[a]): Int32 = match l {
case Nil => 0
case x :: xs => ???
}
When a program has multiple holes, it can be useful to name them. For example:
def length(l: List[a]): Int32 = match l {
case Nil => ?base
case x :: xs => ?step
}
Flix requires that each named hole has a unique name.
Variable Holes and Auto-Completion
Flix has support for a special variable hole which enables type-driven auto-completion suggestions. For example, in the program:
def main(): Unit \ IO =
let s: String = "Hello World";
let n: Int32 = s?;
println("The length of ${s} is ${n}!")
If we place the cursor on s?
and ask for auto-completion suggestions, Flix
will suggest:
String.length(s: String): Int32
String.countSubstring(substr: {substr: String}, s: String): Int32
String.levenshtein(s: String, t: String): Int32
- ...
since these are functions that can convert a String
to an Int32
.
As another example, in the program:
def main(): Unit \ IO =
let l: List[Int32] = List.range(1, 10);
let n: Int32 = l?;
println("The value of `n` is ${n + 0}.")
If we place the cursor on l?
, Flix will suggest:
List.product(l: List[Int32]): Int32
List.sum(l: List[Int32]): Int32
List.fold(l: List[Int32]): Int32
List.length(l: List[Int32]): Int32
List.count(f: a -> Bool \ ef, l: List[a]): a \ ef
- ...
since these are functions that can convert a List[Int32]
to an Int32
.
Type Ascriptions
While Flix supports local type inference, it can sometimes be useful to annotate an expression or a let-binding with its type. We call such annotations type ascriptions. A type ascription cannot change the type of an expression nor can it be used to violate type safety.
A type ascription can be placed after an expression:
("Hello" :: "World" :: Nil) : List[String]
and it can also be placed on a let-binding:
let l: List[String] = "Hello" :: "World" :: Nil
Kind Ascriptions
Flix also supports kind ascriptions. Where a type ascription specifies the type of an expression, a kind ascription specifies the kind of a type.
We can use kind ascriptions on type parameters. For example:
def fst1[a: Type, b: Type](p: (a, b)): a = let (x, _) = p; x
Here we have specified that the kind of the two type parameters a
and b
is
Type
. We will typically never have to specify such kinds since they can
inferred.
We can also provide kind ascriptions on algebraic data types:
enum A[t: Type] {
case A(t, t)
}
and on type classes:
class MyClass[t: Type] {
// ...
}
We typically only use kind ascriptions for higher-kinded types.
Redundancy
The Flix compiler aggressively rejects programs that contain unused elements. The idea is to help programmers avoid subtle 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: local variables that are declared, but never used.
- Shadowed local variables: local variables that shadow other local variables.
- Useless expressions: pure expressions whose values are discarded.
- Must use values: expressions whose values are unused but their type is marked as
@MustUse
.
Unused Local Variables
Flix rejects programs with unused variables.
For example, the following program is rejected:
def main(): Unit \ IO =
let x = 123;
let y = 456;
println("The sum is ${x + x}")
with the message:
❌ -- Redundancy Error -------------------------------------------------- Main.flix
>> Unused local variable 'y'. The variable is not referenced within its scope.
3 | let y = 456;
^
unused local variable.
Unused local variables can be prefixed by an underscore _
to supress the error.
For example, if we replace y
by _y
the above program compiles:
def main(): Unit \ IO =
let x = 123;
let _y = 456; // OK
println("The sum is ${x + x}")
Shadowed Local Variables
Flix rejects programs with shadowed variables.
For example, the following program is rejected:
def main(): Unit \ IO =
let x = 123;
let x = 456;
println("The value of x is ${x}.")
with the message:
❌ -- Redundancy Error -------------------------------------------------- Main.flix
>> Shadowed variable 'x'.
3 | let x = 456;
^
shadowing variable.
The shadowed variable was declared here:
2 | let x = 123;
^
shadowed variable.
Useless Expressions
Flix rejects programs with pure expressions whose results are discarded.
For example, the following program is rejected:
def main(): Unit \ IO =
123 + 456;
println("Hello World!")
with the message:
❌ -- Redundancy Error -------------------------------------------------- Main.flix
>> Useless expression: It has no side-effect(s) and its result is discarded.
2 | 123 + 456;
^^^^^^^^^
useless expression.
The expression has type 'Int32'
An expression that has no side-effect and whose result is unused is suspicious, since it could just be removed from the program without changing its meaning.
Must Use Values
Flix rejects programs with expressions whose values are discarded but where
their type is marked with the @MustUse
annotation. Function types, and the
Result
and Validation
types from the Flix Standard Library are marked as
@MustUse
.
For example, the following program is rejected:
def main(): Unit \ IO =
File.creationTime("foo.txt");
println("Hello World!")
with the message:
❌ -- Redundancy Error -------------------------------------------------- Main.flix
>> Unused value but its type is marked as @MustUse.
2 | File.creationTime("foo.txt");
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
unused value.
The expression has type 'Result[String, Int64]'
Even though File.creationTime
has a side-effects, we should probably be using the result Result[String, Int64]
.
At least to ensure that the operation was successful.
If the result of an impure expression is truly not needed, then the discard
expression can be used:
def main(): Unit \ IO =
discard File.creationTime("foo.txt");
println("Hello World!")
which permits a @MustUse
value to be thrown away as long as the expression is non-pure.
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
fuction:
def debug(x: a): a
The debug
"function" isn't really a function; rather its internal compiler
magic that allows you to print any value while fooling the type and effect
system into believing that it is still pure. Using the debug
function this
program:
def sum(x: Int32, y: Int32): Int32 =
debug(x);
debug(y);
x + y
Now compiles and runs.
The debug
function returns its argument. Hence its convenient to use in many
situations.
For example, we can write:
def sum(x: Int32, y: Int32): Int32 = debug(x + y)
to print the value of x + y
and return it.
We can also use it inside e.g. a for-yield
expression:
for(i <- List.range(0, 10);
j <- debug(List.range(i, 10)))
yield (i, j)
Or in a pipeline:
List.range(1, 100) |>
List.map(x -> debug(x + 1)) |>
List.filter(x -> debug(x > 5))
Debug Format
The debug
expression (and its variants) do not use the ToString
type
class. Instead they print the internal Flix representation of the given value.
For example, the expression:
debug(1 :: 2 :: Nil)
prints:
Cons(1, Cons(2, Nil))
We can also print values that do not have a ToString
instance:
debug(x -> x + 123)
prints:
Int32 -> Int32
We can always obtain the ToString
representation by using an interpolated
string. For example:
debug("${x}")
Debug Variants
The debug
function comes in three variants:
debug
: Prints its argument.debug!
: Prints its argument and source location.debug!!
: Prints its argument, source location, and source code.
The following program:
def main(): Unit =
debug("A message");
debug!("Another message");
debug!!("A third message");
()
prints:
"A message"
[C:\tmp\flix\Main.flix:3] "Another message"
[C:\tmp\flix\Main.flix:4] A third message = "A third message"
The third debug!!
variant is intended to be used in situations like:
let x = 123;
let y = 456;
debug!!(x + y)
where it prints:
[C:\tmp\flix\Main.flix:3] x + y = 579
Note: The
debug
expression should not be used in production code.
Warning: The Flix compiler treats the
debug
expression as pure, hence under certain circumstances the compiler may reorder or entirely remove a use ofdebug
.
Tools
This chapter covers the tooling which Flix ships with, including:
- A fully-featured Visual Studio Code extension.
- A package manager.
- A built-in test framework.
Visual Studio Code Extension
Flix comes with a fully-featured Visual Studio Code Extension:
The Flix extension uses the real Flix compiler hence all information (e.g. error messages) are always 1:1 with the real Flix programming language.
Flix also comes with an (optional) Visual Studio Code color theme called "Flixify Dark".
Features
-
Semantic Syntax Highlighting
- Code highlighting for *.flix files. This work best with the official vscode theme.
-
Diagnostics
- Compiler error messages.
-
Auto-complete
- Auto-complete as you type.
- Auto-completion is context aware.
- Type-directed completion of program holes.
-
Snippets
- Auto-complete common code constructs.
-
Inlay Hints
- Shows inline type information.
-
Type and Effect Hovers
- Hover over any expression to see its type and effect.
- Hover over any local variable or formal parameter to see its type.
- Hover over any function to see its type signature and documentation.
-
Jump to Definition
- Jump to the definition of any function.
- Jump to the definition of any local variable or formal parameter.
- Jump to the definition of any enum case.
-
Find References
- Find all references to a function.
- Find all references to a local variable or formal parameter.
- Find all references to an enum case.
- Find all implementations of a type class.
-
Symbols
- List all document symbols.
- List all workspace symbols.
-
Rename
- Rename local variables or formal parameters.
- Rename functions.
-
Code Lenses
- Run
main
from within the editor. - Run tests from within the editor.
- Run
-
Highlight
- Highlights semantically related symbols.
-
Semantic Tokens
- Additional code highlighting hints provided by the compiler.
Known Limitations
-
There is a known issue with PowerShell and using file names that contain special characters. We recommend that Flix source files are given only ASCII names.
-
The extension assumes that you are working in "Workspace Mode", i.e. you must have a folder open which contains your Flix source code.
-
Upon startup, the Flix compiler has to load the entire Flix standard library into its caches which takes a few seconds.
Test Framework
Flix comes with a simple built-in test framework.
A test is a Flix function marked with the @Test
annotation. That's it.
A test function can return any value. If it returns a Bool then true
is interpreted as success and false
as failure. Any non-Boolean value is interpreted as success.
The Assert.eq
function can be used to test for equality between two values that implement the Eq
and ToString
type classes. The advantage of Assert.eq
(over ==
) is that it will print the two values if they are unequal. The Assert.eq
function should not be used outside of unit tests.
Here is an example:
def add(x: Int32, y: Int32): Int32 = x + y
@Test
def testAdd01(): Bool = 0 == add(0, 0)
@Test
def testAdd02(): Bool = Assert.eq(1, add(0, 1))
@Test
def testAdd03(): Bool = Assert.eq(2, add(1, 1))
@Test
def testAdd04(): Bool = Assert.eq(4, add(1, 2))
@Test @Skip
def testAdd05(): Bool = Assert.eq(8, add(2, 3))
Running the tests (e.g. with the command test
) yields:
Running 5 tests...
PASS testAdd01 237,3us
PASS testAdd02 21,1us
PASS testAdd03 10,3us
FAIL testAdd04 (Assertion Error)
SKIP testAdd05 (SKIPPED)
--------------------------------------------------------------------------------
FAIL testAdd04
Assertion Error
Expected: 4
Actual: 3
dev.flix.runtime.HoleError: Hole '?Assert.assertEq' at Assert.flix:32:13
at Assert.Def%eq%174731.invoke(Unknown Source)
at Cont%Bool.unwind(Cont%Bool)
at Ns.m_testAdd04(Unknown Source)
at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:77)
at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.base/java.lang.reflect.Method.invoke(Method.java:568)
at ca.uwaterloo.flix.language.phase.jvm.JvmBackend$.$anonfun$link$1(JvmBackend.scala:286)
at ca.uwaterloo.flix.language.phase.jvm.JvmBackend$.$anonfun$getCompiledDefs$2(JvmBackend.scala:259)
at ca.uwaterloo.flix.tools.Tester$TestRunner.runTest(Tester.scala:182)
at ca.uwaterloo.flix.tools.Tester$TestRunner.$anonfun$run$7(Tester.scala:153)
at ca.uwaterloo.flix.tools.Tester$TestRunner.$anonfun$run$7$adapted(Tester.scala:152)
at scala.collection.immutable.Vector.foreach(Vector.scala:1856)
at ca.uwaterloo.flix.tools.Tester$TestRunner.run(Tester.scala:152)
--------------------------------------------------------------------------------
Passed: 3, Failed: 1. Skipped: 1. Elapsed: 3,0ms.
Build and Package Management
Flix comes with a build system and package manager. The build system makes it simple to compile a Flix program to a collection of Java classes and to build a fat JAR. The package manager makes it possible to create Flix packages, publish them on GitHub, and depend on them via a manifest file. The package manager also makes it possible to depend on Java JAR-artifacts published on Maven.
The Flix build system supports the following commands:
init
: creates a new Flix project in the current directory.check
: checks the current project for compiler errors.build
: builds the current project (i.e. emits Java bytecode).build-jar
: builds a jar-file from the current project.build-pkg
: builds a fpkg-file from the current project.run
: runs main in current project.test
: runs all tests in the current project.
All commands can be executed from the command line, from the REPL, and from VSCode.
All commands, except build-pkg
work without a manifest file. To build,
package, and publish a Flix project, a flix.toml
manifest is required. The
init
command will create an empty skeleton flix.toml
manifest, if not
already present.
Project Structure
Flix scans for source files in the paths *.flix
, src/**.flix,
, and
test/**.flix
.
Flix scans for Flix packages and JARs in the paths lib/**.fpkg
and
lib/**.jhar
.
Build Management
We now discuss the build commands. Each command can be executed from the command line, from the REPL, and from VSCode.
Creating a New Project
We can create a new project, inside a directory, with the init
command.
This will create the default Flix project structure:
.
├── flix.toml
├── LICENSE.md
├── README.md
├── src
│ └── Main.flix
└── test
└── TestMain.flix
2 directories, 6 files
The most relevant files are flix.toml
, src/Main.flix
and
test/TestMain.flix
.
The flix.toml
manifest file is discussed in the next section.
Tip: The
init
command is safe to use; it will only create files that do not already exist.
Checking a Project
We can check a project for compiler errors with the check
command. During
development, the check
command is preferable to the build
command because it
skips code generation (and hence is significantly faster).
Building a Project
We can compile a project with the build
command. Running the build
command
will compile the entire project and emit bytecode, i.e. compiled Java classes,
to the build
directory.
Flix has no clean
command. Deleting the build
directory serves the same
purpose.
Building a JAR-file
We can compile a project to a fat JAR-file with the build-jar
command. The
build-jar
command emits a artifact/project.jar
file. If there is main
function, we can run it:
$ java -jar artifact/project.jar
The JAR-file contains all class files from the build
directory. The built JAR
may depend on external JARs, if the project, or one of its dependencies, depends
on JAR-files.
Note: The project must be compiled with
build
before runningbuild-jar
.
Building a Flix Project
We can bundle a project into a Flix package file (fpkg) with the build-pkg
command. Running the build-pkg
command emits a artifact/project.fpkg
file.
A Flix package file (fpkg) is essentially zip-file of the project source code. A
Flix package, together with its flix.toml
manifest, can be published on
GitHub.
Running a Project
We do not have to build a JAR-file to run a project, we can simply use the run
command which will compile and run the main entry point.
Testing a Project
We can use the test
command to run all test cases in a project. Flix will
collect all functions marked with @Test
, execute them, and print a summary of
the results:
Running 1 tests...
PASS test01 1,1ms
Passed: 1, Failed: 0. Skipped: 0. Elapsed: 3,9ms.
Package Management
Every non-trivial Flix project should have a flix.toml
manifest. The manifest
contains information about the project and its dependencies.
A minimal manifest is of the form:
[package]
name = "hello-library"
description = "A simple library"
version = "0.1.0"
flix = "0.35.0"
license = "Apache-2.0"
authors = ["John Doe <john@example.com>"]
Note: The
flix
field is not yet used, but it will be used in the future.
Adding Flix Dependencies
We can add dependencies on other Flix packages to the manifest:
[dependencies]
"github:flix/museum" = "1.4.0"
"github:magnus-madsen/helloworld" = "1.3.0"
Note: Flix requires version numbers to follow SemVer.
Adding Maven Dependencies
We can also add dependencies on Maven packages to the manifest:
[mvn-dependencies]
"org.junit.jupiter:junit-jupiter-api" = "5.9.2"
Understanding Dependency Resolution
Flix dependency resolution works as follows:
- Flix reads
flix.toml
and computes the transitive set of Flix package dependencies. - Flix downloads all of these Flix packages.
- 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 onorg.apache.commons:commons-lang3
Publishing a Package on GitHub
Creating and publish a package on GitHub is straightforward:
- Check that you have a
flix.toml
manifest (if not create one withinit
). - Check that the version field in
flix.toml
is correct. - Run
check
andtest
to ensure that everything looks alright. - Run
build-pkg
. Check that theartifact
directory is populated. - Go to the repository on GitHub:
- Click "Releases".
- Click "Draft new release".
- Enter a tag of the form
v1.2.3
(i.e. use SemVer). - Upload the
package.fpkg
andflix.toml
from theartifact
directory.
Tip: See the Museum Project for an example of a package that has been published on GitHub.
Advanced Features
In this chapter, we discuss some advanced features of Flix, including:
Checked 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
andchecked_ecast
expressions are guaranteed to be safe. The Flix compiler will check at compile-time that every checked cast cannot go wrong.
Checked Type Casts
The following program:
def main(): Unit =
let s = "Hello World";
let o: ##java.lang.Object = s;
()
does not compile:
❌ -- Type Error --------------------------------------------------
>> Expected type: 'Object' but found type: 'String'.
4 | let o: ##java.lang.Object = s;
^
expression has unexpected type.
because in Flix the String
type is not a subtype of Object
.
We can use a checked type cast to safely upcast from String
to Object
:
def main(): Unit =
let s = "Hello World";
let o: ##java.lang.Object = checked_cast(s);
()
We can use the checked_cast
construct to safely upcast any Java type to one of
its super-types:
let _: ##java.lang.Object = checked_cast("Hello World");
let _: ##java.lang.CharSequence = checked_cast("Hello World");
let _: ##java.io.Serializable = checked_cast("Hello World");
let _: ##java.lang.Object = checked_cast(null);
let _: ##java.lang.String = checked_cast(null);
Checked Effect Casts
The following program:
def hof(f: Int32 -> Int32 \ IO): Int32 \ IO = f(42)
def main(): Int32 \ IO =
hof(x -> x + 1)
does not compile:
❌ -- Type Error --------------------------------------------------
>> Expected argument of type 'Int32 -> Int32 \ IO', but got 'Int32 -> Int32'.
4 | hof(x -> x + 1)
^^^^^^^^^^
expected: 'Int32 -> Int32 & Impure \ IO'
The function 'hof' expects its 1st argument to be of type 'Int32 -> Int32 \ IO'.
Expected: Int32 -> Int32 & Impure \ IO
Actual: Int32 -> Int32
because in Flix a pure function is not a subtype of an impure function.
Specifically, the hof
requires a function with the IO
effect, but we are
passing in a pure function.
We can use a checked effect cast to safely upcast upcast a pure expression to an impure expression:
def main(): Int32 \ IO =
hof(x -> checked_ecast(x + 1))
The checked_ecast
construct allows us to pretend that x + 1
has the IO
effect.
Note: In Flix – as a general rule – higher-order functions should not require their function arguments to have a specific effect. Instead they should be effect polymorphic.
Function Types
Neither the checked_cast
nor the checked_ecast
constructs work on function types.
For example, the following does not work:
let f: Unit -> ##java.lang.Object = checked_cast(() -> "Hello World")
because it tries to cast the function type Unit -> String
to String -> Object
.
Instead, we should write:
let f: Unit -> ##java.lang.Object = (() -> checked_cast("Hello World"))
because it directly casts String
to Object
.
Unchecked Type and Effect Casts
Flix also supports unchecked type and effect casts.
Unchecked Type Casts
An unchecked type cast instructs the compiler that an expression has a specific type.
Warning️️: Type casts are very dangerous and should be used with utmost caution!
Flix programmers should normally never need to use an unchecked type cast.
Example: Safe Cast to a Super-Type
The expression below casts a String
to an Object
:
unchecked_cast("Hello World" as ##java.lang.Object)
Note: It is safer to use the checked_cast
expression.
Example: Safe Cast from Null to an Object-Type
The expression below casts the null
value (of type Null
) to String
:
unchecked_cast(null as ##java.lang.String)
Note: It is safer to use the checked_cast
expression.
Example: Unsafe Type Cast
The expression below contains an illegal cast and triggers a
ClassCastException
at runtime:
unchecked_cast((123, 456) as ##java.lang.Integer)
Effect Casts
An unchecked effect cast instructs the compiler that an expression has a specific effect.
Warning️️: Effect casts are extremely dangerous and should be used with extreme caution!
Flix programmers should normally never need to use an unchecked effect cast.
Example: Unsafe Effect Cast
We can pretend an impure expression is pure:
def main(): Unit =
unchecked_cast(println("Hello World") as _ \ {})
Here we call println
which has the IO
effect and then we explicitly, and
unsafely, cast away the effect, pretending that the expression is pure.
Warning: Never cast effectful expressions to pure. You have been warned.
bug!
and unreachable!
Flix supports two special "functions": bug!
and
unreachable!
that can be used to indicate when an
internal program invariant is broken and execute
should abort.
For example:
match o {
case Some(x) => ...
case None => bug!("The value of `o` cannot be empty.")
}
As another example:
match k {
case n if n == 0 => ...
case n if n >= 0 => ...
case n if n <= 0 => ...
case n => unreachable!()
}
Use of bug!
and unreachable!
should be avoided
whenever possible.
Type Match
Flix supports a type match construct that enables compile-time pattern matching on the type of a polymorphic value.
For example, we can write a function that inspects the type of its argument:
def inspect(x: a): String = typematch x {
case _: Int32 => "x is an Int32"
case _: String => "x is a String"
case _: _ => "x is neither an Int32 nor a String"
}
def main(): Unit \ IO =
println(inspect(12345));
println(inspect("abc"));
println(inspect(false))
Here the inspect
function pattern matches on the type of the formal parameter
x
using the typematch
construct. For example, if the type of x
is an
Int32
then the function returns the string "x is an Int32"
and so forth.
The typematch
construct is eliminated at compile-time, hence there is no
runtime cost.
As the example shows, the typematch
construct always requires a default case.
This is because Flix has infinitely many types, and a typematch
cannot cover
all of them.
A type match can also inspect more complex types, as the following example shows:
def inspect(x: a): String = typematch x {
case _: List[Int32] => "x is a list of integers"
case _: List[String] => "x is a list of strings"
case _: _ => "x is something else"
}
def main(): Unit \ IO =
println(inspect(1 :: 2 :: 3 :: Nil));
println(inspect("abc" :: "def" :: Nil));
println(inspect(false))
We can also bind values with type match, as the following example shows:
def inspect(x: a): String = typematch x {
case i: Int32 => "${i * i}"
case s: String => String.toUpperCase(s)
case _: _ => "-"
}
def main(): Unit \ IO =
println(inspect(12345));
println(inspect("abc"));
println(inspect(false))
Warning: While type match is a powerful meta-programming construct, it should be sparingly and with great care.
A typical legitimate use case for type match is when we want to work around
limitations imposed by the JVM. For example, the Flix Standard Library use type
match to implement the Array.copyOfRange
function as shown below:
def copyOfRange(_: Region[r2], b: Int32, e: Int32, a: Array[a, r1]): ... =
typematch a {
case arr: Array[Int16, r1] =>
import static java.util.Arrays.copyOfRange(Array[Int16, r1], Int32, Int32): ...
...
case arr: Array[Int32, r1] =>
import static java.util.Arrays.copyOfRange(Array[Int32, r1], Int32, Int32): ...
...
// ... additional cases ...
}
Here type match allows us to call the right overloaded version of
java.util.Arrays.copyOfRange
. Thus Flix programmers can use our version of
copyOfRange
(i.e., Array.copyOfRange
) while underneath the hood, we always
call the most efficient Java version.
Purity Reflection
Note: This is an advanced feature and should only be used by experts.
Purity reflection enables higher-order functions to inspect the purity of their function arguments.
This allows us to write functions that use selective lazy and/or parallel evaluation.
For example, here is the implementation of Set.count
:
@ParallelWhenPure
pub def count(f: a -> Bool \ ef, s: Set[a]): Int32 \ ef =
typematch f {
case g: a -> Bool \ {} =>
let h = (k, _) -> g(k);
let Set(t) = s;
RedBlackTree.parCount(threads() - 1, h, t)
case g: a -> Bool \ ef => foldLeft((b, k) -> if (g(k)) b + 1 else b, 0, s)
case _: _ => unreachable!()
}
Here the typematch
construct is used to reflect on the purity of f
:
- If
f
is pure then we evaluateSet.count
in parallel over the elements of the set. - If
f
is effectful then we use an ordinary (single-threaded) fold.
The advantage is that we get parallelism for free – if f
is pure.
Type-Level Programming
Note: This feature is experimental. Do not use in production.
This section assumes prior familiarity with type-level programming and phantom types.
Type-Level Booleans
A unique Flix feature is its support for type-level Boolean formulas. This
means true
and false
are types, but also that formulas such as x and (not y)
are types. A type-level Boolean formulas has kind Bool
. Two type-level
Boolean formulas are equal if the formulas are equivalent (i.e. have the same
truth tables). For example, the two types true
and x or not x
are the same
type.
While type-level Boolean formulas are not as expressive as general refinement types or dependent types they support complete type inference and parametric polymorphism. This means that they are very ergonomic to work with.
We can use type-level Boolean formulas to statically enforce program invariants.
We illustrate with a few examples:
Humans and Vampires
///
/// We can use a phantom type-level Boolean to model whether a person is alive
/// or is undead (i.e. a vampire).
///
enum Person[_isAlive: Bool] {
/// A person has a name, an age, and is modelled as a record.
case P({name = String, age = Int32})
}
///
/// We interpret the Boolean `true` is alive and the Boolean `false` as undead
/// (i.e. a vampire).
///
type alias Alive = true
type alias Undead = false
///
/// A person who is born is alive.
///
def born(name: String): Person[Alive] =
Person.P({name = name, age = 0})
///
/// A person who is alive and is bitten becomes a vampire.
///
/// Note that the type system enforces that an already undead (i.e. a vampire)
/// cannot be bitten again.
///
def bite(p: Person[Alive]): Person[Undead] = match p {
/// The implementation is not important; it simply restructs the person.
case Person.P(r) => Person.P(r)
}
///
/// Two persons can be married, but only if they are both alive or both undead.
///
/// (The church does not yet recognize human-vampire marriages.)
///
/// Note that the type system enforces that both arguments have the same type.
///
def marry(_p1: Person[isAlive], _p2: Person[isAlive]): Unit = ()
///
/// We can implement a more sophisticated version of born.
///
/// If two persons have a child then that child is a vampire if one of them is.
///
/// Note that here we use the type-level computation `isAlive1 and isAlive2`
/// to compute whether the result is alive or undead.
///
def offspring(p1: Person[isAlive1], p2: Person[isAlive2]): Person[isAlive1 and isAlive2] =
match (p1, p2) {
case (Person.P(r1), Person.P(r2)) =>
Person.P({name = "Spawn of ${r1.name} and ${r2.name}", age = 0})
}
///
/// A person can age-- no matter if they are alive or undead.
///
/// Note that this function preserves the `isAlive` parameter. That is, if a
/// person is alive they stay alive.
///
def birthday(p: Person[isAlive]): Person[isAlive] = match p {
case Person.P(r) => Person.P({name = r.name, age = r.age + 1})
}
We can now illustrate how the type system enforces certain invariants.
For example, the type system ensures that person cannot be bitten twice:
let p = birthday(bite(born("Dracula")));
bite(p);
If we compile this program then the Flix compiler emits a compiler error:
❌ -- Type Error --------------------------------------------------
>> Expected argument of type 'Person[true]', but got 'Person[false]'.
69 | bite(p);
^
expected: 'Person[true]'
The function 'bite' expects its 1st argument to be of type 'Person[true]'.
Here we have to recall that true
means Alive
and false
means Undead
.
Common Problems
- ToString is not defined on 'a'
- Records and Complex Instances
- Expected kind 'Bool or Effect' here, but kind 'Type' is used
ToString is not defined on 'a'
Given the program:
def main(): Unit \ IO =
let l = Nil;
println(l)
The Flix compiler reports:
❌ -- Type Error ---------------------
>> ToString is not defined on a. [...]
3 | println(l)
^^^^^^^^^^
missing ToString instance
The issue is that the empty list has the polymorphic type: List[a]
for any
a
. This means that Flix cannot select the appropriate ToString
type class
instance.
The solution is to specify the type of the empty list. For example, we can write:
def main(): Unit \ IO =
let l: List[Int32] = Nil;
println(l)
which solves the problem because Flix can find an instance of ToString
type
class for the concrete type List[Int32]
.
Records and Complex Instances
Given the program:
instance Eq[{fstName = String, lstName = String}]
The Flix compiler reports:
❌ -- Instance Error --------------------------------------------------
>> Complex instance type '{ fstName = String, lstName = String }' in 'Eq'.
1 | instance Eq[{fstName = String, lstName = String}]
^^
complex instance type
This is because, at least for the moment, it is not possible type define type class instances on records (or Datalog schema rows). This may change in the future. Until then, it is necessary to wrap the record in an algebraic data type. For example:
enum Person({fstName = String, lstName = String})
and then we can implement Eq
for the Person
type:
instance Eq[Person] {
pub def eq(x: Person, y: Person): Bool =
let Person(r1) = x;
let Person(r2) = y;
r1.fstName == r2.fstName and r1.lstName == r2.lstName
}
Expected kind 'Bool or Effect' here, but kind 'Type' is used
Given the program:
enum A[a, b, ef] {
case A(a -> b \ ef)
}
The Flix compiler reports:
❌ -- Kind Error -----------------------------------------------
>> Expected kind 'Bool or Effect' here, but kind 'Type' is used.
2 | case A(a -> b \ ef)
^^
unexpected kind.
Expected kind: Bool or Effect
Actual kind: Type
This is because Flix assumes every un-annotated type variable to have kind
Type
. However, in the above case a
and b
should have kind Type
, but ef
should have kind Bool
. We can make this explicit like so:
enum A[a: Type, b: Type, ef: Bool] {
case A(a -> b \ ef)
}
Glossary
Effect Polymorphic. A function whose effect(s) depend on the effect(s) of its function argument. See also higher-order function.
Higher-Order Function. A function that takes a function argument or returns a function.
Additional Information
More information about the Flix programming language can be found in:
- The research literature written by programming language researchers.
- A series of blog posts written by the community.
Getting Help
If you have a question or comment we are happy to help you out on our Gitter channel:
Reporting a Bug
If you encounter a bug, you can report it here:
https://github.com/flix/flix/issues
but first you may wish to talk to us on Gitter.
Research Literature
The following research papers cover specific aspects of Flix:
- The Principles of the Flix Programming Language
- Flix: A Meta Programming Language for Datalog
- Relational Nullable Types with Boolean Unification
- Fixpoints for the Masses: Programming with First-Class Datalog Constraints
- Polymorphic Types and Effects with Boolean Unification
- Implicit Parameters for Logic Programming
- Safe and Sound Program Analysis with Flix
- Tail Call Elimination and Data Representation for Functional Languages on the Java Virtual Machine
- From Datalog to Flix: A Declarative Language for Fixed Points on Lattices
- Programming a Dataflow Analysis in Flix
Blog Posts
A few people are writing about various aspects of Flix on their blogs:
Paul Butcher is writing a blog post series on Flix:
- An introduction to Datalog in Flix: Part 1
- An introduction to Datalog in Flix: Part 2
- An introduction to Datalog in Flix: Part 3
- An introduction to Datalog in Flix: Part 4
Susan Potter is writing a blog post series on Flix:
Magnus Madsen wrote a few blog posts on Flix during COVID:
- In Defense of Programming Languages
- Taming Impurity with Polymorphic Effects
- Naming Functional and Destructive Operations
- Redundancies as Compile-Time Errors
- Design Flaws in Flix
Magnus Madsen did an interview about Flix on the Happy Path Programming podcast:
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 (
A
…Z
,a
…z
,_
,!
).- e.g.
String
,ALL_UPPER
,Shriek!
- Can be used to name: namespaces, annotations, type classes, effects, predicates (within datalog), tags (within enums), types
- e.g.
- Lowercase name: An identifier that starts with aa lowercase letter followed by any number of uppercase and lowercase letters, underscore, and exclamation mark (
A
…Z
,a
…z
,_
,!
).- e.g.
anIdentifier
,x
,this_and_that
- Can be used to name: annotations, attributes (within datalog), functions, labels (within records), variables
- e.g.
- 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
- e.g.
- 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
- e.g.
- Operator name: An identifier of minimum length 2 consisting of any combination of
+
,-
,*
,<
,>
,=
,!
,&
,|
,^
, and$
.- e.g.
>==>
,<*>
- Can be used to name: functions
- e.g.
Note that greek letters, math symbols, and operator letters cannot be combined within a single identifier.
Reserved Identifiers
The following are reserved by Flix and cannot be redefined within user code:
!=
, **
, ..
, ::
, :=
, <-
, <=
, ==
, =>
, >=
, or
,
&&&
, <+>
, <<<
, <=>
, >>>
, ???
, ^^^
, and
, mod
, not
, rem
, |||
, ~~~
,
$DEFAULT$
, *
, +
, -
, /
, :
, <
,
>
, @
, Absent
, Bool
, Impure
, Nil
, Predicate
, Present
, Pure
,
Read
, RecordRow
, Region
, SchemaRow
, Type
, Write
, alias
, case
, catch
, chan
,
class
, def
, deref
, else
, enum
, false
, fix
, force
,
if
, import
, inline
, instance
, into
, lat
, law
, lawful
, lazy
, let
, match
,
namespace
, null
, opaque
, override
, pub
, ref
, region
, reify
,
reifyBool
, reifyEff
, reifyType
, rel
, sealed
, set
, spawn
, Static
, true
,
type
, use
, where
, with
, discard
, object
Precedence
- Unary operators (
+
,-
,~~~
, andnot
) - User-defined operators (including operators defined in the standard library such as
|>
) - Functions applied infix with backticks
- Composition (
<+>
) - Multiplicative (
**
,*
,/
,mod
, andrem
) - Additive (
+
and-
) - Shift (
<<<
and>>>
) - Comparison (
<=
,>=
,<
, and>
) - Equality (
==
,!=
, and<==>
) - Bitwise And (
&&&
) - Bitwise Xor (
^^^
) - Bitwise Or (
|||
) - Logical
and
- Logical
or
- Channel
<-