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

newer
[Haskell-cafe] A useful trick for...

older
Re: [Haskell-cafe] How to...

Jon Cast

6 Apr 2004 6 Apr '04

6:33 p.m.

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

Show replies by date

Iavor S. Diatchki

5 Apr 5 Apr

7:34 p.m.

New subject: Newbie: Is it possible to catch _|_ ?

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

Russ Lewis

7 Apr 7 Apr

5:41 a.m.

New subject: Newbie: Is it possible to catch _|_ ?

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

Graham Klyne

9:51 a.m.

New subject: Newbie: Is it possible to catch _|_ ?

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.HuttonMeijerW... Source in CVS: http://cvs.haskell.org/cgi-bin/cvsweb.cgi/HaXml/src/Text/ParserCombinators/H... 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 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

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

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

Matthew Walton

2:41 p.m.

New subject: Newbie: Is it possible to catch _|_ ?

Isn't Happy [1] a bottom-up parser generator in the style of yacc? [1] http://www.haskell.org/happy/ As for parsing yacc's input files, if you can come up with an EBNF grammar for it that avoids some of the nasty recursion possibilities [2] then I can't see why you couldn't parse it with Parsec or some other parsing library. Or even with a parser written using Happy. Parsec's not that bad really, but the HuttonMeijerWallace one is easier if you start off with those and move to Parsec if you need a more powerful solution. But I may be biased as I'm a former student of Graham Hutton's. With all the choices available though there's not much point writing your own unless you've got very unusual requirements, something new to bring to the table, or you like the challenge. So I would definitely recommend HuttonMeijerWallace or Parsec if you're wanting to parse something. It's possible Happy-generated parsers run faster, but I don't really know and I was quite content with Parsec's speed when I used it in my final-year project. Not that it was parsing anything particularly huge at the time. Matthew [1] http://www.haskell.org/happy/ [2] the proper terms for which I can't remember, but I seem to recall that left recusion is one of the nasty ones Graham Klyne wrote:

...

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.HuttonMeijerW...

Source in CVS: http://cvs.haskell.org/cgi-bin/cvsweb.cgi/HaXml/src/Text/ParserCombinators/H...

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!)

Russ Lewis

10 Apr 10 Apr

9 a.m.

New subject: Newbie: Is it possible to catch _|_ ?

Thanks guys for the links to parsers. I wasn't so much looking for a parser as I was exploring the mappings of algorithms. One of my passions is to explore how different computer programming languages interrelate. In particular, I am fascinated with the concept of transforming a program in one language into another language. A parser language is, almost by definition, the specification of a transform (from a linear structure to a heirarchal one), so I am very interested in different ways to build parsers, as then I'm transforming a transform.... Matthew Walton wrote:

...

Isn't Happy [1] a bottom-up parser generator in the style of yacc?

[1] http://www.haskell.org/happy/

As for parsing yacc's input files, if you can come up with an EBNF grammar for it that avoids some of the nasty recursion possibilities [2] then I can't see why you couldn't parse it with Parsec or some other parsing library. Or even with a parser written using Happy.

Parsec's not that bad really, but the HuttonMeijerWallace one is easier if you start off with those and move to Parsec if you need a more powerful solution. But I may be biased as I'm a former student of Graham Hutton's.

With all the choices available though there's not much point writing your own unless you've got very unusual requirements, something new to bring to the table, or you like the challenge.

So I would definitely recommend HuttonMeijerWallace or Parsec if you're wanting to parse something. It's possible Happy-generated parsers run faster, but I don't really know and I was quite content with Parsec's speed when I used it in my final-year project. Not that it was parsing anything particularly huge at the time.

Matthew

[1] http://www.haskell.org/happy/ [2] the proper terms for which I can't remember, but I seem to recall that left recusion is one of the nasty ones

Graham Klyne wrote:

...
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.HuttonMeijerW...

Source in CVS: http://cvs.haskell.org/cgi-bin/cvsweb.cgi/HaXml/src/Text/ParserCombinators/H...

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!)

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

7757

Age (days ago)

7761

Last active (days ago)

List overview

Download

5 comments

5 participants

participants (5)

Graham Klyne
Iavor S. Diatchki
Jon Cast
Matthew Walton
Russ Lewis