为我的编译器实现代数数据类型

Question

过去几周我一直在尝试编写一个小型编译器，同时阅读了 Stephen Diehl 的精彩教程 "Write You A Haskell"。我目前在写编译器之前先写一个解释器。

我无法表示从代数数据类型构造函数应用程序评估的值（例如在 Haskell Just 1、Left "error" 等中）。

我的值当前由以下类型表示：

data Value
    = Int Integer
    | Flt Double
    | Chr Char
    | Str String
    | Lam Name AST.Expr (Scope Value)
    | HLam (Value -> Value)

如何实现类型构造函数？

到目前为止我想到了这个：

data Value
    = Int Integer
    | Flt Double
    | Chr Char
    | Str String
    | App Constr [Value]  -- Constr applied of [Value]
    | Lam Name AST.Expr (Scope Value)
    | HLam (Value -> Value)

-- Constructor ID and signature
-- would be translated to a lambda abstraction
data Constr = Constr Name [Type]

但是我每次使用构造函数时都必须检查签名的长度和应用值的数量是否相等。

还有其他解决方案吗？

提前致谢。

Answer 1

所以有很多解决方案。最奇特的是使用 sized-vector and type-natural 之类的东西来限制要匹配的类型构造函数和参数的数量。如果您对这种方法感兴趣，我会查看链接库的源代码以了解它是如何完成的，但它涉及大量的 GHC 扩展和相当多的工作。

一个不太花哨的解决方案是使用创建一系列构造函数类型和应用程序类型，如下所示。

data Const0 
data Const1
-- etc.
data ConstN

data App0 = App0 Const0
data App1 = App1 Const1 Value
-- etc.
data AppN = AppN ConstN Value Value ... Value

data AppI = AppI0 App0 | AppI1 App1 | ... | AppIN App1N

这需要手动或自动产生相当多的噪音。

坦率地说，我预计在类型级别强制执行此不变量所付出的努力得不偿失。相反，我建议使用 smart constructors 在值级别强制执行此操作。

为我的编译器实现代数数据类型

Implementing algebraic data types to my compiler

compiler-construction

haskell

algebraic-data-types

type-constructor