The Vine Programming Language

Vine is an experimental new programming language based on interaction nets.

Vine is a multi-paradigm language, featuring seamless interop between functional and imperative patterns.

See vine/examples/ for examples of Vine.

cargo run -r --bin vine run vine/examples/$NAME.vi

If you're curious to learn more, join the Vine Discord server.

(Vine is still under heavy development; many things will change.)

Getting Started

Let's get started! Once you've installed Vine, we'll take a look at a basic Hello, world! program.

Installation

Make sure you have Rust installed.

# clone the Vine repository
git clone https://github.com/VineLang/vine
cd ./vine

# install the Vine cli
cargo install --path cli

# make sure everything is working
vine run vine/examples/hello_world.vi

You should see:

Hello, world!

Head over to the next page to learn more about what just happened.

Optional: Vine VSCode Extension

Make sure you have Node.js installed.

cd lsp/client
npm i

Then, run "Developer: Install Extension from Location..." and select the lsp/client directory.

You can check that it's working by opening one of the example files and making a syntax error. When you save, you should see an error appear.

Optional: Vine Workspace Configuration

LSP

// .vscode/settings.json
{
  // list all of your top-level Vine programs (globs are supported)
  "vine.entrypoints": ["src/main.vi"]
}

Make sure you reload the window after changing this file.

Formatter

Make sure you have dprint installed.

// dprint.json
{
  "exec": {
    "commands": [
      {
        "exts": ["vi"],
        "command": "vine fmt"
      }
    ]
  },
  "plugins": ["https://plugins.dprint.dev/exec-0.5.0.json"]
}

Hello, world!

Let's run our first Vine program!

// vine/examples/hello_world.vi

pub fn main(&io: &IO) {
  io.println("Hello, world!");
}

We can run this with:

vine run vine/examples/hello_world.vi

You should see something like the following:

Hello, world!

Interactions
  Total                  297
  Annihilate             159
  Commute                  0
  Copy                    17
  Erase                   34
  Expand                  46
  Call                    27
  Branch                  14

Memory
  Heap                   480 B
  Allocated            6_016 B
  Freed                6_016 B

Performance
  Time                     0 ms
  Speed            8_054_237 IPS

At the top, notice that it successfully printed Hello, world!.

At the bottom, you'll also see several statistics printed out. You don't need to worry about them for now. If you want to disable them, you can use --no-stats.

Let's break down what just happened.

  • fn main: declares a function, named main
    • pub: makes it public
    • (&io: &IO): it takes a single parameter:
      • &IO: of type &IO
      • &io: to be dereferenced and bound to the variable io
    • { ... }: in the function body
      • io.println: uses the println method on IO
      • ("Hello, world!"): calls it with the string Hello, world!

We'll go into this in more detail in future chapters.

Every Vine program must contain a pub fn main(&io: &IO) { ... } ("a public function main that takes a reference to IO").

Vine Language Features

An overview of Vine's language features, from the usual to the bizarre.

The Usual

Vine has the usual complement of standard programming language features, including:

  • integer literals and operations: 1 + 2 * 3
  • float literals and operations: 1.0 + 2.0 * 3.0
  • booleans and boolean operators (including short-circuiting): true && !(false || 1 == 2)
  • character, string, and list literals and operations: "abc" ++ "def" ++ ['g', 'h', 'i']
  • tuples: (1, 1.0, "abc"), (1, 2).0
  • variables: let x = 5; x += 1
  • basic control flow:
    • if condition { ... } else { ... }
    • while condition { ... }
    • loop { ... } (loops until break)
    • return value
    • break, continue
    • loop labels: while.label ... { ... break.label ... }

(Try some of these snippets in the vine repl!)

Many of Vine's features are influenced by Rust, and it has a similar expression-oriented syntax, type system, and module system.

Modules

Vine programs are structured into modules. Every Vine file is a module. Modules consist of a collection of items.

// main.vi

// function item named `main`
pub fn main(&io: &IO) {
  io.println("Hello, world!");
}

// constant item named `answer`
const answer: N32 = 42;

Every item has a visibility, which determines where they can be accessed. By default, items are private, and can only be accessed within the module they were defined in. Items can be made public with the pub keyword; public items can be accessed anywhere.

Modules can have submodules.

// main.vi

mod messages {
  pub const greeting: String = "Hello, world!";
  pub const farewell: String = "Goodbye, world!";
}

pub fn main(&io: &IO) {
  io.println(messages::greeting);
  io.println(messages::farewell);
}

Submodules can be included from a separate file:

// messages.vi

pub const greeting: String = "Hello, world!";
pub const farewell: String = "Goodbye, world!";

// main.vi

mod messages = "./messages.vi";

pub fn main(&io: &IO) {
  io.println(messages::greeting);
  io.println(messages::farewell);
}

Items from other modules can be imported with a use item:

// main.vi

mod messages = "./messages.vi";

use messages::{greeting, farewell};

pub fn main(&io: &IO) {
  io.println(greeting);
  io.println(farewell);
}

Types

Vine is statically typed. Every expression has a type, like Bool or List[N32]. Type parameters are written in square brackets.

Types fall in to several categories:

Primitive Types

N32

The type N32 describes natural numbers1, represented with 32 bits of precision.

N32 values can be written as literals in decimal (46), hex (0x2e), or binary (0b101110). Digits can be separated with underscores (1_000_000).

N32s support the usual arithmetic and bitwise operators (4 * 11 + 2, 5 << 3 | 6)

F32

The type F32 describes 32-bit floating-point numbers (following IEEE 754).

F32 values can be written as literals (4.6e1). The decimal point is required.

F32s support the usual arithmetic operators (3.6 * 12.3 + 1.72).

Char

The type Char describes Unicode scalar values. Chars are primarily used within Strings.

Char values can be written as literals using single quotes ('.').

Chars support adding an N32, resulting in another Char ('a' + 4), as well as subtracting another Char, resulting in an N32 ('G' - 'A').

Bool

The type Bool describes booleans.

The two Bool values can be written as literals (true, false).

Bools support the usual short-circuiting logical operators (&&, ||, !) and non-short-circuiting ("bitwise") operators (&, |, ^).

Expressions that evaluate to booleans are called conditions.

IO

IO is a special primitive type used to interact with the outside world. Values of this type cannot be explicitly constructed; instead, an IO handle is passed in to main at the start of the program. See the section on IO for more detail.

1

Natural numbers are non-negative integers. In other programming languages, they are often referred to as "unsigned integers". Seeing as positive integers do have a sign (namely, a positive sign), the only truly unsigned integer is zero.

Standard

The standard library defines various commonly-used types.

(In the following sections, the time complexity of operations is described in Big O notation.)

String

The type String describes Unicode strings, represented as a list of Unicode scalar values.

Strings can be written as literals using double quotes ("Hello, world!").

Strings can be concatenated with the ++ operator (O(1)).

List

The generic type List[T] describes lists of values of type T.

Lists are optimized for fast concatenation and in-order iteration. Accessing the first value in a list is O(1), but accessing an arbitrary value is O(n). An array is a better choice if frequently accessing elements by index.

Lists can be written as literals using square brackets ([1, 2, 3]).

Lists can be concatenated with the ++ operator (O(1)).

Lists can be used as a queue by using .push_back to enqueue and .pop_front to dequeue (both O(1)).

Lists can be used as a stack by using .push_front to push and .pop_front to pop (both O(1)).

Array

The generic type Array[T] describes arrays of values of type T.

Arrays are optimized for fast random access. Accessing an arbitrary value in the array is O(log(n)).

Elements can be added and removed from either the front or the back with push_front/pop_front/push_back/pop_back (O(log(n))).

Arrays can be converted to and from lists with Array::to_list/Array::from_list (O(n)).

Map

The generic type Map[K, V] describes mappings from keys of type K to values of type V.

Maps are sorted by their key, and can be efficiently iterated over using .iter and .into_iter.

Inserting, accessing, and removing a value by key can be done with .insert/.get/.remove (O(log(n))).

The maximum/minimum key-value pair can be removed with .remove_max/.remove_min (O(log(n))).

Structs

Structs are fixed-sized, heterogenous collections of values.

Structs are either tuples or objects, and are either anonymous or named.

// anonymous tuple struct
let a = (1, 'a', 4.6); // a: (N32, Char, F32)

// anonymous object struct
let b = { p: false, q: "xyz" }; // b: { p: Bool, r: String }

// named tuple struct
struct Foo(N32, Char, F32);
let foo = Foo(1, 'a', 4.6); // foo: Foo

// named object struct
struct Bar { p: Bool, r: String }
let bar = Bar({ p: false, q: "xyz" }); // bar: Bar

The values of a tuple struct are accessed by their index.

let a = (1, 'a', 4.6);
a.0 // 1
a.1 // 'a'
a.2 // 4.6

a.2 *= 10.0;
a.2 // 46.0

The values of an object struct are accessed by their key.

let b = { p: false, q: "xyz" };
b.p // false
b.q // "xyz"

b.p = !b.p;
b.p // true

Named struct types can be generic.

struct Pair[T](T, T);

let u = Pair(1, 2); // u: Pair[N32]
let v = Pair(true, false); // v: Pair[Bool]

struct Box[T] { value: T }

let x = Box({ value: 46 }); // x: Box[N32]
let y = Box({ value: "abc" }); // y: Box[String]

Enums

An enum is a type with a fixed set of variants. An enum value is one of those variants.

enum Weekday {
  Monday,
  Tuesday,
  Wednesday,
  Thursday,
  Friday,
}

let day = Weekday::Friday; // day: Weekday

day is Weekday::Monday // false
day is Weekday::Friday // true

let mood = match day {
  Weekday::Monday { ":(" }
  Weekday::Friday { ":)" }
  _ { ":|" }
};
mood // ":)"

Enum variants can have associated fields in the form of a tuple or an object.

enum Shape {
  Point,
  Circle(F32),
  Rect { width: F32, height: F32 },
}

let x = Shape::Point; // x: Shape
let y = Shape::Circle(1.0); // y: Shape
let z = Shape::Rect({ width: 4.0, height: 6.0 }); // z: Shape

Pattern matching can be used to branch on the variant of the enum and access its fields.

fn perimeter(shape: Shape) -> F32 {
  match shape {
    Shape::Point {
      0.0
    }
    Shape::Circle(radius) {
      6.28 * radius
    }
    Shape::Rect({ width, height }) {
      2.0 * (width + height)
    }
  }
}

perimeter(Shape::Point) // 0.0
perimeter(Shape::Circle(1.0)) // 6.28
perimeter(Shape::Rect({ width: 4.0, height: 6.0 })) // 20.0

Pattern matching is discussed further in the Patterns section.

Standard Enums

The standard library defines the enum types Option[T] and Result[T, E]:

enum Option[T] {
  Some(T),
  None,
}

enum Result[T, E] {
  Ok(T),
  Err(E),
}

Methods

User-defined types can have methods, functions defined in the type's module that take the type as their first parameter.

enum Shape {
  Circle(F32),
  Rect { width: F32, height: F32 },
}

mod Shape {
  pub fn perimeter(shape: Shape) -> F32 {
    match shape {
      Shape::Circle(radius) {
        6.28 * radius
      }
      Shape::Rect({ width, height }) {
        2.0 * (width + height)
      }
    }
  }
}

let shape = Shape::Circle(1.0);
shape.perimeter() // 6.28

The first parameter of a methods can also be a reference, allowing the method to mutate the value it is called upon.

mod Shape {
  pub fn scale(&shape: &Shape, factor: F32) {
    match &shape {
      &Shape::Circle(radius) {
        radius *= factor;
      }
      &Shape::Rect({ width, height }) {
        width *= factor;
        height *= factor;
      }
    }
  }
}

let shape = Shape::Rect({ width: 4.0, height: 6.0 });
shape.perimeter() // 20.0
shape.scale(2.3);
shape.perimeter() // 46.0

IO

All IO in Vine is done by calling functions on an IO handle, passed in to main at the start of the program. For example, here is a basic cat program:

use std::option::Option::Some;

pub fn main(&io: &IO) {
  while io.read_line() is Some(line) {
    io.println(line);
  }
}

Any function that needs to do IO must take a reference to this handle.

use std::option::Option::Some;

pub fn main(&io: &IO) {
  if io.prompt("What is your name? ") is Some(name) {
    greet(&io, name);
  }
}

fn greet(&io: &IO, name: String) {
  io.println("Hello, " ++ name ++ "!");
}

Any function that does not get passed a reference to an IO handle is pure (i.e. does not interact with the outside world).

IO calls are asynchronous and do not block the execution of the rest of the program.

Every IO function takes the IO handle by reference, and the IO handle is updated after every low-level IO operation (like printing or reading a byte). This ensures that the IO is executed in the expected order, despite being asynchronous.

Patterns

Patterns appear in:

  • let bindings (let pattern = ...)
  • fn parameters (fn foo(pattern: ...) { ... })
  • match arms (match foo { pattern => { ... } })
  • is expressions (foo is pattern)

Patterns are used to declare variables, unwrap data, and match values.

Complete Patterns

Variables are declared using variable patterns.

let x = 1; // here, `x` is a variable pattern

Variable patterns are often subpatterns of other patterns.

Tuple patterns unwrap tuples:

let tuple = (1, 2);
let (x, y) = tuple; // here, `(x, y)` is a tuple pattern
                    // and `x` and `y` are variable subpatterns
x // 1
y // 2

Similarly, struct patterns unwrap structs:

struct Foo(N32, String);

let foo = Foo(123, "abc");
let Foo(x, y) = foo;
x // 123
y // "abc"

The _ pattern is a complete pattern that discards the matched value.

let tuple = (1, 2);
let (x, _) = tuple; // discard the second field
x // 1

These are all complete patterns, because they match all values of their type. Only complete patterns can be used in let bindings and fn parameters.

Other kinds of complete patterns include:

Incomplete Patterns

Enum patterns match values of an enum type. They are incomplete patterns, because they do not match all values of their type; they only match one variant of the enum. Any pattern with incomplete subpatterns is also incomplete.

Incomplete patterns can be used in match expressions to perform pattern matching. For example:

fn display(score: Option[N32]) -> String {
  match score {
    Some(value) => "score: " ++ value.to_string(),
    None => "no score",    
  }
}

display(Some(123)) // "score: 123"
display(None) // "no score"

Incomplete patterns can also be used with the is operator.

Conditions

Conditions are expressions which evaluate to booleans (the Bool type).

Conditions include:

  • the usual:
    • boolean literals (true, false)
    • short-circuiting logical operators (&&, ||, !)
    • non-short-circuiting ("bitwise") operators (&, |, ^)
    • comparison operators (==, !=, <, <=, >, >=)
  • comparison chains
  • the is operator
  • the implication operator (=>)

Comparison Chains

In Vine, you can chain comparison operators.

For example, a < b < c is equivalent to (a < b) & (b < c).

More generally, a() < b() < c() is equivalent to

do {
  let x = a();
  let y = b();
  let z = c();
  (x < y) & (y < z)
}

Note that comparison chains do not short-circuit; all of the subexpressions are evaluated exactly once.

All of the comparison operators can be chained. As a contrived example, these are equivalent:

1 == 1 < 2 <= 3 > 0 != 5 // true
(1 == 1) & (1 < 2) & (2 <= 3) & (3 > 0) & (0 != 5) // true

The is Operator

The is operator checks if an expression matches some pattern, and returns a boolean.

let option = Some(1);
option is Some(_); // true
option is None; // false

Any variables bound by the patterns are in scope in subsequent true-paths including && chains, then-blocks of an if, and the body of a while.

let option = Some(1);

option is Some(value) && value > 0; // true

if option is Some(value) {
  value; // 1
} else {
  // `value` is not bound in this scope
}

A true-path is broken by negation (!) and disjunction (||).

// invalid:
!(option is Some(value)) && value > 0

// invalid:
option is Some(value) || value > 0

Implication

In logic, the statement "P implies Q" is true if, whenever P is true, Q is also true. This is equivalent to "P is false, or Q is true". Vine has an implication operator, =>, with the same semantics.

true => true // true
true => false // false
false => true // true
false => false // true

The implies operator also continues the true-path; variables bound in the left-hand side are in scope in the right-hand side:

let x = Some(1);
x is Some(value) => value > 0 // true
x is Some(value) => value == 0 // false

let y = None;
y is Some(value) => value > 0 // true
y is Some(value) => value == 0 // true

A common pattern in other languages is to write value == null || validate(value) to validate a nullable value. In Vine, this is written with the implication operator:

value is Some(value) => validate(value)

Values, Spaces, and Places

The result of an expression in Vine has one of three forms: a value, a space, or a place.

  • a value represents some piece of data
  • a space represents somewhere that data can be put
  • a place is the combination of a value and a space.

We'll use the following code example to explore these concepts further.

let x = 1 + 2;
x + 1;
x = 5;
x *= 2;

On line 1, the expression 1 + 2 results in the value 3. The variable x is then declared with an initial value of 3.

On line 2, the expression x results in its value 3, so the expression x + 1 results in the value 4. This expression is unused so its result is simply discarded.

On line 3, we have an assignment statement. This expects a space on the left-hand side, and a value on the right-hand side, and will put the value into the space. In this particular case, the expression x on the left-hand side results in a space – whatever value is put into this space will become the new value of x. Then, the assignment operator puts the value 5 into the space. The value of x is now 5.

On line 4, the *= operator expects a place on the left-hand side, and a value on the right-hand side. Thus, x results in its place, which is the combination of the value 5 and a space to put a new value for x. The *= operator uses the value to calculate 5 * 2, and puts the value 10 into x's space. Thus, the value of x is now 10.

Expression Resolution

Expression Positions

Every expression is located in either a value position, a space position, or a place position. The form of the expression's position determines the form of the result of the expression.

We saw above that the expression x could result in a value, a space, or a place; this is determined by the form of its position.

  • On line 2, in x + 1, x is in a value position, so it results in a value.
  • On line 3, in x = 5, x is in a space position, so it results in a space.
  • On line 4, in x *= 2, x is in a place position, so it results in a place.

Expression Forms

Independent of its position, every expression has a form - it is either a value expression, a space expression, or a place expression. For example, variable expressions, like x, are place expressions.

The form of an expression determines the form of what the expression evaluates to. If this form does not match the form of the expression's position, it is coerced to become the result.

  • On line 2, in x + 1, x evaluates to a place. It is in a value position, so it is coerced to a value.
  • On line 3, in x = 5, x evaluates to a place. It is in a space position, so it is coerced to a space.
  • On line 4, in x *= 2, x evaluates to a place. It is in a place position, so it is not coerced.

Coercion

There are two rules for coercion.

  • When a place is coerced to a value, the resulting value is a copy of the place's value; the other copy is put into the place's space.

  • When a place is coerced to a space, the resulting space is the place's space; the place's value is discarded.

These two rules result in the behavior described in the first section.

Values and spaces cannot be coerced. It is an error to have a value expression in a non-value position, or a space expression in a non-space position.

References

A reference is a value that represents a place.

References can be created using the & reference operator.

let x = 1; // x: N32
let r = &x; // r: &N32

r is now a reference to the place that x evaluated to. It is of type &N32, the type representing references to N32s.

References can be unwrapped using the & reference pattern.

let x = 1;
let r = &x;

let &y = r; // unwrap the reference `r` into a place, and name it `y`
y = 2; // write the value `2` into the place

x // 2

References can be passed to function calls to allow mutation of local variables:

fn increment(&n: &N32) { 
  n += 1;
}

let x = 0;
increment(&x);
x // 1

Under the hood, methods that mutate their receiver use references:

let x = [1, 2, 3];
x.push_back(4); // equivalent to: `List::push_back(&x, 4)` (note the reference!)
x // [1, 2, 3, 4]

References are also useful when a function only needs to access part of a data structure:

// Inefficient

fn is_empty(list: List[N32]) -> N32 {
  list.len() != 0
}

let x = [1, 2, 3, 4];
let e = is_empty(x); // inefficient; clones the whole list
x // [1, 2, 3, 4]
e // false

// Efficient

fn is_empty(&list: &List[N32]) -> N32 {
  list.len() != 0
}

let x = [1, 2, 3, 4];
let e = is_empty(&x); // efficient; no clones necessary
x // [1, 2, 3, 4]
e // false

(This is why List::len takes its receiver by reference, despite not needing to mutate it.)

Dereference Operator

The place contained in a reference can also be accessed with the * dereference operator:

let x = 1;
let r = &x;
*r = 2;
x // 2

(Note that there are currently some bugs/limitations with this; if you have a reference stored in a variable, it is preferred to use reference patterns instead.)

This can be useful when a function returns a reference:

let x = [1, 2, 3];
*x.get(2) = 4;
x // [1, 2, 4]

The * operator can also be written as a postfix operator using .*:

let x = [1, 2, 3];
x.get(2).* = 4;
x // [1, 2, 4]

Dereference Pattern

The * dereference pattern takes a value pattern of type &T, and yields a place pattern of type T. This can be used, for example, to "split" a reference to a struct into references to its fields.

struct Pair(N32, N32);

fn increment(&n: &N32) { 
  n += 1;
}

fn increment_pair(r: &Pair) {
  let &Pair(*x, *y) = r; // x: &N32, y: &N32
  increment(x);
  increment(y);
}

let pair = Pair(0, 0);
increment_pair(&pair);
pair // Pair(1, 1)

The Inverse

Vine's concept of the inverse is not something seen in other programming languages, as it is a concept that is only possible due to the unique properties of interaction nets.

The inverse type ~N32 represents an expectation of an N32. Such an expectation must be fulfilled with an N32. The type ~~N32 is equivalent to the type N32.1

The inverse operator can be applied to a value, a space, or a place.

  • The inverse operator, when applied to a space s of type T, evaluates to a value of type ~T. This value is the expectation of a T that will be put into the space s.

  • The inverse operator, when applied to a value v of type T, evaluates to a space of type ~T. Whatever expectation is put into the space will be fulfilled with the value v.

  • The inverse operator, when applied to a place p of type T, evaluates to a place q of type ~T. The value of q is the inverse of the space of p; the space of q is the inverse of the value of p.

The inverse pattern is essentially the reverse of the inverse operator, and can be used to unwrap inverse types.

Out Parameters

The inverse operator can be used to implement out parameters:

// `foo` takes an expectation of an `N32` as its parameter
fn foo(~n: ~N32) {
  // and fulfills it with `123`
  n = 123;
}

let x: N32;
let e = ~x; // e: ~N32
// `e` is now an expectation of an `N32` to put into `x`
foo(e); // we pass `e` to `foo`, which fulfills it with `123`
x // 123

(References can serve a similar role, but references also carry with them a current value.)

DIY Functions

The inverse operator can also be used to implement functions from scratch. The following code using functions:

let add_one = fn(x: N32) { x + 1 };
let a = 1;
let b = add_one(a);
b // 2

Could be written without functions like so:

// `add_one` will be a tuple:
// - the first element will be an expectation of the input
// - the second element will be the output
let add_one: (~N32, N32) = do {
  let x: N32;
  (
    ~x, // create an expectation for the input, which will be put into `x`
    x + 1, // calculate the output
  )
};
let a = 1;
let b = do {
  let (~i, o) = add_one; // destructure the tuple
  i = a; // fulfill the input expectation with `a`
  o // evaluate to the output
};
b // 2

Note that here, the order in which these computations can resolve does not align with the imperative order of execution; the fulfillment on line 14 must be resolved before x + 1 on line 8 can be resolved. This value is in a sense flowing "backwards"; counter to the usual forward flow.

Backwards Flow

This effect can be generalized; if you invert all uses of a variable, the variable will flow "backwards":

// Normal, forward flow:
let x: String;
x = "a";
io.println("0: " ++ x);
io.println("1: " ++ x);
x = "b";
io.println("2: " ++ x);
io.println("3: " ++ x);
x = "c";

0: a
1: a
2: b
3: b

// Inverted, backward flow:
let ~x: String;
~x = "a";
io.println("0: " ++ ~x);
io.println("1: " ++ ~x);
~x = "b";
io.println("2: " ++ ~x);
io.println("3: " ++ ~x);
~x = "c";

0: b
1: b
2: c
3: c

Normally, writing to a variable affects accesses on later lines. For an inverted variable, writing to a variable affects accesses on earlier lines.

This gets extra peculiar when you initialize the variable:

// Normal, forward flow:
let x = "a";
io.println("0: " ++ x);
io.println("1: " ++ x);
x = "b";
io.println("2: " ++ x);
io.println("3: " ++ x);
x = "c";
io.println("4: " ++ x);
io.println("5: " ++ x);

0: a
1: a
2: b
3: b
4: c
5: c

// Inverted, backward flow:
let ~x = "a";
io.println("0: " ++ ~x);
io.println("1: " ++ ~x);
~x = "b";
io.println("2: " ++ ~x);
io.println("3: " ++ ~x);
~x = "c";
io.println("4: " ++ ~x);
io.println("5: " ++ ~x);

0: b
1: b
2: c
3: c
4: a
5: a

The initialization of a normal variable affects accesses on lines before any reassignment of the variable. The initialization of an inverted variable affects accesses on lines after any reassignment of the variable.

Time Travel

At this point, a natural question is: when is this useful?

It turns out that there are many situations where the inverse operator is useful, and allows writing code that could not be expressed without it.

Consider the following function:

fn sub_min(&list: &List[N32]) {
  let min_acc = None[N32];

  let it = list.iter();
  while it.next() is Some(&val) {
    if min_acc is Some(m) => val < m {
      min_acc = Some(val);
    }
  }

  let min = min_acc.unwrap();

  let it = list.iter();
  while it.next() is Some(&val) {
    val -= min
  }
}

This function calculates the minimum of a list of numbers, and subtracts every number in the list by that minimum. For example:

let x = [4, 3, 7, 9];
sub_min(&x);
x // [1, 0, 4, 6]

This function currently iterates over the list twice; once to calculate the minimum, and once to do the subtraction. At a first glance, it looks like there is no way to merge these two loops, because you need to calculate the minimum of all the numbers before you can subtract from any of them.

The only way you could merge these loops is if you could somehow know what the minimum value was before the loop even started.

As it turns out, this is possible, using the inverse operator. Since an inverted variable flows "backwards in time", we can use one to send the minimum values from the end of the loop back to all of the previous iterations of the loop.

fn sub_min(&list: &List[N32]) {
  // our accumulator will still flow forwards, as usual
  let min_acc = None[N32];

  // but we'll have an inverted variable to store the final minimum value
  let ~min: N32;

  let it = list.iter();
  while it.next() is Some(&val) {
    // as we iterate over the list, we update `min_acc` as usual
    if min_acc is Some(m) => val < m {
      min_acc = Some(val);
    }
    
    // but we simultaneously subtract the final minimum from the value
    val -= ~min;
  }

  // now that we know the real minimum, we set the inverted variable,
  // propagating this value back to all of the loop iterations
  ~min = min_acc.unwrap();
}

This is mind-bending to think about, but extremely useful once you get the hang of it!

1

Any value can be considered to be an expectation of an expectation of itself. Consider the value 5. It expects to be used, at some point. Let's call the thing that will use it u. u is expecting an N32. (That expectation will eventually be fulfilled with 5.) Since u is expecting an N32, u is an ~N32. Since 5 is expecting u, and u is an ~N32, 5 is an ~~N32 (in addition to being an N32). Thus, the types N32 and ~~N32 are equivalent.

The Vine Compiler

An introduction to the internals of the Vine compiler. Here be dragons!

Architecture

The cli is the entrypoint to the compiler, and collects all of the compilation options. Most notably, it creates a list of entrypoints, paths to top-level modules (the main module, the standard library, and any third-party libraries).

The loader then takes this list of entrypoints and queries the file system for their contents. It invokes the parser (which in turn invokes the lexer) to parse the file into an AST. The loader then finds any files included in this AST, and recursively loads them. Once this process is complete, the loader returns an AST node representing the entire compilation unit.

The resolver then takes the AST and uses it to build a module graph. The nodes of the module graph are called definitions. Definitions can have different kinds of bindings, usually represented as AST nodes (taken out of the original compilation unit AST). For example, an fn item will have a value binding, and the parameters and body of the function will be represented as AST nodes. The resolver also disambiguates certain AST nodes, e.g. differentiating local variables from constants.

The checker then passes over the module graph and checks the types and forms of all expressions. It also disambiguates AST nodes based on the inferred types and forms; e.g. desugaring method calls and inserting explicit coercions.

The distiller then takes every value binding and distills the AST into Vine Intermediate Representation. VIR is much simpler than the AST; compound expressions are distilled into sequential, atomic steps, and high-level control-flow constructs are distilled into a Stacked Flow Graph.

The normalizer then transforms the VIR to remove all of the divergence.

The analyzer then performs various analyses on the VIR, including reachability analysis, and dataflow analysis (determining which locals are used by which stages, and how).

The emitter then converts the VIR into a collection of Ivy nets.

Stacked Flow Graphs

Many compilers use Control Flow Graphs (CFGs) to represent the control flow of a function. The Vine compiler uses Stacked Flow Graphs (SFGs), an extension of CFGs, a representation that allows for greater parallelization (among other benefits).

Layers, Stages, and Steps

An SFG consists of a forest of layers. Each layer is itself analogous to a CFG, and consists of several stages (analogous to basic blocks in a CFG).

Flow begins in the initial stage of the initial layer. Flow can transfer between layers. Once flow exits a layer, flow returns to the previous layer. This is analogous to a call stack (hence the "stacked" flow graph).

Each stage contains a series of steps. Flow visits each step in a stage sequentially.

A step can:

  • invoke a variable
  • transfer to another layer
  • diverge to an ancestor layer
  • perform a primitive operation, such as constructing a tuple, or calling a function

After the last step of a stage, if the stage has a terminator, flow transfers to another stage in the same layer. Otherwise, flow exits the layer.

Interfaces and Transfers

Every stage has an interface. Within a layer, multiple stages may have the same interface. Every interface has one or more stages; interfaces with exactly one stage are unconditional.

A transfers specifies a target interface. If there are multiple stages with that interface, the transfer must supply a payload which will determine which stage is transferred to. The interface specifies the type of this payload, and how it is used.

For example, a boolean interface has two stages. One stage is associated with a payload of true; the other with false.

Forestry and Divergence

Recall that layers are structured in a forest; the forest has one or more root layers, and every non-root layer has a single parent layer.

When transferring to another layer (i.e. in a transfer step), the target must be in either a root layer, or a child of the current layer.

A step can diverge, causing flow to immediately exit several layers. A diverge step specifies a target ancestor layer, and optionally a stage in that layer. Flow exits layers until it reaches the target ancestor layer. If a stage is specified, flow transfers to that stage; otherwise, the target layer is exited as well.

(Divergence is used to implement features like return, break, and continue. In the 'call stack' analogy, divergence is analogous to throwing an exception that is caught by a function higher up on the stack.)

In Vine, SFGs are normalized before being emitted. Normalization removes all divergence by splitting stages at points where flow may diverge.

Ivy and the IVM

Vine compiles to Ivy, a low-level interaction-combinator programming language.

Ivy code runs on the IVM, a performant interaction combinator runtime.

Ivy Overview

An Ivy program consists of a series of named global nets. The name of a global net must start with ::, and may contain arbitrary identifier characters or additional ::s (e.g. ::foo::bar).

Ivy nets are specified with a syntax based on the interaction calculus; each net has a root tree, attached to its singular free port; any number of pairs of trees; and a wiring specified by pairs of variables.

// definition of the net `::main` (which is the entrypoint of the program)
::main {
  fn(io _) // <-- the root tree, a combinator with label `fn`
  // ^  ^-- eraser node
  // '----- a variable, representing one half of a wire
  io = @io_print_char(::char::i @io_print_char(::char::v _))
  // ^-- pair         ^^^^^^^^^                ^^^^^^^^^
  //             global net reference    extrinsic function node
}

// more global net definitions; here serving the role of constants
::char::i { 105 }
::char::v { 118 }
::char::nl { 10 }
//           ^^-- external value node

See Ivy's Interaction System.

Ivy's Interaction System

Ivy's interaction system is based on the symmetric interaction combinators, with various extensions.

Agent Types

Combinators

Ivy has a (theoretically) unlimited number of binary combinator agent types, each identified with a label. Two combinators of the same label annihilate, whilst two combinators of different labels commute.

Ivy also has an eraser agent, which is a nilary combinator.

Globals

Ivy programs are structured as a collection of named global nets. Each global net corresponds to a nilary global agent. A global agent expands into the corresponding global net when necessary during interaction.

Extrinsics

Extrinsic agents represent entities and operations external to the interaction net.

  • extrinsic values are nilary agents that represent external entities
  • extrinsic functions are n-ary agents that represent external operations
  • extrinsic branches are ternary agents that represent a boolean query on an external entity

Extrinsics are discussed in more detail on the corresponding page.

Interaction Rules

Ivy has 7 categories of interaction rules:

  • Annihilate
  • Commute
  • Copy
  • Erase
  • Expand
  • Call
  • Branch

For combinator agents, the Annihilate, Commute, Copy, and Erase rules behave equivalently to the standard rules for symmetric interaction combinators.

Annihilate

When two non-nilary agents of the same type interact, they annihilate. The wires previously connected to their auxiliary ports are linked together.

Commute

When two non-nilary agents of different types interact, they commute, analogously to interaction combinators.

Copy

When a nilary agent and a non-nilary agent of certain types interact, the nilary agent is copied to each of the non-nilary agent's auxiliary wires. This happens when:

  • the nilary agent is an eraser
  • the nilary agent is an extrinsic value, and the non-nilary agent is a combinator
  • the nilary agent is a global agent, and the non-nilary agent is a combinator of a label that does not appear in the global net (or any global net transitively referenced)

Erase

When two nilary agents interact, they are erased.

Expand

When a global agent interacts with a non-nilary agent, it is expanded (unless the Copy rule above applies). The global agent is simply replaced with the corresponding global net (and the other agent is untouched).

Call

When an extrinsic value interacts with an extrinsic function, the associated operation is performed on the associated entity, and some extrinsic value is returned.

Branch

When an extrinsic value interacts with an extrinsic branch, the associated query is performed on the associated entity. Based on the boolean result, one of the first two auxiliary wires is linked to the third, and the other is connected to an eraser.

Statistics

The IVM collects various statistics during execution. The Vine and Ivy CLIs display these statistics after running a program.

Let's take a look at a sample stat block, section by section.

Interactions

Interactions
  Total           11_106_946
  Annihilate       4_319_083
  Commute             33_750
  Copy             2_378_685
  Erase              315_132
  Expand             556_910
  Call             3_227_767
  Branch             275_619

Total shows the total number of interactions performed in the execution of the program. This measures how much "work" was done, in a deterministic and universal way; the same program will always have the exact same interaction count, no matter what machine it is run on.

The other numbers break down the various types of interactions.

Memory

Memory
  Heap                   784 B
  Allocated      242_850_688 B
  Freed          242_850_688 B

Heap shows the greatest size of the runtime's heap over the course of the program, measured in bytes. In this case, it never needed to use more than a kilobyte of heap space throughout the entire program.

Allocated shows the total number of bytes allocated through the program, and Freed shows the total number of bytes freed. These numbers should always match; if they differ, that indicates that there was a vicious circle in the interaction net.

In this case, Allocated and Freed are much greater than Heap; this shows that the evaluator was reusing its memory buffer very effectively. (This is very common for the IVM.)

These numbers are deterministic when the program is executed sequentially, but can vary when executed in parallel (since the OS's thread scheduling is non-deterministic).

Performance

Performance
  Time                   175 ms
  Speed           63_375_794 IPS

Time is the amount of time elapsed over the execution of the program.

Speed is the speed of the execution, measured in IPS (interactions per second), and equal to Interactions / Time.

Parallel Statistics

Some statistics only apply to parallel execution.

Workload

Workload
  Workers                 16
  Active                  16
  Minimum            312_096
  Average            694_184
  Maximum            855_071
  Moved                  111

Workers is the number of worker threads available to the IVM.

Active is the number of worker threads that were used.

Minimum, Average, and Maximum describe the statistics of the number of interactions performed by each active worker.

Moved is the number of active pairs that were moved between workers.

Performance

Performance
  Time                    19 ms
  Speed          569_167_395 IPS
  Working                230 ms
  Rate            48_201_985 IPS

Time and Speed are the same as in sequential execution.

Working is the total of the amounts of time each worker was active.

Rate is the average speed of an individual worker, and equal to Interactions / Working.

Extrinsics

Extrinsics are how programs running in the IVM interact with the outside world.

An extrinsic value is a nilary agent that represents an external entity. They are opaque to the interaction net, and can only be manipulated and queried via extrinsic functions and extrinsic branches.

An extrinsic function is an agent that represents an external operation. They operate solely on extrinsic values, and return only extrinsic values. Extrinsic functions may have side effects. Extrinsic functions are the only way for the interaction net to manipulate extrinsic values.

An extrinsic branch is a ternary agent that represents a boolean query on an external entity. They query a single extrinsic value, and select one of two branches. Extrinsic branches are the only way for the interaction net to inspect extrinsic values.

Currently, there is a fixed set of extrinsics built-in to IVM. In the future, they will be extensible (#54).

Extrinsic Value Types

N32

An N32 extrinsic value represents a 32-bit natural number. They can be written as integer literals in Ivy programs.

Vine's N32, Char, and Bool types are all represented by N32 extrinsic values.

F32

An F32 extrinsic value represents a 32-bit floating-point number. They can be written as float literals in Ivy programs.

IO

An IO extrinsic value represents an IO handle, and can be used to perform IO. IO values cannot be written in Ivy programs. When an Ivy program is run, the ::main net is connected to an IO value. This is the only way to obtain an IO value.

Extrinsic Functions

General Arithmetic

The @add/@sub/@mul/@div/@rem extrinsic functions perform arithmetic on N32 or F32 values. They input two values and output one. If both inputs are N32s, the output will be an N32; otherwise, the output is an F32.

Comparisons

The @eq/@ne/@lt/@le extrinsic functions take two N32 or two F32 values and return an N32 value representing the result of the comparison (1 for true, and 0 for false).

Specialized Arithmetic

The @n32_shl/@n32_shr/@n32_rotl/@n32_rotr/@n32_and/@n32_or/@n32_xor extrinsic functions take two N32 values, perform a bitwise operation, and output an N32 value.

The @n32_add_high/@n32_mul_high extrinsic functions return the 32 most-significant bits of the 64-bit result of an operation on two N32 values.

IO

The @io_print_char extrinsic functions takes an IO value and an N32 value representing a Unicode scalar value, prints the character to stdout, and returns an IO value.

The @io_print_byte extrinsic function takes an IO value and an N32 value, prints the least-significant byte to stdout, and returns an IO value.

The @io_flush extrinsic function takes an IO value and an N32 value, flushes stdout, discards the N32, and returns an IO value.

The @io_read_byte extrinsic function takes an IO value and an N32 value, reads a byte from stdin, and returns that byte as an N32, or the N32 parameter if no byte could be read.

The @seq extrinsic function takes two extrinsic values and returns the first. It is useful for sequentializing side effects from other extrinsic functions.