C implementation of Tic-Tac-Toe in a single call to printf

simias 5 years ago |

Oddly 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.

hugomg 5 years ago | |

If you are curious, this is what the resulting format string looks like after expanding all the macros:

https://gist.github.com/hugomg/73e91ebca7ced3c5c6f955e9e830b...

coliveira 5 years ago | |

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.

ufo 5 years ago | | |

Another reason is that this was intended as an IOCCC submission and IOCCC has a file size limit.

russfink 5 years ago | |

One time, I had to maintain C code That somebody had #define'd to look like FORTRAN. It was impressive.

gamegoblin 5 years ago | | |

Much of the original Bourne shell was written in C that had been macro'd to look like Algol [1].

E.g.

    /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(

[1] https://research.swtch.com/shmacro

bondarchuk 5 years ago | | |

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?

gmfawcett 5 years ago | | |

Might have been this. The style is usually attributed to Arthur Whitney:

https://code.jsoftware.com/wiki/Essays/Incunabulum

simias 5 years ago | | |

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.

TeMPOraL 5 years ago | | |

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.

Gene_Parmesan 5 years ago | | |

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.

keitmo 5 years ago | | |

"The determined Real Programmer™ can write FORTRAN in any language."

a1369209993 5 years ago | | |

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.)

http://www.catb.org/jargon/html/story-of-mel.html

codezero 5 years ago | | |

One time, I had to maintain FORTRAN code. Much of it was still in FORTRAN 66.

voldacar 5 years ago | |

The macros are a form of data compression. Otherwise the string would be absurdly huge

mci 5 years ago |

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

lifthrasiir 5 years ago | |

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.

[1] https://www.ioccc.org/2012/kang/

[2] https://news.ycombinator.com/item?id=2748402

Luc 5 years ago | |

‘Strongly prefer‘ != disqualification

andi999 5 years ago | | |

'Strongly prefer'== banned for life

mjburgess 5 years ago |

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.

yokohummer7 5 years ago |

> %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?

Someone 5 years ago | |

One use is aligning outputs:

  char *prefix = "example";
  char *line1 = "line 1";
  char *line2 = "line 2";
  printf("%s: %n%s\n", prefix, &n, line1);
  printf("%*s%s\n", n, "", line2);

will output

  example: line 1
           line 2

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)

quietbritishjim 5 years ago | | |

> 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);

JoshTriplett 5 years ago | | |

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.

Someone 5 years ago | | |

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)

JanisL 5 years ago | | |

This makes me wonder if there's some sort of Unicode equivalent for this?

7786655 5 years ago | | |

wcwidth()

JanisL 5 years ago | | |

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

tgv 5 years ago | | |

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);

MertsA 5 years ago | | |

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.

zlynx 5 years ago | |

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.

MertsA 5 years ago | |

Well the fun use is using it to exploit printf format string vulnerabilities. Microcorruption has a fun level involving that IIRC.

CamperBob2 5 years ago | |

Normally you'd use %n with input functions like scanf(), not printf().

bawolff 5 years ago | |

To support format string vulnerabilities! /s

lukaszdk 5 years ago |

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.

[1] https://nicholas.carlini.com/

learnstats2 5 years ago | |

>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.

commandlinefan 5 years ago | | |

Ha, if I had a longer weekend my wife would demand I use it taking her out.

learnstats2 5 years ago | | |

Do you not like spending time with your wife? That seems a shame.

LoSboccacc 5 years ago | | |

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.

DaiPlusPlus 5 years ago | |

> 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...).

joaizn 5 years ago | |

>with no strings attached

What about char arrays?

codegladiator 5 years ago |

> in a single call to printf

> while(*d) printf(fmt, arg)

How's that a single call ?

zeroimpl 5 years ago | |

It also turns out “arg” is a macro which calls scanf. Would be better if they described it more realistically.

usr1106 5 years ago | |

> 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.

lelf 5 years ago | | |

printf once in a while

RoutinePlayer 5 years ago | | |

"a call to printf in a while loop"

haberman 5 years ago |

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()."

sfoley 5 years ago | |

Should be "an infinite number of printf()s and scanf()s".

identity0 5 years ago | | |

Would you say that an infinite loop has infinite lines of code?

yjftsjthsd-h 5 years ago | | |

It has infinite instructions, yes. (Well, "unbounded" or "endless", if we're being picky.)

identity0 5 years ago | | |

No it doesn’t. It has finite instructions for the loop body, and then one jump instruction for the loop.

blunte 5 years ago |

Title correction: Tic Tac Toe written almost entirely in #defines.

kzrdude 5 years ago | |

And executed in the Printf virtual machine

JanisL 5 years ago | |

While this is no doubt true the (ab)use of printf is really where the magic happens though

eternauta3k 5 years ago |

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.

f2f 5 years ago |

thanks. now i have nightmares.

yenwodyah 5 years ago |

It isn't really a "single call" to printf if it's in a while loop, is it?

phire 5 years ago | |

That's what you are getting hung up over?

There is a call to scanf in the middle of the arg #define

rosstex 5 years ago |

If you're reading these Nicholas, thanks for your super help in CS 161 Spring 2016!

peter_d_sherman 5 years ago |

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"

phkahler 5 years ago |

I thought the program was going to consist of only the call to printf(). But alas, that is inside a while loop.

staycoolboy 5 years ago |

Excellent obfuscation. It ticks all the boxes:

- esoteric modes of operation of a common function

- truly novel use of macros

- visibly beautiful

avidphantasm 5 years ago |

I am jealous of people who have time to do things like this.

thr0w__4w4y 5 years ago | |

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.

yitchelle 5 years ago |

Love the attempt the blindside the reader with funky formatting showing "%N".

TapamN 5 years ago | |

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.

techbio 5 years ago |

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” :)

anta40 5 years ago |

ttt.c(25): fatal error C1091: compiler limit: string exceeds 65535 bytes in length

Aaargghhh MSVC 2019 doesn't like this :(

hebetude 5 years ago |

fake news, single call to while

tikej 5 years ago |

Looks a bit like scientific codes from 3 decades ago :)

mariomatos 5 years ago |

Some advanced clickbait we have here.

encom 5 years ago | |

Nah.

Dennis Ritchie HATES him. Program like a pro with this one weird trick! You won't believe what happens!

That's proper bait.

qllp100 5 years ago | | |

Hence advanced bait. printf() is called in a while loop, so it is hardly a single call.

taspeotis 5 years ago | | |

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.

quietbritishjim 5 years ago | | |

Where?

    int main() {
        while(*d) printf(fmt, arg);
    }

shawnz 5 years ago | | |

On line 57: https://github.com/carlini/printf-tac-toe/blob/master/printt...

mariomatos 5 years ago | |

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.