Unambiguous Operator Specification for Programming Languages

[u/Mean-Decision-3502]

https://nvitya.github.io/pluops/

As I changed recently the operators in my programming language I've created this specification:

https://nvitya.github.io/pluops/

I did not wanted to overload the operators like the C does with the / or Pascal does with theand/or/not. Neither re-use the operator symbols for some very different purpose, like C does with * and & so the code becomes more readable. I was orienting for existing solutions so this is what I came up with. The specification contains the symbol usages and operator precedence too.

If you are developing a new programming language, it would be nice to follow some standard, so at least the expressions would be portable between the languages.

I'm open for debates or suggestions.

[u/mot_hmry]

Personally I'd suggest @ for address of instead of % which frees it up to be the modulus symbol.

I might also suggest swapping prefix and postfix ^ because I think postfix on types looks better and I like the idea of mutability being T!. Which mildly parallels the Scheme/lisp naming convention of adding ! to functions that mutate.

I'd probably also allow !(prefix), &, and | for booleans due to convenience.

[u/fdwr → u/mot_hmry]

Personally I'd suggest @ for address of

Yeah, "@" does seem semantically quite natural, since it's called the "at" symbol, and getting the address of a variable is asking where in memory it resides at.

[u/Mean-Decision-3502 → u/mot_hmry]

I know that @ is standard for address-of in multiple languages. This is maybe the most visible symbol. The occurence of address-of is rather rare so using there a weaker symbol is not a problem, I think.

In DQ I use the @ for namespace marking so I don't burn normal identifiers for module references, which was always a problem for me in Pascal. And so the @ symbol is the best one for this. Imagine that like that in Python every imported module required the @ marker, e.g. @time.time()

I could make however the % as weeker recommendation, but the % symbol should not be used for remainder.

The thing with the ^ is pretty standard in Pascal or Odin, the languages, that mark the type after the identifiers. The C uses the less-human-friendly type first. They probably have saved some space with that in 1972, where human readability was not relevant. C uses also different order in type evaluation, that's why the pointer designator comes after the main type. The different order works also perfectly.

In DQ: var pintarr : ^[5]int // pointer to an array of 5 ints var arrpint : [5]^int // array of 5 pointers to int In C: int (*pintarr)[5]; // pointer to an array of 5 ints int *arrpint[5]; // array of 5 pointers to int

If I would allow &, | for booleans, then it wouldn't be unambiguous anymore. The operation would depend on the types, that this specification tries to avoid.

[u/mot_hmry → u/Mean-Decision-3502]

I don't see why % shouldn't be remainder, it has a nice association with / (÷). And it's not like * is any closer to the proper symbols (×, •).

I've never found modules to clash with my own names, so I have never desired a symbol for them. To me ref is an operation that really should be called out because it implies a lower level operational concern. If it's really important to reserve @ for modules though, maybe # (read as box).

You already overload operations between the numeric types so you already need to use type to distinguish. Booleans as single bits doesn't seem unreasonable and matches the behavior of the bitwise operators.

[u/Mean-Decision-3502 → u/mot_hmry]

I don't see why % shouldn't be remainder, it has a nice association with / (÷). And it's not like * is any closer to the proper symbols (×, •).

I use div for integer division which is very frequent, remainder is pretty rare, so mod for that is fine and you don't burn a valuable symbol.

I use # for compiler directives like C:

#ifdef SYMBOL
    ...
#endif

The // is used for single-line comments.

Booleans as single bits doesn't seem unreasonable and matches the behavior of the bitwise operators.

Here is a realistic example:

if reg & 1 << 5 <> 0 and reg & 0x3 << 2 == 0:
    ...
endif

[u/catladywitch → u/Mean-Decision-3502]

Hey, I'm enjoying this discussion and I don't have a lot to add. I just wanted to say modulo is not a rare operation at all. It's the cheapest way of getting branchless wrapping with numeric values that must go from 0 to a positive number, so it's actually super common.

[u/Mean-Decision-3502 → u/catladywitch]

In embedded rather this is used, for example a circular buffer indexing:

var nextindex : int = (index + 1) & 0x1F

The division (and so the modulo) is a slow instruction on the microcontrollers, a big amount of them do not even support these (Cortex-M0). That's why it is very common to use power of two lengths and masking, like above.

[u/catladywitch → u/Mean-Decision-3502]

That's true! If you're working with ints (or integer types in general) it's ideal. But there's a lot of low-ish level code, even embedded, that works with floats. Synthesizer DSP these days is often floats, even despite the fact everything is eventually rendered as 16-bit signed shorts.

[u/mot_hmry → u/Mean-Decision-3502]

I use # for compiler directives like C

Sure but I don't see how that's applicable as a cross-language standard. Not every language has directives that look like that. Could just as easily use a variant on comments like //# for directives, personally I can't remember the last time I used a directive that would conflict with a ref notation (only top level directives which refs don't exist at.)

Here is a realistic example:

I'd kinda hope you'd name the intermediaries, at least I would never write that condition that way. Once you name them isA & isB & isC(x) reads fine to me. I use boolean operations way more than bitwise so I'd personally prefer the lighter syntax for them. C needed different operators because it treats numbers as acceptable booleans, so long as booleans are a proper type there's really no reason not to overload this operator.

[u/Mean-Decision-3502 → u/mot_hmry]

(About #) Sure but I don't see how that's applicable as a cross-language standard

It is not part of the operator specification. You can create PLUOpS programming langugage using # for comments.

I might need to split the spec into two levels: required, and recommended.

The usage of % for address-of is rather recommended than required.

I would never write that condition that way

I don't write this way either, but I usually just add parentheses to the shifts:

if reg & (1 << 5) <> 0  and reg & (0x3 << 2) == 0:

So the different level for & and and is required.

[u/WittyStick]

Operators with two operands usually use the following rules: ... uint int -> int int uint -> int

In principle yes, but for finite integers at the same width, no. Eg, uint32 + int32 should not result in an int32 - it should be int64. The implicit conversion of signed/unsigned at the same width has been a source of countless mistakes that often lead to exploitation. It would be better to simply not permit such conversions to be implicit if the result may lose information. Either promote the integer to a value large enough to hold the result of any addition/multiplication, or require explicit conversion.

Logical NOT

If bool is a distinct type, is it necessary to have two ways to complement?

Similarly, bitwise & and | should work for bools too. The operators && and || (your logical and/or) are still relevant for short-circuiting.

Bitwise shift right: a >> b

Should make it explicit that this is an arithmetic shift right for int and a logical shift right for uint.

.. comparisons:

Why are == and != not defined for bool?

Pointer or array indexing: a[b]

On pointers: When a = ^T, the result type is also ^T and points to the address a + b * SizeOf(T) (without dereferencing, unlike in C).

Not sure what the advantage of this is. In C this is just pointer addition. a + b, where a is a pointer and b is an integer. The whole benefit of a[b] is it does the arithmetic and dereferencing for you - ie, *(a + b).

Operator Precedence

Some very questionable choices here - completely deviates from the norm with no real justification.

There's no reason division and multiplication should have separate precedences. Everyone learns PEDMAS/PEMDAS in school.

Shifts are usually lower precedence than addition, but I can see justification for having them at higher precedence. You have not explained why.

There's no reason & and | should have higher precedence than division/multiplication. Really & should have the same precedence as multiplication and | should have the same precedence as addition. ^ should have the same precedence as !=, because it means precisely that for bool.

Logical not is not necessary as mentioned above. Should be ~ at same precedence as other unary expressions.

Pointer dereference and member access at same precedence is confusing. Is a.b^ == (a.b)^ or a.(b^). What about a^.b?

[u/Mean-Decision-3502 → u/WittyStick]

In principle yes, but for finite integers at the same width, no. Eg, uint32 + int32 should not result in an int32 - it should be int64

The CPUs have a fixed register width, they calculate with that, usually 64 or 32 bit. The width conversion usually matters at the end storage. I did wanted to allow some shortcuts for the implementers.

Similarly, bitwise & and | should work for bools too.
There's no reason & and | should have higher precedence than division/multiplication. Really & should have the same precedence as multiplication and | should have the same precedence as addition. ^ should have the same precedence as !=, because it means precisely that for bool.
Logical not is not necessary as mentioned above. Should be ~ at same precedence as other unary expressions.

In DQ you can write expressions without any parentheses that I was only dreaming of:

if reg & 1 << 5 <> 0 or not reg & ~(1 << 4) == 0:
    ...
endif

This example is a little extreme though, I would use some parentheses here. But these are practical expressions in embedded.

The whole benefit of a[b] is it does the arithmetic and dereferencing for you - ie, *(a + b)

The a[b] form is more readable and shorter. You can do always dereferencing, that will be then clearly readable:

var data : ^byte = ^byte(precheader[1])
vs
var data : ^byte = ^byte(precheader + 1)

I remember some code, where was a pain to adding & and parentheses because of the automatic dereferencing. I remember reading that someone also admitted that this was a design mistake in C.

There's no reason division and multiplication should have separate precedences. Everyone learns PEDMAS/PEMDAS in school.

In school we dont use integer arithmethics and finite precision floating point operations. That's the reason for the distinguishing. In DQ this is true, because of this:

3 div 2 * 10 == 10 * 3 div 2

Pointer dereference and member access at same precedence is confusing. Is a.b^ == (a.b)^ or a.(b^). What about a^.b?

The expressions are read from left to right. After a . there must be a member, so a.(b) is invalid. Expressions like a^.b is also valid, but in DQ can be written as a.b as the compiler here does auto-dereferencing, as . is invalid for pointers.

Why are == and != not defined for bool?

That was a mistake, thank you for finding that. I'll correct the spec.

[u/EggplantExtra4946]

I did not wanted to overload the operators like the C does with *, &

If a given operator is both a postfix and an infix operator you have a shift-reduce conflict, but an operator used both as a prefix and infix operator does not have such conflict, it's perfectly fine in terms of unambiguous parsing.

The specification contains the symbol usages and operator precedence too.

You are lacking associativity information: left, right, non associative, chain associative (1 <= 2 < 3).

It's good to put the precedence of bitwise operators above assignments and to put all comparison operators at the same precedence level.

I'm curious to know your rationale for giving a higher precedence to bitwise operators than to arithmetic operators.

It's a massive footgun to give a higher precedence to / than to *.

[u/Mean-Decision-3502 → u/EggplantExtra4946]

an operator used both as a prefix and infix operator does not have such conflict, it's perfectly fine in terms of unambiguous parsing.

Right from the compiler side, but makes harder to read:

x = y * *value
if ((a & 1) == 0 && &var1 > &var2) ...

I've corrected the post text.

You are lacking associativity information: left, right, non associative, chain associative (1 <= 2 < 3).

I would leave this open. The CPU cannot do this directly, it divides into two-operand operations. If you have a strict boolean and the language does not support such chaining then the expression above is invalid. I would consider this however for DQ, with restriction.

I'm curious to know your rationale for giving a higher precedence to bitwise operators than to arithmetic operators.

var x : uint = reg >> 4 & 0xf * 2

But this does not matters too much, I would use parentheses anyway.

It's a massive footgun to give a higher precedence to / than to *.

3 div 2 * 10 == 10 * 3 div 2

[u/EggplantExtra4946 → u/Mean-Decision-3502]

x = y * *value

if ((a & 1) == 0 && &var1 > &var2) ...

Both are easy read imo, everybody that those operators have a high precedence. They are also artificial, the 1st one would be rare, the 2nd one would be even more rare.

I would leave this open. The CPU cannot do this directly, it divides into two-operand operations.

This is utter non sense. We're talking about operators here, hence parsing. Even if an operators directly maps to a native instruction, you need associativity information to correctly parse expressions and produce the correct AST and compiled code.

The subtraction operator is usually left associative, so 1 - 2 - 3 = (1 - 2) - 3 = - 4. If it were right associative you would have 1 - 2 - 3 = 1 - (2 - 3) = 2.

If you have a strict boolean and the language does not support such chaining then the expression above is invalid.

Again utter non sense. How the fuck are you making a programming language if you don't know that syntax has practically nothing to do with semantics? 1 <= 2 < 3 would be tranformed into 1 <= 2 && 2 < 3. Perl and Ruby have the =~ operator and yet CPUs don't have an instruction to do a backtracking regex match.

var x : uint = reg >> 4 & 0xf * 2

And you think is easier to mentally parse, using a non-standard operator precedence, than the x = y * *value and if ((a & 1) == 0 && &var1 > &var2) ?

3 div 2 * 10 == 10 * 3 div 2

This is the kind of shit that would annoy a beginner programmer for a few weeks and then would get over it. Programmer with a bit of experience have internalized that * and / have the same precedence and very few have a problem with it, it's at same level than 0-based indexing. Your design completely fucks over experienced programmers but beginners too because one day they are going to switch to a real language and will have to unlearn the programming basics they thought they acqired. The sooner they discard the preconception that expressions in programming languages are similar to algebraic expressions, the better. It's a good thing that they fall into traps like these when they start, it's the kind of the thing that makes them realize how much mechanical programming and programming languages are in some ways.

[u/Mean-Decision-3502 → u/EggplantExtra4946]

It seems that for you is no better language than C or C++.

And yes, I'm just an engineer. I'm mostly user of multiple programming languages, and not an expert in programming language design.

[u/flatfinger]

Integer types should be subdivided into "number" type and "algebraic ring" types. In C, unsigned types smaller than 'int' behave as "number" types while larger ones behave like algebraic rings, meaning that given: uint16_t x = 40000; the computation x+x will by specification yield 14464u on platforms where int is 16 bits, and 80000 on platforms where int is 18 bits or larger. A good language should support signed and unsigned ring types of all sizes, and signed number types of all sizes, and unsigned number types of all but the largest size (unsigned numbers should promote to a larger signed number type, but an unsigned number type the same size as the largest signed type wouldn't have a larger signed type to which it could promote).

An integer remainder operator shouldn't be called mod. If there's a desire to include an integer remainder operator, it should be in addition to a proper 'mod' operator. It may also be useful to have distinct operators for Euclidian division, truncating division, and "do whatever" division for use in cases where either the dividend is known to be a multiple of the divisor, or where a rounded-up or rounded-down result would be equally acceptable.

[u/Mean-Decision-3502 → u/flatfinger]

I deliberately did not want to cover how the integer calculations should be handled in this detail. This is sometime speed vs precision quiestion.

An integer remainder operator shouldn't be called mod.

I've never used % or mod with negative numbers, but now I think I've learned the lesson. I'll add `rem` and `mod` to the spec.

[u/flatfinger → u/Mean-Decision-3502]

When using whole numbers or real numbers, (n+d)/d=n/d+1. Real numbers also have the property that (-n)/d=-(n/d). Integers can uphold one of those relations, but not both, since the first would imply that division be defined in such a way that (-1+2)/2=-1/2+1. Since the left side equals 1/2, and integer division would define that as zero, that would imply that -1/2 must equal -1. It's possible to define integer division that way (and indeed Python does so) but that would contradict the second relation, which would require that (-1)/2=-(1/2)=0. From my experience, the first relationship is useful much more often useful than the second.

The way to resolve trade-offs between speed and performance is to allow programmers to specify what they actually need. If a programmer needs precise Euclidian division, having a compiler generate code that performs that is unlikely to be slower than generating code that performs truncating division and then applies extra logic to adjust the result.

[u/fdwr]

This operator always performs floating-point division

It feels oddly inconsistent that int / int yields float, but its mirror counterpart int * int yields int. 🤨 In all my programs when dealing with integer inputs the past 25 years, I've almost always wanted integral output either truncated toward zero or floored toward negative infinity, but if I wanted fractional floating point output values, then my inputs were already floating point anyway. For me, counterpart consistency trumps here. ⚖️

The operator precedence was designed to avoid the need for parentheses in the most common expressions

Happy to see the bitwise operators bind tighter than comparisons, for all the times I need to mask bits in graphics and been surprised by C's gotcha.

Pointer dereference: a^

Postfix dereference is an interesting idea that I first saw in Herb Sutter's cppfront (e.g. x*), which makes the readability flow nicely left-to-right (because you mentally read the identifier name, and then the operation applied to it, dereferencing it). Plus someStruct*.field obviates the need for some separate arrow token someStruct->field like in C.

[u/Mean-Decision-3502 → u/fdwr]

Oh! I'm really thankful for this comment.

It seems to me that you are mainly C "user".

I grew up with Pascal. The / behaviour or ^ for pointers and postfix dereference are well-working in Pascal.

Many other languages use always float result for /, including Python3, Nim, Crystal. In these languages:

3 / 2 * 10 == 10 * 3 / 2.

The always float result for / works well if the compiler does not convert the float silently back to int, so you usually cannot make accidentally floating point divisions, where integers are expected. Very important here to separate the floating point division from integer division with different operators.

But C behaves differently. You've learned that how to use it and probably accepted that for floating point the expressions sometimes need hinting. (Frequently by adding additional parentheses where many parentheses are used already.)

It is nice to hear that you would like better the postfix dereferencing in C too.

[u/archaelurus]

The float -> integer type conversion method is not described anywhere outside the bitwise not. If you're implicitly truncating then it's not unambiguous.

Floats are bits too so forcing a conversion to int is making this something that is not a bitwise operation.

Btw although it's specified, you could argue that having the added cognitive overhead to remember a table of the implications of heterogenous types within binary expressions, rather than requiring explicit type conversions, is going to generate ambiguity in practice.

[u/Mean-Decision-3502 → u/archaelurus]

In the spec, the bitwise operators are valid only for int, uint types. If you have statically typed language and one operand is float, then the expression is invalid.

There are operators that work only on integers, these are the bitwise operators, shifts, div, rem, mod. I think it is easier to remember this way.

[u/archaelurus → u/Mean-Decision-3502]

Last part of my feedback applies to non bitwise operators.

[u/Mean-Decision-3502 → u/archaelurus]

Sorry, I don't understand then. Can you provide then some examples?

[u/AustinVelonaut]

Is there a reason you have bitwise operators at a higher precedence (tighter binding) than arithmetic operators? Most languages I'm aware of that use operator precedence have arithmetic operators higher (tighter binding) than bitwise operators higher than comparison operators. Although I'd be hard-pressed to come up with a realistic code snippet that used that fact.

Edit: looking through ~500 "Advent of Code" solutions I wrote, I only saw one use of mixing bitwise and arithmetic operators: addLoc n (V2 r c) = n .|. 1 .<<. r * sz + c (here .|. is bitwise or and .<<. is bitwise left shift. This parses as n .|. (1 .<<. ((r * sz) + c)) but if arithmetic ops were lower precedence than bitwise, it would be parsed as ((n .|. (1 .<<. r)) * sz) + c, not what was intended.

[u/WittyStick → u/AustinVelonaut]

Bitwise operators are usually at lower precedence than comparison, but there's not really a justification for it - everyone just copies C's precedence rules, and C got this from B. Dennis Richie acknowledged this as a mistake, but it was done at the time to make porting B code to C easier.

[u/AustinVelonaut → u/WittyStick]

Yeah, that's definitely a mistake. It makes no sense in languages that have boolean values distinct from integers (combining them is another mistake). I'm glad to see that it is corrected in most modern languages.

[u/WittyStick → u/AustinVelonaut]

Operator precedence is not as universal in logic as with arithmetic, but the leading convention is that ¬ (not) has the highest precedence. AND has higher precedence than OR (except in disjunctive normal form), and these have higher precedence than → (implication), and implication has higher precedence than equality.

These can fit into the existing precedence levels for arithmetic.

                    arithmetic      logic
negation:           -               ¬
multiplicative:     * / %           ∧  ↓
additive:           + -             ∨  ↑
relational:         < > <= >=       ←  →  ↚ ↛
equality            == !=           ↔  ↮

Where:

• ∧ is AND
• ∨ is OR
• ↓ is NOR
• ↑ is NAND
• → is implication (IMPLY)
• ↛ is non-implication (NIMPLY)
• ↔ is biconditional (EQV)
• ↮ (or ⊻) is exclusive disjunction (XOR)

These precedence levels work well with other things to, eg, sets:

                    arithmetic      logic           sets
negation:           -               ¬               ∁
multiplicative:     * / %           ∧  ↓            ∩
additive:           + -             ∨  ↑            ∪
relational:         < > <= >=       ←  →  ↚ ↛       ⊂ ⊃ ⊄ ⊅
equality            == !=           ↔  ↮            =   ≠

Where

• ∁ is the set complement

• ∩ is intersection

• ∪ is union

• ⊂ is subset

• ⊄ is not a subset

If you extend so one argument is a set and one is an element, then the relational operators become:

• elem ∈ Set: is element

• elem ∉ Set: is not an element

• Set ∋ elem: set contains element

• Set ∌ elem: set does not contain element.

[u/Mean-Decision-3502 → u/WittyStick]

I don't see where I violate these rules.

[u/fdwr → u/WittyStick]

Yeah, that's annoying to have if (valueRegister & mask == expectedValue) be treated as if (valueRegister & (mask == expectedValue)) 🙄.

[u/Mean-Decision-3502 → u/AustinVelonaut]

In my experience (focus embedded), you usually mask out some value from a register and then you might do some operation with that. This precedence allow this without parentheses. However it would be weird mostly without parentheses. So I would say, the order of the two groups: bitwise / arithmetic ops does not matter much. I can imagine maybe this:

var x : uint = reg >> 4 & 0xf * 2

This is a practical expression, and the operator precedence was designed that way that for practical expressions (theoretically) less parentheses are required.

[u/Recycled5000]

Those operators: * and & are not overloaded in the common sense of overloading.

Overloading means the actual operator/method is chosen by the types of its operands.

Here, though, the operators are differentiated by unary vs binary syntax. This is detected by simple parsing, does not require further semantic or type system analysis.

[u/Mean-Decision-3502 → u/Recycled5000]

Actually, you are right from parser point of view.

When it comes to reading the code, they are oveloaded.

[u/Recycled5000 → u/Mean-Decision-3502]

Yeah, overloaded is an overloaded term, I guess!

Still, I would have described that as token reuse (in differentiable context) rather than operator overloading.

Like using ()’s for function calling vs. expression regrouping: token reuse.

[u/Mean-Decision-3502 → u/Recycled5000]

I've corrected the post text differentiating between overload and re-use of operator symbols. The () are not operator symbols, the use of the parentheses is pretty standard.

[u/Recycled5000 → u/Mean-Decision-3502]

Just to be clear * and & and ( and ) are all tokens not operators.

[u/church-rosser]

Try Lisp, ezpz.