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

7 Apr 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:

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  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@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe