标签: data-reify

拿一个最小的语言(显然叫做Hutton's Razor):

{-# OPTIONS_GHC -fno-warn-missing-methods #-}

data Expr =
    Lit Int
  | Add Expr Expr
  deriving (Eq, Show)

instance Num Expr where
  fromInteger = Lit . fromInteger
  (+)         = Add

tree 0 = 1
tree n =
  let shared = tree (n - 1)
  in  shared + shared

如果我们只是tree 30在GHCi中运行,那么类型将默认为,Integer并且我们将立即得到答案,因为tree共享的递归计算.但是如果我们运行tree 30 :: Expr,我们会得到一个巨大的语法树,因为Haskell提供的共享let不会转移到嵌入式语言中的表达式.

该data-reify库可用于观察表达式中可能存在的任何隐式共享.我们可以添加一些机器来实现:

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE TypeFamilies #-}

import Control.Applicative
import Data.Reify …

我有一个EDSL它提供了列表式组合子数组(map,zipWith,等.)

一些组合器要求某些输入是随机访问.例如,Gather从另一个指定的索引处从数据数组中选择元素的数据数组:

Gather (Manifest [10,11,12]) (Manifest [2,0,0,1,2]) = [12,10,10,11,12]

该语言使用data-reify包来恢复共享.问题在于,有时相同的子树包含需要提供随机访问的节点和可以按顺序计算的节点.让他们共享会破坏后续的评估者.

例如,在下面的树中,我希望[1,2,3]保持共享,但Manifests将它们包装为恢复图中的不同节点:

     [1, 2, 3]
     /       \
 Manifest Manifest
    |        |
    |     Map (+1)
    \     /
    Gather

更复杂的示例可能包括许多共享节点,所有共享节点都应该变得不同(即使Map (+1) (Manifest [1,2,3])可以共享).

     [1, 2, 3]
     /       \
 Manifest Manifest
    |        |
 Map (+1)  Map (+1)
    |       /|
 Map (*2)  / |
    \     /  |
    Gather   |
        \    |
        ZipWith (+)

即使我找到了简单案例(直接Gather引用Manifest)的解决方案,它也已经涵盖了大多数用例.

欢迎任何指示!

下面是一个简单的语言模型.

module …