I fairly quickly figured out that the grammar is something like E ::= "[]" | "[" E "]" | "-" E | "E E", and that eval([E]) = 2^eval(E) (and eval(-E) = -eval(E)), and then went down the rabbit hole of trying to come up with some feval(E1 E2) = f(eval(E1), eval(E2)) for juxtaposition, and thinking about whether it’s left or right associative. I was also thinking that maybe it’s n-ary rather than binary so that associativity does not matter.
Anyway, I think where I went wrong is that I decided that [E] is a unary operator by itself, and did not reconsider this. So the lesson is… don’t just assume the simplest possible AST structure implied by the grammar?
I did exactly the same thing. I’m curious, is there a way to systematically solve problems of this type? E.g. if I made an assumption that this is an algebra with one unary and one binary operation, can that be strictly refuted just from the examples given?
Unfortunately no, I don’t think any contradictions can be derived from the examples given in the post if we assume -E and [E] unary, and E E binary operators. Here are some example assignments for these operators that satisfy (AFAICT) the examples from the post (assuming left associativity for juxtaposition, and that the precedence of - is lower, so that -E E is interpreted as -(E E) in the last example):
I guess the reasoning for why the solution given in the post is more “valid” than this one is “something something Occam’s razor” or that it is “more elegant” (whatever “elegant” means), but if someone can make a more precise argument I would be interested to hear. (In particular, in my mind Occam’s razor is something to do with empiricism, while what we are doing here is pure logic, so not sure how it exactly applies?)
Kolmogorov complexity? Your solution takes more bits to specify than the one in the solution (at least if you’ve already defined a standard library with concepts like primes)?
Yep, that “standard library” part sure seems problematic, I am not sure if an algorithm for listing primes is shorter than just the above lookup table.
I don’t think you could refute it. I believe you could construct a binary polynomial function that gives the correct answer to every example.
For example it is difficult to reconcile the cases of 3, 12, and 19 using a reasonable-looking function, but you could solve all three cases by defining E E as the left-associative binary operation
If you give it the up-front caveat “this can represent all rational numbers and at least some algebraic irrationals”, I think that rules out the polynomial appromixation approach, since you can’t give arbitrary arguments and get intermediate values by continuity. But I’m not certain of that.
I fairly quickly figured out that the grammar is something like
E ::= "[]" | "[" E "]" | "-" E | "E E", and thateval([E]) = 2^eval(E)(andeval(-E) = -eval(E)), and then went down the rabbit hole of trying to come up with somefeval(E1 E2) = f(eval(E1), eval(E2))for juxtaposition, and thinking about whether it’s left or right associative. I was also thinking that maybe it’s n-ary rather than binary so that associativity does not matter.Anyway, I think where I went wrong is that I decided that
[E]is a unary operator by itself, and did not reconsider this. So the lesson is… don’t just assume the simplest possible AST structure implied by the grammar?I did exactly the same thing. I’m curious, is there a way to systematically solve problems of this type? E.g. if I made an assumption that this is an algebra with one unary and one binary operation, can that be strictly refuted just from the examples given?
Unfortunately no, I don’t think any contradictions can be derived from the examples given in the post if we assume
-Eand[E]unary, andE Ebinary operators. Here are some example assignments for these operators that satisfy (AFAICT) the examples from the post (assuming left associativity for juxtaposition, and that the precedence of-is lower, so that-E Eis interpreted as-(E E)in the last example):Definitions for
[E]:Definitions for
E E:Definitions for
-E:I guess the reasoning for why the solution given in the post is more “valid” than this one is “something something Occam’s razor” or that it is “more elegant” (whatever “elegant” means), but if someone can make a more precise argument I would be interested to hear. (In particular, in my mind Occam’s razor is something to do with empiricism, while what we are doing here is pure logic, so not sure how it exactly applies?)
Kolmogorov complexity? Your solution takes more bits to specify than the one in the solution (at least if you’ve already defined a standard library with concepts like primes)?
Yep, that “standard library” part sure seems problematic, I am not sure if an algorithm for listing primes is shorter than just the above lookup table.
I don’t think you could refute it. I believe you could construct a binary polynomial function that gives the correct answer to every example.
For example it is difficult to reconcile the cases of 3, 12, and 19 using a reasonable-looking function, but you could solve all three cases by defining
E Eas the left-associative binary operationIf you give it the up-front caveat “this can represent all rational numbers and at least some algebraic irrationals”, I think that rules out the polynomial appromixation approach, since you can’t give arbitrary arguments and get intermediate values by continuity. But I’m not certain of that.