[Versa] '-'

[Michael Olson]

Just wanted to send out an update on this.  I made pretty good progress  
last night.  What I accomplished is to break the expressions into  
different expressions based on type.  So you have a boolean-expression  
which is the results of all of the boolean operators, constants and a  
few other things.


Then, given the different expression types, I can define which are  
allowed as operands for all of our different operators and which are  
allowed as a top level query (ie DOT is not a top level query).

I have three small things left to do, the first is make sure that  
function arguments are getting allowing the correct arguments (should  
be anything), the second is to fix a shift reduce (see below) and the  
third is to verify that I have precedence set up correctly for some of  
the operators.

A couple of notes, variable-reference and function-call default to  
"list-expressions" as list expressions are the most general in the  
grammar.

I currently have the conversion functions in the grammar.  As an  
example, the grammar defines 'boolean(' query-expression ')' as a way  
to convert any expression into a boolean.  Without this, it would be  
impossible, in our grammar, to have a boolean expression that starts  
with a function call (as these are lists).  We can decide (assumiung we  
like this grammar) if we want to keep that.  It would not allow

$x + $y

as a query anywhere, you need to do

number($x) + $y


The shift reduce has to do with precedence in a chained traversal, given

all() - rdf:type -> . < 2 - 1-> *


Which is just a silly traversal but shows the point.  It can either be  
reduced into

(all() - rdf:type -> . < 2) - 1 -> *

Which is a traversal chain

or, it can be shifted into

all() - rdf:type -> (. < 2 - 1)  -> *

Which is invalid.

Mike








On Sep 26, 2005, at 7:50 PM, Michael Olson wrote:

>>>
>>> The solutions I currently see as possible are
>>> a)  double dash so all() -- rdf:type -> *
>>> b)  a new symbol for subtraction.  XPath did it with "div" I assume
>>> because of the same problems with the "/" path operator.  We could do
>>> "sub"
>>> c)  A symbol to start a traversal, something like # all() - rdf:type  
>>> ->
>>> *
>>> d) Reorder the bgen file so that the arc-start-expression always
>>> reduces first and live with the error.
>>
>> d) In effect using precedence.
>>
>> I actually think we want (d) in combination with parens to  
>> disambiguate.
>> See below.
>>
>>
>>> IMO
>>>
>>> a) +2
>>> b) +1
>>> c) -1
>>> d) -10
>>>
>>> I'm very opposed to "d" because down the road, someone may try to  
>>> clean
>>> up the grammar and all of the sudden everything breaks for no reason.
>>
>> We make the precedence rule explicit for this case, either using some
>> BisonGen feature (I'm not up to date on Bgen features), or by a simple
>> comment to warn people that the grammar is ordered that way for a
>> reason.
>>
>> More importantly, we should require parens in some ambiguous cases.   
>> The
>> essence of the problem is:
>>
>> $a - $b - $c -> *
>>
>> If you restrict the primary-expressions that are allowed as operands  
>> in
>> traversal expressions, you can eliminate this ambiguity.  In other
>> words, mandate parens and make the above illegal.  The user would have
>> to write:
>>
>> ($a - $b) - $c -> *
>>
>> or
>>
>> $a - ($b - $c) -> *
>>
>> or
>>
>> $a - ($b - $c -> *)
>>
>> This would require primary expression to be split up into two
>> non-terminals, one of which mandates the parens, and adding another
>> non-terminal which is a traversal expression with parens around it.   
>> It
>> would be fiddly, but I think it would be well worth it to avoid  
>> options
>> a through c.
>>
>
> Your example points out the biggest problem I have been running into,  
> variables and functions.
>
> Its easy to take all other use cases and separate them into  
> expressions by "what starts a traverse" and "what starts a  
> subtraction".
>
> You still run into a reduce/reduce conflict with $x - $y.
>
> Now, as you mention we can just order the bison correctly and state in  
> docs that "this always reduces to the start of a traversal".
>
> This means
> 1)  you cannot just have "$x - $y" as a query which is sad but not a  
> show stopper
> 2)  the precedence is not in the EBNF, but is implementation specific.  
>  If someone took the EBNF and put it through a LR(1) parser they would  
> get different results
> 3)  it is very prone to future errors by simple re-ording of the bison  
> file
> 4)  we would be going against what the bison manual itself says,  
> basically fix all reduce reduce conflicts as they are very bad.
>
> 2 & 3 are the biggies for me.  4 give me pause and 1, as I said, is  
> said but not major.
>
> I have not given up yet and plan on spending the evening trying to  
> resolve this, but as it currently stands, my vote is for a or b (or e  
> see below).  Probably b ( 'sub' is the subtraction operator) since  
> subtraction is a new feature in versa we would not be breaking  
> anything.
>
> One other solution I have come up with is typing of variables and  
> functions but I hesitate to bring this up in a mostly python  
> community.  It would look something like:
>
> The default type for a variable/function is list.  This would allow us  
> to then type all possible starting expressions for a traversal.  So
>
> $x - $y is always the start of a traversal as the type of $x is a list  
> and we can say (in short hand)
>
> traversal :== list '-' list '-' boolean
>
> Then, given a subtraction you would need to do
>
> (number)$x - $y
>
> I suppose we could go a step farther and say that the conversion  
> functions are a part of the grammar.  Then it would look like
>
> number($x) - $y
>
> Mike
>
>
>>
>> -- Uche Ogbuji                               Fourthought, Inc.
>> http://uche.ogbuji.net                    http://fourthought.com
>> http://copia.ogbuji.net                   http://4Suite.org
>> Articles: http://uche.ogbuji.net/tech/publications/
>>
>> _______________________________________________
>> Versa mailing list
>> Versa at lists.fourthought.com
>> http://lists.fourthought.com/mailman/listinfo/versa
>>
> ----------------------------------------------------------------------- 
> ------------------
> Mike Olson                                                Principal  
> Consultant
> mike.olson at fourthought.com                +1 720 253 4662
> Fourthought, Inc.                                       
> http://Fourthought.com
> PO Box 270590,                                       http://4Suite.org
> Louisville, CO 80027-5009, USA
> XML strategy, XML tools, knowledge management
>
> _______________________________________________
> Versa mailing list
> Versa at lists.fourthought.com
> http://lists.fourthought.com/mailman/listinfo/versa
>
------------------------------------------------------------------------ 
-----------------
Mike Olson                                                Principal  
Consultant
mike.olson at fourthought.com                +1 720 253 4662
Fourthought, Inc.                                       
http://Fourthought.com
PO Box 270590,                                       http://4Suite.org
Louisville, CO 80027-5009, USA
XML strategy, XML tools, knowledge management