响应（在（锈）（Lisp））

许多年前，Peter Norvig写了一篇漂亮的文章，关于用Python创建Lisp解释器。这是我看过的最有趣的教程，不仅因为它向您介绍了我最喜欢的语言家族（Lisp），而且因为它切入了口译员的本质，使您乐于跟随并快速完成。

最近，我有一段时间想学习Rust。这是一种优美的系统语言，我已经看到采用它的人做出了一些伟大的工作。我想，有什么比在其中创建Lisp解释器更好的学习Rust的方法呢？

因此，Rips（一种锈迹斑斑的锈）诞生了。在本文中，您和我将继续关注Norvig的Lispy，但我们将在Rust🙂中代替Python。

如果您还没听说过轻率的话，那么保罗·格雷厄姆（Paul Graham）的一些文章（一，二，三）以及一些Rich Hickey的谈话将使您大为恼火。简而言之，一切都是列表，一切都是表达式，这使得语言非常强大。

我们的结构将与Norvig的教程类似，尽管我会从以下两个方面略微偏离：

而不是2个停止点（Lispy Calculator和Full Lispy），我们有4个停止点。这反映了我在Rust中构建它的阶段。

Norvig的语法基于Scheme。我们也将基于Scheme，但是由于我也是Clojure的粉丝，因此有时我对一些功能使用略有不同的命名和不同的实现。我会在论文中指出这样做的时间。

最后，这是我在Rust中编写的第一个程序。我可能滥用了某些内容，因此，如果您是Rust黑客，我很想听听您的反馈🙂。

正如Norvig建议的那样，我们的第一个目标是创建一个Lisp子集，该子集可以完成基本计算器可以完成的工作。

为了尽可能简化，对于语言1，我们仅支持加法和减法。没有变量定义，没有if语句，nada。

这与Lispy有点不同，但是我发现在Rust中编写该停止点要方便得多。因此，我们的目标是：

我们将需要分析程序并将其转换为抽象语法树。之后，我们可以评估抽象语法树并获得结果。 （有关更详细的定义和说明，请参阅Norvig的文章）。

我们还需要一个错误类型。我们会保持简单，但是如果您好奇的话，可以使用一种更强大的方法。

最后，我们需要一个环境类型。这是我们将存储定义的变量，内置函数等的地方：

我们的目标是采用我们的程序，并从中构建一个抽象的语法树。对于我们来说，这将是RispExp。为此，首先我们将采用我们的程序，并将其切成一堆标记：

fn标记化（expr：String）-> Vec {expr。 replace（“（”，“（”）。replace（“）”，“）”））。 split_whitespace（）。 map（| x | x。to_string（））。搜集 （） }

fn parse （令牌：＆'a [字符串]）->结果 {let（令牌，休息）=令牌。 split_first（）。 ok_or（RispErr ::原因（“无法获得令牌”。to_string（）））？ match＆token [..] {“（” => read_seq（rest），“）” => Err（RispErr :: Reason（“ unexpected`）`。” to_string（））），_ =>确定（（parse_atom （令牌），休息）），}}

注意：通过返回“下一个”切片，我与Norvig的实现略有不同。这使我们可以递归和解析嵌套列表，而无需更改原始列表。

我们获取当前位置的令牌。如果它是列表“（”的开头，我们将开始阅读并解析其后的标记，直到出现右括号为止：

fn read_seq （令牌：＆'a [字符串]）->结果 {让mut res：Vec = vec！ []; let mut xs =令牌；循环{let（next_token，rest）= xs。 split_first（）。 ok_or（RispErr ::原因（“找不到结尾`）`”。to_string（）））吗？如果next_token ==“）” {return Ok（（RispExp :: List（res），rest））//跳过`）`，}之后转到令牌let（exp，new_xs）= parse（＆xs）?;水库推（exp）; xs = new_xs; }}

如果它是列表“）”的结束标记，则我们返回一个错误，因为read_seq应该跳过了它。

fn parse_atom（令牌：＆str）-> RispExp {让potential_float：结果 =令牌。解析（）;匹配potential_float {确定（v）=> RispExp ::数字（v），Err（_）=> RispExp ::符号（令牌。to_string（）。clone（））}}）

让我们继续创建默认的全局环境。正如Norvig解释的那样，环境是我们将存储变量定义和内置函数的地方。

要实现内置操作（+，-），我们需要一种保存rust函数引用的方法。让我们更新RispExp，以便我们可以存储rust函数引用：

然后，我们可以创建一个default_env函数，该函数返回RispEnv，该函数实现+和-

fn default_env（）-> RispEnv {让mut数据：HashMap = HashMap :: new（）;数据。插入（“ +”。to_string（），RispExp :: Func（| args：＆[RispExp] |->结果 {让sum = parse_list_of_floats（args）?. iter（）。fold（0.0，| sum，a | sum + a）;确定（RispExp :: Number（sum））}））;数据。 insert（“-”。to_string（），RispExp :: Func（| args：＆[RispExp] |->结果 {让floats = parse_list_of_floats（args）?;让first = * floats。first（） 。ok_or（RispErr ::原因（“期望至少一个数字”。to_string（）））?;让sum_of_rest = floats [1 ..]。iter（）。fold（0.0，| sum，a | sum + a） ; Ok（RispExp :: Number（first-sum_of_rest））}））; RispEnv {数据}}

为了简化此过程，我创建了一个快速助手，该助手强制我们收到的所有RispExp都是浮点数：

fn parse_list_of_floats（args：＆[RispExp]）->结果，RispErr> {args。 iter（）。映射（| x | parse_single_float（x））。收集（）} fn parse_single_float（exp：＆RispExp）->结果 {match exp {RispExp ::数字（num）=>确定（* num），_ => Err（RispErr ::原因（“期望一个数字“。to_string（））），}}

如果是符号，我们将在环境中查询该符号并将其返回（目前，它应该是RispExp :: Func）

如果是列表，我们将评估第一个表格。它应该是RispExp :: Func。然后，我们将调用该函数，并将所有其他评估形式作为参数。

fn eval（exp：＆RispExp，env：＆mut RispEnv）->结果 {match exp {RispExp :: Symbol（k）=> env.data。得到（k）。 ok_or（RispErr ::原因（格式！（“意外符号k ='{}'”，k）））。 map（| x | x。clone（）），RispExp ::数字（_a）=>确定（exp。clone（）），RispExp :: List（list）=> {let first_form = list。 first（）。 ok_or（RispErr ::原因（“预期为非空列表”。to_string（）））？让arg_forms =＆list [1 ..];让first_eval = eval（first_form，env）?;匹配first_eval {RispExp :: Func（f）=> {let args_eval = arg_forms。 iter（）。 map（| x | eval（x，env））。收集:: ，RispErr >>（）; f（＆args_eval？）}，_ => Err（RispErr :: Reason（“第一个形式必须是一个函数”。to_string（））），}}，RispExp :: Func（_）=> Err（RispErr ::原因（“意外形式”。to_string（））），}}

我们首先需要一种将RispExp转换为字符串的方法。让我们实现展示广告特质

impl fmt ::显示RispExp {fn fmt（＆self，f：＆mut fmt :: Formatter）-> fmt :: Result {let str = match self {RispExp :: Symbol（s）=> s。 clone（），RispExp ::数字（n）=> n。 to_string（），RispExp :: :: List（list）=> {让xs：Vec = list。 iter（）。 map（| x | x。to_string（））。搜集 （）;格式！ （“（{{}）”，xs。join（“，”））}，RispExp :: Func（_）=>“ Function {}”。 to_string（），};写！ （f，“ {}”，str）}}

fn parse_eval（expr：字符串，env：＆mut RispEnv）->结果 {let（parsed_exp，_）= parse（＆tokenize（expr））?;让evaled_exp = eval（＆parsed_exp，env）?;好的（evaled_exp）} fn slurp_expr（）->字符串{let mut expr = String :: new（）; io :: stdin（）。 read_line（＆mut expr）。预期（“读取行失败”）； expr} fn main（）{let env =＆mut default_env（）;循环{println！ （“ risp>”）;让expr = slurp_expr（）;匹配parse_eval（expr，env）{确定（res）=> println！ （“ //🔥=> {}”，res），Err（e）=> match e {RispErr ::原因（msg）=> println！ （“ //🙀=> {}”，msg），}，}}}

好的，我们有一个基本的计算器。现在，让我们添加对布尔值的支持，并介绍一些相等比较器。

impl fmt ::显示RispExp {fn fmt（＆self，f：＆mut fmt :: Formatter）-> fmt :: Result {let str = match self {RispExp :: Bool（a）=> a。 to_string（），

fn eval（exp：＆RispExp，env：＆mut RispEnv）->结果 {match exp {... RispExp :: Bool（_a）=>确定（exp。clone（）），

fn parse_atom（令牌：＆str）-> RispExp {匹配令牌。 as_ref（）{“ true” => RispExp :: Bool（true），“ false” => RispExp :: :: Bool（false），_ => {让potential_float：结果 =标记。解析（）;匹配potential_float {确定（v）=> RispExp ::数字（v），错误（_）=> RispExp ::符号（token。to_string（）。clone（））}}}}

现在，我们应该很好。为了真正看到这些效果，让我们实现=，>， =， 6 5 3 2）为true，因为6> 5> 3>2。让我们为Risp做这个：

fn default_env（）-> RispEnv {让mut数据：HashMap = HashMap :: new（）; ...数据。 insert（“ =”。to_string（），RispExp :: Func（sure_tonicity！（| a，b | a == b）））;数据。 insert（“>”。to_string（），RispExp :: Func（sure_tonicity！（| a，b | a> b）））;数据。 insert（“> =”。to_string（），RispExp :: Func（sure_tonicity！（| a，b | a> = b）））;数据。 insert（“ {{| args：＆[RispExp] | ->结果 {让floats = parse_list_of_floats（args）?;让first =浮动。首先（）。 ok_or（RispErr ::原因（“预期至少一个数字”。to_string（）））？ let rest =＆floats [1 ..]; fn f（上一个：＆f64，xs：＆[f64]）-> bool {匹配xs。 first（）{Some（x）=> $ check_fn（prev，x）&& f（x，＆xs [1 ..]），None => true，}};好（RispExp :: :: Bool（f（first，rest）））}}}; }

好的，现在，让我们将其设为一种语言。让我们介绍一下def和if。

fn eval（exp：＆RispExp，env：＆mut RispEnv）->结果 {match exp {... RispExp :: List（list）=> {let first_form = list。 first（）。 ok_or（RispErr ::原因（“预期为非空列表”。to_string（）））？让arg_forms =＆list [1 ..];匹配eval_built_in_form（first_form，arg_forms，env）{一些（res）=> res，None => {let first_eval = eval（first_form，env）?;匹配first_eval {RispExp :: Func（f）=> {let args_eval = arg_forms。 iter（）。 map（| x | eval（x，env））。收集:: ，RispErr >>（）;返回f（＆args_eval？）; }，_ => Err（RispErr :: Reason（“第一个形式必须是一个函数”。to_string（））），}}}}，

我们采用第一种形式，并尝试将其评估为内置形式。如果可以的话，瞧，否则我们评估为正常。

fn eval_built_in_form（exp：＆RispExp，arg_forms：＆[RispExp]，env：＆mut RispEnv）->选项> {match exp {RispExp ::符号=> match s。 as_ref（）{“ if” =>一些（eval_if_args（arg_forms，env）），“ def” =>一些（eval_def_args（arg_forms，env）），_ => None，}，_ => None，}}

fn eval_if_args（arg_forms：＆[RispExp]，env：mut RispEnv）->结果 {让test_form = arg_forms。首先（）。 ok_or（RispErr ::原因（“预期的测试表单”。to_string（），））？让test_eval = eval（test_form，env）?;匹配test_eval {RispExp :: Bool（b）=> {let form_idx = if b {1} else {2};让res_form = arg_forms。获取（form_idx）。 ok_or（RispErr :: Reason（format！（“ expected form idx = {}”，form_idx）））？让res_eval = eval（res_form，env）; res_eval}，_ => Err（RispErr :: Reason（format！（“意外的测试表单='{}'”，test_form。to_string（））））}}

fn eval_def_args（arg_forms：＆[RispExp]，env：＆mut RispEnv）->结果 {让first_form = arg_forms。首先（）。 ok_or（RispErr :: Reason（“ expected first form”。to_string（），））?;让first_str =匹配first_form {RispExp ::符号（s）=>确定（s。clone（）），_ => Err（RispErr ::原因（“预期的第一个形式是符号”。to_string（），）） } ?;让second_form = arg_forms。得到（1）。 ok_or（RispErr ::原因（“预期的第二种形式”。to_string（），））？如果是arg_forms。 len（）> 2 {return Err（RispErr :: Reason（“ def只能有两种形式”。to_string（），））}让second_eval = eval（second_form，env）?;环境数据。插入（first_str，second_eval）;好的（first_form。clone（））}

risp>（def a 1）//🔥=> a risp>（+ a 1）//🔥=> 2 risp>（if（>（2 4 6）1 2）//🔥=> 2 risp>（if（ 1

现在，让我们将其作为一种全面的语言。让我们实现_lambdas_！我们的语法如下所示：

＃[derive（Clone）]枚举RispExp {Bool（bool），Symbol（String），Number（f64），List（Vec ），Func（fn（＆[RispExp]）->结果 ），Lambda（RispLambda）// bam}＃[derive（Clone）] struct RispLambda {params_exp：Rc ，body_exp：Rc ，}

impl fmt ::显示RispExp {fn fmt（＆self，f：＆mut fmt :: Formatter）-> fmt :: Result {let str = match self {... RispExp :: Lambda（_）=>“ Lambda {}”。 to_string（），

fn eval（exp：＆RispExp，env：＆mut RispEnv）->结果 {match exp {... RispExp :: Lambda（_）=> Err（RispErr ::原因（“意外形式”。 to_string（））），

现在，让我们更新eval来处理fn-这将是创建Lambda表达式的内置调用：

fn eval_lambda_args（arg_forms：＆[RispExp]）->结果 {让params_exp = arg_forms。首先（）。 ok_or（RispErr ::原因（“预期的args形式”。to_string（），））？让body_exp = arg_forms。得到（1）。 ok_or（RispErr ::原因（“预期的第二种形式”。to_string（），））？如果是arg_forms。 len（）> 2 {return Err（RispErr :: Reason（“ fn定义只能具有两种形式”。to_string（），））}}（RispExp :: Lambda（RispLambda {body_exp：Rc :: new（body_exp。clone （）），params_exp：Rc :: new（params_exp。clone（）），}））}

目前，我们只有全球环境。为了支持lambda，我们需要引入作用域环境的概念。每当我们调用lambda时，都需要实例化一个新环境。

为此，我们首先更新RispEnv结构，以保留外部引用：

让我们更新default_env，以指定生存期并返回None作为外部环境：

fn env_get（k：＆str，env：＆RispEnv）->选项 {匹配环境数据。 get（k）{一些（exp）=>一些（exp。clone（）），无=> {match＆env.outer {一些（outer_env）=> env_get（k，＆outside_env），无=>无}}} }} fn eval（exp：＆RispExp，env：＆mut RispEnv）->结果 {match exp {RispExp :: Symbol（k）=> env_get（k，env）。 ok_or（RispErr ::原因（格式！（“意外符号k ='{}'”，k））），

让我们更新一下eval，以便我们知道列表中的第一个表单是lambda时该怎么做：

fn eval（exp：＆RispExp，env：＆mut RispEnv）->结果 {... let first_eval = eval（first_form，env）?;匹配first_eval {RispExp :: Func（f）=> {f（＆eval_forms（arg_forms，env）？）}}，RispExp :: Lambda（lambda）=> {let new_env =＆mut env_for_lambda（lambda.params_exp，arg_forms，env ）?; eval（＆lambda.body_exp，new_env）}，_ => Err（RispErr :: Reason（“第一个形式必须是一个函数”。to_string（））），}

我们首先有一个快速帮助程序函数来评估表达式列表，因为我们将同时对RispExp :: Func和RispExp :: Lambda进行操作

fn eval_forms（arg_forms：＆[RispExp]，env：＆mut RispEnv）->结果，RispErr> {arg_forms。 iter（）。 map（| x | eval（x，env））。搜集 （） }

然后，我们创建一个函数调用env_for_lambda。这将获取params_exp，并创建一个环境，其中每个参数对应于该索引处的参数：

fn env_for_lambda （参数：Rc ，arg_forms：＆[RispExp]，external_env：＆'a mut RispEnv，）->结果，RispErr> {让ks = parse_list_of_symbol_strings（ ？;如果ks。 len（）！= arg_forms。 len（）{return Err（RispErr :: Reason（format！（“ expected {} arguments，got {}”，ks。len（），arg_forms。len（））））; }让vs = eval_forms（arg_forms，external_env）?; let mut数据：HashMap = HashMap :: new（）;对于以ks为单位的（k，v）。 iter（）。 zip（vs. iter（））{数据。 insert（k。clone（），v。clone（））; }好（RispEnv {数据，外部：某（outer_env），}）}

为此，我们需要帮助器parse_list_of_symbol_strings，以确保我们所有的param定义实际上都是符号：

fn parse_list_of_symbol_strings（格式：Rc ）->结果，RispErr> {让list =匹配形式。 as_ref（）{RispExp :: List（s）=>确定（s。clone（）），_ => Err（RispErr :: Reason（“预期的args形式为列表”。to_string（），））}？ ;清单

......