Show HN: Compile C to Not Gates

[tomhee]

Hi! I've been working on the flipjump project, a programming language with 1 opcode: flip (invert) a bit, then jump (unconditionally). So a bit-flip followed by more bit-flips. It's effectively a bunch of NOT gates. This language, as poor as it sounds, is RICH.

Today I completed my compiler from C to FlipJump. It takes C files, and compiles them into flipjump. I finished testing it all today, and it works! My key interest in this project is to stretch what we know of computing and to prove that anything can be done even with minimal power.

I appreciate you reading my announcement, and be happy to answer questions.

More links:

- The flipjump language: https://github.com/tomhea/flip-jump https://esolangs.org/wiki/FlipJump

- c2fj python package https://pypi.org/project/c2fj/

[bangaladore]

Reminds me of movfuscator [1]. This can compile programs to movs and only movs.

[1] https://github.com/Battelle/movfuscator

[LPisGood]

Battelle is great. They also created some software called Cantor Dust [1] that turns files into images to allow humans to easily spot obfuscated data or files.

The sad thing about this kind of work, because I love it, is that to get paid to do it you need clearances and polygraphs and periodic reinvestigations/continuous monitoring and all sorts of things that I find unpleasant.

[1] https://github.com/Battelle/cantordust

[beng-nl]

Agreed that is a fine piece of work. But the author is Chris Domas. Which is plain from the repo readme, but it’d be clearer to link to his repo.

[tromp]

Am I right in deducing that this language gets its power from self-modifying code? I.e. flipping bits within addresses of the opcodes of the running program?

[tomhee]

You are indeed right

[tomhee]

There is also a brainfuck to flipjump compiler: https://github.com/tomhea/bf2fj

[david-gpu]

Ah, the convenience of brainfuck with the performance of flipjump. Excellent.

[tomhee]

By the way, as a challenge, try how you can program an "If" statement in Flipjump.

[greenbit]

I wondered this as well.

Thinking about it, if all you have is "invert some (N>1?) bits somewhere and jump to somewhere" .. I could see maybe it might work if you use self modifying code and there's really a 2nd instruction that is a no-op? Seems like it might work more like a cellular automata?

Of course, one could just go look at the documentation, but where's the fun in that?

[alok-g]

Would like to know the answer. Thx.

[pizza]

Ah interesting.. wonder if you can model this with a recursively expanded algebraic expression. I've been thinking lately along similar lines about polynomials that encode pushdown automata, so this is cool to see.

[tomhee]

If you have an answer I'd be happy to hear it!

[Firehawke]

Wouldn't it be better to call it "compile C to Linux or BSD"?

I kid, I kid.

[dingdingdang]

It always amazes me that this is possible (to some extend anyway, I mean, the base layer is binary so obviously simpler higher-end CPU instructions are possible!)

Is there any potential performance win in this? What I mean is; since this general direction could, in principle if not in practise, enable the targeting of say, the 5-10 most efficient CPU instructions rather than attempting to use the whole surface area... would this potentially be a win?

[eimrine]

I was expecting to see a way to translate hello_world.c into an electronic schematic full of NAND elements, kind of Mealy machine.

[tonetegeatinst]

Looking forward to the poor security researcher who gets to reverse engineer some malware sample they compiles this into for obfuscation... Its going to be an interesting blog post.

[jkrshnmenon]

I wonder if someone has already made a Reverse Engineering CTF challenge for this concept.

[tomhee]

There actually was one with subleq: https://www.google.com/amp/s/blog.attify.com/flare-4-ctf-wri...

[og2023]

I read it as reverse engineering WTF challenge... cool stuff though, seriously.

[dlcarrier]

Maxim (now owned by Analog) actually manufactures a single-instruction processor series, called MAXQ. It uses a single move instruction, with a flag for literals, and a transport triggered architecture.

[Zamiel_Snawley]

What is the intended use case for such a processor?

[jvanderbot]

Is the family of circuits using just NOT gates actually universal? Or is "flip" and "jump" secretly using a lot of other gates.

[tomhee]

The power is within the self modification of the code. The jump might be implemented by a multiplexer, though it can be implemented in other ways too.

[Imustaskforhelp]

hey this could actually be pretty nice if we can convert flipjump into sqlite native instructions like how it is possible for brainfuck , then you are on to something huge!

You would create although highly inefficient , after many years , maybe the first , language like those lisps where you could store data in sqlite and run it fromt there (but with C)

[tomhee]

That's cool! And that's possible. Do you have any more data to read about it?

[Nevermnd]

Did I miss something? I thought NAND was you're 'universal gate' ?

[artemonster]

Id appreciate more explanations from the power of combined bitflip & goto

[tomhee]

Sure!

https://github.com/tomhea/flip-jump/wiki/Learn-FlipJump

This will let you understand how to implement the very basic "if" in flipjump.

I tried to make it as easy for newcomers, but please feel free and update me if something is written complicated.

After you understand up to the macros, you can try yourself to understand the xor macro, which most of the library is built based on it: https://github.com/tomhea/flip-jump/blob/fe51448932e78db7d76...

[platz]

How is a jump realized by Not Gates?

[tomhee]

I dont think that the jump can be realized by NOT gates, but it's essentially "where to find the next NOT command". The jump is indeed a crucial part of the language, as it allows going back, and especially to make self-modifying code.

[Jerrrry]

I'm guessing by not jumping into a terminating/ halting NOOP.

The logic is within the branching.

[jumploops]

AND, OR, NOT - pick 2

[sroussey]

NOR - pick 1

[dang]

Looks like we banned you and this domain because of the egregious vote manipulation and bogus comments at https://news.ycombinator.com/item?id=34856792.

That was a long time ago, though, and the project is interesting enough, so I'm going to assume you've learned your lesson and unban you. Please stop using multiple accounts for this though!

[tomhee]

Thanks man, I appreciate it.

[jimbob45]

Dang, I have to know what triggered you to say this. It’s not the same user account so you would have had to have recognized the URL and written based on that.

Do you keep notes on each astroturfed submission and auto-trigger reposts to notify yourself? Or did you just happen to recognize this? 20 minutes from his post to your comment is absurdly good moderation.