Unintuitive operator precedence

[p-e-w]

The code

let a = {x: 1}; in abs a.x

gives ERROR: abs({x:1}): domain error. The reason is that abs a.x is actually interpreted as (abs a).x. Similarly (and contrary to what I claimed in #48!), f a[0] appears to be equivalent to (f a)[0] rather than f(a[0]), although this is often hard to notice because of Curv's array nature.

I find this behavior highly unintuitive. The main reason is that the syntax itself already suggests that a and x (being joined together by a period) are bound more closely than abs and a (being separated by a space). I have been bitten by this issue in many forms; indeed, almost every time I was confused about what some Curv code did the problem came down to precedence.

Another confusing example is

move cross(a, b) cube

which one might expect to translate a cube by the cross product of a and b (since in every mainstream programming language, a function call f(a,b) forms a syntactic unit). Instead, it gives an error, because it attempts to pass the function cross as the argument to move, so move (cross(a, b)) cube is needed instead.

Such (apparently) ambiguous precedence rules are typical of research-associated languages like Haskell and OCaml. I have always found such languages to be very difficult to parse mentally. Lisp is on the opposite end of the spectrum, where everything is bracketed so there is never any question about precedence, at the expense of increased verbosity. Scala shows a nice balance between the two extremes.

[doug-moen]

If you put parentheses around the a in your first two examples, and eliminate spaces, you get:

   abs(a).x
   f(a)[0]

and then the operator precedence rules can be seen to be the same as in C, Python, Javascript. Probably you find this behaviour intuitive?

White space has no syntactic meaning, other than to separate tokens, which again is the same as C and Javascript. So these are equivalent:

   abs (a).x
   f (a)[0]

In Curv, parentheses are used for grouping, they aren't part of function call syntax. So the parentheses in these examples can be dropped, and you get this:

   abs a.x
   f a[0]

The problem here is that the white space is interpreted by humans as an indication of how the subexpressions are grouped, but according to the grammar, the subexpressions are not grouped that way. So, for good coding style, it is better to write these expressions like this:

   abs a .x
   f a [0]

Or parenthesize the a and drop the spaces.

A related problem occurs, in every programming language, if you use inconsistent indentation that doesn't correspond to the actual hierarchical structure of the program.

I have thought about creating an alternative grammar for Curv that uses significant whitespace. The benefit is that your whitespace and indentation cannot be out of sync with the hierarchical structure of your code. That's why people like Python. With significant whitespace, the following expressions will group differently:

   a+b * c          == (a+b)*c
   a + b*c          == a+(b*c)
   abs a.x          == abs(a.x)
   abs(a) .x        == (abs(a)).x

[doug-moen]

move cross(a, b) cube

is another example where the spacing doesn't match the syntax. The correct coding style for this syntax is

move cross (a,b) cube

which, syntactically, is a call to a curried function move with 3 arguments. This is different from the intended code, which is:

move (cross(a,b)) cube

A possible solution to this problem is to issue a warning message when the spacing in an expression does not match the parse tree. So, we would issue warnings for expressions like these:

abs a.x
move cross(a, b) cube
sin -1

For example:

WARNING: Misleading syntax. Perhaps you meant one of the following:
    abs a .x
    abs (a.x)

The C++ compilers I use have analogous warnings, eg for "misleading indentation", and for writing if(x=y) when you might have meant if(x==y).

[p-e-w]

Thank you for the detailed response. I do understand most of the precedence rules now, but unfortunately, that doesn't make them any more intuitive. The experience of working with other languages creates some strong expectations for how things "should work" that are hard to shake off...

The suggestion to write

   abs a .x
   f a [0]

looks alien when coming from any of the top 10 languages in use today. Much more familiar would be

   (abs a).x
   (f a)[0]

I do like the idea to improve the compiler with warnings if such "visually ambiguous" expressions are encountered. But is it really out of the question to increase the precedence of field access and indexing? You can always get the "old" behavior back by using parentheses.

[doug-moen]

In a "top 10" programming language, function call is an n-ary operation:

f(arg1, arg2, ...)

The parentheses are part of the syntax. In Curv, function call is a binary operator, written as juxtaposition:

f x

Since any subexpression can be parenthesized, you can also write f(x), or (f)x, or (f)(x), but the parentheses in these cases are optional.

The argument position of a function call is any "primary expression". For example:

42
identifier
(parenthesized subexpression)
[a,b,c] -- a list
(a,b,c) -- also a list
{a: 1, b: 2} -- a record

You said: "Is it really out of the question to increase the precedence of field access and indexing?"

What is indexing? The following are two examples of the juxtaposition operator:

min[a,b,c]   // compute the minimum of 3 numbers
matrix[i,j]  // the element at row i, column j of matrix

What I think you are asking for is that these operations, with no spaces:

a.b
a[b]

have higher precedence than juxtaposition with a space:

f x

so that

f a.b     parses as     f(a.b)
f a[b]    parses as     f(a[b])

[doug-moen]

It turns out that Ruby has white-space-sensitive expression parsing, which I think is similar to what is being discussed here for Curv.

a + b is interpreted as a+b (Here a is a local variable) a +b is interpreted as a(+b) (Here a is a method)

[s-ol]

It turns out that Ruby has white-space-sensitive expression parsing, which I think is similar to what is being discussed here for Curv.

a + b is interpreted as a+b (Here a is a local variable) a +b is interpreted as a(+b) (Here a is a method)

in Moonscript there is a related gotcha with the - operator, which depending on spacing is either unary (-5, method -variable) or binary (3 - 5, a - b), documented here. Since moonscript takes most of its syntax from Coffeescript (which leans on ruby) I assume they all share this gotcha.

[doug-moen]

It turns out that Lua does not always require a function argument to be parenthesized. These function calls are legal:

print "hello world" <-> print("hello world") f{x=10, y=20} <-> f({x=10, y=20})

Which is just like Curv.

However, Lua does not permit a bare identifier or numeric literal to be used as a function argument, unlike Curv. Those need to be parenthesized.

I guess that if Curv syntax were restricted so that you are required to type abs(a) instead of abs a, then the ambiguity problem associated with abs a.x would go away. Similarly, if you have to type sin(1) instead of sin 1, then there is no expectation that sin -1 will work.

The downside is that curried functions get noisier. Current code:

map f list = [for (x in list) f x];

New version:

map(f)(list) = [for (x in list) f(x)];

With Lua-like syntax, Curv looks more like a top-ten programming language, but you have to type more parentheses than at present.

White-space-sensitive expression parsing would reduce the number of parentheses that you need to type, compared with the current syntax. Eg, you can write abs r.x instead of abs(r.x).

[p-e-w]

It seems that at the core of the problem is a semantic ambiguity in Curv. The expression

a b

where b is a list of integers, can mean either "the value of the function a with argument b" or "the elements of list a whose indices are given by b", and there is no way to know which meaning applies without knowing the type of a.

But the intuitively correct parsing, IMO, would be that the second meaning (indexing) implies a higher precedence of the juxtaposition operator than the first (function call). I realize this is likely impossible to achieve with the existing infrastructure because parsers usually don't do type inference, and after parsing it is already too late because the AST depends on operator precedence.

How about turning . into a top-level binary operator with high precedence and using it for indexing? That is

a b

parses as

juxtaposition(a, b)

while

a . b

parses as

joint(a, b)

with joint having a higher precedence than juxtaposition. The syntax for indexing would then be

list.[0]

to get the first element, while the syntax for record field access remains as it is, and everything remains whitespace-independent, which I believe is a valuable property to preserve. No compiler warnings need to be introduced. Now we have

abs a.x  <=>  abs (a.x)
f a.[0]  <=>  f (a.[0])

as desired, for the price of a small syntax change.

Note that while using a period for indexing is not standard among mainstream programming languages, there is a precedent in Rust's tuple indexing, i.e. tuple.0.

[doug-moen]

1. There is a problem with giving function call a lower precedence than field selection and indexing.

The reason that they all have the same precedence in top-ten programming languages is so that you can chain together a series of field selections and function calls, without parentheses piling up at the left side of the expression. For example,

a(x).b(y).c(z)

instead of ((a(x)).b(y)).c(z) or ((a x).b y).c z.

This property is also useful in Curv. These chains occur in a few contexts when using shape operators from the standard library:

smooth d .union [shape1, shape2]
regular_polygon n .mitred d
prism 5 .mitred {d: 2, h: 3}

See also lib.blend. Longer chains might be needed with future libraries, if a more "object oriented" style emerges.

Notice the white space between each element of the chain: that's my standard coding style when writing shape expressions. It is consistent with writing a space between each element of a curried function call like f a b.

2. The problem with inventing a new syntax for indexing is that it creates a usability problem. New users will not be familiar with the syntax, and it will be an irritant for people who switch between Curv and other languages.

I ran experiments in Curv using an explicit indexing operator. I tested a.[i] and a'i, converting all of my code to each syntax and trying to use the syntax for a while.

a'0         <==>   a[0]
a'i         <==>   a[i]
a'[X,Y,Z]   <==>   a[[X,Y,Z]]
m'i'j       <==>   m[i,j]

In the end, I couldn't get used to it, even though I found a'i to be terser and more elegant than a[i]. So that's when I settled on the current syntax.

3. We can combine my goal, keeping function call, field selection and indexing at equal precedence levels, so that you can chain them, with @p-e-w's goal, by using a grammar with two sets of call, select and index operators at two different precedence levels.

Here's an excerpt from the current grammar:

unary ::= power | '-' unary | '+' unary | '!' unary | 'var' unary
power ::= postfix | postfix '^' unary
postfix ::= primary | postfix primary | postfix '.' identifier
primary ::= identifier | numeral | string | '(' list ')' | '[' list ']' | '{' list '}'

Here's a modification, with two levels of postfix ("tight" and "loose"). A "loose postfix expression" requires white space between each component of the chain. A "tight postfix expression" has no white space between components, and requires function call arguments to be parenthesized, bracketed or braced.

power ::= Lpostfix | Lpostfix '^' unary
Lpostfix ::= Tpostfix | Lpostfix Tpostfix | Lpostfix .identifier
Tpostfix ::= primary | Tpostfix(list) | Tpostfix[list] | Tpostfix{list} | Tpostfix.identifier

This is a small change to the grammar, easily implemented.

I tried to find examples of existing code that could be simplified using this change. There's not a huge impact, but I found a few.

is_vec2 x = is_list x && count x == 2 && is_num(x[0]) && is_num(x[1]);
is_vec2 x = is_list x && count x == 2 && is_num x[0] && is_num x[1];

for (i in indices(a[0]))
for (i in indices a[0])

assert (defined(shape.dist) && is_fun(shape.dist));
assert (defined shape.dist && is_fun shape.dist);

normalize(perp(b-a))
normalize perp(b-a)

n1 = normalize(cross(v1-v3,v2-v3));
n1 = normalize cross(v1-v3,v2-v3);

abs(dot(p[[X,Y,Z]], v0))
abs dot(p[[X,Y,Z]], v0)

size(shapes[i])[X]
size shapes[i] [X]

Is this a good change? I'm still thinking about it.

[doug-moen]

For the record, @p-e-w said "if Curv restricted arguments to lists those concerns would mostly disappear". This suggests that function arguments should always be parenthesized, which eliminates the visual ambiguity problem.

I haven't closed this bug yet. I've got 3 alternative ideas for dealing with the issue (all of them are discussed above).

1. Warning messages for misleading expression syntax, when the whitespace between tokens suggests a different grouping than what the grammar provides.
2. White-space sensitive expression parsing. f a.b parses as f(a.b), while f a .b parses as f(a).b.
3. Function arguments are parenthesized. I would still allow f[a,b] and f{a:1,b:2}, since there is no visual ambiguity, and to avoid the pain of writing f([a,b]) and f({a:1,b:2}). Curried function calls become awkward -- f(a)(b)(c) -- unless we adopt the syntax used by Reason, a functional programming language that looks like Javascript, where f(a,b,c) is a shorthand for f(a)(b)(c).

[p-e-w]

@doug-moen

Looking at those three options, I would go with number 3: Arguments always have to be surrounded by parentheses, either (), [], or {}. This turns a function and its arguments into an unambiguous syntactic unit, which will be immediately familiar to users of most mainstream programming languages.

Currying would still work by means of the >> operator. f(a)(b)(c) is in most cases more clearly expressed as c >> (b >> f(a)). The brackets around b >> f(a) are a bit unfortunate, but currying with more than two arguments is ugly anyway.

Whatever you choose to do, please do not make Curv whitespace-sensitive... :worried: :smiley:

[lf94]

Whatever you choose to do, please do not make Curv whitespace-sensitive

This 10000x :laughing:

[doug-moen]

In Curv 0.5, I've implemented @p-e-w 's suggested syntax for array indexing, which is now a.[i]. The old syntax still works, but is deprecated. Of course, this in itself doesn't fix the problem.

Fixing the problem by changing operator precedence is a tar pit.

• It fixes some of the ambiguous syntax situations described above, but not all of them.
• If dot has high precedence than function-call, then it eliminates one common mistake, at the cost of eliminating a nice property of the current syntax, which is the ability to chain a sequence of function call and indexing operations without having parentheses pile up at the start of the expression. I use these chains frequently when writing smooth r .union [a, b] expressions.
• It's a disruptive change. Previous syntax changes have been introduced by deprecating old syntax while adding new syntax.
• And it doesn't fix the real underlying issue, since it will always be possible to write expressions where the grouping as suggested by white space is different from the grouping as defined by operator precedence.

To get out of this tar pit, I'm adding warning messages about "ambiguous syntax", where the use of white space indicates a different grouping than what the precedence rules prescribe.

[doug-moen]

I'm not ruling out the idea of making radical syntax changes to Curv. Just not today. For the moment, these warning messages should help users avoid a common pitfall.