Kestrel lang

Type system

Kestrel implements the Hindley–Milner extended with a subset of Haskell's type classes(you might know them in rust as "traits").

Pure semantics

In kestrel every function is pure. This, of course, does not mean that kestrel programs cannot perform side effects. The side effects are just modelled as data, thus the side effects are implicitly tracked in the type system. The type that represents an effectful computation is defined in the Task module. Effectful computations can be chained with the Task.await function.

The two main advantages are:

• Pure and impure code are clearly separated, and impure code cannot leak into pure logic
• This opens the door to interesting, powerful optimizations

Easy concurrent code

Since a Task can be forked and killed, its possible define a concurrency combinators algebra similar to javascript's Promise.all/Promise.race, but with built-in cancellation (defined in the Async module)

For example, here's how one could set a timeout for a fetch call:

// Type is inferred as
// `Fn(String, Int) -> Option<Response>`
let fetch_with_timeout = fn url, ms {
  Async.race([
    Http.fetch(url) |> Task.map(Some),
    Task.sleep(ms) |> Task.map_to(None),
  ])
}

Or here's how to easily create a retry logic for a task - the code can be easily edited to allow more sophisticated strategies like exponential backoff

// Type is inferred as
// `Fn(Task<Result<a, b>>, Int) -> Task<Result<a, b>>`
let retry_n_times = fn task, n {
  let#await result = task;
  match result {
    Ok(_) => result,
    Err(_) =>
      if n <= 0 {
        result
      } else {
        retry_n_times(task, n - 1)
      },
  }
}

Optimizations

Due to its pure semantics, it's possible to implement aggressive optimizations.

As an example, we can write an Option.map function just by reusing Option.and_then without incurring in overhead due to the extra function calls. This optimization is used in the standard library to write Option.map_2, ..., map_* in a more readable way (example - the code is using the let# syntax)

pub(..) type Option<a> {
  None,
  Some(a),
}

@inline
pub let and_then = fn option, f {
  match option {
    None => None,
    Some(x) => f(x),
  }
}

pub let map = fn option, mapper {
  and_then(option, fn x {
    Some(mapper(x))
  })
}

This code ends up being transformed in the usual code to write the map function:

pub let map = fn option, mapper {
  match option {
    None => None,
    Some(x) => Some(mapper(x)),
  }
}

pub let map = fn option, mapper {
  // ↓ arguments of the and_then call become a let expression.
  let option = option; // <- this is syntactically valid due to shadowing
  let f = fn x {
    Some(mapper(x))
  };
  // ↓ this was the body of the and_then function
  match option {
    None => None,
    Some(x) => f(x),
  }
}

pub let map = fn option, mapper {
  match option {
    None => None,
    Some(x) => fn x {
      Some(mapper(x))
    } (x), // <- note that the function is immediately called
  }
}

pub let map = fn option, mapper {
  match option {
    None => None,
    Some(x) => {
      let x = x;
      Some(mapper(x))
    },
  }
}

pub let map = fn option, mapper {
  match option {
    None => None,
    Some(x) => Some(mapper(x)),
  }
}

{
  let x = some_function();
  let y = another_function();
  y + x
}

another_function() + some_function()

There are a few other optimization strategies already implemented, such as tail call optimization or constant folding.

Vscode extension

Kestrel has a language server protocol implementation, that is consumed by this vscode extension to allow powerful capabilities. You can refer to the extension to see what features are implemented.