Simon Fowler | 27 Jul 16:18 2012
Picon

Access to the Parse Tree for Expressions

Dear all,

I'm currently working on a project which would benefit from access to the parse tree - ideally, we would like to deconstruct an expression into its constituent types. Currently we are using the exprType function to return the type of an expression, but this is limited as it only works for one 'level', per se.

An example would be as follows. Currently, if we were to type in "map", we would be given a result of type Type, which we could further deconstruct into the various subtypes, as so:

map :: (a -> b) -> [a] -> [b]
split into:
    (a -> b)
    [a]
    [b]


This is sufficient for the basics of the project at the moment, but ideally, we would like to use the parse tree to analyse the structure of expressions and thereby the types of the corresponding sub-expressions. Take "foldr drop" for example; we can determine the different types for the different functions with exprType:

foldr :: (a -> b -> b) -> b -> [a] -> [b]
drop :: Int -> [c] -> [c]

Now we can call exprType on the application "foldr drop":

foldr drop :: (Int -> [c] -> [c]) ->  [c] -> [Int] -> [c]
which would be split, according to our current code, into:
    arg1: (Int -> [c] -> [c])
    arg2: [c]
    arg3: [Int]
    result: [c]

The problem here is that we are unable to separate the "drop" from the "foldr". The project we are working on involves composing and decomposing expressions, and it is important that we can decompose the type of "foldr drop" into the types of the sub-expressions "foldr" and "drop" recursively.

Ideally, we would like to construct a data structure which is much more akin to a parse tree with type annotations, in this case: 
    PTreeApp
        (PTreeExpr "foldr"  [| (a -> b -> b) -> b -> [a] -> [b] |])
        (PTreeExpr "drop"   [| Int -> [c] -> [c] |])
        [| (Int -> [c] -> [c]) -> [c] -> [Int] -> [c] |]
where the types in semantic brackets are a structural representation (e.g. TypeRep.Type) of the given types.


Looking at the code of exprType, a call is firstly made to hscTcExpr, which in turn makes a call to hscParseStmt to return the parse tree. This would seem to provide the functionality that we would require, in that it would give access to a type-checkable parsed statement, but it doesn't seem to be exported by HscMain. Is there another function, which is accessible through the API, that would support this or something similar?

I am far from an expert using the GHC API, so apologies if I am doing something grossly wrong or have missed something blatantly obvious. 

Thank you for taking the time to read this.

Kind regards,
Simon 
_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Simon Marlow | 30 Jul 12:17 2012
Picon

Re: Access to the Parse Tree for Expressions

On 27/07/2012 15:18, Simon Fowler wrote:
> Dear all,
>
> I'm currently working on a project which would benefit from access to
> the parse tree - ideally, we would like to deconstruct an expression
> into its constituent types. Currently we are using the exprType function
> to return the type of an expression, but this is limited as it only
> works for one 'level', per se.
>
> An example would be as follows. Currently, if we were to type in "map",
> we would be given a result of type Type, which we could further
> deconstruct into the various subtypes, as so:
>
> map :: (a -> b) -> [a] -> [b]
> split into:
>      (a -> b)
>      [a]
>      [b]
>
>
> This is sufficient for the basics of the project at the moment, but
> ideally, we would like to use the parse tree to analyse the structure of
> expressions and thereby the types of the corresponding sub-expressions.
> Take "foldr drop" for example; we can determine the different types for
> the different functions with exprType:
>
> foldr :: (a -> b -> b) -> b -> [a] -> [b]
> drop :: Int -> [c] -> [c]
>
> Now we can call exprType on the application "foldr drop":
>
> foldr drop :: (Int -> [c] -> [c]) ->  [c] -> [Int] -> [c]
> which would be split, according to our current code, into:
>      arg1: (Int -> [c] -> [c])
>      arg2: [c]
>      arg3: [Int]
>      result: [c]
>
> The problem here is that we are unable to separate the "drop" from the
> "foldr". The project we are working on involves composing and
> decomposing expressions, and it is important that we can decompose the
> type of "foldr drop" into the types of the sub-expressions "foldr" and
> "drop" recursively.
>
> Ideally, we would like to construct a data structure which is much more
> akin to a parse tree with type annotations, in this case:
>      PTreeApp
>          (PTreeExpr "foldr"  [| (a -> b -> b) -> b -> [a] -> [b] |])
>          (PTreeExpr "drop"   [| Int -> [c] -> [c] |])
>          [| (Int -> [c] -> [c]) -> [c] -> [Int] -> [c] |]
> where the types in semantic brackets are a structural representation
> (e.g. TypeRep.Type) of the given types.
>
>
> Looking at the code of exprType, a call is firstly made to hscTcExpr,
> which in turn makes a call to hscParseStmt to return the parse tree.
> This would seem to provide the functionality that we would require, in
> that it would give access to a type-checkable parsed statement, but it
> doesn't seem to be exported by HscMain. Is there another function, which
> is accessible through the API, that would support this or something similar?
>
> I am far from an expert using the GHC API, so apologies if I am doing
> something grossly wrong or have missed something blatantly obvious.

What you want is unfortunately not provided by the GHC API at the 
moment.  exprType only returns the Type; I think what you want is the 
typechecked abstract syntax for the expression, so that you can traverse 
and analyse it.

It wouldn't be hard to do this.  TcRnDriver.tcRnExpr needs to return the 
LHsExpr Id (maybe it needs to be zonked first), and then we need to 
expose an API to provide access to this via the GHC module.  Feel free 
to have a go yourself, or make a ticket and we'll hopefully get around 
to it.

Cheers,
	Simon

Gmane