DARPA suggests turning old C code automatically into Rust

[coppice]

I am feeling less guilty about my ignorance of the complex data type in C.  When googling C Data Types, the first five answers, starting with the new AI "summary", followed by Wikipedia and the next three returned responses don't mention a complex data type.  Same with the 700 page C training book I got in 1997, even as a possibility for the future.  So it didn't have complex data from its start at ATT,  through its explosion in popularity, through ANSI C and the 1995 update.  It seems that the vast majority of the users of the language didn't miss its absence much, and probably a significant proportion of that population is unaware of its availability to this day.

Oh, we missed it. However, real world complex support entered the C world in such a late and piecemeal fashion, most of us who use a lot of complex data had already settled into our own way of doing things. Rather like the way that in a sane world we would have had things like int16_t from day one, but because we didn't there is still more code using other people's macro names than the standardised ones.

[Marco]

Maybe making memory safe C++ a better idea.

Backwards compatibility is non negotiable. Swift will likely get a subset with all noncopyable types though, then there will be three somewhat mainstream borrow checked languages to choose from.

[SiliconWizard]

For example, C could easily "fix" right-shifting negative values for two's complement types (intN_t, int_fastN_t, int_leastN_t) by standardizing it the way all compilers that don't produce garbage do it (which is right shifting the storage bit pattern, duplicating the sign bit).  This is the right approach, because it has been shown in practice to work –– C99, C23, Fortran 95, Fortran 2003 for example.

myC refuses to compile and throws an error for any attempt to shift signed integers. To avoid the restriction, you need to manually define what is meant by "shift" signed things.

All undefined behaviors and implementation-defined behaviors are handled this way: it's the user that must define them, otherwiser the compiler refuses to compile!

- if it comes out garbage, it's not my fault - that's my approach 

Anything implicit in a prog language is a gun pointed at your head. That's why Ada has a very strict typing behavior and pretty much no implicit anything.
Implicit makes it look easy to use, until it backfires and you're then very sorry. So in a way, that's like languages for kids.

As to bit shifting, there are various lines of thoughts.
- The reasonable and rational: bit shifting on signed integers are "arithmetic shifts". Sign is preserved.
- The bare one: bit shifting always done as pure bit shifting whatever the signedness (crazy, but simple).
- Making bit shifting on signed integers UB. Even crazier.
- And, as you proposed, making bit shifting on signed integers forbidden entirely. No question.

Arithmetic shifting is like seeing the shifting as equivalent to a mulitply or divide by a power of 2. It's a higher-level operation.

The general problem with UB is that any reasonable developer should consider "UB" as "forbidden" in general, but the standard says "do as you wish, I don't care". And so does the compiler. Sure it gives more flexibility for compilers.

[Nominal Animal]

Arithmetic right-shift operation on negative numbers using two's complement format isn't exactly dividing by a power of two, because arithmetic right shift of \$v\$ by \$n\$ bits actually implements
$$v^\prime = \begin{cases}
\displaystyle \frac{v}{2^n}, & v \ge 0 \\
\displaystyle \frac{v - 2^{n-1}}{2^n}, & v \le 0 \\
\end{cases}$$
That is, most current C compiler implementations yield
    (-63) >> 1 == -32   but   -63/2  == -31
    (-61) >> 2 == -16   but   -61/4  == -15
    (-57) >> 3 == -8    but   -57/8  == -7
    (-49) >> 4 == -4    but   -49/16 == -3
because they use two's complement format for signed integers, and arithmetic right shift is the same as shifting the storage pattern right with new shifted-in bits getting the value of the original sign bit.

In particular, for n > 0, we have (-1) >> n == -1.

The mathematical properties and ease of integer negation and bit pattern inversion (they're supported by all instruction set architectures, and are extremely lightweight operations) is what makes this implementation superior, for both programmers and compiler writers.

In particular, when you have an unsigned integer value with at least one most significant bit unused, negating the value v, arithmetic right-shift by n bits, and negating the result again, implements
    v' = (v >> n) + !!(v % (1 << n))
i.e., increments the result by one whenever any of the shifted bits out were nonzero.  (!! is the not-not operator, which yields 0 if the operand is zero, and 1 if the operand is nonzero.)  This is surprisingly commonly used during various padding calculations, and the most common way this is implemented is
    v' = 1 + ((v - 1) >> n)
which yields the exact same results for v ≥ 1, but has issues with v=0 (unless the arithmetic right shift is used for the v=0 case, such that (-1)>>n == -1).

In both cases one or both of the negations, as well as the increment and/or decrement, can be merged with other operations in the same expression.  The difference is only with how v=0 behaves.  (Technically, the negation approach is also limited to half the range of the unsigned type, whereas the increment-shift-decrement supports the full range of the unsigned type except for zero.)

This is also a perfect example of where practical exploration and competition can prove superior to carefully planned design.

Any human language designer would be attracted to define negative right shift as the division by a power of two, because of the symmetries and apparent simplicity.  However, only optimization work on actual real-life operations would tell such a designer that no, the desire for symmetry there is unwarranted, and because of practical code and machine implementations, being asymmetric this way following what the actual processors do, yields better performing code.  Even the world of embedded computing is way too complex for any single human mind to comprehend, so at some point, the designer has to relinguish some control, and instead let the language evolve on its own, only holding the reins lightly –– like for a horse going home –– gently guiding the direction, instead of dictating directions and considerations.

I think strict focus and careful planning is required at all stages of language design and extension/development.

Strict focus: yes, definitely.  You want to keep the overall shape and paradigm (approach to problem solving) clear, and avoid trying to cater to every single whim.

Careful planning: In the latter stages, extensions do not need to be and should not be pre-planned; they can simply be experimented with as needed.  Their inclusion into the standard proper, however, should be very carefully examined and investigated, to see if they fit, do not break existing code, and do not pose other difficulties to existing implementations.

In contrast, the core language must be carefully planned beforehand.  That part dictates what the approach to problem solving will be, and getting it even slightly wrong will require a new language; fixing such in backwards-compatible manner just does not work well enough (again, Python 2to3).

I don't know if this is what you meant, though.

In my opinion and experience, pre-planning possible extensions by language designers is a no-no for me, because they're limited to their own vision.  Allowing nonstandard extensions to flourish, and then carefully pick what will be included, in the "stable phase" of the language, is absolutely required for the language to stay current and as useful as possible in the long term.  Heck, I even like having competing extensions, because that way a larger fraction of the possible extensions will be explored; and as long as the selection process is careful enough and fitting within the language, I claim will result in better development than any human pre-planners can achieve.

(Of course, if you define that pre-planning that the extensions should be experimentally implemented first, before their inclusion in the language proper, then my needs are fulfilled.  However, that also requires that language designers become compiler/interpreter implementers also, or at least work very closely with some.  This is the crucial difference in my opinion: whether a language is fully defined as a theoretical construct first, or whether only its core, its idea, its paradigm is, with extensions and additions tested first and examined in practice, then modified, and finally selected for inclusion into the language.)

[DiTBho]

Arithmetic right-shift operation on negative numbers using two's complement format isn't exactly dividing by a power of two

In the early 90s, it was well described in computer science books written by people like Clements.
I remember there were at least a couple of examples and exercises with solutions, very useful for practice.

Nowadays almost nobody writes books that deal with these issues with assembly examples anymore.
And there are even things that I don't find implemented in hardware.
For example, without any software support, the MIPS5++ ISA does not offer any sign extensions for any shift operation.

This is a bloody example of how you can do whatever you want as long as you know that you can't blame the compiler.
If you get weird behavior, well that sort of thing is not supported by the hardware you are compiling for.

[newbrain]

As to bit shifting, there are various lines of thoughts.
- The reasonable and rational: bit shifting on signed integers are "arithmetic shifts". Sign is preserved.
- The bare one: bit shifting always done as pure bit shifting whatever the signedness (crazy, but simple).
- Making bit shifting on signed integers UB. Even crazier.
- And, as you proposed, making bit shifting on signed integers forbidden entirely. No question.

The way the C standard defines right shifts for negative integers is missing: implementation defined.

The result of E1 >> E2 is E1 right-shifted E2 bit position. [...] If E1 has a signed type and a negative value, the resulting value is implementation-defined

There's a very substantial difference between IDB and UB.
OTOH, left shifts on signed integers that change the sign bit are UB.

As discussed already (ISTR) that was a sane decision at the time the first standard came out.
Probably much less now, and as C23 moved to forced 2's complement, they could have taken the step of defining the right shift as always being an arithmetic one. For the left shift I'm not taking position, but it's the same (undefined) behaviour as integer overflow - which is at least consistent.

Arithmetic right-shift operation on negative numbers using two's complement format isn't exactly dividing by a power of two
[excellent argumentation snipped]

They should have gone the way of FORTH: integer division rounds towards minus infinity. Problem solved!

[DiTBho]

The way the C standard defines right shifts for negative integers is missing: implementation defined.

Do you like myC approach = compiler refuses to compile on { ID, UB } ?

[Nominal Animal]

Arithmetic right-shift operation on negative numbers using two's complement format isn't exactly dividing by a power of two

They should have gone the way of FORTH: integer division rounds towards minus infinity. Problem solved!

Yup! 

(I admit, I completely forgot that rounding towards negative infinity is also exactly equivalent here!)

[SiliconWizard]

Arithmetic right-shift operation on negative numbers using two's complement format isn't exactly dividing by a power of two

They should have gone the way of FORTH: integer division rounds towards minus infinity. Problem solved!

Yup! 

(I admit, I completely forgot that rounding towards negative infinity is also exactly equivalent here!)

Yes, I was gonna reply to your post and this isn't needed now.
Ultimately, the difference is indeed in the rounding. Either could be justified depending on the application. Of course, it's good to know that there can be a difference, although it's entirely implementation-defined when it comes to C and other languages. The underlying reason for this difference is of course the very low-level implementation (rtl/gate level), which is easier this way. The arithmetic shift right is just a matter of shifting everything right and copying the sign bit.

The TLDR; would be never to use a right shift on signed integers in C if you want your code half-portable.
If you don't care, while it's indeed implementation-defined, you'll find that on "most" modern targets and "most" compilers, the right shift on signed integers is just a classic arithmetic shift (due to it being available directly as an instruction on most targets), so if that's what you want and don't want to rely on inline assembly, then, you can always use that. After checking and at your own risk.

[newbrain]

The way the C standard defines right shifts for negative integers is missing: implementation defined.

Do you like myC approach = compiler refuses to compile on { ID, UB } ?

A honest question:

Does "refuses to compile IDB" mean it will not allow anything on Annex J.3 to pass compilation, or that a specific behaviour has been defined?
In the latter case, that would no be any different from a C compiler.

In the former, and the same holds for UB (J.2), how can you catch them all at compilation time?

Many of both can possibly caught only at runtime (e.g. converting a double to float: it's IDB if the value fits, UB otherwise) unless the language is so far removed from C that the comparison is only syntactical (I think I remember heavy limitation on pointers?).

While having a syntactically "comfort zone" language is not a bad idea, in this case I'd personally go for something less niche - most likely, Rust (yes, Rust has its problems too) - also to help me compartmentalize my habits and idioms.

EtA: UB annex chapter, and an extra question: What about J.1, Unspecified behaviour?

[Nominal Animal]

The TLDR; would be never to use a right shift on signed integers in C if you want your code half-portable.

I disagree, literally because I haven't encountered a C compiler that did not implement right shift on signed integers as an arithmetic right shift.  To me, this is practically portable across all architectures I've been interested in thus far, and that's quite a few.

I do insist that it and other expectations on such implementation-defined behaviour should be well documented in the project, though; preferably including build tests/checks that lets builders/integrators check and verify.

This is what I aim to do, and I do claim it makes such projects –– even when those projects go beyond the text of ISO Standard C and occasionally even beyond POSIX C or GNU C domains –– more portable than only using allegedly strictly standards-compliant code.  It isn't "clean" so to speak, but it is very practical.

That said, I do usually check the alternate forms of the same expressions avoiding implementation-defined behaviour, to see if the compilers I use generate acceptable code.  (No need to be optimal, though; I only want to avoid the pathologically bad cases.)  If they do, then I use the standards-compliant expressions.  Godbolt.org is an excellent resource for this.

After checking and at your own risk.

There is always a certain amount of risk when using C, because there is disagreement on the exact interpretation of the details of the C standard.  As someone who writes C code, I firmly believe the developer should always acknowledge that risk, and bear the consequences.

You see, in my opinion, developers should always be responsible for the real-world end product they publish.  This means that if compilers used have a bug, the developer should feel responsible for working around that bug until the compilers fix it on their end, instead of throwing ones hands up that "it's not in my code, I'm not responsible!".  (I don't mean any bug in any version; only in most commonly used current versions.  Responding that "I would do the workaround if it impacted more users, but I just cannot allocate the time needed for this right now" is perfectly okay.)

The point I'm trying to make here is that even if you follow the standards to the letter, a developer should not feel like it takes away their risk or responsibility of the end product.  Thus, using and documenting extensions and expected implementation details is acceptable –– it is, after all, how the POSIX C standard ensures portability with respect to deviations from ISO C.

[DiTBho]

Does "refuses to compile IDB" mean it will not allow anything

myC is strongly typed and beats its user hard.
Each type carries with it properties and operators that "may" or "may not" be defined.
If they are not, the compiler refuses to compile.

Above, we were talking about operations defined on a data type, the "signed type"

on uint(x)_t, with x equal to the bits of the CPU registers {8, 16, 32, 64, ...}, all the logical and arithmetic operations supported by the CPU are defined by default, and should be careful that if something is not defined in the machine layer because it is not supported by the hw, then the compiler refuses to compile explicitly reporting the problem.

on sint(x)t instead, no operation involving shifts, or bitset/tst/get, etc. is defined, and therefore the compiler simply refuses to compile if you try to use them.
If you insist on using them, you need to define all operations in a machine-level extension.

For all types (including boolean_t), the range is always checked at runtime. If something goes out of range, an exception is immediately raised.

You can also define "subrange", e.g. uint8_t i0'subrange={0...10}; and be careful that this also includes the range of validity of the iterators, which must be written in a particular way, otherwise when it exits the loop the value of the iterator could be "10+1" and an exception is raised!

uint8_t i0'subrange={0...10};
for (i0=0; i0=<10; i0++) { } <------- won't work!

uint8_t i0'subrange={0...11};
for (i0=0; i0=<10; i0++) { } <------- will work!

uint8_t i0;
for (i0=0; i0=<10; i0++) { } <------- will work!

There is no overflow, there is no underflow, and there is absolutely no "casting" as is done in C

To go from one type to another, you need to define "bridge function", which expressly express how to go from one type to another, and the valid criteria for validity, so, once again, the range!

[newbrain]

Thanks!
So you 'undefined' all behaviour unless explicitly described.

I think the first two example should have a "<=" rather than a "<" ?

I gather that by "no casting" you also include "no automatic promotion/demotion", summing a uint8_t{0...10} to a int16_t{-1000...1000} and assigning the result to an int32_t or, worse, to a uint32_t will then need a number of explicit conversions?

The type system is similar (in representation, names, syntax...) to C, but totally different in semantics, I see (pun half-intended).

Checking overflow and throwing an exception (IIUC the mechanism) on all operation (and libraries!) is going to incur in a heavy runtime cost, apart from the cases when it can be proved not to occur at compilation time, but I understand the intent and it can be warranted in your context.

[Siwastaja]

The way the C standard defines right shifts for negative integers is missing: implementation defined.

Do you like myC approach = compiler refuses to compile on { ID, UB } ?

I think that is a convoluted way of saying "my language does not have implementation defined or undefined behavior".

Which is very sensible design.

[DiTBho]

So you 'undefined' all behaviour unless explicitly described.

Precisely 

Checking overflow and throwing an exception (IIUC the mechanism) on all operation (and libraries!) is going to incur in a heavy runtime cost, apart from the cases when it can be proved not to occur at compilation time, but I understand the intent and it can be warranted in your context.

Yes, talking about the implementation of myC, this is a serious problem because that "language feature" increases the code size and reduces the speed.

If you compare the binary code produces (same C source) by gcc-mips32 with the code produces by myC-mips32 (in c/89 compatibility mode), it's significantly slower and takes up many more Kb.

The above example is not even optimal for an ICE connected to a myC-dbgTAP.
Instead of sub-ranging a "variable" it is better to define a "new type", derived from a primary type (e.g. uint32_t) with a limited range, and then use the new type for a variable.

It makes debugging much easier, and faster.

myC has a local (per function) "variable space" which has to be loaded at every "function call", and a global "type space", a table that is loaded into memory in session crt0.

Both describe objects in terms of properties, the "variable space" is on demand.

The subrange property is there, in the table. By addressing the table by "type-id" or by "var-id" at runtime, the range-check has to
- load the range from the table
- check if the register content is within the range
- trap if it's not

Always many loads and comparisons 

[SiliconWizard]

Not leaving anything ID or UB is good, but one has to realize it's much harder than it looks.
Yes, sometimes this is intentional (like, some parts of the C standard that leave some things ID or UB to *potentially* allow compilers to be simpler or yield more efficient code), and that part can be deemed questionable.
But the reality is that many of the ID or UB parts of C initially come from missing specs (things that were overlooked), then developers start to count on specific behaviors of the available compilers, then years later, standard comittees decide that these missing specs must be mentioned, but they can't make them anything other than ID or UB, which could potentially break existing code all over the place. That's the (sometimes sad) reality.

When designing a new language, it's a good idea to try and identify as many of these cases and not make them open questions (so no ID or UB). It's also easier to do now that there is literally decades of experience in programming. But being exhaustive is kind of an elusive goal, and so there will probably always be some edge case that we have forgotten to specify, and existing code bases will hinder change.

The lack of a formal specification makes it all even harder. If all you have is a compiler (so, software itself) to define a programming language, then you are at the complete mercy of its implementation and you may rely on compiler behaviors that you don't even completely grasp, you just observe that "it appears to work". Yes Rust, I'm looking at you.

[DiTBho]

Rust, I'm looking at you

eh, I don't know how many languages ​​- excecpt Ada - have a formal spec.
Maybe only academic things, and not even well done.
As far as I know, in the various advanced academic courses you never touch anything really useful.
Not even years later when you grew up with the industry.

That's life in Computer Science

[Siwastaja]

But the reality is that many of the ID or UB parts of C initially come from missing specs (things that were overlooked), then developers start to count on specific behaviors of the available compilers, then years later, standard comittees decide that these missing specs must be mentioned, but they can't make them anything other than ID or UB, which could potentially break existing code all over the place. That's the (sometimes sad) reality.

This is why it would be interesting to see a "new C" which is allowed to break compatibility for good reasons - for example removal of IDB/UB -, but doesn't try to turn everything upside down and invent a completely new language either. Because when you do that, you lose the wisdom collected over the years, and will repeat many of the same mistakes again.

I mean, I'm not a big fan of the Python 2->3 transition but that demonstrates such a thing can be done.

[SiliconWizard]

While I'm not a fan of the name, Zig kind of does that.

[cfbsoftware]

Rust, I'm looking at you

eh, I don't know how many languages ​​- excecpt Ada - have a formal spec.

Modula-2 underwent a rigorous, but excruciating formalisation process. See "ISO/IEC 10514-1, the standard for Modula-2: Process Aspects" for some of the issues involved:

https://dl.acm.org/doi/pdf/10.1145/242903.242950

The guys working on the Rust specification would do well to study that process before going too far.

https://blog.rust-lang.org/inside-rust/2023/11/15/spec-vision.html

[SiliconWizard]

Rust, I'm looking at you

eh, I don't know how many languages ​​- excecpt Ada - have a formal spec.

Modula-2 underwent a rigorous, but excruciating formalisation process. See "ISO/IEC 10514-1, the standard for Modula-2: Process Aspects" for some of the issues involved:

Yep. Thanks for the paper - should be a good read.

And while one may argue to no end that standards are not "formal specs" (however we want to define this), any standardized language can be considered having one. Unless you like nitpicking.
Point is - whether it's a standard or not, you need a spec good enough to allow developing compilers that will compile the same code yielding the same observable result, and likewise allow developers to write code that will work with any compliant compiler.

That is undoubtedly the case with C and Ada (if one excludes bugs rather than lack of specs). Probably also C++, although it's so complex that it's hard to validate.

Since a new language can't get a standard before years (or sometimes decades), a spec is all you can have early on.

The absence of a spec (formal enough that it is reasonably unambiguous and authoritative) prevents any third-party from writing compilers and any developer from writing code they'll be sure will be correct ten or twenty years from now, which is game over in my book.

[westfw]

Rude question:

Is BASIC a memory-safe language?  Could it be?

[magic]

IIRC, Microsoft Visual Basic and Quick Basic were memory safe
(With exception of the latter offering peek/poke instructions.)

There was indeed a plan to rewrite Linux as a microkernel in a message-passing dialect of Visual Basic.

[SiliconWizard]

There was indeed a plan to rewrite Linux as a microkernel in a message-passing dialect of Visual Basic.

 

[magic]

It was supposed to be the 3.0 release, but it didn't happen
https://lkml.org/lkml/2005/3/2/247