C implementation of Tic-Tac-Toe in a single call to printf
github.comOddly enough I find that the #define macro soup detracts from the performance here. I was rather unimpressed at first because obfuscating C code by just #define'ing a bunch of code is a trivial and rather uninteresting way to write unreadable code. Of course you can make any arbitrary code look like a printf call with enough macros!
But it's actually a lot more clever than that.
I feel like this would be a lot more impressive if it was written in simple and clear C since then you'd see that there really isn't any tic-tac-toe logic being explicitly implemented the way you'd expect.
If you are curious, this is what the resulting format string looks like after expanding all the macros:
https://gist.github.com/hugomg/73e91ebca7ced3c5c6f955e9e830b...
The reason he had to use macros is that the actual formatting string is huge and difficult to understand. In this case, macros really serve a useful purpose, instead of just obfuscating code.
Another reason is that this was intended as an IOCCC submission and IOCCC has a file size limit.
One time, I had to maintain C code That somebody had #define'd to look like FORTRAN. It was impressive.
Much of the original Bourne shell was written in C that had been macro'd to look like Algol [1].
E.g.
[1] https://research.swtch.com/shmacro/usr/src/cmd/sh/mac.h: #define IF if( #define THEN ){ #define ELSE } else { #define ELIF } else if ( #define FI ;} #define BEGIN { #define END } #define SWITCH switch( #define IN ){ #define ENDSW } #define FOR for( #define WHILE while(Quite some time ago I saw a piece of C code (probably linked from here) in APL style, I have been trying to find it since, does anyone know what I mean?
Might have been this. The style is usually attributed to Arthur Whitney:
I've had to deal with code like that, only poorly mimicking Lisp instead: `#define unless(_x) if (!(_x))` etc...
One of my favourite accidental features in Rust is that macros are so annoying and cryptic to write that people think twice before abusing them.
I understand the temptation. I keep catching myself on writing `unless( ... )` in C++ every couple days, and I've considered adding a macro for it, but ultimately decided against it, as the rest of the team would not understand why I need it.
Wouldn't be surprised if that was intentional, actually. The idea of making syntax a little unwieldy for things that you should really think twice before using is not a new one.
"The determined Real Programmer™ can write FORTRAN in any language."
Real Programmers write machine code in any language, thank you very much. (Which TFA rather nearly is, actually, though it's a bit macro-assemblery for a proper example.)
One time, I had to maintain FORTRAN code. Much of it was still in FORTRAN 66.
The macros are a form of data compression. Otherwise the string would be absurdly huge
I am afraid that the author has disqualified himself by publishing the source code before the judging of IOCCC 2020 is over. See catch 22 in the rules: "The judges STRONGLY prefer to not know who is submitting entries to the IOCCC."[1] Even the winners are asked not to publish the code until it is available on the IOCCC web site.[2]
[1] https://ioccc.org/2020/rules.txt [2] Personal communication
It is true that publishing the source code this early is risky, but submitting the code that has been already published is not prohibited by its own. My winning entry (2012/kang [1]) was in fact published independently and was even on HN [2]. I'm pretty sure that this is not the only occurrence, having seen some winning entries trending on Twitter before the public announcement.
‘Strongly prefer‘ != disqualification
'Strongly prefer'== banned for life
Relevant talk on the motivation for printf-programming:
https://www.usenix.org/conference/usenixsecurity15/technical....
Very interesting. Roughly, that the existence of Turing-complete functions within programs creates a fundamental vulnerability that even rigid control over the control flow of a program cannot avoid.
> %n takes a pointer and writes (!!) the number of bytes printed so far.
> Okay, everyone probably knows this. Let's get a bit more advanced.
Ok, but I didn't know about that. What's the use?
One use is aligning outputs:
will outputchar *prefix = "example"; char *line1 = "line 1"; char *line2 = "line 2"; printf("%s: %n%s\n", prefix, &n, line1); printf("%*s%s\n", n, "", line2);
That’s a bit more robust than using strlen(s)+2, where you have to keep that magic constant 2 in sync with ": ". Moving ": " to a variable and using strlen(s)+strlen(separator) would fix that, though (at the price of speed, unless you’ve a compiler that optimizes that away)example: line 1 line 2> That’s a bit more robust than using strlen(s)+2
strlen wouldn't even be an option if you were formatting something that's not a string e.g.
int n; int prefix_num = 23; char *line1 = "line 1"; char *line2 = "line 2"; printf("example %d: %n%s\n", prefix_num, &n, line1); printf("%*s%s\n", n, "", line2);This only works if you're not dealing with Unicode, where the number of bytes, the number of characters, and the width of those characters can all vary.
You don’t need Unicode for that. It also requires you use a monospaced font.
I think the feature predates that and Unicode, though. But even then, it fails if you underline text the way it was done at the time, either by using backspace and underline characters or by using termcap (https://en.wikipedia.org/wiki/Termcap)
This makes me wonder if there's some sort of Unicode equivalent for this?
wcwidth()
Thanks, I wasn't aware of this. Here's a man page for anyone else that was interested: https://man7.org/linux/man-pages/man3/wcwidth.3.html
I'd never heard of %n, but I use printf's return value (the number of bytes written) for this kind of purpose, so
n = printf("%s: ", prefix); printf("%s\n", line1); printf("%*s%s\n", n, " ", line2);Yeah but the difference is that you can use %n wherever you need it in the format string. Depending on what arguments come after it figuring out the length of the printed arguments might not be trivial whereas with printf, it already has to keep a count of it during execution in order to return it at the end so it's easy to add support for it.
I seem to recall using it to auto-adjust column widths.
And we did something with it involving string translations. Since we didn't control the translated format string we couldn't just count the characters in the source code.
But it's been a really long time and I don't recall the details.
Well the fun use is using it to exploit printf format string vulnerabilities. Microcorruption has a fun level involving that IIRC.
Normally you'd use %n with input functions like scanf(), not printf().
To support format string vulnerabilities! /s
This is just crazy and I love it <3
From a description on the author's website[1] of a Doom clone written in 13k of JavaScript.
> Until recently all content on this website was research, and while writing papers can be fun, sometimes you just need to blow off a little steam.
I think more companies should allow for their employees to have some plain old fun with no strings attached on a regular basis.
>I think more companies should allow for their employees to have some plain old fun with no strings attached on a regular basis.
Maybe we could call this additional 'holiday pay' or a longer 'weekend' and mandate it through law so that everyone benefits.
Ha, if I had a longer weekend my wife would demand I use it taking her out.
Do you not like spending time with your wife? That seems a shame.
a law would be government overreach, but the idea is solid and the results tangibles; should be within the realm of a union regulations, if we ever manage to get one going.
> I think more companies should allow for their employees to have some plain old fun with no strings attached on a regular basis.
Nicholas Carlini's resume is crazy-insane and he's highly desirable, so of course Google Brain is going to lend him far more flexibility than Google Analytics would have with a recent college-hire, or at the other end of the supply/demand distribution: the working flexibility Amazon would afford a warehouse employee (if they aren't a contractor...).
>with no strings attached
What about char arrays?
> in a single call to printf
> while(*d) printf(fmt, arg)
How's that a single call ?
It also turns out “arg” is a macro which calls scanf. Would be better if they described it more realistically.
> How's that a single call
syntactically it is. But it's not a very clear description. So how would you describe that single call location getting executed in a loop so everybody understands what is really meant? A single line of code is worse.
printf once in a while
"a call to printf in a while loop"
In case you're wondering (like me) how you'd get input from printf():
> We ab^H^Huse [the Turing-completeness of printf()] to implement a the logic of tic-tac-toe entirely within this one printf call (and a call to scanf() to read user input).
So it should be "one printf() and one scanf()."
Should be "an infinite number of printf()s and scanf()s".
Would you say that an infinite loop has infinite lines of code?
It has infinite instructions, yes. (Well, "unbounded" or "endless", if we're being picky.)
No it doesn’t. It has finite instructions for the loop body, and then one jump instruction for the loop.
Title correction: Tic Tac Toe written almost entirely in #defines.
And executed in the Printf virtual machine
While this is no doubt true the (ab)use of printf is really where the magic happens though
I was expecting the tic-tac-toe to be written in machine code in an array, and printf would smash the stack to jump to it.
thanks. now i have nightmares.
It isn't really a "single call" to printf if it's in a while loop, is it?
That's what you are getting hung up over?
There is a call to scanf in the middle of the arg #define
If you're reading these Nicholas, thanks for your super help in CS 161 Spring 2016!
Holy Crap Batman!
Never in a million years would I have thought that printf() was Turing-Complete -- and yet, here's the proof that it is...
And then there's this related paper:
https://www.usenix.org/system/files/conference/usenixsecurit...
Page 175: "Printf is Turing-complete"
I thought the program was going to consist of only the call to printf(). But alas, that is inside a while loop.
Excellent obfuscation. It ticks all the boxes:
- esoteric modes of operation of a common function
- truly novel use of macros
- visibly beautiful
I am jealous of people who have time to do things like this.
I hear you on that. But for me, the jealousy dissipates quickly once I realize that even if I had /lots/ of time, I don't think I would come up with this.
Love the attempt the blindside the reader with funky formatting showing "%N".
That's not too unusual for IOCCC entries. Of the top of my head, there's a flight simulator shaped like an airplane, and an addition routine shaped like a full-adder.
A more subtle touch is that the #defines spell out NOUGHTs AnD CRoSSES.
I’m impressed with the aesthetics, and humor: formatted ‘fmt’, “printf oriented programming”...
Suggests in my mind, somehow, thought I’d share: “CTRL-F oriented programming” :)
ttt.c(25): fatal error C1091: compiler limit: string exceeds 65535 bytes in length
Aaargghhh MSVC 2019 doesn't like this :(
fake news, single call to while
Looks a bit like scientific codes from 3 decades ago :)
Some advanced clickbait we have here.
Nah.
Dennis Ritchie HATES him. Program like a pro with this one weird trick! You won't believe what happens!
That's proper bait.
Hence advanced bait. printf() is called in a while loop, so it is hardly a single call.
I don’t want to jump on the title hate bandwagon - what the author has done is definitely creative and clever and this discussion detracts from it - but it also uses scanf.
Where?
int main() { while(*d) printf(fmt, arg); }Ah, well spotted, thanks. I didn't think it was fair to call the title click bait just because it used a while loop to drive the calls to printf, but also including a scanf call is definitely not in the same spirit.
Alas, it's technically difficult to get input from the user using printf.
If you’re willing to lose almost all portability, I think you could read a value from an I/O port, pass that to printf, use that as the field width for a string to print, count the character length of the resulting string using %n to move it into a variable, and then backspace over that to prevent the output from dirtying your output. You could only use the results in a subsequent call to printf, though.
Of course, just hiding an assignment in a printf argument would be much easier, but wouldn’t be fun.
Of course, that would lose lots and lots of portability, and you could, likely, only get it to work on systems that don’t do memory protection between processes, and then, not all of them.
I guess it would not be very hard to use this trick to have printf read joysticks on many micro’s from the 1980’s.
In that case it might just be easier to ROP your way to scanf.
Hmm that is a good point :-)
Well, I got downvoted. I should have mentioned that I meant this in a good way. My account is new and I have since read the rules in the welcome page. But think about it, a whole game implemented only in a print statement? Wow, that can’t be real. And it is at the very 1st place of the top posts. I clicked on it expecting a cool article explaining something interesting, but no. It is the implementation. So, well done.