Introduction

Dynamic languages such as Python are built on top of an interpreter that is able to understand a broad variety of bytecode instructions allowing them to replicate algorithms and process data. This design makes programs based on interpreter languages well-suited for platform independency and allows fast iterations in development.

lovm2 - love em too - is a small language building framework that comes with a dead-simple stack-based virtual machine written in Rust doing exactly that. Furthermore, it comes with tools for generating said bytecode out of the box allowing you to rapidly prototype your own coding language without a hassle. There are no advanced concepts to care about. No polymorphism, closures, asynchronous runtime... just straightforward functions, variables and data structures.

The static lovm2 library is to tiny that compiling it into your language yields almost no overhead and also makes it applicable for usage inside a Python environment via pylovm2.

The project is in an early development stage and no API is stable yet. Feel free to contribute.

Setup

Modify your Cargo.toml
- Add the latest crates.io version
```
lovm2 = "0.4.6"
```
- ... or - if you feel lucky - use the current master branch directly
```
lovm2 = { git = "https://github.com/lausek/lovm2" }
```
Run cargo update on your terminal
Import the useful lovm2 modules into scope using use lovm2::prelude::*;

Concepts

This chapter aims to give you a brief overview of the internal workings. Even though lovm2 is designed to be as simple as possible, it is still quite important to grasp the implementation concepts behind it.

The general steps of coming to a runnable program are roughly:

Create a new ModuleBuilder and populate it with functions aka. Hir data
Call module_builder.build() consuming the builder and returning a runnable Module
Load the module into an instance of a virtual machine Vm using load_and_import_all
Start the program by calling run on the virtual machine

Bytecode

lovm2 is centered around the value stack. This is where the actual computation happens, parameters are passed to functions and data is shared with interrupts. There are instructions that put values on top of the stack like Pushc, Pushl, and Pushg. Some just take a value off and store it somewhere like Movel, Moveg. Almost all other instructions will take a given amount of values from it and leave a return value in place.

For example, the term 1 + (2 * 3) will be compiled to this sequence:

 instruction    | stack
----------------------------
 Pushc          | [1]
 Pushc          | [1, 2]
 Pushc          | [1, 2, 3]
 Mul            | [1, 6]
 Add            | [7]

You do not need to micromanage the bytecode itself. There are common language constructs with which you can built pretty much everything. These constructs are composed on a function level as Hir so every new function gets its own high-level intermediate representation. Below you can see the transformation process of a function into a runnable CodeObject.

Hir -> Lir -> CodeObject

CodeObject's on their own are already valid programs, but - as usual in every language - functions can be bundled together in some sort of collection - called Module.

Hir -> Lir -> CodeObject
                         \
Hir -> Lir -> CodeObject  --> Module
                         /
Hir -> Lir -> CodeObject

Modules

While you are already familiar with the "lovm2 native" representation of executable code, Modules are far more abstract under the hood. lovm2 is able to load specifically compiled shared objects at runtime and execute real native functions as well.

And that's not all. As long as your structure implements the CallProtocol trait you are free to even implement native functions inside your own compiler.

Types

Simple Types

Bool, Int, Float

Nil is the default return type of functions that do not have return values.

String

Ref

Complex Types

List and Dict are a bit more complicated, because they need to store other values. As such, they support the len, get and set methods.

These types also utilize Ref heavily. If you use the standard lovm2 functionality for generating programs, you will always implicitly work with a Ref to the corresponding data. The virtual machine will also ensure that every value being stored inside these types is itself wrapped up in a reference. This is required for the implementation of slices. The Box instruction implements this functionality.

Conversion

The Cast instruction is able to convert data according to the following rules:

from / to	Nil	Bool	Int	Float	String	List	Dict	Ref
Nil	✓				✓
Bool		✓	✓		✓
Int		✓	✓	✓	✓
Float			✓	✓	✓
String			~	~	✓
List					✓	✓
Dict					✓		✓
Ref					✓			✓

Building Programs

This chapter will show you how to utilize the gen module in order to compile your own lovm2 programs. It is also possible to persist compiled modules onto your disk and load them later.

use lovm2::prelude::*;

fn main() {
let mut builder = ModuleBuilder::new();

// creates the entry point `Hir` and returns a mutable reference.
// this is actually a shortcut for builder.add(ENTRY_POINT)
let main_hir = builder.entry();

// modify `main_hir` with statements
// if in doubt, just call the `step` method and pass it the hir element
main_hir.step(Interrupt::new(10));

let module = builder.build().except("compile error");
println!("{}", module);
}

Functions

The whole ModuleBuilder is centered around the creation of Hir. As we already found out in the Concepts chapter, a Hir is conceptually equal to a function. The resulting bytecode is able to process a given amount of parameters and leave a return value in place.

As you can see in this example listing, you should not need to create such data manually as there is functionality for adding it to the builder directly.

use lovm2::prelude::*;

fn main() {
// creates a hir with no arguments
let fn_no_args = builder.add("fn1");

// creates a hir that expects parameter n
let fn_with_args = builder.add_with_args("fn2", &[lv2_var!(n)]);
}

To return from function, add a Return::value(expr) to the hir specifying the returned value or Return::nil() if no value is produced.

Due to the convention that every function has to return a value, an implicit Return::nil() is appended if the last instruction is not a return already.

Helper Macros

There are a bunch of macros inside the prelude that trivialize creating more complicated lovm2 constructs for developers.

lv2_var!(ident, ...) turns all the identifiers given into the special type Variable which is needed basically everywhere. If more than one ident is declared, this returns a tuple.
lv2_dict!(... ident => expr) creates an Expr that will dynamically initialize a dictionary with the key-values pairs specified.
lv2_list!(... item) creates an Expr that initializes a list dynamically.
lv2_call!(ident, ... args) syntactic sugar for the Call element.
lv2_access!(ident, ... keys) syntactic sugar for the Access element.

Expressions

The Expr represents any computation that leads to a new value on the stack. Expressions can be nested arbitrarily. For example, the formula f(2) * (1 + 2) gets transformed into something like this:

Value(1)
        \
         -- Operation(+)
        /               \
Value(2)                 -- Operation(*)
                        / 
              Call(f, 2)

Note that lovm2 does not care about operator priorities so its your parsers duty to correctly handle them.

To give you an overview of what an expression could look like, here is the stripped down version of its actual implementation.


#![allow(unused)]
fn main() {
pub enum Expr {
    // a constant value
    Value,
    // variable in read position
    Variable,
    // call to a function
    Call,
    // operations with one operand
    Operation1,
    // operations with two operands
    Operation2,
    // result of a type conversion
    Cast,
    // attribute read on a list or dict
    Access,
    // create a mutable subpart of a list
    Slice,
    // special variant for creating lists and dicts
    DynamicValue,
}
}

Assignment

To create or change a local variable, it is sufficient to use this construct:


#![allow(unused)]
fn main() {
Assign::local(&lv2_var!(n), expr)
}

It is possible to manipulate the global context using this variant:


#![allow(unused)]
fn main() {
Assign::global(&lv2_var!(n), expr)
}

There is even a way of setting the values on lists and dictionaries. Under the hood, Set is actually expecting a Ref as the target location - which is retrieved by Access - and overwrites the value inside. This is compatible with the way dictionaries and lists are internally constructed.


#![allow(unused)]
fn main() {
Assign::local(&lv2_var!(point), lv2_dict!());
Assign::set(&lv2_access!(point, x), x_coord);
Assign::set(&lv2_access!(point, y), y_coord);
}

Branching

While working on your functions hir, you can call the .branch() method to create a point of conditional execution.


#![allow(unused)]
fn main() {
let main_hir = builder.entry();

// ...

let equal_check = main_hir.branch();

equal_check
    .add_condition(expr)
    .step(...);

equal_check
    .default_condition()
    .step(...);
}

Repeating

Optimization

The rudimentary bytecode optimizer is enabled by default. It acts upon the generated Lir.

Constant evaluation

Computing constant operations ahead can not only improve the programs performance, but also drop certain constants out of the CodeObject overall therefore reducing its size.

Logical short-curcuit

All languages should not evaluate the second operand of a Or or And operation if the first result is already sufficient for the expressions outcome.

Small adjustments

Virtual Machine

The virtual machine is the heart of lovm2 projects and thrives computation forward. It maintains the whole program state inside a Context and shares said data with every function and module interested in it.

Context

The context stores the programs state.


#![allow(unused)]
fn main() {
pub struct Context {
    /// loaded modules
    pub modules: HashMap<String, Rc<Module>>,
    /// the module that will be run first
    pub entry: Option<Rc<dyn CallProtocol>>,
    /// available functions
    pub scope: HashMap<Variable, CallableRef>,
    /// global variables
    pub globals: HashMap<Variable, Value>,
    /// call stack with local variables
    pub lstack: Vec<Frame>,
    /// value stack
    pub vstack: Vec<Value>,
}
}

Hooks

Load Hook

vm.set_load_hook(callback)

The load hook is a special function bound to the Vm that will be consulted first whenever a module should be loaded into the Context.

If the hook is able to resolve the requested name to a module, it can return

Import Hook

vm.set_import_hook(callback)

The import hook handles the naming of functions being imported into the scope.

Interrupt

vm.set_interrupt(n, callback)

Interrupts are more like a runtime extension of the bytecode. You can use this to implement optional extensions and frequently used functions without the overhead of a name lookup.

The test environment uses Interrupt(10) to analyse the programs state at a certain point of execution.

The lovm2 Guide