CODEWITHSUNDEEP
parsinghaskelltext-parsingsyntactic-sugarhaskell-parsing
Přemysl Šťastný
Přemysl Šťastný

Reputation: 1832

How to correctly desugar syntactic tree? - reduction of data structure definition / constructor disabling

I am developing a new language in Haskell and I run into a problem with syntactic tree T desugaring.

I have a set of functions f1, f2,... fn, which are simplifying the tree T from the "sugar". They are separated into different recursive functions so the code is more readable (each have some specific task and it is much simpler to understand what they are doing than if they were implemented into one recursion).

The composed function for desugaring looks like

f :: T -> T
f = f1 . f2 . f3 . ... . fn

I have read (and I think) that the best practice in Haskell is, that you represent data in a way, they can't get a wrong/undefined/impossible value. The problem is, that each function f1,...,fn basically reduce the type T by some constructors. (eg. f1 applied to T removes some sugar, represented by some constructor, which can't appear in any later function f2,...,fn).

So to hold the best practices, I would have to somehow define types T1, T2,..., Tn, where

f1 :: T -> T1
f2 :: T1 -> T2
...
fn :: Tn-1 -> Tn

How can I do this please? I was thinking about using Haskell templates but it seems to me like an overkill. Is there some polymorphism approach to that? Can this implementation be overcome without sacrificing code readability?

Why does it matter?

I said the best practices, which might be considered by community as opinion based, so I explain it further.

All functions f1, f2,...,fn are counting on their predecessor to their job. But if the type T is passed from and to f1, f2,...,fn, the compiler

  1. Makes many warning about pattern matching (if they are not properly handled by error "This shouldn't be possible")

  2. I don't get so good compilation check about the code correctness. Compiler can't know, whether I don't do something, which shouldn't be possible. (eg. using syntactic sugar, which was already removed)

A concrete example

For simplicity, let's suppose the Haskell Template Language.Haskell.TH.Exp. If I want to use the same approach for language processing, I might want to define f1 as function, which substitutes all ArithSeqE ([ 1 ,2 .. 10 ]) for AppEs (f x) generating the arithmetic sequence.

Now, I would like to (somehow) define a new type out of Language.Haskell.TH.Exp - T1, which forbids usage of constructor ArithSeqE, so the compiler know that it can't be in any further T2,T3,...Tn and therefore f2,f3,...,fn don't have to pattern match it and can't use it.

Upvotes: 3

Views: 177

Answers (1)

amalloy
amalloy

Reputation: 91837

I have a solution to only some of your problems. I hope that even a partial solution may inspire better ideas.

My idea is to parameterize your sum type, with one type parameter per constructor you may eliminate. The idea is that, while the constructors will remain, you can parameterize them so that they are uninhabited. This way, while the compiler will still, alas, remind you to match the impossible constructors, it will be impossible for one of your desugaring steps to actually leave such a constructor in place.

Suppose you have this type:

data Expr = Value Int
          | Pair Value Value
          | Values [Expr]

You might have a desugaring step that replaces each Pair with a two-element Values constructor. First, we need to replace the two-field constructor with a one-field constructor:

data PairContents = PairContents Value Value
data Expr = Value Int
          | Pair PairContents
          | Values [Expr]

Then, we add a type parameter that allows us to either allow or forbid a PairContents:

newtype No x = No Void
data PairContents = PairContents Value Value
data Expr pairf = Value Int
                | Pair (pairf PairContents)
                | Values [Expr]

Now, a refactoring step that removes all Pair constructors can have the type

desugarPairs :: Expr Identity -> Expr No

It's impossible for an Expr No to contain any Pair constructor, because the type of its Pair field is No PairContents, which is Void, and thus uninhabitable.

As I say, there are several problems with my approach. It means you need 10 type parameters if you have 10 refactoring steps that each desugar one construct; you still have to pattern-match on Pair in the next step even though you know it's impossible. I hope someone will have a better suggestion. But at least this accomplishes something: your refactoring steps can be relied on to have removed all of the sugar they claim to.

Upvotes: 3

Related Questions