Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Introduction

The Lane Programming Language is a user-facing guide to Lane.

This book explains how to read, write, and understand Lane programs. Normative language rules are maintained in ../spec, and compiler implementation notes are maintained with the compiler.

Introduction to the Lane Language

Lane is a functional programming language.

Unlike many industrial programming languages, Lane never promises to run correctly on every common platform, and it never promises backward compatibility. The Lane language and the lane tool are open source under the MIT license, so anyone may use, modify, and even commercialize them. However, every design decision in Lane and every implementation decision in the lane tool are dictated by the original author, MilkyNatas. Lane is something I make for fun, so I am not here to pamper users.

Getting Started

You can use Lane by installing the lane tool, or you can try it in the official playground.

The traditional first step in learning programming or a programming language is to write a Hello World program, which prints hello, world. First, write the following text in a local file or in the playground editor:

module Hello

import Basic.Io.*

pub fn hello() -> Unit ! Io {
  println("hello, world")
}

How to run this program depends on the context. In a Unix environment with the lane tool installed, suppose we save the text above as hello.lane. The content of that file is the program's source code. Run the following command:

lane run hello.lane:hello

This runs the program and prints the following output in the terminal:

hello, world

The command we just entered in the terminal also shows that we need to pass the directory that contains the Basic library. In general, installing the toolchain will ask us to set the $LANE_HOME environment variable to a suitable location, and the Basic library is installed under $LANE_HOME/basic by default. Basic is the standard library of the Lane language, but the library itself has no special privileges. Therefore, we can also write another file named io.lane in the current directory and use it to temporarily provide the standard library content we need:

module Basic.Io

pub let println : (String) -> Unit ! Io = extern("println")

Then run:

lane run hello.lane:hello --lib io.lane --no-basic

This prints the expected output.

By comparison, completing this task in the playground is much easier. The web page includes the Basic library files needed to run the example, including the io.lane file we need. Ideally, after the hello program has been entered, the output box will show:

hello, world

It is worth explaining the command and program text we used.

  • Line 1 declares a module named Hello. The first statement in any Lane file must be a module name declaration, and each file can declare only one module.
  • Line 3 imports another module. The wildcard * imports every name under the Basic.Io module. Here, we use only one name: println.
  • Lines 5-7 define a function.
    • At the beginning of line 5, pub declares the function's visibility. It means the function can be accessed externally, for example by the lane run command or by other modules.
    • fn is the keyword for declaring a function, and hello after it is the function's name.
    • The parentheses after the function name are the function's parameter list. The hello function has no parameters, so the parentheses are empty.
    • After the arrow -> is the function's return type. Unit ! Io means the function returns a value of type Unit and declares that it may produce an Io effect.
  • The function body on line 6 is enclosed in braces, and it contains only one expression. That expression calls println to print the string to the terminal.
  • The part enclosed in double quotes " is a string.

The concepts that appear here, including modules, strings, functions, visibility, types, and effects, are explained in detail in the main chapters.

Now look at the command we ran. lane run is the main entry point for running a Lane file. It takes a positional argument that specifies the function to run and the file that contains it. In our example, we run the hello function in hello.lane. It is easy to imagine defining multiple functions in one file and running whichever one is needed.

--lib <file> adds another Lane source file as a library, while --lib-dir <path> adds every Lane file under a directory as a library. Because we passed one of these options, hello.lane can import the Basic.Io module defined in another file.

Bindings, Integers, Functions, and Builtin Functions

With Lane's builtin integer type and builtin functions, we can use Lane to do some simple computation. For example, we can compute the sum of two integers:

// integer.lane
module Integer

import Basic.Io.*

let add : (Int, Int) -> Int = builtin("%i64_add")

let sum : Int = add(1, 2)

pub fn print_sum() -> Unit ! Io {
  println("sum is " + to_string(sum))
}

Run lane run integer.lane:print_sum --lib io.lane, and you should see sum is 3 printed in the console.

The first line of this program is a comment. A comment starts with two consecutive slashes //, and the rest of the line is only used to explain the meaning of the program; it does not affect the program's behavior. Comments are ignored by the compiler, which in this case is what lane run invokes, so they may contain any text.

This time, first look at line 6. It binds the value add(1, 2) to the name sum. After we bind a value to a name, we can use that name anywhere to stand for the original value. For example, we use sum on line 11; if we replaced that sum with add(1, 2), the program would produce the same result.

After the colon in a let binding is the type of the binding. The type of sum is Int, which means sum is an integer, more precisely a 64-bit integer.

The expression used to compute sum is the function application add(1, 2). We can understand this by common sense: the result of add(1, 2) is the integer 3.

Line 4 binds the builtin function builtin("%i64_add") to the name add. Here, the type of add is (Int, Int) -> Int, which means add is a function. Both of its parameters are integers, and its return type is also an integer. Therefore, after passing two integers as arguments to add, the result, which is the value of the whole expression, is also an integer.

The right-hand side of the binding on line 4 is a builtin function. For now, we do not need to care about the details of this function. We only need to know that implementing integer addition inside the Lane language itself would be very troublesome; by using a builtin function, we can hand this function to the compiler, and the compiler will implement the correct operation for us.

Lane's Int type is a 64-bit integer, which means its range is from -2^63 to 2^63-1. In general, we will not need numbers that large. Besides Int, Lane has other builtin types, such as Bool, String, and Unit.

We can slightly modify line 6 of the program above:

let sum : Bool = add(1, 2)

That is, we change the type of sum to the Boolean type Bool. If we run lane run or lane check again, the compiler will immediately report an error:

expected `Bool`, found `Int`

This means that we need sum to be a Bool, but the type of the right-hand side of = is Int.

Types can help us avoid many errors before the program runs. In the following chapters, we will see how Lane helps us do this.

Local Bindings and Scope

Bindings can be written at the top level of a file, but they are more commonly written inside function definitions. These are local bindings. For example, the integer-printing program above can be written like this:

// scope.lane
module Scope

import Basic.Io.*

let add : (Int, Int) -> Int = builtin("%i64_add")

pub fn print_sum() -> Unit ! Io {
  let sum = add(1, 2)
  println("sum is " + to_string(sum))
}

This program produces the same result as before. The difference is that local bindings can omit their types. Notice that we did not write : Int here; the compiler automatically infers that the type of sum is Int. This feature is very useful when a type is hard to write down.

There is another difference: now only the inside of the print_sum function can access sum. More precisely, sum can be accessed only after the local let binding on line 9 and before the function definition ends on line 11. This region is called a scope. Each local binding can be accessed only by expressions inside its scope. For a top-level binding, its scope is the whole file. For a binding marked with the pub visibility marker, other modules can also access it by importing the module.

Inside the scope of a binding, if a new binding with the same name appears, the new binding shadows the old one. For example:

pub fn print_sum() -> Unit ! Io {
  let sum = add(1, 2)
  let sum = add(3, 4)
  println("sum is " + to_string(sum))
}

This program prints sum is 7, not sum is 3, because the second binding shadows the first binding. Now consider another example. In this example, we define a local function. Like a local binding, it can be accessed by later expressions inside its scope:

pub fn print_sum() -> Unit ! Io {
  let sum = add(1, 2)
  fn add3(a : Int, b : Int, c : Int) -> Int {
    let sum = add(a, b)
    add(sum, c)
  }
  let sum = add3(sum, sum, sum)
  println("sum is " + to_string(sum))
}

This program prints sum is 9. The reason is that the sum on line 2 has the result 3; the sum on line 5 refers to the binding on line 4, not the shadowed binding on line 2. When add3(sum, sum, sum) is computed on line 7, the argument sum refers to the binding on line 2, because the scope of the sum bound on line 4 is only inside the body of add3, and it ends when that function body ends on line 6. Therefore, the final result is add3(3, 3, 3) => add(add(3, 3), 3) => add(6, 3) => 9.

Scope limits where a binding can be accessed; shadowing ensures that the meaning of a name is determined by the nearest effective binding with that name. With these two rules, we can compose code with more confidence, without worrying that some distant binding with the same name will accidentally change the meaning of the current code.

Booleans, Enums, and Pattern Matching

In Lane, we can compare two numbers and enter different program branches based on the result of the comparison. The print_less_one function defined below prints the smaller of its two arguments:

// compare.lane
let less : (Int, Int) -> Bool = builtin("%i64_lt")

fn print_less_one(a : Int, b : Int) -> Unit ! Io {
  match less(a, b) {
    true => println(to_string(a))
    false => println(to_string(b))
  }
}

To avoid repetition, from now on we will no longer write out the module declaration and module import statements every time.

In the program above, we bind the builtin function %i64_lt to less. It compares the sizes of two integers. When a < b, less(a, b) returns the Boolean value true. There are only two Boolean values: true and false. The next three lines of code match on the comparison result: if the result is true, the program prints a; otherwise, it prints b.

For Boolean values, besides pattern matching, we can also use a conditional expression, also known as an if-then-else expression. The following function has the same behavior as the one above:

fn print_less_one(a : Int, b : Int) -> Unit ! Io {
  if less(a, b) {
    println(to_string(a))
  } else {
    println(to_string(b))
  }
}

If the expression after if evaluates to true, then the expression inside the first pair of braces, also called the then branch, becomes the result of the whole conditional expression; otherwise, the expression inside the second pair of braces, also called the else branch, becomes the result of the whole conditional expression.

Like Bool, we can also define our own types whose values can be described by listing all possible cases. For example, we can define the two sides of a coin:

enum Coin {
  head()
  tail()
}

Then we can construct the corresponding value with TypeName::constructor(). For example:

let first_coin : Coin = Coin::head()

When there is no ambiguity, the type name can be omitted:

let second_coin : Coin = tail()

With pattern matching, we can use these values:

match coin {
  Coin::head() => println("head")
  tail() => println("tail")
}

Enum values can also carry data. For example, we can define a shape type. A shape can be a circle or a rectangle. If it is a circle, we need a floating-point number Double to describe its radius; if it is a rectangle, we need two floating-point numbers to describe its length and width:

enum Shape {
  circle(Double)
  rectangle(Double, Double)
}

Defining values of the shape type works the same way as before: we only need to put the carried data inside the parentheses:

let shape1 : Shape = circle(4.0)

let shape2 : Shape = rectangle(2.0, 3.0)

We can write a function that computes the area of a shape:

fn area(shape : Shape) -> Double {
  match shape {
    circle(r) => r * r * pi
    rectangle(x, y) => x * y
  }
}

We will introduce the floating-point type Double, the multiplication sign *, and the constant pi later, but that does not stop us from understanding this program. Pattern matching enters the branch corresponding to how the value was constructed and binds the data carried by the value to the names inside the parentheses. For example, circle(r) binds the circle's radius to r, and rectangle(x, y) binds the rectangle's length and width to x and y.

Structs

A struct is another kind of user-defined type, different from an enum type.

Sometimes the data type we need has only one shape, such as a point in two-dimensional space:

enum Point {
  point(Int, Int)
}

let p : Point = point(1, 2)

In this situation, it is more convenient to use a Lane struct. The syntax for defining a struct is similar to the syntax for defining an enum type, except that both the name and the type of each field must be written out. The syntax for constructing a struct literal is also similar to the syntax for constructing an enum value, except that each field name must be written out, followed by the corresponding value after a colon:

struct Point {
  x : Int
  y : Int
}

let p : Point = Point::{ x: 1, y: 2 }

Structs are used in a way similar to enum types, and their fields can also be accessed through pattern matching:

fn squared_distance(p : Point) -> Int {
  match p {
    Point::{ x: first, y: second } => first * first + second * second
  }
}

When a struct field name is the same as the name we want to bind in the pattern, we can use shorthand syntax:

fn squared_distance(p : Point) -> Int {
  match p {
    Point::{ x, y } => x * x + y * y
  }
}

Besides pattern matching, struct fields can also be accessed directly with dot notation:

fn squared_distance(p : Point) -> Int {
  p.x * p.x + p.y * p.y
}

Lists and Generics

Lane also supports a special type and its corresponding literal syntax: lists. A list is an ordered collection of elements, and all elements must have the same type. We can use square brackets [] to write list literals, with elements separated by commas ,. For example:

let int_list : List[Int] = [1, 2, 3]

let bool_list : List[Bool] = [true, false, true]

As we can see, the list type List itself is not a concrete type, but a generic type. List[Int] means a list whose element type is Int, and List[Bool] means a list whose element type is Bool. We can use List[T] to mean a list whose element type is some type T.

User-defined enums and structs can also be generic types like this. For example, we can define a generic binary tree type:

enum Tree[T] {
  leaf(T)
  node(Tree[T], Tree[T])
}

We can also define a simple boxed type:

struct Box[T] {
  value : T
}

We can understand this type as follows: for any type T, Box[T] represents a box whose carried value has type T.

Therefore, we can put values of any type into a box of type Box[T]:

let int_box : Box[Int] = Box::{ value: 42 }

let bool_box : Box[Bool] = Box::{ value: true }

In fact, lists are defined as a generic enum type in the Basic.Data.List module:

module Basic.Data.List

enum List[T] {
  empty()
  cons(T, List[T])
}

The list literal [1, 2, 3] written with square brackets is actually shorthand for cons(1, cons(2, cons(3, empty()))).

Besides structs and enums, functions can also be generic. For example, we can define a function that accepts a list and returns its length:

fn[T] length(list : List[T]) -> Int {
  match list {
    empty() => 0
    cons(_, tail) => 1 + length(tail)
  }
}

let int_list : List[Int] = [1, 2, 3]

fn print_length(list : List[Int]) -> Unit ! Io {
  println("length is " + to_string(length(list)))
}

The program above prints length is 3. We use [T] in the function definition on line 1, which means length is a generic function. It can accept a list with any element type as its argument. No matter what the element type of the list is, the length function can correctly compute the length of the list. This lets us use the same function to compute the length of lists with different element types, without writing a new function for each type.

Recursive Functions and Higher-Order Functions

In the program that prints the length of a list, the length function calls itself. Such a function is a recursive function. A recursive function is a function that directly or indirectly calls itself in its function body. Recursion is a common programming technique, especially suitable for processing data types with recursive structure, such as lists and trees.

Basically, all list-related operations are suitable for implementation with recursive functions. For example, we can define a function that computes the sum of all integers in a list:

fn sum(list : List[Int]) -> Int {
  match list {
    empty() => 0
    cons(head, tail) => head + sum(tail)
  }
}

Suppose we have a list [1, 2, 3]. We can observe the computation process of this function:

  sum([1, 2, 3])
= 1 + sum([2, 3])
= 1 + (2 + sum([3]))
= 1 + (2 + (3 + sum([])))
= 1 + (2 + (3 + 0))
= 6

Lists have a common operation called mapping, or map. A mapping operation applies a function to each element in a list and returns a new list; the new list contains the result of applying the function to each corresponding element in the original list. For example, we can define a function that doubles every integer in a list:

fn double_list(list : List[Int]) -> List[Int] {
  match list {
    empty() => empty()
    cons(head, tail) => cons(head * 2, double_list(tail))
  }
}

This function returns a new list where each element is twice the corresponding element in the original list. For example, double_list([1, 2, 3]) returns [2, 4, 6].

Suppose we have a function for checking whether an integer is even:

fn is_even(n : Int) -> Bool {
  n % 2 == 0
}

We can define a function that checks whether each element in a list is even:

fn is_even_list(list : List[Int]) -> List[Bool] {
  match list {
    empty() => empty()
    cons(head, tail) => cons(is_even(head), is_even_list(tail))
  }
}

is_even_list([1, 2, 3]) returns [false, true, false].

As we can see, double_list and is_even_list have very similar structures. They both use recursion and pattern matching to process lists. To avoid repeated code, we can define a more general higher-order function map, which accepts a function and a list as parameters and returns a new list:

fn[T, U] map(f : (T) -> U, list : List[T]) -> List[U] {
  match list {
    empty() => empty()
    cons(head, tail) => cons(f(head), map(f, tail))
  }
}

In this function, T and U are type parameters. They represent the element type of the input list and the element type of the output list, respectively. f is a function that accepts a parameter of type T and returns a result of type U. The map function applies f to each element in the list and returns a new list.

This ability to pass functions as arguments lets us write more general and more reusable code. We can use map to implement double_list and is_even_list:

fn is_even_list(list : List[Int]) -> List[Bool] {
  map(is_even, list)
}

To implement double_list, we can define a simple function double and pass it to map:

fn double(n : Int) -> Int {
  n * 2
}

fn double_list(list : List[Int]) -> List[Int] {
  map(double, list)
}

Of course, since the double function is very simple, we can also use an anonymous function directly:

fn double_list(list : List[Int]) -> List[Int] {
  map(fn(n : Int) -> Int { n * 2 }, list)
}

An anonymous function is itself an expression. It can be used directly wherever a function is needed, without first giving it a name. Usually, we use anonymous functions when we need to pass a function as an argument. This reduces the cost of naming and makes the code more concise. Of course, because an anonymous function is an ordinary expression, it can also be bound to a name for use elsewhere, or returned as a return value.

Contextual Resolution and Operator Overloading

We finally have a chance to uncover the mystery behind the addition operator +. Earlier, we used + to compute the sum of integers, and we also used + to concatenate strings and compute the sum of floating-point numbers. With the previous introduction to generics, we can understand + as a generic function: its parameter types and return type all depend on the types of the arguments. Its declaration might roughly look like this:

fn[T] +(a : T, b : T) -> T { ... }

Of course, this is not legal Lane syntax. In Lane, + is not an ordinary function name; the compiler resolves it as a call to the op_add function. The real declaration of op_add is roughly like this:

module Basic.Ops

import Basic.Builtins.*

pub fn[T] op_add(a : T, b : T, auto op : Add[T]) -> T {
  op.add(a, b)
}

pub offer int_add_ops : Add[Int] = Add::{ add: int_add }

In other words, op_add calls the add field in its third parameter op to perform the real addition. Ignoring the new keywords auto and offer for now, we can see that op_add has an extra parameter op, whose type is Add[T]. That type is defined as follows:

module Basic.Ops

struct Add[T] {
  add : (T, T) -> T
}

It is only a wrapper around a function type. In other words, the third parameter of op_add is not the function itself, but a struct value containing an add field; that add field is the function, which accepts two parameters of type T and returns a result of type T.

The key is that, in the same context where op_add is called, there must be a value of type Add[T]. This value is automatically passed as the third parameter of op_add. For integer addition, the function that performs the actual computation is the builtin function in the Basic.Builtins module:

module Basic.Builtins

pub let int_add : (Int, Int) -> Int = builtin("%i64_add")

This builtin("%i64_add") is the builtin function we mentioned earlier. Then the Basic.Ops module wraps it into a value of type Add[Int]:

module Basic.Ops

pub offer int_add_ops : Add[Int] = Add::{ add: int_add }

The int_add_ops binding is not declared with let, but with offer. A binding declared with offer enters a "candidate context". When a function declares an "automatic parameter" with auto, callers do not need to pass that parameter explicitly; instead, the compiler can look in the candidate context for a candidate value with a matching type.

That is, when we call op_add in some context, which is what happens when we use the + operator, if that context contains a value of type Add[T], then this value is automatically passed as the third parameter of op_add. In the usual case, as long as we import the relevant bindings from the Basic.Ops module, int_add_ops enters the candidate context, allowing addition for integers to work normally.

With this mechanism, addition for the Double type can be implemented in a similar way. As long as the Basic.Builtins module defines a builtin function double_add, and the Basic.Ops module provides a double_add_ops binding, the + operator can support addition for floating-point numbers.

Review this once more. When we use the + operator in a program:

fn add_numbers(a : Int, b : Int) -> Int {
  a + b
}

The compiler treats it as a call to op_add:

fn add_numbers(a : Int, b : Int) -> Int {
  op_add(a, b)
}

The op_add function has an implicit parameter op, whose type is Add[Int]. The compiler looks in the current context for a value of type Add[Int]. If it finds one, it passes that value as the third parameter of op_add, completing integer addition.

fn add_numbers(a : Int, b : Int) -> Int {
  op_add(a, b, op=int_add_ops)
}

When we use the + operator to concatenate strings, the compiler looks for a value of type Add[String], thereby completing string concatenation. It looks as if the behavior of op_add changes depending on the types of the arguments, but in fact these are two different calls whose automatically filled arguments are not the same. This feature is called Contextual Resolution. It allows us to provide different default implementations for the same function in different contexts. With Contextual Resolution, operator overloading is easy to implement: the same operator can have different behavior on operands of different types.

Input/Output and Effects

In the first program that printed a string, we defined the println function like this:

pub let println : (String) -> Unit ! Io = extern("println")

This binding uses extern("println") to refer to a function supplied by the execution environment. extern differs from builtin: a builtin is an operation understood and implemented directly by the compiler, while an extern names a symbol that the runtime must provide when the program is loaded. The type of println carries ! Io, indicating that it may interact observably with the external environment while returning Unit. Lane functions without effects remain pure; a function such as println, which changes the console's contents, must declare Io in its type.

Like Int, Io is a type built into Lane rather than declared by the Basic.Io module. It has no effect operations that a program can handle; instead, it uniformly represents interaction with the terminal, files, clocks, randomness, environment variables, networks, and other parts of the outside world. Basic.Io is only an ordinary library module that exports the println function bound to the println runtime symbol; neither its module name nor the symbol name receives special treatment from the compiler.

What about other effects? In Lane, users can define effects just as they define custom types:

effect Exception {
  raise(String) -> Unit
}

This defines an exception effect, one of the most typical uses of effects. When a program reaches a situation that it cannot handle normally, it can raise an exception and let the program that calls it handle the exceptional situation. For example, we have a function first that takes the first element from a list. Its return type is the list's element type. What should it return if the list contains no elements? We can use the following enum type to express the return type:

enum Option[T] {
  some(T)
  none()
}

But we can also let the function produce an Exception effect:

fn[T] first(ls : List[T]) -> T ! Exception {
  match ls {
    empty() => raise!("no elements in the list")
    some(head, tail) => head
  }
}

The syntax for producing an effect is operation!(arguments). The operation can be a branch defined in a custom effect or a function that produces an effect. Just as some can be viewed as a function of type (T) -> Option[T], raise can be viewed as a function of type (String) -> Unit ! Exception. When an effect appears in an expression, the whole expression must either pass the effect outward, for example in a function signature, or handle it with a handle-with expression.

In the example above, the first function produces the raise effect without handling it, so executing the function also produces, or more precisely may produce, an Exception effect. We can handle this effect at the call site. Handling an effect is similar to pattern matching on an enum value: different effect operations enter different branches. Because Exception has only one operation, raise, there is only one branch:

fn print_first_integer() -> Unit ! Io {
  let list = [1, 2, 3, 4]
  handle first(list) with {
    raise(msg, _resume) => println("got exception: " + msg)
  } final v {
    println("first integer is: " + to_string(v))
  }
}

Notice two new things: the raise pattern has a second, unused parameter, resume; and in addition to using the with block to match every operation of type Exception, we need final as a fallback for when the function call returns normally. For example, calling the function above prints first integer is: 1. That is, the 1 returned normally by first([1, 2, 3, 4]) is bound to the name v in the final block.

The following program expresses this logic: when calling first encounters raise, use 0 as the default result of the call.

handle first(list) with {
  raise(_msg, _resume) => 0
} final v {
  v
}

However, the logic for handling an effect is often not in the same program as the code that produces the effect. For example, a huge program may call first after many layers of nesting, but first does not know how its caller intends to handle the effect. We can suppose the following situation:

handle {
  ...
  let fst = first(some_list)
  ...
} with {
  ...
} final v {
  ...
}

The effectful first function is only one line in a program with tens of millions of lines. Here, we want 0 to be bound to fst when first raises an exception, rather than having the whole expression evaluate to 0. We can use resume to do this:

handle {
  ...
  let fst = first(some_list)
  ...
} with {
  raise(_msg, resume) => resume(0)
} final v {
  ...
}

resume is a function that represents the continuation of the program at the call to first. When resume(0) is called, the program returns to where first was executed, fills the first(some_list) expression with the value 0, and continues running the rest of the program.

Summary

So far, we have introduced most of the language features commonly used in Lane. With these features, we can already write large programs. Later chapters will discuss each basic feature in more detail.

Types

Types are an extremely important concept in the Lane programming language. The organization, underlying representation, and behavioral abstraction of data all rely on types.

Builtin Types

Lane provides several important builtin types:

Int
Double
String
Unit
Bool
Void

Their definitions are not exposed to programmers. However, we can roughly understand Void, Bool, and Unit as having definitions like these:

enum Void {}
enum Bool {
  true()
  false()
}
enum Unit {
  unit()
}

Void cannot be constructed; Unit always has exactly one value, unit(); and Bool has two values, true() and false().

In actual Lane programs, there is no need to import the definitions of these types. The actual forms of unit(), true(), and false() are (), true, and false, respectively.

The Boolean type provides the special operators &&, ||, and !, called “and,” “or,” and “not,” respectively. They are used as follows:

assert_eq!(true && true, true)
assert_eq!(true && false, false)
assert_eq!(false && true, false)
assert_eq!(false && false, false)

assert_eq!(true || true, true)
assert_eq!(true || false, true)
assert_eq!(false || true, true)
assert_eq!(false || false, false)

assert_eq!(!true, false)
assert_eq!(!false, true)

It is also important to note that && and || are short-circuiting operators. For a && b, if a evaluates to false, b is not evaluated. Likewise, for a || b, if a evaluates to true, b is not evaluated. This matters especially when evaluating b may produce an effect. Short-circuiting will be discussed again in the later section on effects.

The integer type Int is a 64-bit integer, covering every integer from -(2^63) to 2^63 - 1.

The floating-point type Double is a 64-bit floating-point number conforming to the IEEE 754 standard. It includes positive infinity, double_inf; negative infinity, double_neg_inf; and not-a-number, double_nan.

Lane's string type is a sequence of ASCII codes.

Function Types

Function types use arrows: (A) -> B denotes a function that accepts one parameter of type A and returns a value of type B. For example:

fn f(x : Int) -> Int {
  x * 2
}

Its type is:

f : (Int) -> Int

For a function f of type (A) -> B and a value x of type A, the expression f(x) always has type B.

The number of parameters of a function is called its arity. Here is an example of a binary function:

fn f(x : Int, y : Int) -> Int {
  x + y
}

A function can also have arity zero, for example:

fn f() -> Int {
  42
}

If the parameters of a function f include another function, then f is a higher-order function. If its parameters do not include functions, then it is a first-order function. Ordinary values can be regarded as zeroth-order. If the highest-order parameter of f is of order n, then f is an n + 1-order function.

For example, the following function is second-order:

fn[A, B] apply(f : (A) -> B, x : A) -> B {
  f(x)
}

Function types can also carry type variables. For example, the type of the apply function above can be written as:

apply : [A, B]((A) -> B, A) -> B

This type can be read as follows: if A and B are types, f has type (A) -> B, and x has type A, then apply[A, B](f, x) has type B.

Here, type parameters can usually be inferred automatically by the compiler, so they need not always be written. Normally, apply[A, B](f, x) can be written simply as apply(f, x).

We can also read only half of the type above: if A and B are types, then apply[A, B] has type ((A) -> B, A) -> B.

This way of understanding types is essential for the existential types discussed below.

Existential Types

We have already seen an example of a generic type: the list type List. It can be written as type List : [Type] -> Type, which reads: if A is a type, then List[A] is also a type. In other words, List itself is not a type.

We can define a simplest generic type, Box, which stores only one value:

enum Box[T] {
  box(T)
}

We can regard box as having type [T](T) -> Box[T]. This common kind of polymorphic type is called a universal type. But sometimes we need a box, Hide, that can store any content without reflecting the type of that content in the type of the box itself. In other words, we need a constructor of type [T](T) -> Hide and the corresponding definition of the type Hide. In Lane, we can write this as follows:

enum Hide {
  hide[T](T)
}

Notice that the type variable T is no longer introduced by the enum declaration; it is introduced by the constructor hide. In this example, Hide itself is a type, namely Hide : Type; while hide needs a type parameter and has type [T](T) -> Hide. Its type has the same left-hand side as the type of box and differs only on the right-hand side, but the difference is fundamental.

How can we use such a type? We can use pattern matching, or a binding specifically for irrefutable patterns:

let v : Hide = hide[Int](10)
...
let hide[T](x) = v
// or
match v {
  hide[T](x) => ...
}

Note, however, that because v has type Hide, using it does not tell us that it stores an integer. We know only that after unpacking it, x has type T. Therefore, neither the value x nor the type T can escape its scope. For example, the following program is illegal:

fn[T] escape(v : Hide) -> T {
  let hide[T](x) = v
  x
}

This is because unpacking v essentially matches the hidden type to the type variable T. This T shadows the type variable T introduced by the function's type parameter in the surrounding context. Thus, the program above is no different from the following program:

fn[R] escape(v : Hide) -> R {
  let hide[T](x) = v
  x
}

This makes the problem clear: x has type T, while the function must return R. There is clearly no evidence that these two types are the same, so the function cannot compile.

Inductive Types

Lane supports user-defined finite data types of arbitrary depth. A classic example is the List data structure in the Basic.Data.List package. Let us revisit its definition:

pub enum List[T] {
  empty()
  cons(T, List[T])
}

The constructor cons has two parameters: one of the element type T, and one of the list's own type, List[T]. This naturally raises a question: does List form an infinite data structure by containing itself? The answer is no. Lane uses a strict evaluation strategy: before a value is bound, every subexpression on which it depends must first be evaluated. For example:

let x = f(1 + 1, fib(30))

This binding first evaluates 1 + 1 and fib(30) from left to right, calls f after obtaining their results, and finally binds the result to x.

Therefore, it is impossible to define a list that contains itself:

let l = cons(1, l)

This code cannot compile because the expression on the right-hand side uses l before l is bound. By providing the empty() constructor, the definition of List ensures that at least one path lets a list eventually terminate rather than becoming an infinite structure.

Inductive types are used through pattern matching; we have already seen this in the definition of length. Pattern matching requires every case to be covered. For a list, for example, we must match both empty() and cons(x, xs).

Structs as Interfaces

An “interface” describes the requirements or constraints that a program places on a type. Lane has no language feature that corresponds exactly to interface in other languages, but structs can usually express this kind of constraint. We have already seen this when defining and using Add; now we will continue with the example of aggregating elements in data structures. This example gradually abstracts two questions: how elements are combined, and how a data structure is traversed.

First, consider summing an integer list:

fn sum(list : List[Int]) -> Int {
  match list {
    empty() => 0
    cons(x, xs) => x + sum(xs)
  }
}

This function is a special case of a more general program. Summation does not apply only to integers; it may also apply to floating-point numbers or other types that support addition. We can therefore first generalize it into the following list traversal function:

fn[T] visit(list : List[T], init : T, auto offer add_ops : Add[T]) -> T {
  match list {
    empty() => init
    cons(x, xs) => x + visit(xs, init)
  }
}

Here, Add[T] means that the element type T supports addition, while init is the result for an empty list. This example already shows that an aggregation operation depends both on the way the element type combines values and on the way the list itself is traversed.

More generally, a list has a general fold operation: it starts with init, takes elements from the list in turn, and accumulates the result.

pub fn[T, R] fold(list : List[T], init : R, f : (T, R) -> R) -> R {
  match list {
    empty() => init
    cons(x, xs) => f(x, fold(xs, init, f))
  }
}

The two parameters of the combining operation can even have different types: f has type (T, R) -> R, rather than (T, T) -> T. Thus, sum can be viewed as a special case of fold:

fn sum(list : List[Int]) -> Int {
  fold(list, 0, int_add)
}

For lists, fold is a very general function; almost any list operation can be expressed as a fold.

However, aggregation is not limited to lists. The same task can be performed on a binary tree:

enum Tree[T] {
  leaf()
  node(Tree[T], T, Tree[T])
}

fn sum(tree : Tree[Int]) -> Int {
  match tree {
    leaf() => 0
    node(l, x, r) => sum(l) + x + sum(r)
  }
}

List.sum and Tree.sum have both similarities and differences. Both use integer addition and 0 as the result for an empty structure; their traversal strategies differ: List follows successor nodes, whereas Tree must visit its left and right subtrees. For a tree, we can first write a traversal function corresponding to the list visit:

fn[T] visit(tree : Tree[T], init : T, sum : (T, T) -> T) -> T {
  match tree {
    leaf() => init
    node(l, x, r) => sum(sum(visit(l, init, sum), x), visit(r, init, sum))
  }
}

At this point, we can clearly separate two kinds of abstraction: one constrains how elements are combined, and the other constrains how a container is traversed. Struct interfaces can express these two requirements separately.

First, use Monoid to describe the way an element type must combine values:

struct Monoid[T] {
  empty : T
  append : (T, T) -> T
}

offer int_impl_monoid : Monoid[Int] = ...
offer double_impl_monoid : Monoid[Double] = ...

empty and append cannot be filled in arbitrarily. append must satisfy associativity; appending empty to any x must produce x, which means that empty is an identity element. A structure satisfying these two laws is commonly called a monoid. The Lane compiler cannot verify these conventions, so they must be ensured by the implementer of the interface.

With this interface, each element type can provide its own aggregation rules. For example, the integer instance can use 0 and addition, while the floating-point instance can use its own identity element and combining operation. auto offer monoid : Monoid[T] means that the function requires a Monoid[T] implementation, but callers normally do not need to pass it manually. The tree traversal function can therefore stop receiving an initial value and combining function explicitly:

fn[T] visit(tree : Tree[T], auto offer monoid : Monoid[T]) -> T {
  match tree {
    leaf() => monoid.empty
    node(l, x, r) => monoid.append(monoid.append(visit(l), x), visit(r))
  }
}

Next, use Foldable to describe the traversal capability that a data structure must provide:

struct Foldable[F : [Type] -> Type] {
  fold_map : [T, R](F[T], (T) -> R, Monoid[R]) -> R
}

Here, Foldable constrains not an individual type, but a type constructor such as Tree or List. The [Type] -> Type after the colon in F indicates that, for any type T, F[T] is a type. fold_map accepts a container, a function that maps elements to aggregation results, and a Monoid[R]; it traverses the container and returns the final aggregation result.

Therefore, List and Tree can each provide a Foldable implementation that describes their own traversal order, while a Monoid implementation independently determines how elements are combined. Together, they allow the same aggregation operation to apply to different data structures and element types. This is the key role of structs as interfaces in Lane: they do not impose an inheritance relationship on types, but explicitly record the capabilities and conventions that a program requires.

Higher-Kinded Types

Higher-Rank Types

Infinite Data Types

Introduction

The first implementation of the Lane language is lanec, a compiler written in the MoonBit programming language.