[Haskell-cafe] Newbie: Is it possible to catch _|_ ?
spamhole-2001-07-16 at deming-os.org
Tue Apr 6 23:41:27 EDT 2004
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 parsings available.
More complex symbols like
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?
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
> 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
> 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
> 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
> 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
More information about the Haskell-Cafe