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