Re: [Haskell-cafe] Automatic fixity allocation for symbolic operators
On Sat, 14 Oct 2006, Jim Apple wrote: On 10/14/06, Brian Hulley [EMAIL PROTECTED] wrote: User defined fixities are an enormous problem for an interactive editor This is the second or third time you've proposed a language change based on the editor you're writing. I don't think this is a fruitful avenue. I assume that editor developers, compiler writers and language tool writers (documentation extraction, source code formatting) get much more insight into syntactic issues than other users. Finding some problem when implementing one of these tools often reveals weak points in the language syntax. I repeat my example of a source code formatting tool which must decide whether to format a + b * c or a + b * c It needs to know the precedences of the used operators, which, as Brian pointed out, is possibly not even defined somewhere. Alternatively consider a compiler which must have a parser that must adapt the grammar to the module contents (infix statements) in order to parse the module correctly. Even worse: The same symbol can have different precedences, because infix operators can be declared locally. The same problem for a human: In order to analyse the meaning of an expression with infix operators he must know the precedences. That is, problems with infix operators are by far not bound to a text editor! You may argue that difficult language syntaxes like that of C++ push the parser technique forward. However this seems to me like Windows pushes memory development. Concerning the automatic precedence assigment according to the characters in an infix operator, I think that it is difficult to find a reasonable algorithm, because that algorithm would also limit the kind of operator schemes that can be used. If the operations can be associated with basic mathematical operations like +, *, =, then it would work, but what about different structures? How would you translate lattice operations up and down, how operations like parallel and serial composition? Summed up, I think infix handling must be somehow improved, but I don't know how. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Automatic fixity allocation for symbolic operators
Hello, Henning Thielemann wrote: [...] I repeat my example of a source code formatting tool which must decide whether to format a + b * c or a + b * c It needs to know the precedences of the used operators, which, as Brian pointed out, is possibly not even defined somewhere. Alternatively consider a compiler which must have a parser that must adapt the grammar to the module contents (infix statements) in order to parse the module correctly. Even worse: The same symbol can have different precedences, because infix operators can be declared locally. I would suggest to first parse modulo fixity and precedence (keep all operator applications in flat lists) and only later, if/when precedence and fixity information is available, parse those operator lists. The same problem for a human: In order to analyse the meaning of an expression with infix operators he must know the precedences. That is, problems with infix operators are by far not bound to a text editor! Quite so. I wouldn't consider it a problem though. The meaning of the expression also depends on the meaning (definition) of the operators involved, and of other functions used in the expression. That information may also be located elsewhere or even not yet available, just as precedence declarations. Locality has been wittingly sacrificed for flexibility. Regards, Arie -- Mr. Pelican Shit may be Willy. ^ /e\ --- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re: [Haskell-cafe] Automatic fixity allocation for symbolic operators
Regarding latticess and locality... This idea probably won't help with editors, but the OP's question has sparked a discussion here and some thinking in my head--thanks Brian. What if operator precedences were specified as a partial order instead of using numbers? Using numbers implies a potentially deceptive sense of completeness: well I've given @+@ a precedence 5 and let that be written in stone forever so that all conflicts are resolved henceforth. Most fixities I've dealt with are put into play only amongst related operators in a project (@+@ or @*@ in MySpecialLib) or amongst operators from a related library. If the syntax were like: infixr @+@ infixr @+@ prec @+@ @*@ then the programmer gets to specify as much as they have decided and no more. 5 @+@ 3 * 7 would simply be under defined and would require parens. Perhaps Brian's original idea of systematically determining unspecified operator precedences could be recast in this system. Consider (woefully under contemplated) precedence specifiers such as: precInherit * - @*@ precAll ?+? ?*? Regarding precAll: I'm not a regular expressions/glob for semantics fan, but you get the idea. The idea is to define a partial order on operators and let undecided operator relationships remain undefined. Composition remains an open issue, but perhaps someone else will have a light bulb about that. Nick On 10/16/06, Arie Peterson [EMAIL PROTECTED] wrote: Hello, Henning Thielemann wrote: [...] I repeat my example of a source code formatting tool which must decide whether to format a + b * c or a + b * c It needs to know the precedences of the used operators, which, as Brian pointed out, is possibly not even defined somewhere. Alternatively consider a compiler which must have a parser that must adapt the grammar to the module contents (infix statements) in order to parse the module correctly. Even worse: The same symbol can have different precedences, because infix operators can be declared locally. I would suggest to first parse modulo fixity and precedence (keep all operator applications in flat lists) and only later, if/when precedence and fixity information is available, parse those operator lists. The same problem for a human: In order to analyse the meaning of an expression with infix operators he must know the precedences. That is, problems with infix operators are by far not bound to a text editor! Quite so. I wouldn't consider it a problem though. The meaning of the expression also depends on the meaning (definition) of the operators involved, and of other functions used in the expression. That information may also be located elsewhere or even not yet available, just as precedence declarations. Locality has been wittingly sacrificed for flexibility. Regards, Arie -- Mr. Pelican Shit may be Willy. ^ /e\ --- ___ 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
Re: [Haskell-cafe] Automatic fixity allocation for symbolic operators
On Mon, 16 Oct 2006, Nicolas Frisby wrote: Regarding latticess and locality... This idea probably won't help with editors, but the OP's question has sparked a discussion here and some thinking in my head--thanks Brian. What if operator precedences were specified as a partial order instead of using numbers? Using numbers implies a potentially deceptive sense of completeness: well I've given @+@ a precedence 5 and let that be written in stone forever so that all conflicts are resolved henceforth. Most fixities I've dealt with are put into play only amongst related operators in a project (@+@ or @*@ in MySpecialLib) or amongst operators from a related library. If the syntax were like: infixr @+@ infixr @+@ prec @+@ @*@ dict.leo.org says: great minds think alike http://www.haskell.org/pipermail/haskell-cafe/2005-February/009260.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[3]: [Haskell-cafe] Automatic fixity allocation for symbolic operators
Hello Nicolas, Monday, October 16, 2006, 6:31:42 PM, you wrote: What if operator precedences were specified as a partial order instead of using numbers? precInherit * - @*@ precAll ?+? ?*? Regarding precAll: I'm not a regular expressions/glob for semantics fan, but you get the idea. The idea is to define a partial order on operators and let undecided operator relationships remain undefined. Composition remains an open issue, but perhaps someone else will have a light bulb about that. well, it is what typically done when you define expression parsers by hand (for any language that had fixed precedences). smth like this: expr1 ::= expr2 | expr1 + expr2 | expr1 - expr2 expr2 ::= expr3 | expr2 * expr3 | expr2 / expr3 expr3 ::= ... but when you want to have user-defined operators, that will mean that you need either to define precedences to all other operators (including those from other libs), or sometimes user programs will not compile because they used combination of operators with undefined precedence good for making good headache :) -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Automatic fixity allocation for symbolic operators
Jim Apple wrote: On 10/14/06, Brian Hulley [EMAIL PROTECTED] wrote: User defined fixities are an enormous problem for an interactive editor This is the second or third time you've proposed a language change based on the editor you're writing. I don't think this is a fruitful avenue. Bertram Felgenhauer wrote: Brian Hulley wrote: infixr 9 .!! 99.9 Ouch. As far as editors go I have little sympathy. Nicolas Frisby wrote: I think it's unreasonable to tie programmers' hands for the sake of off-loading rather trivial tasks to editors. J. Garrett Morris wrote: On 10/14/06, Nicolas Frisby [EMAIL PROTECTED] wrote: Perhaps the editor could assume a default precedence ... I agree that changing the language in such an unintuitive way - breaking existing code in the process - to suit an editor is counterproductive and ridiculous. I feel that the example I used of an interactive editor has somewhat eclipsed the purpose of my post, which was basically to see if there is some way to arrive at an agreed association of operator precedences with symbolic ops such that this would include the current Prelude operators and have some kind of intuitive extension to all other possible symbolic ops which would respect one's expectations that * and + should be similar to * and + in terms of relative precedence and absolute associativity. After all, if a library writer decided to make * bind more loosely than + one might justifiably be frustrated at the apparent inconsistency therefore why not just make all this systematic and fixed down to remove these problems? I had thought perhaps someone might have already made such a global operator table suitable for functional programming, or some suitable algorithm hence the inclusion of my first stumbling attempt at one to try and set the ball rolling and at least save someone else several hours of hard work going down the same dead end if such it is. Jim Apple wrote: There are three ways to change Haskell's lexical structure: 1. DIY on an open-source compiler/interpreter of your choice. 2. Write your own compiler/interpreter. 3. Get the change into Haskell''. If the Haskell'' procedure is like the Haskell' procedure, you'll have to do 1 or 2 before you do 3. It's possible that you will convince someone that your syntax changes are worth doing, and that this person will do step 1 or step 2 for you, but I don't think so. I haven't done the research myself, but I think if you look at the source control logs for Your Favorite Haskell Compiler/interpreter and the HCAR, you will find very few commits/projects devoted to syntax. I think this is because Haskellers are much more interested in semantics. Afaiu the whole concept of type classes arose because of the desire to avoid having to think up different names for related functions and MPTCs were suggested by the syntax for single parameter TCs (though I can't remember the reference where I think I remember reading this latter point). Proposing changes that break existing code or segment the Haskell code base just doesn't seem like a win. Since all syntactic and many semantic changes necessarily break existing code or segment the code base this would seem to imply that the language should not be changed at all or that everything must be backwards compatible, so that we have to drag the Achilles heel of original mistakes around for all eternity. I'd have thought a solution would be to just use a tool to automatically convert existing code to whatever new syntax is found to be better, thus allowing the language to be gradually perfected as more and more issues are brought to light. Still I agree with you that a more sensible approach in terms of someone like me writing an editor is simply for me to take Haskell as an inspiration and incorporate my ideas in it so that any changes can later be seen in relation to a (hopefully facilitated and enjoyable) programming experience rather than trying to share my ideas piecemeal and insufficiently contextualized as they arise. Thanks to all who replied, Brian. -- Logic empowers us and Love gives us purpose. Yet still phantoms restless for eras long past, congealed in the present in unthought forms, strive mightily unseen to destroy us. http://www.metamilk.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Automatic fixity allocation for symbolic operators
Hi - I'm wondering if it is possible to construct a methodical procedure to assign a fixity to symbolic operators so that we could get rid of the need for user defined fixites. User defined fixities are an enormous problem for an interactive editor, because it is not possible to construct a parse tree of some code if you don't know what the fixities are, and an editor must be able to do something useful with a code fragment without having to look inside other modules (because the other modules may not yet have even been written!). Also, the programmer or reader of code needs to be able to understand each code fragment independently as well. From the Haskell98 report, the Prelude defines: infixr 9 ., !! infixr 8 ^, ^^, ** infixl 7 *, /, `quot`, `rem`, `div`, `mod` infixl 6 +, - infixr 5 :, ++ infix 4 ==, /=, , =, =, infixr 3 infixr 2 || infixl 1 , = infixr 1 = infixr 0 $, $!, `seq` Suppose we ignore the varid operators and just consider the symbolic ops. What I'm trying to find is a systematic way to assign fixities to all other possible sequences of symbol characters that is consistent with what we've already got in the Prelude. As a first step, we could say that mirrored operators must share the same precedence ie: == For associativity, we could assign each character an associativity weight: -1 left associative 0neutral 1right associative and say that the associativity is simply the sign of the sum of the associativity weights of the characters thus: -1 =0 1 =0 + 1 + 1ie infixr Note that I don't care about non-associative ops since the non-associativity of something should be a question for the type checker not the parser imho - ideally we should be able to create a parse tree for any possible operator expression. To form the precedence, we could assign each character a precedence value eg: 9 .! 8^ 7*/ 6+- 5: 4= 3 2| 1 0$ A first attempt might be to say that the precedence is simply the decimal expansion of the precedence values eg = has precedence 1.14 and $! has precedence 0.9. However, as noted above, mirrored ops must share the same precedence so an alternative is to create some ordering of characters such that when the set of characters in an operator is sorted according to this ordering, the decimal expansion of the precedence digits will give the same relative ordering for operator precedences as the Prelude. For example, using $ | + - * / ^ . ! : = as the ordering, we'd get: infixr 9 .!! 99.9 infixr 8 ^, ^^, **8 8.87.7 infixl 7 *, /,77 infixl 6 +, -6 6 infixr 5 : , ++ 56.6 infix 4 ==, /=, , =, =, 4.4 7.4 11.41.41 infixr 3 3.3 infixr 2 ||2.2 infixl 1 , =1.11.14 infixr 1 =1.14 infixr 0 $, $!00.9 Although most existing ops get a similar precedence (eg ^ ^^ and ** are all still in the same group relative to the other ops despite the fact that within the group there is now an ordering) the main problem seems to be that = = get precedences that bind too loosely and /= is totally wrong. This problem aside, the above algorithm would give sensible precedences for such things as: :: 5.1 +*6.116.11 where the use of neutralizes the associativity contribution of or respectively (since (-1) + 1 == 0), giving us the intuitive associativity we'd expect from the interesting character in the middle. (The problem of /= getting 7.4 could be solved by putting / after = in the order, to get 4.7, but unfortunately this would mean that since must be before =, would be before / so / would get the wrong precedence compared to *) Another issue is that there is no assignment of associativity weights such that * is infixl but ** is infixr (ditto + and ++) so perhaps we'd need to associate each character with an associativity function. Similar to precedences, we then define an associativity ordering and let the resulting associativity be the sign of the composition of the sorted functions applied to 1 eg: ^ const (-1) * \x - x * (-1) = id const (-1) (+1) (+ (-1)) Then *(\x - x * (-1)) 1===-1 ie left ** (\x - x * (-1)) . (\x - x * (-1)) $ 1 === +1 ie right = = (+ (-1)) . (+ (-1)) . id$ 1 === -1 *-- remember ordering
Re: [Haskell-cafe] Automatic fixity allocation for symbolic operators
Brian Hulley wrote: infixr 9 .!! 99.9 infixr 8 ^, ^^, **8 8.87.7 infixl 7 *, /,77 infixl 6 +, -6 6 infixr 5 : , ++ 56.6 infix 4 ==, /=, , =, =, 4.4 7.4 11.41.41 infixr 3 3.3 infixr 2 ||2.2 infixl 1 , =1.11.14 infixr 1 =1.14 infixr 0 $, $!00.9 Ouch. Really, the first priority in the language should be human readability. Looking up a fixity isn't that hard, but remembering a rule like this is pretty awful. You also restrict the freedom of library designers for no good reason. Precedences aren't usually random ... As far as editors go I have little sympathy. I also see nothing wrong with forcing a coder to have at least a module stub that defines its interface and the operator precedences, to make the parsing work reliably. You'll have to deal with the case where parsing fails anyway, and it shouldn't be too hard between failures due to unsufficient information (which shouldn't be tagged as errors, but maybe give some other indication) and real errors. Bertram ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re: [Haskell-cafe] Automatic fixity allocation for symbolic operators
Perhaps the editor could assume a default precedence when the user-defined precedence is not yet available. Preferably, the editor would also somehow yell at the user to indicate that it is making such an assumption. I think it's unreasonable to tie programmers' hands for the sake of off-loading rather trivial tasks to editors. Nick On 10/14/06, Bertram Felgenhauer [EMAIL PROTECTED] wrote: Brian Hulley wrote: infixr 9 .!! 99.9 infixr 8 ^, ^^, **8 8.87.7 infixl 7 *, /,77 infixl 6 +, -6 6 infixr 5 : , ++ 56.6 infix 4 ==, /=, , =, =, 4.4 7.4 11.41.41 infixr 3 3.3 infixr 2 ||2.2 infixl 1 , =1.11.14 infixr 1 =1.14 infixr 0 $, $!00.9 Ouch. Really, the first priority in the language should be human readability. Looking up a fixity isn't that hard, but remembering a rule like this is pretty awful. You also restrict the freedom of library designers for no good reason. Precedences aren't usually random ... As far as editors go I have little sympathy. I also see nothing wrong with forcing a coder to have at least a module stub that defines its interface and the operator precedences, to make the parsing work reliably. You'll have to deal with the case where parsing fails anyway, and it shouldn't be too hard between failures due to unsufficient information (which shouldn't be tagged as errors, but maybe give some other indication) and real errors. Bertram ___ 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
Re: Re: [Haskell-cafe] Automatic fixity allocation for symbolic operators
On 10/14/06, Nicolas Frisby [EMAIL PROTECTED] wrote: Perhaps the editor could assume a default precedence when the user-defined precedence is not yet available. Preferably, the editor would also somehow yell at the user to indicate that it is making such an assumption. Perhaps it could even assume the fixity that is specified in the prelude for operators without fixity declarations, thus behaving exactly like the compiler would: Any operator lacking a fixity declaration is assumed to be infixl 9 (4.4.2) I agree that changing the language in such an unintuitive way - breaking existing code in the process - to suit an editor is counterproductive and ridiculous. /g ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Automatic fixity allocation for symbolic operators
On 10/14/06, Brian Hulley [EMAIL PROTECTED] wrote: User defined fixities are an enormous problem for an interactive editor This is the second or third time you've proposed a language change based on the editor you're writing. I don't think this is a fruitful avenue. There are three ways to change Haskell's lexical structure: 1. DIY on an open-source compiler/interpreter of your choice. 2. Write your own compiler/interpreter. 3. Get the change into Haskell''. If the Haskell'' procedure is like the Haskell' procedure, you'll have to do 1 or 2 before you do 3. It's possible that you will convince someone that your syntax changes are worth doing, and that this person will do step 1 or step 2 for you, but I don't think so. I haven't done the research myself, but I think if you look at the source control logs for Your Favorite Haskell Compiler/interpreter and the HCAR, you will find very few commits/projects devoted to syntax. I think this is because Haskellers are much more interested in semantics. Proposing changes that break existing code or segment the Haskell code base just doesn't seem like a win. Jim ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe