haskell 构建DAG以重用节点

我想构建DAG，但在评估时不确定如何在不重复工作的情况下进行。
我从一个AST开始

data Node =
    Lit Double
  | Neg Node
  | Add Node Node

但是遍历let x = Lit 1.0 in Add x x计算 * x两次。我提出了几种方法，但都有问题。

在评论中已经指出，我可能不是指通常意义上的求值。我用它来用XLA在C++中构造一个图。
方法1：缓存已计算的节点

缓存经过评估的节点，然后在节点比较相等的地方重用它们。这是低效的，因为用户知道哪些节点在哪里被重用，所以看起来我们应该能够使用该信息。

方法2：拓扑排序

我尝试了一个拓扑排序（它是拓扑排序吗？）List Node，其中

data Node =
    Lit Double
  | Neg Nat
  | Add Nat Nat

所以我可以将前面的例子表示为[Lit 1.0, Add 0 0]，这样就可以了，但是我不知道如何构造这个列表。
在上面的例子中，它是微不足道的，但是当我有这样的图表时，它就变得混乱了

Lit 1.0
      |
     Neg  Lit 2.0
      | \ /
      | Add
      | /
      Add

因为在构造图的过程中不清楚如何对列表中的节点进行排序。（如果可以看到整个图，那么对节点进行排序是很明显的，但在构造图的过程中却不能。）

方法2a：具有全局状态的拓扑排序

如果我使用的是命令式语言，我可以使用一个全局状态，在创建节点时添加节点。将可变状态转换为函数设置，我立刻想到了State monad，但我 Package 了这个函数，我不想向用户公开monadic计算：我希望他们做

let x = val 1.0
    y = x + x
 in y + y

无

do x <- val 1.0
   y <- x + x
   y + y

我想知道引用透明性是否直接意味着我不能这样做，因为表达式应该被它们的值替换。

方法2b：拓扑排序-合并子图

使用拓扑排序，但是单独构建组件图，然后当我遇到一个合并图的节点时合并它们，比如Add。我不清楚如何做。我可以测试节点的相等性，但是像第一种方法一样，这似乎是一种浪费，因为我们忘记了在哪里重用了什么，然后重新计算它。
我在伊德里斯这样做，但我想在 haskell 也是这样。

粗略地说，你有两个选择：
1.在AST中显式表示共享。这意味着在图中添加一个Let节点。如下所示：

data Expr = Lit Double | Add Expr Expr | Var Int | Let Int Expr Expr

例如，let x = 1; y = x+x in y+y可能如下所示

Let 0 (Lit 1) (Let 1 (Add (Var 0) (Var 0)) (Add (Var 1) (Var 1)))
 -- let x = 1 in   let y = (+)     x       x in (+)      y       y

对于奖励点，使用MonadSupply或类似的方法来简化新变量的分配，如下所示：

do
    x <- fresh
    y <- fresh
    pure $ Let x (Lit 1) (Let y (Add (Var x) (Var x)) (Add (Var y) (Var y)))

您还可以添加方便的函数来操作一元表达式，如

type ExprM = Supply Int Expr

lit :: Double -> ExprM
add :: ExprM -> ExprM -> ExprM
name :: ExprM -> (ExprM -> ExprM) -> ExprM
name val fBody = do
    v <- fresh
    eVal <- val
    eBody <- fBody (var v)
    pure (Let v eVal eBody)

然后，用户可以写入，例如

name (lit 1) $ \x -> name (add x x) $ \y -> add y y

1.在AST外部表示共享--这种方法通常与散列consing捆绑在一起。

data ExprP = Lit Double | Add Int Int
type Env = IntMap ExprP
type IEnv = Map ExprP Int -- optional

这里的表达式只表示顶级操作是什么;所有子树都存储为指针，可以在关联的Env中查找。例如，您的let x = 1; y = x+x in y+y是指向environment：

fromList
    [ (0, Lit 1)
    , (1, Add 0 0)
    , (2, Add 1 1)
    ]

要获得奖励积分，请使用State管理您的环境，如下所示

type Expr = State (Int, Env) Int
allocPointer :: ExprP -> Expr
allocPointer e = do
    (n, env) <- get
    put (n+1, insert n e env)
    pure n

lit :: Double -> Expr
lit = allocPointer . Lit

add :: Int -> Int -> Expr
add a b = allocPointer (Add a b)

然后用户可以写，比如说，

do
    x <- lit 1
    y <- add x x
    add y y

可选的反向环境可以用来实现自动共享--在allocPointer中，当用户请求将e添加到环境中时，可以在反向环境中查找e，并简单地返回适当的指针，而不是在指针已经存在的情况下分配新的指针。

do
    x <- lit 1
    y <- add x x
    z <- add x x
    add y z

并且这将自动发现y和z是相同的（低成本地，即，不需要递归地比较整个项的相等性，仅通过注意到顶层指针相等）。

haskell 构建DAG以重用节点

1条答案

相关问题

热门标签

最新问答