MoonBit Pearls Vol 4: Choreographic Programming with Moonchor

July 11, 2025 · 24 min read

Traditional distributed programming is notoriously painful, primarily because we need to reason about the implicit global behavior while writing the explicit local programs that actually run on each node. This fragmented implementation makes programs difficult to debug, understand, and deprives them of type-checking provided by programming languages. Choreographic Programming makes the global behavior explicit by allowing developers to write a single program that requires communication across multiple participants, which is then projected onto each participant to achieve global behavior.

Choreographic programming is implemented in two distinct approaches:

As a completely new programming language (e.g., Choral), where developers write Choral programs that will be compiled into participant-specific Java programs.
As a library (e.g., HasChor), leveraging Haskell's type system to ensure static properties of choreographic programming while seamlessly integrating with Haskell's ecosystem.

MoonBit's functional programming features and powerful type system make it particularly suitable for building choreographic programming libraries.

This article demonstrates the core concepts and basic usage of choreographic programming using MoonBit's moonchor library through several examples.

Guided Tour: Bookstore Application

Let's examine a bookstore application involving two roles: Buyer and Seller. The core logic is as follows:

The buyer sends the desired book title to the seller.
The seller queries the database and informs the buyer of the price.
The buyer decides whether to purchase the book.
If the buyer decides to purchase, the seller deducts the book from inventory and sends the estimated delivery date to the buyer.
Otherwise, the interaction terminates.

Traditional Implementation

Here, we focus on core logic rather than implementation details, using send and recv functions to represent message passing. In the traditional approach, we need to develop two separate applications for buyer and seller. We assume the following helper functions and types exist:

fn () -> String
get_title() -> String
String {
  "Homotopy Type Theory"
}

fn (title : String) -> Int
get_price(String
title : String
String) -> Int
Int {
  50
}

fn () -> Int
get_budget() -> Int
Int {
  100
}

fn (title : String) -> String
get_delivery_date(String
title : String
String) -> String
String {
  "2025-10-01"
}

enum Role {
  Role
Buyer
  Role
Seller
}

async fn[T] async (msg : T, target : Role) -> Unit
send(T
msg : type parameter T
T, Role
target : enum Role {
  Buyer
  Seller
}
Role) -> Unit
Unit {
  ...
}

async fn[T] async (source : Role) -> T
recv(Role
source : enum Role {
  Buyer
  Seller
}
Role) -> type parameter T
T {
  ...
}

The buyer's application:

async fn async () -> Unit
book_buyer() -> Unit
Unit {
  let String
title = () -> String
get_title()
  async (msg : String, target : Role) -> Unit
send(String
title, Role
Seller)
  let Int
price = async (source : Role) -> Int
recv(Role
Seller)
  if Int
price (self_ : Int, other : Int) -> Bool
<= () -> Int
get_budget() {
    async (msg : Bool, target : Role) -> Unit
send(true, Role
Seller)
    let Unit
delivery_date = async (source : Role) -> Unit
recv(Role
Seller)
    (input : String) -> Unit
Prints any value that implements the Show trait to the standard output,
followed by a newline.
Parameters:

value : The value to be printed. Must implement the Show trait.
Example:
  println(42)
  println("Hello, World!")
  println([1, 2, 3])
println("The book will be delivered on: \{Unit
delivery_date}")
  } else {
    async (msg : Bool, target : Role) -> Unit
send(false, Role
Seller)
  }
}

The seller's application:

async fn async () -> Unit
book_seller() -> Unit
Unit {
  let String
title = async (source : Role) -> String
recv(Role
Buyer)
  let Int
price = (title : String) -> Int
get_price(String
title)
  async (msg : Int, target : Role) -> Unit
send(Int
price, Role
Buyer)
  let Bool
decision = async (source : Role) -> Bool
recv(Role
Buyer)
  if Bool
decision {
    let String
delivery_date = (title : String) -> String
get_delivery_date(String
title)
    async (msg : String, target : Role) -> Unit
send(String
delivery_date, Role
Buyer)
  }
}

These two implementations suffer from at least the following issues:

No type safety guarantee: Note that both send and recv are generic functions. Type safety is only ensured when the types of sending and receiving messages match; otherwise, runtime errors may occur during (de)serialization. The compiler cannot verify type safety at compile time because it cannot determine which send corresponds to which recv. Type safety is dependent on the developer not making mistakes.
Potential deadlocks: If the developer accidentally forgets to write some send in the buyer's program, both buyer and seller may wait indefinitely for each other's messages and be stuck. Alternatively, if a buyer's connection is temporarily interrupted during network communication, the seller will keep waiting for the buyer's message. Both scenarios lead to deadlocks.
Explicit synchronization required: To communicate the purchase decision, the buyer must explicitly send a Bool message. Subsequent coordination requires ensuring both buyer and seller follow the same execution path at the if price <= get_budget() and if decision branches - a property that cannot be guaranteed at compile time.

The root cause of these problems lies in splitting what should be a unified coordination logic into two separate implementations based on implementation requirements. Next, we'll examine how choreographic programming addresses these issues.

moonchor Implementation

With choreographic programming, we can write the buyer's and seller's logic in the same function, which then exhibits different behaviors with different parameters when called. We use moonchor's API to define the buyer and seller roles. In moonchor, roles are defined as trait Location. To provide better static properties, roles are not only values but also unique types that need to implement the Location trait.

struct Buyer {} derive(trait Show {
  output(Self, &Logger) -> Unit
  to_string(Self) -> String
}
Trait for types that can be converted to String
Show, trait Hash {
  hash_combine(Self, Hasher) -> Unit
  hash(Self) -> Int
}
Trait for types that can be hashed
Hash)

impl @moonchor.Location for struct Buyer {
}
Buyer with (_/0) -> String
name(_) {
  "buyer"
}

struct Seller {} derive(trait Show {
  output(Self, &Logger) -> Unit
  to_string(Self) -> String
}
Trait for types that can be converted to String
Show, trait Hash {
  hash_combine(Self, Hasher) -> Unit
  hash(Self) -> Int
}
Trait for types that can be hashed
Hash)

impl @moonchor.Location for struct Seller {
}
Seller with (_/0) -> String
name(_) {
  "seller"
}

let Buyer
buyer : struct Buyer {
}
Buyer = struct Buyer {
}
Buyer::{  }

let Seller
seller : struct Seller {
}
Seller = struct Seller {
}
Seller::{  }

Buyer and Seller types don't contain any fields. Types implementing the Location trait only need to provide a name method that returns a string as the role's identifier. This name method is critically important - it serves as the definitive identity marker for roles and provides a final verification mechanism when type checking cannot guarantee type safety. Never assign the same name to different roles, as this will lead to unexpected runtime errors. Later we'll examine how types provide a certain level of safety and why relying solely on types is insufficient.

Next, we define the core logic of the bookstore application, which is referred to as a choreography:

async fn async (ctx : ?) -> Unit
bookshop(?
ctx : @moonchor.ChoreoContext) -> Unit
Unit {
  let Unit
title_at_buyer = ?
ctx.(Buyer, (Unit) -> String) -> Unit
locally(Buyer
buyer, Unit
_unwrapper => () -> String
get_title())
  let Unit
title_at_seller = ?
ctx.(Buyer, Seller, Unit) -> Unit
comm(Buyer
buyer, Seller
seller, Unit
title_at_buyer)
  let Unit
price_at_seller = ?
ctx.(Seller, (Unit) -> Int) -> Unit
locally(Seller
seller, fn(Unit
unwrapper) {
    let String
title = Unit
unwrapper.(Unit) -> String
unwrap(Unit
title_at_seller)
    (title : String) -> Int
get_price(String
title)
  })
  let Unit
price_at_buyer = ?
ctx.(Seller, Buyer, Unit) -> Unit
comm(Seller
seller, Buyer
buyer, Unit
price_at_seller)
  let Unit
decision_at_buyer = ?
ctx.(Buyer, (Unit) -> Bool) -> Unit
locally(Buyer
buyer, fn(Unit
unwrapper) {
    let Int
price = Unit
unwrapper.(Unit) -> Int
unwrap(Unit
price_at_buyer)
    Int
price (self_ : Int, other : Int) -> Bool
< () -> Int
get_budget()
  })
  if ?
ctx.(Buyer, Unit) -> Bool
broadcast(Buyer
buyer, Unit
decision_at_buyer) {
    let Unit
delivery_date_at_seller = ?
ctx.(Seller, (Unit) -> String) -> Unit
locally(Seller
seller, Unit
unwrapper => (title : String) -> String
get_delivery_date(
      Unit
unwrapper.(Unit) -> String
unwrap(Unit
title_at_seller),
    ))
    let Unit
delivery_date_at_buyer = ?
ctx.(Seller, Buyer, Unit) -> Unit
comm(
      Seller
seller, Buyer
buyer, Unit
delivery_date_at_seller,
    )
    ?
ctx.(Buyer, (Unit) -> Unit) -> Unit
locally(Buyer
buyer, fn(Unit
unwrapper) {
      let Unit
delivery_date = Unit
unwrapper.(Unit) -> Unit
unwrap(Unit
delivery_date_at_buyer)
      (input : String) -> Unit
Prints any value that implements the Show trait to the standard output,
followed by a newline.
Parameters:

value : The value to be printed. Must implement the Show trait.
Example:
  println(42)
  println("Hello, World!")
  println([1, 2, 3])
println("The book will be delivered on \{Unit
delivery_date}")
    })
    |> (t : Unit) -> Unit
Evaluates an expression and discards its result. This is useful when you want
to execute an expression for its side effects but don't care about its return
value, or when you want to explicitly indicate that a value is intentionally
unused.
Parameters:

value : The value to be ignored. Can be of any type.
Example:
  let x = 42
  ignore(x) // Explicitly ignore the value
  let mut sum = 0
  ignore([1, 2, 3].iter().each((x) => { sum = sum + x })) // Ignore the Unit return value of each()
ignore
  }
}

This program is somewhat lengthy, so let's analyze it line by line.

The function parameter ctx: @moonchor.ChoreoContext is the context object provided by moonchor to applications, containing all interfaces for choreographic programming on the application side. First, we use ctx.locally to execute an operation get_title() that only needs to run at the buyer role. The first parameter of ctx.locally is the role. The second parameter is a closure where the content is the operation to execute, with the return value being wrapped as the return value of ctx.locally. Here, get_title() returns a String, while title_at_buyer has type @moonchor.Located[String, Buyer], indicating this value exists at the buyer role and cannot be used by other roles. If you attempt to use title_at_buyer at the seller role, the compiler will report an error stating that Buyer and Seller are not the same type.

Next, the buyer needs to send the book title to the seller, which we implement using ctx.comm. The first parameter of ctx.comm is the sender role, the second is the receiver role, and the third is the message to send. Here, the return value title_at_seller has type @moonchor.Located[String, Seller], indicating this value exists at the seller role. As you might have guessed, ctx.comm corresponds precisely to the send and recv operations. However, here type safety is guaranteed: ctx.comm is a generic function that ensures (1) the sent and received messages have the same type, and (2) the sender and receiver roles correspond to the type parameters of the parameter and return types, namely @moonchor.Located[T, Sender] and @moonchor.Located[T, Receiver].

Moving forward, the seller queries the database to get the book price. At this step we use the unwrapper parameter passed to the ctx.locally closure. This parameter is an object for unpacking Located types, whose type signature also includes a role type parameter. We can understand how it works by examining the signature of Unwrapper::unwrap: fn[T, L] Unwrapper::unwrap(_ : Unwrapper[L], v : Located[T, L]) -> T. This means in ctx.locally(buyer, unwrapper => ...), unwrapper has type Unwrapper[Buyer], while title_at_seller has type Located[String, Seller], so unwrapper.unwrap(title_at_seller) yields a result of type String. This explains why we can use title_at_seller in the closure but not title_at_buyer.

Knowledge of Choice

Explicit synchronization in the subsequent process is critical. We need a dedicated section to explain that. In choreographic programming, this synchronization is referred to as Knowledge of Choice. In the example above, the buyer needs to know whether to purchase the book, and the seller needs to know the buyer's decision. We use ctx.broadcast to implement this functionality.

The first parameter of ctx.broadcast is the sender's role, and the second parameter is the message to be shared with all other roles. In this example, both buyer and seller need to know the purchase decision, so the buyer broadcasts this decision decision_at_buyer to all participants (here only the seller) via ctx.broadcast. Interestingly, the return value of broadcast is a plain type rather than a Located type, meaning it can be used by all roles directly at the top level without needing to be unwrapped with unwrapper in locally. This allows us to use MoonBit's native if conditional statements for subsequent flows, ensuring both buyer and seller follow the same branch.

As the name suggests, ctx.broadcast serves to broadcast a value throughout the entire choreography. It can broadcast not just Bool types but any other type as well. Its results can be applied not only to if conditions but also to while loops or any other scenarios requiring common knowledge.

Launch Code

How does such a choreography run? moonchor provides the run_choreo function to launch a choreography. Currently, due to MoonBit's multi-backend feature, providing stable, portable TCP servers and cross-process communication interfaces presents challenges. Therefore, we'll use coroutines and channels to explore the actual execution process of choreographies. The complete launch code is as follows:

test "Blog: bookshop" {
  let Unit
backend = (Array[Buyer]) -> Unit
@moonchor.make_local_backend([Buyer
buyer, Seller
seller])
  (() -> Unit) -> Unit
@toolkit.run_async(() => (Unit, async (?) -> Unit, Buyer) -> Unit
@moonchor.run_choreo(Unit
backend, async (ctx : ?) -> Unit
bookshop, Buyer
buyer) )
  (() -> Unit) -> Unit
@toolkit.run_async(() => (Unit, async (?) -> Unit, Seller) -> Unit
@moonchor.run_choreo(Unit
backend, async (ctx : ?) -> Unit
bookshop, Seller
seller) )
}

The above code launches two coroutines that execute the same choreography at the buyer and seller respectively. This can also be understood as the bookshop function being projected (also called EPP, endpoint projection) into two completely different versions: the "buyer version" and "seller version". In this example, the first parameter of run_choreo is a Backend type object that provides the underlying communication mechanism required for choreographic programming. We use the make_local_backend function to create a local backend (not to be confused with MoonBit's multi-backend mentioned earlier), which can run in local processes using the channel API provided by peter-jerry-ye/async/channel as the communication foundation. In the future, moonchor will provide more backend implementations, such as HTTP.

API and Partial Principles

We have gained a preliminary understanding of choreographic programming and moonchor. Next, we will formally introduce the APIs we've used along with some unused ones, while explaining some of their underlying principles.

Roles

In moonchor, we define roles by implementing the Location trait. The trait is declared as follows:

pub(open) trait trait Location {
  name(Self) -> String
}
Location: trait Show {
  output(Self, &Logger) -> Unit
  to_string(Self) -> String
}
Trait for types that can be converted to String
Show + trait Hash {
  hash_combine(Self, Hasher) -> Unit
  hash(Self) -> Int
}
Trait for types that can be hashed
Hash {
  (Self) -> String
name(type parameter Self
Self) -> String
String
}

The Location trait object implements Eq:

impl trait Eq {
  op_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
Eq for &trait Location {
  name(Self) -> String
}
Location with (self : &Location, other : &Location) -> Bool
op_equal(&Location
self, &Location
other) {
  &Location
self.(&Location) -> String
name() (self : String, other : String) -> Bool
Tests whether two strings are equal by comparing their characters.
Parameters:

self : The first string to compare.
other : The second string to compare.
Returns true if both strings contain exactly the same sequence of
characters, false otherwise.
Example:
  let str1 = "hello"
  let str2 = "hello"
  let str3 = "world"
  inspect(str1 == str2, content="true")
  inspect(str1 == str3, content="false")
== &Location
other.(&Location) -> String
name()
}

If two roles' name methods return the same string, they are considered the same role; otherwise, they are not. When determining whether a value belongs to a certain role, the name method serves as the definitive arbiter. This means values can have the same type but actually represent different roles. This feature is particularly important when handling dynamically generated roles. For example, in the bookstore scenario, there might be multiple buyers, and the seller needs to handle multiple buyer requests simultaneously, dynamically generating buyer roles based on server connections. In this case, the buyer type would be defined as:

struct DynamicBuyer {
  String
id : String
String
} derive(trait Show {
  output(Self, &Logger) -> Unit
  to_string(Self) -> String
}
Trait for types that can be converted to String
Show, trait Hash {
  hash_combine(Self, Hasher) -> Unit
  hash(Self) -> Int
}
Trait for types that can be hashed
Hash)

impl @moonchor.Location for struct DynamicBuyer {
  id: String
}
DynamicBuyer with (Unit) -> String
name(Unit
self) {
  "buyer-\{Unit
self.String
id}"
}

Located Values

Since values located at different roles may coexist in a choreography, we need a way to distinguish which role each value is located at. In moonchor, this is represented by the Located[T, L] type, indicating a value of type T located at role L.

type Located[T, L]

type Unwrapper[L]

Located Values are constructed via ChoreoContext::locally or ChoreoContext::comm. Both functions return a Located value.

To use a Located Value, we employ the unwrap method of the Unwrapper object. These concepts have already been demonstrated in the bookstore application example and won't be elaborated further here.

Local Computation

The most common API we've seen in examples is ChoreoContext::locally, which is used to perform a local computation at a specific role. Its signature is as follows:

type ChoreoContext

fn[T, L : trait Location {
  name(Self) -> String
}
Location] (self : ChoreoContext, location : L, computation : (Unwrapper[L]) -> T) -> Located[T, L]
locally(
  ChoreoContext
self : type ChoreoContext
ChoreoContext,
  L
location : type parameter L
L,
  (Unwrapper[L]) -> T
computation : (type Unwrapper[L]
Unwrapper[type parameter L
L]) -> type parameter T
T
) -> type Located[T, L]
Located[type parameter T
T, type parameter L
L] {
  ...
}

This API executes the computation closure at the specified location role and wraps the result as a Located Value. The computation closure takes a single parameter - an unwrapper object of type Unwrapper[L], which is used within the closure to unpack Located[T, L] values into T types. This API binds computation results to specific roles, ensuring values can only be used at their designated roles. Attempting to use a value at another role or process values from different roles with this unwrapper will trigger compiler errors.

Communication

The ChoreoContext::comm API handles value transmission between roles. Its declaration is as follows:

trait trait Message {
}
Message: trait ToJson {
  to_json(Self) -> Json
}
Trait for types that can be converted to Json
ToJson + trait @json.FromJson {
  from_json(Json, @json.JsonPath) -> Self raise @json.JsonDecodeError
}
Trait for types that can be converted from Json
@json.FromJson {}

async fn[T : trait Message {
}
Message, From : trait Location {
  name(Self) -> String
}
Location, To : trait Location {
  name(Self) -> String
}
Location] async (self : ChoreoContext, from : From, to : To, value : Located[T, From]) -> Located[T, To]
comm(
  ChoreoContext
self : type ChoreoContext
ChoreoContext,
  From
from : type parameter From
From,
  To
to : type parameter To
To,
  Located[T, From]
value : type Located[T, L]
Located[type parameter T
T, type parameter From
From]
) -> type Located[T, L]
Located[type parameter T
T, type parameter To
To] {
  ...
}

Sending and receiving typically require serialization and deserialization. In moonchor's current implementation, Json is the message carrier for convenience. In the future, byte streams may be adopted as a more efficient and universal carrier.

ChoreoContext::comm has three type parameters: the message type to send, plus the sender and receiver role types From and To. These two role types correspond exactly to the method's from parameter, to parameter, as well as the value parameter and return value type. This ensures type safety during message (de)serialization between sender and receiver, and guarantees send/receive operations are properly paired, preventing accidental deadlocks.

Broadcast

When needing to share a value among multiple roles, we use the ChoreoContext::broadcast API to have a role broadcast a value to all other roles. Its signature is as follows:

async fn[T : trait Message {
}
Message, L : trait Location {
  name(Self) -> String
}
Location] type ChoreoContext
ChoreoContext::async (self : ChoreoContext, loc : L, value : Located[T, L]) -> T
broadcast(
  ChoreoContext
self : type ChoreoContext
ChoreoContext,
  L
loc : type parameter L
L,
  Located[T, L]
value : type Located[T, L]
Located[type parameter T
T, type parameter L
L]
) -> type parameter T
T {
  ...
}

The broadcast API is similar to the communication API, with two key differences:

Broadcast doesn't require specifying receiver roles - it defaults to all roles in the choreography;
The broadcast return value isn't a Located Value, but rather the message's type.

These characteristics reveal broadcast's purpose: enabling all roles to access the same value, allowing operations on this value at the choreography's top level rather than being confined within ChoreoContext::locally. For example, in the bookstore case, both buyer and seller need consensus on the purchase decision to ensure subsequent processes remain synchronized.

Backend and Execution

The API for running a choreography is as follows:

type Backend

typealias async (type ChoreoContext
ChoreoContext) -> type parameter T
T as Choreo[T]

async fn[T, L : trait Location {
  name(Self) -> String
}
Location] async (backend : Backend, choreography : async (ChoreoContext) -> T, role : L) -> T
run_choreo(
  Backend
backend : type Backend
Backend,
  async (ChoreoContext) -> T
choreography : Choreo[type parameter T
T],
  L
role : type parameter L
L
) -> type parameter T
T {
  ...
}

It takes three parameters: a backend, a user-written choreography, and the role to execute. The backend contains the concrete implementation of the communication mechanism, while the execution role specifies where this choreography should run. For example, in previous cases, the buyer's program needs to pass a value of type Buyer here, while the seller needs to pass a value of type Seller.

moonchor provides a local backend based on coroutines and channels:

fn (locations : Array[&Location]) -> Backend
make_local_backend(Array[&Location]
locations: type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[&trait Location {
  name(Self) -> String
}
Location]) -> type Backend
Backend {
  ...
}

This function establishes communication channels between all roles specified in the parameters, providing concrete communication implementations - namely the send and recv methods. The local backend can only be used for monolithic concurrent programs rather than true distributed applications. Well, the backend is pluggable: With other backends implemented based on stable network communication APIs, moonchor can easily be used to build distributed programs.

(Optional Reading) Case Study: Multi-Replica KVStore

In this section, we'll explore a more complicated case study - implementing a multi-replica KVStore using moonchor. We'll still only use moonchor's core APIs while fully leveraging MoonBit's generics and first-class functions. Our goal is to explore how MoonBit's powerful expressiveness can enhance choreographic programming functionalities.

Basic Implementation

First, let's prepare by defining two roles: Client and Server:

struct Server {} derive(trait Hash {
  hash_combine(Self, Hasher) -> Unit
  hash(Self) -> Int
}
Trait for types that can be hashed
Hash, trait Show {
  output(Self, &Logger) -> Unit
  to_string(Self) -> String
}
Trait for types that can be converted to String
Show)

struct Client {} derive(trait Hash {
  hash_combine(Self, Hasher) -> Unit
  hash(Self) -> Int
}
Trait for types that can be hashed
Hash, trait Show {
  output(Self, &Logger) -> Unit
  to_string(Self) -> String
}
Trait for types that can be converted to String
Show)

impl @moonchor.Location for struct Server {
}
Server with (_/0) -> String
name(_) {
  "server"
}

impl @moonchor.Location for struct Client {
}
Client with (_/0) -> String
name(_) {
  "client"
}

let Server
server : struct Server {
}
Server = struct Server {
}
Server::{  }

let Client
client : struct Client {
}
Client = struct Client {
}
Client::{  }

To implement a KVStore like Redis, we need to implement two basic interfaces: get and put (corresponding to Redis's get and set). The simplest implementation uses a Map data structure to store key-value pairs:

struct ServerState {
  Map[String, Int]
db: type Map[K, V]
Mutable linked hash map that maintains the order of insertion, not thread safe.
Example
  let map = { 3: "three", 8 :  "eight", 1 :  "one"}
  assert_eq(map.get(2), None)
  assert_eq(map.get(3), Some("three"))
  map.set(3, "updated")
  assert_eq(map.get(3), Some("updated"))
Map[String
String, Int
Int]
}

fn struct ServerState {
  db: Map[String, Int]
}
ServerState::() -> ServerState
new() -> struct ServerState {
  db: Map[String, Int]
}
ServerState {
  { Map[String, Int]
db: {} }
}

For the KVStore, get and put requests are sent by clients over the network. Before receiving requests, we don't know their specific content. Therefore, we need to define a request type Request that includes the request type and parameters:

enum Request {
  (String) -> Request
Get(String
String)
  (String, Int) -> Request
Put(String
String, Int
Int)
} derive(trait ToJson {
  to_json(Self) -> Json
}
Trait for types that can be converted to Json
ToJson, trait @json.FromJson {
  from_json(Json, @json.JsonPath) -> Self raise @json.JsonDecodeError
}
Trait for types that can be converted from Json
FromJson)

For convenience, our KVStore only supports String keys and Int values. Next, we define a Response type to represent the server's response to requests:

typealias Int
Int? as Response

The response is an optional integer. For Put requests, the response is None; for Get requests, the response is the corresponding value wrapped in Some, or None if the key doesn't exist.

fn (state : ServerState, request : Request) -> Int?
handle_request(ServerState
state : struct ServerState {
  db: Map[String, Int]
}
ServerState, Request
request : enum Request {
  Get(String)
  Put(String, Int)
}
Request) -> enum Option[A] {
  None
  Some(A)
}
Response {
  match Request
request {
    Request::(String) -> Request
Get(String
key) => ServerState
state.Map[String, Int]
db.(self : Map[String, Int], key : String) -> Int?
Get the value associated with a key.
get(String
key)
    Request::(String, Int) -> Request
Put(String
key, Int
value) => {
      ServerState
state.Map[String, Int]
db(Map[String, Int], String, Int) -> Unit
[key] = Int
value
      Int?
None
    }
  }
}

Our goal is to define two functions, put and get, to simulate the client's request initiation process. Their respective tasks are:

Generate the request at the Client, wrapping the key-value pair;
Send the request to the Server;
The Server processes the request using the handle_request function;
Send the response back to the Client.

As we can see, the logic of put and get functions is similar. We can abstract the three processes (2, 3, and 4) into a single function called access_server.

async fn async (ctx : ?, state_at_server : ?, key : String, value : Int) -> Unit
put_v1(
  ?
ctx : @moonchor.ChoreoContext,
  ?
state_at_server : @moonchor.Located[struct ServerState {
  db: Map[String, Int]
}
ServerState, struct Server {
}
Server],
  String
key : String
String,
  Int
value : Int
Int
) -> Unit
Unit {
  let ?
request = ?
ctx.(Client, (Unit) -> Request) -> ?
locally(Client
client, Unit
_unwrapper => Request::(String, Int) -> Request
Put(String
key, Int
value))
  async (ctx : ?, request : ?, state_at_server : ?) -> ?
access_server_v1(?
ctx, ?
request, ?
state_at_server) |> (t : ?) -> Unit
Evaluates an expression and discards its result. This is useful when you want
to execute an expression for its side effects but don't care about its return
value, or when you want to explicitly indicate that a value is intentionally
unused.
Parameters:

value : The value to be ignored. Can be of any type.
Example:
  let x = 42
  ignore(x) // Explicitly ignore the value
  let mut sum = 0
  ignore([1, 2, 3].iter().each((x) => { sum = sum + x })) // Ignore the Unit return value of each()
ignore
}

async fn async (ctx : ?, state_at_server : ?, key : String) -> ?
get_v1(
  ?
ctx : @moonchor.ChoreoContext,
  ?
state_at_server : @moonchor.Located[struct ServerState {
  db: Map[String, Int]
}
ServerState, struct Server {
}
Server],
  String
key : String
String
) -> @moonchor.Located[enum Option[A] {
  None
  Some(A)
}
Response, struct Client {
}
Client] {
  let ?
request = ?
ctx.(Client, (Unit) -> Request) -> ?
locally(Client
client, Unit
_unwrapper => Request::(String) -> Request
Get(String
key))
  async (ctx : ?, request : ?, state_at_server : ?) -> ?
access_server_v1(?
ctx, ?
request, ?
state_at_server)
}

async fn async (ctx : ?, request : ?, state_at_server : ?) -> ?
access_server_v1(
  ?
ctx : @moonchor.ChoreoContext,
  ?
request : @moonchor.Located[enum Request {
  Get(String)
  Put(String, Int)
}
Request, struct Client {
}
Client],
  ?
state_at_server : @moonchor.Located[struct ServerState {
  db: Map[String, Int]
}
ServerState, struct Server {
}
Server]
) -> @moonchor.Located[enum Option[A] {
  None
  Some(A)
}
Response, struct Client {
}
Client] {
  let Unit
request_at_server = ?
ctx.(Client, Server, ?) -> Unit
comm(Client
client, Server
server, ?
request)
  let Unit
response = ?
ctx.(Server, (Unit) -> Int?) -> Unit
locally(Server
server, fn(Unit
unwrapper) {
    let Request
request = Unit
unwrapper.(Unit) -> Request
unwrap(Unit
request_at_server)
    let ServerState
state = Unit
unwrapper.(?) -> ServerState
unwrap(?
state_at_server)
    (state : ServerState, request : Request) -> Int?
handle_request(ServerState
state, Request
request)
  })
  ?
ctx.(Server, Client, Unit) -> ?
comm(Server
server, Client
client, Unit
response)
}

With this, our KVStore implementation is complete. We can write a simple choreography to test it:

async fn async (ctx : ?) -> Unit
kvstore_v1(?
ctx : @moonchor.ChoreoContext) -> Unit
Unit {
  let ?
state_at_server = ?
ctx.(Server, (Unit) -> ServerState) -> ?
locally(Server
server, Unit
_unwrapper => struct ServerState {
  db: Map[String, Int]
}
ServerState::() -> ServerState
new())
  async (ctx : ?, state_at_server : ?, key : String, value : Int) -> Unit
put_v1(?
ctx, ?
state_at_server, "key1", 42)
  async (ctx : ?, state_at_server : ?, key : String, value : Int) -> Unit
put_v1(?
ctx, ?
state_at_server, "key2", 41)
  let ?
v1_at_client = async (ctx : ?, state_at_server : ?, key : String) -> ?
get_v1(?
ctx, ?
state_at_server, "key1")
  let ?
v2_at_client = async (ctx : ?, state_at_server : ?, key : String) -> ?
get_v1(?
ctx, ?
state_at_server, "key2")
  ?
ctx.(Client, (Unit) -> Unit) -> Unit
locally(Client
client, fn(Unit
unwrapper) {
    let Int
v1 = Unit
unwrapper.(?) -> Unit
unwrap(?
v1_at_client).() -> Int
unwrap()
    let Int
v2 = Unit
unwrapper.(?) -> Unit
unwrap(?
v2_at_client).() -> Int
unwrap()
    if Int
v1 (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ Int
v2 (self : Int, other : Int) -> Bool
Compares two integers for equality.
Parameters:

self : The first integer to compare.
other : The second integer to compare.
Returns true if both integers have the same value, false otherwise.
Example:
  inspect(42 == 42, content="true")
  inspect(42 == -42, content="false")
== 83 {
      (input : String) -> Unit
Prints any value that implements the Show trait to the standard output,
followed by a newline.
Parameters:

value : The value to be printed. Must implement the Show trait.
Example:
  println(42)
  println("Hello, World!")
  println([1, 2, 3])
println("The server is working correctly")
    } else {
      () -> Unit
panic()
    }
  })
  |> (t : Unit) -> Unit
Evaluates an expression and discards its result. This is useful when you want
to execute an expression for its side effects but don't care about its return
value, or when you want to explicitly indicate that a value is intentionally
unused.
Parameters:

value : The value to be ignored. Can be of any type.
Example:
  let x = 42
  ignore(x) // Explicitly ignore the value
  let mut sum = 0
  ignore([1, 2, 3].iter().each((x) => { sum = sum + x })) // Ignore the Unit return value of each()
ignore
}

test "kvstore v1" {
  let Unit
backend = (Array[Server]) -> Unit
@moonchor.make_local_backend([Server
server, Client
client])
  (() -> Unit) -> Unit
@toolkit.run_async(() => (Unit, async (?) -> Unit, Server) -> Unit
@moonchor.run_choreo(Unit
backend, async (ctx : ?) -> Unit
kvstore_v1, Server
server))
  (() -> Unit) -> Unit
@toolkit.run_async(() => (Unit, async (?) -> Unit, Client) -> Unit
@moonchor.run_choreo(Unit
backend, async (ctx : ?) -> Unit
kvstore_v1, Client
client))
}

This program stores two numbers 42 and 41 under "key1" and "key2" respectively, then retrieves these values from the server and verifies their sum equals 83. If any request returns None or the calculation result isn't 83, the program will panic.

Double Replication

Now, let's enhance the KVStore with fault tolerance. The simplest approach is to create a backup replica that maintains identical data to the primary replica, while performing consistency checks during Get requests.

We'll create a new role for the backup replica:

struct Backup {} derive(trait Hash {
  hash_combine(Self, Hasher) -> Unit
  hash(Self) -> Int
}
Trait for types that can be hashed
Hash, trait Show {
  output(Self, &Logger) -> Unit
  to_string(Self) -> String
}
Trait for types that can be converted to String
Show)

impl @moonchor.Location for struct Backup {
}
Backup with (_/0) -> String
name(_) {
  "backup"
}

let Backup
backup : struct Backup {
}
Backup = struct Backup {
}
Backup::{  }

Define a function to check consistency: this function verifies whether all replica responses are identical, and panics if inconsistencies are found.

fn (responses : Array[Int?]) -> Unit
check_consistency(Array[Int?]
responses: type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[enum Option[A] {
  None
  Some(A)
}
Response]) -> Unit
Unit {
  match Array[Int?]
responses.(self : Array[Int?]) -> Int??
Removes the last element from a array and returns it, or None if it is empty.
Example
  let v = [1, 2, 3]
  assert_eq(v.pop(), Some(3))
  assert_eq(v, [1, 2])
pop() {
    Int??
None => return
    (Int?) -> Int??
Some(Int?
f) =>
      for Int?
res in Array[Int?]
responses {
        if Int?
res (x : Int?, y : Int?) -> Bool
!= Int?
f {
          () -> Unit
panic()
        }
      }
  }
}

Most other components remain unchanged. We only need to add replica handling in the access_server function. The new access_server_v2 logic works as follows: after receiving a request, the Server forwards it to Backup; then Server and Backup process the request separately; after processing, Backup sends the response back to Server, where Server performs consistency checks on both results.

async fn async (ctx : ?, state_at_server : ?, state_at_backup : ?, key : String, value : Int) -> Unit
put_v2(
  ?
ctx : @moonchor.ChoreoContext,
  ?
state_at_server : @moonchor.Located[struct ServerState {
  db: Map[String, Int]
}
ServerState, struct Server {
}
Server],
  ?
state_at_backup : @moonchor.Located[struct ServerState {
  db: Map[String, Int]
}
ServerState, struct Backup {
}
Backup],
  String
key : String
String,
  Int
value : Int
Int
) -> Unit
Unit {
  let ?
request = ?
ctx.(Client, (Unit) -> Request) -> ?
locally(Client
client, Unit
_unwrapper => Request::(String, Int) -> Request
Put(String
key, Int
value))
  async (ctx : ?, request : ?, state_at_server : ?, state_at_backup : ?) -> ?
access_server_v2(?
ctx, ?
request, ?
state_at_server, ?
state_at_backup) |> (t : ?) -> Unit
Evaluates an expression and discards its result. This is useful when you want
to execute an expression for its side effects but don't care about its return
value, or when you want to explicitly indicate that a value is intentionally
unused.
Parameters:

value : The value to be ignored. Can be of any type.
Example:
  let x = 42
  ignore(x) // Explicitly ignore the value
  let mut sum = 0
  ignore([1, 2, 3].iter().each((x) => { sum = sum + x })) // Ignore the Unit return value of each()
ignore
}

async fn async (ctx : ?, state_at_server : ?, state_at_backup : ?, key : String) -> ?
get_v2(
  ?
ctx : @moonchor.ChoreoContext,
  ?
state_at_server : @moonchor.Located[struct ServerState {
  db: Map[String, Int]
}
ServerState, struct Server {
}
Server],
  ?
state_at_backup : @moonchor.Located[struct ServerState {
  db: Map[String, Int]
}
ServerState, struct Backup {
}
Backup],
  String
key : String
String
) -> @moonchor.Located[enum Option[A] {
  None
  Some(A)
}
Response, struct Client {
}
Client] {
  let ?
request = ?
ctx.(Client, (Unit) -> Request) -> ?
locally(Client
client, Unit
_unwrapper => Request::(String) -> Request
Get(String
key))
  async (ctx : ?, request : ?, state_at_server : ?, state_at_backup : ?) -> ?
access_server_v2(?
ctx, ?
request, ?
state_at_server, ?
state_at_backup)
}

async fn async (ctx : ?, request : ?, state_at_server : ?, state_at_backup : ?) -> ?
access_server_v2(
  ?
ctx : @moonchor.ChoreoContext,
  ?
request : @moonchor.Located[enum Request {
  Get(String)
  Put(String, Int)
}
Request, struct Client {
}
Client],
  ?
state_at_server : @moonchor.Located[struct ServerState {
  db: Map[String, Int]
}
ServerState, struct Server {
}
Server],
  ?
state_at_backup : @moonchor.Located[struct ServerState {
  db: Map[String, Int]
}
ServerState, struct Backup {
}
Backup]
) -> @moonchor.Located[enum Option[A] {
  None
  Some(A)
}
Response, struct Client {
}
Client] {
  let Unit
request_at_server = ?
ctx.(Client, Server, ?) -> Unit
comm(Client
client, Server
server, ?
request)
  let Unit
request_at_backup = ?
ctx.(Server, Backup, Unit) -> Unit
comm(Server
server, Backup
backup, Unit
request_at_server)
  let Unit
response_at_backup = ?
ctx.(Backup, (Unit) -> Int?) -> Unit
locally(Backup
backup, fn(Unit
unwrapper) {
    let Request
request = Unit
unwrapper.(Unit) -> Request
unwrap(Unit
request_at_backup)
    let ServerState
state = Unit
unwrapper.(?) -> ServerState
unwrap(?
state_at_backup)
    (state : ServerState, request : Request) -> Int?
handle_request(ServerState
state, Request
request)
  })
  let Unit
backup_response_at_server = ?
ctx.(Backup, Server, Unit) -> Unit
comm(Backup
backup, Server
server, Unit
response_at_backup)
  let Unit
response_at_server = ?
ctx.(Server, (Unit) -> Int?) -> Unit
locally(Server
server, fn(Unit
unwrapper) {
    let Request
request = Unit
unwrapper.(Unit) -> Request
unwrap(Unit
request_at_server)
    let ServerState
state = Unit
unwrapper.(?) -> ServerState
unwrap(?
state_at_server)
    let Int?
response = (state : ServerState, request : Request) -> Int?
handle_request(ServerState
state, Request
request)
    let Int?
backup_response = Unit
unwrapper.(Unit) -> Int?
unwrap(Unit
backup_response_at_server)
    (responses : Array[Int?]) -> Unit
check_consistency([Int?
response, Int?
backup_response])
    Int?
response
  })
  ?
ctx.(Server, Client, Unit) -> ?
comm(Server
server, Client
client, Unit
response_at_server)
}

As before, we can write a simple choreography to test it:

async fn async (ctx : ?) -> Unit
kvstore_v2(?
ctx : @moonchor.ChoreoContext) -> Unit
Unit {
  let ?
state_at_server = ?
ctx.(Server, (Unit) -> ServerState) -> ?
locally(Server
server, Unit
_unwrapper => struct ServerState {
  db: Map[String, Int]
}
ServerState::() -> ServerState
new())
  let ?
state_at_backup = ?
ctx.(Backup, (Unit) -> ServerState) -> ?
locally(Backup
backup, Unit
_unwrapper => struct ServerState {
  db: Map[String, Int]
}
ServerState::() -> ServerState
new())
  async (ctx : ?, state_at_server : ?, state_at_backup : ?, key : String, value : Int) -> Unit
put_v2(?
ctx, ?
state_at_server, ?
state_at_backup, "key1", 42)
  async (ctx : ?, state_at_server : ?, state_at_backup : ?, key : String, value : Int) -> Unit
put_v2(?
ctx, ?
state_at_server, ?
state_at_backup, "key2", 41)
  let ?
v1_at_client = async (ctx : ?, state_at_server : ?, state_at_backup : ?, key : String) -> ?
get_v2(?
ctx, ?
state_at_server, ?
state_at_backup, "key1")
  let ?
v2_at_client = async (ctx : ?, state_at_server : ?, state_at_backup : ?, key : String) -> ?
get_v2(?
ctx, ?
state_at_server, ?
state_at_backup, "key2")
  ?
ctx.(Client, (Unit) -> Unit) -> Unit
locally(Client
client, fn(Unit
unwrapper) {
    let Int
v1 = Unit
unwrapper.(?) -> Unit
unwrap(?
v1_at_client).() -> Int
unwrap()
    let Int
v2 = Unit
unwrapper.(?) -> Unit
unwrap(?
v2_at_client).() -> Int
unwrap()
    if Int
v1 (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ Int
v2 (self : Int, other : Int) -> Bool
Compares two integers for equality.
Parameters:

self : The first integer to compare.
other : The second integer to compare.
Returns true if both integers have the same value, false otherwise.
Example:
  inspect(42 == 42, content="true")
  inspect(42 == -42, content="false")
== 83 {
      (input : String) -> Unit
Prints any value that implements the Show trait to the standard output,
followed by a newline.
Parameters:

value : The value to be printed. Must implement the Show trait.
Example:
  println(42)
  println("Hello, World!")
  println([1, 2, 3])
println("The server is working correctly")
    } else {
      () -> Unit
panic()
    }
  })
  |> (t : Unit) -> Unit
Evaluates an expression and discards its result. This is useful when you want
to execute an expression for its side effects but don't care about its return
value, or when you want to explicitly indicate that a value is intentionally
unused.
Parameters:

value : The value to be ignored. Can be of any type.
Example:
  let x = 42
  ignore(x) // Explicitly ignore the value
  let mut sum = 0
  ignore([1, 2, 3].iter().each((x) => { sum = sum + x })) // Ignore the Unit return value of each()
ignore
}

test "kvstore 2.0" {
  let Unit
backend = (Array[Server]) -> Unit
@moonchor.make_local_backend([Server
server, Client
client, Backup
backup])
  (() -> Unit) -> Unit
@toolkit.run_async(() => (Unit, async (?) -> Unit, Server) -> Unit
@moonchor.run_choreo(Unit
backend, async (ctx : ?) -> Unit
kvstore_v2, Server
server) )
  (() -> Unit) -> Unit
@toolkit.run_async(() => (Unit, async (?) -> Unit, Client) -> Unit
@moonchor.run_choreo(Unit
backend, async (ctx : ?) -> Unit
kvstore_v2, Client
client) )
  (() -> Unit) -> Unit
@toolkit.run_async(() => (Unit, async (?) -> Unit, Backup) -> Unit
@moonchor.run_choreo(Unit
backend, async (ctx : ?) -> Unit
kvstore_v2, Backup
backup) )
}

Abstracting Replication Strategy with Higher-Order Functions

During the double replication implementation, we encountered coupled code where server request processing, backup requests, and consistency checking were intertwined.

Using MoonBit's higher-order functions, we can abstract the replication strategy away from the concrete processing logic. Let's analyze what constitutes a replication strategy. It should encapsulate how the server processes requests using replicas after receiving them. The key insight is that the replication strategy itself is request-agnostic and should be decoupled from the actual request handling. This makes the strategy swappable, allowing easy switching between different strategies or implementing new ones in the future.

Of course, real-world replication strategies are far more complicated and often resist clean separation. For this example, we simplify the problem to focus on moonchor's programming capabilities, directly defining the replication strategy as a function determining how the server processes requests after receiving them. We can define it with a type alias:

typealias async (@moonchor.ChoreoContext, @moonchor.Located[enum Request {
  Get(String)
  Put(String, Int)
}
Request, struct Server {
}
Server]) -> @moonchor.Located[
  enum Option[A] {
  None
  Some(A)
}
Response,
  struct Server {
}
Server,
] as ReplicationStrategy

Now we can simplify the access_server implementation by passing the strategy as a parameter:

async fn async (ctx : ?, request : ?, strategy : async (?, ?) -> ?) -> ?
access_server_v3(
  ?
ctx: @moonchor.ChoreoContext,
  ?
request: @moonchor.Located[enum Request {
  Get(String)
  Put(String, Int)
}
Request, struct Client {
}
Client],
  async (?, ?) -> ?
strategy: ReplicationStrategy
) -> @moonchor.Located[enum Option[A] {
  None
  Some(A)
}
Response, struct Client {
}
Client] {
  let ?
request_at_server = ?
ctx.(Client, Server, ?) -> ?
comm(Client
client, Server
server, ?
request)
  let ?
response = async (?, ?) -> ?
strategy(?
ctx, ?
request_at_server)
  ?
ctx.(Server, Client, ?) -> ?
comm(Server
server, Client
client, ?
response)
}

async fn async (ctx : ?, strategy : async (?, ?) -> ?, key : String, value : Int) -> Unit
put_v3(
  ?
ctx: @moonchor.ChoreoContext,
  async (?, ?) -> ?
strategy: ReplicationStrategy,
  String
key: String
String,
  Int
value: Int
Int
) -> Unit
Unit {
  let ?
request = ?
ctx.(Client, (Unit) -> Request) -> ?
locally(Client
client, Unit
_unwrapper => Request::(String, Int) -> Request
Put(String
key, Int
value))
  async (ctx : ?, request : ?, strategy : async (?, ?) -> ?) -> ?
access_server_v3(?
ctx, ?
request, async (?, ?) -> ?
strategy) |> (t : ?) -> Unit
Evaluates an expression and discards its result. This is useful when you want
to execute an expression for its side effects but don't care about its return
value, or when you want to explicitly indicate that a value is intentionally
unused.
Parameters:

value : The value to be ignored. Can be of any type.
Example:
  let x = 42
  ignore(x) // Explicitly ignore the value
  let mut sum = 0
  ignore([1, 2, 3].iter().each((x) => { sum = sum + x })) // Ignore the Unit return value of each()
ignore
}

async fn async (ctx : ?, strategy : async (?, ?) -> ?, key : String) -> ?
get_v3(
  ?
ctx: @moonchor.ChoreoContext,
  async (?, ?) -> ?
strategy: ReplicationStrategy,
  String
key: String
String
) -> @moonchor.Located[enum Option[A] {
  None
  Some(A)
}
Response, struct Client {
}
Client] {
  let ?
request = ?
ctx.(Client, (Unit) -> Request) -> ?
locally(Client
client, Unit
_unwrapper => Request::(String) -> Request
Get(String
key))
  async (ctx : ?, request : ?, strategy : async (?, ?) -> ?) -> ?
access_server_v3(?
ctx, ?
request, async (?, ?) -> ?
strategy)
}

This successfully abstracts the replication strategy from the request handling logic. Below, we reimplement the double replication strategy:

async fn async (state_at_server : ?, state_at_backup : ?) -> async (?, ?) -> ?
double_replication_strategy(
  ?
state_at_server: @moonchor.Located[struct ServerState {
  db: Map[String, Int]
}
ServerState, struct Server {
}
Server],
  ?
state_at_backup: @moonchor.Located[struct ServerState {
  db: Map[String, Int]
}
ServerState, struct Backup {
}
Backup],
) -> ReplicationStrategy {
  fn(
    ?
ctx: @moonchor.ChoreoContext,
    ?
request_at_server: @moonchor.Located[enum Request {
  Get(String)
  Put(String, Int)
}
Request, struct Server {
}
Server]
  ) {
    let Unit
request_at_backup = ?
ctx.(Server, Backup, ?) -> Unit
comm(Server
server, Backup
backup, ?
request_at_server)
    let Unit
response_at_backup = ?
ctx.(Backup, (Unit) -> Int?) -> Unit
locally(Backup
backup, fn(Unit
unwrapper) {
      let Request
request = Unit
unwrapper.(Unit) -> Request
unwrap(Unit
request_at_backup)
      let ServerState
state = Unit
unwrapper.(?) -> ServerState
unwrap(?
state_at_backup)
      (state : ServerState, request : Request) -> Int?
handle_request(ServerState
state, Request
request)
    })
    let Unit
backup_response = ?
ctx.(Backup, Server, Unit) -> Unit
comm(Backup
backup, Server
server, Unit
response_at_backup)
    ?
ctx.(Server, (Unit) -> Int?) -> ?
locally(Server
server, fn(Unit
unwrapper) {
      let Request
request = Unit
unwrapper.(?) -> Request
unwrap(?
request_at_server)
      let ServerState
state = Unit
unwrapper.(?) -> ServerState
unwrap(?
state_at_server)
      let Int?
res = (state : ServerState, request : Request) -> Int?
handle_request(ServerState
state, Request
request)
      (responses : Array[Int?]) -> Unit
check_consistency([Unit
unwrapper.(Unit) -> Int?
unwrap(Unit
backup_response), Int?
res])
      Int?
res
    })
  }
}

Note the function signature of double_replication_strategy - it returns a function of type ReplicationStrategy. Given two parameters, it constructs a new replication strategy. This demonstrates using higher-order functions to abstract replication strategies, known as higher-order choreography in choreographic programming.

We can test it with a simple choreography:

async fn async (ctx : ?) -> Unit
kvstore_v3(?
ctx: @moonchor.ChoreoContext) -> Unit
Unit {
  let ?
state_at_server = ?
ctx.(Server, (Unit) -> ServerState) -> ?
locally(Server
server, Unit
_unwrapper => struct ServerState {
  db: Map[String, Int]
}
ServerState::() -> ServerState
new())
  let ?
state_at_backup = ?
ctx.(Backup, (Unit) -> ServerState) -> ?
locally(Backup
backup, Unit
_unwrapper => struct ServerState {
  db: Map[String, Int]
}
ServerState::() -> ServerState
new())
  let async (?, ?) -> ?
strategy = async (state_at_server : ?, state_at_backup : ?) -> async (?, ?) -> ?
double_replication_strategy(?
state_at_server, ?
state_at_backup)
  async (ctx : ?, strategy : async (?, ?) -> ?, key : String, value : Int) -> Unit
put_v3(?
ctx, async (?, ?) -> ?
strategy, "key1", 42)
  async (ctx : ?, strategy : async (?, ?) -> ?, key : String, value : Int) -> Unit
put_v3(?
ctx, async (?, ?) -> ?
strategy, "key2", 41)
  let ?
v1_at_client = async (ctx : ?, strategy : async (?, ?) -> ?, key : String) -> ?
get_v3(?
ctx, async (?, ?) -> ?
strategy, "key1")
  let ?
v2_at_client = async (ctx : ?, strategy : async (?, ?) -> ?, key : String) -> ?
get_v3(?
ctx, async (?, ?) -> ?
strategy, "key2")
  ?
ctx.(Client, (Unit) -> Unit) -> Unit
locally(Client
client, fn(Unit
unwrapper) {
    let Int
v1 = Unit
unwrapper.(?) -> Unit
unwrap(?
v1_at_client).() -> Int
unwrap()
    let Int
v2 = Unit
unwrapper.(?) -> Unit
unwrap(?
v2_at_client).() -> Int
unwrap()
    if Int
v1 (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ Int
v2 (self : Int, other : Int) -> Bool
Compares two integers for equality.
Parameters:

self : The first integer to compare.
other : The second integer to compare.
Returns true if both integers have the same value, false otherwise.
Example:
  inspect(42 == 42, content="true")
  inspect(42 == -42, content="false")
== 83 {
      (input : String) -> Unit
Prints any value that implements the Show trait to the standard output,
followed by a newline.
Parameters:

value : The value to be printed. Must implement the Show trait.
Example:
  println(42)
  println("Hello, World!")
  println([1, 2, 3])
println("The server is working correctly")
    } else {
      () -> Unit
panic()
    }
  })
  |> (t : Unit) -> Unit
Evaluates an expression and discards its result. This is useful when you want
to execute an expression for its side effects but don't care about its return
value, or when you want to explicitly indicate that a value is intentionally
unused.
Parameters:

value : The value to be ignored. Can be of any type.
Example:
  let x = 42
  ignore(x) // Explicitly ignore the value
  let mut sum = 0
  ignore([1, 2, 3].iter().each((x) => { sum = sum + x })) // Ignore the Unit return value of each()
ignore
}

test "kvstore 3.0" {
  let Unit
backend = (Array[Server]) -> Unit
@moonchor.make_local_backend([Server
server, Client
client, Backup
backup])
  (() -> Unit) -> Unit
@toolkit.run_async(() => (Unit, async (?) -> Unit, Server) -> Unit
@moonchor.run_choreo(Unit
backend, async (ctx : ?) -> Unit
kvstore_v2, Server
server))
  (() -> Unit) -> Unit
@toolkit.run_async(() => (Unit, async (?) -> Unit, Client) -> Unit
@moonchor.run_choreo(Unit
backend, async (ctx : ?) -> Unit
kvstore_v2, Client
client))
  (() -> Unit) -> Unit
@toolkit.run_async(() => (Unit, async (?) -> Unit, Backup) -> Unit
@moonchor.run_choreo(Unit
backend, async (ctx : ?) -> Unit
kvstore_v2, Backup
backup))
}

Implementing Role-Polymorphism Through Parametric Polymorphism

To implement new replication strategies like triple replication, we need to define two new Backup types for differentiation:

struct Backup1 {} derive(trait Hash {
  hash_combine(Self, Hasher) -> Unit
  hash(Self) -> Int
}
Trait for types that can be hashed
Hash, trait Show {
  output(Self, &Logger) -> Unit
  to_string(Self) -> String
}
Trait for types that can be converted to String
Show)

impl @moonchor.Location for struct Backup1 {
}
Backup1 with (_/0) -> String
name(_) {
  "backup1"
}

let Backup1
backup1: struct Backup1 {
}
Backup1 = struct Backup1 {
}
Backup1::{}

struct Backup2 {} derive(trait Hash {
  hash_combine(Self, Hasher) -> Unit
  hash(Self) -> Int
}
Trait for types that can be hashed
Hash, trait Show {
  output(Self, &Logger) -> Unit
  to_string(Self) -> String
}
Trait for types that can be converted to String
Show)

impl @moonchor.Location for struct Backup2 {
}
Backup2 with (_/0) -> String
name(_) {
  "backup2"
}

let Backup2
backup2: struct Backup2 {
}
Backup2 = struct Backup2 {
}
Backup2::{}

Next, we need to modify the core logic of access_server. An immediate problem emerges: to have both Backup1 and Backup2 process the request and return responses, we'd need to repeat these statements: let request = unwrapper.unwrap(request_at_backup); let state = unwrapper.unwrap(state_at_backup); handle_request(state, request). Code duplication is a code smell that should be abstracted away. Here, moonchor's "roles as types" advantage becomes apparent - we can use MoonBit's parametric polymorphism to abstract the backup processing logic into a polymorphic function do_backup, which takes a role type parameter B representing the backup role:

async fn[B : @moonchor.Location] async (ctx : ?, request_at_server : ?, backup : B, state_at_backup : ?) -> ?
do_backup(
  ?
ctx : @moonchor.ChoreoContext,
  ?
request_at_server : @moonchor.Located[enum Request {
  Get(String)
  Put(String, Int)
}
Request, struct Server {
}
Server],
  B
backup : type parameter B
B,
  ?
state_at_backup : @moonchor.Located[struct ServerState {
  db: Map[String, Int]
}
ServerState, type parameter B
B]
) -> @moonchor.Located[enum Option[A] {
  None
  Some(A)
}
Response, struct Server {
}
Server] {
  let Unit
request_at_backup = ?
ctx.(Server, B, ?) -> Unit
comm(Server
server, B
backup, ?
request_at_server)
  let Unit
response_at_backup = ?
ctx.(B, (Unit) -> Int?) -> Unit
locally(B
backup, fn(Unit
unwrapper) {
    let Request
request = Unit
unwrapper.(Unit) -> Request
unwrap(Unit
request_at_backup)
    let ServerState
state = Unit
unwrapper.(?) -> ServerState
unwrap(?
state_at_backup)
    (state : ServerState, request : Request) -> Int?
handle_request(ServerState
state, Request
request)
  })
  ?
ctx.(B, Server, Unit) -> ?
comm(B
backup, Server
server, Unit
response_at_backup)
}

This enables us to freely implement either double or triple replication strategies. For the triple replication strategy, we simply need to call do_backup twice within the function returned by triple_replication_strategy:

async fn async (state_at_server : ?, state_at_backup1 : ?, state_at_backup2 : ?) -> async (?, ?) -> ?
triple_replication_strategy(
  ?
state_at_server: @moonchor.Located[struct ServerState {
  db: Map[String, Int]
}
ServerState, struct Server {
}
Server],
  ?
state_at_backup1: @moonchor.Located[struct ServerState {
  db: Map[String, Int]
}
ServerState, struct Backup1 {
}
Backup1],
  ?
state_at_backup2: @moonchor.Located[struct ServerState {
  db: Map[String, Int]
}
ServerState, struct Backup2 {
}
Backup2]
) -> ReplicationStrategy {
  fn(
    ?
ctx: @moonchor.ChoreoContext,
    ?
request_at_server: @moonchor.Located[enum Request {
  Get(String)
  Put(String, Int)
}
Request, struct Server {
}
Server]
  ) {
    let ?
backup_response1 = async (ctx : ?, request_at_server : ?, backup : Backup1, state_at_backup : ?) -> ?
do_backup(
      ?
ctx, ?
request_at_server, Backup1
backup1, ?
state_at_backup1,
    )
    let ?
backup_response2 = async (ctx : ?, request_at_server : ?, backup : Backup2, state_at_backup : ?) -> ?
do_backup(
      ?
ctx, ?
request_at_server, Backup2
backup2, ?
state_at_backup2,
    )
    ?
ctx.(Server, (Unit) -> Int?) -> ?
locally(Server
server, fn(Unit
unwrapper) {
      let Request
request = Unit
unwrapper.(?) -> Request
unwrap(?
request_at_server)
      let ServerState
state = Unit
unwrapper.(?) -> ServerState
unwrap(?
state_at_server)
      let Int?
res = (state : ServerState, request : Request) -> Int?
handle_request(ServerState
state, Request
request)
      (responses : Array[Int?]) -> Unit
check_consistency([
        Unit
unwrapper.(?) -> Int?
unwrap(?
backup_response1),
        Unit
unwrapper.(?) -> Int?
unwrap(?
backup_response2),
        Int?
res,
      ])
      Int?
res
    })
  }
}

Since we've successfully separated the replication strategy from the access process, the access_server, put, and get functions require no modifications. Let's test the final KVStore implementation:

async fn async (ctx : ?) -> Unit
kvstore_v4(?
ctx: @moonchor.ChoreoContext) -> Unit
Unit {
  let ?
state_at_server = ?
ctx.(Server, (Unit) -> ServerState) -> ?
locally(Server
server, Unit
_unwrapper => struct ServerState {
  db: Map[String, Int]
}
ServerState::() -> ServerState
new())
  let ?
state_at_backup1 = ?
ctx.(Backup1, (Unit) -> ServerState) -> ?
locally(Backup1
backup1, Unit
_unwrapper => struct ServerState {
  db: Map[String, Int]
}
ServerState::() -> ServerState
new())
  let ?
state_at_backup2 = ?
ctx.(Backup2, (Unit) -> ServerState) -> ?
locally(Backup2
backup2, Unit
_unwrapper => struct ServerState {
  db: Map[String, Int]
}
ServerState::() -> ServerState
new())
  let async (?, ?) -> ?
strategy = async (state_at_server : ?, state_at_backup1 : ?, state_at_backup2 : ?) -> async (?, ?) -> ?
triple_replication_strategy(
    ?
state_at_server, ?
state_at_backup1, ?
state_at_backup2,
  )
  async (ctx : ?, strategy : async (?, ?) -> ?, key : String, value : Int) -> Unit
put_v3(?
ctx, async (?, ?) -> ?
strategy, "key1", 42)
  async (ctx : ?, strategy : async (?, ?) -> ?, key : String, value : Int) -> Unit
put_v3(?
ctx, async (?, ?) -> ?
strategy, "key2", 41)
  let ?
v1_at_client = async (ctx : ?, strategy : async (?, ?) -> ?, key : String) -> ?
get_v3(?
ctx, async (?, ?) -> ?
strategy, "key1")
  let ?
v2_at_client = async (ctx : ?, strategy : async (?, ?) -> ?, key : String) -> ?
get_v3(?
ctx, async (?, ?) -> ?
strategy, "key2")
  ?
ctx.(Client, (Unit) -> Unit) -> Unit
locally(Client
client, fn(Unit
unwrapper) {
    let Int
v1 = Unit
unwrapper.(?) -> Unit
unwrap(?
v1_at_client).() -> Int
unwrap()
    let Int
v2 = Unit
unwrapper.(?) -> Unit
unwrap(?
v2_at_client).() -> Int
unwrap()
    if Int
v1 (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ Int
v2 (self : Int, other : Int) -> Bool
Compares two integers for equality.
Parameters:

self : The first integer to compare.
other : The second integer to compare.
Returns true if both integers have the same value, false otherwise.
Example:
  inspect(42 == 42, content="true")
  inspect(42 == -42, content="false")
== 83 {
      (input : String) -> Unit
Prints any value that implements the Show trait to the standard output,
followed by a newline.
Parameters:

value : The value to be printed. Must implement the Show trait.
Example:
  println(42)
  println("Hello, World!")
  println([1, 2, 3])
println("The server is working correctly")
    } else {
      () -> Unit
panic()
    }
  })
  |> (t : Unit) -> Unit
Evaluates an expression and discards its result. This is useful when you want
to execute an expression for its side effects but don't care about its return
value, or when you want to explicitly indicate that a value is intentionally
unused.
Parameters:

value : The value to be ignored. Can be of any type.
Example:
  let x = 42
  ignore(x) // Explicitly ignore the value
  let mut sum = 0
  ignore([1, 2, 3].iter().each((x) => { sum = sum + x })) // Ignore the Unit return value of each()
ignore
}

test "kvstore 4.0" {
  let Unit
backend = (Array[Server]) -> Unit
@moonchor.make_local_backend([Server
server, Client
client, Backup1
backup1, Backup2
backup2])
  (() -> Unit) -> Unit
@toolkit.run_async(() => (Unit, async (?) -> Unit, Server) -> Unit
@moonchor.run_choreo(Unit
backend, async (ctx : ?) -> Unit
kvstore_v4, Server
server))
  (() -> Unit) -> Unit
@toolkit.run_async(() => (Unit, async (?) -> Unit, Client) -> Unit
@moonchor.run_choreo(Unit
backend, async (ctx : ?) -> Unit
kvstore_v4, Client
client))
  (() -> Unit) -> Unit
@toolkit.run_async(() => (Unit, async (?) -> Unit, Backup1) -> Unit
@moonchor.run_choreo(Unit
backend, async (ctx : ?) -> Unit
kvstore_v4, Backup1
backup1))
  (() -> Unit) -> Unit
@toolkit.run_async(() => (Unit, async (?) -> Unit, Backup2) -> Unit
@moonchor.run_choreo(Unit
backend, async (ctx : ?) -> Unit
kvstore_v4, Backup2
backup2))
}

With this, we've completed the multi-replica KVStore implementation. Throughout this example, we never manually used any send or recv to express distributed node interactions. Instead, we leveraged moonchor's choreographic programming capabilities to handle all communication and synchronization processes, avoiding potential type errors, deadlocks, and explicit synchronization issues.

Conclusion

In this article, we've explored the elegance of choreographic programming through moonchor while witnessing MoonBit's powerful expressiveness. For deeper insights into choreographic programming, you may refer to Haskell's library HasChor, the Choral language, or moonchor 的源码. To try moonchor yourself, simply install it via the command moon add Milky2018/moonchor@0.15.0.

MoonBit Pearls Vol.03：01 knapsack problem

July 3, 2025 · 13 min read

The 0/1 Knapsack Problem is a classic dynamic programming (DP) problem commonly found in algorithm competitions. This article presents five versions of the solution, starting from a basic brute-force approach and gradually evolving into a DP-based implementation.

Problem Definition

There are several items, each with aweightand a value:

struct Item {
  Int
weight : Int
Int
  Int
value : Int
Int
}

Now, given a list of items (items) and a knapsack capacity (capacity), select a subset of the items such that the total weight does not exceed the knapsack capacity, and the total value is maximized.

typealias enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
@list.T as List

let @list.T[Item]
items_1 : enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Item {
  weight: Int
  value: Int
}
Item] = (arr : FixedArray[Item]) -> @list.T[Item]
@list.of([
  { Int
weight: 7, Int
value: 20 },
  { Int
weight: 4, Int
value: 10 },
  { Int
weight: 5, Int
value: 11 },
])

Take items_1 as an example. If the knapsack capacity is 10, the optimal solution is to select the last two items. Their combined weight is 4 + 5 = 9, and their total value is 10 + 11 = 21.

Note that items cannot be split. Therefore, greedily selecting the item with the highest value-to-weight ratio does not always yield the correct result.

For example, in the case above, if we pick only the first item (which has the highest ratio), we get 20 points in total, but the knapsack will be full and no other items can be added.

Problem Modeling

First, we define some basic objects and operations.

//A combination of items, referred to as "combination" throughout the article
struct Combination {
  @list.T[Item]
items : enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Item {
  weight: Int
  value: Int
}
Item]
  Int
total_weight : Int
Int
  Int
total_value : Int
Int
}

//An empty combination
let Combination
empty_combination : struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination = {
  @list.T[Item]
items: () -> @list.T[Item]
Creates an empty list
@list.empty(),
  Int
total_weight: 0,
  Int
total_value: 0,
}

//Add an item to a combination and return a new combination
fn struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination::(self : Combination, item : Item) -> Combination
add(Combination
self : struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination, Item
item : struct Item {
  weight: Int
  value: Int
}
Item) -> struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination {
  {
    @list.T[Item]
items: Combination
self.@list.T[Item]
items.(self : @list.T[Item], head : Item) -> @list.T[Item]
add(Item
item),
    Int
total_weight: Combination
self.Int
total_weight (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ Item
item.Int
weight,
    Int
total_value: Combination
self.Int
total_value (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ Item
item.Int
value,
  }
}

//Two combinations are considered equal if they have the same total value
impl trait Eq {
  op_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
Eq for struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination with (self : Combination, other : Combination) -> Bool
op_equal(Combination
self, Combination
other) {
  Combination
self.Int
total_value (self : Int, other : Int) -> Bool
Compares two integers for equality.
Parameters:

self : The first integer to compare.
other : The second integer to compare.
Returns true if both integers have the same value, false otherwise.
Example:
  inspect(42 == 42, content="true")
  inspect(42 == -42, content="false")
== Combination
other.Int
total_value
}

//Compare two combinations by their total value
impl trait Compare {
  compare(Self, Self) -> Int
}
Trait for types whose elements are ordered
The return value of [compare] is:

zero, if the two arguments are equal
negative, if the first argument is smaller
positive, if the first argument is greater
Compare for struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination with (self : Combination, other : Combination) -> Int
compare(Combination
self, Combination
other) {
  Combination
self.Int
total_value.(self : Int, other : Int) -> Int
Compares two integers and returns their relative order.
Parameters:

self : The first integer to compare.
other : The second integer to compare against.
Returns an integer indicating the relative order:

A negative value if self is less than other
Zero if self equals other
A positive value if self is greater than other
Example:
  let a = 42
  let b = 24
  inspect(a.compare(b), content="1") // 42 > 24
  inspect(b.compare(a), content="-1") // 24 < 42
  inspect(a.compare(a), content="0") // 42 = 42
compare(Combination
other.Int
total_value)
}

Now, we can begin thinking about how to solve the problem.

1.Naive Enumeration

Enumeration is the most straightforward approach. By following the problem definition step by step, we can arrive at a solution:

Enumerate all possible combinations;
Filter out only the valid combinations-those that fit in the knapsack;
Select the one with the maximum total value.

Thanks to the two functions provided by our modeling, we can translate the three steps above directly into MoonBit code. The all_combinations function, which we'll implement later, has the type(List[Item]) -> List[Combination].

fn (items : @list.T[Item], capacity : Int) -> Combination
solve_v1(@list.T[Item]
items : enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Item {
  weight: Int
  value: Int
}
Item], Int
capacity : Int
Int) -> struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination {
  (items : @list.T[Item]) -> @list.T[Combination]
all_combinations(@list.T[Item]
items)
  .(self : @list.T[Combination], f : (Combination) -> Bool) -> @list.T[Combination]
Filter the list.
Example
  assert_eq(@list.of([1, 2, 3, 4, 5]).filter(x => x % 2 == 0), @list.of([2, 4]))
filter(fn(Combination
comb) { Combination
comb.Int
total_weight (self_ : Int, other : Int) -> Bool
<= Int
capacity })
  .(self : @list.T[Combination]) -> Combination
unsafe_maximum()
}

Note that we use unsafe_maximum instead of maximum because we're taking the maximum of a non-empty list, and in this case, maximum will not return None.Since the problem guarantees that a solution exists (as long as capacity is non-negative), we can safely use unsafe_maximum. It skips the empty-list check but implicitly assumes the result will exist.

Now let's implement the enumeration step.Suppose all_combinations takes a list of items and returns a list of combinations, each representing a possible subset of those items. If this seems unclear at first, we can begin by looking at the definition of the list structure, which looks roughly like this:

enum List[A] {
  Empty
  More(A, tail~ : List[A])
}

In other words, a list has two possible forms:

An empty list, represented as Empty;
A non-empty list, represented as More, which contains the first element (A) and the rest of the list (tail: List[A]), which is itself also a list.

This structure gives us a hint for how to recursively build combinations:

If the item list is empty, the only possible combination is the empty combination;
Otherwise, there must be a first item item1 and a remaining list items_tail. In this case, we can:
1. Recursively compute all combinations of items_tail, which represent combinations that do not include item1;
2. For each of those, add item1 to form new combinations that do include it;
3. Merge both sets to obtain all combinations of the original items list.

For example, if the item list is a, b, c, then the combinations can be divided into two parts:

Without a	With a (by adding a to the left side)
{ }	{ a }
{ b }	{ a, b }
{ c }	{ a, c }
{ b, c }	{ a, b, c }

fn (items : @list.T[Item]) -> @list.T[Combination]
all_combinations(@list.T[Item]
items : enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Item {
  weight: Int
  value: Int
}
Item]) -> enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination] {
  match @list.T[Item]
items {
    @list.T[Item]
Empty => (x : Combination) -> @list.T[Combination]
@list.singleton(Combination
empty_combination)
    (Item, @list.T[Item]) -> @list.T[Item]
More(Item
item1, @list.T[Item]
tail=@list.T[Item]
items_tail) => {
      let @list.T[Combination]
combs_without_item1 = (items : @list.T[Item]) -> @list.T[Combination]
all_combinations(@list.T[Item]
items_tail)
      let @list.T[Combination]
combs_with_item1 = @list.T[Combination]
combs_without_item1.(self : @list.T[Combination], f : (Combination) -> Combination) -> @list.T[Combination]
Maps the list.
Example
  assert_eq(@list.of([1, 2, 3, 4, 5]).map(x => x * 2), @list.of([2, 4, 6, 8, 10]))
map(_.(self : Combination, item : Item) -> Combination
add(Item
item1))
      @list.T[Combination]
combs_with_item1 (self : @list.T[Combination], other : @list.T[Combination]) -> @list.T[Combination]
Concatenate two lists.
a + b equal to a.concat(b)
+ @list.T[Combination]
combs_without_item1
    }
  }
}

By using pattern matching (match), we've translated the five lines of logic above into MoonBit code for the first time, line by line.

2.Early Filtering: Enumerate Only Valid Combinations

In the first version, generating all combinations and filtering out those that fit in the knapsack were two separate steps.During the enumeration process, many invalid combinations were generated-combinations that had already exceeded the knapsack capacity but were still extended with more items.If we filter them earlier, we can avoid generating many unnecessary combinations on top of invalid ones, which is clearly more efficient.Looking at the code, we see that invalid combinations are only produced during .map(_.add(item1)).So we can optimize by only adding item1 to combinations that can still fit it.

We now rename all_combinations to all_combinations_valid, which returns only combinations that can actually fit in the knapsack. The generation and filtering processes are now interleaved.

fn (items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid(
  @list.T[Item]
items : enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Item {
  weight: Int
  value: Int
}
Item],
  Int
capacity : Int
Int // Add capacity as a parameter because filtering requires it
) -> enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination] {
  match @list.T[Item]
items {
    @list.T[Item]
Empty => (x : Combination) -> @list.T[Combination]
@list.singleton(Combination
empty_combination) // An empty combination is always valid
    (Item, @list.T[Item]) -> @list.T[Item]
More(Item
item1, @list.T[Item]
tail=@list.T[Item]
items_tail) => {
      // Recursively obtain combinations without this item (by assumption, all valid)
      let @list.T[Combination]
valid_combs_without_item1 = (items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid(
        @list.T[Item]
items_tail, Int
capacity,
      )
      // Add item1 to valid combinations that can still hold it
      let @list.T[Combination]
valid_combs_with_item1 = @list.T[Combination]
valid_combs_without_item1
        .(self : @list.T[Combination], f : (Combination) -> Bool) -> @list.T[Combination]
Filter the list.
Example
  assert_eq(@list.of([1, 2, 3, 4, 5]).filter(x => x % 2 == 0), @list.of([2, 4]))
filter(fn(Combination
comb) { Combination
comb.Int
total_weight (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ Item
item1.Int
weight (self_ : Int, other : Int) -> Bool
<= Int
capacity })
        .(self : @list.T[Combination], f : (Combination) -> Combination) -> @list.T[Combination]
Maps the list.
Example
  assert_eq(@list.of([1, 2, 3, 4, 5]).map(x => x * 2), @list.of([2, 4, 6, 8, 10]))
map(_.(self : Combination, item : Item) -> Combination
add(Item
item1))
      // Both parts are valid, so we return their union
      @list.T[Combination]
valid_combs_with_item1 (self : @list.T[Combination], other : @list.T[Combination]) -> @list.T[Combination]
Concatenate two lists.
a + b equal to a.concat(b)
+ @list.T[Combination]
valid_combs_without_item1
    }
  }
}

This structure naturally supports inductive reasoning, making it easy to prove the correctness of all_combinations_valid-it indeed returns only valid combinations.

Since all_combinations_valid already returns only valid combinations, we no longer need to filter in solve.We simply remove the filter from solve:

fn (items : @list.T[Item], capacity : Int) -> Combination
solve_v2(@list.T[Item]
items : enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Item {
  weight: Int
  value: Int
}
Item], Int
capacity : Int
Int) -> struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination {
  (items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid(@list.T[Item]
items, Int
capacity).(self : @list.T[Combination]) -> Combination
unsafe_maximum()
}

3.Maintain Order to Enable Early Termination

In the previous version, to construct new combinations, we needed to iterate over every combination in valid_combs_without_item1.

But we can observe: if item1 cannot be added to a certain combination, then it definitely cannot be added to any combination with a greater total weight than that one. In other words, if valid_combs_without_item1 is sorted in ascending order of total weight, then we don't need to traverse it entirely during filtering.

During filtering, as soon as we encounter a combination that can't fit item1, we can immediately discard the remaining combinations.Since this logic is common, the standard library provides a function called take_while, which we use to replace filter.

To make valid_combs_without_item1 sorted, we could use a sorting algorithm-but that would require traversing the entire list, which defeats the purpose.Therefore, we adopt a different approach: ensure that the list returned by all_combinations_valid is already sorted in ascending order.

This requires a leap of faith via recursion:

fn (items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid_ordered(
  @list.T[Item]
items : enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Item {
  weight: Int
  value: Int
}
Item],
  Int
capacity : Int
Int
) -> enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination] {
  match @list.T[Item]
items {
    @list.T[Item]
Empty => (x : Combination) -> @list.T[Combination]
@list.singleton(Combination
empty_combination) // A single-element list is naturally in ascending order.
    (Item, @list.T[Item]) -> @list.T[Item]
More(Item
item1, @list.T[Item]
tail=@list.T[Item]
items_tail) => {
      // We assume that all_combinations_valid_ordered returns a list sorted in ascending order (inductive hypothesis).
      let @list.T[Combination]
valid_combs_without_item1 = (items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid_ordered(
        @list.T[Item]
items_tail, Int
capacity,
      )
      // Then valid_combs_with_item1 is also in ascending order, because taking a prefix of an ascending list and adding the same weight to each element still yields an ascending list by total weight.
      let @list.T[Combination]
valid_combs_with_item1 = @list.T[Combination]
valid_combs_without_item1
        .(self : @list.T[Combination], p : (Combination) -> Bool) -> @list.T[Combination]
Take the longest prefix of a list of elements that satisfies a given predicate.
Example
  let ls = @list.from_array([1, 2, 3, 4])
  let r = ls.take_while(x => x < 3)
  assert_eq(r, @list.of([1, 2]))
take_while(fn(Combination
comb) { Combination
comb.Int
total_weight (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ Item
item1.Int
weight (self_ : Int, other : Int) -> Bool
<= Int
capacity })
        .(self : @list.T[Combination], f : (Combination) -> Combination) -> @list.T[Combination]
Maps the list.
Example
  assert_eq(@list.of([1, 2, 3, 4, 5]).map(x => x * 2), @list.of([2, 4, 6, 8, 10]))
map(_.(self : Combination, item : Item) -> Combination
add(Item
item1))
      // Now, we only need to ensure that the merged result is also sorted in ascending order to maintain our initial assumption.
      (a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order(@list.T[Combination]
valid_combs_with_item1, @list.T[Combination]
valid_combs_without_item1)
    }
  }
}

The final task is to implement the function merge_keep_order, which merges two ascending lists into one ascending list:

fn (a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order(
  @list.T[Combination]
a : enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination],
  @list.T[Combination]
b : enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination]
) -> enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination] {
  match (@list.T[Combination]
a, @list.T[Combination]
b) {
    (@list.T[Combination]
Empty, @list.T[Combination]
another) | (@list.T[Combination]
another, @list.T[Combination]
Empty) => @list.T[Combination]
another
    ((Combination, @list.T[Combination]) -> @list.T[Combination]
More(Combination
a1, @list.T[Combination]
tail=@list.T[Combination]
a_tail), (Combination, @list.T[Combination]) -> @list.T[Combination]
More(Combination
b1, @list.T[Combination]
tail=@list.T[Combination]
b_tail)) =>
      // If a1 is lighter than b1, and b1 is part of an ascending list, then:
      //   a1 is lighter than all combinations in b
      // Since list a is also in ascending order
      //   a1 is also lighter than all combinations in a_tail
      // Therefore, a1 is the smallest among all elements in a and b
      if Combination
a1.Int
total_weight (self_ : Int, other : Int) -> Bool
< Combination
b1.Int
total_weight {
        // We first recursively merge the rest of the list, then prepend a1
        (a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order(@list.T[Combination]
a_tail, @list.T[Combination]
b).(self : @list.T[Combination], head : Combination) -> @list.T[Combination]
add(Combination
a1)
      } else { //
        (a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order(@list.T[Combination]
a, @list.T[Combination]
b_tail).(self : @list.T[Combination], head : Combination) -> @list.T[Combination]
add(Combination
b1)
      }
  }
}

Although it might seem a bit verbose, I still want to point this out: by following a case-based analysis aligned with the structure of the code, it's actually easy to prove the correctness of all_combinations_valid_ordered and merge_keep_order - they do return a sorted list.

For an ascending list, the maximum element is simply the last one. So we replaced unsafe_maximum with unsafe_last.

fn (items : @list.T[Item], capacity : Int) -> Combination
solve_v3(@list.T[Item]
items : enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Item {
  weight: Int
  value: Int
}
Item], Int
capacity : Int
Int) -> struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination {
  (items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid_ordered(@list.T[Item]
items, Int
capacity).(self : @list.T[Combination]) -> Combination
unsafe_last()
}

Looking back, this version of the optimization might not seem like a big win - after all, we still have to traverse the entire list during the merge. That was my initial impression too, but I later discovered something unexpected.

4.Removing Redundant Combinations with Equal Weights for Optimal Time Complexity

So far, the optimizations we've made haven't addressed time complexity, but they've laid the groundwork for this next step. Now let's consider the algorithm's time complexity.

In the worst case (e.g., when the knapsack is large enough to hold everything), the combination list returned by all_combinations can contain up to $2^{number of items}$ elements. This results in an exponential time complexity, especially since all_combinations is called multiple times, each time returning a potentially large list.

To reduce the time complexity, we need to limit the length of the candidate combination list. This is based on a simple observation: if two combinations have the same total weight, the one with the higher total value is always better. Therefore, we don't need to keep both in the list.

By eliminating these redundant combinations, the list length will never exceed the knapsack's capacity (thanks to the pigeonhole principle). This optimization reduces the algorithm's time complexity to $\mathcal{O}(number of items \times capacity)$ . Upon reviewing the code, the only place where redundant combinations may still be introduced is the else branch of merge_keep_order. To prevent this, we just need to make a small modification to that section.

fnalias (x : T, y : T) -> T
@math.maximum

fn (a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order_and_dedup(
  @list.T[Combination]
a : enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination],
  @list.T[Combination]
b : enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination]
) -> enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination] {
  match (@list.T[Combination]
a, @list.T[Combination]
b) {
    (@list.T[Combination]
Empty, @list.T[Combination]
another) | (@list.T[Combination]
another, @list.T[Combination]
Empty) => @list.T[Combination]
another
    ((Combination, @list.T[Combination]) -> @list.T[Combination]
More(Combination
a1, @list.T[Combination]
tail=@list.T[Combination]
a_tail), (Combination, @list.T[Combination]) -> @list.T[Combination]
More(Combination
b1, @list.T[Combination]
tail=@list.T[Combination]
b_tail)) =>
      if Combination
a1.Int
total_weight (self_ : Int, other : Int) -> Bool
< Combination
b1.Int
total_weight {
        (a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order_and_dedup(@list.T[Combination]
a_tail, @list.T[Combination]
b).(self : @list.T[Combination], head : Combination) -> @list.T[Combination]
add(Combination
a1)
      } else if Combination
a1.Int
total_weight (self_ : Int, other : Int) -> Bool
> Combination
b1.Int
total_weight {
        (a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order_and_dedup(@list.T[Combination]
a, @list.T[Combination]
b_tail).(self : @list.T[Combination], head : Combination) -> @list.T[Combination]
add(Combination
b1)
      } else { // "In this case, a1 and b1 have the same weight, creating a duplicate. We keep the one with the higher total value."
        let Combination
better = (x : Combination, y : Combination) -> Combination
maximum(Combination
a1, Combination
b1)
        (a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order_and_dedup(@list.T[Combination]
a_tail, @list.T[Combination]
b_tail).(self : @list.T[Combination], head : Combination) -> @list.T[Combination]
add(Combination
better)
      }
  }
}

Simply replace the corresponding parts with all_combinations_valid_ordered_nodup (arguably the longest function name I've ever written) and solve_v4.

fn (items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid_ordered_nodup(
  @list.T[Item]
items : enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Item {
  weight: Int
  value: Int
}
Item],
  Int
capacity : Int
Int
) -> enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination] {
  match @list.T[Item]
items {
    @list.T[Item]
Empty => (x : Combination) -> @list.T[Combination]
@list.singleton(Combination
empty_combination)
    (Item, @list.T[Item]) -> @list.T[Item]
More(Item
item1, @list.T[Item]
tail=@list.T[Item]
items_tail) => {
      let @list.T[Combination]
combs_without_item1 = (items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid_ordered_nodup(
        @list.T[Item]
items_tail, Int
capacity,
      )
      let @list.T[Combination]
combs_with_item1 = @list.T[Combination]
combs_without_item1
        .(self : @list.T[Combination], p : (Combination) -> Bool) -> @list.T[Combination]
Take the longest prefix of a list of elements that satisfies a given predicate.
Example
  let ls = @list.from_array([1, 2, 3, 4])
  let r = ls.take_while(x => x < 3)
  assert_eq(r, @list.of([1, 2]))
take_while(fn(Combination
comb) { Combination
comb.Int
total_weight (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ Item
item1.Int
weight (self_ : Int, other : Int) -> Bool
<= Int
capacity })
        .(self : @list.T[Combination], f : (Combination) -> Combination) -> @list.T[Combination]
Maps the list.
Example
  assert_eq(@list.of([1, 2, 3, 4, 5]).map(x => x * 2), @list.of([2, 4, 6, 8, 10]))
map(_.(self : Combination, item : Item) -> Combination
add(Item
item1))
      (a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order_and_dedup(@list.T[Combination]
combs_with_item1, @list.T[Combination]
combs_without_item1)
    }
  }
}

fn (items : @list.T[Item], capacity : Int) -> Combination
solve_v4(@list.T[Item]
items : enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Item {
  weight: Int
  value: Int
}
Item], Int
capacity : Int
Int) -> struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination {
  (items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_valid_ordered_nodup(@list.T[Item]
items, Int
capacity).(self : @list.T[Combination]) -> Combination
unsafe_last()
}

At this point, we've essentially reinvented the dynamic programming solution for the 0/1 knapsack problem.

Conclusion

This article's content came from a sudden idea I had one morning while lying in bed. From the first to the fourth version, all code was written entirely on my phone without any debugging-yet correctness was easily guaranteed. Compared to conventional solutions often seen in algorithm competitions, the functional programming style used here brings the following advantages:

No loops, only recursion and structural decomposition. To extract elements from a list, pattern matching (match) is required, which naturally prompts consideration of empty cases and expresses intent more clearly than initializing a DP array.
Composition of higher-order functions. Standard functions like filter, take_while, map, and maximum replace boilerplate loops (for, while), making the traversal purpose clearer at a glance.
Declarative code. The later versions of the solution are direct translations of the first one. Rather than just implementing a solution, the code describes the problem itself. This ensures the correctness of the first version. Each subsequent improvement was made without affecting the correctness, allowing for a safe and iterative process.

Of course, this solution doesn't apply state space compression, so a tradeoff between readability and efficiency remains. The functional style is slightly idealistic but still leaves room for many optimizations. A future direction would be to convert the list structure into a tree, exploiting the fact that functions only pass two argument groups throughout execution-possibly even a single value. This could reduce space complexity to O(capacity), though it's beyond the scope of this article. We believe the approach here offers a beginner-friendly and understandable way to write correct code.

Appendix

Further Optimization Details

Given that the order of items does not affect the total value of the result, we can convert all_combinations into a tail-recursive version.

Additionally, since the list produced by take_while is immediately discarded after being passed to map, certain syntax-level techniques can be used to avoid creating this temporary list altogether.

fn (items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_loop(
  @list.T[Item]
items : enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Item {
  weight: Int
  value: Int
}
Item],
  Int
capacity : Int
Int
) -> enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination] {
  loop @list.T[Item]
items, (x : Combination) -> @list.T[Combination]
@list.singleton(Combination
empty_combination) {
    @list.T[Item]
Empty, @list.T[Combination]
combs_so_far => @list.T[Combination]
combs_so_far
    (Item, @list.T[Item]) -> @list.T[Item]
More(Item
item1, @list.T[Item]
tail=@list.T[Item]
items_tail), @list.T[Combination]
combs_so_far => {
      let @list.T[Combination]
combs_without_item1 = @list.T[Combination]
combs_so_far
      let @list.T[Combination]
combs_with_item1 = @list.T[Combination]
combs_without_item1
        .(self : @list.T[Combination]) -> Iter[Combination]
iter()
        .(self : Iter[Combination], f : (Combination) -> Bool) -> Iter[Combination]
Takes elements from the iterator as long as the predicate function returns true.
Type Parameters

T: The type of the elements in the iterator.
Arguments

self - The input iterator.
f - The predicate function that determines whether an element should be taken.
Returns
A new iterator that contains the elements as long as the predicate function returns true.
take_while(fn(Combination
comb) { Combination
comb.Int
total_weight (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ Item
item1.Int
weight (self_ : Int, other : Int) -> Bool
<= Int
capacity })
        .(self : Iter[Combination], f : (Combination) -> Combination) -> Iter[Combination]
Transforms the elements of the iterator using a mapping function.
Type Parameters

T: The type of the elements in the iterator.
R: The type of the transformed elements.
Arguments

self - The input iterator.
f - The mapping function that transforms each element of the iterator.
Returns
A new iterator that contains the transformed elements.
map(_.(self : Combination, item : Item) -> Combination
add(Item
item1))
        |> (iter : Iter[Combination]) -> @list.T[Combination]
Convert the iterator into a list. Preserves order of elements.
If the order of elements is not important, use from_iter_rev instead.
@list.from_iter
      continue @list.T[Item]
items_tail,
        (a : @list.T[Combination], b : @list.T[Combination]) -> @list.T[Combination]
merge_keep_order_and_dedup(@list.T[Combination]
combs_with_item1, @list.T[Combination]
combs_without_item1)
    }
  }
}

fn (items : @list.T[Item], capacity : Int) -> Combination
solve_v5(@list.T[Item]
items : enum @list.T[A] {
  Empty
  More(A, tail~ : @list.T[A])
}
List[struct Item {
  weight: Int
  value: Int
}
Item], Int
capacity : Int
Int) -> struct Combination {
  items: @list.T[Item]
  total_weight: Int
  total_value: Int
}
Combination {
  (items : @list.T[Item], capacity : Int) -> @list.T[Combination]
all_combinations_loop(@list.T[Item]
items, Int
capacity).(self : @list.T[Combination]) -> Combination
unsafe_last()
}

Side Notes

In the first version, the Combination generated by all_combinations(items) even contains one more node than More, making it a true master of linked list node reuse.
An ascending order can't be treated as "broken" order, so the corresponding take_while must be converted to drop_while. When using an array, we can directly cut segments via binary_search on indices.
If you're interested, consider how to generalize the above approach to various other knapsack problems.
The original name of all_combinations_loop was: generate_all_ordered_combination_that_fit_in_backpack_list_without_duplicates_using_loop.

Test

test {
  for (@list.T[Item], Int) -> Combination
solve in [(items : @list.T[Item], capacity : Int) -> Combination
solve_v1, (items : @list.T[Item], capacity : Int) -> Combination
solve_v2, (items : @list.T[Item], capacity : Int) -> Combination
solve_v3, (items : @list.T[Item], capacity : Int) -> Combination
solve_v4, (items : @list.T[Item], capacity : Int) -> Combination
solve_v5] {
    (a : Int, b : Int, msg? : String, loc~ : SourceLoc = _) -> Unit raise Error
Asserts that two values are equal. If they are not equal, raises a failure
with a message containing the source location and the values being compared.
Parameters:

a : First value to compare.
b : Second value to compare.
loc : Source location information to include in failure messages. This is
usually automatically provided by the compiler.
Throws a Failure error if the values are not equal, with a message showing
the location of the failing assertion and the actual values that were
compared.
Example:
  assert_eq(1, 1)
  assert_eq("hello", "hello")
assert_eq((@list.T[Item], Int) -> Combination
solve(@list.T[Item]
items_1, 10).Int
total_value, 21)
  }
}

MoonBit Pearls Vol.02:Object-Oriented Programming in Moonbit

June 23, 2025 · 20 min read

Liu Ziyue

16：9moonbit pearls封面.png

Introduction

In the world of software development, object-oriented programming (OOP) is an unavoidable topic. Languages like Java and C++ have built countless complex systems with their powerful OOP mechanisms. However, Moonbit, as a modern language centered around functional programming, how does it implement OOP?

Moonbit is a language with functional programming at its core, and its approach to object-oriented programming differs significantly from traditional programming languages. It abandons traditional inheritance mechanisms in favor of the "composition over inheritance" design philosophy. At first glance, this might feel unfamiliar to programmers accustomed to traditional OOP, but upon closer inspection, you'll discover an unexpected elegance and practicality in this approach.

This article will take you through an in-depth exploration of object-oriented programming in Moonbit using a vivid RPG game development example. We'll dissect the three major OOP characteristics—encapsulation, inheritance, and polymorphism—and compare them with their C++ counterparts. Finally, we'll provide some best practice recommendations for real-world development.

Encapsulation

Imagine we're developing a classic single-player RPG game. In this fantasy world, heroes roam, battle monsters, purchase equipment from NPC merchants, and ultimately rescue a trapped princess. To build such a world, we first need to model all its elements.

Whether it's brave heroes, vicious monsters, or simple tables and chairs, all objects in the game world share some common features. We can abstract these objects as Sprites, with each Sprite having a few basic attributes:

ID: A unique identifier for the object, like an ID number.
x and y: Coordinates on the game map.

Classic Encapsulation in C++

In C++, we're accustomed to using class to encapsulate data:

// A basic Sprite class
class Sprite {
private:
    int id;
    double x;
    double y;

public:
    // Constructor to create objects
    Sprite(int id, double x, double y) : id(id), x(x), y(y) {}

    // Public "getter" methods to access data
    int getID() const { return id; }
    double getX() const { return x; }
    double getY() const { return y; }

    // "Setter" methods to modify data
    void setX(double newX) { x = newX; }
    void setY(double newY) { y = newY; }
};

You might ask, "Why bother with all these get methods? Why not just make the fields public?" This question touches on the core idea of encapsulation.

Why Encapsulation?

Imagine if your colleague directly modified sprite.id = enemy_id. The hero could instantly "transform" into an ally of the enemy and waltz straight to the end—clearly not the game mechanic we want! Encapsulation acts like a protective net around data. private fields paired with getter methods ensure that external code can only read critical data but not modify it arbitrarily. This design makes the code more robust, avoiding unintended side effects.

Elegant Encapsulation in Moonbit

In Moonbit, the approach to encapsulation undergoes a subtle yet important shift. Let's look at a simple version first:

// Defining Sprite in Moonbit
pub struct Sprite {
  id: Int          // Immutable by default, readable but not writable externally
  mut x: Double    // `mut` keyword indicates mutability
  mut y: Double
}

// We can define methods for the struct
pub fn Sprite::get_x(self: Self) -> Double {
  self.x
}

pub fn Sprite::get_y(self: Self) -> Double {
  self.y
}

pub fn Sprite::set_x(self: Self, new_x: Double) -> Unit {
  self.x = new_x
}

pub fn Sprite::set_y(self: Self, new_y: Double) -> Unit {
  self.y = new_y
}

Two key differences stand out here:

1. Explicit Mutability Declaration

In Moonbit, fields are immutable by default. If you want a field to be modifiable, you must explicitly use the mut keyword. In our Sprite, id remains immutable—perfectly aligning with our design intent, as we don't want an object's identity to be arbitrarily altered. Meanwhile, x and y are marked as mut because sprites need to move freely in the world.

2. Simpler Access Control

Since id is immutable by default, we don't even need to write a get_id method for it! External code can directly read it via sprite.id, but any attempt to modify it will be firmly rejected by the compiler. This is more concise than C++'s "private + getter" pattern while maintaining the same level of safety.

💡 Practical Advice

When designing data structures, prioritize determining which fields truly need to be mutable. Moonbit's default immutability helps avoid many unintended state modification bugs.

Inheritance

The second pillar of object-oriented programming is inheritance. In our RPG world, there are various types of Sprites. For simplicity, we'll define three:

Hero: The player-controlled character.
Enemy: Opponents to be defeated.
Merchant: NPCs who sell items.

Inheritance Hierarchy in C++

In C++, we naturally use class inheritance to build this hierarchy:

class Hero : public Sprite {
private:
    double hp;
    double damage;
    int money;

public:
    Hero(int id, double x, double y, double hp, double damage, int money)
        : Sprite(id, x, y), hp(hp), damage(damage), money(money) {}

    void attack(Enemy& e) { /* ... */ }
};

class Enemy : public Sprite {
private:
    double hp;
    double damage;

public:
    Enemy(int id, double x, double y, double hp, double damage)
        : Sprite(id, x, y), hp(hp), damage(damage) {}

    void attack(Hero& h) { /* ... */ }
};

class Merchant : public Sprite {
public:
    Merchant(int id, double x, double y) : Sprite(id, x, y) {}
    // Merchant-specific methods...
};

C++'s object-oriented approach is built on the "is-a" relationship: Hero is a Sprite, Enemy is a Sprite. This way of thinking is intuitive and easy to grasp.

Composition-Based Thinking in Moonbit

Now, let's switch to Moonbit. Here, we need to make an important mental shift: Moonbit's structs do not support direct inheritance. Instead, we use traits and composition.

This design forces us to rethink the problem: we no longer treat Sprite as an inheritable "parent class" but instead split it into two independent concepts:

SpriteData: A pure data structure storing all shared Sprite data.
Sprite: A trait defining the behaviors all Sprites should have.

Here's the actual code:

// 1. Define the shared data structure
pub struct SpriteData {
  id: Int
  mut x: Double
  mut y: Double
}

// 2. Define the Trait describing common behaviors
pub trait Sprite {
  getSpriteData(Self) -> SpriteData  // Core method that must be implemented
  getID(Self) -> Int = _             // = _ indicates a default implementation
  getX(Self) -> Double = _
  getY(Self) -> Double = _
  setX(Self, Double) -> Unit = _
  setY(Self, Double) -> Unit = _
}

// Default implementations for Sprite
// Once getSpriteData is implemented, other methods become automatically available
impl Sprite with getID(self) {
  self.getSpriteData().id
}

impl Sprite with getX(self) {
  self.getSpriteData().x
}

impl Sprite with getY(self) {
  self.getSpriteData().y
}

impl Sprite with setX(self, new_x) {
  self.getSpriteData().x = new_x
}

impl Sprite with setY(self, new_y) {
  self.getSpriteData().y = new_y
}

Understanding the Power of Traits

The Sprite trait defines a "contract": any type claiming to be a Sprite must be able to provide its SpriteData. Once this condition is met, methods like getID, getX, and getY become automatically available. The = _ syntax indicates that the method has a default implementation, a new syntactic feature in Moonbit.

With this foundation, we can implement concrete game characters:

// Define Hero
pub struct Hero {
  SpriteData
sprite_data: struct SpriteData {
  id: Int
  mut x: Double
  mut y: Double
}
SpriteData  // Composing SpriteData
  Double
hp: Double
Double
  Int
damage: Int
Int
  Int
money: Int
Int
}

// Implement the Sprite trait, only needing to provide getSpriteData
pub impl trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite for struct Hero {
  sprite_data: SpriteData
  hp: Double
  damage: Int
  money: Int
}
Hero with (self : Hero) -> SpriteData
getSpriteData(Hero
self) {
  Hero
self.SpriteData
sprite_data
}

pub fn struct Hero {
  sprite_data: SpriteData
  hp: Double
  damage: Int
  money: Int
}
Hero::(self : Hero, e : Enemy) -> Unit
attack(Hero
self: struct Hero {
  sprite_data: SpriteData
  hp: Double
  damage: Int
  money: Int
}
Self, Enemy
e: struct Enemy {
  sprite_data: SpriteData
  hp: Double
  damage: Int
}
Enemy) -> Unit
Unit {
  // Attack logic...
}

// Define Enemy
pub struct Enemy {
  SpriteData
sprite_data: struct SpriteData {
  id: Int
  mut x: Double
  mut y: Double
}
SpriteData
  Double
hp: Double
Double
  Int
damage: Int
Int
}

pub impl trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite for struct Enemy {
  sprite_data: SpriteData
  hp: Double
  damage: Int
}
Enemy with (self : Enemy) -> SpriteData
getSpriteData(Enemy
self) {
  Enemy
self.SpriteData
sprite_data
}

pub fn struct Enemy {
  sprite_data: SpriteData
  hp: Double
  damage: Int
}
Enemy::(self : Enemy, h : Hero) -> Unit
attack(Enemy
self: struct Enemy {
  sprite_data: SpriteData
  hp: Double
  damage: Int
}
Self, Hero
h: struct Hero {
  sprite_data: SpriteData
  hp: Double
  damage: Int
  money: Int
}
Hero) -> Unit
Unit {
  // Attack logic...
}

// Define Merchant
pub struct Merchant {
  SpriteData
sprite_data: struct SpriteData {
  id: Int
  mut x: Double
  mut y: Double
}
SpriteData
}

pub impl trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite for struct Merchant {
  sprite_data: SpriteData
}
Merchant with (self : Merchant) -> SpriteData
getSpriteData(Merchant
self) {
  Merchant
self.SpriteData
sprite_data
}

Note the shift in mindset here: Moonbit adopts a "has-a" relationship instead of the traditional OOP "is-a" relationship. Hero has SpriteData and implements the Sprite capabilities.

Does Moonbit Seem More Complex?

At first glance, Moonbit's code might appear to require more "boilerplate" than C++. But this is only superficial! Here, we deliberately avoided many complexities inherent in C++: constructors, destructors, const correctness, template instantiation, etc. More importantly, Moonbit's design shines in large-scale projects—we'll discuss this in detail later.

Polymorphism

Polymorphism is the third pillar of object-oriented programming, referring to the ability of the same interface to produce different behaviors when applied to different objects. Let's explore this through a concrete example: suppose we need to implement a who_are_you function that can identify the type of an object and return an appropriate response.

Polymorphism Mechanisms in C++

C++'s polymorphism mechanisms are complex, encompassing static polymorphism (templates) and dynamic polymorphism (virtual functions, RTTI, etc.). A full discussion of C++ polymorphism is beyond this article's scope, but we'll focus on two classic runtime polymorphism approaches.

Method 1: Virtual Function Mechanism

The traditional approach is to define virtual functions in the base class and override them in subclasses:

class Sprite {
public:
    virtual ~Sprite() = default;  // Virtual destructor
    // Define a "pure virtual function," forcing subclasses to implement it
    virtual std::string say_name() const = 0;
};

// "Override" this function in subclasses
class Hero : public Sprite {
public:
    std::string say_name() const override {
        return "I am a hero!";
    }
    // ...
};

class Enemy : public Sprite {
public:
    std::string say_name() const override {
        return "I am an enemy!";
    }
    // ...
};

class Merchant : public Sprite {
public:
    std::string say_name() const override {
        return "I am a merchant.";
    }
    // ...
};

// Now the who_are_you function becomes trivial!
void who_are_you(const Sprite& s) {
    std::cout << s.say_name() << std::endl;
}

Method 2: RTTI + dynamic_cast

If we don't want to define virtual functions for each class, we can use C++'s Runtime Type Information (RTTI):

class Sprite {
public:
    // Only classes with virtual functions can use RTTI
    virtual ~Sprite() = default;
};

// Implementation of who_are_you
void who_are_you(const Sprite& s) {
    if (dynamic_cast<const Hero*>(&s)) {
        std::cout << "I am a hero!" << std::endl;
    } else if (dynamic_cast<const Enemy*>(&s)) {
        std::cout << "I am an enemy!" << std::endl;
    } else if (dynamic_cast<const Merchant*>(&s)) {
        std::cout << "I am a merchant." << std::endl;
    } else {
        std::cout << "I don't know who I am" << std::endl;
    }
}

How RTTI Works

With RTTI enabled, the C++ compiler maintains an implicit type_info structure for each object with virtual functions. When dynamic_cast is used, the compiler checks this type information: if it matches, it returns a valid pointer; otherwise, it returns nullptr. While powerful, this mechanism incurs runtime overhead.

However, the second method has issues in large projects:

Type Unsafety. If you add a new subclass but forget to update the who_are_you function, this bug will only surface at runtime! In modern software development, we prefer such errors to be caught at compile time.
Performance Overhead. With RTTI enabled, every type check involves a cumbersome type information lookup, which hampers optimization and can lead to performance issues.
Opaque Data. With RTTI, C++ implicitly adds type information to each class, but this is invisible to the code author. This is problematic for library developers who desire more control over their code. In fact, many large projects disable RTTI—most notably LLVM, a C++ compiler project that itself avoids using RTTI.

Moonbit's ADT Mechanism

Moonbit elegantly solves polymorphism using Algebraic Data Types (ADTs). We introduce a new structure—SpriteEnum:

pub trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum  // New: type conversion method
}

// Moonbit allows enum tags and type names to overlap
pub enum SpriteEnum {
  Hero(Hero)
  Enemy(Enemy)
  Merchant(Merchant)
}

// We still need to implement getSpriteData for Sprite
pub impl Sprite for Hero with getSpriteData(self) {
  self.sprite_data
}

pub impl Sprite for Enemy with getSpriteData(self) {
  self.sprite_data
}

pub impl Sprite for Merchant with getSpriteData(self) {
  self.sprite_data
}

// Implement asSpriteEnum for the three subclasses
// This essentially "boxes" the concrete type into the enum
pub impl Sprite for Hero with asSpriteEnum(self) {
  Hero(self)  // Note: Hero here is the enum tag, not the type
}

pub impl Sprite for Enemy with asSpriteEnum(self) {
  Enemy(self)
}

pub impl Sprite for Merchant with asSpriteEnum(self) {
  Merchant(self)
}

Now we can implement a type-safe who_are_you function:

test "who are you" {
  fn who_are_you(s: &Sprite) -> String {
    // Use pattern matching for type dispatch
    match s.asSpriteEnum() {
      Hero(_) => "hero"
      Enemy(_) => "enemy"
      Merchant(_) => "merchant"
    }
  }

  let hero = Hero::new();
  let enemy = Enemy::new();
  let merchant = Merchant::new();
  inspect(who_are_you(hero), content="hero")
  inspect(who_are_you(enemy), content="enemy")
  inspect(who_are_you(merchant), content="merchant")
}

The beauty of this approach lies in its compile-time type safety! If you add a new Sprite subclass but forget to update the who_are_you function, the compiler will immediately flag the error instead of waiting until runtime to reveal the issue.

Static Dispatch vs. Dynamic Dispatch

You might notice the &Sprite in the function signature. In Moonbit, this is called a Trait Object, supporting dynamic dispatch similar to C++'s virtual function mechanism. If you write fn[S: Sprite] who_are_you(s: S), it becomes static dispatch (generics), where the compiler generates specialized code for each concrete type.

The key difference lies in handling heterogeneous collections. Suppose a hero has an AOE skill that targets an array of different enemy types. You must use Array[&Sprite] instead of Array[V], as the latter cannot accommodate different concrete types simultaneously.

Moonbit also supports direct method calls akin to C++'s virtual functions:

pub trait SayName {
  say_name(Self) -> String
}

pub impl SayName for Hero with say_name(_) {
  "hero"
}

pub impl SayName for Enemy with say_name(_) {
  "enemy"
}

pub impl SayName for Merchant with say_name(_) {
  "merchant"
}

test "say_name" {
  fn who_are_you(s: &SayName) -> String {
    s.say_name()  // Directly call the trait method, like a virtual function
  }

  let hero = Hero::new();
  let enemy = Enemy::new();
  let merchant = Merchant::new();
  inspect(who_are_you(hero), content="hero")
  inspect(who_are_you(enemy), content="enemy")
  inspect(who_are_you(merchant), content="merchant")
}

Explicit RTTI

Essentially, Moonbit's ADT approach makes C++'s implicit RTTI process explicit. Developers know exactly what types exist, and the compiler can perform completeness checks at compile time.

Multi-Level Inheritance: Building Complex Capability Hierarchies

As the game system evolves, we notice that both Hero and Enemy have hp (hit points), damage (attack power), and an attack method. Can we abstract these common features into a Warrior (fighter) layer?

Multi-Level Inheritance in C++

In C++, we can naturally insert new intermediate layers into the inheritance chain:

class Warrior : public Sprite {
protected: // Using protected so subclasses can access
    double hp;
    double damage;

public:
    Warrior(int id, double x, double y, double hp, double damage)
        : Sprite(id, x, y), hp(hp), damage(damage) {}

    virtual void attack(Sprite& target) = 0; // All warriors can attack

    double getHP() const { return hp; }
    double getDamage() const { return damage; }
};

class Hero final : public Warrior {
    private:
        int money;
    public:
        Hero(int id, double x, double y, double hp, double damage, int money)
            : Warrior(id, x, y, hp, damage), money(money) {}
};

class Enemy final : public Warrior {
    public:
        Enemy(int id, double x, double y, double hp, double damage)
            : Warrior(id, x, y, hp, damage) {}
};

class Merchant final : public Sprite {
    public:
        Merchant(int id, double x, double y) : Sprite(id, x, y) {}
}; // Merchant still directly inherits from Sprite

This forms a clear inheritance chain: Sprite → Warrior → Hero/Enemy, and Sprite → Merchant.

Composition-Based Multi-Level Capabilities in Moonbit

In Moonbit, we stick to composition, building a more flexible capability system:

pub struct WarriorData {
  hp: Double
  damage: Double
}

// Warrior trait inherits from Sprite, forming a capability hierarchy
pub trait Warrior : Sprite {
  getWarriorData(Self) -> WarriorData
  asWarriorEnum(Self) -> WarriorEnum
  attack(Self, target: &Warrior) -> Unit = _  // Default implementation
}

pub enum WarriorEnum {
  Hero(Hero)
  Enemy(Enemy)
}

// Redefine Hero to compose two types of data
pub struct Hero {
  sprite_data: SpriteData    // Base sprite data
  warrior_data: WarriorData  // Warrior data
  money: Int                 // Hero-specific data
}

// Hero needs to implement multiple traits
pub impl Sprite for Hero with getSpriteData(self) {
  self.sprite_data
}

pub impl Warrior for Hero with getWarriorData(self) {
  self.warrior_data
}

pub impl Warrior for Hero with asWarriorEnum(self) {
  Hero(self)
}

// Redefine Enemy
pub struct Enemy {
  sprite_data: SpriteData
  warrior_data: WarriorData
}

pub impl Sprite for Enemy with getSpriteData(self) {
  self.sprite_data
}

pub impl Warrior for Enemy with getWarriorData(self) {
  self.warrior_data
}

pub impl Warrior for Enemy with asWarriorEnum(self) {
  Enemy(self)
}

Sometimes, we might need to convert a parent type to a child type. For example, our merchant might react differently to different Sprites: when encountering a Warrior, they say, "Want to buy something?"; when encountering another merchant, they do nothing. In such cases, we need to convert the Sprite parent type to the Warrior child type. The recommended approach is to add a tryAsWarrior function to the Sprite trait:

pub trait Sprite {
  // other methods
  tryAsWarrior(Self) -> &Warrior? = _  // Attempt to convert to Warrior
}

impl Sprite with tryAsWarrior(self) {
  match self.asSpriteEnum() {
    // The first item needs `as &Warrior` to inform the compiler that the expression returns a &Warrior.
    // Without this `as` statement, the compiler would infer the type as `Hero` based on the first expression,
    // leading to a compilation error.
    Hero(h) => Some(h as &Warrior)
    Enemy(e) => Some(e)
    _ => None
  }
}

pub fn Merchant::ask(self: Merchant, s: &Sprite) -> String {
  match s.tryAsWarrior() {
    Some(_) => "Want to buy something?"  // Speak to warriors
    None => ""                           // Stay silent for other types
  }
}

The brilliance of this design lies in its ultimate flexibility:

Hero and Enemy compose SpriteData and WarriorData while implementing both Sprite and Warrior traits, gaining all required capabilities.
Merchant only needs to compose SpriteData and implement the Sprite trait.
If we later introduce a Mage capability, we simply define MageData and the Mage trait.
A character can even be both a Warrior and a Mage, becoming a "spellblade," without dealing with C++'s diamond inheritance problem.

The Diamond Inheritance Problem

Suppose we want to create a Profiteer class that is both a merchant and an enemy. In C++, if Profiteer inherits from both Enemy and Merchant, diamond inheritance occurs: Profiteer ends up with two copies of Sprite data! This can lead to bizarre bugs where modifying one copy of the data doesn't reflect in the other. Moonbit's composition approach avoids this problem entirely.

Deep Issues with Traditional Object-Oriented Programming

At this point, you might think, "Moonbit's approach requires more code and seems more complex!" Indeed, in terms of lines of code, Moonbit appears to need more "boilerplate." However, in real-world software engineering, traditional OOP has several deep-seated issues:

1. Fragile Inheritance Chains

Problem: Any modification to a parent class affects all subclasses, potentially causing unpredictable ripple effects.

Imagine your RPG game has been out for two years, with hundreds of different Sprite subclasses. Now you need to refactor the base Sprite class. You'll quickly realize this is impractical. In a traditional inheritance system, this change impacts every subclass, and even minor tweaks can have massive consequences. Some subclasses might exhibit unexpected behavior changes, requiring you to manually inspect and test all related code.

Moonbit's Solution: Compositional design lets us use ADTs to immediately identify all Sprite subclasses, clearly understanding the scope of any refactoring.

2. The Nightmare of Diamond Inheritance

Problem: Multiple inheritance can lead to diamond inheritance, causing data duplication and method call ambiguities.

As mentioned earlier, when the Profiteer class inherits from both Enemy and Merchant, it ends up with two copies of Sprite data. This not only wastes memory but can also lead to data inconsistency bugs.

Moonbit's Solution: Composition naturally avoids this issue. Profiteer can have SpriteData, WarriorData, and MerchantData, all clearly defined.

3. Runtime Error Risks

Problem: Many issues in traditional OOP only surface at runtime, increasing debugging difficulty and project risk.

Recall the dynamic_cast example earlier? If you add a new subclass but forget to update the relevant type-checking code, the bug only appears when that code path executes. In large projects, this could mean bugs are discovered only in production.

Moonbit's Solution: ADTs paired with pattern matching provide compile-time type safety. Omitting any case triggers a compiler error.

4. Complexity Explosion

Problem: Deep inheritance trees become difficult to understand and maintain.

After years of development, your game might evolve an inheritance tree like this:

Sprite
├── Warrior
│   ├── Hero
│   │   ├── Paladin
│   │   ├── Berserker
│   │   └── ...
│   └── Enemy
│       ├── Orc
│       ├── Dragon
│       └── ...
├── Mage
│   ├── Wizard
│   └── Sorceror
└── NPC
    ├── Merchant
    ├── QuestGiver
    └── ...

When refactoring, you might spend significant time just understanding this complex inheritance web, and any change could have unintended side effects.

Moonbit's Solution: A flat, compositional structure makes the system easier to understand. Each capability is an independent trait, and composition relationships are immediately clear.

Conclusion

Through this in-depth comparison, we've seen two fundamentally different philosophies of object-oriented programming:

Traditional OOP in C++: Inheritance-based "is-a" relationships, intuitive but prone to complexity traps.
Modern OOP in Moonbit: Composition-based "has-a" relationships, slightly more complex initially but more elegant in the long run.

While Moonbit's approach requires more "boilerplate" code, this extra code buys us:

Better Type Safety: More errors caught at compile time.
Clearer Architecture: Composition relationships are easier to understand than inheritance.
Easier Maintenance: Changes have more controlled impact.
Fewer Runtime Errors: ADTs and pattern matching ensure completeness.

We must acknowledge that traditional inheritance still has value for small projects or specific scenarios. However, as software systems grow in complexity, Moonbit's "composition over inheritance" philosophy demonstrates superior adaptability and maintainability.

We hope this article provides valuable guidance for your Moonbit programming journey, helping you leverage Moonbit's design strengths when building complex systems.

Full Code Example

pub struct SpriteData {
  Int
id: Int
Int
  mut Double
x: Double
Double
  mut Double
y: Double
Double
}

pub fn struct SpriteData {
  id: Int
  mut x: Double
  mut y: Double
}
SpriteData::(id : Int, x : Double, y : Double) -> SpriteData
new(Int
id: Int
Int, Double
x: Double
Double, Double
y: Double
Double) -> struct SpriteData {
  id: Int
  mut x: Double
  mut y: Double
}
SpriteData {
  struct SpriteData {
  id: Int
  mut x: Double
  mut y: Double
}
SpriteData::{ Int
id, Double
x, Double
y }
}

// 2. Define the Trait describing common behaviors
pub trait trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite {
  (Self) -> SpriteData
getSpriteData(type parameter Self
Self) -> struct SpriteData {
  id: Int
  mut x: Double
  mut y: Double
}
SpriteData
  (Self) -> SpriteEnum
asSpriteEnum(type parameter Self
Self) -> enum SpriteEnum {
  Hero(Hero)
  Enemy(Enemy)
  Merchant(Merchant)
}
SpriteEnum
  (Self) -> &Warrior?
tryAsWarrior(type parameter Self
Self) -> &trait Warrior {
  getWarriorData(Self) -> WarriorData
  asWarriorEnum(Self) -> WarriorEnum
  attack(Self, target : &Warrior) -> Unit
}
Warrior? = _
  (Self) -> Int
getID(type parameter Self
Self) -> Int
Int = _
  (Self) -> Double
getX(type parameter Self
Self) -> Double
Double = _
  (Self) -> Double
getY(type parameter Self
Self) -> Double
Double = _
  (Self, Double) -> Unit
setX(type parameter Self
Self, Double
Double) -> Unit
Unit = _
  (Self, Double) -> Unit
setY(type parameter Self
Self, Double
Double) -> Unit
Unit = _
}

// Default implementations for Sprite
impl trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite with (self : Self) -> Int
getID(Self
self) {
  Self
self.(Self) -> SpriteData
getSpriteData().Int
id
}

impl trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite with (self : Self) -> Double
getX(Self
self) {
  Self
self.(Self) -> SpriteData
getSpriteData().Double
x
}

impl trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite with (self : Self) -> Double
getY(Self
self) {
  Self
self.(Self) -> SpriteData
getSpriteData().Double
y
}

impl trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite with (self : Self, new_x : Double) -> Unit
setX(Self
self, Double
new_x) {
  Self
self.(Self) -> SpriteData
getSpriteData().Double
x = Double
new_x
}

impl trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite with (self : Self, new_y : Double) -> Unit
setY(Self
self, Double
new_y) {
  Self
self.(Self) -> SpriteData
getSpriteData().Double
y = Double
new_y
}

impl trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite with (self : Self) -> &Warrior?
tryAsWarrior(Self
self) {
  match Self
self.(Self) -> SpriteEnum
asSpriteEnum() {
    (Hero) -> SpriteEnum
Hero(Hero
h) => (&Warrior) -> &Warrior?
Some(Hero
h as trait Warrior {
  getWarriorData(Self) -> WarriorData
  asWarriorEnum(Self) -> WarriorEnum
  attack(Self, target : &Warrior) -> Unit
}
&Warrior)
    (Enemy) -> SpriteEnum
Enemy(Enemy
e) => (&Warrior) -> &Warrior?
Some(Enemy
e)
    _ => &Warrior?
None
  }
}

pub enum SpriteEnum {
  (Hero) -> SpriteEnum
Hero(struct Hero {
  sprite_data: SpriteData
  hp: Double
  damage: Int
  money: Int
}
Hero)
  (Enemy) -> SpriteEnum
Enemy(struct Enemy {
  sprite_data: SpriteData
  hp: Double
  damage: Int
}
Enemy)
  (Merchant) -> SpriteEnum
Merchant(struct Merchant {
  sprite_data: SpriteData
}
Merchant)
}

pub struct WarriorData {
  Double
hp: Double
Double
  Double
damage: Double
Double
}

pub trait trait Warrior {
  getWarriorData(Self) -> WarriorData
  asWarriorEnum(Self) -> WarriorEnum
  attack(Self, target : &Warrior) -> Unit
}
Warrior : trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite {  // Warrior inherits from Sprite
  (Self) -> WarriorData
getWarriorData(type parameter Self
Self) -> struct WarriorData {
  hp: Double
  damage: Double
}
WarriorData
  (Self) -> WarriorEnum
asWarriorEnum(type parameter Self
Self) -> enum WarriorEnum {
  Hero(Hero)
  Enemy(Enemy)
}
WarriorEnum
  (Self, &Warrior) -> Unit
attack(type parameter Self
Self, target: &trait Warrior {
  getWarriorData(Self) -> WarriorData
  asWarriorEnum(Self) -> WarriorEnum
  attack(Self, target : &Warrior) -> Unit
}
Warrior) -> Unit
Unit = _
}

impl trait Warrior {
  getWarriorData(Self) -> WarriorData
  asWarriorEnum(Self) -> WarriorEnum
  attack(Self, target : &Warrior) -> Unit
}
Warrior with (self : Self, target : &Warrior) -> Unit
attack(Self
self, &Warrior
target) {
  (t : (Self, &Warrior)) -> Unit
Evaluates an expression and discards its result. This is useful when you want
to execute an expression for its side effects but don't care about its return
value, or when you want to explicitly indicate that a value is intentionally
unused.
Parameters:

value : The value to be ignored. Can be of any type.
Example:
  let x = 42
  ignore(x) // Explicitly ignore the value
  let mut sum = 0
  ignore([1, 2, 3].iter().each((x) => { sum = sum + x })) // Ignore the Unit return value of each()
ignore((Self
self, &Warrior
target))
  // ...
}

pub enum WarriorEnum {
  (Hero) -> WarriorEnum
Hero(struct Hero {
  sprite_data: SpriteData
  hp: Double
  damage: Int
  money: Int
}
Hero)
  (Enemy) -> WarriorEnum
Enemy(struct Enemy {
  sprite_data: SpriteData
  hp: Double
  damage: Int
}
Enemy)
}

// Define Hero
pub struct Hero {
  sprite_data: SpriteData
  warrior_data: WarriorData
  money: Int
}

pub fn struct Hero {
  sprite_data: SpriteData
  hp: Double
  damage: Int
  money: Int
}
Hero::() -> Hero
new(
) -> struct Hero {
  sprite_data: SpriteData
  hp: Double
  damage: Int
  money: Int
}
Hero {
  let SpriteData
sprite_data = struct SpriteData {
  id: Int
  mut x: Double
  mut y: Double
}
SpriteData::(id : Int, x : Double, y : Double) -> SpriteData
new(0, 42, 33)
  let WarriorData
warrior_data = struct WarriorData {
  hp: Double
  damage: Double
}
WarriorData::{ Double
hp: 100, Double
damage: 20 }
  struct Hero {
  sprite_data: SpriteData
  hp: Double
  damage: Int
  money: Int
}
Hero::{SpriteData
sprite_data, WarriorData
warrior_data, Int
money: 1000}
}

pub impl trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite for struct Hero {
  sprite_data: SpriteData
  hp: Double
  damage: Int
  money: Int
}
Hero with (self : Hero) -> SpriteData
getSpriteData(Hero
self) {
  Hero
self.SpriteData
sprite_data
}

pub impl trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite for struct Hero {
  sprite_data: SpriteData
  hp: Double
  damage: Int
  money: Int
}
Hero with (self : Hero) -> SpriteEnum
asSpriteEnum(Hero
self) {
  (Hero) -> SpriteEnum
Hero(Hero
self)
}

pub impl trait Warrior {
  getWarriorData(Self) -> WarriorData
  asWarriorEnum(Self) -> WarriorEnum
  attack(Self, target : &Warrior) -> Unit
}
Warrior for struct Hero {
  sprite_data: SpriteData
  hp: Double
  damage: Int
  money: Int
}
Hero with (self : Hero) -> WarriorData
getWarriorData(Hero
self) {
  Hero
self.WarriorData
warrior_data
}

pub impl trait Warrior {
  getWarriorData(Self) -> WarriorData
  asWarriorEnum(Self) -> WarriorEnum
  attack(Self, target : &Warrior) -> Unit
}
Warrior for struct Hero {
  sprite_data: SpriteData
  hp: Double
  damage: Int
  money: Int
}
Hero with (self : Hero) -> WarriorEnum
asWarriorEnum(Hero
self) {
  WarriorEnum::(Hero) -> WarriorEnum
Hero(Hero
self)
}

// Define Enemy
pub struct Enemy {
  sprite_data: SpriteData
  warrior_data: WarriorData
}

pub fn struct Enemy {
  sprite_data: SpriteData
  hp: Double
  damage: Int
}
Enemy::() -> Enemy
new() -> struct Enemy {
  sprite_data: SpriteData
  hp: Double
  damage: Int
}
Enemy {
  let SpriteData
sprite_data = struct SpriteData {
  id: Int
  mut x: Double
  mut y: Double
}
SpriteData::(id : Int, x : Double, y : Double) -> SpriteData
new(0, 42, 33)
  let WarriorData
warrior_data = struct WarriorData {
  hp: Double
  damage: Double
}
WarriorData::{ Double
hp: 100, Double
damage: 5}
  struct Enemy {
  sprite_data: SpriteData
  hp: Double
  damage: Int
}
Enemy::{SpriteData
sprite_data, WarriorData
warrior_data}
}

pub impl trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite for struct Enemy {
  sprite_data: SpriteData
  hp: Double
  damage: Int
}
Enemy with (self : Enemy) -> SpriteData
getSpriteData(Enemy
self) {
  Enemy
self.SpriteData
sprite_data
}

pub impl trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite for struct Enemy {
  sprite_data: SpriteData
  hp: Double
  damage: Int
}
Enemy with (self : Enemy) -> SpriteEnum
asSpriteEnum(Enemy
self) {
  (Enemy) -> SpriteEnum
Enemy(Enemy
self)
}

pub impl trait Warrior {
  getWarriorData(Self) -> WarriorData
  asWarriorEnum(Self) -> WarriorEnum
  attack(Self, target : &Warrior) -> Unit
}
Warrior for struct Enemy {
  sprite_data: SpriteData
  hp: Double
  damage: Int
}
Enemy with (self : Enemy) -> WarriorData
getWarriorData(Enemy
self) {
  Enemy
self.WarriorData
warrior_data
}

pub impl trait Warrior {
  getWarriorData(Self) -> WarriorData
  asWarriorEnum(Self) -> WarriorEnum
  attack(Self, target : &Warrior) -> Unit
}
Warrior for struct Enemy {
  sprite_data: SpriteData
  hp: Double
  damage: Int
}
Enemy with (self : Enemy) -> WarriorEnum
asWarriorEnum(Enemy
self) {
  WarriorEnum::(Enemy) -> WarriorEnum
Enemy(Enemy
self)
}

// Define Merchant
pub struct Merchant {
  sprite_data: SpriteData
}

pub fn struct Merchant {
  sprite_data: SpriteData
}
Merchant::() -> Merchant
new() -> struct Merchant {
  sprite_data: SpriteData
}
Merchant {
  let SpriteData
sprite_data = struct SpriteData {
  id: Int
  mut x: Double
  mut y: Double
}
SpriteData::(id : Int, x : Double, y : Double) -> SpriteData
new(0, 42, 33)
  struct Merchant {
  sprite_data: SpriteData
}
Merchant::{SpriteData
sprite_data}
}

pub impl trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite for struct Merchant {
  sprite_data: SpriteData
}
Merchant with (self : Merchant) -> SpriteData
getSpriteData(Merchant
self) {
  Merchant
self.SpriteData
sprite_data
}

pub impl trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite for struct Merchant {
  sprite_data: SpriteData
}
Merchant with (self : Merchant) -> SpriteEnum
asSpriteEnum(Merchant
self) {
  (Merchant) -> SpriteEnum
Merchant(Merchant
self)
}

pub fn struct Merchant {
  sprite_data: SpriteData
}
Merchant::(self : Merchant, s : &Sprite) -> String
ask(Merchant
self: struct Merchant {
  sprite_data: SpriteData
}
Merchant, &Sprite
s: &trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite) -> String
String {
  (t : Merchant) -> Unit
Evaluates an expression and discards its result. This is useful when you want
to execute an expression for its side effects but don't care about its return
value, or when you want to explicitly indicate that a value is intentionally
unused.
Parameters:

value : The value to be ignored. Can be of any type.
Example:
  let x = 42
  ignore(x) // Explicitly ignore the value
  let mut sum = 0
  ignore([1, 2, 3].iter().each((x) => { sum = sum + x })) // Ignore the Unit return value of each()
ignore(Merchant
self)
  match &Sprite
s.(&Sprite) -> &Warrior?
tryAsWarrior() {
    &Warrior?
Some(_) =>"what to buy something?"
    &Warrior?
None => ""
  }
}

test "who are you" {
  fn (&Sprite) -> String
who_are_you(&Sprite
s: &trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum
  tryAsWarrior(Self) -> &Warrior?
  getID(Self) -> Int
  getX(Self) -> Double
  getY(Self) -> Double
  setX(Self, Double) -> Unit
  setY(Self, Double) -> Unit
}
Sprite) -> String
String {
    match &Sprite
s.(&Sprite) -> SpriteEnum
asSpriteEnum() {
      SpriteEnum
Hero(_) => "hero"
      SpriteEnum
Enemy(_) => "enemy"
      SpriteEnum
Merchant(_) => "merchant"
    }
  }
  let Hero
hero = struct Hero {
  sprite_data: SpriteData
  hp: Double
  damage: Int
  money: Int
}
Hero::() -> Hero
new();
  let Enemy
enemy = struct Enemy {
  sprite_data: SpriteData
  hp: Double
  damage: Int
}
Enemy::() -> Enemy
new();
  let Merchant
merchant = struct Merchant {
  sprite_data: SpriteData
}
Merchant::() -> Merchant
new();
  (obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect((&Sprite) -> String
who_are_you(Hero
hero), String
content="hero")
  (obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect((&Sprite) -> String
who_are_you(Enemy
enemy), String
content="enemy")
  (obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect((&Sprite) -> String
who_are_you(Merchant
merchant), String
content="merchant")
}
pub trait trait SayName {
  say_name(Self) -> String
}
SayName {
  (Self) -> String
say_name(type parameter Self
Self) -> String
String
}

pub impl trait SayName {
  say_name(Self) -> String
}
SayName for struct Hero {
  sprite_data: SpriteData
  hp: Double
  damage: Int
  money: Int
}
Hero with (Hero) -> String
say_name(_) {
  "hero"
}

pub impl trait SayName {
  say_name(Self) -> String
}
SayName for struct Enemy {
  sprite_data: SpriteData
  hp: Double
  damage: Int
}
Enemy with (Enemy) -> String
say_name(_) {
  "enemy"
}

pub impl trait SayName {
  say_name(Self) -> String
}
SayName for struct Merchant {
  sprite_data: SpriteData
}
Merchant with (Merchant) -> String
say_name(_) {
  "merchant"
}

test "say_name" {
  fn (&SayName) -> String
who_are_you(&SayName
s: &trait SayName {
  say_name(Self) -> String
}
SayName) -> String
String {
    &SayName
s.(&SayName) -> String
say_name()
  }

  let Hero
hero = struct Hero {
  sprite_data: SpriteData
  hp: Double
  damage: Int
  money: Int
}
Hero::() -> Hero
new();
  let Enemy
enemy = struct Enemy {
  sprite_data: SpriteData
  hp: Double
  damage: Int
}
Enemy::() -> Enemy
new();
  let Merchant
merchant = struct Merchant {
  sprite_data: SpriteData
}
Merchant::() -> Merchant
new();
  (obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect((&SayName) -> String
who_are_you(Hero
hero), String
content="hero")
  (obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect((&SayName) -> String
who_are_you(Enemy
enemy), String
content="enemy")
  (obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect((&SayName) -> String
who_are_you(Merchant
merchant), String
content="merchant")
}

test "merchant ask" {
  let Hero
hero = struct Hero {
  sprite_data: SpriteData
  hp: Double
  damage: Int
  money: Int
}
Hero::() -> Hero
new();
  let Enemy
enemy = struct Enemy {
  sprite_data: SpriteData
  hp: Double
  damage: Int
}
Enemy::() -> Enemy
new();
  let Merchant
merchant = struct Merchant {
  sprite_data: SpriteData
}
Merchant::() -> Merchant
new();

  (obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(Merchant
merchant.(self : Merchant, s : &Sprite) -> String
ask(Hero
hero), String
content="what to buy something?")
  (obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(Merchant
merchant.(self : Merchant, s : &Sprite) -> String
ask(Enemy
enemy), String
content="what to buy something?")
  (obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect(Merchant
merchant.(self : Merchant, s : &Sprite) -> String
ask(Merchant
merchant), String
content="")
}

MoonBit Pearls Vol.01：Implementing a Pratt Parser in MoonBit

June 11, 2025 · 8 min read

myfreess

Last week, the MoonBit community launched the "MoonBit Pearls" campaign, calling for high-quality documentation and code examples. After meticulous selection, we are proud to officially release the first featured article in the "MoonBit Pearls" column this week.

As a long-term knowledge repository, this column will continuously curate and showcase outstanding documentation. We encourage more developers to contribute in the future, collectively enriching the MoonBit community ecosystem.

Below is the content of the first submission. The author provides a comprehensive case study demonstrating how to implement a Pratt parser in MoonBit:

Implementing a Pratt Parser in MoonBit

During the compilation process, syntax analysis (also known as parsing) is a critical step. The primary responsibility of a parser is to convert a stream of tokens into an Abstract Syntax Tree (AST).

This article introduces an implementation algorithm for parsers: Pratt Parsing, a top-down operator precedence parsing method, and demonstrates how to implement it using MoonBit.

Why Use a Pratt Parser?

Infix expressions are familiar to almost every programmer. Even staunch Lisp/Forth programmers are aware that a majority of the world writes arithmetic expressions like this:

24 * (x + 4)

For compiler (or interpreter) writers, such infix expressions are slightly more challenging to parse compared to the prefix expressions used in Lisp or the postfix expressions used in Forth.

For example, a naive handwritten recursive descent parser would require multiple mutually recursive functions and the elimination of left recursion during syntax analysis, making the code less maintainable as the number of operators grows. Parser generator tools are also not entirely satisfactory for this problem. Consider the BNF for a simple arithmetic expression with addition and multiplication:

Expr ::=
    Factor
    | Expr '+' Factor
Factor ::=
    Atom
    | Factor '*' Atom
Atom ::=
    'number'
    | '(' Expr ')'

This does not look very intuitive and might require revisiting formal language theory from university courses.

Some languages, like Haskell, support custom infix operators, which are almost impossible to handle simply with parser generator tools.

The Pratt parser elegantly solves the problem of parsing infix expressions while also being easily extensible to support new operators (without modifying the source code!). It is recommended alongside recursive descent parsers in the renowned compilation textbook Crafting Interpreters and is used in projects like rust-analyzer.

Binding Power

In Pratt parsers, the concept used to describe associativity and precedence is called binding power. For each infix operator, the binding power is represented as a pair of integers—one for the left and one for the right. For example:

expr:   A     +     B     *     C
power:     3     3     5     5

As the name suggests, a higher number means higher priority in capturing an operand (in this example, A, B, and C are operands).

The above example demonstrates operators with different precedence levels, while the associativity of the same operator is represented by asymmetric binding powers.

expr:   A     +     B     +     C
power:     1     2     1     2

In this case, when parsing reaches B, the expression is grouped as follows due to the higher binding power on the left:

expr:   (A + B)     +     C
power:           1     2

Next, let’s see how the Pratt parser uses this concept during execution.

Overview and Preparation

The main framework of a Pratt parser looks like this:

fn parse(self : Tokens, min_bp : Int) -> SExpr ! ParseError {
    ...
    while true {
       parse(...)
    }
    ...
}

As shown above, it is implemented using a combination of recursion and loops. This corresponds to two modes:

The leftmost expression is always the innermost, e.g., "1 + 2 + 3" = "(1 + 2) + 3", which can be parsed using just a loop.
The rightmost expression is always the innermost, e.g., "1 + 2 + 3" = "1 + (2 + 3)", which can be parsed using recursion alone.

The min_bp parameter represents the binding power of the nearest unfinished operator on the left.

Our goal is to read a token stream and output a prefix expression without worrying about precedence:

enum SExpr {
  (String) -> SExpr
Atom(String
String)
  (Char, Array[SExpr]) -> SExpr
Cons(Char
Char, type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[enum SExpr {
  Atom(String)
  Cons(Char, Array[SExpr])
}
SExpr])
}

impl trait Show {
  output(Self, &Logger) -> Unit
  to_string(Self) -> String
}
Trait for types that can be converted to String
Show for enum SExpr {
  Atom(String)
  Cons(Char, Array[SExpr])
}
SExpr with (self : SExpr, logger : &Logger) -> Unit
output(SExpr
self, &Logger
logger) {
    match SExpr
self {
        (String) -> SExpr
Atom(String
s) => &Logger
logger.(&Logger, String) -> Unit
write_string(String
s)
        (Char, Array[SExpr]) -> SExpr
Cons(Char
op, Array[SExpr]
args) => {
            &Logger
logger.(&Logger, Char) -> Unit
write_char('(')
            &Logger
logger.(&Logger, Char) -> Unit
write_char(Char
op)
            for Int
i = 0; Int
i (self_ : Int, other : Int) -> Bool
< Array[SExpr]
args.(self : Array[SExpr]) -> Int
Returns the number of elements in the array.
Parameters:

array : The array whose length is to be determined.
Returns the number of elements in the array as an integer.
Example:
  let arr = [1, 2, 3]
  inspect(arr.length(), content="3")
  let empty : Array[Int] = []
  inspect(empty.length(), content="0")
length(); Int
i = Int
i (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ 1 {
                &Logger
logger.(&Logger, Char) -> Unit
write_char(' ')
                &Logger
logger.(&Logger, String) -> Unit
write_string(Array[SExpr]
args(Array[SExpr], Int) -> SExpr
Retrieves an element from the array at the specified index.
Parameters:

array : The array to get the element from.
index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Throws a panic if the index is negative or greater than or equal to the
length of the array.
Example:
  let arr = [1, 2, 3]
  inspect(arr[1], content="2")
[i].(self : SExpr) -> String
to_string())
            }
            &Logger
logger.(&Logger, Char) -> Unit
write_char(')')
        }
    }
}

test {
    (obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect((Char, Array[SExpr]) -> SExpr
Cons('+', [(String) -> SExpr
Atom("3"), (String) -> SExpr
Atom("4")]), String
content="(+ 3 4)")
}

Since errors may occur during this process, the return type of parseExpr is SExpr ! ParseError.

Before writing the parser, however, we need to split the input string into a simple token stream.

enum Token {
  Token
LParen
  Token
RParen
  (String) -> Token
Operand(String
String)
  (Char) -> Token
Operator(Char
Char)
  Token
Eof
} derive(trait Show {
  output(Self, &Logger) -> Unit
  to_string(Self) -> String
}
Trait for types that can be converted to String
Show, trait Eq {
  op_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
Eq)

struct Tokens {
  mut Int
position : Int
Int
  Array[Token]
tokens : type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[enum Token {
  LParen
  RParen
  Operand(String)
  Operator(Char)
  Eof
}
Token]
}

This token stream requires two methods: peek() and pop().

The peek() method retrieves the first token in the stream without modifying the state—in other words, it is side-effect-free and merely "peeks" at the upcoming content. For an empty token stream, it returns Eof.

fn (self : Tokens) -> Token
peek(Tokens
self : struct Tokens {
  mut position: Int
  tokens: Array[Token]
}
Tokens) -> enum Token {
  LParen
  RParen
  Operand(String)
  Operator(Char)
  Eof
}
Token {
  if Tokens
self.Int
position (self_ : Int, other : Int) -> Bool
< Tokens
self.Array[Token]
tokens.(self : Array[Token]) -> Int
Returns the number of elements in the array.
Parameters:

array : The array whose length is to be determined.
Returns the number of elements in the array as an integer.
Example:
  let arr = [1, 2, 3]
  inspect(arr.length(), content="3")
  let empty : Array[Int] = []
  inspect(empty.length(), content="0")
length() {
    Tokens
self.Array[Token]
tokens.(self : Array[Token], idx : Int) -> Token
Retrieves the element at the specified index from an array without bounds
checking.
Parameters:

array : The array from which to retrieve the element.
index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Example:
  let arr = [1, 2, 3]
  inspect(arr.unsafe_get(1), content="2")
unsafe_get(Tokens
self.Int
position)
  } else {
    Token
Eof
  }
}

The pop() method consumes a token after peeking.

fn (self : Tokens) -> Token
pop(Tokens
self : struct Tokens {
  mut position: Int
  tokens: Array[Token]
}
Tokens) -> enum Token {
  LParen
  RParen
  Operand(String)
  Operator(Char)
  Eof
}
Token {
  if Tokens
self.Int
position (self_ : Int, other : Int) -> Bool
< Tokens
self.Array[Token]
tokens.(self : Array[Token]) -> Int
Returns the number of elements in the array.
Parameters:

array : The array whose length is to be determined.
Returns the number of elements in the array as an integer.
Example:
  let arr = [1, 2, 3]
  inspect(arr.length(), content="3")
  let empty : Array[Int] = []
  inspect(empty.length(), content="0")
length() {
    let Int
pos = Tokens
self.Int
position
    Tokens
self.Int
position (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+= 1
    Tokens
self.Array[Token]
tokens.(self : Array[Token], idx : Int) -> Token
Retrieves the element at the specified index from an array without bounds
checking.
Parameters:

array : The array from which to retrieve the element.
index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Example:
  let arr = [1, 2, 3]
  inspect(arr.unsafe_get(1), content="2")
unsafe_get(Int
pos)
  } else {
    Token
Eof
  }
}

The tokenize function is responsible for converting a string into a token stream.

fn (this : Char) -> Bool
isDigit(Char
this : Char
Char) -> Bool
Bool {
    Char
this is '0'..='9'
}

fn (this : Char) -> Bool
isAlpha(Char
this : Char
Char) -> Bool
Bool {
    Char
this is 'A'..='Z' (Bool, Bool) -> Bool
|| Char
this is 'a'..='z'
}

fn (this : Char) -> Bool
isWhiteSpace(Char
this : Char
Char) -> Bool
Bool {
    Char
this (self : Char, other : Char) -> Bool
Compares two characters for equality.
Parameters:

self : The first character to compare.
other : The second character to compare.
Returns true if both characters represent the same Unicode code point,
false otherwise.
Example:
  let a = 'A'
  let b = 'A'
  let c = 'B'
  inspect(a == b, content="true")
  inspect(a == c, content="false")
== ' ' (Bool, Bool) -> Bool
|| Char
this (self : Char, other : Char) -> Bool
Compares two characters for equality.
Parameters:

self : The first character to compare.
other : The second character to compare.
Returns true if both characters represent the same Unicode code point,
false otherwise.
Example:
  let a = 'A'
  let b = 'A'
  let c = 'B'
  inspect(a == b, content="true")
  inspect(a == c, content="false")
== '\t' (Bool, Bool) -> Bool
|| Char
this (self : Char, other : Char) -> Bool
Compares two characters for equality.
Parameters:

self : The first character to compare.
other : The second character to compare.
Returns true if both characters represent the same Unicode code point,
false otherwise.
Example:
  let a = 'A'
  let b = 'A'
  let c = 'B'
  inspect(a == b, content="true")
  inspect(a == c, content="false")
== '\n'
}

fn (this : Char) -> Bool
isOperator(Char
this : Char
Char) -> Bool
Bool {
    let String
operators = "+-*/"
    String
operators.(self : String, c : Char) -> Bool
Returns true if this string contains the given character.
contains_char(Char
this)
}

type! LexError Int
Int

fn (source : String) -> Tokens raise LexError
tokenize(String
source : String
String) -> struct Tokens {
  mut position: Int
  tokens: Array[Token]
}
Tokens!type! LexError Int
LexError {
    let Array[Token]
tokens = []
    let Array[Char]
source = String
source.(self : String) -> Array[Char]
Converts the String into an array of Chars.
to_array()
    let StringBuilder
buf = type StringBuilder
StringBuilder::(size_hint~ : Int) -> StringBuilder
Creates a new string builder with an optional initial capacity hint.
Parameters:

size_hint : An optional initial capacity hint for the internal buffer. If
less than 1, a minimum capacity of 1 is used. Defaults to 0. It is the size of bytes,
not the size of characters. size_hint may be ignored on some platforms, JS for example.
Returns a new StringBuilder instance with the specified initial capacity.
new(Int
size_hint = 100)
    let mut Int
i = 0
    while Int
i (self_ : Int, other : Int) -> Bool
< Array[Char]
source.(self : Array[Char]) -> Int
Returns the number of elements in the array.
Parameters:

array : The array whose length is to be determined.
Returns the number of elements in the array as an integer.
Example:
  let arr = [1, 2, 3]
  inspect(arr.length(), content="3")
  let empty : Array[Int] = []
  inspect(empty.length(), content="0")
length() {
        let Char
ch = Array[Char]
source.(self : Array[Char], idx : Int) -> Char
Retrieves the element at the specified index from an array without bounds
checking.
Parameters:

array : The array from which to retrieve the element.
index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Example:
  let arr = [1, 2, 3]
  inspect(arr.unsafe_get(1), content="2")
unsafe_get(Int
i)
        Int
i (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+= 1
        if Char
ch (self : Char, other : Char) -> Bool
Compares two characters for equality.
Parameters:

self : The first character to compare.
other : The second character to compare.
Returns true if both characters represent the same Unicode code point,
false otherwise.
Example:
  let a = 'A'
  let b = 'A'
  let c = 'B'
  inspect(a == b, content="true")
  inspect(a == c, content="false")
== '('{
            Array[Token]
tokens.(self : Array[Token], value : Token) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
  let v = []
  v.push(3)
push(Token
LParen)
        } else if Char
ch (self : Char, other : Char) -> Bool
Compares two characters for equality.
Parameters:

self : The first character to compare.
other : The second character to compare.
Returns true if both characters represent the same Unicode code point,
false otherwise.
Example:
  let a = 'A'
  let b = 'A'
  let c = 'B'
  inspect(a == b, content="true")
  inspect(a == c, content="false")
== ')' {
            Array[Token]
tokens.(self : Array[Token], value : Token) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
  let v = []
  v.push(3)
push(Token
RParen)
        } else if (this : Char) -> Bool
isOperator(Char
ch) {
            Array[Token]
tokens.(self : Array[Token], value : Token) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
  let v = []
  v.push(3)
push((Char) -> Token
Operator(Char
ch))
        } else if (this : Char) -> Bool
isAlpha(Char
ch) {
            StringBuilder
buf.(self : StringBuilder, ch : Char) -> Unit
Writes a character to the StringBuilder.
write_char(Char
ch)
            while Int
i (self_ : Int, other : Int) -> Bool
< Array[Char]
source.(self : Array[Char]) -> Int
Returns the number of elements in the array.
Parameters:

array : The array whose length is to be determined.
Returns the number of elements in the array as an integer.
Example:
  let arr = [1, 2, 3]
  inspect(arr.length(), content="3")
  let empty : Array[Int] = []
  inspect(empty.length(), content="0")
length() (Bool, Bool) -> Bool
&& ((this : Char) -> Bool
isAlpha(Array[Char]
source(Array[Char], Int) -> Char
Retrieves an element from the array at the specified index.
Parameters:

array : The array to get the element from.
index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Throws a panic if the index is negative or greater than or equal to the
length of the array.
Example:
  let arr = [1, 2, 3]
  inspect(arr[1], content="2")
[i]) (Bool, Bool) -> Bool
|| (this : Char) -> Bool
isDigit(Array[Char]
source(Array[Char], Int) -> Char
Retrieves an element from the array at the specified index.
Parameters:

array : The array to get the element from.
index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Throws a panic if the index is negative or greater than or equal to the
length of the array.
Example:
  let arr = [1, 2, 3]
  inspect(arr[1], content="2")
[i]) (Bool, Bool) -> Bool
|| Array[Char]
source(Array[Char], Int) -> Char
Retrieves an element from the array at the specified index.
Parameters:

array : The array to get the element from.
index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Throws a panic if the index is negative or greater than or equal to the
length of the array.
Example:
  let arr = [1, 2, 3]
  inspect(arr[1], content="2")
[i] (self : Char, other : Char) -> Bool
Compares two characters for equality.
Parameters:

self : The first character to compare.
other : The second character to compare.
Returns true if both characters represent the same Unicode code point,
false otherwise.
Example:
  let a = 'A'
  let b = 'A'
  let c = 'B'
  inspect(a == b, content="true")
  inspect(a == c, content="false")
== '_') {
                StringBuilder
buf.(self : StringBuilder, ch : Char) -> Unit
Writes a character to the StringBuilder.
write_char(Array[Char]
source(Array[Char], Int) -> Char
Retrieves an element from the array at the specified index.
Parameters:

array : The array to get the element from.
index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Throws a panic if the index is negative or greater than or equal to the
length of the array.
Example:
  let arr = [1, 2, 3]
  inspect(arr[1], content="2")
[i])
                Int
i (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+= 1
            }
            Array[Token]
tokens.(self : Array[Token], value : Token) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
  let v = []
  v.push(3)
push((String) -> Token
Operand(StringBuilder
buf.(self : StringBuilder) -> String
Returns the current content of the StringBuilder as a string.
to_string()))
            StringBuilder
buf.(self : StringBuilder) -> Unit
Resets the string builder to an empty state.
reset()
        } else if (this : Char) -> Bool
isDigit(Char
ch) {
            StringBuilder
buf.(self : StringBuilder, ch : Char) -> Unit
Writes a character to the StringBuilder.
write_char(Char
ch)
            while Int
i (self_ : Int, other : Int) -> Bool
< Array[Char]
source.(self : Array[Char]) -> Int
Returns the number of elements in the array.
Parameters:

array : The array whose length is to be determined.
Returns the number of elements in the array as an integer.
Example:
  let arr = [1, 2, 3]
  inspect(arr.length(), content="3")
  let empty : Array[Int] = []
  inspect(empty.length(), content="0")
length() (Bool, Bool) -> Bool
&& (this : Char) -> Bool
isDigit(Array[Char]
source(Array[Char], Int) -> Char
Retrieves an element from the array at the specified index.
Parameters:

array : The array to get the element from.
index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Throws a panic if the index is negative or greater than or equal to the
length of the array.
Example:
  let arr = [1, 2, 3]
  inspect(arr[1], content="2")
[i]) {
                StringBuilder
buf.(self : StringBuilder, ch : Char) -> Unit
Writes a character to the StringBuilder.
write_char(Array[Char]
source(Array[Char], Int) -> Char
Retrieves an element from the array at the specified index.
Parameters:

array : The array to get the element from.
index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Throws a panic if the index is negative or greater than or equal to the
length of the array.
Example:
  let arr = [1, 2, 3]
  inspect(arr[1], content="2")
[i])
                Int
i (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
  inspect(42 + 1, content="43")
  inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+= 1
            }
            Array[Token]
tokens.(self : Array[Token], value : Token) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
  let v = []
  v.push(3)
push((String) -> Token
Operand(StringBuilder
buf.(self : StringBuilder) -> String
Returns the current content of the StringBuilder as a string.
to_string()))
            StringBuilder
buf.(self : StringBuilder) -> Unit
Resets the string builder to an empty state.
reset()
        } else if (this : Char) -> Bool
isWhiteSpace(Char
ch) {
            continue
        } else {
            raise (Int) -> LexError
LexError(Int
i)
        }
    } else {
        return struct Tokens {
  mut position: Int
  tokens: Array[Token]
}
Tokens::{ Int
position : 0, Array[Token]
tokens }
    }
}

test {
    (obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect((source : String) -> Tokens raise LexError
tokenize("(((((47)))))").Array[Token]
tokens, String
content=
      #|[LParen, LParen, LParen, LParen, LParen, Operand("47"), RParen, RParen, RParen, RParen, RParen]
    )
    (obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect((source : String) -> Tokens raise LexError
tokenize("13 + 6 + 5 * 3").Array[Token]
tokens, String
content=
      #|[Operand("13"), Operator('+'), Operand("6"), Operator('+'), Operand("5"), Operator('*'), Operand("3")]
    )
}

Finally, we need a function to compute the binding power of operators, which can be implemented simply using match. In practice, a key-value container should be used for easy addition of new operators.

fn (op : Char) -> (Int, Int)?
infix_binding_power(Char
op : Char
Char) -> (Int
Int, Int
Int)? {
  match Char
op {
    '+' => ((Int, Int)) -> (Int, Int)?
Some((1, 2))
    '-' => ((Int, Int)) -> (Int, Int)?
Some((1, 2))
    '/' => ((Int, Int)) -> (Int, Int)?
Some((3, 4))
    '*' => ((Int, Int)) -> (Int, Int)?
Some((3, 4))
    _ => (Int, Int)?
None
  }
}

Parser Implementation

First, retrieve the first token and assign it to the variable lhs (short for left-hand side, representing the left operand).

If it is an operand, store it.
If it is a left parenthesis, recursively parse the first expression and then consume a matching right parenthesis.
Any other result indicates an error, which should be raised.

Next, we peek at the first operator:

If the result is Eof, this is not a failure—a single operand can be a complete expression, so we break the loop.
If the result is an operator, proceed normally.
If the result is a right parenthesis, break the loop.
Any other result raises a ParseError.

We then need to determine which operator the lhs belongs to. This is where the min_bp parameter comes into play, representing the binding power of the nearest unfinished operator on the left. Its initial value is 0 (no operator is competing for the first operand). However, we first check if the operator is a parenthesis—if so, it means we are parsing an expression inside parentheses and should break the loop to end. This is one of the reasons for using the peek method, as we cannot determine whether to consume the operator here.

After calculating the binding power (l_bp, r_bp) of the current operator, we compare l_bp with min_bp:

If l_bp is less than min_bp, immediately break, returning lhs to the higher-level operator waiting for the right operand.
Otherwise, consume the current operator using pop, recursively call parseExpr to obtain the right operand with r_bp as the new min_bp, and assign the result to lhs before continuing the loop.

type! ParseError (Int
Int, enum Token {
  LParen
  RParen
  Operand(String)
  Operator(Char)
  Eof
}
Token) derive (trait Show {
  output(Self, &Logger) -> Unit
  to_string(Self) -> String
}
Trait for types that can be converted to String
Show)

fn (self : Tokens, min_bp~ : Int = ..) -> SExpr raise ParseError
parseExpr(Tokens
self : struct Tokens {
  mut position: Int
  tokens: Array[Token]
}
Tokens, Int
min_bp~ : Int
Int = 0) -> enum SExpr {
  Atom(String)
  Cons(Char, Array[SExpr])
}
SExpr ! type! ParseError (Int, Token)
ParseError {
    let mut SExpr
lhs = match Tokens
self.(self : Tokens) -> Token
pop() {
        Token
LParen => {
            let SExpr
expr = Tokens
self.(self : Tokens, min_bp~ : Int = ..) -> SExpr raise ParseError
parseExpr()
            if Tokens
self.(self : Tokens) -> Token
peek() is Token
RParen {
                (t : Token) -> Unit
Evaluates an expression and discards its result. This is useful when you want
to execute an expression for its side effects but don't care about its return
value, or when you want to explicitly indicate that a value is intentionally
unused.
Parameters:

value : The value to be ignored. Can be of any type.
Example:
  let x = 42
  ignore(x) // Explicitly ignore the value
  let mut sum = 0
  ignore([1, 2, 3].iter().each((x) => { sum = sum + x })) // Ignore the Unit return value of each()
ignore(Tokens
self.(self : Tokens) -> Token
pop())
                SExpr
expr
            } else {
                raise ((Int, Token)) -> ParseError
ParseError((Tokens
self.Int
position, Tokens
self.(self : Tokens) -> Token
peek()))
            }
        }
        (String) -> Token
Operand(String
s) => (String) -> SExpr
Atom(String
s)
        Token
t => raise ((Int, Token)) -> ParseError
ParseError((Tokens
self.Int
position (self : Int, other : Int) -> Int
Performs subtraction between two 32-bit integers, following standard two's
complement arithmetic rules. When the result overflows or underflows, it
wraps around within the 32-bit integer range.
Parameters:

self : The minuend (the number being subtracted from).
other : The subtrahend (the number to subtract).
Returns the difference between self and other.
Example:
  let a = 42
  let b = 10
  inspect(a - b, content="32")
  let max = 2147483647 // Int maximum value
  inspect(max - -1, content="-2147483648") // Overflow case
- 1, Token
t))
    }
    while true {
        let Char
op = match Tokens
self.(self : Tokens) -> Token
peek() {
            Token
Eof | Token
RParen => break
            (Char) -> Token
Operator(Char
op) => Char
op
            Token
t => raise ((Int, Token)) -> ParseError
ParseError((Tokens
self.Int
position, Token
t))
        }
        guard (op : Char) -> (Int, Int)?
infix_binding_power(Char
op) is ((Int, Int)) -> (Int, Int)?
Some((Int
l_bp, Int
r_bp)) else {
            raise ((Int, Token)) -> ParseError
ParseError((Tokens
self.Int
position, (Char) -> Token
Operator(Char
op)))
        }
        if Int
l_bp (self_ : Int, other : Int) -> Bool
< Int
min_bp {
            break
        }
        (t : Token) -> Unit
Evaluates an expression and discards its result. This is useful when you want
to execute an expression for its side effects but don't care about its return
value, or when you want to explicitly indicate that a value is intentionally
unused.
Parameters:

value : The value to be ignored. Can be of any type.
Example:
  let x = 42
  ignore(x) // Explicitly ignore the value
  let mut sum = 0
  ignore([1, 2, 3].iter().each((x) => { sum = sum + x })) // Ignore the Unit return value of each()
ignore(Tokens
self.(self : Tokens) -> Token
pop())
        let SExpr
rhs = Tokens
self.(self : Tokens, min_bp~ : Int) -> SExpr raise ParseError
parseExpr(Int
min_bp = Int
r_bp)
        SExpr
lhs = (Char, Array[SExpr]) -> SExpr
Cons(Char
op, [SExpr
lhs, SExpr
rhs])
        continue
    }
    return SExpr
lhs
}

fn (s : String) -> SExpr raise Error
parse(String
s : String
String) -> enum SExpr {
  Atom(String)
  Cons(Char, Array[SExpr])
}
SExpr ! type Error
Error {
    (source : String) -> Tokens raise LexError
tokenize(String
s).(self : Tokens, min_bp~ : Int = ..) -> SExpr raise ParseError
parseExpr()
}

Now we have an extensible parser for arithmetic expressions. Additional test cases can be added to verify its correctness:

test {
  (obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect((s : String) -> SExpr raise Error
parse("13 + 6 + 5 * 3"), String
content="(+ (+ 13 6) (* 5 3))")
  (obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect((s : String) -> SExpr raise Error
parse("3 * 3 + 5 * 5"), String
content="(+ (* 3 3) (* 5 5))")
  (obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect((s : String) -> SExpr raise Error
parse("(3 + 4) * 3 * (17 * 5)"), String
content="(* (* (+ 3 4) 3) (* 17 5))")
  (obj : &Show, content~ : String, loc~ : SourceLoc = _, args_loc~ : ArgsLoc = _) -> Unit raise InspectError
Tests if the string representation of an object matches the expected content.
Used primarily in test cases to verify the correctness of Show
implementations and program outputs.
Parameters:

object : The object to be inspected. Must implement the Show trait.
content : The expected string representation of the object. Defaults to
an empty string.
location : Source code location information for error reporting.
Automatically provided by the compiler.
arguments_location : Location information for function arguments in
source code. Automatically provided by the compiler.
Throws an InspectError if the actual string representation of the object
does not match the expected content. The error message includes detailed
information about the mismatch, including source location and both expected
and actual values.
Example:
  inspect(42, content="42")
  inspect("hello", content="hello")
  inspect([1, 2, 3], content="[1, 2, 3]")
inspect((s : String) -> SExpr raise Error
parse("(((47)))"), String
content="47")
}

However, the capabilities of Pratt parsers extend beyond this. They can also parse prefix operators (e.g., bitwise NOT !n), array indexing operators arr[i], and even ternary operators c ? e1 : e2. For more detailed parsing techniques, refer to Simple but Powerful Pratt Parsing. The author of this blog implemented an industrial-grade Pratt parser in the renowned program analysis tool rust-analyzer.

Guided Tour: Bookstore Application

Traditional Implementation​

moonchor Implementation​

Knowledge of Choice​

Launch Code​

API and Partial Principles

Roles​

Located Values​

Local Computation​

Communication​

Broadcast​

Backend and Execution​

(Optional Reading) Case Study: Multi-Replica KVStore

Basic Implementation​

Example

Double Replication​

Example

Abstracting Replication Strategy with Higher-Order Functions​

Implementing Role-Polymorphism Through Parametric Polymorphism​

Conclusion

Problem Definition​

Problem Modeling​

1.Naive Enumeration​

Example

Example

2.Early Filtering: Enumerate Only Valid Combinations​

Example

Example

3.Maintain Order to Enable Early Termination​

Example

Example

4.Removing Redundant Combinations with Equal Weights for Optimal Time Complexity​

Example

Example

Conclusion​

Appendix​

Further Optimization Details​

Type Parameters

Arguments

Returns

Type Parameters

Arguments

Returns

Side Notes​

Test​

Introduction​

Encapsulation​

Classic Encapsulation in C++​

Elegant Encapsulation in Moonbit​

Inheritance​

Inheritance Hierarchy in C++​

Composition-Based Thinking in Moonbit​

Polymorphism​

Polymorphism Mechanisms in C++​

Method 1: Virtual Function Mechanism​

Method 2: RTTI + dynamic_cast​

Moonbit's ADT Mechanism​

Multi-Level Inheritance: Building Complex Capability Hierarchies​

Multi-Level Inheritance in C++​

Composition-Based Multi-Level Capabilities in Moonbit​

Deep Issues with Traditional Object-Oriented Programming​

1. Fragile Inheritance Chains​

2. The Nightmare of Diamond Inheritance​

3. Runtime Error Risks​

4. Complexity Explosion​

Conclusion​

Full Code Example​

Implementing a Pratt Parser in MoonBit​

Why Use a Pratt Parser?​

Binding Power​

Overview and Preparation​

Example

Example

Example

Example

Example

Parser Implementation​

Traditional Implementation

moonchor Implementation

Knowledge of Choice

Launch Code

Roles

Located Values

Local Computation

Communication

Broadcast

Backend and Execution

Basic Implementation

Double Replication

Abstracting Replication Strategy with Higher-Order Functions

Implementing Role-Polymorphism Through Parametric Polymorphism

Problem Definition

Problem Modeling

1.Naive Enumeration

2.Early Filtering: Enumerate Only Valid Combinations

3.Maintain Order to Enable Early Termination

4.Removing Redundant Combinations with Equal Weights for Optimal Time Complexity

Conclusion

Appendix

Further Optimization Details

Side Notes

Test

Introduction

Encapsulation

Classic Encapsulation in C++

Elegant Encapsulation in Moonbit

Inheritance

Inheritance Hierarchy in C++

Composition-Based Thinking in Moonbit

Polymorphism

Polymorphism Mechanisms in C++

Method 1: Virtual Function Mechanism

Method 2: RTTI + dynamic_cast

Moonbit's ADT Mechanism

Multi-Level Inheritance: Building Complex Capability Hierarchies

Multi-Level Inheritance in C++

Composition-Based Multi-Level Capabilities in Moonbit

Deep Issues with Traditional Object-Oriented Programming

1. Fragile Inheritance Chains

2. The Nightmare of Diamond Inheritance

3. Runtime Error Risks

4. Complexity Explosion

Conclusion

Full Code Example

Implementing a Pratt Parser in MoonBit

Why Use a Pratt Parser?

Binding Power

Overview and Preparation

Parser Implementation