函数式里的依赖注入：Reader Monad

2025年7月23日 · 阅读需 9 分钟

经常搞六边形架构的人也知道，为了保持核心业务逻辑的纯粹和独立，我们会把像数据库、外部 API 调用这些“副作用”放在“端口”和“适配器”里，然后通过 DI 的方式注入到应用层。可以说，经典的面向对象和分层架构，离不开 DI。

然后，当我想在 MoonBit 里做点事情的时候，我发现我不能呼吸了。

我们也想讲究一个入乡随俗，但是在 moonbit 这种函数味儿很浓郁的场地，没有类，没有接口，更没有我们熟悉的那一套 DI 容器。那我怎么做 DI？

我当时就在想，软件工程发展到至今已经约 57 年，真的没有在函数式编程里解决 DI 的方法吗？

有的兄弟，有的。只是它在函数式编程里也属于一种 monad：Reader Monad

什么是 Monad

普通的函数就像一个流水线，你丢进去一袋面粉，然后直接跑到生产线末端，等着方便面出来。但这条流水线需要自动处理中间的所有复杂情况：

没放面粉/“没有下单，期待发货”（null）
面团含水量不够把压面机干卡了（抛出异常）
配料机需要读取今天的生产配方，比如是红烧牛肉味还是香菇炖鸡味（读取外部配置）
流水线末端的打包机需要记录今天打包了多少包（更新计数器）

Monad 就是专门管理这条复杂流水线的“总控制系统”。它把你的数据和处理流程的上下文一起打包，确保整个流程能顺畅、安全地进行下去。

在软件开发中，Monad 这一家子有几个常见的成员：

Option：处理“可能没有”的情况。盒子里要么有东西，要么是空的
Result：处理“可能会失败”的情况。盒子要么是绿的（成功），里面装着结果；要么是红的（失败），里面装着错误信息
State Monad：处理“需要修改状态”的情况。这个盒子在产出结果的同时，还会更新盒子侧面的一个计数器。或者说就是 React 里的 useState
Future(Promise)：处理“未来才有”的情况。这个盒子给你一张“提货单”，承诺未来会把货给你
Reader Monad: 盒子可以随时查阅“环境”，但不能修改它

Reader Monad

Reader Monad 的思想，最早可以追溯到上世纪90年代，在 Haskell 这种纯函数式编程语言的圈子里流行起来。当时大家为了坚守“函数纯度”这个铁律（即函数不能有副作用），就必须找到一种优雅的方式来让多个函数共享同一个配置环境，Reader Monad 就是为了解决这个矛盾而诞生的。

如今，它的应用场景已经非常广泛：

应用配置管理：用来传递数据库连接池、API密钥、功能开关等全局配置
请求上下文注入：在 Web 服务中，把当前登录的用户信息等打包成一个环境，供请求处理链上的所有函数使用
实现六边形架构：在六边形（或端口与适配器）架构中，它被用来在核心业务逻辑（Domain/Application Layer）和外部基础设施（Infrastructure Layer）之间建立一道防火墙

简单来说，Reader Monad 就是一个专门处理只读环境依赖的工具。它要解决的就是这些问题：

参数钻孔 (Parameter Drilling)：我们不想把一个 Properties 层层传递
逻辑与配置解耦：业务代码只关心“做什么”，而不用关心“配置从哪来”。这使得代码非常干净，且极易测试

核心方法

一个 Reader 库通常包含以下几个核心部分。

Reader::pure

就像是把一颗糖直接放进一个标准的午餐盒里。它把一个普通的值，包装成一个最简单的、不依赖任何东西的 Reader 计算。

pure 通常是流水线的打包机，它把你计算出的最终结果（一个普通值）重新放回 Reader “流水线”上，所谓“移除副作用”。

typealias @reader.Reader

// `pure` 创建一个不依赖环境的计算
let ?
pure_reader : Reader[String
String, Int
Int] = (Int) -> ?
Reader::pure(100)

test {
  // 无论环境是什么 (比如 "hello")，结果都是 100
  (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(?
pure_reader.(String) -> Int
run("hello"), 100)
}

Reader::bind

这是流水线的“连接器”。例如把“和面”这一步和“压面”这一步连接起来，并确保它们能连成一条“生产线”。

为什么需要它？ 为了自动化！ 。bind 让这个过程全自动，你只管定义好每个步骤，它负责传递。

fnalias () -> ?
@reader.ask

// 步骤1: 定义一个 Reader，它的工作是从环境（一个Int）中读取值
let ?
step1 : Reader[Int
Int, Int
Int] = () -> ?
ask()

// 步骤2: 定义一个函数，它接收一个数字，然后返回一个新的 Reader 计算
fn (n : Int) -> ?
step2_func(Int
n : Int
Int) -> Reader[Int
Int, Int
Int] {
  (Int) -> ?
Reader::pure(Int
n (self : Int, other : Int) -> Int
Multiplies two 32-bit integers. This is the implementation of the *
operator for Int.
Parameters:

self : The first integer operand.
other : The second integer operand.
Returns the product of the two integers. If the result overflows the range of
Int, it wraps around according to two's complement arithmetic.
Example:
  inspect(42 * 2, content="84")
  inspect(-10 * 3, content="-30")
  let max = 2147483647 // Int.max_value
  inspect(max * 2, content="-2") // Overflow wraps around
* 2)
}

// 使用 bind 将两个步骤连接起来
let ?
computation : Reader[Int
Int, Int
Int] = ?
step1.((Int) -> ?) -> ?
bind((n : Int) -> ?
step2_func)

test {
  // 运行整个计算，环境是 5
  // 流程: step1 从环境得到 5 -> bind 把 5 交给 step2_func -> step2_func 计算 5*2=10 -> pure(10)
  (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(?
computation.(Int) -> Int
run(5), 10)
}

Reader::map

就像是给午餐盒里的三明治换个标签。它只改变盒子里的东西（比如把薄荷塘换成酒心巧克力），但不动午餐盒本身。

很多时候我们只是想对结果做个简单转换，用 map 比用 bind 更直接，意图更清晰。

// `map` 只转换结果，不改变依赖
let ?
reader_int : Reader[Unit
Unit, Int
Int] = (Int) -> ?
Reader::pure(5)

let ?
reader_string : Reader[Unit
Unit, String
String] = ?
reader_int.((Unit) -> String) -> ?
map(Unit
n => "Value is \{Unit
n}")

test {
  (a : String, b : String, 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(?
reader_string.(Unit) -> String
run(()), "Value is 5")
}

ask

ask 就像是流水线上的一个工人，随时可以抬头看一眼挂在墙上的“生产配方”。这是我们真正读取环境的唯一手段。

bind 只负责在幕后传递，但当你想知道“配方”里到底写了什么时，就必须用 ask 把它“问”出来。

// `ask` 直接获取环境
let ?
ask_reader : Reader[String
String, String
String] = () -> ?
ask()

let String
result : String
String = ?
ask_reader.(String) -> String
run("This is the environment")

test {
  (a : String, b : String, 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(String
result, "This is the environment")
}

而我们接下来会经常用到的 asks，只是对 ask().map() 的封装。

DI 对比 Reader Monad

搞个经典例子：开发一个 UserService，它需要一个 Logger 来记录日志，还需要一个 Database 来获取数据。

普通的 DI 我这里用我第二喜欢的 TypeScript 举例：

interface Logger {
  info(message: string): void
}
interface Database {
  getUserById(id: number): { name: string } | undefined
}

// 业务类通过构造函数声明其依赖
class UserService {
  constructor(
    private logger: Logger,
    private db: Database
  ) {}

  getUserName(id: number): string | undefined {
    this.logger.info(`Querying user with id: ${id}`)
    const user = this.db.getUserById(id)
    return user?.name
  }
}

// 创建依赖实例并注入
const myLogger: Logger = { info: (msg) => console.log(`[LOG] ${msg}`) }
const myDb: Database = {
  getUserById: (id) => (id === 1 ? { name: 'MoonbitLang' } : undefined)
}

const userService = new UserService(myLogger, myDb)
const userName = userService.getUserName(1) // "MoonbitLang"

// 一般来说我们会用一些库管理注入，不会手动实例化。例如 InversifyJS 亦或者是……Angular

而 Reader Monad 呢

fnalias ((Unit) -> String) -> ?
@reader.asks

struct User {
  String
name : String
String
}

trait trait Logger {
  info(Self, String) -> Unit
}
Logger {
  (Self, String) -> Unit
info(type parameter Self
Self, String
String) -> Unit
Unit
}

trait trait Database {
  getUserById(Self, Int) -> User?
}
Database {
  (Self, Int) -> User?
getUserById(type parameter Self
Self, Int
Int) -> struct User {
  name: String
}
User?
}

struct AppConfig {
  &Logger
logger : &trait Logger {
  info(Self, String) -> Unit
}
Logger
  &Database
db : &trait Database {
  getUserById(Self, Int) -> User?
}
Database
}

fn (id : Int) -> ?
getUserName(Int
id : Int
Int) -> Reader[struct AppConfig {
  logger: &Logger
  db: &Database
}
AppConfig, String
String?] {
  ((Unit) -> String) -> ?
asks(Unit
config => {
    Unit
config.&Logger
logger.(&Logger, String) -> Unit
info("Querying user with id: \{Int
id}")
    let User?
user = Unit
config.&Database
db.(&Database, Int) -> User?
getUserById(Int
id)
    User?
user.(self : User?, f : (User) -> String) -> String?
Maps the value of an Option using a provided function.
Example
  let a = Some(5)
  assert_eq(a.map(x => x * 2), Some(10))

  let b = None
  assert_eq(b.map(x => x * 2), None)
map(User
obj => User
obj.String
name)
  })
}

struct LocalDB {}

impl trait Database {
  getUserById(Self, Int) -> User?
}
Database for struct LocalDB {
}
LocalDB with (LocalDB, id : Int) -> User?
getUserById(_, Int
id) {
  if Int
id (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")
== 1 {
    (User) -> User?
Some({ String
name: "MoonbitLang" })
  } else {
    User?
None
  }
}

struct LocalLogger {}

impl trait Logger {
  info(Self, String) -> Unit
}
Logger for struct LocalLogger {
}
LocalLogger with (LocalLogger, content : String) -> Unit
info(_, String
content) {
  (input : String) -> Unit
Prints any value that implements the Show trait to the standard output,
followed by a newline.
Parameters:

value : The value to be printed. Must implement the Show trait.
Example:
  println(42)
  println("Hello, World!")
  println([1, 2, 3])
println("\{String
content}")
}

test "Test UserName" {
  let AppConfig
appConfig = struct AppConfig {
  logger: &Logger
  db: &Database
}
AppConfig::{ &Database
db: struct LocalDB {
}
LocalDB::{  }, &Logger
logger: struct LocalLogger {
}
LocalLogger::{  } }
  (a : String, b : String, 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((id : Int) -> ?
getUserName(1).(AppConfig) -> Unit
run(AppConfig
appConfig).() -> String
unwrap(), "MoonbitLang")
}

可以发现，getUserName 函数同样不持有任何依赖，它只是一个“计算描述”。

这个特性让 Reader Monad 成为了实现六边形架构的天作之合。在六边形架构里，核心原则是 “依赖倒置” ——核心业务逻辑不应该依赖具体的基础设施。

getUserName 的例子就是最好的体现。AppConfig 就是一个 Ports 集合

而 getUserName 这个核心业务逻辑，它只依赖 AppConfig 这个抽象，完全不知道背后到底是 MySQL 还是 PostgreSQL，还是一个假实现：一个 Mock DB

但它不能解决什么问题？状态修改。

Reader Monad 的环境永远是“只读”的。一旦注入，它在整个计算过程中都不能被改变。

如果你需要一个可变的状态，找它的兄弟 State Monad 吧。

也就是说，它的好处很明显：它可以在任意地方读取配置；

当然它的坏处也很明显：它只会读取。

简单的 i18n 工具库

经常搞前端的人都知道，我们如果要搞 i18n，大概率会用上 i18next 这类库。它的核心玩法，通常是把一个 i18n 实例通过 React Context 注入到整个应用里，任何组件想用翻译，直接从 Context 里拿就行。所以这其实也可以是一种依赖注入。

回归初心了属于是，本来寻找 DI(Context) 的目的就是为了给 cli 工具支持 i18n。当然这里只是一个简单的演示。

首先，先安装依赖

moon add colmugx/reader

接着，我们来定义 i18n 库需要的环境和字典类型。

typealias String as Locale

typealias String as TranslationKey

typealias String as TranslationValue

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

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

struct I18nConfig {
  // 这里只是方便演示添加了 mut
  mut String
lang : String
Locale
  Map[String, Map[String, String]]
dict : type Map[K, V]
Mutable linked hash map that maintains the order of insertion, not thread safe.
Example
  let map = { 3: "three", 8 :  "eight", 1 :  "one"}
  assert_eq(map.get(2), None)
  assert_eq(map.get(3), Some("three"))
  map.set(3, "updated")
  assert_eq(map.get(3), Some("updated"))
Dict
}

接下来是翻译函数 t

fn (key : String) -> ?
t(String
key : String
TranslationKey) -> Reader[struct I18nConfig {
  mut lang: String
  dict: Map[String, Map[String, String]]
}
I18nConfig, String
TranslationValue] {
  ((Unit) -> String) -> ?
asks(Unit
config => Unit
config.Map[String, Map[String, String]]
dict
    .(self : Map[String, Map[String, String]], key : String) -> Map[String, String]?
Get the value associated with a key.
get(Unit
config.String
lang)
    .(self : Map[String, String]?, f : (Map[String, String]) -> String) -> String?
Maps the value of an Option using a provided function.
Example
  let a = Some(5)
  assert_eq(a.map(x => x * 2), Some(10))

  let b = None
  assert_eq(b.map(x => x * 2), None)
map(Map[String, String]
lang_map => Map[String, String]
lang_map.(self : Map[String, String], key : String) -> String?
Get the value associated with a key.
get(String
key).(self : String?, default : String) -> String
Return the contained Some value or the provided default.
unwrap_or(String
key))
    .(self : String?, default : String) -> String
Return the contained Some value or the provided default.
unwrap_or(String
key))
}

完事了，看起来很简单是不是

接下来，假设我们的 CLI 工具需要根据操作系统的 LANG 环境变量来显示不同语言的欢迎信息。

fn (content : String) -> ?
welcome_message(String
content : String
String) -> Reader[struct I18nConfig {
  mut lang: String
  dict: Map[String, Map[String, String]]
}
I18nConfig, String
String] {
  (key : String) -> ?
t("welcome").((Unit) -> Unit) -> ?
bind(Unit
welcome_text => (String) -> Unit
Reader::pure("\{Unit
welcome_text} \{String
content}"))
}

test {
  let Map[String, Map[String, String]]
dict : type Map[K, V]
Mutable linked hash map that maintains the order of insertion, not thread safe.
Example
  let map = { 3: "three", 8 :  "eight", 1 :  "one"}
  assert_eq(map.get(2), None)
  assert_eq(map.get(3), Some("three"))
  map.set(3, "updated")
  assert_eq(map.get(3), Some("updated"))
Dict = {
    "en_US": { "welcome": "Welcome To" },
    "zh_CN": { "welcome": "欢迎来到" },
  }

  // 假设你的系统语言 LANG 是 zh_CN
  let I18nConfig
app_config = struct I18nConfig {
  mut lang: String
  dict: Map[String, Map[String, String]]
}
I18nConfig::{ String
lang: "zh_CN", Map[String, Map[String, String]]
dict }
  let ?
msg = (content : String) -> ?
welcome_message("MoonbitLang")
  (a : String, b : String, 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(?
msg.(I18nConfig) -> String
run(I18nConfig
app_config), "欢迎来到 MoonbitLang")

  // 切换语言
  I18nConfig
app_config.String
lang = "en_US"
  (a : String, b : String, 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(?
msg.(I18nConfig) -> String
run(I18nConfig
app_config), "Welcome To MoonbitLang")
}

欢迎来到 MoonbitLang

MoonBit pearls vol.4 用 MoonBit 探索协同式编程（下篇）

2025年7月17日 · 阅读需 12 分钟

本文旨在使用 MoonBit 语言的协同式编程库 moonchor，用多个例子阐释协同式编程的核心思想和基本用法。上篇文章中我们提到了如何通过一个书店应用展示moonbit在协同式编程里的实践。

案例研究：多副本 KVStore

在本节中，我们将探讨一个更复杂的案例，使用 moonchor 实现多副本的 KVStore。我们依然只使用 moonchor 的核心 API，但会充分利用 MoonBit 的泛型和一等公民函数这两个特性。我们的目的是探索 MoonBit 的强大表达能力可以为协同式编程的带来多大的可能性。

基本实现

首先做一些准备工作，定义客户端 Client 和服务器 Server 两个角色：

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

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

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

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

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

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

要实现一个 KVStore，例如 Redis，我们需要实现最基本的两个接口：get 和 put（对应 Redis 的 get 和 set）。最简单的实现就是用一个 Map 数据结构来存储键值对：

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

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

对于 KVStore 而言，get 和 put 请求是客户端通过网络发送过来的，在接收到请求前，我们并不知道具体的请求是什么。所以我们需要定义一个请求类型 Request，它包含了请求的类型和参数：

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

为了方便，我们的 KVStore 只支持 String 类型的键和 Int 类型的值。接下来，我们定义一个 Response 类型，用于表示服务器对请求的响应：

typealias Int
Int? as Response

响应是一个可选的整数。当请求是 Put 时，响应是 None；当请求是 Get 时，响应是键对应的值包裹上一个 Some，如果键不存在，则响应为 None。

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

我们的目标是定义两个函数 put 和 get 模拟客户端发起请求的过程。它们要做的事情分别是：

在 Client 处生成请求，包装键值对；
将请求发送给 Server；
Server 使用 handle_request 函数处理请求；
将响应发送回 Client。

可以看到，put 和 get 函数的逻辑是相似的，我们可以把 2、3、4 三个过程抽象成一个函数，叫作 access_server。

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

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

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

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

这样我们的 KVStore 就完成了。我们可以写一个简单的 choreography 来测试它：

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

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

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

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

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

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

这个程序的含义是，分别在 "key1" 和 "key2" 存储两个数字 42 和 41，然后从服务器获取这两个值并检查它们的和是否等于 83。如果有任何一个请求返回 None 或者计算结果不是 83，程序就会 panic。

双副本

现在，考虑为 KVStore 增加容错功能。最简单的容错就是构建一个从副本，它与主副本存有相同的数据，并在处理 Get 请求时检查主从数据的一致性。

我们为从副本构建一个新的角色：

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

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

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

定义一个函数用于检查一致性：这个函数会检查所有副本的响应是否一致，如果不一致，则 panic。

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

其余的大部分内容都不需要修改，只要在 access_server 函数中增加对副本的处理即可。新的 access_server_v2 的逻辑是，Server 接收到请求后，将请求转发给 Backup；然后 Server 和 Backup 分别处理请求；Backup 处理完请求后发回给 Server，Server 对两个结果进行一致性检验。

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

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

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

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

和刚才一样，我们可以写一个简单的 choreography 来测试它：

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

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

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

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

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

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

利用高阶函数抽象复制策略

在双副本实现过程中，出现了一些耦合的代码：Server 处理请求、备份请求、检查结果一致性的代码放在了一起。

利用 MoonBit 的高阶函数特性，我们可以把复制策略从具体处理过程中抽象出来。我们分析一下什么是复制策略。复制策略应该包含一个过程，即服务器拿到请求后如何利用各个副本处理它的方式。关键在于，复制策略本身是和请求无关的，应该被从具体请求处理过程中剥离出来。这样的话，我们就能让复制策略成为可替换的部分，便于日后能轻易地在不同的复制策略之间进行切换，或者实现新的复制策略。

当然，真实世界的复制策略是非常复杂的，往往很难清晰地从处理流程中剥离出来。在这个例子中，我们为了简化问题，专注于 moonchor 的编程能力，直接将复制策略定义为 Server 在接收到请求后决定如何处理请求的函数。我们可以用一个类型别名来定义它：

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

接下来，我们就可以简化 access_server 的实现了。我们将策略作为参数传递进去：

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

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

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

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

这样一来，复制策略被成功从处理请求的逻辑中抽象出来了。下面，我们重新实现一遍双副本的复制策略：

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

注意看 double_replication_strategy 的函数签名，它返回一个 ReplicationStrategy 类型的函数。只要提供两个参数，double_replication_strategy 就能构造出一个新的复制策略。至此，我们成功利用高阶函数抽象出了复制策略，这个特性在协同式编程中叫作高阶 choreography。

同样的，我们可以写一个简单的 choreography 来测试它：

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

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

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

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

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

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

利用参数化多态实现角色多态

如果要进一步实现新的复制策略，例如三副本，我们需要定义两个新的 Backup 类型以做区分：

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

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

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

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

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

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

接下来需要修改 access_server 的核心逻辑。我们立刻发现了问题，为了让 Backup1 和 Backup2 都处理一遍请求并且得到响应，需要将以下几条语句重复：let request = unwrapper.unwrap(request_at_backup); let state = unwrapper.unwrap(state_at_backup); handle_request(state, request)。重复代码是坏味道，应当被抽象出来。此时，moonchor 的「角色作为类型」优势就体现出来了，我们可以利用 MoonBit 的参数化多态，将从副本处理逻辑抽象成一个多态函数 do_backup，它接收一个角色类型参数 B，表示从副本的角色：

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

如此一来，我们就能随心所欲地实现双副本或者三副本的复制策略了。对于三副本策略，只需在 triple_replication_strategy 返回的函数内调用 do_backup 两次即可：

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

由于我们成功完成了复制策略和访问过程的分离，access_server、put、get 函数不需要任何修改。让我们对最终的 KVStore 进行测试：

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

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

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

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

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

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

至此，我们完成了多副本 KVStore 的构建。在这个例子中，我们没有手动使用任何 send 和 recv 来表达分布式节点间的交互，而是通过 moonchor 的协同式编程能力实现了所有通信和同步过程，避免可能的类型错误、死锁和显式同步问题。

结语

在这篇文章中，我们借助 moonchor 体验了协同式编程的魅力，还见识了 MoonBit 强大的表达能力。关于协同式编程的更多细节，可以参考 Haskell 的库 HasChor、Choral 语言、moonchor 的源码。想要自己尝试使用 moonchor，可以通过 moon add Milky2018/moonchor@0.15.0 命令安装。

MoonBit Pearls Vol.04: 用MoonBit探索协同式编程

2025年7月11日 · 阅读需 26 分钟

传统的分布式程序设计是非常痛苦的，其中一个重要的因素是，很多整体的逻辑需要拆散到各个分布式节点中实现，分散的实现使得程序难以调试、难以理解，并且无法享用编程语言提供的类型检查能力。Choreographic Programming，即协同式编程，提供了一种整体的视角，允许开发者编写需要多个参与者协同工作的单一程序，然后将这个整体程序分别投射到各个参与者，最终实现协同工作的效果。

协同式编程通过两种不同的方式实现：其一是作为一种全新的编程语言，例如 Choral，开发者编写 Choral 程序，然后用编译器将这个单体程序编译到各个参与者专属的 Java 程序；其二是作为一个库，例如 HasChor，直接利用 Haskell 的类型系统就能实现协同式编程的静态性质，并且完美兼容 Haskell 的生态。MoonBit 的函数式编程特性和强大的类型系统使得它很适合用于构建协同式编程的库。

本文旨在使用 MoonBit 语言的协同式编程库 moonchor，用多个例子阐释协同式编程的核心思想和基本用法。

导览：书店应用

让我们考察一个书店应用，该应用包含两个角色：买家和卖家，其核心逻辑如下：

买家向卖家发送想要购买的书的标题；
卖家通过查询数据库告诉买家书的价格；
买家决定是否购买书籍；
如果买家决定购买，卖家从数据库中扣除书籍的库存并发送预期送达日期给买家；
否则，交互中止。

传统实现

我们在此不关心实现细节，只关心核心逻辑，使用 send 和 recv 函数来表示发送和接收消息。按照传统的实现方式，我们需要为买家和卖家分别开发两个应用。在表示这些应用之前，我们假设已经存在一些函数和类型：

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

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

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

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

enum Role {
  Role
Buyer
  Role
Seller
}

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

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

买家的应用如下：

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

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

卖家的应用如下：

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

这两个应用至少有以下几个问题：

无法保证类型安全：注意到 send 和 recv 都是泛型函数，只有当发送和接收的类型一致时，才能保证类型安全；否则，可能会在序列化、反序列化过程发生运行时错误。而编译期无法检查这种类型安全性，因为编译器无法知道每个 send 对应哪个 recv，只能寄希望于开发者不会写错。
可能导致死锁：万一买家程序的某个 send 语句漏写了，买家和卖家可能会同时等待对方的消息；或者在网络交互时，某个买家连接暂时断开了，卖家也会一直等待买家的消息。上述两种情况都导致死锁。
需要显式同步：买家为了向卖家传达是否要购买的决定，必须显式地发送一个 Bool 类型的消息。后续的协同过程需要保证买家和卖家在 if price <= get_budget() 和 if decision 这两个位置走进相同的分支，而这一特点也是无法在编译期保证的。

导致这些问题的根本原因是我们将一个整体的协同逻辑按照实现的需求拆成了两个独立的部分。接下来，我们看看使用协同式编程如何解决上述问题。

moonchor 实现

使用协同式编程，我们可以将买家和卖家的逻辑写在同一个函数中，然后让它根据调用该函数时不同的参数表现出不同的行为。我们使用 moonchor 中的 API 来定义买家和卖家的角色。在 moonchor 中，角色被定义为 trait Location。为了提供更好的静态性质，角色不仅是值，同时还是一个独特的类型，该类型需要实现 Location 这个 trait。

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

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

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

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

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

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

可以看见，我们定义的 Buyer 和 Seller 类型不包含任何字段。实现 Location trait 的类型只需要提供一个 name 方法，返回一个字符串作为角色的名称。这个 name 方法非常重要，它标识着角色的身份属性，并在类型检查无法保证类型安全时，提供最终检查手段。不要为不同的角色设置相同的名称，否则会导致意外的运行时错误。我们将在后文了解到类型如何保证一定程度的安全性，以及为什么仅依靠类型是不够的。

接下来，我们定义书店应用的核心逻辑，它被称作一个 choreography：

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

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

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

这个程序稍微有点长，我们先逐行分析一下。

函数的参数 ctx: @moonchor.ChoreoContext 是 moonchor 给应用提供的上下文对象，它包含了协同式编程在应用侧的所有接口。首先，我们使用 ctx.locally 执行一个仅在买家角色处需要执行的操作 get_title()。ctx.locally 的第一个参数是角色，第二个参数是一个闭包，闭包的内容就是需要执行的参数，返回值被包装后作为 ctx.locally 的返回值。在这里，get_title() 的返回值是 String 类型，而 title_at_buyer 的类型是 @moonchor.Located[String, Buyer]，表示这个值位于买家这个角色，无法被其它角色使用。当你试图在卖家角色中使用 title_at_buyer 时，编译器会报错，告诉你 Buyer 和 Seller 不是同一个类型。

接下来，买家需要将书名发送给卖家，我们使用 ctx.comm 来实现这个操作。ctx.comm 的第一个参数是发送者角色，第二个参数是接收者角色，第三个参数是发送的内容。在这里，ctx.comm 的返回值 title_at_seller 的类型是 @moonchor.Located[String, Seller]，表示这个值位于卖家角色。你已经猜到了，ctx.comm 对应的操作正是 send 和 recv。但这里，类型得到了保障：ctx.comm 是一个泛型函数，它保证1）发送和接受的消息是同一个类型；2）发送者和接收者的角色对应为参数类型和返回值类型的类型参数，即 @moonchor.Located[T, Sender] 和 @moonchor.Located[T, Receiver]。

再往下，卖家开始通过查询数据库获取书的价格。在这一步我们用到了 ctx.locally 传递给闭包的参数 unwrapper。这个参数是一个用于为 Located 类型解包的对象，它的类型签名中也包含一个角色类型参数，我们通过 Unwrapper::unwrap 方法的签名即可看懂它是如何工作的：fn[T, L] Unwrapper::unwrap(_ : Unwrapper[L], v : Located[T, L]) -> T。也就是说，ctx.locally(buyer, unwrapper => ...) 中的 unwrapper 的类型是 Unwrapper[Buyer]，而 title_at_seller 的类型是 Located[String, Seller]，因此 unwrapper.unwrap(title_at_seller) 的结果类型是 String。这就是我们可以在闭包中使用 title_at_seller 而不能使用 title_at_buyer 的原因。

Knowledge of Choice

在后续的流程中，如何解决显式同步问题是一个关键点，以至于我们要单独用一个小节来说明。在协同式编程中，这个问题被称作 Knowledge of Choice（选择知识）。在上面的例子中，买家需要知道是否购买书籍，而卖家需要知道买家是否购买书籍。我们使用 ctx.broadcast 来实现这个功能。

ctx.broadcast 的第一个参数是发送者的角色，第二个参数是需要共享给所有其它角色的消息。在这个例子中，买家和卖家都需要知道买家是否购买书籍，因此买家要将这一决定 decision_at_buyer 通过 ctx.broadcast 发送给所有参与者（在这里只有卖家）。有趣的是，这个 broadcast 的返回值是一个普通类型而非 Located 类型，这意味着它可以被所有角色使用，并且直接在顶层使用而不需要在 locally 中用 unwrapper 解包。因此，我们能够利用 MoonBit 本身的 if 条件语句来编写后续流程，从而保证买家和卖家在 if 分支中走入相同的分支。

从名字可以看出，ctx.broadcast 的作用是在整个 choreography 中广播一个值。它不仅可以广播一个 Bool 类型，也可以广播任意其它类型。它的结果不仅可以应用于 if 条件语句，也可以用于 while 循环或者任何其它需要公共知识的地方。

启动代码

这样一个 choreography 怎样运行呢？moonchor 提供了 run_choreo 函数来启动一个 choreography。目前，由于 MoonBit 的多后端特性，提供稳定的、可移植的 TCP 服务器和跨进程通信接口是一项挑战，因此我们将使用协程和通道来探寻 choreography 的真正运行过程。完整的启动代码如下：

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

上述代码启动了两个协程，分别在买家和卖家处执行同一个 choreography。也可以理解为，bookshop 这个函数被投射成（也被称为 EPP，端点投射）了「买家版」和「卖家版」两个完全不同的版本。在上面的例子中，run_choreo 的第一个参数是一个 Backend 类型的对象，它提供了协同式编程所需的底层通信机制。我们使用 make_local_backend 函数创建了一个本地后端（不要和刚刚提到的 MoonBit 多后端混淆），这个后端可以在本地进程中运行，使用 peter-jerry-ye/async/channel 提供的通道 API 作为通信基础。在未来，moonchor 还会提供更多的后端实现，例如 HTTP。

API 和部分原理

我们已经对协同式编程和 moonchor 有了初步的了解。接下来，我们正式引入刚刚用到的 API 以及一些没有用到的 API，并且介绍它们的部分原理。

角色

在 moonchor 中，我们通过实现 Location 这个 trait 来定义角色。该 trait 的声明如下：

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

Location 的 trait object 实现了 Eq：

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

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

如果两个角色的 name 方法返回相同的字符串，那么它们被认为是同一个角色，否则就不是。在判断某个值是否是某个角色时，name 方法是最终裁定者。也就是说，可以存在类型相同但实际上不是同一角色的值。这个特性在处理动态生成的角色时是尤其重要的。比如在书店例子中，买家有可能不止一个，卖家需要同时处理多个买家请求，并且根据服务器接收到的连接来动态生成买家角色。此时，买家的类型定义如下：

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

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

Located Values

因为 choreography 中会同时出现位于不同角色的值，因此我们需要某种手段来区分每个值都是位于哪个角色之处的。在 moonchor 中，这个用 Located[T, L] 这个类型表示位于角色 L 处的类型为 T 的值。

type Located[T, L]

type Unwrapper[L]

构建一个 Located Value 的方式是通过 ChoreoContext::locally 或 ChoreoContext::comm。这两个函数都会返回一个 Located 值。

使用一个 Located Value 的方式是通过 Unwrapper 对象的 unwrap 方法。这些内容在上面的书店应用中已经展示过了，不作赘述。

局部计算

我们在例子中见到的最常见的 API 即为 ChoreoContext::locally，它用于在某个角色处执行一个局部计算动作。其签名如下：

type ChoreoContext

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

该 API 表示会在 location 这个角色处执行 computation 这个闭包，并将计算结果包装成一个 Located Value。computation 闭包的唯一参数是一个解包器对象，类型为 Unwrapper[L]，它在闭包中用于将 Located[T, L] 类型的值解包成 T 类型。这个 API 的作用是将计算的结果绑定到某个角色上，确保该值只能在该角色处使用。如果试图在其它角色处使用这个值，或用这个解包器处理其它角色的值，编译器会报错。

通信

ChoreoContext::comm API 用于将一个值从一个角色发送到另一个角色。其签名如下：

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

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

发送和接收通常意味着需要序列化和反序列化过程。在 moonchor 目前的实现中，为了方便，使用 Json 作为消息的物理载体。未来可能会改用字节流作为更高效和通用的物理载体。

ChoreoContext::comm 有三个类型参数，除了要发送的消息类型，还有发送方和接收方的角色类型 From 和 To。这两个类型刚好对应了该方法的 from 参数、to 参数，以及 value 参数和返回值的类型。这保证了发送方和接收方在该消息序列化、反序列化的类型安全性，并且保证发送和接收行为必然会配对，不会因疏忽导致死锁。

广播

当需要在多个角色之间共享一个值时，我们使用 ChoreoContext::broadcast API 让某个角色将一个值广播给所有其它角色。其签名如下：

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

广播和通信的 API 很相似，除了两点不同：

广播不需要指明接收方的角色，默认是该 choreography 中的所有角色；
广播的返回值并非 Located Value，而是消息本身的类型。

这两个特点揭示了广播的目的：所有角色都能访问到同一个值，从而在 choreography 的顶层对该值进行操作而不是局限在 ChoreoContext::locally 方法内部。例如在书店例子中，买家和卖家需要对「是否购买」这一决定达成共识，以确保后续的流程仍然保持一致。

后端和运行

运行一个 choreography 的 API 如下：

type Backend

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

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

它接收三个参数：一个后端、一个用户编写的 choreography 和一个待运行的角色。后端包含了通信机制的具体实现，待运行的角色则是指定这个 choreography 要在哪个位置执行。比如之前的例子中，买家的程序需要在此处传递一个 Buyer 类型的值，而卖家需要传递 Seller 类型的值。

moonchor 提供了一个基于协程和通道的本地后端：

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

这个函数为参数中的所有角色之间构建通信通道，提供具体的通信实现，即 send 和 recv 方法。尽管本地后端只能用于单体并发程序而非真正的分布式应用程序，但它的实现是可插拔的。只要拥有了基于稳定的网络通信 API 实现的其它后端，moonchor 就能轻松用于构建分布式程序了。

（可选阅读）案例研究：多副本 KVStore

基本实现

首先做一些准备工作，定义客户端 Client 和服务器 Server 两个角色：

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

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

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

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

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

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

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

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

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

为了方便，我们的 KVStore 只支持 String 类型的键和 Int 类型的值。接下来，我们定义一个 Response 类型，用于表示服务器对请求的响应：

typealias Int
Int? as Response

响应是一个可选的整数。当请求是 Put 时，响应是 None；当请求是 Get 时，响应是键对应的值包裹上一个 Some，如果键不存在，则响应为 None。

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

我们的目标是定义两个函数 put 和 get 模拟客户端发起请求的过程。它们要做的事情分别是：

在 Client 处生成请求，包装键值对；
将请求发送给 Server；
Server 使用 handle_request 函数处理请求；
将响应发送回 Client。

可以看到，put 和 get 函数的逻辑是相似的，我们可以把 2、3、4 三个过程抽象成一个函数，叫作 access_server。

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

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

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

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

这样我们的 KVStore 就完成了。我们可以写一个简单的 choreography 来测试它：

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

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

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

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

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

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

双副本

现在，考虑为 KVStore 增加容错功能。最简单的容错就是构建一个从副本，它与主副本存有相同的数据，并在处理 Get 请求时检查主从数据的一致性。

我们为从副本构建一个新的角色：

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

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

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

定义一个函数用于检查一致性：这个函数会检查所有副本的响应是否一致，如果不一致，则 panic。

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

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

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

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

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

和刚才一样，我们可以写一个简单的 choreography 来测试它：

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

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

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

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

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

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

利用高阶函数抽象复制策略

在双副本实现过程中，出现了一些耦合的代码：Server 处理请求、备份请求、检查结果一致性的代码放在了一起。

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

接下来，我们就可以简化 access_server 的实现了。我们将策略作为参数传递进去：

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

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

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

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

这样一来，复制策略被成功从处理请求的逻辑中抽象出来了。下面，我们重新实现一遍双副本的复制策略：

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

同样的，我们可以写一个简单的 choreography 来测试它：

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

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

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

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

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

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

利用参数化多态实现角色多态

如果要进一步实现新的复制策略，例如三副本，我们需要定义两个新的 Backup 类型以做区分：

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

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

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

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

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

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

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

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

由于我们成功完成了复制策略和访问过程的分离，access_server、put、get 函数不需要任何修改。让我们对最终的 KVStore 进行测试：

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

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

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

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

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

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

结语

MoonBit Pearls Vol.03：01背包问题

2025年7月3日 · 阅读需 13 分钟

01背包问题是算法竞赛中经典的dp题目。文中总共包含五个版本的代码。从最朴素的枚举法开始，在不断的改进下，最终变成了dp解法。

问题定义

有若干个物品，每件物品的有重量weight和价值value：

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

现在，给定一个物品列表items，和背包的容量capacity。从中选出若干件物品，使得这些物品的总重量不超过背包的容量，且物品的总价值最大。

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 },
])

以上面的items_1为例，假设背包容量是 $10$ ，那么最优的方案是选取后两个物品，占用 $4+5=9$ 的容量，总共有 $10+11=21$ 点价值。

注意，由于我们不能把物品切割，因此优先挑选性价比最高的物品并非正解。例如，在上面的例子中，若选取了性价比最高的物品1，则只有 $20$ 点价值，而此时背包已经放不下其他物品了。

问题建模

我们先定义一些基础的对象与操作。

//物品的组合，下文简称组合
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
}

//空的组合
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,
}

//往组合中添加物品，得到新的组合
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,
  }
}

//两个组合等效，意思是它们总价值一样
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
}

//比较两个组合的大小，就是比较它们总价值的大小
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)
}

然后，我们就可以开始思考如何解决问题了。

一、朴素的枚举

枚举法是最朴素的方案，我们依照问题的定义，一步一步执行，就能得到答案：

枚举出所有的组合；
过滤出其中有效的组合，也就是那些能装入背包的；
答案是其中总价值最大的那个。

得益于标准库提供的两个函数，我们可以将上面三行文字一比一地翻译为MoonBit代码。其中all_combinations是我们后续需要实现的函数，它的类型是(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()
}

注意这里使用的是unsafe_maximum而不是maximum。这是因为空列表列表中没有最大值，maximum在这种情况下会返回一个None。但我们知道，题目保证答案存在（只要capacity不是负数），所以我们可以改用unsafe_maximum。它在输入空列表的情况下直接中断程序，其它情况返回列表中的最大值。

接下来我们去实现枚举的过程。函数all_combinations接受一个物品的列表，返回一个组合的列表，其中包含所有能由这些物品构造出的组合。也许你现在没有头绪，这时我们可以先查看一下列表的定义。它大概长这样：

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

也就是说，列表分为两种：

第一种是空的列表，叫Empty；
第二种是非空的列表，叫More，其中包含了第一个元素（A）和剩余的部分（tail~ : T[A]），剩余部分也是一个列表。

这启示我们按物品列表是否为空来分情况讨论：

如果物品列表为空，那么唯一的一种组合方式就是空的组合；
否则，一定存在第一个物品item1和剩余部分items_tail。这种情况下，我们可以：
1. 先求出不含item1的那些组合。这其实就是items_tail能凑出的那些组合，可以递归地求出。
2. 再求出包含item1的那些组合。它们与不含item1的组合一一对应，只差把item1加入其中。
3. 将这两者合并起来，就是所有items能凑出的组合。

例如，当物品列表包含a,b,c三个元素时，答案分为以下两个部分：

不含a的部分	包含a的部分
{ }	{ 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
    }
  }
}

通过使用模式匹配（match），我们再一次将上面的五行文字一比一地翻译成了MoonBit代码。

二、提前过滤，仅枚举有效的组合

在第一个版本中，枚举所有组合和过滤出能放入背包的组合是不相干的两个过程。在枚举的过程中，出现了很多无效的组合。这些组合早已放不进背包中，却还在后续的过程中被添加物品。不如早一点过滤它们，避免在它之上不断产生新的无效组合。观察代码，发现无效的组合只会在.map(_.add(item1))这一步产生。于是我们可以做出改进：仅向能再装下item1的组合添加item1。

我们将all_combinations改为all_combinations_valid，仅返回能装入这个背包的组合。现在枚举和过滤将交替进行。

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 // 添加一个参数，因为过滤需要知道背包的容量
) -> 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) => {
      // 我们假设 all_combinations_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,
      )
      // 由于添加了过滤，所以它里面的组合都是有效的
      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))
      // 两个部分都仅包含有效组合，所以合并后也仅包含有效组合
      @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
    }
  }
}

遵循代码的结构进行分类讨论，很容易证明all_combinations_valid的正确性——它返回的所有组合确实都是有效的。

由于all_combinations_valid返回的那些组合都是有效的，就不再需要在solve中过滤了。我们将solve中的filter删去。

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()
}

三、维护升序性质，提前结束过滤

在上个版本中，为了过滤出那些能装下item1的组合，我们必须遍历valid_combs_without_item1中的每一个组合。

但我们可以发现：如果item1没法放入一个组合，那么item1一定都无法放入比这个组合总重量更大的那些组合。

这也就是说，如果valid_combs_without_item1能按总重量升序排列，那么过滤时就不需要完整地遍历它了。在过滤的过程中，一旦碰到一个放不下item1的组合，就可以立刻舍去后续的所有组合。由于这种逻辑很常见，标准库提供了一个叫take_while的函数，我们用它替换掉filter。

要想让valid_combs_without_item1升序排列，可以用排序算法，但这却要遍历整个列表，违背了初衷。因此，我们得采用另一种方案：想办法让all_combinations_valid返回的列表是升序的。这需要一次递归的信仰之跃：

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) // 单元素的列表，自然是升序的
    (Item, @list.T[Item]) -> @list.T[Item]
More(Item
item1, @list.T[Item]
tail=@list.T[Item]
items_tail) => {
      // 我们假设 all_combinations_valid_ordered 返回的列表是升序的（归纳假设）
      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,
      )
      // 那么它也是升序的，因为一个升序的列表先截取一部分，再往每个元素加上同样的重量，它们的总重量还是升序的
      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))
      // 现在我们只需要确保合并后也升序，就能衔接上最开始的假设
      (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)
    }
  }
}

最后的任务是完成函数merge_keep_order，它将两个升序的列表合并为一个升序的列表：

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)) =>
      // 如果 a1 比 b1 更轻，而 b 又是升序的，说明
      //   a1 比 b 里所有组合都轻
      // 由于 a 是升序的，所以
      //   a1 比 a_tail 里所有组合都轻
      // 所以 a1 是 a 和 b 中最小的那一个
      if Combination
a1.Int
total_weight (self_ : Int, other : Int) -> Bool
< Combination
b1.Int
total_weight {
        // 我们先递归地合并出答案的剩余部分，再把 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)
      }
  }
}

虽然看起来有点啰嗦，但我还是想提一句：通过遵循代码结构的分类讨论，很容易证明all_combinations_valid_ordered和merge_keep_order的正确性——它确实返回的一个升序的列表。

对于一个升序的列表，它的最大值就是最后一个。于是我们将unsafe_maximum替换成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()
}

回过头来看，在这一版的改进中，我们似乎并没有得到什么太大的好处，毕竟在合并列表的过程中，我们仍然需要遍历整个列表。最初我也是这么想的，但后来意外地发现merge_keep_order的真正作用在下一个版本。

四、去除等同重量的冗余组合，达到最优时间复杂度

目前为止，我们进行的都不是时间复杂度层面的优化，但这些优化恰恰为接下来的步骤铺平了道路。现在让我们来考察一下时间复杂度。

在最差情况下（背包很大，全都放得下），组合列表（all_combinations的返回值）将最多包含 $2^{物品数量}$ 个元素。这导致整个算法的时间复杂度也是指数级的，因为all_combinations会被调用 $物品数量$ 次，而每次都会遍历组合列表。

为了降低时间复杂度，我们就需要降低组合列表的长度。这基于一个观察：如果有两个组合，它们总重量相同，那么总价值更高的那个组合总是比另一个更好。因此，我们不需要在列表中同时保留两者。

如果能排除那些冗余的组合，组合列表的长度将不会超过背包容量（抽屉原理），进而将整个算法的时间复杂度降低到 $\mathcal{O}(物品数量 \times 背包容量)$ 。观察代码，现在唯一有可能会向列表中引入冗余组合的地方是merge_keep_order的else分支。为了避免这种情况出现，我们只需要对这个地方进行一点改动：

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 { // 此时 a1 和 b1 一样重，出现冗余，保留总价值更高的那个
        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)
      }
  }
}

all_combinations_valid_ordered_nodup（这是我这辈子写过的名字最长的函数了）和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()
}

至此，我们重新发明了01背包问题的dp解法。

总结

这篇文章的内容是我某天早上躺在床上的突发奇想，从第一版到第四版代码完全在手机上写成，没有经过任何调试，但却能轻松地保证了正确性。相比传统算法竞赛题解中常见的写法，本文中使用的函数式写法带来了以下优势：

告别循环，使用递归分情况讨论。要想从列表中获取元素，必须使用模式匹配（match），这提醒我考虑列表为空时的答案。它相比dp数组的初始值拥有更加明确的含义。
依赖库函数进行遍历。标准库中提供的高阶函数（filter、take_while、map、maximum）能替换掉样板化的循环（for、while），便于读者一眼看出遍历的目的。
声明式编程。第一版的代码是想法的一比一地翻译。与其说是在描述一个算法，更像是在描述这个问题本身，这保证了第一版的正确性。而随后每次改进都在不影响结果的前提下进行，于是继承了第一版的正确性。

当然，从来就没有银弹。我们需要可读性和效率之间做取舍。函数式的风格固然好理解，但还是有许多优化余地的。进一步的优化方向是将列表替换成数组，再替换成从头到尾只使用两个滚动数组，甚至是只使用一个数组。这可以将空间复杂度优化成 $\mathcal{O}(背包容量)$ ，但不在本文的讨论范围内。我相信初学者更希望看到的是一个易于理解的代码。

附录

题外话

在第一版中，all_combinations(items)产生的Combination甚至比其中的More还多一个，堪称链表节点复用大师。
升序还可以换成降序，对应的take_while要换成drop_while。而改用Array后可以通过binary_search来寻找下标直接切分。
如果你感兴趣，可以考虑一下怎么把上面的做法拓展到各种其它的背包问题。
all_combinations_loop原名：generate_all_ordered_combination_that_fit_in_backpack_list_without_duplicates_using_loop。

测试

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：MoonBit中的面向对象编程

2025年6月23日 · 阅读需 22 分钟

刘子悦

alt text

引言

在软件开发的世界里，面向对象编程（OOP）无疑是一座绕不开的话题。Java、C++ 等语言凭借其强大的 OOP 机制构建了无数复杂的系统。然而，Moonbit，作为一门围绕函数式编程构建的现代语言，它如何实现 OOP？

Moonbit 是一门以函数式编程为核心的语言，它的面向对象编程思路与传统编程语言有很大不同。它抛弃了传统的继承机制，拥抱"组合优于继承"的设计哲学。乍一看，这可能让习惯了传统OOP的程序员有些不适应，但细细品味，你会发现这种方法有着意想不到的优雅和实用性。

本文将通过一个生动的RPG游戏开发例子，带你深入体验Moonbit中的面向对象编程。我们会逐一剖析封装、继承和多态这三大特性，并与C++的实现方式进行对比，最后提供一些实际开发中的最佳实践建议。

封装（Encapsulation）

想象一下，我们要开发一款经典的单机RPG游戏。在这个奇幻世界里，英雄四处游历，与怪物战斗，向NPC商人购买装备，最终拯救被困的公主。要构建这样一个世界，我们首先需要对其中的所有元素进行建模。

不管是勇敢的英雄、凶恶的怪物，还是朴实的桌椅板凳，它们在游戏世界中都有一些共同的特征。我们可以将这些对象都抽象为Sprite（精灵），每个Sprite都应该具备几个基本属性：

ID：对象的唯一标识符，就像身份证号码一样。
x和y：在游戏地图上的坐标位置。

C++的经典封装方式

在C++的世界里，我们习惯于用class来构建数据的封装：

// 一个基础的 Sprite 类
class Sprite {
private:
    int id;
    double x;
    double y;

public:
    // 构造函数，用来创建对象
    Sprite(int id, double x, double y) : id(id), x(x), y(y) {}

    // 提供一些公共的 "getter" 方法来访问数据
    int getID() const { return id; }
    double getX() const { return x; }
    double getY() const { return y; }

    // 可能还需要 "setter" 方法来修改数据
    void setX(double newX) { x = newX; }
    void setY(double newY) { y = newY; }
};

你可能会问："为什么要搞这么多get方法，直接把属性设为public不就好了？"这就涉及到封装的核心思想了。

为什么需要封装？

想象一下，如果你的同事直接通过sprite.id = enemy_id来修改ID，英雄瞬间就能"变身"成敌人的同伙，直接大摇大摆地走到终点——但这显然不是我们想要的游戏机制！封装就像给数据加了一道防护网，private字段配合getter方法，确保外部只能读取而无法随意修改关键数据。这样的设计让代码更加健壮，避免了意想不到的副作用。

Moonbit的优雅封装

到了Moonbit这里，封装的思路发生了微妙而重要的变化。让我们先看一个简单的版本：

// 在 Moonbit 中定义 Sprite
pub struct Sprite {
  id: Int          // 默认不可变，外部可读但不可写
  mut x: Double    // mut 关键字表示可变
  mut y: Double
}

// 我们可以为 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
}

注意到这里有两个关键的不同点：

1. 可变性的显式声明

在Moonbit中，字段默认是不可变的（immutable）。如果你想让某个字段可以被修改，必须明确使用mut关键字。在我们的Sprite中，id保持不可变——这完美符合我们的设计意图，毕竟我们不希望对象的身份被随意篡改。而x和y被标记为mut，因为精灵需要在世界中自由移动。

2. 更简洁的访问控制

由于id本身就是不可变的，我们甚至不需要为它编写get_id方法！外部代码可以直接通过sprite.id来读取它，但任何尝试修改的行为都会被编译器坚决拒绝。这比C++的"private + getter"模式更加简洁明了，同时保持了同样的安全性。

💡 实践建议

在设计数据结构时，优先考虑哪些字段真正需要可变。Moonbit的默认不可变设计能帮你避免很多意外的状态修改bug。

继承（Inheritance）

面向对象编程的第二大支柱是继承。在我们的RPG世界中，会有多种不同类型的Sprite。为了简化示例，我们定义三种：

Hero（英雄）：玩家操控的角色
Enemy（敌人）：需要被击败的对手
Merchant（商人）：售卖道具的NPC

C++的继承层次

在C++中，我们很自然地使用类继承来构建这种层级关系：

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) {}
    // 商人专有的方法...
};

C++的面向对象建立在 "is-a" 关系基础上：Hero是一个Sprite，Enemy是一个Sprite。这种思维方式直观且容易理解。

Moonbit的组合式思维

现在轮到Moonbit了。这里需要进行一次重要的思维转换：Moonbit的struct不支持直接继承。取而代之的是使用trait（特质）和组合（Composition）。

这种设计迫使我们重新思考问题：我们不再将Sprite视为可被继承的"父类"，而是将其拆分为两个独立的概念：

SpriteData：一个纯粹的数据结构，存储所有Sprite共享的数据
Sprite：一个trait，定义所有Sprite应该具备的行为能力

让我们看看实际的代码：

// 1. 定义共享的数据结构
pub struct SpriteData {
  id: Int
  mut x: Double
  mut y: Double
}

// 2. 定义描述通用行为的 Trait
pub trait Sprite {
  getSpriteData(Self) -> SpriteData  // 必须实现的核心方法
  getID(Self) -> Int = _             // = _ 表示有默认实现
  getX(Self) -> Double = _
  getY(Self) -> Double = _
  setX(Self, Double) -> Unit = _
  setY(Self, Double) -> Unit = _
}

// Sprite的默认实现
// 只要实现了 getSpriteData，就自动拥有了其他方法
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
}

理解Trait的威力

Sprite trait定义了一个"契约"：任何声称自己是Sprite的类型，都必须能够提供它的SpriteData。一旦满足了这个条件，getID、getX、getY等方法就会自动可用。这里的= _语法表示该方法有默认实现，这是Moonbit的最新语法特性。

有了这个基础架构，我们就可以实现具体的游戏角色了：

// 定义Hero
pub struct Hero {
  SpriteData
sprite_data: struct SpriteData {
  id: Int
  mut x: Double
  mut y: Double
}
SpriteData  // 组合SpriteData
  Double
hp: Double
Double
  Int
damage: Int
Int
  Int
money: Int
Int
}

// 实现Sprite trait，只需要提供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 {
  // 攻击逻辑...
}

// 定义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 {
  // 攻击逻辑...
}

// 定义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
}

注意这里的思维方式转变：Moonbit采用的是 "has-a" 关系，而不是传统OOP的 "is-a" 关系。Hero拥有SpriteData，并且实现了Sprite的能力。

看起来Moonbit更复杂？

初看之下，Moonbit的代码似乎比C++要写更多"模板代码"。但这只是表面现象！我们这里刻意回避了C++的诸多复杂性：构造函数、析构函数、const正确性、模板实例化等等。更重要的是，Moonbit这种设计在大型项目中会展现出巨大优势——我们稍后会详细讨论这一点。

多态（Polymorphism）

多态是面向对象编程的第三大支柱，指的是同一个接口作用于不同对象时产生不同行为的能力。让我们通过一个具体例子来理解：假设我们需要实现一个who_are_you函数，它能够识别传入对象的类型并给出相应回答。

C++的多态机制

C++的多态机制实际上是一个比较复杂的问题，笼统地说，它包括静态多态（模板）和动态多态（虚函数、RTTI等）。对C++多态机制的讨论超出了我们这篇文章的内容范围，读者如果有兴趣可以自行查阅相关书籍。这里我们重点讨论两种经典的运行时多态方法。

方法一：虚函数机制

最传统的做法是为基类定义虚函数，让子类重写：

class Sprite {
public:
    virtual ~Sprite() = default;  // 虚析构函数
    // 定义一个"纯虚函数"，强制子类必须实现它
    virtual std::string say_name() const = 0;
};

// 在子类中"重写"(override)这个函数
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.";
    }
    // ...
};

// 现在 who_are_you 函数变得极其简单！
void who_are_you(const Sprite& s) {
    std::cout << s.say_name() << std::endl;
}

方法二：RTTI + dynamic_cast

如果我们不想为每个类单独定义虚函数，还可以使用C++的运行时类型信息（RTTI）：

class Sprite {
public:
    // 拥有虚函数的类才能使用 RTTI
    virtual ~Sprite() = default;
};

// 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;
    }
}

RTTI的工作原理

开启RTTI后，C++编译器会为每个有虚函数的对象维护一个隐式的type_info结构。当使用dynamic_cast时，编译器检查这个类型信息：匹配则返回有效指针，不匹配则返回nullptr。这种机制虽然功能强大，但也带来了运行时开销。

不过，第二种方法在大型项目中存在一些问题：

类型不安全。如果你新增了一个子类但忘记修改who_are_you函数，这个bug只能在运行时才能被发现！在现代软件开发中，我们更希望此类错误能在编译时就被捕获。
性能不够好。开启RTTI后，每一次判断类型都会调用一个比较麻烦的类型信息读取方法，这不太利于优化，因此很容易出现性能上的问题。
数据不透明。开启RTTI后，C++会为每一个类隐式地添加一块类型信息，但是代码的编写者是看不到的，这对于一些期望对代码拥有更强掌控力的库编写者而言非常头疼。事实上，不少大型项目会考虑禁用RTTI，最典型的就是LLVM，这个C++的编译器项目反而自己并不愿意使用RTTI.

Moonbit的ADT机制

Moonbit通过引入代数数据类型（Algebraic Data Type，ADT）来优雅地解决多态问题。我们需要添加一个新的结构——SpriteEnum：

pub trait Sprite {
  getSpriteData(Self) -> SpriteData
  asSpriteEnum(Self) -> SpriteEnum  // 新增：类型转换方法
}

// Moonbit允许enum的标签名和类名重名
pub enum SpriteEnum {
  Hero(Hero)
  Enemy(Enemy)
  Merchant(Merchant)
}

// 我们仍然需要实现Sprite中的getSpriteData
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
}

// 为三个子类实现 asSpriteEnum 方法
// 这里实际上是将具体类型"装箱"到enum中
pub impl Sprite for Hero with asSpriteEnum(self) {
  Hero(self)  // 注意：这里的Hero是enum标签，不是类型
}

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

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

现在我们可以实现类型安全的who_are_you函数了：

test "who are you" {
  fn who_are_you(s: &Sprite) -> String {
    // 使用模式匹配进行类型分发
    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")
}

这种方法的美妙之处在于：它是编译时类型安全的！如果你添加了一个新的Sprite子类但忘记修改who_are_you函数，编译器会立即报错，而不是等到运行时才发现问题。

静态分发 vs 动态分发

你可能注意到函数签名中的&Sprite。这在Moonbit中被称为Trait Object，支持动态分发，类似于C++的虚函数机制。如果你写成fn[S: Sprite] who_are_you(s: S)，那就是静态分发（泛型），编译器会为每种具体类型生成专门的代码。

两者的关键区别在于处理异构集合的能力。假设英雄有AOE技能需要攻击一个包含不同类型敌人的数组，你必须使用Array[&Sprite]而不是Array[V]，因为后者无法同时容纳不同的具体类型。

当然，Moonbit也支持类似C++虚函数的直接方法调用：

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()  // 直接调用trait方法，类似虚函数
  }

  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")
}

显式化的RTTI

实际上，Moonbit的ADT方法就是将C++隐式的RTTI过程显式化了。开发者明确知道有哪些类型，编译器也能在编译时进行完整性检查。

多层继承：构建复杂的能力体系

随着游戏系统的发展，我们发现Hero和Enemy都有hp（生命值）、damage（攻击力）和attack方法。能否将这些共同特征抽象出来，形成一个Warrior（战士）层级呢？

C++的多层继承

在C++中，我们可以很自然地在继承链中插入新的中间层：

class Warrior : public Sprite {
protected: // 使用 protected，子类可以访问
    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; // 战士都能攻击

    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) {}
}; // 商人仍然直接继承 Sprite

这形成了一个清晰的继承链：Sprite → Warrior → Hero/Enemy，Sprite → Merchant。

Moonbit的组合式多层能力

在Moonbit中，我们继续坚持组合的思路，构建一个更灵活的能力体系：

pub struct WarriorData {
  hp: Double
  damage: Double
}

// Warrior trait 继承自 Sprite，形成能力层次
pub trait Warrior : Sprite {
  getWarriorData(Self) -> WarriorData
  asWarriorEnum(Self) -> WarriorEnum
  attack(Self, target: &Warrior) -> Unit = _  // 默认实现
}

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

// 重新定义Hero，现在它组合了两种数据
pub struct Hero {
  sprite_data: SpriteData    // 基础精灵数据
  warrior_data: WarriorData  // 战士数据
  money: Int                 // 英雄特有数据
}

// Hero 需要实现多个 trait
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)
}

// 重新定义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)
}

有时我们也可能会遇到需要将父基类转换成子基类的场景。例如，我们的商人可能对不同的Sprite做出不同的反应：当他遇到一个Warrior时，他会说"Want to buy something?"，当他遇到另一个商人时，则什么也不做。这个时候，我们就需要把Sprite父基类转换成Warrior子基类。推荐的方式是为Sprite trait添加一个tryAsWarrior的函数：

pub trait Sprite {
  // other methods
  tryAsWarrior(Self) -> &Warrior? = _  // 尝试转换为Warrior
}

impl Sprite with tryAsWarrior(self) {
  match self.asSpriteEnum() {
    // 第一项需要添加 as &Warrior, 来告知编译器整个表达式返回一个&Warrior
    // 如果不加这个as语句，编译器就会根据第一个表达式的类型
    // 判断整个表达式的类型为Hero，从而引发编译错误。
    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?"  // 对战士说话
    None => ""                           // 对其他类型保持沉默
  }
}

这种设计的精妙之处在于它的极致灵活性：

Hero和Enemy通过组合SpriteData和WarriorData，同时实现Sprite和Warrior两个trait，获得了所需的全部能力
Merchant只需要组合SpriteData并实现Sprite trait即可
如果将来要引入Mage（法师）能力，只需定义MageData和Mage trait
一个角色甚至可以同时是Warrior和Mage，成为"魔剑士"，而不需要处理C++中的菱形继承问题

菱形继承问题

假设我们要创建一个既是商人又是敌人的Profiteer（奸商）类。在C++中，如果Profiteer同时继承Enemy和Merchant，就会出现菱形继承：Profiteer会拥有两份Sprite数据！这可能导致修改了一份数据，但调用时却使用了另一份的诡异bug。Moonbit的组合方式从根本上避免了这个问题。

传统面向对象编程的深层问题

看到这里，你可能会想："Moonbit的方法需要写更多代码，看起来更复杂啊！"确实，从代码行数来看，Moonbit似乎需要更多的"模板代码"。但是，在真实的软件工程实践中，传统的面向对象编程方式实际上存在诸多深层问题：

1. 脆弱的继承链

问题：对父类的任何修改都会影响所有子类，可能产生难以预估的连锁反应。

想象一下你的RPG游戏已经发布了两年，拥有上百种不同的Sprite子类。现在你需要给基础的Sprite类做一个重构。然而，你可能很快就会发现这并不现实。在传统继承体系中，这个改动会影响到每一个子类，即便是很小的改动可能也影响巨大。某些子类可能因为这个改动出现意外的行为变化，而你需要逐一检查和测试所有相关代码。

Moonbit的解决方案：组合式设计让我们可以通过ADT直接找到Sprite的所有子类，立刻知道重构代码的影响范围。

2. 菱形继承的噩梦

问题：多重继承容易导致菱形继承，产生数据重复和方法调用歧义。

如前所述，Profiteer类同时继承Enemy和Merchant时，会拥有两份Sprite数据。这不仅浪费内存，更可能导致数据不一致的bug。

Moonbit的解决方案：组合天然避免了这个问题，Profiteer可以拥有SpriteData、WarriorData和MerchantData，清晰明了。

3. 运行时错误的隐患

问题：传统OOP的许多问题只能在运行时被发现，增加了调试难度和项目风险。

还记得前面dynamic_cast的例子吗？如果你添加了新的子类但忘记更新相关的类型判断代码，只有在程序运行到那个分支时才会暴露问题。在大型项目中，这可能意味着bug在生产环境中才被发现。

Moonbit的解决方案：ADT配合模式匹配提供编译时类型安全。遗漏任何一个case，编译器都会报错。

4. 复杂度爆炸

问题：深层继承树变得难以理解和维护。

经过几年的开发，你的游戏可能演化出这样的继承树：

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

当需要重构时，你可能需要花费大量时间来理解这个复杂的继承关系，而且任何改动都可能产生意想不到的副作用。

Moonbit的解决方案：扁平化的组合结构让系统更容易理解。每个能力都是独立的trait，组合关系一目了然。

结语

通过这次深入的比较，我们看到了两种截然不同的面向对象编程哲学：

C++的传统OOP：基于继承的"is-a"关系，直观但可能陷入复杂度陷阱
Moonbit的现代OOP：基于组合的"has-a"关系，初学稍复杂但长期更优雅

Moonbit的方法虽然需要编写更多的"模板代码"，但这些额外的代码换来的是：

更好的类型安全：编译时捕获更多错误
更清晰的架构：组合关系比继承关系更容易理解
更容易的维护：修改影响范围更可控
更少的运行时错误：ADT和模式匹配提供完整性保证

尽管我们必须承认，对于小型项目或特定场景，传统继承依然有其价值。但现实情况是，随着软件系统复杂度的增长，Moonbit这种组合优于继承的设计哲学确实展现出了更强的适应性和可维护性。

希望这篇文章能为你的Moonbit编程之旅提供有价值的指导，让你在构建复杂系统时能够充分利用Moonbit的设计优势。

完整版代码

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. 定义描述通用行为的 Trait
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 = _
}

// Sprite的默认实现
// 只要实现了 getSpriteData，就自动拥有了其他方法
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 继承自 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)
}

// 定义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)
}

// 定义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)
}

// 定义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：使用MoonBit编写Pratt解析器

2025年6月11日 · 阅读需 9 分钟

myfreess

上周 MoonBit 社区发起 MoonBit Pearls 高质量文档与示例征集活动，经过精细筛选，本周正式推出"MoonBit Pearls"专栏的首篇入选文章。专栏作为长期知识沉淀平台，持续收录优质文档。我们期待更多开发者参与后续投稿，共同丰富 MoonBit 社区生态。

以下是首篇投稿正文内容，作者通过完整案例，演示了如何用 MoonBit 编写 Pratt 解析器：

在编译过程中，语法分析（也称为解析，Parsing）是一个关键步骤。解析器的主要职责是将Token流转换成抽象语法树（AST）。

本文将介绍一种解析器的实现算法：Pratt解析(Pratt Parsing)，是自顶向下的算符优先分析法(Top Down Operator Precedence Parsing)，并展示如何用MoonBit来实现它。

为什么用Pratt解析器

几乎每个程序员都不会对中缀表达式感到陌生, 即使是坚定的Lisp/Forth程序员，至少也知道世界上有大半人这样写算术表达式：

24 * (x + 4)

而对于编译器(或者解释器)的编写者而言，这样的中缀表达式要比Lisp所用的前缀表达式和Forth使用的后缀表达式难解析一点。例如，使用朴素的手写递归下降解析器来解析就需要多个互相递归的函数，还得在分析表达式语法时消除左递归，这样的代码在运算符增多时变得很不友好。解析器生成工具在这一问题上也不是很令人满意的选项，以一个简单加法和乘法运算表达式的BNF为例：

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

这看起来并不是很直观，搞不好还得花时间复习一下大学里上过的形式语言课程。

而有些语言如Haskell支持自定义的中缀运算符，这几乎不太可能简单地用某种解析器生成工具解决。

Pratt解析器很好地解决了中缀表达式解析的问题，与此同时，它还很方便扩展支持添加新的运算符(不需要改源码就可以做到！)。它被著名的编译原理书籍《Crafting Interpreters》推荐和递归下降解析器一同使用，rust-analyzer项目中也使用了它。

结合力

Pratt 解析器中用于描述结合性和优先级的概念叫做binding power(结合力)，对于每个中缀运算符而言，其结合力是一对整数 - 左右各一个。如下所示：

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

而其作用和名字非常符合，数字越大，越能优先获取某个操作数(operand, 这个例子中A B C都是操作数)。

上面的例子展示了具有不同优先级的运算符，而同一运算符的结合性通过一大一小的结合力来表示。

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

在这个例子中，当解析到B时，由于左边的结合力较大，表达式会变成这样：

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

接下来让我们看看Pratt解析器在具体执行时如何使用这一概念。

概览与前期准备

Pratt解析器的主体框架大概是这样：

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

从上文可以看出，它是交替使用递归和循环实现的。这其实对应着两种模式：

永远是最左边的表达式在最内层，即"1 + 2 + 3" = "(1 + 2) + 3", 只需要使用循环就能解析
永远最右边的表达式在最内层，即"1 + 2 + 3" = "1 + (2 + 3)", 这只使用递归也可以解析

min_bp是一个代表左侧某个还没有解析完毕的运算符结合力的参数。

我们的目标是读入一个token流，并输出一个不需要考虑优先级的前缀表达式：

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)")
}

由于这个过程中可能有各种各样的错误，所以parseExpr的返回类型是Sexpr ! ParseError。

不过在开始编写解析器之前，我们还需要对字符串进行分割，得到一个简单的Token流。

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]
}

这个token流需要实现两个方法：peek() pop()

peek()方法能获取token流中的第一个token，对状态无改变，换言之它是无副作用的，只是偷看一眼将要处理的内容。对于空token流，它返回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
  }
}

pop()在peek()的基础上消耗一个token。

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
  }
}

tokenize函数负责将一个字符串解析成token流。

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")]
    )
}

最后我们还需要一个计算运算符结合力的函数，这可以用简单的match实现。在实际操作中为了便于添加新运算符，应该使用某种键值对容器。

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
  }
}

解析器实现

首先取出第一个token并赋值给变量lhs(left hand side的缩写，表示左侧参数)。

如果它是操作数，就存储下来
如果是左括号，则递归解析出第一个表达式，然后消耗掉一个成对的括号。
其他结果都说明解析出了问题，抛出错误

接着我们试着看一眼第一个运算符：

假如此时结果是Eof，那并不能算失败，一个操作数也可以当成是完整的表达式，直接跳出循环
结果是运算符, 正常返回
结果是右括号，跳出循环
其他结果则返回ParseError

接下来我们需要决定lhs归属于哪个操作符了，这里就要用到min_bp这个参数，它代表左边最近的一个尚未完成解析的操作符的结合力，其初始值为0(没有任何操作符在左边争抢第一个操作数)。不过，此处我们要先做个判断，就是运算符是不是括号 - 假如是括号，说明当前是在解析一个括号里的表达式，也应该跳出循环直接结束。这也是使用peek方法的原因之一，因为我们无法确定到底要不要在这里就消耗掉这个运算符。

在计算好当前运算符op的结合力之后，首先将左侧结合力l_bp和min_bp进行比较：

l_bp小于min_bp，马上break，这样就会将lhs返回给上层还等着右侧参数的运算符
否则用pop方法消耗掉当前操作符，并且递归调用parseExpr获取右侧参数，只是第二个参数使用当前操作符的右结合力r_bp。解析成功之后将结果赋值给lhs，继续循环

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()
}

现在我们获得了一个可扩展的四则运算表达式解析器，可以在下面测试块中添加更多的例子来验证其正确性。

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")
}

不过，pratt parser的能力不止于此，它还可以解析前缀运算符(例如按位取反!n)、数组索引运算符arr[i]乃至于三目运算符c ? e1 : e2。关于这方面更详细的解析请见Simple but Powerful Pratt Parsing, 这篇博客的作者在著名的程序分析工具rust-analyzer中实现了一个工业级的pratt parser。

什么是 Monad​

Reader Monad​

核心方法​

Reader::pure​

Reader::bind​

Reader::map​

ask​

DI 对比 Reader Monad​

Example

简单的 i18n 工具库​

Example

Example

Example

Example

Example

Example

案例研究：多副本 KVStore​

基本实现​

Example

双副本​

Example

利用高阶函数抽象复制策略​

利用参数化多态实现角色多态​

结语

导览：书店应用​

传统实现​

moonchor 实现​

Knowledge of Choice​

启动代码​

API 和部分原理​

角色​

Located Values​

局部计算​

通信​

广播​

后端和运行​

（可选阅读）案例研究：多副本 KVStore​

基本实现​

Example

双副本​

Example

利用高阶函数抽象复制策略​

利用参数化多态实现角色多态​

结语​

问题定义​

问题建模​

一、朴素的枚举​

Example

Example

二、提前过滤，仅枚举有效的组合​

Example

Example

三、维护升序性质，提前结束过滤​

Example

Example

四、去除等同重量的冗余组合，达到最优时间复杂度​

Example

Example

总结​

附录​

更多细节优化​

Type Parameters

Arguments

Returns

Type Parameters

Arguments

Returns

题外话​

测试​

引言​

封装（Encapsulation）​

C++的经典封装方式​

Moonbit的优雅封装​

继承（Inheritance）​

C++的继承层次​

Moonbit的组合式思维​

多态（Polymorphism）​

C++的多态机制​

方法一：虚函数机制​

方法二：RTTI + dynamic_cast​

什么是 Monad

Reader Monad

核心方法

Reader::pure

Reader::bind

Reader::map

ask

DI 对比 Reader Monad

简单的 i18n 工具库

案例研究：多副本 KVStore

基本实现

双副本

利用高阶函数抽象复制策略

利用参数化多态实现角色多态

导览：书店应用

传统实现

moonchor 实现

Knowledge of Choice

启动代码

API 和部分原理

角色

Located Values

局部计算

通信

广播

后端和运行

（可选阅读）案例研究：多副本 KVStore

基本实现

双副本

利用高阶函数抽象复制策略

利用参数化多态实现角色多态

结语

问题定义

问题建模

一、朴素的枚举

二、提前过滤，仅枚举有效的组合

三、维护升序性质，提前结束过滤

四、去除等同重量的冗余组合，达到最优时间复杂度

总结

附录

更多细节优化

题外话

测试

引言

封装（Encapsulation）

C++的经典封装方式

Moonbit的优雅封装

继承（Inheritance）

C++的继承层次

Moonbit的组合式思维

多态（Polymorphism）

C++的多态机制

方法一：虚函数机制

方法二：RTTI + dynamic_cast

Moonbit的ADT机制

多层继承：构建复杂的能力体系

C++的多层继承

Moonbit的组合式多层能力

传统面向对象编程的深层问题

1. 脆弱的继承链

2. 菱形继承的噩梦

3. 运行时错误的隐患

4. 复杂度爆炸

结语

完整版代码

为什么用Pratt解析器

结合力

概览与前期准备

解析器实现