有没有办法在我的递归函数中强制使用 Variant 类型

Question

我已经完成了作业的最后一个问题，该问题要求以下内容

"Add a local definition construct “let v=e in f” where v is a variable and e and f are expressions. This means that v has the value e with in f, and this over-rides any value of v in the environment (or an enclosing let, too). As with the previous example, you’ll need to think of a syntax for this that you can easily parse with an extension of the existing parser"

我的问题是给定代码库中的解析器和编译器使用的下面概述的预定义 expr 类型在我的 let 语句实现中无法识别，我收到以下错误：

错误：该表达式的类型为 expr，但表达式应为 char

类型

我已经向解析器添加了功能，该解析器翻译形式为“~ var1 = exp1 > exp2”的 let 语句，其中解析器的输出形式为 Bes “(v1, e1, e2)”。这一切都经过验证并且有效。当我在编译器匹配语句中添加了一个 case 来识别刚才提到的第二种形式时，就会出现我的问题；匹配后，我的 "preprocessor" 函数被调用，如下所示。它应该在编译器中匹配 v1、e1 和 e2，并在 e2 上递归匹配，在 return 表达式 e2 的更新形式进行进一步编译之前，用表达式 e1 替换变量 v1 的任何实例。相反，我收到上面的匹配错误。

表达式定义

type expr =
    Num of int
  | Var of char
  | Add of expr*expr
  | Mul of expr*expr
  | Con of expr*expr*expr
  | Bes of expr*expr*expr

指令定义

type instr =
  | Push of int
  | Fetch of char
  | Add2
  | Mul2
  | Con2

其他类型

type program = instr list

type stack = int list

我的预处理器函数

let rec preprocessor eo2 eo1 vo1  : expr =

    match eo2 with
    | Num n -> eo2
    | Var v -> if (v = vo1) then eo1 else eo2
    | Add (e1, e2) -> Add ((preprocessor e1 eo1 vo1),(preprocessor e2 eo1 vo1))
    | Mul (e1, e2) -> Mul ((preprocessor e1 eo1 vo1),(preprocessor e2  eo1 vo1))
    | Con (e1,e2,e3) -> Con ((preprocessor e1 eo1 vo1), (preprocessor e2     eo1 vo1), (preprocessor e3 eo1 vo1))
(*  | Bes (v1,e1,e2) -> (preprocessor e2 e1 v1) *)

编译器函数

(*
compile : expr -> instr list
*)

let rec compile e =


  match e with
  | Num n -> [Push n]
  | Var v -> [Fetch v]
  | Add (e1,e2) -> compile e2 @ compile e1 @ [Add2]
  | Mul (e1,e2) -> compile e2 @ compile e1 @ [Mul2]
  | Con (e1,e2,e3) -> compile e3 @ compile e2 @ compile e1 @ [Con2]
  | Bes (v1,e1,e2) -> compile (preprocessor e2 e1 v1) @ [] (*ERROR SOURCE LINE*)

我希望预处理器函数将子表达式 e2 中的任何变量更改为表达式 e1，然后可以在编译过程中继续执行。相反，我收到错误消息，告诉我提供了 expr 而不是预期的 char。我已经尝试了一些事情，例如使用 let 语句将 e2 e1 和 v1 分配给新变量，我明确地为它们提供了 expr 类型 (e2:expr) 等，我还尝试从预处理器中显式 return expr 但我仍然卡住了。代码库似乎太大了，不能直接转储在这里，所以如果我应该发布功能解析器，请告诉我。感谢您的帮助

Answer 1

错误来自 v1 具有类型 expr 而你需要一个 char 因为你正在比较 v1 与每个 v 或 Var v，其类型为 char。问题的根源是你的 Bes 构造函数有错误的类型，它应该是 Bes of char * expr * expr，因为你语言的 let v = x in y 构造中的 v 应该是一个变量，它在您的实现中用 char 类型表示。
使用预处理来实现 let 不是一个好主意：

2.1。它会爆炸你的代码，考虑下面的例子：
```
let x = <very-big-expr> in
let y = x + x + x in
y + y
```
将最终复制 <very-big-exp> 6 次。一般来说，这将是一个指数级的爆炸，这将导致 AST 达到千兆字节

2.2。复制表达式并不总是有效的，例如在表达式可能有副作用的语言中，这会破坏程序的语义，请考虑以下示例
```
let x = read_int () in
let y = read_int () in
x*x + y
```
假设输入"3\n4\n"，正确的实现应该是return3*3+4=13，而你的实现会导致代码，
```
read_int () * read_int () + read_int ()
```
这将读取两个整数并将它们相乘并要求第三个整数并因通道错误结束而失败。

这意味着，您必须将 Bes 作为您语言的原始语言并正确编译它。
如果你决定坚持预处理阶段，那么你不应该直接将 Bes 添加到原语集，并执行 AST->AST 转换每次您的解析器看到 let 语句时。那么你将永远不会在编译器代码中看到 Bes 。这实际上会使 let 成为语法糖或宏，这又是 Let 的不正确语义，请参见上面的 (1) 和 (2)。

有没有办法在我的递归函数中强制使用 Variant 类型

Is there a way to enforce a Variant type in my recursive function

types

ocaml

utop