4 ms·

Ask HN: Proof, order of operations and functional languages

3 points by nopassrecover 17y ago

Hi, I am wondering how to prove (or possibly disprove if I've missed something) that these two approaches are equally comprehensive. Imagine that we have three functions (someFunc, someFunc2 and someFunc3) and these are each a substitute for a mathematical operator (e.g. * , +, -, /). Now I have code like this: someFunc(w, someFunc2(x, someFunc3(y, z)). If I perform all the permutations of switching someFunc, someFunc2 and someFunc3 with a mathematical operator (e.g. *, +, -, /) will I have performed all of the same equations as can be generated using mathematical order of operations (e.g. w someFunc x someFunc2 y someFunc3 z)? Is there a proof for this or some area of research/theory that is relevant? I feel like I'm missing something basic but my research hasn't yielded anything, perhaps because this is so basic.

vii 17y ago
Clearly these things are quite different. For example, w - x * y + z is w - (x * y) + z There is no way to write this as someFunc(w, someFunc2(x, someFunc3(y, z)) where the someFuncs are one of *,+,-,/ -- you would have to use someFunc(w,someFunc3(someFunc2(x,y),z)). Unless you mean that the x,y,w,z can be freely permuted?
- nopassrecover 17y ago
  Er I hadn't considered that. I will generate all possible substitutions of someFunc with (+,*,-,/) and all possible substitutions of w,x,y,z with the set of arguments.
ajuc 17y ago
w sf x sf2 y sf3 z is equivalent to sf3(sf2(sf(w,x),y),z) assuming left to right evaluation (and equal priorities of operations). Trees of operations: w sf x sf2 y sf3 z w-sf1-sf2-sf3 | | | x y z sf(w,sf2(x,sf3(y,z))) sf1-sf2-sf3-z | | | w x y You can permutate w,x,y,z in these trees - I was sure this will give the same expressions, but now I'm not. Interesting question. Edit: oh, so you wanted to permutate functions, not arguments. Then it won't give the same expressions.
- nopassrecover 17y ago
  As I just commented in another comment I will generate all possible substitutions of someFunc with (+,*,-,/) and all possible substitutions of w,x,y,z with the set of arguments. Now what I am trying to work out is that I am not assuming equal priorities of operations for w sf x sf2 y sf3 z. I see you've reoganised the nested approach, would this still satisfy?
ajuc 17y ago
I've tried version with 3 arguments (x,y,z) and 2 functions (+,/), and these two aproaches are not equivalent. For example: /(x,+(y,z)) has no equivalent expression that can be made from x f1 y f2 z if you permutate arguments or substitute functions (f1=/ f2 = +) or (f2=+ f1=/) because / binds stronger than +.
- nopassrecover 17y ago
  Thanks for that :-) Now to find out what this kind of theory is called and work out how to create equivalence :-)

3 points by nopassrecover 17y ago

vii 17y ago

Clearly these things are quite different. For example, w - x * y + z is w - (x * y) + z There is no way to write this as someFunc(w, someFunc2(x, someFunc3(y, z)) where the someFuncs are one of *,+,-,/ -- you would have to use someFunc(w,someFunc3(someFunc2(x,y),z)). Unless you mean that the x,y,w,z can be freely permuted?

nopassrecover 17y ago
Er I hadn't considered that. I will generate all possible substitutions of someFunc with (+,*,-,/) and all possible substitutions of w,x,y,z with the set of arguments.

ajuc 17y ago

w sf x sf2 y sf3 z is equivalent to sf3(sf2(sf(w,x),y),z) assuming left to right evaluation (and equal priorities of operations). Trees of operations: w sf x sf2 y sf3 z w-sf1-sf2-sf3 | | | x y z sf(w,sf2(x,sf3(y,z))) sf1-sf2-sf3-z | | | w x y You can permutate w,x,y,z in these trees - I was sure this will give the same expressions, but now I'm not. Interesting question. Edit: oh, so you wanted to permutate functions, not arguments. Then it won't give the same expressions.

nopassrecover 17y ago
As I just commented in another comment I will generate all possible substitutions of someFunc with (+,*,-,/) and all possible substitutions of w,x,y,z with the set of arguments. Now what I am trying to work out is that I am not assuming equal priorities of operations for w sf x sf2 y sf3 z. I see you've reoganised the nested approach, would this still satisfy?

ajuc 17y ago

I've tried version with 3 arguments (x,y,z) and 2 functions (+,/), and these two aproaches are not equivalent. For example: /(x,+(y,z)) has no equivalent expression that can be made from x f1 y f2 z if you permutate arguments or substitute functions (f1=/ f2 = +) or (f2=+ f1=/) because / binds stronger than +.

nopassrecover 17y ago
Thanks for that :-) Now to find out what this kind of theory is called and work out how to create equivalence :-)