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 *, & and /. 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/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/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/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/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/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 *.