3 posts tagged with "MoonBit"

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!suberror 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 ! suberror 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.

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​

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