Inside C++ is a Turing Incomplete language waiting to get out

OK, I lied. I’m just clickbaiting. It ain’t waiting for that. But I have something to say about the concept …

There’s an esolong (esoteric programming language) out there named something like “Froogle”. That’s not it’s name, but it’s something like that. If anyone can identify it’s actual name, then please comment. It has an interesting feature that you can do loops and conditionals in it (IIRC), but it is nevertheless Turing Incomplete. It has a companion language, named something like “Smoogle”, that adds on extra feature: jumps. This one extra feature makes it Turing Complete.

Someone observed that C++’s templates are Turing Complete. I joked that in order to find the answer to any problem one didn’t need to go through the labour of actually running a program; merely compiling it would suffice.

But here’s the interesting thing … C++ is accumulating a lot of features like constexpr which are accessible at compile time.

So you can do a lot of compiler checks. Aha, isn’t that interesting? It’s like Rust being able to do a lot of consistency checks, but with C++ not as powerful as Rust.

So idea here is to somehow have a split-level language: a part that is Turing incomplete, and a part that is complete. This peculiar lower-tier as-yet-to-be-determined language could speed up computation in the higher tier, and act as a correctness guarantee.

We can see contracts and stuff entering C++. The debate rages on as to whether late binding is a good idea or not. People like Alan Kay, and Lispers, are firmly in the camp of extreme late binding. C++ is firmly in the camp of Bondage And Discipline. What you get out of the latter is at least some guarantees of correctness. In fact, it’s pretty clear the direction that C++ wants to go in: it wants to be an engineering language, like Rust.

Can this idea be pushed further, and what form would it take, and how would it be implemented? So, my idea is that you could somehow specify what relationships can exist between objects, and the compiler could statically verify that these constraints hold.

My idea formed when I was looking at the clock settings for the Raspberry Pi Pico (great microcontroller with some good documentation). The Pico SDK is written in C, and it made me wonder what could happen if written in C++.

Here’s the specific problem I was thinking of: it’s a general problem in MCUs (microcontrollers) that you want to set the frequency of something, say a PWM frequency. What you must often do is to factor about that number into a prescaler and a count, such that prescaler*count = frequency.

Now, the problem is, you might not do it right, and say, compute a wrong count for the size of the register. That means that you mess up your frequency calculation, and the MCU won’t behave in the way you want it to.

Now, C++ has “limits”, which tell you the bounds on a number. Maybe, with some constexprs and some static setup, you could get C++ to statically assert the frequencies always make sense.

That’s just an example. The trick would be to come up with some language that could solve that kind of problem generically.

There’s an Indian professor at an American university that studies the expressiveness of programming languages. He’s fairly well-known, but alas, I don’t remember his name (once again, if you can supply his name, then please do). He is interested in making strict mathematical statements about what it means for a language to be more expressive than another.

I’m almost inverting his ideas: I want to know what a less expressive language can buy me,

Anyway, that’s just a daft idea I had late last night. Don’t be hating.

About mcturra2000

Computer programmer living in Scotland.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s