[Haskell-cafe] Newbie: Is it possible to catch _|_ ?

[Graham Klyne]

I'm not familiar with yacc, but I understand that it's a bottom-up parser 
generator.  I've not come across any bottom-up parser generators written in 
Haskell.

I have seen (at least) three examples of top-down parser generators coded 
in Haskell:
(1) in Simon Thompson's book, the Craft of Functional Programming.  I have 
done an implementation based on these ideas [3], which I have since 
discarded in favour of Parsec...
(2) the Parsec parser library [1], which is a very full-functioned and 
easy-to-use library, but which might be not-so-easy for a Haskell newcomer 
to figure out its internal workings because it is heavily based on Monads.
(3) the HuttonMeijerWallace parser combinator library [2], which is also 
based on a Monad but, being less complex, is easier to follow its internals.

[1] http://www.cs.uu.nl/~daan/parsec.html
     (also in the Haskell hierarchical libraries, under 'text'.

[2] API Documentation:
http://www.cs.york.ac.uk/fp/HaXml/HaXml/Text.ParserCombinators.HuttonMeijerWallace.html
Source in CVS:
http://cvs.haskell.org/cgi-bin/cvsweb.cgi/HaXml/src/Text/ParserCombinators/HuttonMeijerWallace.hs
Being part of HaXml:
http://www.cs.york.ac.uk/fp/HaXml/

[3] http://www.ninebynine.org/Software/HaskellUtils/Withdrawn/Parse.hs
(And related code in same directory.  This was just about the first real 
program I write in Haskell, so don't look to this for an example of how one 
*should* program using Haskell!)

#g
--

At 22:41 06/04/04 -0700, Russ Lewis wrote:
>I am new to Haskell (and to functional programming).  In fact, I haven't 
>written a single line of Haskell code.  But I love programming languages, 
>and when I read the Gentle Introduction to Haskell, I started pondering 
>how to use Haskell to solve my current favorite problem, which is the 
>generation of parsers for yacc-style languages.
>
>I asked this question on the list because, in my trivial implementation of 
>a Haskell yacc parser, there is the potential for expressions which expand 
>to themselves.  I don't know how I would avoid this without making the 
>yacc->Haskell translation substantially nontrivial.
>
>Basically, you figure that for each yacc symbol, you define a function 
>which takes as input a list of tokens and returns a list of list of 
>tokens; in each list, the first token is what you were parsing for and the 
>rest is any remaining tokens in the stream.  So the yacc symbol:
>
>exp2:
>   NUM
>;
>
>would turn into Haskell code something like this:
>
>parse_exp1 [] = []
>parse_exp1 token NUM:xs = (token exp1 NUM:xs):[]
>parse_exp1 xs = []
>
>The last line simply says that if there are no matches, then there are no 
>parsings available.
>
>More complex symbols like
>   exp2:
>      exp1 "++"
>   ;
>
>Would require recursion like this:
>
>   parse_exp2 [] = []
>   parse_exp2 token exp1 a : token '++' : xs = (token exp2 exp1 a : xs) : []
>   parse_exp2 xs = join_lists map parse_exp2 parse_exp1 xs
>
>.....where join_lists joins all of the returned lists of lists into a 
>single list of lists
>
>Finally, expressions with multiple possible parsings, such as
>   exp3:
>      NUM
>      exp4
>   ;
>
>would require multiple parse stacks returned:
>   parse_exp3 [] = []
>   parse_exp3 token NUM : xs = ((token exp3 NUM) : xs) : ( parse_exp3 
> parse_exp4 token NUM : xs )
>   ... (more expressions) ...
>
>The complex 2nd line is required because the parser needs to consider the 
>fact that the correct parsing might be to parse NUM->exp3 OR the correct 
>parsing might be NUM.....->exp4->exp3.  So it generates a pair of parse 
>stacks, one for each possibility.
>
>But what if exp4 recurses back into exp3 with this yacc definition?
>   exp4:
>      exp3 "++"
>   ;
>
>Now the expression 'parse_exp3 parse_exp4 ......' is going to expand to 
>include 'parse_exp3' of the same token stream.  This is obviously an 
>infinite loop.
>
>What I was hoping was that Haskell would detect the infinte loop, and I 
>could basically "catch" that infinite loop and turn it into [] (i.e. no 
>valid parsing down this path).
>
>Now I have to find something else, I guess...
>
>Russ Lewis
>
>Iavor S. Diatchki wrote:
>
>>hello,
>>this is an attempt to give an answer to someone who is new to Haskell.
>>
>>the answer to your question is: no, there is no way to "catch" _|_,
>>as that would mean that we can solve the halting problem.
>>a piece of advice, especially while you are new to haskell ---
>>don't worry too much about _|_. occasonally you will run into
>>an infinite loop, but that probably means you have a bug in your program,
>>so fix it, and don't try to "catch" it.
>>
>>as an unrelated comment, Haskell does have some exception handling features,
>>but they often get pretty advanced.  mostly these are unrelated to _|_.
>>
>>what the previous answers were saying, is that some implementations 
>>(notably GHC)
>>can sometimes detect that a program will loop forever, and instead of 
>>generating
>>code that will simply loop, they generate code that produces a helpful 
>>message,
>>so that you can fix your program.
>>
>>the way this particular feture happens to be implemented in GHC is that
>>it generates code that raises an exception.  it is hard to see why one 
>>might want
>>to handle this exception, especially since there are no guarantees 
>>whatsoever that
>>it will ever occur.  furthermore this is highly GHC specific behaviour.
>>
>>hope this is helpful
>>-iavor
>>
>>
>>
>>Jon Cast wrote:
>>
>>>Russ Lewis <spamhole-2001-07-16 at deming-os.org> wrote:
>>>
>>>
>>>
>>>>Another newbie question: Is it possible to catch _|_ - that is, to 
>>>>encounter it, handle it and continue?  I'm assuming that you all are 
>>>>going to say no, since I can't figure out any way to do this and retain 
>>>>the functional nature of Haskell.
>>>>
>>>
>>>
>>>This isn't possible in a deterministic language, for several reasons.
>>>The IO monad, however, is non-deterministic, and its `catch' function
>>>can be used to catch any _|_ value that can be caught, specifically
>>>those arising from calls to throw, error, and certain infinite loops.
>>>It is non-deterministic, though, so it won't catch all _|_s, nor will it
>>>give any guarantee as to which _|_ it will catch (for example, in error
>>>3 + throw (DynException (toDynamic False)) it's indeterminate whether
>>>error's return value or throw's return value will ultimately be caught.
>>>
>>>Jon Cast
>>>_______________________________________________
>>>Haskell-Cafe mailing list
>>>Haskell-Cafe at haskell.org
>>>http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>_______________________________________________
>Haskell-Cafe mailing list
>Haskell-Cafe at haskell.org
>http://www.haskell.org/mailman/listinfo/haskell-cafe

------------
Graham Klyne
For email:
http://www.ninebynine.org/#Contact