为什么ML/Haskell数据类型对于像数学表达式那样定义“语言”很有用？

Question

这更像是一个关于功能语言中类似ML系列的静态类型系统的软问题。我明白为什么你需要数据类型来描述像列表和树这样的数据结构，但是为数据类型中的命题逻辑定义“表达式”似乎只会带来一些便利，并不是必需的。例如

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各种值。

如何在函数中用这个表达式的表示来做同样的事情？你不能，因为在表达式的初始规范和它的最终评估之间没有“中间形式”：你只能将表达式视为单一的不透明函数调用。在一个特定的值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表示法更通用，更强大，可以用许多不同方式折叠起来。其中一种方法就是评估它，正如基于功能的表示所做的那样。但也有其他：

• 评估之前简化表达
• 为这种表达得到很好的形成
• 怎么算深度嵌套的最深的部分，必须定义的所有变量的列表树，估计很多栈帧怎样的评估可能需要
• 转换表达式为String接近Haskell的表达，你可以键入得到相同的结果

所以如果可能的话，您希望尽可能使用信息丰富的ADT，然后最终将树折叠成更紧凑的形式，只要您具备与其相关的特定功能即可。