February 2002 - Haskell

RE: H98 Report: expression syntax glitch
by Simon Peyton-Jones 28 Feb '02

28 Feb '02

I'm inclined to stay with the formulation as a side condition, assuming you all think it's correct. Filling it out as a complete context free grammar as you suggest looks complex. That makes it easy to introduce new errors. And in fact the meta-rule can be implemented by simply telling the parser to resolve shift/reduce errors by shifting. So the extra complexity in the grammar is not mirrored in the implementation. So I propose to say that 'let', 'lambda' and 'if' productions have a side condition that (say) let .. in exp is syntactially valid only if the phrase is followed by one of the punctuation symbols ) ] } | ; , .. where of then else Any objectors? Myself I think this is way better than "leftwards precedence" and "rightwards precedence", which I never did understand Simon | -----Original Message----- | From: Ross Paterson [mailto:ross@soi.city.ac.uk] | Sent: 27 February 2002 10:43 | To: Simon Peyton-Jones | Cc: haskell(a)haskell.org | Subject: Re: H98 Report: expression syntax glitch | | | On Tue, Feb 26, 2002 at 08:23:03AM -0800, Simon Peyton-Jones wrote: | > I didn't phrase it right. I meant that a let/lambda/if always | > extends to the next relevant (not part of a smaller expression) | > punctuation symbol; and if that phrase parses as an exp | that's fine, | > otherwise it's a parse error. So I should not really speak | in terms | > of 'ambiguity'. | > | > Perhaps we can simply say that | > let .. in exp | > is legal only if the phrase is followed by one of the punctuation | > symbols. That's nice, because we don't need to talk of | "not part of a | > smaller expression". | | OK, so you have a context-free grammar qualified by a rule | forbidding some of the derivations of that grammar. | | Another solution would be to subdivide exp^10 using a | superscript I've called A or B from lack of imagination: | | exp10A -> \ apat[1] ... apat[n] -> exp (lambda | abstraction, n>=1) | | let decls in exp (let expression) | | if exp then exp else exp (conditional) | exp10B -> case exp of { alts } (case expression) | | do { stmts } (do expression) | | fexp | | Only the latter sort can be followed by infix operators or | type signatures. We could extend the distinction to the exp^i | (here x ranges over {A,B}): | | exp -> exp0B :: [context =>] type (expression | type signature) | | exp0 | expi -> expiA | | expiB | expix -> expi+1B [qop(n,i) expi+1x] | | lexpix | | rexpix | lexpix -> (lexpiB | expi+1B) qop(l,i) expi+1x | lexp6x -> - exp7x | rexpix -> expi+1B qop(r,i) (rexpix | expi+1x) | | and the rules for sections would be | | aexp -> ... | | ( expi+1B qop(a,i) ) (left section) | | ( qop(a,i) expi+1 ) (right section) | | It's complicated, but it does at least specify precisely the | language and parses we want in a single context-free description. |

2 1

library design conventions
by Hal Daume III 27 Feb '02

27 Feb '02

it says: > A function or action taking a some kind of state and returning a pair > consisting of a result and a new state, the result is the first element > of the pair and the new state is the second, see e.g. Random. unfortunatly, Random and the mapAccum{RL} functions don't agree at all. the accumulating map functions assume the state is in the first element and the new element is in the second, but random doesn't behave this way and it appears neither do the libraries. am i the only one bothered by this? i would prefer if at least the libraries would change and put the state in the first position of the pair. it's probably hopeless to get Random to change at this point, as with the mapAccum functions. - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

1 2

RE: H98 Report: expression syntax glitch
by Simon Marlow 27 Feb '02

27 Feb '02

> Consider the following Haskell 98 expressions: > > (let x = 10 in x `div`) > (let x = 10 in x `div` 3) > > To parse the first, a bottom-up parser should reduce the > let-expression > before the operator, while to parse the second it should shift. > But it needs 4 tokens of lookahead to decide which to do. That seems > unreasonable, and is well beyond the LALR(1) parsers used by > Hugs and GHC. > Replacing `div` by + needs 2 tokens of lookahead, which is > still too much. > I think the first should be made illegal, but can't think of > a clean rule. > (There are similar expressions using lambda and if.) This is a known problem with the Haskell grammar. Another example in a similar vein is let x = 3 in x == 4 == True which should parse as (let x = 3 in x == 4) == True according to the "extends as far to the right as possible" rule, because '==' is nonfix. In order to do this, the parser must have access to the fixity information for '==', which is unreasonable (fixity declarations can even be local to a binding group). Perhaps it is possible to post-process the parse when the fixities have been resolved, but that seems overly complex even if it is possible. My favourite solution would be to remove the notion of operator precedence from the grammar altogether and specify fixity resolution separately. Cheers, Simon

2 1

H98 Report: expression syntax glitch
by Ross Paterson 27 Feb '02

27 Feb '02

Consider the following Haskell 98 expressions: (let x = 10 in x `div`) (let x = 10 in x `div` 3) To parse the first, a bottom-up parser should reduce the let-expression before the operator, while to parse the second it should shift. But it needs 4 tokens of lookahead to decide which to do. That seems unreasonable, and is well beyond the LALR(1) parsers used by Hugs and GHC. Replacing `div` by + needs 2 tokens of lookahead, which is still too much. I think the first should be made illegal, but can't think of a clean rule. (There are similar expressions using lambda and if.)

3 4

Re: Behavior of fromInteger on out-of-range arguments
by George Russell 27 Feb '02

27 Feb '02

Dean Herrington wrote > It seems to me that the behavior for `(fromInteger x)::Int`, where x is > an Integer outside Int range, should be the same (in terms of the > Haskell report) as that for `y + y`, where y is an Int such that > `toInteger y + toInteger y` is outside Int range. I agree almost entirely. Note that Haskell 98 does not define what happens on overflow (section 6.4). Personally my preference would be for making overflowing operations on Ints cause an error, and on Words wrap, as happens with SML. I think GHC just wraps everything. There is one exception though. According to section 6.4.1 a numeric literal should be interpreted as "the application of the function fromInteger to the appropriate value of type Integer". In my opinion a numeric literal in an exact type (such as Int or Ratio Int) which does not fit in the target representation should ALWAYS raise an error, either at run-time or compile-time, since I can conceive of no conceivable use for typing such a literal, and so it is almost certainly a user error. (The situation is different for inexact types such as Float, since it is understood that say a literal like 0.1 may not be exactly representable, and there is no other convenient way of typing it.)

1 0

RE: H98 Report: expression syntax glitch
by Simon Peyton-Jones 27 Feb '02

27 Feb '02

I didn't phrase it right. I meant that a let/lambda/if always extends to the next relevant (not part of a smaller expression) punctuation symbol; and if that phrase parses as an exp that's fine, otherwise it's a parse error. So I should not really speak in terms of 'ambiguity'. Perhaps we can simply say that let .. in exp is legal only if the phrase is followed by one of the punctuation symbols. That's nice, because we don't need to talk of "not part of a smaller expression". So (let x = 10 in x `div`) would be rejected because x `div` isn't a exp. Simon | -----Original Message----- | From: Ross Paterson [mailto:ross@soi.city.ac.uk] | Sent: 26 February 2002 16:06 | To: Simon Peyton-Jones | Cc: haskell(a)haskell.org | Subject: Re: H98 Report: expression syntax glitch | | | On Tue, Feb 26, 2002 at 07:30:44AM -0800, Simon Peyton-Jones wrote: | > Replace "The ambiguity is resolved by the meta rule that | each of these | > constructs extends as far to the right as possible" by | > | > "The ambiguity is resolved by the meta rule that each | > of these constructs extends to the nearest occurrence of | > the following punctuation symbols that does not form part of | > a nested expression: | > | > ) ] } | ; , .. where of then else | | I didn't think this was going to be pretty, but it doesn't | quite work either. There's no ambiguity in | | (let x = 10 in x `div`) | | The context-free grammar gives exactly one parse for this, | and we want to disallow it. It seems you need to retain the | old meta-rule for the ambiguities but also explicitly exclude | certain forms. |

3 3

java program
by Stewart Litt 27 Feb '02

27 Feb '02

dear sir/madam iam contacting you regarding a java problem which i have come across. My teacher at manchester met has set a problem for us to solve but thinking his teaching is excellent and everyone understands him wen no one does I would appreciate you helping me in this problem as it would save us from embarrassment. THE PROBLEM: Consider a simplified plan of the liverpool bus system. The system consists of a network of bus stops(at most 20) and bus lines (at most 5). Each bus stop has a unique name and each busline has a unique number. Each bus stop is connected to other bus stops by at most 3 different bus lines. Each of these bus lines connects a bus stop to exactly one other bus stop and for each bus stop and each connecting bus line it is known how many minutes the bus needs to get to the next bus stop. The objectives are to design and implement in java: 1. A representation of the bus system using suitable data structures. 2. A mechanism to go from one bus stop to a conected bus stop via a particular bus line. 3. A mechanism for searching for a connection between two given bus stops. A command line text based interface should be provided that will allow the user to issue a series of the following five commands: start: Allows to enter the current bus stop by name and resets the total journey time to zero. list: The system will show the total journey time so far, and all information on the current bus stop, that is, its name and the numbers of all outgoing bus lines. go: The system asks for the number of a busline. If the number is that of an outgoing busline, then the system finds out the busstop connected to the current bus stop and makes it the new current bus stop. If the number is not that of an outgoing bus line, then the system will indicate this by a message , but make no other changes. search: The system asks for the name of a bus stop. The system will then indicate whether there is a way to get to this bus stop from the current bus stop, but makes no other changes. exit: Stops and exits the system. Description of the liverpool bus stop below. THE LIVERPOOL BUS SYSTEM Bus Stop Outgoing bus line Connected bus stop Time in mins Bootle strand 22 South road 11 Pier head 10 Shiel road 14 22 Bootle strand 7 79 Edge hill 11 Edge hill 79 Picton clock 10 Green lane 10 Page moss 13 22 Bootle strand 18 Page moss 10 Prescot 8 Picton clock 79 Netherly 21 Shiel road 10 Green lane 5 South road 22 Green lane 9 _________________________________________________________________ Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp.

3 2

Get paid cash every time you receive email!
by elist365＠citiz.net 27 Feb '02

27 Feb '02

1 0

Behavior of fromInteger on out-of-range arguments
by David Feuer 26 Feb '02

26 Feb '02

What about having Int be considered a restricted integer that notices overflow, and create another type (bit bunch?) that does not notice overflow, and require explicit conversion to go from one to the other? This would seem to be the best of both worlds. The "bit bunch" type could also provide useful info about its size. It could even be possible to have a "machine-specific bit-bunch" of the same size as an Int or bit bunch, but with machine-specified overflow behavior that the programmer can discover (whether this should be at compile-time or run-time I couldn't say). Question: Is there any standard way in Haskell of determining the maximal and minimal Int values? If not, there should. David Feuer

3 2

RE: Behavior of fromInteger on out-of-range arguments
by Simon Peyton-Jones 26 Feb '02

26 Feb '02

| It'd be lovely if the Haskell report took a stand on the | issue, but I suspect that may be too much to hope for. Actually, it'd be an easy, non-destablising change to make to the Report to specify the behaviour of the Int instance of fromInteger on numbers larger than will fit in an Int. If a consensus emerges I'm quite happy to enshrine it in H98. Simon

3 2