Traits and instances
This post will explain how the trait system and instance resolution works in Siko. Siko uses traits for describing interfaces, they can be used to constrain generic types in generic functions. Here is a sample trait:
trait Foo[T] {
fn foo(self) -> ()
}
This trait expresses that whatever type has an instance for this trait, that type will have a foo method that returns an empty tuple. To be able to use the trait in practice you need to add instances for types.
struct Bar {
}
instance Foo[Bar] {
fn foo(self) -> () {
}
}
This instance expresses that the struct Bar implements the Foo interface and if you call its foo() method then the instance’s implementation will be used. Let’s use it.
fn someFunc[T: Foo[T]](value: T) {
value.foo();
}
fn main() {
let b = Bar();
b.foo(); // this calls the instance's foo() function
someFunc(b); // the monomorphized version of someFunc will call the same foo() function
}
So far this is kind of what you would expect in a language with generics, it even uses standard naming for these patterns. No surprise there. The cool part is how Siko mixes global instance resolution with Scala style scope based resolution.
Canonical instances
If you do not add a name to your instance then it will be a so called canonical instance. It behaves as you would expect if you are familiar with Rust’s type system (or any other similar system) and it is available globally. For each type and trait pair there can be only a single canonical instance. This ensures that canonical instances are unambiguous. In Rust lingo, this property is called coherence.
Resolution of scoped instances
However, we are not stopping here. You can add names to instances and then they become something that you can export from your module and import from other modules.
module A {
// this instance is named MyFooInstance and it is exported (due to the pub keyword)
pub instance MyFooInstance Foo[Bar] {
fn foo(self) -> () {
}
}
}
module Main {
import A // this imports all public items, including MyFooInstance
fn someFunc[T: Foo[T]](value: T) {
value.foo();
}
fn main() {
let b = Bar();
b.foo();
someFunc(b);
}
}
The exact order of resolution is the following:
- module local instances have the highest priority
- imported instances have a slightly lower priority
- if all else fails then global, canonical instances are searched
In case there are multiple matching candidate instances (in any of the priority levels) then the resolution fails with instance ambiguity. This system ensures that you have fine grained control over which instance(s) are used in which context. You do not have to worry about other modules creating unwanted instances. You can easily create local specialized instances which do not affect the other parts of your program. We do not need complex algorithms to sort instances and try to figure out which one is ‘more specialized’ and you can write as many different instances as you want.
Additionally, you can still keep the same level of ease-of-use that you’d expect and there is no extra boilerplate or manually passing around instances.
The Drop trait
There is a corner case in the system, the handling of instances for Drop. The Drop trait defines a type’s destructor. The Drop trait behaves differently compared to other traits because the compiler can conjure up Drop implementations for types which do not have Drop instances. These functions are not bound to a scope so using scope bound instances for Drop would not make any sense. The solution Siko uses is that Drop instances must be canonical instances which I think even make sense conceptually. You really do not want multiple destructors for a type.
Implicits and effect handlers
Siko now supports implicits and effect handlers. Because it may not be obvious what these features do and more importantly how they are implemented, we will look into them using a simple teletype example. Without much further ado, let’s dive into the code. Here is the full example and we will explore it in detail afterwards.
module TeleType {
pub effect TeleType {
fn readLine() -> String
fn println(input: &String)
}
pub fn run() {
while True {
let input = readLine();
if input == "exit" {
break;
}
println("You said: " + input);
}
}
}
module Main {
import TeleType as T
implicit mut state: Int
fn mockReadLine() -> String {
if state < 3 {
state += 1;
"mocked: ${state}"
} else {
"exit".toString()
}
}
fn mockPrintln(input: &String) {
let expectedString = "You said: mocked: ${state}";
assert(expectedString == input);
}
fn testTeleType() {
let mut state = 0;
with T.println = mockPrintln,
T.readLine = mockReadLine,
state = state {
T.run();
}
}
fn realTeleType() {
println("Starting teletype");
with T.println = println,
T.readLine = readLine {
T.run();
}
}
fn main() {
testTeleType();
realTeleType();
}
}
The example program defines a single TeleType effect that allows for reading and writing to the console in a controlled manner. The effect definition looks similar to a trait definition because it acts as an interface but in contrast to instances (the trait implementations), effects are not handled globally, their actual implementation is context dependent. The execution context of a code block determines how the effect is handled. In other words, the effect acts as a hole in the program, allowing the caller to control what happens when an effect is called. Because Siko is a low level programming language, it does not have a language specific runtime, it does not do stack juggling in a way that you would expect if you heard about algebraic effects previously.
In Siko, effects are statically resolved at compile time and every function that uses an effect is monomorphized to a specific implementation of the effect. In the actual compiled code, there are no runtime checks or dynamic dispatch involved when dealing with effects. In the case of the teletype example, the teletype loop is compiled twice, once for testing and once for real execution. When the monomorphizer encounters a with block it updates the effect handlers in the current context, so that whenever an effect call is encountered, the selected implementation will simply replace the effect call. This is as static as it gets, the function call is literally just replaced. Obviously, everything is type checked and the monomorphizer will complain if the effect is not handled properly, i.e. the current context does not provide an implementation for an encountered effect call.
So far so good, but you may be wondering: the usability of this is questionable because it is not possible to attach state to the effect calls. That’s where implicits come into play! Similarly to effects, implicits are also context dependent, but they are not functions, rather they are variables that can be used in the current context. They don’t provide functionality, they provide state. In the example, we define an implicit variable named state that keeps track of the current state of the test executor. Implicits are bound to local variables using the with block, similarly to effects. Every code in that execution context (arbitrarily deep in the callchain) that wants to use the implicit variable can do so and will use the bound local variable behind the scenes. As you can see, the actual teletype implementation is not aware of the test code injecting state into the loop. Implicits can be immutable and mutable. Implicits are compiled away into an implicitly passed context parameter. The context variable contains a list of implicits in the current execution context and each access to the implicit is replaced by accessing the correct member of the context variable.
I find both implicits and effect handlers a clean abstraction but there are still open design questions. For example, Siko currently does not have closures but I want to introduce them and their interaction with effects and implicits is not yet clear.
Siko language redesign
For those who encountered Siko before and for some reason still remember it, you may have noticed that the language has undergone some significant changes. The goal of this redesign is to improve usability, performance, and overall developer experience. Both visually and semantically, the language is now an imperative language.
module Main {
fn main() {
println("Hello, Siko!");
}
}
