CODEWITHSUNDEEP
haskellcompiler-constructionalgebraic-data-typestype-constructor
baxbaxwalanuksiwe
baxbaxwalanuksiwe

Reputation: 1494

Implementing algebraic data types to my compiler

I've been trying to write a small compiler for the past few weeks, while reading Stephen Diehl's great tutorial "Write You A Haskell". I'm currently writing an interpreter before writing the compiler.

I have troubles to represent my values evaluated from an algebraic data type constructor application (e.g. in Haskell Just 1, Left "error", etc...).

My values are currently represented by the following type:

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

How would one implement type constructors ?

So far I've thought of this:

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]

But I would have to check every time I work with the constructor if the lengths of the signature and the number of applied values are equal.

Is there another solution ?

Thanks in advance.

Upvotes: 2

Views: 724

Answers (1)

walpen
walpen

Reputation: 379

So there are a number of solutions. The fanciest is to use something like sized-vector and type-natural to constrain the arity of type constructors and arguments to match. If this approach interests you I would look at the source code of the linked libraries to see how it is done, but it involves a huge number of GHC extensions and quite a bit of work.

A less fancy solution is to use create a family of constructor types and app types, as in.

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

This requires producing either manually or automatically quite a bit of noise.

To be frank, I expect the effort of enforcing this invariant in the type level is not worth the benefit. Instead I would suggest using smart constructors to enforce this at a value level.

Upvotes: 3

Related Questions