---

Introduction​

In today's software world, no programming language ecosystem can be an isolated island. As an emerging general-purpose language, MoonBit's success in the vast technological landscape hinges on its seamless integration with existing ecosystems.

MoonBit provides multiple compilation backends, including JavaScript, which opens the door to the vast JavaScript ecosystem. This integration capability greatly expands MoonBit's application scenarios for both front-end browser development and Node.js applications. It allows developers to leverage the type safety and high performance of MoonBit while reusing a wide range of existing JavaScript libraries.

In this article, using Node.js as our example, we'll explore MoonBit's JavaScript FFI step-by-step. We'll cover various topics from basic function calls to complex type and error handling, demonstrating how to build an elegant bridge between the MoonBit and JavaScript worlds.

Prerequisites​

Before we begin, let's configure our project. If you don't have an existing project, you can use the moon new tool to create a new MoonBit project.

To let the MoonBit toolchain know that our target platform is JavaScript, we need to add the following content to the moon.mod.json file in the project's root directory:

{
  "preferred-target": "js"
}

This configuration tells the compiler to use the JavaScript backend by default when executing commands like moon build or moon check. Of course, if you want to specify it temporarily on the command line, you can achieve the same effect with the --target=js option.

Building the Project​

After completing the above configuration, simply run the familiar build command in the project's root directory:

> moon build

After the command executes successfully, since our project includes an executable entry by default, you can find the build artifacts in the target/js/debug/build/ directory. MoonBit conveniently generates three files for us:

• .js file: The compiled JavaScript source code.
• .js.map file: A Source Map file for debugging.
• .d.ts file: A TypeScript declaration file, which is convenient for integration into TypeScript projects.

First JavaScript API Call​

MoonBit's FFI design is principled and consistent. Similar to calling into C or other languages, we define an external function through a declaration with the extern keyword:

extern "js" fn consoleLog(msg : String) -> Unit = "(msg) => console.log(msg)"

This line of code is the core of enabling our FFI call. Let's break it down:

• extern "js": Declares that this is an external function pointing to the JavaScript environment.

• fn consoleLog(msg : String) -> Unit: This is the function's type signature in MoonBit. It accepts a parameter of type String and returns a unit value (Unit).

• "(msg) => console.log(msg)": The string literal on the right side of the equals sign is the essence of this declaration, containing the native JavaScript function to be executed.

  Here, we use a concise arrow function. The MoonBit compiler will embed this code as is into the final generated .js file, enabling the call from MoonBit to JavaScript.

  Tip If your JavaScript code snippet is relatively complex, you can use the #| syntax to define multi-line strings to improve readability.

Once this FFI declaration is ready, we can call consoleLog in our MoonBit code just like a normal function:

test "hello" {
  consoleLog("Hello from JavaScript!")
}

Run moon test, and you will see the message printed by JavaScript's console.log in the console. Our first bridge is successfully built!

Interfacing with JavaScript Types​

Establishing the call flow is just the first step. The real challenge lies in handling type differences between the two languages. MoonBit is a statically typed language, while JavaScript is dynamically typed. Establishing a safe and reliable type mapping between them is a key consideration in FFI design.

Below, we'll cover how to interface with different JavaScript types in MoonBit, starting from the easiest cases.

JavaScript Types Requiring No Conversion​

The simplest case involves types in MoonBit whose underlying compiled representation in JavaScript corresponds directly to a native JavaScript type. In this case, we can pass them directly without any conversion.

The common "zero-cost" interface types are shown below:

MoonBit Type	Corresponding JavaScript Type
String	string
Bool	boolean
Int, UInt, Float, Double	number
BigInt	bigint
Bytes	Uint8Array
Array[T]	Array<T>
Function Type	Function

Based on these mappings, we can bind many simple JavaScript functions. In fact, in the previous example of binding the console.log function, we have already used the correspondence between the String type in MoonBit and the string type in JavaScript.

Note: Maintaining the Internal Invariants of MoonBit Types

A crucial detail is that all of MoonBit's standard numeric types (Int, Float, etc.) map to the number type in JavaScript, i.e., IEEE 754 double-precision floating-point numbers. This means that when an integer value crosses the FFI boundary into JavaScript, its behavior will follow floating-point semantics, which may lead to unexpected results from MoonBit's perspective, such as differences in integer overflow behavior:

extern "js" fn incr(x : Int) -> Int = "(x) => x + 1"

test "incr" {
  // In MoonBit, @int.max_value + 1 will overflow and wrap around
  inspect(@int.max_value + 1, content="-2147483648")
  // In JavaScript, it is treated as a floating-point number and does not overflow
  inspect(incr(@int.max_value), content="2147483648") // ???
}

This is essentially illegal because, according to the internal invariant of the Int type in MoonBit, its value cannot be 2147483648 (which exceeds the maximum value allowed by the type). This may cause unexpected behavior in other MoonBit code downstream that relies on this point. Similar issues may arise when handling other data types across the FFI boundary, so please be sure to pay attention to this when writing related logic.

External JavaScript Types​

Of course, the JavaScript world is much richer than these basic types. We will quickly encounter undefined, null, symbol, and various complex host objects, which have no direct counterparts in MoonBit.

For this situation, MoonBit provides the #external annotation. This annotation acts as a contract, telling the compiler: "Please trust me, this type actually exists in the external world (JavaScript). You don't need to care about its internal structure, just treat it as an opaque handle."

For example, we can define a type that represents JavaScript's undefined like this:

#external
type Undefined

extern "js" fn Undefined::new() -> Self = "() => undefined"

However, a standalone Undefined type isn't very useful, as undefined typically appears as part of a union type, like string | undefined.

A more practical approach is to create an Optional[T] type that precisely maps to T | undefined in JavaScript, and which can be easily converted to and from MoonBit's built-in Option[T] (aliased as T?).

To achieve this, we first need a type to represent any JavaScript value, similar to TypeScript's any. This is where #external is useful:

#external
pub type Value

Consequently, we need methods to get the undefined value and to check if a given value is undefined:

extern "js" fn Value::undefined() -> Value =
  #| () => undefined

extern "js" fn Value::is_undefined(self : Self) -> Bool =
  #| (n) => Object.is(n, undefined)

For easier debugging, we'll implement the Show trait for our Value type, allowing it to be printed:

pub impl Show for Value with output(self, logger) {
  logger.write_string(self.to_string())
}

pub extern "js" fn Value::to_string(self : Value) -> String =
  #| (self) =>
  #|   self === undefined ? 'undefined'
  #|     : self === null ? 'null'
  #|     : self.toString()

Next comes the 'magic' of the conversion process. We'll define two special conversion functions:

fn[T] Value::cast_from(value : T) -> Value = "%identity"

fn[T] Value::cast(self : Self) -> T = "%identity"

What is %identity

%identity is a special intrinsic provided by MoonBit for zero-cost type casting. It performs type checking at compile time, but has no effect at runtime. It essentially tells the compiler: "Trust me, I know the real type of this value; just treat it as the target type."

This is a double-edged sword: it provides powerful expressiveness at the FFI boundary, but misuse can break type safety. Therefore, its use should be strictly limited to a FFI-related scope.

With these building blocks, we can construct Optional[T]:

#external
type Optional[_] // Corresponds to T | undefined

/// Create an undefined Optional
fn[T] Optional::undefined() -> Optional[T] {
  Value::undefined().cast()
}

/// Check if an Optional is undefined
fn[T] Optional::is_undefined(self : Optional[T]) -> Bool {
  self |> Value::cast_from |> Value::is_undefined
}

/// Unwrap T from Optional[T], panic if it is undefined
fn[T] Optional::unwrap(self : Self[T]) -> T {
  guard !self.is_undefined() else { abort("Cannot unwrap an undefined value") }
  Value::cast_from(self).cast()
}

/// Convert Optional[T] to MoonBit's built-in T?
fn[T] Optional::to_option(self : Optional[T]) -> T? {
  guard !Value::cast_from(self).is_undefined() else { None }
  Some(Value::cast_from(self).cast())
}

/// Create Optional[T] from MoonBit's built-in T?
fn[T] Optional::from_option(value : T?) -> Optional[T] {
  guard value is Some(v) else { Optional::undefined() }
  Value::cast_from(v).cast()
}

test "Optional from and to Option" {
  let optional = Optional::from_option(Some(3))
  inspect(optional.unwrap(), content="3")
  inspect(optional.is_undefined(), content="false")
  inspect(optional.to_option(), content="Some(3)")
  let optional : Optional[Int] = Optional::from_option(None)
  inspect(optional.is_undefined(), content="true")
  inspect(optional.to_option(), content="None")
}

With this setup, we've successfully crafted a safe and ergonomic representation for T | undefined within MoonBit's type system. The same method can also be used to interface with other JavaScript-specific types like null, symbol, RegExp, etc.

Handling JavaScript Errors​

A robust FFI layer must handle errors gracefully. By default, if JavaScript code throws an exception during an FFI call, it won't be caught by MoonBit's try-catch mechanism. Instead, it will crash the entire program:

// This is an FFI call that will throw an exception
extern "js" fn boom_naive() -> Value raise = "(u) => undefined.toString()"

test "boom_naive" {
  // This code will directly crash the test process instead of returning a `Result` via `try?`
  inspect(try? boom_naive()) // failed: TypeError: Cannot read properties of undefined (reading 'toString')
}

The correct approach is to wrap the call in a try...catch block on the JavaScript side, and then pass either the successful result or the caught error back to MoonBit. While we could do this directly in the JavaScript code of our extern "js" declaration, a more reusable solution exists:

First, let's define an Error_ type to encapsulate JavaScript errors:

suberror Error_ Value

pub impl Show for Error_ with output(self, logger) {
  logger.write_string("@js.Error: ")
  let Error_(inner) = self
  logger.write_object(inner)
}

Next, we'll define a core FFI wrapper function, Error_::wrap_ffi. Its role is to execute an operation (op) in the JavaScript realm and, depending on the outcome, call either a success (on_ok) or error (on_error) callback:

extern "js" fn Error_::wrap_ffi(
  op : () -> Value,
  on_ok : (Value) -> Unit,
  on_error : (Value) -> Unit,
) -> Unit =
  #| (op, on_ok, on_error) => { try { on_ok(op()); } catch (e) { on_error(e); } }

Finally, using this FFI function and MoonBit closures, we can create a more idiomatic Error_::wrap function that returns a T raise Error_:

fn[T] Error_::wrap(
  op : () -> Value,
  map_ok~ : (Value) -> T = Value::cast,
) -> T raise Error_ {
  // Define a variable to pass the result in and out of the closure
  let mut res : Result[Value, Error_] = Ok(Value::undefined())
  // Call the FFI, passing two closures that will modify the value of res based on the JS execution result
  Error_::wrap_ffi(op, fn(v) { res = Ok(v) }, fn(e) { res = Err(Error_(e)) })
  // Check the value of res and return the corresponding result or throw an error
  match res {
    Ok(v) => map_ok(v)
    Err(e) => raise e
  }
}

Now, we can safely call the function that previously threw an exception, and we can handle possible errors with pure MoonBit code:

extern "js" fn boom() -> Value = "(u) => undefined.toString()"

test "boom" {
  let result = try? Error_::wrap(boom)
  inspect(
    (result : Result[Value, Error_]),
    content="Err(@js.Error: TypeError: Cannot read properties of undefined (reading 'toString'))",
  )
}

Interfacing with External JavaScript APIs​

Having mastered the key techniques for bridging types and handling errors, it's time to turn our attention to the wider world: the Node.js and NPM ecosystem. The entry point to all of it is a binding for the require() function:

extern "js" fn require_ffi(path : String) -> Value = "(path) => require(path)"

/// A more convenient wrapper that supports chained property access, e.g., require("a", keys=["b", "c"])
pub fn require(path : String, keys~ : Array[String] = []) -> Value {
  keys.fold(init=require_ffi(path), Value::get_with_string)
}

// ... where the definition of Value::get_with_string is as follows:

fn[T] Value::get_with_string(self : Self, key : String) -> T {
  self.get_ffi(Value::cast_from(key)).cast()
}

extern "js" fn Value::get_ffi(self : Self, key : Self) -> Self = "(obj, key) => obj[key]"

With this require function, we can easily load Node.js's built-in modules, such as the node:path module, and call its methods:

// Load the basename function of the node:path module
let basename : (String) -> String = require("node:path", keys=["basename"]).cast()

test "require Node API" {
  inspect(basename("/foo/bar/baz/asdf/quux.html"), content="quux.html")
}

More excitingly, we can use the same method to call the vast collection of third-party libraries on NPM. Let's take a popular statistical calculation library simple-statistics as an example.

First, we need to initialize package.json and install dependencies, just like in a standard JavaScript project. Here we use pnpm, you can also use npm or yarn:

> pnpm init
> pnpm install simple-statistics

Once the preparation is complete, we can directly require this library in our MoonBit code and get the standardDeviation function from it:

let standard_deviation : (Array[Double]) -> Double = require(
  "simple-statistics",
  keys=["standardDeviation"],
).cast()

Now, whether we use moon run or moon test, MoonBit can correctly load dependencies via Node.js and execute the code, returning the expected result.

test "require external lib" {
  inspect(standard_deviation([2, 4, 4, 4, 5, 5, 7, 9]), content="2")
}

This is quite powerful: with just a few lines of FFI code, we've connected MoonBit's type-safe world with NPM's vast and mature ecosystem.

Conclusion​

In this article, we've explored the fundamentals of interacting with JavaScript in MoonBit, from the most basic type interfacing to complex error handling, and finally to the easy integration of external libraries. These features bridge the gap between MoonBit's static type system and JavaScript's dynamic typing, reflecting a modern approach to cross-language interoperability, while allowing developers to enjoy the type safety and modern features of MoonBit while seamlessly accessing the vast JavaScript ecosystem, opening up immense application prospects.

Of course, with great power comes great responsibility. While the FFI is powerful, we must handle type conversions and error boundaries carefully to ensure program robustness.

Mastering these FFI techniques is a crucial skill for developers wanting to extend MoonBit applications with JavaScript libraries. By applying these techniques, we can build high-quality applications that leverage both the strengths of MoonBit and the rich resources of the JavaScript ecosystem.

To learn more about MoonBit's ongoing progress in JavaScript interoperability, please check out the web frontend of mooncakes.io and its underlying UI library, rabbit-tea, both built with MoonBit.

Regular expression engines can be implemented using fundamentally different approaches, each with distinct trade-offs in performance, memory usage, and implementation complexity. This article explores two mathematically equivalent but practically different methods for regex matching: Brzozowski derivatives and Thompson's virtual machine approach.

Both methods operate on the same abstract syntax tree representation, providing a unified foundation for direct performance comparison. The key insight is how these seemingly different approaches solve identical problems through different computational strategies—one through algebraic transformation, the other through program execution.

Conventions & Definitions​

To establish a common foundation, both regex engines start with a shared AST representation that captures the essential structure of regular expressions in a tree format:

enum Ast {
  Chr(Char)
  Seq(Ast, Ast)
  Rep(Ast, Int?)
  Opt(Ast)
} derive(Show, Hash, Eq)

Additionally, we provide smart constructors to simplify regex construction:

fn Ast::chr(chr : Char) -> Ast {
  Chr(chr)
}

fn Ast::seq(self : Ast, other : Ast) -> Ast {
  Seq(self, other)
}

fn Ast::rep(self : Ast, n? : Int) -> Ast {
  Rep(self, n)
}

fn Ast::opt(self : Ast) -> Ast {
  @fs.
  Opt(self)
}

The AST defines four fundamental regex operations:

1. Chr(Char) matches a single literal character.
2. Seq(Ast, Ast) matches one pattern followed by another through concatenation.
3. Rep(Ast, Int?) repeats a pattern either unlimited times when None or exactly n times when Some(n).
4. Opt(Ast) makes a pattern optional, equivalent to pattern? in standard regex syntax.

For example, we can build the regex (ab*)?—an optional sequence of 'a' followed by zero or more 'b's—as:

Ast::chr('a').seq(Ast::chr('b').rep()).opt()

Brzozowski Derivative​

The derivative-based approach transforms regular expressions algebraically using formal language theory. For each input character, it computes the "derivative" of the regex by asking: "what remains to be matched after consuming this character?" This creates a new regex representing the remaining pattern.

We extend the basic Ast type to represent derivatives and nullability explicitly:

enum Exp {
  Nil
  Eps
  Chr(Char)
  Alt(Exp, Exp)
  Seq(Exp, Exp)
  Rep(Exp)
} derive(Show, Hash, Eq, Compare)

The constructors in Exp represent:

1. Nil represents an impossible pattern that can never match anything.
2. Eps matches the empty string.
3. Chr(Char) matches a single character.
4. Alt(Exp, Exp) represents alternation, providing choice between patterns.
5. Seq(Exp, Exp) represents concatenation of two patterns.
6. Rep(Exp) represents repetition of a pattern.

We use the Exp::of_ast function to convert the Ast into the more expressive Exp format:

fn Exp::of_ast(ast : Ast) -> Exp {
  match ast {
    Chr(c) => Chr(c)
    Seq(a, b) => Seq(Exp::of_ast(a), Exp::of_ast(b))
    Rep(a, None) => Rep(Exp::of_ast(a))
    Rep(a, Some(n)) => {
      let sec = Exp::of_ast(a)
      let mut exp = sec
      for _ in 1..<n {
        exp = Seq(exp, sec)
      }
      exp
    }
    Opt(a) => Alt(Exp::of_ast(a), Eps)
  }
}

We also provide smart constructors for Exp to simplify pattern building:

fn Exp::seq(a : Exp, b : Exp) -> Exp {
  match (a, b) {
    (Nil, _) | (_, Nil) => Nil
    (Eps, b) => b
    (a, Eps) => a
    (a, b) => Seq(a, b)
  }
}

However, the smart constructor for Alt is strictly necessary—it ensures that the constructed Exp is normalized to "similarity" as mentioned in the original paper by Brzozowski. Two regexes are similar if one can be reduced to the other by applying the following rules:

$$\begin{align} & A \mid \emptyset &&\rightarrow A \\ & A \mid B &&\rightarrow B \mid A \\ & A \mid (B \mid C) &&\rightarrow (A \mid B) \mid C \end{align}$$

Therefore, we normalize the Alt construction to always use the same associativity and order of alternatives:

fn Exp::alt(a : Exp, b : Exp) -> Exp {
  match (a, b) {
    (Nil, b) => b
    (a, Nil) => a
    (Alt(a, b), c) => a.alt(b.alt(c))
    (a, b) => {
      if a == b {
        a
      } else if a > b {
        Alt(b, a)
      } else {
        Alt(a, b)
      }
    }
  }
}

The nullable function determines if a pattern can match the empty string without consuming input:

fn Exp::nullable(self : Exp) -> Bool {
  match self {
    Nil => false
    Eps => true
    Chr(_) => false
    Alt(l, r) => l.nullable() || r.nullable()
    Seq(l, r) => l.nullable() && r.nullable()
    Rep(_) => true
  }
}

The deriv function computes the derivative of a pattern with respect to a character, transforming the pattern based on the rules defined in the Brzozowski derivative. We have reordered the rules to match the order in the deriv function:

$$\begin{align} D_{a} \emptyset &= \emptyset \\ D_{a} \epsilon &= \emptyset \\ D_{a} a &= \epsilon \\ D_{a} b &= \emptyset & \text{ for }(a \neq b) \\ D_{a} (P \mid Q) &= (D_{a} P) \mid (D_{a} Q) \\ D_{a} (P \cdot Q) &= (D_{a} P \cdot Q) \mid (\nu(P) \cdot D_{a} Q) \\ D_{a} (P\ast) &= D_{a} P \cdot P\ast \\ \end{align}$$

fn Exp::deriv(self : Exp, c : Char) -> Exp {
  match self {
    Nil => self
    Eps => Nil
    Chr(d) if d == c => Eps
    Chr(_) => Nil
    Alt(l, r) => l.deriv(c).alt(r.deriv(c))
    Seq(l, r) => {
      let dl = l.deriv(c)
      if l.nullable() {
        dl.seq(r).alt(r.deriv(c))
      } else {
        dl.seq(r)
      }
    }
    Rep(e) => e.deriv(c).seq(self)
  }
}

To simplify our implementation, we only perform strict matching—the pattern must match the entire input string. Therefore, we only check for nullability after the entire input has been consumed:

fn Exp::matches(self : Exp, s : String) -> Bool {
  loop (self, s.view()) {
    (Nil, _) => {
      return false
    }
    (e, []) => {
      return e.nullable()
    }
    (e, [c, .. s]) => {
      continue (e.deriv(c), s)
    }
  }
}

Virtual Machine​

The VM approach compiles regular expressions into bytecode instructions for a simple virtual machine. This method transforms the pattern-matching problem into program execution, where the VM simulates all possible paths through a non-deterministic finite automaton simultaneously.

Ken Thompson's 1968 paper described a regex engine that compiled patterns into IBM 7094 machine code. The key insight was to avoid exponential backtracking by maintaining multiple execution threads that advance through input in lockstep, processing one character at a time across all possible matching paths.

Instruction Set and Program Representation​

The VM operates on four fundamental instructions that correspond to NFA operations:

enum Ops {
  Done
  Char(Char)
  Jump(Int)
  Fork(Int)
} derive(Show)

Each instruction serves a specific purpose in NFA simulation. Done marks successful completion of pattern matching, equivalent to Thompson's original match. Char(c) consumes input character c and advances to the next instruction. Jump(addr) provides unconditional jump to instruction at address addr (Thompson's jmp). Fork(addr) creates two execution paths—one continues to the next instruction, another jumps to addr (Thompson's split).

The Fork instruction is crucial for handling non-determinism in patterns like alternation and repetition, where multiple execution paths must be explored simultaneously. This maps directly to NFA ε-transitions, where execution can spontaneously branch without consuming input.

We define a Prg that wraps an array of instructions with convenience methods for building and manipulating bytecode programs.

struct Prg(Array[Ops]) derive(Show)

fn Prg::push(self : Prg, inst : Ops) -> Unit {
  self.0.push(inst)
}

fn Prg::length(self : Prg) -> Int {
  self.0.length()
}

fn Prg::op_set(self : Prg, index : Int, inst : Ops) -> Unit {
  self.0[index] = inst
}

AST Compilation to Bytecode​

The Prg::of_ast function translates AST patterns into VM instructions using standard NFA construction techniques:

1. Seq(a, b):

   code for a
   code for b

2. Rep(a, None) (unbounded repetition):

       Fork L1, L2
   L1: code for a
       Jump L1
   L2:

3. Rep(a, Some(n)) (fixed repetition):

   code for a
   code for a
   ... (n times) ...

4. Opt(a) (optional):

       Fork L1, L2
   L1: code for a
   L2:

Note that the Fork constructor only accepts one address, because we always want to proceed to the next instruction after the Fork.

fn Prg::of_ast(ast : Ast) -> Prg {
  fn compile(prog : Prg, ast : Ast) -> Unit {
    match ast {
      Chr(chr) => prog.push(Char(chr))
      Seq(l, r) => {
        compile(prog, l)
        compile(prog, r)
      }
      Rep(e, None) => {
        let fork = prog.length()
        prog.push(Fork(0))
        compile(prog, e)
        prog.push(Jump(fork))
        prog[fork] = Fork(prog.length())
      }
      Rep(e, Some(n)) =>
        for _ in 0..<n {
          compile(prog, e)
        }
      Opt(e) => {
        let fork_inst = prog.length()
        prog.push(Fork(0))
        compile(prog, e)
        prog[fork_inst] = Fork(prog.length())
      }
    }
  }

  let prog : Prg = []
  compile(prog, ast)
  prog.push(Done)
  prog
}

VM Execution Loop​

In Rob Pike's implementation, the VM executes one-past the end of the input string to handle the final acceptance state. To make this explicit, our matches function implements the core VM execution loop using a two-phase approach:

Phase 1 handles character processing. For each input character, it processes all active threads in the current context. Char instructions that match the current character create new threads in the next context. Jump and Fork instructions immediately spawn new threads in the current context. After processing all threads, it swaps contexts and continues with the next character.

Phase 2 handles final acceptance. After consuming all input, it processes remaining threads looking for Done instructions. It handles any final Jump/Fork instructions that don't consume input. It returns true if any thread reaches a Done instruction.

fn Prg::matches(self : Prg, data : @string.View) -> Bool {
  let Prg(prog) = self
  let mut curr = Ctx::new(prog.length())
  let mut next = Ctx::new(prog.length())
  curr.add(0)
  for c in data {
    while curr.pop() is Some(pc) {
      match prog[pc] {
        Done => ()
        Char(char) if char == c => {
          next.add(pc + 1)
        }
        Jump(jump) =>
          curr.add(jump)
        Fork(fork) => {
          curr.add(fork)
          curr.add(pc + 1)
        }
        _ => ()
      }
    }
    let temp = curr
    curr = next
    next = temp
    next.reset()
  }
  while curr.pop() is Some(pc) {
    match prog[pc] {
      Done => return true
      Jump(x) => curr.add(x)
      Fork(x) => {
        curr.add(x)
        curr.add(pc + 1)
      }
      _ => ()
    }
  }
  false
}

In the original blog post, Rob Pike uses a recursive function to handle Fork and Jump instructions so that threads are executed according to their priorities. Instead, we use a stack-like structure to manage all threads of execution, which naturally respects thread priority:

struct Ctx {
  deque : @deque.Deque[Int]
  visit : FixedArray[Bool]
}

fn Ctx::new(length : Int) -> Ctx {
  { deque: @deque.new(), visit: FixedArray::make(length, false) }
}

fn Ctx::add(self : Ctx, pc : Int) -> Unit {
  if !self.visit[pc] {
    self.deque.push_back(pc)
    self.visit[pc] = true
  }
}

fn Ctx::pop(self : Ctx) -> Int? {
  match self.deque.pop_back() {
    Some(pc) => {
      self.visit[pc] = false
      Some(pc)
    }
    None => None
  }
}

fn Ctx::reset(self : Ctx) -> Unit {
  self.deque.clear()
  self.visit.fill(false)
}

The visit array is used to drop low-priority threads. When a new thread is added, we first check if it is already in the deque using the visit array. If it is, we drop it; otherwise, we add it to the deque and mark it as visited. This mechanism is necessary to avoid infinite loops or exponential blowup when the regex contains patterns that can be expanded indefinitely, such as (a?)*.

Benchmarks and Performance Analysis​

The benchmark demonstrates both approaches on a pathological case that challenges many regex implementations:

test (b : @bench.T) {
  let n = 15
  let txt = "a".repeat(n)
  let chr = Ast::chr('a')
  let ast : Ast = chr.opt().rep(n~).seq(chr.rep(n~))
  let exp = Exp::of_ast(ast)
  b.bench(name="derive", () => exp.matches(txt) |> ignore())
  let tvm = Prg::of_ast(ast)
  b.bench(name="thompson", () => tvm.matches(txt) |> ignore())
}

This pattern (a?){n}a{n} represents a classical exponential blowup case for backtracking engines. The pattern allows n different ways to match n 'a' characters, creating exponential search spaces in naive implementations.

name     time (mean ± σ)         range (min … max)
derive     41.78 µs ±   0.14 µs    41.61 µs …  42.13 µs  in 10 ×   2359 runs
thompson   12.79 µs ±   0.04 µs    12.74 µs …  12.84 µs  in 10 ×   7815 runs

The benchmark results show that the VM approach is significantly faster than the derivative-based approach for this case. The derivative method frequently allocates intermediate regex structures, leading to higher overhead and slower performance. In contrast, the VM executes a fixed set of instructions and rarely allocates new structures once the deque grows to its full size.

However, the derivative approach is easier to reason about. We can easily prove termination of the algorithm, as the number of derivatives to be computed is bounded by the size of the AST and strictly decreases with each recursive application of the deriv function. The VM approach, on the other hand, can potentially run indefinitely if the input Prg contains infinite loops, and requires careful handling of thread priority to avoid infinite loops and exponential blowup in the number of threads.

When working with structured data, printing it in a clear and adaptable format is a common challenge. This comes up often in debugging, logging, and code generation. For instance, an array literal [a,b,c] should ideally print on one line if the screen is wide enough, but gracefully wrap and indent when space is limited.

Traditional solutions often rely on manually concatenating strings while tracking indentation levels. This approach is not only tedious, but also error-prone.

A more elegant solution is to use function composition. With this approach, we build a prettyprinter: a system where users combine primitive formatting functions into a Doc structure that describes the intended layout. Given a maximum width, the prettyprinter automatically chooses the most readable formatting.

This makes the printing process declarative—you specify what the layout should look like under different conditions, and the system figures out how to render it.

SimpleDoc Primitives

We begin with a minimal representation called SimpleDoc. It consists of just four primitives:

enum SimpleDoc {
  Empty
  Line
  Text(String)
  Cat(SimpleDoc, SimpleDoc)
}

• Empty: represents an empty string
• Line: represents a newline
• Text(String): plain text without line breaks
• Cat(SimpleDoc, SimpleDoc): concatenates two SimpleDocss

Using these primitives, we can implement a simple rendering function. It flattens a SimpleDoc into a string using a stack-based traversal:

fn SimpleDoc::render(doc : SimpleDoc) -> String {
  let buf = StringBuilder::new()
  let stack = [doc]
  while stack.pop() is Some(doc) {
    match doc {
      Empty => ()
      Line => {
        buf..write_string("\n")
      }
      Text(text) => {
        buf.write_string(text)
      }
      Cat(left, right) =>
        stack..push(right)..push(left)
    }
  }
  buf.to_string()
}

Here’s a quick test: we can see that the expressiveness of SimpleDoc is equivalent to String: Empty corresponds to "", Line corresponds to "\n", Text("a") corresponds to "a", and Cat(Text("a"), Text("b")) corresponds to "a" + "b".

test "simple doc" {
  let doc : SimpleDoc = Cat(Text("hello"), Cat(Line, Text("world")))
  inspect(
    doc.render(),
    content=(
      #|hello
      #|world
    ),
  )
}

At this stage, the SimpleDoc doesn’t yet handle indentation or layout choices—but we’re about to fix that.

ExtendDoc: Nest, Choice, Group

To handle real-world formatting, we extend SimpleDoc with three new primitives:

enum ExtendDoc {
  Empty
  Line
  Text(String)
  Cat(ExtendDoc, ExtendDoc)
  Nest(Int, ExtendDoc)
  Choice(ExtendDoc, ExtendDoc)
  Group(ExtendDoc)
}

• Nest Nest(Int, ExtendDoc) indents the doc by n spaces after each line break. Nested levels accumulate.

• Choice Choice(ExtendDoc, ExtendDoc) stores two alternative layouts. Usually, the first parameter is the more compact layout without line breaks, and the second is the layout with Lines. The renderer uses the first layout in compact mode and the second otherwise.

• Group Group(ExtendDoc) groups an ExtendDoc and decides between compact or non-compact layout based on the available width. If the remaining space is sufficient, it prints compactly; otherwise, it falls back to the layout with line breaks.

Measuring Space​

To know whether compact layout fits, we need a way to estimate how many characters a document would require:

let max_space = 9999

fn ExtendDoc::space(self : Self) -> Int {
  match self {
    Empty => 0
    Line => max_space
    Text(str) => str.length()
    Cat(a, b) => a.space() + b.space()
    Nest(_, a) | Choice(a, _) | Group(a) => a.space()
  }
}

Here, Line is treated as requiring “infinite” space. This guarantees that if a Group contains a line break, it won’t attempt to print compactly.

Rendering ExtendDoc​

We extend SimpleDoc::render to implement ExtendDoc::render. Since after printing a substructure we need to return to the original indentation level, the stack must also store two states for each pending ExtendDoc: indentation and whether compact mode is active. We also maintain a column variable to track the number of characters already used on the current line, in order to calculate remaining space. Finally, the function adds a width parameter to specify the maximum line width.

fn ExtendDoc::render(doc : ExtendDoc, width~ : Int = 80) -> String {
  let buf = StringBuilder::new()
  let stack = [(0, false, doc)] // default: no indentation, non-compact mode
  let mut column = 0
  while stack.pop() is Some((indent, fit, doc)) {
    match doc {
      Empty => ()
      Line => {
        buf..write_string("\n")
        for _ in 0..<indent {
          buf.write_string(" ")
        }
        column = indent
      }
      Text(text) => {
        buf.write_string(text)
        column += text.length()
      }
      Cat(left, right) =>
        stack..push((indent, fit, right))..push((indent, fit, left))
      Nest(n, doc) => stack..push((indent + n, fit, doc))
      Choice(a, b) =>
        stack.push(if fit { (indent, fit, a) } else { (indent, fit, b) })
      Group(doc) => {
        let fit = fit || column + doc.space() <= width
        stack.push((indent, fit, doc))
      }
    }
  }
  buf.to_string()
}

Let’s use ExtendDoc to describe a (expr) and print it under different width:

let softline : ExtendDoc = Choice(Empty, Line)

impl Add for ExtendDoc with op_add(a, b) {
  Cat(a, b)
}

test "tuple" {
  let tuple : ExtendDoc = Group(
    Text("(") + Nest(2, softline + Text("expr")) + softline + Text(")"),
  )
  inspect(tuple.render(width=40), content="(expr)")
  inspect(
    tuple.render(width=5),
    content=(
      #|(
      #|  expr
      #|)
    ),
  )
}

Here, softline is defined as a choice between Empty and Line. Since rendering starts in non-compact mode, we wrap the whole expression with Group. When the width is sufficient, the entire expression prints on one line; otherwise, it automatically wraps with indentation. To improve readability, we overloaded the + operator for ExtendDoc.

Composition Functions

In practice, users rely more on higher-level combinators built from the ExtendDoc primitives—like the softline above. Let’s introduce some useful functions for structured printing.

softline & softbreak​

let softbreak : ExtendDoc = Choice(Text(" "), Line)

Similar to softline, except that in compact mode it inserts a space. Note that within the same Group, all Choices follow the same compact or non-compact decision.

let abc : ExtendDoc = Text("abc")
let def : ExtendDoc = Text("def")
let ghi : ExtendDoc = Text("ghi")

test "softbreak" {
  let doc : ExtendDoc = Group(abc + softbreak + def + softbreak + ghi)
  inspect(doc.render(width=20), content="abc def ghi")
  inspect(
    doc.render(width=10),
    content=(
      #|abc
      #|def
      #|ghi
    ),
  )
}

autoline & autobreak​

let autoline : ExtendDoc = Group(softline)
let autobreak : ExtendDoc = Group(softbreak)

autoline and autobreak make sure the ExtendDocs fit as much as possible on one line, like text editors do.

test {
  let doc : ExtendDoc = Group(
    abc + autobreak + def + autobreak + ghi,
  )
  inspect(doc.render(width=10), content="abc def ghi")
  inspect(
    doc.render(width=5),
    content=(
      #|abc def
      #|ghi
    ),
  )
  inspect(
    doc.render(width=3),
    content=(
      #|abc
      #|def
      #|ghi
    ),
  )
}

sepby​

fn sepby(xs : Array[ExtendDoc], sep : ExtendDoc) -> ExtendDoc {
  match xs {
    [] => Empty
    [x, .. xs] => xs.fold(init=x, (a, b) => a + sep + b)
  }
}

sepby inserts a separator sep between ExtendDocs.

let comma : ExtendDoc = Text(",")
test {
  let layout = Group(sepby([abc, def, ghi], comma + softbreak))
  inspect(layout.render(width=40), content="abc, def, ghi")
  inspect(
    layout.render(width=10),
    content=(
      #|abc,
      #|def,
      #|ghi
    ),
  )
}

surround​

fn surround(m : ExtendDoc, l : ExtendDoc, r : ExtendDoc) -> ExtendDoc {
  l + m + r
}

surround wraps an ExtendDoc with left and right delimiters.

test {
  inspect(surround(abc, Text("("), Text(")")).render(), content="(abc)")
}

Printing JSON

Using the functions above, we can implement a JSON prettyprinter. This function recursively processes each JSON element and generates the appropriate layout.

fn pretty(x : Json) -> ExtendDoc {
  fn comma_list(xs, l, r) {
    (Nest(2, softline + sepby(xs, comma + softbreak)) + softline)
    |> surround(l, r)
    |> Group
  }

  match x {
    Array(elems) => {
      let elems = elems.iter().map(pretty).collect()
      comma_list(elems, Text("["), Text("]"))
    }
    Object(pairs) => {
      let pairs = pairs
        .iter()
        .map(p => Group(Text(p.0.escape()) + Text(": ") + pretty(p.1)))
        .collect()
      comma_list(pairs, Text("{"), Text("}"))
    }
    String(s) => Text(s.escape())
    Number(i) => Text(i.to_string())
    False => Text("false")
    True => Text("true")
    Null => Text("null")
  }
}

When rendered, the JSON automatically adapts to different widths:

test {
  let json : Json = {
    "key1": "string",
    "key2": [12345, 67890],
    "key3": [
      { "field1": 1, "field2": 2 },
      { "field1": 1, "field2": 2 },
      { "field1": [1, 2], "field2": 2 },
    ],
  }
  inspect(
    pretty(json).render(width=80),
    content=(
      #|{
      #|  "key1": "string",
      #|  "key2": [12345, 67890],
      #|  "key3": [
      #|    {"field1": 1, "field2": 2},
      #|    {"field1": 1, "field2": 2},
      #|    {"field1": [1, 2], "field2": 2}
      #|  ]
      #|}
    ),
  )
  inspect(
    pretty(json).render(width=30),
    content=(
      #|{
      #|  "key1": "string",
      #|  "key2": [12345, 67890],
      #|  "key3": [
      #|    {"field1": 1, "field2": 2},
      #|    {"field1": 1, "field2": 2},
      #|    {
      #|      "field1": [1, 2],
      #|      "field2": 2
      #|    }
      #|  ]
      #|}
    ),
  )
  inspect(
    pretty(json).render(width=20),
    content=(
      #|{
      #|  "key1": "string",
      #|  "key2": [
      #|    12345,
      #|    67890
      #|  ],
      #|  "key3": [
      #|    {
      #|      "field1": 1,
      #|      "field2": 2
      #|    },
      #|    {
      #|      "field1": 1,
      #|      "field2": 2
      #|    },
      #|    {
      #|      "field1": [
      #|        1,
      #|        2
      #|      ],
      #|      "field2": 2
      #|    }
      #|  ]
      #|}
    ),
  )
}

Conclusion

By combining a small set of primitives with function composition, we can build a flexible, declarative prettyprinter that adapts structured data layouts to the available screen width.

This approach scales well: you describe layout intentions with combinators like sepby, surround, or autobreak, and the rendering engine takes care of indentation, line breaks, and fitting.

The current implementation can be further optimized:

• Memoizing space calculations to improve performance.
• Adding a ribbon parameter to balance whitespace vs. content density
• Supporting advanced layouts like hanging indents or mandatory line breaks

For a deeper dive, see Philip Wadler’s classic paper A prettier printer – Philip Wadler, as well as prettyprinter libraries in Haskell, OCaml, and other languages.

Introduction​

Let's first illustrate how incremental computation looks like with an example similar to spreadsheet. First define a dependency graph like this:

In this graph, t1's value is computed from n1 + n2 and t2's value is computed from t1 + n3.

When we want to get the value of t2, the computation defined in the graph will be done: first t1 is computed by n1 + n2, then t2 is computed by t1 + n3. This process is the same as non-incremental computation.

However, when we start to change values in n1, n2, or n3, things get different. Say we swap the value of n1 and n2, then get t2's value. In non-incremental computation, both t1 and t2 will be recomputed. But the computation of t2 is actually not needed, since all its dependency t1 and n3 are not changed (swap n1 and n2 wont change t1's value).

The following code example does exactly what we describe above. We use Cell::new to define n1, n2, and n3, which does not need computation. And Thunk::new to define t1 and t2 with computation.

test {
  // a counter to record the times of t2's computation
  let mut cnt = 0
  // start define the graph
  let n1 = Cell::new(1)
  let n2 = Cell::new(2)
  let n3 = Cell::new(3)
  let t1 = Thunk::new(fn() {
    n1.get() + n2.get()
  })
  let t2 = Thunk::new(fn() {
    cnt += 1
    t1.get() + n3.get()
  })
  // get the value of t2
  inspect(t2.get(), content="6")
  inspect(cnt, content="1")
  // swap value of n1 and n2
  n1.set(2)
  n2.set(1)
  inspect(t2.get(), content="6")
  // t2 does not recompute
  inspect(cnt, content="1")
}

In this article, we will show how to implement an incremental computation library in MoonBit with the api used in the above example:

Cell::new
Cell::get
Cell::set
Thunk::new
Thunk::get

Problem Analysis and Solution​

To implement the library, there are three main problems to solve:

Build up dependency graph on the fly​

As a library in MoonBit, we don't have any easy ways to build up the dependency graph statically, since MoonBit does not have any meta programming mechanism currently. Therefore, we need to construct dependency graph on the fly. Since all we care about is what cells/thunks does a thunk depend on, a good option to build up dependency graph would be when user calls Thunk::get. Take the code above as an example:

let n1 = Cell::new(1)
let n2 = Cell::new(2)
let n3 = Cell::new(3)
let t1 = Thunk::new(fn() { n1.get() + n2.get() })
let t2 = Thunk::new(fn() { t1.get() + n3.get() })
t2.get()

When user calls t2.get(), we can know that at runtime t1.get() and n3.get() are called inside it. Therefore, t1 and n3 are dependencies of t2 and we can construct a subgraph:

The same story will also happen when t1.get() is called inside t2.get().

So here is the plan:

1. we declare a stack to record which thunk are we currently getting. The reason we use stack here is that we are essentially record call stacks of every get.
2. whenever we call get, mark it as the dependency of stack top. If it's a thunk, push it onto stack.
3. whenever a thunk's get finished, pop it off the stack.

Let's see the full process of above example under this algorithm:

1. when we call t2.get, push t2 on the stack.

   

2. when we call t1.get inside t2.get, mark t1 as a dependency of t2 and push t1 onto the stack.

   

3. when we call n1.get inside t1.get, mark n1 as a dependency of t1.

   

4. same story goes for n2.

   

5. when t1.get finished, pop it from stack.

   

6. when we call n3.get, mark n3 as a dependency of t2

   

Besides the edge from dependent to dependency, we'd better also record an edge from dependency to dependent, so that we can easily traverse the graph backwards when we need.

In the code below, we'll use outgoing_edges to refer to edge from parent(dependent) to child (dependency) and incoming_edges to refer to the opposite.

A mechanism to mark outdated node​

Whenever we call Cell::set, the node itself and all nodes depend on it should be marked as outdated. This will be one of the criteria to determine whether a thunk needs to be recomputed. This is generally a recursive backward traverse from a leaf of a graph. We can describe the process as pseudo MoonBit code:

fn dirty(node: Node) -> Unit {
  for n in node.incoming_edges {
    n.set_dirty(true)
    dirty(node)
  }
}

Determine whether a thunk needs to be recomputed​

Whenever we call Thunk::get, we need to determine whether it really needs to be recomputed. But the dirty mechanism we describe in the last subsection is not enough. If we only use dirtiness to determine whether a thunk needs to be recomputed, there would be unneeded computation. Let's see it from the example we give at the beginning:

n1.set(2)
n2.set(1)
inspect(t2.get(), content="6")

After we swap the value of n1 and n2, n1, n2, t1, and t2 should all be marked as dirty, but when we call t2.get, there is no need to recompute t2, since the value of t1 does not change.

This reminds us that despite dirtiness, we need also to record whether a node's value differs from its last value. If a node is both dirty and one of its dependencies' value changed, it needs to be recomputed.

We can describe the algorithm as the pseudo MoonBit code below:

fn propagate(self: Node) -> Unit {
  // When a node is dirty, it might need to be recomputed
  if self.is_dirty() {
    // after recomputing, it's no longer dirty
    self.set_dirty(false)
    for dependency in self.outgoing_edges() {
      // recursively recompute every dependency
      dependency.propagate()
      // If a dependency's value changed, the node needs to be recomputed
      if dependency.is_changed() {
        // remove all incoming_edges and outgoing_edges, since they will be reconstructed during evaluate
        self.incoming_edges().clear()
        self.outgoing_edges().clear()
        self.evaluate()
        return
      }
    }
  }
}

Implementation​

Given the algorithms described in the last section, the implementation should be quite straightforward.

First, let's define Cell:

struct Cell[A] {
  mut is_dirty : Bool
  mut value : A
  mut is_changed : Bool
  incoming_edges : Array[&Node]
}

Since Cell can only be leaf node in dependency graph, it does not have outgoing_edges. The trait Node here is used to abstract node in dependency graph.

Then, let's define Thunk:

struct Thunk[A] {
  mut is_dirty : Bool
  mut value : A?
  mut is_changed : Bool
  thunk : () -> A
  incoming_edges : Array[&Node]
  outgoing_edges : Array[&Node]
}

Thunk's value is optional, since it only exists after we first call Thunk::get.

We can easily add new for both types:

fn[A : Eq] Cell::new(value : A) -> Cell[A] {
  Cell::{
    is_changed: false,
    value,
    incoming_edges: [],
    is_dirty: false,
  }
}

fn[A : Eq] Thunk::new(thunk : () -> A) -> Thunk[A] {
  Thunk::{
    value: None,
    is_changed: false,
    thunk,
    incoming_edges: [],
    outgoing_edges: [],
    is_dirty: false,
  }
}

Thunk and Cell are the two kinds of node in dependency graph, we can use the trait Node mentioned above to abstract them:

trait Node {
  is_dirty(Self) -> Bool
  set_dirty(Self, Bool) -> Unit
  incoming_edges(Self) -> Array[&Node]
  outgoing_edges(Self) -> Array[&Node]
  is_changed(Self) -> Bool
  evaluate(Self) -> Unit
}

And implement the trait for both types:

impl[A] Node for Cell[A] with incoming_edges(self) {
  self.incoming_edges
}

impl[A] Node for Cell[A] with outgoing_edges(_self) {
  []
}

impl[A] Node for Cell[A] with is_dirty(self) {
  self.is_dirty
}

impl[A] Node for Cell[A] with set_dirty(self, new_dirty) {
  self.is_dirty = new_dirty
}

impl[A] Node for Cell[A] with is_changed(self) {
  self.is_changed
}

impl[A] Node for Cell[A] with evaluate(_self) {
  ()
}

impl[A : Eq] Node for Thunk[A] with is_changed(self) {
  self.is_changed
}

impl[A : Eq] Node for Thunk[A] with outgoing_edges(self) {
  self.outgoing_edges
}

impl[A : Eq] Node for Thunk[A] with incoming_edges(self) {
  self.incoming_edges
}

impl[A : Eq] Node for Thunk[A] with is_dirty(self) {
  self.is_dirty
}

impl[A : Eq] Node for Thunk[A] with set_dirty(self, new_dirty) {
  self.is_dirty = new_dirty
}

impl[A : Eq] Node for Thunk[A] with evaluate(self) {
  // push self into node_stack top
  // now self is active target
  node_stack.push(self)
  // `self.thunk` might contains `source.get()`,
  // such as `s1.get()`, `s2.get()` and `s3.get()`
  //
  // when call `Thunk::get` or `Cell::get`,
  // they will treat `node_stack.last()` as themself's target.
  // if source is `Cell`, then it only record `incoming_edges`.
  // if source is `Thunk`, then it record `incoming_edges` and `outgoing_edges`, connect each other.
  //
  let value = (self.thunk)()
  self.is_changed = match self.value {
    None => true
    Some(v) => v != value
  }
  self.value = Some(value)
  // pop self from node_stack
  // now self is no longer active target
  node_stack.unsafe_pop() |> ignore
}

The only complicated implementation is Thunk's evaluate. Here we need first to push the thunk on stack for dependency recording. node_stack is defined as below:

let node_stack : Array[&Node] = []

Then do the real computation and compare it with the last value to update self.is_changed. is_changed is used later to determine whether we need to recompute a thunk.

dirty and propagate are almost the same as the pseudo code described above:

fn &Node::dirty(self : &Node) -> Unit {
  for dependent in self.incoming_edges() {
    if not(dependent.is_dirty()) {
      dependent.set_dirty(true)
      dependent.dirty()
    }
  }
}

fn &Node::propagate(self : &Node) -> Unit {
  if self.is_dirty() {
    self.set_dirty(false)
    for dependency in self.outgoing_edges() {
      dependency.propagate()
      if dependency.is_changed() {
        self.incoming_edges().clear()
        self.outgoing_edges().clear()
        self.evaluate()
        return
      }
    }
  }
}

With all the foundation we build, the three main api: Cell::get, Cell:set, and Thunk::get are easy to implement.

To get value from a cell, it's simply just return the value filed in struct. But before that, we need first record it as a dependency if it's called inside Thunk::get.

fn[A] Cell::get(self : Cell[A]) -> A {
  if node_stack.last() is Some(target) {
    target.outgoing_edges().push(self)
    self.incoming_edges.push(target)
  }
  self.value
}

Whenever we set a cell, we need to first make sure that the two states is_changed and dirty are updated correctly. Then mark every dependent as dirty.

fn[A : Eq] Cell::set(self : Cell[A], new_value : A) -> Unit {
  if self.value != new_value {
    self.is_changed = true
    self.value = new_value
    self.set_dirty(true)
    &Node::dirty(self)
  }
}

In Thunk::get, similar to Cell::get, we first need to record self as a dependency. After that we pattern match on self.value. If it's None, it means that this is the first time user tries to get the thunk's value, so we can safely just evaluate it. If it's Some, we use propagate to make sure that we only recompute thunks that's really needed.

fn[A : Eq] Thunk::get(self : Thunk[A]) -> A {
  if node_stack.last() is Some(target) {
    target.outgoing_edges().push(self)
    self.incoming_edges.push(target)
  }
  match self.value {
    None => self.evaluate()
    Some(_) => &Node::propagate(self)
  }
  self.value.unwrap()
}

Reference​

• Adapton: Composable, demand-driven incremental computation, PLDI 2014 original paper of adapton
• illusory0x0/adapton.mbt adapton library in MoonBit

Introduction​

Python, with its concise syntax and vast ecosystem, has become one of the most popular programming languages today. However, discussions around its performance bottlenecks and the maintainability of its dynamic typing system in large-scale projects have never ceased. To address these challenges, the developer community has explored various optimization paths.

The python.mbt tool, officially launched by MoonBit, offers a new perspective. It allows developers to call Python code directly within the MoonBit environment. This combination aims to merge MoonBit's static type safety and high-performance potential with Python's mature ecosystem. Through python.mbt, developers can leverage MoonBit's static analysis capabilities, modern build and testing tools, while enjoying Python's rich library functions, making it possible to build large-scale, high-performance system-level software.

This article aims to delve into the working principles of python.mbt and provide a practical guide. It will answer common questions such as: How does python.mbt work? Is it slower than native Python due to an added intermediate layer? What are its advantages over existing tools like C++'s pybind11 or Rust's PyO3? To answer these questions, we first need to understand the basic workflow of the Python interpreter.

How the Python Interpreter Works​

The Python interpreter executes code in three main stages:

1. Parsing: This stage includes lexical analysis and syntax analysis. The interpreter breaks down human-readable Python source code into tokens and then organizes these tokens into a tree-like structure, the Abstract Syntax Tree (AST), based on syntax rules.

   For example, for the following Python code:

   def add(x, y):
     return x + y
   
   a = add(1, 2)
   print(a)

   We can use Python's ast module to view its generated AST structure:

   Module(
       body=[
           FunctionDef(
               name='add',
               args=arguments(
                   args=[
                       arg(arg='x'),
                       arg(arg='y')]),
               body=[
                   Return(
                       value=BinOp(
                           left=Name(id='x', ctx=Load()),
                           op=Add(),
                           right=Name(id='y', ctx=Load())))]),
           Assign(
               targets=[
                   Name(id='a', ctx=Store())],
               value=Call(
                   func=Name(id='add', ctx=Load()),
                   args=[
                       Constant(value=1),
                       Constant(value=2)])),
           Expr(
               value=Call(
                   func=Name(id='print', ctx=Load()),
                   args=[
                       Name(id='a', ctx=Load())]))])

2. Compilation: Next, the Python interpreter compiles the AST into a lower-level, more linear intermediate representation called bytecode. This is a platform-independent instruction set designed for the Python Virtual Machine (PVM).

   Using Python's dis module, we can view the bytecode corresponding to the above code:

     2           LOAD_CONST               0 (<code object add>)
                 MAKE_FUNCTION
                 STORE_NAME               0 (add)
   
     5           LOAD_NAME                0 (add)
                 PUSH_NULL
                 LOAD_CONST               1 (1)
                 LOAD_CONST               2 (2)
                 CALL                     2
                 STORE_NAME               1 (a)
   
     6           LOAD_NAME                2 (print)
                 PUSH_NULL
                 LOAD_NAME                1 (a)
                 CALL                     1
                 POP_TOP
                 RETURN_CONST             3 (None)

3. Execution: Finally, the Python Virtual Machine (PVM) executes the bytecode instructions one by one. Each instruction corresponds to a C function call in the CPython interpreter's underlying layer. For example, LOAD_NAME looks up a variable, and BINARY_OP performs a binary operation. It is this process of interpreting and executing instructions one by one that is the main source of Python's performance overhead. A simple 1 + 2 operation involves the entire complex process of parsing, compilation, and virtual machine execution.

Understanding this process helps us grasp the basic approaches to Python performance optimization and the design philosophy of python.mbt.

Paths to Optimizing Python Performance​

Currently, there are two mainstream methods for improving Python program performance:

1. Just-In-Time (JIT) Compilation: Projects like PyPy analyze a running program and compile frequently executed "hotspot" bytecode into highly optimized native machine code, thereby bypassing the PVM's interpretation and significantly speeding up computationally intensive tasks. However, JIT is not a silver bullet; it cannot solve the inherent problems of Python's dynamic typing, such as the difficulty of effective static analysis in large projects, which poses challenges for software maintenance.
2. Native Extensions: Developers can use languages like C++ (with pybind11) or Rust (with PyO3) to directly call Python functions or to write performance-critical modules that are then called from Python. This method can achieve near-native performance, but it requires developers to be proficient in both Python and a complex system-level language, presenting a steep learning curve and a high barrier to entry for most Python programmers.

python.mbt is also a native extension. But compared to languages like C++ and Rust, it attempts to find a new balance between performance, ease of use, and engineering capabilities, with a greater emphasis on using Python features directly within the MoonBit language.

1. High-Performance Core: MoonBit is a statically typed, compiled language whose code can be efficiently compiled into native machine code. Developers can implement computationally intensive logic in MoonBit to achieve high performance from the ground up.
2. Seamless Python Calls: python.mbt interacts directly with CPython's C-API to call Python modules and functions. This means call overhead is minimized, bypassing Python's parsing and compilation stages and going straight to the virtual machine execution layer.
3. Gentler Learning Curve: Compared to C++ and Rust, MoonBit's syntax is more modern and concise. It also has comprehensive support for functional programming, a documentation system, unit testing, and static analysis tools, making it more friendly to developers accustomed to Python.
4. Improved Engineering and AI Collaboration: MoonBit's strong type system and clear interface definitions make code intent more explicit and easier for static analysis tools and AI-assisted programming tools to understand. This helps maintain code quality in large projects and improves the efficiency and accuracy of collaborative coding with AI.

Using Pre-wrapped Python Libraries in MoonBit​

To facilitate developer use, MoonBit will officially wrap mainstream Python libraries once the build system and IDE are mature. After wrapping, users can use these Python libraries in their projects just like importing regular MoonBit packages. Let's take the matplotlib plotting library as an example.

First, add the matplotlib dependency in your project's root moon.pkg.json or via the terminal:

moon update
moon add Kaida-Amethyst/matplotlib

Then, declare the import in the moon.pkg.json of the sub-package where you want to use the library. Here, we follow Python's convention and set an alias plt:

{
  "import": [
    {
      "path": "Kaida-Amethyst/matplotlib",
      "alias": "plt"
    }
  ]
}

After configuration, you can call matplotlib in your MoonBit code to create plots:

let sin : (Double) -> Double = @math.sin

fn main {
  let x = Array::makei(100, fn(i) { i.to_double() * 0.1 })
  let y = x.map(sin)

  // To ensure type safety, the wrapped subplots interface always returns a tuple of a fixed type.
  // This avoids the dynamic behavior in Python where the return type depends on the arguments.
  let (_, axes) = plt::subplots(1, 1)

  // Use the .. cascade call syntax
  axes[0][0]
  ..plot(x, y, color = Green, linestyle = Dashed, linewidth = 2)
  ..set_title("Sine of x")
  ..set_xlabel("x")
  ..set_ylabel("sin(x)")

  @plt.show()
}

Currently, on macOS and Linux, MoonBit's build system can automatically handle dependencies. On Windows, users may need to manually install a C compiler and configure the Python environment. Future MoonBit IDEs will aim to simplify this process.

Using Unwrapped Python Modules in MoonBit​

The Python ecosystem is vast, and even with AI technology, relying solely on official wrappers is not realistic. Fortunately, we can use the core features of python.mbt to interact directly with any Python module. Below, we demonstrate this process using the simple time module from the Python standard library.

Introducing python.mbt​

First, ensure your MoonBit toolchain is up to date, then add the python.mbt dependency:

moon update
moon add Kaida-Amethyst/python

Next, import it in your package's moon.pkg.json:

{
  "import": ["Kaida-Amethyst/python"]
}

python.mbt automatically handles the initialization (Py_Initialize) and shutdown of the Python interpreter, so developers don't need to manage it manually.

Importing Python Modules​

Use the @python.pyimport function to import modules. To avoid performance loss from repeated imports, it is recommended to use a closure technique to cache the imported module object:

// Define a struct to hold the Python module object for enhanced type safety
pub struct TimeModule {
  time_mod: PyModule
}

// Define a function that returns a closure for getting a TimeModule instance
fn import_time_mod() -> () -> TimeModule {
  // The import operation is performed only on the first call
  guard @python.pyimport("time") is Some(time_mod) else {
    println("Failed to load Python module: time")
    panic("ModuleLoadError")
  }
  let time_mod = TimeModule::{ time_mod }
  // The returned closure captures the time_mod variable
  fn () { time_mod }
}

// Create a global time_mod "getter" function
let time_mod: () -> TimeModule = import_time_mod()

In subsequent code, we should always call time_mod() to get the module, not import_time_mod.

Converting Between MoonBit and Python Objects​

To call Python functions, we need to convert between MoonBit objects and Python objects (PyObject).

1. Integers: Use PyInteger::from to create a PyInteger from an Int64, and to_int64() for the reverse conversion.

   test "py_integer_conversion" {
     let n: Int64 = 42
     let py_int = PyInteger::from(n)
     inspect(py_int, content="42")
     assert_eq(py_int.to_int64(), 42L)
   }

2. Floats: Use PyFloat::from and to_double.

   test "py_float_conversion" {
     let n: Double = 3.5
     let py_float = PyFloat::from(n)
     inspect(py_float, content="3.5")
     assert_eq(py_float.to_double(), 3.5)
   }

3. Strings: Use PyString::from and to_string.

   test "py_string_conversion" {
     let py_str = PyString::from("hello")
     inspect(py_str, content="'hello'")
     assert_eq(py_str.to_string(), "hello")
   }

4. Lists: You can create an empty PyList and append elements, or create one directly from an Array[&IsPyObject].

   test "py_list_from_array" {
     let one = PyInteger::from(1)
     let two = PyFloat::from(2.0)
     let three = PyString::from("three")
     let arr: Array[&IsPyObject] = [one, two, three]
   
     let list = PyList::from(arr)
     inspect(list, content="[1, 2.0, 'three']")
   }

5. Tuples: PyTuple requires specifying the size first, then filling elements one by one using the set method.

   test "py_tuple_creation" {
     let tuple = PyTuple::new(3)
     tuple
     ..set(0, PyInteger::from(1))
     ..set(1, PyFloat::from(2.0))
     ..set(2, PyString::from("three"))
   
     inspect(tuple, content="(1, 2.0, 'three')")
   }

6. Dictionaries: PyDict mainly supports strings as keys. Use new to create a dictionary and set to add key-value pairs. For non-string keys, use set_by_obj.

   test "py_dict_creation" {
     let dict = PyDict::new()
     dict
     ..set("one", PyInteger::from(1))
     ..set("two", PyFloat::from(2.0))
   
     inspect(dict, content="{'one': 1, 'two': 2.0}")
   }

When getting elements from Python composite types, python.mbt performs runtime type checking and returns an Optional[PyObjectEnum] to ensure type safety.

test "py_list_get" {
  let list = PyList::new()
  list.append(PyInteger::from(1))
  list.append(PyString::from("hello"))

  inspect(list.get(0).unwrap(), content="PyInteger(1)")
  inspect(list.get(1).unwrap(), content="PyString('hello')")
  inspect(list.get(2), content="None") // Index out of bounds returns None
}

Calling Functions in a Module​

Calling a function is a two-step process: first, get the function object with get_attr, then execute the call with invoke. The return value of invoke is a PyObject that requires pattern matching and type conversion.

Here is the MoonBit wrapper for time.sleep and time.time:

// Wrap time.sleep
pub fn sleep(seconds: Double) -> Unit {
  let lib = time_mod()
  guard lib.time_mod.get_attr("sleep") is Some(PyCallable(f)) else {
    println("get function `sleep` failed!")
    panic()
  }
  let args = PyTuple::new(1)
  args.set(0, PyFloat::from(seconds))
  match (try? f.invoke(args)) {
    Ok(_) => Ok(())
    Err(e) => {
      println("invoke `sleep` failed!")
      panic()
    }
  }
}

// Wrap time.time
pub fn time() -> Double {
  let lib = time_mod()
  guard lib.time_mod.get_attr("time") is Some(PyCallable(f)) else {
    println("get function `time` failed!")
    panic()
  }
  match (try? f.invoke()) {
    Ok(Some(PyFloat(t))) => t.to_double()
    _ => {
      println("invoke `time` failed!")
      panic()
    }
  }
}

After wrapping, we can use them in a type-safe way in MoonBit:

test "sleep" {
  let start = time().unwrap()
  sleep(1)
  let end = time().unwrap()

  println("start = \{start}")
  println("end = \{end}")
}

Practical Advice​

1. Define Clear Boundaries: Treat python.mbt as the "glue layer" connecting MoonBit and the Python ecosystem. Keep core computation and business logic in MoonBit to leverage its performance and type system advantages, and only use python.mbt when necessary to call Python-exclusive libraries.

2. Use ADTs Instead of String Magic: Many Python functions accept specific strings as arguments to control behavior. In MoonBit wrappers, these "magic strings" should be converted to Algebraic Data Types (ADTs), i.e., enums. This leverages MoonBit's type system to move runtime value checks to compile time, greatly enhancing code robustness.

3. Thorough Error Handling: The examples in this article use panic or return simple strings for brevity. In production code, you should define dedicated error types and pass and handle them through the Result type, providing clear error context.

4. Map Keyword Arguments: Python functions extensively use keyword arguments (kwargs), such as plot(color='blue', linewidth=2). This can be elegantly mapped to MoonBit's Labeled Arguments. When wrapping, prioritize using labeled arguments to provide a similar development experience.

   For example, a Python function that accepts kwargs:

   # graphics.py
   def draw_line(points, color="black", width=1):
       # ... drawing logic ...
       print(f"Drawing line with color {color} and width {width}")

   Its MoonBit wrapper can be designed as:

   fn draw_line(points: Array[Point], color~: Color = Black, width: Int = 1) -> Unit {
     let points : PyList = ... // convert Array[Point] to PyList
   
     // construct args
     let args = PyTuple::new(1)
     args .. set(0, points)
   
     // construct kwargs
     let kwargs = PyDict::new()
     kwargs
     ..set("color", PyString::from(color))
     ...set("width", PyInteger::from(width))
     match (try? f.invoke(args~, kwargs~)) {
       Ok(_) => ()
       _ => {
         // handle error
       }
     }
   }

5. Beware of Dynamism: Always remember that Python is dynamically typed. Any data obtained from Python should be treated as "untrusted" and must undergo strict type checking and validation. Avoid using unwrap as much as possible; instead, use pattern matching to safely handle all possible cases.

Conclusion​

This article has outlined the working principles of python.mbt and demonstrated how to use it to call Python code in MoonBit, whether through pre-wrapped libraries or by interacting directly with Python modules. python.mbt is not just a tool; it represents a fusion philosophy: combining MoonBit's static analysis, high performance, and engineering advantages with Python's vast and mature ecosystem. We hope this article provides developers in the MoonBit and Python communities with a new, more powerful option for building future software.