为什么 ML/Haskell 数据类型可用于定义 "languages" 之类的算术表达式？

Question

这更像是一个关于函数式语言（如 ML 系列语言）中的静态类型系统的软问题。我理解为什么您需要数据类型来描述列表和树之类的数据结构，但是像数据类型中的命题逻辑那样定义 "expressions" 似乎只是带来了一些便利，而且没有必要。例如

datatype arithmetic_exp = Constant of int
                        | Neg of arithmetic_exp
                        | Add of (arithmetic_exp * arithmetic_exp)
                        | Mult of (arithmetic_exp * arithmetic_exp)

定义一组值，您可以在这些值上编写一个 eval 函数来给出结果。您也可以定义 4 个函数：const: int -> int、neg: int -> int、add: int * int -> int 和 mult: int * int -> int，然后 add (mult (const 3, neg 2), neg 4) 类型的表达式会给您同样的结果没有任何静态安全损失。唯一的麻烦是你必须做四件事而不是两件事。在学习 SML 和 Haskell 时，我一直在努力思考哪些功能可以为您提供必要的东西，哪些只是一种方便，所以这就是我问的原因。我想如果您想将评估值的过程与值本身分离，这会很重要，但我不确定它在哪里有用。

非常感谢。

Answer 1

初始/一阶/基于数据类型的编码（又名深度嵌入）和最终/高阶/基于评估器的编码（又名浅嵌入）之间存在二元性。您确实通常可以使用组合器的类型类而不是数据类型（并在两者之间来回转换）。

这是一个展示这两种方法的模块：

{-# LANGUAGE GADTs, Rank2Types #-}

module Expr where

data Expr where
  Val :: Int -> Expr
  Add :: Expr -> Expr -> Expr

class Expr' a where
  val :: Int -> a
  add :: a -> a -> a

您可以看到这两个定义看起来非常相似。 Expr' a 基本上是在描述 Expr 上的代数，这意味着如果你有 Expr' a，你可以从 Expr 中得到 a。类似地，因为您可以编写实例 Expr' Expr，所以您可以将类型 forall a. Expr' a => a 的术语具体化为类型 Expr:

的句法值

expr :: Expr' a => Expr -> a
expr e = case e of
  Val n   -> val n
  Add p q -> add (expr p) (expr q)

instance Expr' Expr where
  val = Val
  add = Add

expr' :: (forall a. Expr' a => a) -> Expr
expr' e = e

最后，选择一个表示而不是另一个表示实际上取决于您的主要关注点：如果您想检查表达式的结构（例如，如果您想优化/编译它），如果您有访问 AST。另一方面，如果您只对使用折叠计算不变量感兴趣（例如表达式的深度或其评估），则更高阶的编码就可以了。

Answer 2

ADT 是一种形式，您可以通过简单评估以外的方式检查和操作它。一旦你在一个函数调用中隐藏了所有有趣的数据，你就不能再用它做任何事情，只能评估它。考虑这个定义，类似于您问题中的定义，但使用 Var 项表示变量并删除 Mul 和 Neg 项以专注于加法。

data Expr a = Constant a
            | Add (Expr a) (Expr a)
            | Var String
            deriving Show

显然要写的函数是eval，当然。它需要一种查找变量值的方法，而且很简单：

-- cheating a little bit by assuming all Vars are defined
eval :: Num a => Expr a -> (String -> a) -> a
eval (Constant x) _env = x
eval (Add x y) env = eval x env + eval y env
eval (Var x) env = env x

但是假设您还没有变量映射。您有一个大型表达式，您将针对不同的变量选择对其进行多次评估。一些愚蠢的递归函数构建了一个表达式，如：

Add (Constant 1) 
    (Add (Constant 1) 
         (Add (Constant 1) 
              (Add (Constant 1) 
                   (Add (Constant 1) 
                        (Add (Constant 1) 
                             (Var "x"))))))

每次计算时都重新计算 1+1+1+1+1+1 会很浪费：如果你的计算者能意识到这只是另一种写法 Add (Constant 6) (Var "x") 不是很好吗？

因此，您编写了一个表达式优化器，它在任何变量可用之前运行并尝试简化表达式。当然，您可以应用许多简化规则；下面我只实现了两个非常简单的例子来说明这一点。

simplify :: Num a => Expr a -> Expr a
simplify (Add (Constant x) (Constant y)) = Constant $ x + y
simplify (Add (Constant x) (Add (Constant y) z)) = simplify $ Add (Constant $ x + y) z
simplify x = x

现在我们傻傻的表情是怎样的？

> simplify $ Add (Constant 1) (Add (Constant 1) (Add (Constant 1) (Add (Constant 1) (Add (Constant 1) (Add (Constant 1) (Var "x"))))))
Add (Constant 6) (Var "x")

所有不必要的东西都被删除了，你现在有一个漂亮干净的表达式来尝试 x 的各种值。

如何在函数中使用此表达式的表示来做同样的事情？你不能，因为在表达式的初始规范和它的最终评估之间没有 "intermediate form"：你只能将表达式视为一个单一的、不透明的函数调用。以 x 的特定值对其进行评估必然会重新评估每个子表达式，并且无法解开它们。

这是您在问题中提出的功能类型的扩展，再次增加了变量：

type FExpr a = (String -> a) -> a

lit :: a -> FExpr a
lit x _env = x

add :: Num a => FExpr a -> FExpr a -> FExpr a
add x y env = x env + y env

var :: String -> FExpr a
var x env = env x

用相同的愚蠢表达式多次求值：

sample :: Num a => FExpr a
sample = add (lit 1)
             (add (lit 1)
                  (add (lit 1)
                       (add (lit 1)
                            (add (lit 1)
                                 (add (lit 1)
                                      (var "x"))))))

它按预期工作：

> sample $ \_var -> 5
11

但每次尝试不同的 x 时，它都必须做一堆加法，即使加法和变量大部分是无关的。而且您无法简化表达式树。你不能在定义它的时候简化它：也就是说，你不能让 add 更聪明，因为它根本无法检查它的参数：它的参数是函数，就 add就其而言，无所不能。你也不能在构造它之后简化它：那时你只有一个不透明的函数，它接受一个变量查找函数并产生一个值。

通过将问题的重要部分建模为独立的数据类型，您可以使它们成为程序可以智能操作的值。如果将它们保留为函数，您会得到一个较短的程序，但功能较弱，因为您将所有信息锁定在只有 GHC 可以操作的 lambda 表达式中。

并且一旦您使用 ADT 编写了它，如果您愿意的话，不难将该表示折叠回更短的基于函数的表示。也就是说，拥有类型

的函数可能会很好

convert :: Expr a -> FExpr a

但事实上，我们已经做到了！这正是 eval 所具有的类型。您可能没有注意到 FExpr 类型别名，它未在 eval.

的定义中使用

所以在某种程度上，ADT 表示更通用、更强大，就像一棵树，您可以用许多不同的方式折叠它。其中一种方法是评估它，就像基于函数的表示所做的那样。但还有其他的：

先化简表达式再求值
生成必须定义的所有变量的列表才能使此表达式格式正确
计算树最深处的嵌套深度，以估计评估者可能需要多少堆栈帧
将表达式转换为近似于 Haskell 表达式的字符串，您可以键入以获得相同的结果

因此，如果可能的话，您希望尽可能长时间地使用信息丰富的 ADT，然后在您有特定的事情要做时，最终将树折叠成更紧凑的形式。

为什么 ML/Haskell 数据类型可用于定义 "languages" 之类的算术表达式？

Why are ML/Haskell datatypes useful for defining "languages" like arithmetic expressions?

haskell

types

ml