"Code’s effects can surprise everyone, including the coders."
October 16, 2019 4:31 AM   Subscribe

Slate takes a look at some of the most important pieces of code (via Kottke)
posted by Stark (38 comments total) 48 users marked this as a favorite
 
That was wonderful. Thank you.
posted by KaizenSoze at 4:53 AM on October 16, 2019


"DONT DO POODOO. DO BAILOUT."

Who among us wouldn't prefer bailout?
posted by jquinby at 5:27 AM on October 16, 2019 [9 favorites]


Being pedantic for a moment, operator error was not necessary to trigger the deadly Therac-25 bug.

While the article does correctly note that the machine's overreliance on software was the root-cause of the accidents, the secondary and tertiary causes were also software bugs (hence why the software-dependant design was a mistake. The operators of the machine, as far as I know, did nothing wrong.
posted by schmod at 5:40 AM on October 16, 2019 [4 favorites]


The 737 Max software issue wasn't entirely the software's fault, as I understand it; rather, the root cause was cheaping out on hardware design and not putting enough redundant angle-of-attack sensors on the machine.

Any sane design would have at least three sensors, so if one flakes out the others can outvote it. But the 737 Max has only two, so if one fails it's impossible for the software to tell which of the mismatched readings to trust. Best it can do is just throw its hands up and complain to the pilot if it finds that its sensors don't agree with each other.

Still, that's better than blindly trusting only a single sensor and flat out ignoring the other one all the time, which as I understand it is what the original version did. The only way I can make sense of that design is to guess that it was originally built on the assumption of receiving inputs from three sensors, one of which would be held in reserve as a backup and only checked if the other two disagreed. I'm betting that if I were to crawl through a 737 Max wiring diagram I'd find an AoA connector somewhere with three sets of input pins, two of which get jumpered together by the wiring loom.
posted by flabdablet at 5:49 AM on October 16, 2019 [6 favorites]


Thanks for posting this. Worth the read just to learn about the Perl shirt (and the subsequent read on “illegal prime numbers”).
posted by klausman at 6:29 AM on October 16, 2019 [2 favorites]


and nothing on the Manchester SSEM, of course. While ENIAC operators were mucking about with hard-wired logic and hundreds of thousands of punch cards, Manchester was running stored programmes — admittedly very small ones with extreme limitations (7 instructions, 32 words total) — with digital output. ENIAC was a dead end, and almost nothing that came from it is recognizable in today's technology.
posted by scruss at 6:43 AM on October 16, 2019 [4 favorites]


Bitcoin
Date: 2008
The code that inspired confidence in a type of currency that wouldn’t exist without it


For a certain value of "confidence", I suppose...
posted by Thorzdad at 7:10 AM on October 16, 2019 [7 favorites]


extreme limitations (7 instructions, 32 words total)

32 words ought to be enough for anyone
posted by thelonius at 7:11 AM on October 16, 2019 [11 favorites]


Interesting, but the usual quickly-researched listicle. The part about null-terminated strings was particularly overblown. Whatever low-level representation you choose for a data structure, it will be possible to misuse it. Remember that “less power than a greeting card” factoid earlier in the article? You can’t afford to check everything all the time if you’re running on a greeting card and so efficient-and-risky economically buried slow-and-correct over the years. The same thing happened in computer architecture which is why it’s so hard to implement a safe high-level language.

We’re now at a place where we don’t have to worry so much about cycles and now it’s designer and programmer time and toolchains that encourage the flow of bugs.
posted by Gilgamesh's Chauffeur at 7:12 AM on October 16, 2019 [2 favorites]


We’re now at a place where we don’t have to worry so much about cycles

Folks have been saying that for decades. This is why Wirth's Law is a thing.
posted by flabdablet at 7:25 AM on October 16, 2019 [3 favorites]


I really loved this! Some pieces I recognized, others I didn't at all.

My addition would be Bill Atkinson's MacPaint code. To implement MacPaint, Atkinson also wrote the fast graphic routines that powered MacPaint and the rest of the the original Macintosh's GUI—QuickDraw. QuickDraw was an almost miraculous tool in terms of what it made possible, and it was pretty valuable to the Mac project.

The design of MacPaint echoes through drawing software right up to today—his "marching ants" visual effect of indicating a selected region has become a nearly-universal interface convention, for example.
posted by Sokka shot first at 7:52 AM on October 16, 2019 [7 favorites]


Worth the read just to learn about the Perl shirt

I had one of those shirts...I flew back and forth to Japan many times with it in the 90’s. Never got stopped for wearing it, though.
posted by spacewrench at 7:59 AM on October 16, 2019 [3 favorites]


I ... may have accidentally caused the robots.txt protocol to be invented, back in 1993 when I was teaching myself Perl and wrote a 'bot that did a depth-first traversal of the web. Not recognizing that running tests iteratively from the same starting point, when the starting page in question was sitting on a server at the wrong end of a 14.4k leased line (and I was using something a whole lot faster) was maybe a bad idea ...

Boy, did I get schooled! I got schooled so well that everyone else had to learn the same lesson for the next 25 years!
posted by cstross at 8:22 AM on October 16, 2019 [41 favorites]


I'd add the TCP congestion collapse of 1985. The lore is that the whole Internet was falling over, dropping from speeds of 32 Kbps (lol) to 40 bps. Everyone panicing. Van Jacobsen and Mike Karles looked at the problem, stared at log files, stared at code, stroked their metaphorical beards for six months. And then came up with a three line patch to the standard TCP stack that fixed everything. Three lines of code! Basically the invention of TCP Slow Start.

The reality is a bit more complex and documented in Van Jacobson's SIGCOMM paper. But it's still a great example of how a very thorny problem in a very complex network system can sometimes be fixed with just the tiniest change applied in the right place.
posted by Nelson at 8:24 AM on October 16, 2019 [12 favorites]


> The part about null-terminated strings was particularly overblown.

That contribution was from jwz, so it might come from a place of cantankerousness but probably not ignorance. And as a design decision with consequences it seems more relevant to the subject than a shell script exploit that's clever but not useful (for either good or ill).
posted by ardgedee at 8:31 AM on October 16, 2019 [5 favorites]


The entry about the fork bomb seems particularly weak, as it:
  • claims that code with no ability to propagate from one host to another is a "virus"
  • includes something that is at best a parlor trick in a list of "most significant" code
  • fails to mention the clearly superior "Swedish Chef" form of this trick:
for/*k*/(fork(); fork(); fork()) fork();
posted by sourcequench at 8:45 AM on October 16, 2019 [17 favorites]


There's a kind of top-row purity and quasi-symmetric rhythm to +()(+&+&)&+ that makes it my favourite variant.
posted by flabdablet at 9:19 AM on October 16, 2019 [1 favorite]


sourcequench: "The entry about the fork bomb seems particularly weak

yep - With sane ulimits, fork bombs are boring.
posted by namewithoutwords at 9:25 AM on October 16, 2019 [1 favorite]


They can be a pretty exciting way to find out whether the ulimits are, in fact, sane. On loads and loads of POSIX-compliant systems, even in 2019, they're absolutely not.
posted by flabdablet at 9:26 AM on October 16, 2019 [1 favorite]


I'll say it again: iTunes for Windows.

The sales of iPods exploded after this, paving the way for the iPhone.
posted by JoeZydeco at 10:29 AM on October 16, 2019 [3 favorites]


A little sad to see Monte Carlo simulations make the list. I know statistics and probability is hard, but every time I see someone say "I made a Monte Carlo simulation" in place of "I determined the proper expression and then evaluated it," it makes me die a little inside.
posted by explosion at 10:33 AM on October 16, 2019 [4 favorites]


My favourite Monte Carlo simulations are the ones where the proper expression turns up in the code of the sim as something for evenly-distributed random numbers to get tested against.
posted by flabdablet at 10:40 AM on October 16, 2019 [6 favorites]


Most interesting to me, though hardly the most important:
Fast Inverse Square Root, initially attributed to Carmack, the search for the original author turned into a sort of historical who’s-who of computer graphics.

Binary Space Partitioning for efficiently determining potential visible set in a pre-sorted back-to-front list for any point in a game map (WP has a passable entry and there’s Mike Abrash’s chapter covering Quake’s rough implementation of Seth Teller’s thesis but I can’t find a link that fully captures the jaw-dropping elegance of this one - the first time I fully got it is still the most profound “holy shit” seeing-the-face-of-god-type moment I’ve ever had).

Signed Distance Fields Chris Green @ Valve’s classic on crisp, efficient rendering of text/vector art in 3D environments.

Ken Perlin’s Improved Perlin Noise. Link goes to a solid writeup, original source is here, which includes a link to the Siggraph paper.

Advanced Cave Culling Algorithm Mojang coder Tommo’s 2-entry blog detailing how Minecraft computes potential visible sets within interactive voxel environments, specifically covering how the mobile port was made feasible. Includes some cute interactive visualizations.

There are a bunch of others but those are ones I immediately thought of when I saw the title.
posted by Ryvar at 10:45 AM on October 16, 2019 [11 favorites]


Great read. My one beef: The Apollo 11 computer is a great example of elegant programming. Clean, tight, efficient programming within hard, non-negotiable constraints is, to me anyway, the Jedi level of programming.
posted by prepmonkey at 10:46 AM on October 16, 2019 [5 favorites]


I'd also add Michael Abrash's inner loop for Quake texture mapping, which used parallel floating-point operations to get 40 frames/second at 640x400 on a Pentium/100.
posted by RobotVoodooPower at 10:47 AM on October 16, 2019 [4 favorites]


One addition I would make: VisiCalc (which begat Lotus 1-2-3 which begat Excel). I think you can make the case that spreadsheets turned computers from something hobbyists and academics/scientists would use into something that the wider business world would use.
posted by mhum at 10:49 AM on October 16, 2019 [14 favorites]


Binary Space Partitioning

is super nice. So are k-d trees.
posted by flabdablet at 10:52 AM on October 16, 2019 [1 favorite]


Clean, tight, efficient programming within hard, non-negotiable constraints is, to me anyway, the Jedi level of programming.

It's the most fun to do, by a very wide margin. Pretty rare to find it being done commercially, though, especially now that you can buy an ARM for well under what a 6805 used to cost.
posted by flabdablet at 10:56 AM on October 16, 2019 [1 favorite]


A little sad to see Monte Carlo simulations make the list. I know statistics and probability is hard, but every time I see someone say "I made a Monte Carlo simulation" in place of "I determined the proper expression and then evaluated it," it makes me die a little inside.

Well how the hell else am I going to figure out that pi = 3.15?
posted by invitapriore at 10:59 AM on October 16, 2019 [4 favorites]


explosion: A little sad to see Monte Carlo simulations make the list. I know statistics and probability is hard, but every time I see someone say "I made a Monte Carlo simulation" in place of "I determined the proper expression and then evaluated it," it makes me die a little inside.

I mean, if you've got closed-form expressions for the effects of nuclear warhead detonations under various conditions and configurations, I'm sure the fine scientists of Los Alamos National Laboratory would love to hear about it. My understanding is that a significant portion of present-day nuclear testing is still via simulation.
posted by mhum at 11:05 AM on October 16, 2019 [11 favorites]


Good post.
posted by Wolfdog at 11:06 AM on October 16, 2019 [1 favorite]


how the hell else am I going to figure out that pi = 3.15?

You're not, because it's actually 3.05 as proved by Scientific Experiment.
posted by flabdablet at 11:12 AM on October 16, 2019 [4 favorites]


If you have a better way to locate your cat after it ran away in a wooded area of Monaco, I'd like to ... oh wait, that's a Monte Carlo Tree Search.
posted by RobotVoodooPower at 1:16 PM on October 16, 2019 [5 favorites]


> Worth the read just to learn about the Perl shirt

FWIW my "This Shirt is a Munition" tshirt is still in my closet and I even wore it recently. IT's similar to this one, though I don't recall the "1995 JKF/JO" part (and would have to walk all the way to my bedroom to check it out for sure, which is far too much effort).

I thought perhaps I could find the record of purchase in my email but no luck. I did find this related item from March 28th, 1996:
==================================
[3] Court Dismisses Case Challenging Export Controls
==================================

A federal district court in Washington, D.C. on March 22 dismissed a case brought by privacy activist Phil Karn challenging the constitutionality of export controls on cryptography. In February 1994, Karn applied for a license to export cryptographer Bruce Schneier's book "Applied Cryptography." The State Department approved the license, but shortly thereafter, denied Karn's request for a license to export a disk set which contained text files of different cryptographic algorithms that were printed in the book. Karn filed suit, claiming that the denial violated the Administrative Procedures Act and the First and Fifth Amendments to the Constitution.

The court rejected all of Karn's claims, stating that the case presented a "political question for the two elected branches" to decide. It found that the Arms Export Control Act precluded judicial review of administrative decisions concerning the applicability the "Munitions List," a regulatory listing of items that may not be exported.

On the First Amendment claim, the court held that the restrictions were "content neutral" because the government is "not regulating the export because of the expressive content of the comments and or source code, but instead [is] regulating because of the belief that the combination of encryption source code on machine readable media will make it easier for foreign governments to encode their communications."

More information on the case and on export controls is available at:

http://www.epic.org/crypto/export_controls/
That link to epic.org from the email is still working 23.5 years later, so hurray for them (how many other pages >20 years old are still online?)
posted by flug at 5:48 PM on October 16, 2019 [3 favorites]


>The part about null-terminated strings was particularly overblown

The alternative is to store a length value at the start of a string. But what is the maximum allowable string length? At that time, most languages used a single byte for the length, allowing 255 character strings. Strings that short would be less than optimal today.

Ritchie's decision was remarkably prescient!
posted by monotreme at 7:57 PM on October 16, 2019


The alternative is to store a length value at the start of a string. But what is the maximum allowable string length?

That's an alternative. There are plenty of other ways to do it.

The way Applesoft BASIC did it was to represent each string as a three-byte structure, with one byte for the length and the other two for a memory pointer to the start of the string text. On more capable machines than an Apple II you could go the same way, but using full-sized machine words for both those fields. This would let strings be as large as the addressing range of the machine.

Separating the string's metadata from its text in this way has a number of advantages. String variables become relatively small fixed-length items, about the same size as floating-point numbers and potentially manipulable using the same machine registers used for floating-point. Creating substrings becomes very very fast, since none of the underlying text needs to be moved.

The problem of parsing a machine string from a stream of arbitrary input text, where the length of the input is not known in advance, remains. However, once your design requires a library-managed text pool where all the on-demand text buffer management happens, the centralization of all that management code inside the strings library allows it to be made very robust; you don't get buffer overflow opportunities scattered at random all over the codebase.

String concatenation is also still relatively slow, though no slower than it would be with a null-terminated string representation. And garbage management for the text pool needs careful design (it didn't get that in Applesoft BASIC, which is why programs written in that language would occasionally freeze for a second or two as the BASIC interpreter defragmented the pool).

I do rather suspect that null-terminated strings were only ever a thing because (a) the PDP-11 macro assembly language has a directive that generates them and (b) you can copy one using a loop consisting of only two PDP-11 machine instructions, which is almost irresistibly cool.
posted by flabdablet at 11:45 PM on October 16, 2019


OK, so I have finally understood how Fast Inverse Square Root works, and it's rather wonderful.

Similar pleasures are to be found in superoptimization. The original paper is definitely worth a read.
posted by flabdablet at 12:16 AM on October 17, 2019 [3 favorites]


Oh, man, superoptimizer. I did a presentation about superoptimizer in my undergraduate algorithms class, and may have actually cackled when explaining its performance as m^n, where m is the number of available instructions in your chipset (so pretty big unless you're on a RISC processor), and n is the upper bound on how long you want to wait for your optimization to run. I cooked up a quick implementation that ran on the UltraSPARC the CS department's main server ran on, and let it run on something trivial like "multiply the value in r0 by a constant," printing the less-than-optimal solutions it found as it chugged along. The professor made me kill it after about five minutes, when it became clear that I had put the "brute" back in "brute force."

That might still be my favorite CS paper ever.
posted by Mayor West at 5:45 AM on October 17, 2019 [6 favorites]


« Older Superman Smashes the Klan   |   Daily Newer »


This thread has been archived and is closed to new comments