[Haskell-cafe] Newbie: Is it possible to catch _|_ ?
GK at ninebynine.org
Wed Apr 7 11:51:30 EDT 2004
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
I have seen (at least) three examples of top-down parser generators coded
(1) in Simon Thompson's book, the Craft of Functional Programming. I have
done an implementation based on these ideas , which I have since
discarded in favour of Parsec...
(2) the Parsec parser library , 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 , which is also
based on a Monad but, being less complex, is easier to follow its internals.
(also in the Haskell hierarchical libraries, under 'text'.
 API Documentation:
Source in CVS:
Being part of HaXml:
(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!)
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:
>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
>More complex symbols like
> 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
>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?
> 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
>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...
>Iavor S. Diatchki wrote:
>>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
>>can sometimes detect that a program will loop forever, and instead of
>>code that will simply loop, they generate code that produces a helpful
>>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
>>to handle this exception, especially since there are no guarantees
>>it will ever occur. furthermore this is highly GHC specific behaviour.
>>hope this is helpful
>>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.
>>>Haskell-Cafe mailing list
>>>Haskell-Cafe at haskell.org
>Haskell-Cafe mailing list
>Haskell-Cafe at haskell.org
More information about the Haskell-Cafe