On 13-3-2009 11:35, Invisible wrote:
> andrel wrote:
> 
>> Why not in (reverse) polish, no brackets at all
> 
> Fun thing:
> 
>   12+3*
>   123+*
> 
> These two expressions look different, but are guaranteed to produce the 
> same answer.
Until now I had never realized that even reversed polish could be 
interpreted in more than one way. Your interpretation might be 
consistent,though that might require some checking. I would say that the 
two expressions reduce to 9 and 5. Note that if you insist that 
parameters are eaten from left to right subexpressions are not substrings.

Post a reply to this message

>> Fun thing:
>>
>>   12+3*
>>   123+*
>>
>> These two expressions look different, but are guaranteed to produce 
>> the same answer.
> 
> I thought that 12+3* means (1+2)*3 and 123+* means (2+3)*1 ???

I stand corrected.

I was pretty certain I remember there being a way to modify the exact 
order in which operations are performed yet always arrive at the same 
answer. However, I am currently unable to construct a valid example. 
Perhaps my memory is off...

Post a reply to this message

Invisible wrote:

> I was pretty certain I remember there being a way to modify the exact 
> order in which operations are performed yet always arrive at the same 
> answer. However, I am currently unable to construct a valid example. 
> Perhaps my memory is off...

How about these?

ABC+*DE+*F*
ABC+DE+**F*

Post a reply to this message

> How about these?
> 
> ABC+*DE+*F*
> ABC+DE+**F*

Yes they seem the same to me...

Post a reply to this message

scott wrote:
>> How about these?
>>
>> ABC+*DE+*F*
>> ABC+DE+**F*
> 
> Yes they seem the same to me...

I'M NOT CRAZY! 6_6

Oh, wait...

Post a reply to this message

On 13-3-2009 11:59, Invisible wrote:
> Invisible wrote:
> 
>> I was pretty certain I remember there being a way to modify the exact 
>> order in which operations are performed yet always arrive at the same 
>> answer. However, I am currently unable to construct a valid example. 
>> Perhaps my memory is off...
> 
> How about these?
> 
> ABC+*DE+*F*
> ABC+DE+**F*

such rewriting indeed works for any operator $ that satisfies 
(A$B)$C=A$(B$C) i.e. AB$C$=ABC$$ in RPN.
BTW Why did you choose this example with such a lot or irrelevant detail?

Post a reply to this message

>> So... maybe when printing out any given subtree, I make the print 
>> function take the precedence of the parent node as an extra argument? 
> 
> I'd to print the parens (if needed) in the parent call before recursing.

It's easier to do it the other way around. The function only has to care 
what the precedence of the current operator is before recursing. The 
recursive call can decide what to do about it.

Using this technique, I was also able to "hack" in support for 
associativity. For example, in Haskell function application has the 
highest possible precedence, and left associativity (because of curried 
functions). So, when recursing from a function application call, it 
tells the left subtree that the parent's precedence was 8, but it tells 
the right subtree that the parent's precedence was 9.

The result is that if you have

        $
       / \
      /   \
     $     $
    / \   / \
   A   B C   D

it prints out as "A B (C D)", which is correct.

(Although, needless to say, I spent a day confusing myself with what 
"higher" precedence means, and mixing up left and right associativity. 
It probably doesn't help that the function type constructor is 
right-associative because the function application operator is 
left-associative...)

What can I say? Apparently I'm not very smart.

Post a reply to this message

>> How about these?
>>
>> ABC+*DE+*F*
>> ABC+DE+**F*
> 
> such rewriting indeed works for any operator $ that satisfies 
> (A$B)$C=A$(B$C) i.e. AB$C$=ABC$$ in RPN.

So... any associative operation then?

A quick check confirms that

   ABC*-DE*-F- ==> (A-(B*C))-(D*E)-F   ==> A - BC - DE - F
   ABC*DE*--F- ==> (A-((B*C)-(D*E)))-F ==> A - BC + DE - F

which aren't the same.

> BTW Why did you choose this example with such a lot or irrelevant detail?

My brain is like mush this morning. This was the first correct example I 
could find. It's about 10 years ago that I discovered this effect, so I 
wasn't even sure if I was remembering right!

(Currently attempting to build a Haskell parser, printer and type 
interence engine. This stuff is surprisingly non-trivial. Having an 
argument about RPN in parallel with these activities is exceeding my 
mental capacity!)

Post a reply to this message

On 13-3-2009 12:24, Invisible wrote:
>>> How about these?
>>>
>>> ABC+*DE+*F*
>>> ABC+DE+**F*
>>
>> such rewriting indeed works for any operator $ that satisfies 
>> (A$B)$C=A$(B$C) i.e. AB$C$=ABC$$ in RPN.
> 
> So... any associative operation then?

yes. because associativity is the property that you are using in the 
reordering.

> A quick check confirms that
> 
>   ABC*-DE*-F- ==> (A-(B*C))-(D*E)-F   ==> A - BC - DE - F
>   ABC*DE*--F- ==> (A-((B*C)-(D*E)))-F ==> A - BC + DE - F
> 
> which aren't the same.
> 
>> BTW Why did you choose this example with such a lot or irrelevant detail?
> 
> My brain is like mush this morning. This was the first correct example I 
> could find. It's about 10 years ago that I discovered this effect, so I 
> wasn't even sure if I was remembering right!

I think that as soon as you find an example you try to reduce it to the 
bare essentials and post that. The same actually as when posting a bug.

> (Currently attempting to build a Haskell parser, printer and type 
> interence engine. 

One word: why?

> This stuff is surprisingly non-trivial. Having an 
> argument about RPN in parallel with these activities is exceeding my 
> mental capacity!)

Post a reply to this message

>> So... any associative operation then?
> 
> yes. because associativity is the property that you are using in the 
> reordering.

I guess most people just instinctively "know" that addition and 
multiplication are associative (not to mention commutative) without 
thinking about it too deeply.

>>> BTW Why did you choose this example with such a lot or irrelevant 
>>> detail?
>>
>> My brain is like mush this morning. This was the first correct example 
>> I could find. It's about 10 years ago that I discovered this effect, 
>> so I wasn't even sure if I was remembering right!
> 
> I think that as soon as you find an example you try to reduce it to the 
> bare essentials and post that. The same actually as when posting a bug.

Ooo, 2 extra operations. Big deal.

>> (Currently attempting to build a Haskell parser, printer and type 
>> interence engine. 
> 
> One word: why?

Two words: why not?

Post a reply to this message