[Haskell-cafe] idea: TH calculating type level function results / binary types?

[Marc Weber]

Hi,

Maybe you've noted that I've started writing an XML library which
validates the generated XML against a given DTD at compile time.
Not everything is implemented right now and it would be quite usable if
it didn't take that much time.

The problem:

    To see some details have look at my small announcement on haskellcafe.
    type checking 12 lines of XML code has taken
    > 3hourse using some TypeToNat type equality comparison
    > 35sec using an implementation proposed by Oleg
    > 30sec no longer using HLists to check wether an attribute may be added
      but an AttrOk tag attr class (proposed by Oleg)
    > ?sec after finishing a state transformation implementation propably
      generating thausands of intermediate state or a mixture of this and
      the parser like apporach.

    Even if the last approach works it's a pity because:
    * it took much time to write
    * hard to read code
    * no error messages..
      In the 30sec apprach I've used some instances such as
              class Consume elType state state' | elType state -> state'
              class FailHelper state' state'' | state' -> state''
              instance FailHelper (Fail a) => FailHelper (F a) () -- F indicating sub element could not be consumed, failure
              instance FailHelper a a --  

      So I got error messages telling me
      no instance for MoreElementsExpected
        (Or (E Html_T)
            (E Body_T))
      or such.. that's nice and usable.

    I can't think of a nice way reporting errors when transforming a dtd
    line (a,b,c) (= tag sequence a b c) into
            data State1
            data State2
            data State3
            instance Conseme State1 A_T State2 -- consume tag a 
            instance Conseme State2 B_T State3 -- consume tag b 
            instance Conseme State3 C_T ConsumedEnd -- consume tag c
    in a convinient way without adding much bloat.

    The XHMTL spec has about 150 ! tags.. So even if creating this kind of
    state transforming instances this will result in a lot of bloat.
    So if the compiler has to load a some MB large .hi file it will spend
    unnecessary time just loading them.



an idea: (new?) solution:
  What about enhancing ghc so that 

  a) you can define type level functions and
    calculate the result using template haskell functions:

    benefits:
      * speed (it can even be compiled! )
      * nice error messages on failure
      * mantainable code
      * reusing known source (such as parser combinator libraries)

    syntax could look like this:

      class Bar a b c d | a b -> c, a b -> d

      instance (Maybe x) z $(calculateC) $(calculateD)

      calculateC :: Type -> Type -> Type
      calculateD :: Type -> Type -> Type

    an efficient implementation for
    TypeEq a b typebool | a b -> typebool

    could be done by everyone with ease without reading HList source or
    Olegs papers.. (you should do so anyway ..)
    
  b) add some binary serialization support so that you don't have to do
    expensive data -> type level -> data (de)serializations.
    .hi files wouldn't blow much this way as well.

    So a parse specification such as (1) could really be included within
    types and could become even more complex. Than an exisiting parser
    combinator library could be used and a validating XML library could be
    written within some hours..

    I think ghc is already a superiour compiler because it allows such
    advanced technics thereby making users such as me even ask for more
    :-) I consider this a good sign.


  So has anyone thought about this before?
  Would someone help / guide me implementing this extension in the near
  future?

  Of course it will clash with some instance -X extensions.. but I think
  that in everyday use you'd probably use either this template haskell
  approach or use normal class instance declarations so it I guess it
  could be handled.

Maybe this does already exist in one or the other way?

Sincerly
Marc Weber


(1)
          (Seq
             (Elem Title_T)
             (Seq
                (Star
                   (Or
                      (Elem Script_T)
                      (Or
                         (Elem Style_T)
                         (Or
                            (Elem Meta_T)
                            (Or (Elem Link_T) (Elem Object_T))))))
                (Query
                   (Seq
                      (Elem Base_T)
                      (Star
                         (Or
                            (Elem Script_T)
                            (Or
                               (Elem Style_T)
                               (Or
                                  (Elem Meta_T)
                                  (Or
                                     (Elem Link_T) (Elem Object_T))))))))))