设计一个类型安全的、可扩展的Scala表达式求值器 -

题目

设计一个类型安全的、可扩展的Scala表达式求值器

信息

类型：问答
难度：⭐⭐⭐

考点

类型系统, 模式匹配, 隐式转换, 类型类, 递归数据结构

快速回答

实现一个类型安全的表达式求值器需要：

使用密封特质和样例类定义表达式ADT
利用泛型和类型参数确保操作数类型安全
通过隐式解析实现类型类模式，支持扩展
使用模式匹配实现递归求值逻辑
处理自定义类型和错误边界情况

## 解析

本题目要求设计一个类型安全的表达式求值器，需支持基本运算和自定义类型扩展，同时保证编译期类型安全。

核心实现方案

1. 定义表达式代数数据类型（ADT）

// 基础表达式ADT
sealed trait Expr[T]
case class IntLit(value: Int) extends Expr[Int]
case class BoolLit(value: Boolean) extends Expr[Boolean]
case class Add(left: Expr[Int], right: Expr[Int]) extends Expr[Int]
case class Eq[T](left: Expr[T], right: Expr[T]) extends Expr[Boolean]

关键点：使用泛型T确保操作数类型一致，如Eq要求左右表达式类型相同。

2. 实现类型类求值器

trait Evaluator[T] {
  def evaluate(expr: Expr[T]): Either[String, T]
}

object Evaluator {
  // 隐式实例实现
  implicit val intEvaluator: Evaluator[Int] = new Evaluator[Int] {
    def evaluate(expr: Expr[Int]): Either[String, Int] = expr match {
      case IntLit(v) => Right(v)
      case Add(l, r) => 
        for {
          lv <- evaluate(l)
          rv <- evaluate(r)
        } yield lv + rv
    }
  }

  implicit val boolEvaluator: Evaluator[Boolean] = ...

  // 泛型相等比较实现
  implicit def eqEvaluator[T](implicit ev: Evaluator[T]): Evaluator[Boolean] = 
    new Evaluator[Boolean] {
      def evaluate(expr: Expr[Boolean]): Either[String, Boolean] = expr match {
        case Eq(l, r) => 
          for {
            lv <- ev.evaluate(l)
            rv <- ev.evaluate(r)
          } yield lv == rv
      }
    }
}

3. 入口方法

def evaluate[T](expr: Expr[T])(implicit ev: Evaluator[T]): Either[String, T] = 
  ev.evaluate(expr)

最佳实践

类型安全扩展：添加新表达式类型时需确保类型约束

case class Concat(s1: Expr[String], s2: Expr[String]) extends Expr[String]

自定义类型支持：

case class Person(name: String, age: Int)
implicit val personEvaluator: Evaluator[Person] = ...

错误处理：使用Either处理运行时错误（如除零）

常见错误

类型擦除问题：模式匹配时需用ClassTag解决泛型类型擦除
隐式解析失败：未为自定义类型提供Evaluator实例导致编译错误
递归爆炸：复杂表达式需优化为尾递归或使用@tailrec

扩展知识

Free Monad：可分离表达式定义和求值逻辑

GADTs：使用广义代数数据类型强化类型约束

case class Eq[T](left: Expr[T], right: Expr[T])(implicit eq: Eq[T]) 
  extends Expr[Boolean]

宏优化：对常量表达式进行编译期求值

完整示例

// 使用示例
val expr = Eq(Add(IntLit(2), IntLit(3)), IntLit(5))
evaluate(expr)  // Right(true)

// 类型安全验证
val invalid = Eq(IntLit(1), BoolLit(true)) // 编译错误！类型不匹配