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

[Russ Lewis]

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
>