我想为动态语言制作一个类型化的 AST。目前,我一直专注于处理收藏。这是一个代表性的代码示例:
{-# LANGUAGE GADTs #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE ExistentialQuantification #-}
data Box = forall s. B s
data BinOp = Add | Sub | Mul | Div
deriving (Eq, Show)
data Flag = Empty | NonEmpty
data List :: Flag -> * -> * where
Nil :: List Empty a
Cons :: a -> List f a -> List NonEmpty a
data Expr ty where
EInt :: Integer -> Expr Integer
EDouble :: Double -> Expr Double
-- EList :: List -> Expr List
虽然我可以很好地构造 List
实例:
*Main> :t (Cons (B (EInt 1)) (Cons (B (EDouble 2.0)) Nil))
(Cons (B (EInt 1)) (Cons (B (EDouble 2.0)) Nil))
:: List Box 'NonEmpty
我完全不确定如何在 Expr
中为 EList
编码此类型。我是否走在正确的道路上?
最佳答案
解决此问题的一种方法是使用运行时类型代表来标记值。我在这里引导斯蒂芬妮·韦里奇。让我们举一个小例子。首先,给出一些类型的表示。这通常是通过单例构造来完成的。
data Type :: * -> * where
Int :: Type Int
Char :: Type Char
List :: Type x -> Type [x]
因此,Type Int
包含一个值,我也将其称为 Int
,因为它充当 Int
类型的运行时代表.如果即使在单色事物中也能看到颜色,则 ::
左侧的 Int
为红色,Type< 后面的
Int
为红色。/code> 是蓝色的。
现在我们可以进行存在性包装,保留实用性。
data Cell :: * where
(:::) :: x -> Type x -> Cell
Cell
是一个用其类型的运行时代表标记的值。您可以通过读取其类型标签来恢复该值的效用。事实上,由于类型是一阶结构,我们可以以一种有用的方式检查它们是否相等。
data EQ :: k -> k -> * where
Refl :: EQ x x
typeEQ :: Type x -> Type y -> Maybe (EQ x y)
typeEQ Int Int = Just Refl
typeEQ Char Char = Just Refl
typeEQ (List s) (List t) = case typeEQ s t of
Just Refl -> Just Refl
Nothing -> Nothing
typeEQ _ _ = Nothing
类型代表上的 bool 相等是没有用的:我们需要相等测试来构造所代表的类型可以统一的证据。通过证据生成测试,我们可以写
gimme :: Type x -> Cell -> Maybe x
gimme t (x ::: s) = case typeEQ s t of
Just Refl -> Just x
Nothing -> Nothing
当然,编写类型标签很麻烦。但为什么要养狗并让自己狂吠呢?
class TypeMe x where
myType :: Type x
instance TypeMe Int where
myType = Int
instance TypeMe Char where
myType = Char
instance TypeMe x => TypeMe [x] where
myType = List myType
cell :: TypeMe x => x -> Cell
cell x = x ::: myType
现在我们可以做这样的事情
myCells :: [Cell]
myCells = [cell (length "foo"), cell "foo"]
然后得到
> gimme Int (head myCells)
Just 3
当然,如果我们不必进行单例构造并且可以对我们可能选择在运行时保留的类型进行模式匹配,那么一切都会更加整洁。我希望当神秘的 pi
量词变得不那么神秘时我们就能实现这一目标。
关于haskell - 如何在 FAST 制定的 AST 中指定异构集合的类型?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34259724/