13

I'm trying to implement simple parser in haskell using parsec library (for learning purposes). So I wrote bunch of data structutes and related functions like this:

data SourceElement 
    = StatementSourceElement Statement
    | FunctionSourceElement FunctionName FunctionBody

data Statement 
    = IfStatement Expr Statement Statement
    | WhileStatement Expr Statement

data FunctionBody = FunctionBody [SourceElement]

parseSourceElement :: Parser SourceElement
parseSourceElement = ...

parseFunctionBody :: Parser FunctionBody
parseFunctionBody = ...

It works fine. Now I want to split this stuff into two modules to separate FunctionBody and Statement data structures (because of readability issues). But I can't! The reason is cyclic dependency between SourceElement and FunctionBody.

So, is there any way to solve this problem ?

sergeyz
  • 1,308
  • 2
  • 14
  • 23
  • 3
    Luqui's answer is good for the general case of removing cycles in data structures, but in your case I'd look at re-designing you syntax tree. In OO languages it is sometimes common to represent syntax with a general tree structure (like your SourceElement) and use tags (like your Statement enum) to label it, but in functional language with algebraic types like Haskell you can represent trees directly. – stephen tetley Dec 09 '12 at 17:00
  • stephen tetley - General tree structure is a nice idea, but unfortunately it means that I can create (by accident) invalid syntax tree (if i correctly understand the idea). In my initial tree implementation any constructed tree is valid syntax tree for parsed language. – sergeyz Dec 11 '12 at 18:16
  • @sergeyz, I think you have misunderstood @stephentetley. I believe he was suggesting `data Statement = IfStatement Expr Statement Statement | WhileStatement Expr Statement`, etc. which actually makes sure that you can only create valid trees moreso than this representation. – luqui Dec 11 '12 at 20:24

2 Answers2

13

The typical way I break dependency cycles is by parameterizing something out. In this case, your Function module might do function parsers for your language, but expressed in such a way that it can do so no matter what the rest of the language is like. Thus:

module Function where 

data FunctionBody e = FunctionBody [e]

parseFunctionBody :: Parser e -> Parser (FunctionBody e)

And

module AST where

data SourceElement
    = StatementSourceElement Statement
    | FunctionSourceElement FunctionName (FunctionBody SourceElement)

Thus the mutual recursion is abstracted into a simple recursion + parameterization. I think parameterization is at least as important as separating different things into different files, so it's kind of nice (and kind of annoying) that one forces the other.

luqui
  • 59,485
  • 12
  • 145
  • 204
  • 1
    I agree about the importance of parameterization, but it should be meaningful and thought-out, not ad-hoc. – Roman Cheplyaka Dec 09 '12 at 16:46
  • 1
    I am only partially in agreement with you. I think all code "should be meaningful and thought-out", and the choice of parameterization no more or less so. Gotta try things out to know what getting it right looks like. I would rather use an imperfectly parameterized module than one that is coupled to its context -- at least in the former case there is hope for someone who has another use in mind, even if it is some work away. In the latter case you are screwed. – luqui Dec 10 '12 at 02:35
  • @luqui, I have parametrized my [original](https://github.com/zaretskysa/Jazzist/blob/develop/src/Parsing/Ast.hs) data structures and now I have some new modules: [Statement](https://github.com/zaretskysa/Jazzist/blob/decomposition/src/Parsing/Statement.hs), [Expression](https://github.com/zaretskysa/Jazzist/blob/decomposition/src/Parsing/Expression.hs). The bad thing is that it looks kind of messy. – sergeyz Dec 15 '12 at 16:43
  • @sergeyz, Yeah, that does look kind of messy. It's too bad we have to make that trade-off in current Haskell -- for a long time I've wanted Coq-style "sections" that make highly parametric things more palatable. – luqui Dec 15 '12 at 19:54
6

Haskell actually allows recursive modules, and GHC supports them (with a minor inconvenience of writing .hs-boot files). See How to compile mutually recursive modules.

I don't see anything wrong with using this feature here.

Roman Cheplyaka
  • 37,738
  • 7
  • 72
  • 121
  • 2
    I don't think `.hs-boot` is that minor an inconvenience. The amount of inconvenience has caused me, at least, to switch to another strategy each time I have attempted it. Perhaps it's my idealism -- I feel like .hs-boot files should be easy to automatically generate, so I feel frustrated when I have to write them myself. – luqui Dec 10 '12 at 02:36
  • 1
    You may find [#1409](http://hackage.haskell.org/trac/ghc/ticket/1409) an interesting read. – Roman Cheplyaka Dec 10 '12 at 09:20