列表与递归 Hongbo Zhang 1 基本数据类型：函数 2 函数 在数学上，描述对应关系的⼀种特殊集合 对于特定的输⼊，总是有特定的输出 在计算机中，对相同运算的抽象，避免⼤量重复定义 计算半径为1的圆的⾯积： 3.1415 * 1 * 1 计算半径为2的圆的⾯积： 3.1415 * 2 * 2 计算半径为3的圆的⾯积： 3.1415 * 3 * 3 …… fn ⾯积(半径: radius } 2. let result = (area(1.0), area(2.0), area(3.0)) 4 顶层函数的定义 fn <函数名> (<参数名>: <类型>, <参数名>: <类型>, ...) -> <类型> <表达式块> 定义的函数接⼝让其他使⽤者⽆需关注内部实现 1. fn one () -> Int { 2. 1 3. } 4. 5. fn add_char(ch: } 5 函数的应⽤与计算 当函数定义后，可以通过 <函数名>(<表达式>, <表达式>……) 的⽅式应⽤函数 one() add_char('m', "oonbit") 应⽤函数时，表达式与函数定义时的参数数量应当相同，且类型⼀⼀对应 这是错误的： add_char("oonbit", 'm') 计算应⽤函数的表达式时 从左到右计算定义了参数的表达式的值 替换函数内部参数 简化表达式

输⼊：字符串/字节块 输出：单词流 例如： "12 +678" -> [ Value(12), Plus, Value(678) ] 通常可以通过有限状态⾃动机完成 ⼀般⽤领域特定语⾔定义后，由软件⾃动⽣成程序 算术表达式的词法定义 1. Number = %x30 / (%x31-39) *(%x30-39) 2. LParen = "(" 3. RParen = ")" 4. "+" 5. Minus = "-" 6. Multiply = "*" 7. Divide = "/" 8. Whitespace = " " 3 词法分析 算术表达式的词法定义 1. Number = %x30 / (%x31-39) *(%x30-39) 2. Plus = "+" 每⼀⾏对应⼀个匹配规则 "xxx" ：匹配内容为xxx的字符串 a b ：匹配规则a，成功后匹配规则b ：重复匹配规则a，可匹配0或多次 %x30 ：UTF编码⼗六进制表示为30的字符（ "0" ） 4 词法分析 算术表达式的词法定义 1. Number = %x30 / (%x31-39) *(%x30-39) 2. Plus = "+" "+" "0" "1"-"9" "0"-"9" 单词定义 1. enum Token { 2. Value(Int); LParen; RParen; Plus;

现代编程思想 接⼝ Hongbo Zhang 1 回顾 第六课：定义平衡⼆叉树 我们定义⼀个更⼀般的⼆叉搜索树，允许存放任意类型的数据 1. enum Tree[T] { 2. Empty 3. Node(T, Tree[T], Tree[T]) 4. } 5. 6. // 我们需要⼀个⽐较函数来⽐较值的⼤⼩以了解顺序 7. // 负数表示⼩于，0表示等于，正数表示⼤于 8 -> Int) -> Tree[T] 9. fn delete[T](self: Tree[T], value: T, compare: (T, T) -> Int) -> Tree[T] 第⼋课：定义循环队列 我们需要类型的默认值来初始化数组 1. fn make[T](default: T) -> Queue[T] { 2. { array: Array::make(5, default) fn T::default() -> T 类型的输出： fn T::to_string(self: T) -> String …… 我们将这类函数称为⽅法 3 接⼝ Trait 我们通过接⼝定义⼀系列⽅法的实现需求 1. trait Compare { 2. compare(Self, Self) -> Int // Self代表实现该接⼝的类型 3. } 4. trait Default

tu等环境），并参考⽉ 兔构建系统教程 7 ⽉兔中的表达式 8 ⼀个典型的⽉兔程序 1. //顶层函数定义 2. fn num_water_bottles(num_bottles: Int, num_exchange: Int) -> Int { 3. // 本地函数定义 4. fn consume(num_bottles, num_drunk) { 5. // 条件表达式 基于表达式编程 为了写出正确的程序，我们需要知道程序是如何被运算的：我们需要建⽴计算模型 来理解程序的运算过程 ⽉兔程序可以通过⾯向值编程来描述 ⾯向值编程：定义是什么 我们写的⽉兔代码都是表达⼀个值的表达式 命令式编程⻛格：定义做什么 程序由修改程序状态的命令组成 创建名为x的变量 令x为5 令y指向x …… 10 类型、值与表达式 类型 值 运算 表达式 Int -1 值） 可以使⽤括号来嵌套表达式 11 静态 vs 动态 �静态�指在程序运⾏之前的事物 �动态�指在程序运⾏之时的事物 ⽉兔拥有静态类型系统：在程序运⾏之前，编译器即会检查程序的类型是否定义良好 12 静态类型 每⼀个标识符都关联着唯⼀⼀个类型 �冒号�⽤于关联⼀个标识符和它的类型 x: Int a: Double s: String 每⼀个⽉兔表达式都有⼀个唯⼀的类型，这个类型由组成它的⼦表达式决定

现代编程思想 多元组，结构体与枚举类型 Hongbo Zhang 1 基础数据类型：多元组与结构体 2 回顾：多元组 多元组：固定⻓度的不同类型数据的集合 定义： (<表达式>, <表达式>, ...) 类型： (<表达式类型>, <表达式类型>, ...) 例如： 身份信息： ("Bob", 2023, 10, 24): (String, Int, Int, Int) 成员访问： String; postal: Int } 通过名称，我们能明确数据的信息以及对应字段的含义 5 结构体的定义 结构体的定义形如 struct <结构体名称> { <字段名>: <类型> ; ... } struct PersonalInfo { name: String; age: Int} 定义结构体的值时，形如 { <字段名>: <值> , ... } let info: PersonalInfo PersonalInfo = { name: "Moonbit", age: 1, } 结构体的值的定义不在意顺序： { age: 1, name: "Moonbit", } 如遇到字段名相同的定义⽆法区分时，可在后⾯加上类型声明以作区分 struct A { val: Int } struct B { val: Int } let x = ( { val : 1, } : A ) 6 结构体的访问与更新

也有的定义将树的⾼度等同于最⼤层次，以根为第⼀层 6 树的存储结构 树的存储⽅式有多种（以⼆叉树为例，省略节点存储的数据） 节点与⼦节点关系的列表： [ (0, 1), (0, 2), (1, 3) ] 代数数据结构定义 1. Node(0, 2. Node(1, 3. Leaf(3), 4. Empty), 5. Leaf(2)) 列表定义 数据的逻辑结构独⽴于存储结构 数据 R-Tree：存储空间⼏何结构 …… 8 数据结构：⼆叉树 ⼆叉树要么是⼀棵空树，要么是⼀个节点；它最多具有两个⼦树：左⼦树与右⼦树 叶节点的两个⼦树都是空树 基于递归枚举类型的定义（本节课默认存储数据为整数） 1. enum IntTree { 2. Node(Int, IntTree, IntTree) // 存储的数据，左⼦树，右⼦树 3. Empty 4. } 就像⽣活中排队⼀样，先进⼊队伍的⼈最先获得服务 对于数据的插⼊和删除遵循先进先出（First In First Out, FIFO）的原则 队尾插⼊数据，队头删除数据 15 数据结构：队列 我们在此使⽤的队列由以下接⼝定义： 1. fn empty[T]() -> Queue[T] // 创建空队列 2. fn enqueue[T](q: Queue[T], x: T) -> Queue[T] // 向队尾添加元素

堆栈 我们定义以下操作，以存储整数的堆栈 IntStack 为例 1. empty: () -> IntStack // 创建新的堆栈 2. push : (Int, IntStack) -> IntStack // 将新的元素加⼊栈顶 3. pop: IntStack -> (Option[Int], IntStack) // 从堆栈取出元素 5 整数堆栈 我们实现整数堆栈的定义 self (None, Empty) 10. NonEmpty(top, rest) => (Some(top), rest) 11. } 12. } 我们希望存储很多很多类型在堆栈中 每个类型都要定义⼀个对应的堆栈吗？ IntStack 和 StringStack 似乎结构⼀模⼀样？ 7 泛型数据结构与泛型函数 泛型数据结构与泛型函数以类型为参数，构建更抽象的结构 1. enum Stack[T] } 12. } 将 T 替换为 Int 或 String 即相当于 IntStack 与 StringStack 8 泛型数据结构与泛型函数 我们⽤ [<类型1>, <类型2>, ...] 来定义泛型的类型参数 enum Stack[T]{ Empty; NonEmpty(T, Stack[T]) } struct Pair[A, B]{ first: A; second: B } fn

对于标识符，我们可以直接⽤它所对应的值进⾏替代⸺引⽤透明性 开发实⽤的程序，我们需要⼀些计算之外的�副作⽤� 进⾏输⼊输出 修改内存中的数据等 这些副作⽤可能导致多次执⾏的结果不⼀致 2 引⽤透明性 我们可以定义如下数据绑定和函数 1. let x: Int = 1 + 1 2. fn square(x: Int) -> Int { x * x } 3. let z: Int = square(x) // 2 * 2 } // 4 引⽤透明性可以易于理解 3 命令 函数 print 允许我们输出⼀个字符串，例如 print("hello moonbit") ⽉兔中可以通过 init 代码块来定义初始化指令 可以简单理解为程序主⼊⼝ 1. fn init { 2. println("hello moonbit") // 函数名中的ln代表换⾏ 3. } 4 命令与副作⽤ 输出命令可能会破坏引⽤透明性 命令的类型也是单值类型 1. fn do_nothing() { // 返回值为单值类型时可以省略返回类型声明 2. let _x = 0 // 结果为单值类型，符合函数定义 3. } 7 变量 在⽉兔中，我们可以在代码块中⽤ let mut 定义临时变量 1. let mut x = 1 2. x = 10 // 赋值操作是⼀个命令 在⽉兔中，结构体的字段默认不可变，我们也允许可变的字段，需要⽤ mut

moonbitlang.cn 5 程序设计 6 基础设计流程 设计是将⾮正式的规范转化为可运⾏代码的过程 推荐采⽤由测试驱动的开发流程 �. 理解问题 涉及哪些概念，它们之间存在怎样的联系？ �. 定义接⼝ 程序应当如何与环境互动？ �. 写测试案例 对于典型输⼊，程序应当如何表现？对于⾮正常输⼊呢？ �. 实现规定的⾏为 经常需要将问题分解为更简单的⼦问题并对各⼦问题重复以上流程 7 num_exchange 时，我们只能将拥有的⽔瓶全部喝完，并 结束 我们要取得什么？ 给定⼀开始的⽔瓶数 num_bottles 和交换的条件 num_exchange ，计算最多可 以喝多少瓶⽔ 9 步骤⼆：定义接⼝ 给你两个整数 num_bottles 和 num_exchange ，返回你最多可以喝到多少瓶⽔。 1. fn num_water_bottles(num_bottles: Int, num_exchange: 提示：在⽉兔中，Int值域为-2,147,483,648到+2,147,483,647 14 总结 我们希望推动⼤家采取迭代的设计流程 �. 理解问题 �. 定义接⼝ �. 定义测试案例 �. 实现期望的⾏为 现代软件开发依赖测试驱动开发 在开发流程中尽早定义测试案例并⽤它们指导剩余的开发流程 15

拓展阅读：⼆村映射/部分计算 部分计算：程序优化，根据已知信息，运算进⾏特化 已知源程序与解释器，进⾏部分运算，获得⽬标程序 ⽬标程序 x 输⼊数据 -> 输出数据 2 虚拟机 ⼀处编写，处处运⾏ 定义⼀个不基于任何平台的指令集 在不同平台上实现解释器 两种常⻅的虚拟机 堆栈虚拟机：运算数存储在栈上，数据遵循先进后出原则 寄存器虚拟机：运算数存储在寄存器中 3 寄存器虚拟机 例：Lua ，零代表 false 指令 数据操作： const add minus equal modulo 数据存储： local.get local.set 控制流： if/else call 7 类型定义 数据 1. enum Value { I32(Int) } // 只考虑32位有符号整数 指令 1. enum Instruction { 2. Const(Int) Local_Get(String); Local_Set(String) // 取值、设值 6. If(Int, List[Instruction], List[Instruction]) // 条件判断 7. } 8 类型定义 函数 1. struct Function { 2. name : String 3. // 只考虑⼀种数据类型，故省略每个数据的类型，只保留名称和数量 4. params : List[String];