MUA Interpretor

Project for PPL course.

Build

cargo build

Run

cargo run // Interactive

cargo run <file> // Read in file

MakeUp Programming Language

语言要求

Revised 2021-12-16

基本数据类型value

数字number，字word，表list，布尔bool

• 任何值之间都以空格分隔
• 数字的字面量以[0~9]或'-'开头，不区分整数，浮点数
• 字的字面量以双引号"开头，不含空格，采用Unicode编码。在"后的任何内容，直到空格（包括空格、tab和回车）为止的字符（不含空格），都是这个字的一部分，包括其中可能有的"和[]等符号
• 表的字面量以方括号[]包含，其中的元素以空格分隔；元素可是任意类型；元素类型可不一致
  • 表的第一个元素和[之间，以及最后一个元素和]之间不需要有空格分隔
  • 表中的字不需要"引导
  • 这是一个有三层表的字面量的例子：[a [b [c d] e]]
• 布尔量只有两个值：true和false
• 数字和布尔量在计算时可以被看作是字的特殊形式，即在字面量和变量中的字，当其中的内容是数字或布尔量时，总是可以根据需要自动被转换成数字或布尔量

名字name

一个只含有字母和数字及下划线的字，可以用做名字，名字区分大小写。

基本操作operation

基本形式：操作名 参数

操作名是一个名字，与参数间以空格分隔。参数可以有多个，多个参数间以空格分隔。每个操作所需的参数数量是确定的，所以不需要括号或语句结束符号。所有的操作都有返回值。

一个程序就是操作的序列。

基本操作有：

• make <name> <value>： 将value绑定到name上，绑定后的名字位于当前命名空间，返回value。此文档中的基本操作的名字不能重新命名
• thing <name>：返回word所绑定的值
• :<name>：与thing相同
• print <value>：输出value，返回这个value
• read：返回一个从标准输入读取的数字或字
• 运算符operator
  • add, sub, mul, div, mod：<operator> <number> <number>

⬆️ 第一次提交做到这里 ⬆️

测试共 10 分。

---

• erase <name>：清除word所绑定的值，返回原绑定的值
• isname <word>：返回word是否是一个名字，true/false
• run <list>：运行list中的代码，返回list中执行的最后一个op的返回值
• eq, gt, lt：<operator> <number|word> <number|word>
• and, or：<operator> <bool> <bool>
• not：not <bool>

判断

• if <bool> <list1> <list2>：如果bool为真，则执行list1，否则执行list2。list均可以为空表，返回list1或list2执行后的结果。如果被执行的是空表，返回空表。如果被执行的表只有一项，且非OP，返回该项。
• isnumber <value>：返回value是否是数字
• isword <value>：返回value是否是字
• islist <value>：返回value是否是表
• isbool <value>：返回value是否是布尔量
• isempty <word|list>: 返回word/list是否是空字/空列表

函数定义和调用

定义

make <name> [<list1> <list2>]，其中：

• name为函数名
• list1为参数表
• list2为操作表

以下为函数定义的例子：

make "prt [
  [a]
  [print :a]
]

调用

<functionName> <arglist>，其中：

• 为make中定义的函数名，不需要双引号"
• 是参数表，中的值和函数定义时的中名字进行一一对应绑定

以下为函数调用的例子：prt "hello

本地变量（第二阶段）

以下规则仅适用于第二阶段评测。本地变量的规则在第三阶段将会调整。

• 在函数中访问（读取）变量的值的时候，首先访问本地，如果本地不存在，则访问全局
• 在函数中做make时，永远只写本地： 1. 检查本函数内是否存在这个名字，如果存在，则对已有的变量赋值； 2. 否，则在本地定义一个新的变量
• 在函数内make出来的函数只在该函数内有效，但是这样的函数并不会访问定义它的函数的本地变量，它的外部仍然直接就是全局变量区

函数相关的操作

• return <value>：停止执行函数，设定value为返回给调用者的值
• export <name>：将本地make的变量<name>输出到全局，返回它的值：
  • 如果全局没有这个变量，则增加一个全局变量
  • 如果全局已经有了同名的变量，则替换全局变量的值
  • 在函数内make出来的函数一样可以被export到全部

⬆️ 第二次提交做到这里 ⬆️

自测数据共 50 分； 线上 CI 测试共 60 分。

---

简单函数式编程

首先先介绍两个重要概念。

闭包

闭包的定义：如果函数 f 内定义了函数 g，那么如果 g 存在自由变量（即 g 中未定义的变量），那么将产生闭包。根据以上定义，实现闭包需要支持两项功能：

1. 函数内定义函数；

   这很简单。因为 MUA 函数与表没有区别，所以实际上函数内定义函数就是函数内定义表。

2. 函数可以对上文进行值捕获。

   我们通过一个简单的例子来了解捕获的概念。

   make "f [[x] [
     make "g [[y] [return add :x :y]]
     return g 42
   ]]
   

   上面的函数 f 中嵌套定义了函数 g。函数 g 中存在自由变量 x，函数 g 成为闭包，捕获上文中的变量 x，即在闭包定义时，变量 x 被添加到闭包的作用域中。注意，我们捕获的是值，不是引用，闭包不会对被捕获变量本身产生副作用。那么如果运行以下代码：

   print f 233
   

   结果应输出 275。一言以蔽之，闭包就是“代码 + 环境”。

高阶函数

高阶函数是至少满足下列一个条件的函数：

• 接受一个或多个函数作为输入
• 输出一个函数

根据以上定义，实现高阶函数需要支持两项功能：

• 函数可以接受一个或多个函数作为输入

  因为 MUA 函数与表没有区别，所以接受函数作为输入就是接受列表作为输入，但我们还需要 track 输入的函数的环境。

• 函数可以输出一个函数

  因为 MUA 函数与表没有区别，所以简单来说输出一个函数就是输出一个表，但我们还需要 track 输出的函数的环境。

简单函数式编程

有了以上两大特性，MUA 真正意义上支持了函数式编程，即函数为“一等公民”，和变量地位等同。接下来介绍一个函数式编程综合应用。

make "f1 [[x] [
    make "g1 [[y] [return add :x :y]]
    return :g1
  ]
]
make "c1 f1 42
make "c2 f1 24
print c1 1
print c2 2

f1 接受一个 x 参数，返回一个闭包 g1，闭包环境为 x 与 y。调用 f1 即返回闭包 g1。那么对于 c1 闭包来说，其环境是 x = 42；对于 c2 闭包来说，其环境是 x = 24。随后我们输出调用 c1 与 c2 的结果，输出是：

43
26

补充一个柯里化例子。柯里化是把接受多个参数的函数变换成接受一个单一参数（最初函数的第一个参数）的函数，并且返回接受余下的参数而且返回结果的新函数的技术。

make "curry_two [[f x] [
  return [[y] [return f :x :y]]
]]
make "f2 [[x y] [
  return add :x :y
]]
make "f2p curry_two :f2 42

上面的函数 curry_two 接受函数 f 及其需要的第一个参数，返回一个接受剩下一个参数的函数闭包。闭包捕获了环境中的 f 与 x。f2 是需要两个参数的函数，将 f2 及其第一个参数传入 curry_two，得到一个新函数，其接受一个参数（即原 f2 的第二个参数），返回该参数与 42 的和。因此有下面程序

print f2p 233

输出结果为 275。

任务与一些说明

综合以上背景知识，你需要实现以下特性：

• 闭包。嵌套可能有多层。
• 高阶函数。

总的来说，本阶段的实现重点在于你需要跟踪每个函数的环境。处理多层嵌套时可以考虑维护一个环境的栈，方法很多，这里提供一个建议 :)

同时在原规则中，对于本地变量的要求是

访问变量值时首先访问本地，如果本地不存在则访问全局。在函数内 make 出来的函数只在该函数内有效，但是这样的函数并不能访问定义它的函数的本地变量，它的外部仍然直接就是全局变量区。

支持闭包和高阶函数的 MUA 则不适用以上要求，应为：嵌套定义的函数访问变量时先访问本地，本地不存在则访问定义它函数的本地变量，然后再访问全局变量区。

⬆️ 第三次提交做到这里 ⬆️

自测数据共 30 分； 线上 CI 测试共 35 分。

---

字表处理

• readlist：返回一个从标准输入读取的一行，构成一个表，行中每个以空格分隔的部分是list的一个元素，元素的类型为字
  • 用readlist读入的只可能是单层的表
• word <word> <word|number|bool>：将两个word合并为一个word，第二个值可以是word、number或bool
• sentence <value1> <value2>：将value1和value2合并成一个表，两个值的元素并列，value1的在value2的前面
• list <value1> <value2>：将两个值合并为一个表，如果值为表，则不打开这个表
• join <list> <value>：将value作为list的最后一个元素加入到list中（如果value是表，则整个value成为表的最后一个元素）
• first <word|list>：返回word的第一个字符，或list的第一个元素
• last <word|list>：返回word的最后一个字符，list的最后一个元素
• butfirst <word|list>：返回除第一个元素外剩下的表，或除第一个字符外剩下的字
• butlast <word|list>：返回除最后一个元素外剩下的表，或除最后一个字符外剩下的字

注：如果字表处理操作产生了函数，则该函数在产生时捕获变量形成闭包。

数值计算

• random <number>：返回[0,number)的一个随机数
• int <number>: floor the int
• sqrt <number>：返回number的平方根

其他操作

• save <word>：在名为word的文件中，以源码形式保存当前命名空间内的名字及其对应的值（即将形如 make <key> <value> 的代码写入文件），返回文件名
• load <word>：执行名为word的文件中所有代码，返回true
• erall：清除当前命名空间的全部内容，返回true

注：闭包的 save 相对比较复杂，测试中 save 只涉及全局变量，不考察闭包 save 后 load 行为是否正确。有兴趣的同学可以尝试实现。

既有名字

系统提供了一些常用的量，或可以由其他操作实现但是常用的操作，作为固有的名字。这些名字是可以被删除（erase）的。

• pi：3.14159

测试共 45 分。