Hacker Timesnew | past | comments | ask | show | jobs | submitlogin

How did we end up with printf - within a loop - being Turing-complete? Was it designed that way from the beginning? Were new features added over time until we got there?


Having something Turing-complete is surprisingly easy, and it hides everywhere. The repository have a small document that explains how you can use printf() as a computer : it can performs additions, logical union and negation, which is enough.

It was unintentional, but Ken Thompson being Ken Thompson, can't be 100% sure.


List of examples: https://gwern.net/turing-complete

It was probably unintentional, yeah, I don't recall any mentions of early printf being overloaded to do stuff, nor is it clear why you would do that since you're using it in a much more convenient Turing-complete language already (C).


So there was no extension of the functionality over time, all the formats have been supported from day one?


The key features that is used here is the '%n' format specifier, that fetches a pointer as the next argument, and writes a character count back.

There is actually an interesting question here: was '%n' always in printf, or was it added at one point?

I took a cursory look at some old Unix source archives at TUHS: https://www.tuhs.org/cgi-bin/utree.pl

As far as I can tell from the PDP-11 assembly, Version 7 research Unix (relevant file: /usr/src/libc/stdio/doprnt.s) does not appear to implement it.

The 4.1BSD version of that file even explicitly throws an error, treating it as an invalid format specifier.

The implementation in a System III archive looks suspiciously similar to the BSD one, also throwing an error.

Only in a System V R4 archive (relevant file: svr4/ucblib/libc/port/stdio/doprnt.c) I found an implementation of "%n" that works as expected.

I guess it was added at some point to System V and through that eventually made it into POSIX?


I think it was first introduced in 4.3 BSD Tahoe (released June 15, 1988): https://www.tuhs.org/cgi-bin/utree.pl?file=4.3BSD-Tahoe/usr/...

This was an update to the earlier 4.3 BSD (1986) which still implemented printf() in VAX assembly instead, and doesn't support the %n feature.

So %n may have originally been implemented in 4.3 BSD Tahoe and made its way into SVR4 subsequently.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: