什么是表达式树

一颗表达式树 (Expr tree) 是计算机程序内部用于表达一个表达式的一个类树型 (tree-like) 数据结构的实例，基本上，你可以理解它是一个树型对象。

如下是表达式树的一种定义：

struct Expr;
using Exprs = std::vector<Expr*>;

struct Expr {
  bool isAtom;
};

struct NonAtomExpr : Expr {
  NonAtomExpr( ) : Expr(false) { }
  Expr *head;
  Exprs *children;
};

enum class AtomType {
  Int,
  Flt,
  Str,
  Sbl
};

struct AtomExpr : Expr {
  explicit AtomExpr(AtomType atomType) : Expr(true), atomType(atomType) { }
  AtomType atomType;
}

为了将一个表达式树实例翻译为等价的 LLVM IR Value（比如说一个 constant, 或者一个 function call 等等），我们需要一种统一的方式将每一个表达式树实例集中的每一个实例和类型集中的每一个类型关联起来，抽象地说，就是在我们定义出了一个树集 Exprs 一个类型集 Types 之后，将 Exprs 集中的元素和 Types 集中的元素进行一个满射关联（找到或者说定义出这样的一个函数：f: Exprs → Types 并且它是满射）：

expr-tree-typing.png

图左边表示表达式树集 Exprs, 右边表示类型集 Types.

由于表达式树集 Exprs 里边有无限多个元素，所以无法手动地一一指定每一个表达式树实例的类型。所以，我们迫切地需要一种便捷、优雅、统一的方式来做这件事：给每一个表达式树实例确定一个类型。

基于类型推导指引的类型确定方法

一个类型推导指引 (Type deduction guide) 实例是一个键值对（你也可以理解它为数学上的一个二元元组），key 和 value 都是 Expr.

对于一个表达式树实例（以下都简称表达式树，或者表达式，或者 Expr) 的类型推导，首先需要知道它是什么表达式：是一个 NonAtomExpr 还是一个 AtomExpr, 如果是 AtomExpr, 则可以根据 AtomExpr 的 atomType 字段来推定这个 AtomExpr 的类型。

如果是 NonAtomExpr, 则需要确定它每一个 children（如果有）的类型，它的 head（也有可能是 NonAtomExpr）的类型，然后再确定它自己的类型。

这样，我们立刻就有了一种递归的思路，即：表达式树的类型的推导过程就是递归的，为了确定一个表达式的类型，要么确定它自己的类型，要么确定它的子表达式的类型再确定它自己的类型，就是这么简单。

我们接下来使用 Wolfram Mathematica 数学软件来演示这个过程，因为在 Wolfram 语言中，刚好就有一个内建符号可以做这件事：ReplaceRepeated.

我们首先把类型推导指引实现为 Wolfram 语言中的一个关于 Rule[key_, value_] 的 List Expr:

typeDeductionRules = {
  Condition[x_, IntegerQ[x]] -> Typed[x, "Integer64"],
  Condition[x_, NumberQ[x] && Not[IntegerQ[x]]] -> Typed[x, "Real64"],
  x_ -> UnknownType[x]
}

仅仅定义这三条规则以及可以确定很多表达式的类型了，下面我们来试一试：

截屏2023-01-29 下午6.16.33.png

可以看到，对于 AtomExpr, typing 函数以及顺利地开始工作了。接下来再加上几条关于 NonAtomExpr 的规则，并且为了不让替换过程过早结束，我们还把最后一条 x_ -> UnknownType[x] 去掉：

typeDeductionRules = {
   Condition[x_, IntegerQ[x]] -> Typed[x, "Integer64"],

   Condition[x_, NumberQ[x] && Not[IntegerQ[x]]] -> Typed[x, "Real64"],
   sin[x_] -> Typed[sin[x], "Real64"],

   myFunc1[x : Typed[_, t_], y : Typed[_, t_]] -> 
    Typed[myFunc1[x, y], "Real64"],

   myFunc1[x : Typed[_, t_], y : Typed[_, t_], z : Typed[_, t_]] -> 
    Typed[myFunc1[x, y, z], "Boolean"]
   };