Introduction
Adam: Hello, and welcome to CoRecursive. One piece of feedback I get on the podcast is about an episode I did in the past that was a little bit different called Don and Adam Discuss Folds, where the guest was my neighbor and former colleague, Don. And we talked about folds and recursion and stuff.
People seemed really liked that episode. So, I’m going to do something similar. I haven’t quite figured out how to start this episode off. So, why don’t you state your name and what you do?
Don: My name is Donald McKay. And I’m a Senior Developer for the B Online Learning Limited.
Adam: Despite the fact that we live like not that far away from each other, I haven’t seen you in some time.
Don: No, I haven’t seen any other human beings, aside from people that work at the grocery store for a very long time.
Adam: Yeah, just COVID, just sheltered in place and seeing nobody.
Don: Yeah. You know what? There was one point where I was driving by, and I thought to myself, does Adam even still live there? Like, maybe you move, maybe you got a different place, right?
Adam: Yeah.
Don: And I saw the… Was it the broken Christmas lights? And I’m like, “Yeah, he hasn’t taken those down, yet. They probably would have taken those down if they sold the house.”
Adam: Yeah, a normal person would have taken their Christmas lights down … by now.
The Cursed Computer Iceberge Meme
Adam: So, I found this thing online, and I sent it to you called The Cursed Computer Iceberg Meme, what did you think of this?
Don: There’s a lot of weird things to do with computers and programming in general.
Adam: Yeah, there totally is. So, let me describe this to you. So, I found it, I think on Hacker News. There’s a very large picture of an iceberg, where you can keep scrolling and see more and more of the iceberg. The further down you go, below the water, basically. And there’s various levels, like one is called above the water. One is called on the iceberg. One is below the iceberg and it keeps going down to the deep to the abyss. And all scattered around the various levels, are these terms that linked to various articles or Wikipedia pages or tweets about computing.
So, it could be things like, let me just read some falsehoods that programmers believe about time. No elegant solution to FizzBuzz exists. Chuck Norris is the HTML color, which is super interesting. Parsing Perl is undecidable. PostScript is turning complete. And it just keeps on going. The further down you go, the more obscure they are. I think they’re trying to say like,” Oh, you might have heard of X, like problems with names, but you’ve probably never heard about Perl being undecidable.” That’s like, three levels down the iceberg. It’s even more obscure.
So, this could be like a great source of interesting facts about computers. It could also be like just a great tool for gatekeeping in the world of computer programming, right?
Don: If you don’t know what… At least one of the things, or three of the things from below the waterline. We don’t want to talk to you.
Adam: Yeah. But I thought it was like there’s just so many interesting things in here. I thought this would be great if you pick some that are interesting, and then I pick some that are interesting. We’ll just explain them to each other. So, that’s the idea. Maybe, I’ll start with one. How’s that sound?
Don: Yeah.
Quines
Adam: So, this one I think this is near the top of the iceberg. So, this is a quine. Have you heard of a quine? It’s Q-U-I-N-E.
Don: I have not. I saw it on the list, but I have not heard of it.
Adam: Nice. Okay, so that’s perfect. So, a quine is a program that takes no input at all. And when you run it, it produces itself.
Don: Oh, okay.
Adam: So, that sounds strange, right?
Don: So, it’s like some kind of self-replication thing?
Adam: Yeah. So, it’s a self-replicating program. If you were to take it, like you take a Java program, and you run it at the command line, what it outputs to the standard out to your console is just like the exact contents of that Java program.
Don: Oh, okay.
Adam: It sounds super weird, right? And so, it’s named after this, Douglas Hofstadter. Yeah, he wrote Gödel, Escher, Bach, which is a book I read as a teenager, and he is very big into, I guess, like weird types of recursion. It’s not a book explicitly about computer programming, but it’s about a lot of loops and stuff, right?
Don: Okay. Yeah.
Adam: So, one of the things that was in his book was Hofstadter’s law where he said that, “A project will always take longer than you think it will even if you take into account Hofstadter’s law.” So, it’s like a recursion. Everything to do to with Douglas Hofstadter is like a weird, twisted a circle.
Don: He has a brand.
Adam: Yeah. So, quine is based on I think it’s called quine’s paradox. And quine’s paradox, this is going to be super confusing. Quine’s paradox is:
“yields falsehood when proceeded by its quotation”, yields falsehood when preceded by its quotation.
Which I don’t even think you can parse that. But the interesting thing because I have a couple… There’s several on this thing, they’re related to quine’s. The deeper you go down this thing, the more of these quine’s turn up.
Building A Quine
But how could you even write a program that outputs itself? It’s super tricky to think about. You want to print out a statement that’s in your program, but to print out that statement, you need to also have another statement…
Don: You have to… A statement that yeah, that prints it out. Yeah.
Adam: Yeah. And then, for the next… To handle printing out the statement that prints out that statement, you need to have another print statement. And it seems like it should be just an infinitely large program. But there’s kind of a trick to it.
So, imagine that you have a Java program. And then, so you say at the top, whatever the standard stuff is of creating a program. So, you’re like a public static quine, and then you say public, static main. And that’s kind of like, in the beginning of your program. And then you have two strings. So, you declare a string, we’ll call the first one, first. And then, we’ll call the second string, second.
Don: I’m with you so far.
Adam: Then, you have the bottom of the program. So, the bottom of the program, the first thing you do is you print out the first string. And then, the second thing you do is you print out the first string, but you put it into quotes. So, you’re kind of printing it out, as if it’s in a string itself. Then, the next thing you do is you print out the second string, but you print it out as if it’s in quotes. And then, the very last thing you do is you print out the second string itself. So, that’s kind of the structure of your quine. And then, the question is, what do you put in those two strings?
So, in the first string, you put everything that happened before those strings were declared, the top part of your program.
Don: Okay, yeah.
Adam: And then, in the second string, you put everything that happens in the bottom part of your program after your strings are declared. And then, you’ve kind of just turned the program inside out on itself. So, then, the program now contains the top part of itself, and then a string containing the top part of itself. And then, a string containing a bunch of print statements, and then the actual print statements. And then, when you run it, obviously, it’s going to recreate this.
So, it contains itself twice, once, like as a string. And once it’s not a string, and then it prints itself twice, but it prints itself twice from the strings.
Don: So, the contents of the code are actually in the strings?
Adam: Yeah, yeah. So, you actually have to write out the code, and then also put the code in the strings.
Don: That’s right, yeah.
Adam: So, everything is duplicated.
Don: Yeah.
Adam: And that way, you can print them out.
Why Create Quines?
Don: Is it a mental exercise? What’s the practical use of a quine? I guess, that’s where my brain is going.
Adam: Yeah, that is a good question. I have some further examples that maybe, we’ll get to that. But, yeah, I mean, one way to think of it is just as a puzzle. So, it’s like a puzzle like, how can you do this? How can you create something that prints itself? And some people have come up with cheats for it.
So, in languages, like JavaScript. In JavaScript, you can do eval. So, you can take like a string of code and just like evaluate it.
Don: Yeah.
Adam: So, that makes the problem a lot easier because you don’t… Any code, you can have it as a string, but also, run it in the same thing. Where in Java, you have to do it twice. There was also somebody… I’m just pulling all this from the Wikipedia page, which is surprisingly fascinating.
So, somebody submitted to a contest, what they called the world’s smallest self-producing program. And it was a blank file. And so, if you take a blank file, and you feed it to the C Compiler, it doesn’t know what to do with it. So, it produces no output, which is also a blank file, submit.
Don: But, yeah, that’s pretty clever.
Adam: Yeah, the minimal quine is actually nothing.
Quines as Arrows
Adam: Another thing they were saying is, if you imagine programs in terms of sets, if you have a program that takes in a number, and then adds two to it, right?
Don: Mm-hmm (affirmative).
Adam: You run it, you can pass it five, and returns at seven. So, you have that type of program, you can imagine as something that maps a number to that number plus two. So, on this side, you have all these numbers, and then you have like one, two, three. In the end of the program, you have like a three, four, et cetera.
So, it’s like maps one number to the next. And so, a lot of programs can be viewed like this. They take in two numbers, then it’s like two arrows go into the program, and then one number comes out on the other side. So, if you consider a quine in that kind of view, it’s basically, it takes a no input. So, it’s like, the arrow part takes in nothing. And then, what it returns is itself. So, it’s like an arrow that just points around to itself with no input and its only output is itself.
Don: That’s interesting. It’s definitely like one of those, kind of like, a mental stimulating puzzle, even trying to figure out how it works. It’s like, exercising the logic portions of your brain?
Adam: Yeah.
Don: Trying to figure out. Yeah.
Adam: Yeah, they had a Java example on the Wikipedia, which is kind of what I’m working off here accounting with you. And it took me a while to read it to understand like, “Wait a minute, how does this?” Then, I’m like, “Okay, yeah, it makes sense.” It doesn’t do anything besides what it does.
Don: Yeah, that’s the best of the step. When you look at it, your brain goes, “That’s cool.” And also, “What does it do? What is the function?” And I guess the function is, it’s just a fun little mental Rubik’s Cube for your coding brain, I guess.
Quines Self-Reproduce
Adam: Yeah, like creating one. And so, there’s also an aspect where a quine is like a life form like humans, like we reproduce, like we have children. We have our DNA, which is our code. And then, that is kind of produces another offspring. And if you’re like, some creatures are asexual reproduction, right?
Don: Mm-hmm (affirmative).
Adam: And they were a lot like a quine, I guess. They have code that makes up who they are, and then when they reproduce, they make a new copy of it. So a quine is in some sense, something like that. It’s reproducing itself, it has no other purpose. It doesn’t actually do anything. So, maybe, it’s more like a… I don’t know, a virus or I don’t know. It reproduces without reason, but…
Don: Yeah. The basic concept is true, for an analogy. But in biological organisms, they reproduce, but they don’t reproduce the exact copy.
Adam: Yes.
Don: There’s always that little bit of evolution built into it. So, there’ll be variations and mutations, and the thing that you get billions of copies down the road is going to be different than the one you started with.
Adam: It’s funny, you should mention that Don because this Wikipedia page is deep. That happens through like copying errors. Something tries to reproduce itself, and it makes a mistake, and that’s kind of evolution is powered by one mistake.
Don: By one way. I mean, not all of them are errors, right?
Adam: Well, aren’t they?
Don: Not all evolution is an error. Evolution is usually response to stimulus of the environment, how better to survive.
Adam: But at a very low level, what happens is, a copying error happens, and then if that copying error turns out to be advantageous, then that creature keeps reproducing. If it’s not advantageous, that creature not…
Don: Right. Yeah, yeah.
Adam: Yeah. So, it all starts out which is copying errors.
Don: Those error first. Yeah, so we’re basically exception based logic organisms.
Adam: Yeah, we just accumulate mistakes and eventually, hopefully, some of them are good mistakes.
Don: So, what you’re saying is human beings are a feature not a bug?
Adam: Exactly. But, so there is a something called a radiation hardened quine. So, the thing is that, the radiation in theory can flip bits on your computer, like a solar flare could hit your hard drive, and change some single bit. And if it changed something where you had written the quine to disk, it could change a single character to be slightly different. And in which case, that is evolution.
There’s a small copying error that will happen when that runs, because of whatever. So, somebody created radiation hardened quines, which encode themselves more than once, so that they can error correct on their output.
Don: So, they stopped the evolution?
Adam: I think that we have some redundancies, like in our DNA too, because we don’t want… We want to control the amount of copying errors that happen. We don’t want to just fall apart if some single change happens to our DNA. We have some redundancy. Yeah. Anyways, quines, they’re weird.
Don: They’re weird.
Printer on Fire
Adam: Just wait, I got more. So, what did you find?
Don: So, I took lp0 on fire, as what or otherwise known as printer on fire, error message this generated in some of the… I guess, I think it’s still in the Linux Kernel today. I think it is. Back in the late 50s, computers were being used at a lot of laboratories, and they needed to print out their calculations. They were using computers for calculations, and they needed the results. So, they had to print them out.
And they were spending a lot of their time just waiting around because printers were so slow. So, there was a lot of very experimental units of printers being developed. So, I guess, they even had one like a host of printers that used radiation. I think they use a cathode-ray tube instead of a laser to be essentially be a laser printer.
Adam: Oh, wow.
Don: And yeah, they use the CRT as a light source, but there were experimental and they used heat, a lot of them use heat. So, what could happen is, if the printer malfunctioned, the paper could combust, and if it didn’t stop, it would just keep jamming paper into the fire. Right? It would just keep feeding the fire more paper at.
So, when I first read that, I was like, “Oh, that’s where it comes from?” No, it turns out that these type of printers actually predate that error message. So, there was no evidence of that message appearing at that time. So, that was, I guess, a red herring.
So, then, I started reading about drum printers. So, drum printers are high speed rotary drums. And while they’re not as dangerous as the previous generation, they could still theoretically catch fire from the friction caused by the drum in the case of severe jams, but no known occurrences of fires have happened from those rotary drums. So, maybe, that was not the case.
So, then, I started looking at what the actual error was. And I mean, this is all from Wikipedia research. So, there are three states for line printers, ready, online and check. And if you have online off and check on, then that usually means it still had paper. But if you had online on and check on, it meant that it the printer was still trying to do its job, but there was a problem. And that could theoretically mean there’s a jam, but it’s not stopping.
The printer is continuing to operate. It’s going to shove a bunch of paper in there. And a developer decided that the error message for that should be the printer is on fire.
There Was No Fire
Adam: Oh, so it wasn’t based around a real fire?
Don: No. It wasn’t based around a real fire. It was a cheeky developer that decided that maybe, if I say that it’s on fire, it will convince somebody like an administrator to go and check it immediately because it’s running, and there’s a problem. It didn’t stop running.
So, that was like a recipe for disaster. So, they wanted, I guess they wanted the error message to be a little bit eye catching. So, if you get an error message pop up and says, “Your printer is on fire,” where you’re going to go take a look at it probably sooner than later.
Adam: That seems… I don’t know, if it’s unethical or I don’t know. It’s a bit bold or alarming.
Don: I think it’s supposed to be. But yeah, I thought that this error would turn out a lot differently. I thought that there would be an actual fire involved somewhere.
Printer on Fire Support
Adam: So, I worked with this guy, and I forget his name. He was engineering manager. But he had gotten to start in tech doing support. And in the 80s, he was doing support for this company that sold printers of some sort. And he told me a story that he like, he didn’t mention this printer is on fire error message. But he said that they had sent out some bad driver, at some point that like, was doing something strange, just like running over the same spot.
Instead of advancing the printer, it was just like printing repeatedly, or the same spot, and that it could cause the paper to burst into flames or start to smoke. So, they were getting all these calls. And he was support, and saying like, “Oh, my printer, something’s wrong. It’s just like going over and over again.” And he had to say like, “Okay, is there any smoke?” And then, people will be like, “Oh, that’s a weird question to ask?”
Don: Why do you ask?
Adam: Yeah. And then, he had to instruct them to unplug it and take it outside, which like, they were very confused why?
Don: I don’t want you to panic.
Adam: Yeah.
Don: Is there smoke? No. Okay, what I need you to do, think carefully. Don’t panic. Unplug it and bring it outside immediately.
Adam: Yeah. He told me this story to explain to me that doing support for software is sometimes like a thankless job. But, I don’t think everybody has to face this thing where they have to explain to the customers that we were trying to not burn your house down. So, please take these actions. It was probably businesses at that point. I don’t think many homes had computers with heavy duty printers. But…
Don: From what I could gather, the earliest printers were used in like, your academic or research context. Nobody was plugging this at home to print things out.
CPU on Fire
Adam: So, can I still get this problem? Can I still get this error printer on fire?
Don: I mean, I imagine it says that it’s still in the Linux source code as of version 5.11.13.
Adam: Nice.
Don: So, if something happens with the printer that it sends a status code of online and check both set to on, then, yeah, that message would pop up. It’s also kind of proliferated from there because I think that there’s a lot of messages for example, in some Kernel CPU code, that a thermal failure can result in a message that CPU number zero possible thermal failure, and it will say in [CPU on fire]?.
Adam: So, they came like a meme, but like, a Kernel error message meme.
Don: Yeah. Exactly. Now, I don’t know. The developer that put it in might have read about all of these instances of the earliest printers when they were trying to make them go faster, catching on fire. So, maybe, he was like, “Huh, that’s amusing.” I’ll put that in the message. And we don’t know.
Adam: Yeah, we don’t know.
Don: Maybe, we’ll never know. It’s a mystery.
Adam: That’s awesome.
Don: It’s not as deep of an issue as quines, I think. I think there’s a lot more meat to quines than there was to the printer on fire one. But I mean, it’s interesting. It’s an interesting story.
Ouroboros - The Quine Relay
Adam: Now, that is interesting. So, speaking of quines, okay, so.
Don: We’re going back to quines.
Adam: So, next up, the next one I grabbed from this Cursed Computer Iceberg is called ouroboros.
Don: Ouroboros?
Adam: Yeah.
Don: Like the snake that eats its own tail?
Adam: Exactly, yeah.
Don: It’s ancient sign of infinity.
Adam: It’s exactly, that the snake eating its tail, the ouroboros is an Egyptian symbol, I guess. Yeah, maybe for infinity. I’m not really sure. But, so the other thing that it also is a complicated type of quine has been given this name. The quine concept can be extended. So, instead of just having this single recursion where the program returns itself…
Don: Mm-hmm (affirmative)
Adam: You can have multiple levels, which has been called the ouroboros or a quine relay. So, the way this works is that you have two programming languages. So, imagine our Java program, when you run it, instead of printing out another Java program, it prints out a C++ program.
Don: Okay.
Adam: So, you run your Java program, it prints out a C++ program, then you run your C++ program, what do you think it prints out?
Don: Of the JavaScript program?
Adam: Yeah, the Java program.
Don: I’m sorry, the Java program, yeah.
Adam: So, now, you have two programs that return each other. So, now, you have a loop.
Don: Of infinity, yeah.
Adam: Yeah, a loop of infinity. And then, once again, it doesn’t seem like something that should be possible, but it just uses the same trick. So, you write your Java program, so you have your top part. And then, you have your string, and then you have printing the string. But now, inside the string, instead of just… Before, our Java program had to contain itself inside the string. Now, it needs to contain itself, and also the C++ program.
And so, when you run the Java program, it’s going to get the C++ part of that string and print that out. But it’s going to print that out with inside of it a string that contains the Java program and the C++ program again.
Polar Bear Child
Adam: It’s still like the DNA thing, but it’s like, if you, Don, contains the DNA of a human, but also the DNA of a polar bear, and then if you had a child, your child would be a polar bear, but then that polar bear had a child, it would be your grandson.
Don: It could be human.
Adam: So, it’s like a weird loop.
Don: That’s a great premise for a sci-fi movie.
Adam: A world where polar bears and humans.
Don: The premise of your offspring is a completely different species. And a whole kind of maybe a massive, like a civilization that functions this way, where they switch. There’s a big switch constantly between one species being the majority, and another, I don’t know. It seems like a sci-fi based novel. Yeah, like a weird society. And then like, Yeah, what are these two? What are thes
Adam: Yeah, like weird society. And then, yeah, what are these two groups? And what is different cultures?
Don: You can call it quine, yeah, as the title.
Adam: Exactly.
Don: Yeah.
Adam: Or ouroboros.
Don: I think ouroboros is already taken. I think there’s like several books that are named that. But…
Adam: Oh, is there?
Don: It’s more popular than quine. I had not heard of quine, but I have definitely heard of ouroboros.
Mame’s Quine Relay
Adam: Nice. So, super weird concept. This is stranger and more complicated than a quine. And the weird thing about it, if you think about it is that you have to… when you write your Java program, you have to know what the C++ program is too because the Java program needs to contain it. So, it makes writing these things complicated, but it gets more complicated than there.
So, that is like a two-step quine relay. One goes to the other. But there’s this guy, his GitHub handle is Mame, M-A-M-E. And so, he has this GitHub repo called quine relay. And it says, the following is a Ruby program that generates a rust program, that generates a scala program, that generates a … through 128 languages in total, until it generates the original Ruby program again. A 128 programming languages quine relay.
Don: I guess, you could have N number if you knew the pattern on how to do it. You could have N number of languages, I think.
Adam: I didn’t even know there was a 128 programming languages. There’s a lot.
Don: That does not surprise me like at all. I did not even blink when you’re like 127 programming languages. No, that seemed right.
Adam: But if you think about it like… So, I vaguely heard of this before, I think, and I was like, “That’s strange. How does that work?” And now, I guess, I understand how it works. But I think that makes it more amazing. So, that means, the first Ruby program has to have in some giant string, all 128 other programming languages inside of it. And then, every step needs to be the same. Every result needs to contain the proper result of all the other results.
Don: There’s got to be some method he has of putting them in more than just one string because the string has limitations. You couldn’t put an infinite amount of stuff in one string.
Adam: Yeah. And if different languages have different ways of delimiting a string, then that gets complicated. Some symbol you want to show, you want to have your Ruby program in a string, but the symbols for a Ruby program string conflict with something else. You have to…
Don: Yeah, the technical challenges there are interesting.
Mame Is a Time Traveller
Adam: So, somebody asked on the GitHub issue for this quine relay. They opened an issue. I don’t think this is really issue appropriate. But they said, “How long did it take you?” And he answered, he said, “Infinity, of course. I wrote the first program in Ruby. And then, I wrote the second program in Ruby, that produced the first one. Repeat that through 100 languages. Then, I wrote the third program that produced the second one. And I kept repeating until I reached a fixed point. What you see is the infinia program, which comes from beyond the event horizon.”
Don: Oh, wow.
Adam: So, apparently, name is from the future or from some singularity, that’s been created by self-reproducing programs. It’s not really clear.
Don: That’s awesome. I like how he’s got a sense of humor.
Adam: Yeah. All right. So, that was my second one, which is a quine relay.
Don: Does it count as a second one? I don’t know. I think that it’s pretty much the same one just like part two.
Adam: Yeah, just wait. I think you’re going to see a theme here.
Don: Is there a third one? Is this like, was that like Two Towers? And we’re going to watch, Return of the King? Are there three?
Adam: It’s going to keep going. The further down the iceberg you go, the more quines.
Thank You for Playing Wing Commander
Don: The more quines. I’ll kind of break us away from quines, just for another quick one. This one is also I think, gave me a chuckle, the Thank you for playing Wing Commander message, that happens when you play Wing Commander, and you finished the game, it kicks you back to the command prompt, and it says, “Thank you for playing Wing Commander.”
Wing Commander is a video game which you take control of a spacecraft and fight in a fictional world against aliens. And they’re also allies. It’s like a first person you’re in the cockpit, flying in space, doing missions, shooting things. There’s also a big story component to it as well. It was almost like an RPG and in fact that there was a story playing out, but all the action was you in the cockpit.
I know later Wing Commanders had you walk around the flight deck of the carrier and you can talk to different people. And later on, you can make choices and it became more RPG like, as the series went on. But the first one was pretty much just flying around shooting things.
Adam: I’m just looking it up here.
Don: But it was… Yeah, it was a pretty big game for the era. It was pretty groundbreaking. It was very popular.
Adam: It seems like vaguely Star Warsy.
Don: Like X-wing versus TIE fighter type game, yeah. But Wing Comander had its own world and it had its own world building and everything in its own characters. Anyway, yeah. So, Wing Commander was very popular game and it was in the mid 90s. And the game designer and creative director of Wing Commander was Chris Roberts, who heads up CIG games with the Star Citizen project. That’s very controversial, anyway.
So, Wing Commander was the first game, and Ken Demarest was the programmer. And they were having issues because there was an EMM386 memory manager issue error that would kick you out to the console at the end of the game. And he didn’t know why. And it’s not unheard of, because a lot of games in this era were trying to do a lot with limited memory resources.
So, there was all sorts of tips and tricks and weird hacks that they were trying to do in order to get these games to run on limited hardware, and how production deadlines can be. He didn’t have time to figure it out. So, what he did was he hex edited the error message. So, it would say, “Thank you for playing Wing Commander,” instead of EMM386 memory manager error.
Adam: Nice.
Don: Which is like, I mean, that made the trouble.
Adam: So, where is the error coming from? Who did it?
Don: He never found out. I think that once they ship the game, it was fine. It only happened when you had finished the game. So, you had completed it anyway, you got kicked back to the console and said, “Thank you for playing Wing Commander,” and nobody really thought anything of it. So, it didn’t matter anymore. It was shipped. He went off to work on a different project called BioForge, which was one of my favorite childhood games, too.
It gave me a chuckle, because it’s definitely one of like… I know I’ve been in that situation where you’re on the timeline. You can’t figure it out, you got to move on to something else. So, you make the best of a bad situation, and he just hex edited the error message. And I was sympathetic with him in that moment.
Hacking a Fix Together
Adam: Have you ever had a similar situation where you hacked something together to get it fixed? Like, didn’t really fix it?
Don: No, I don’t think… I might have done that while I was in the middle of trying to fix something else. But I don’t think that I’ve ever deployed anything. And definitely, not like production system.
Adam: Okay, there’s something that I can think of, from when we worked together. It wasn’t you. But let me… That comes to mind.
Don: It wasn’t me.
Adam: Okay. See, if this rings a bell.
Don: Okay.
Adam: A printer page that wasn’t working, and there was a bug with it.
Don: Oh, yeah. No, I know, this story.
Adam: All right. So, tell the story, man.
Don: So, in this particular product, there was a there was a report, you would run the report. And you can print it and there was a button, and you would print it. So, yeah, it would rerun the report again, instead of just formatting the output it already had. It would get that output data again, and then it would format it so that it was printer-friendly.
I’ve tried to forget this, okay. And then, Adam brings it all back. I’ve taken that and just shoved it in the box and tried to forget about it. So, the issue was that the report actually had an error, and the person fix the report, but the printable version was still broken. And they didn’t know why the report was running, but the printable version wasn’t. So, they pushed out the fix to the report so that you could use it again. But the printable version, he’s took the button off. He’s like, “you can’t print it, but it works now.”
And I think that was acceptable for it to be released so that people can use the report because it was broken. And now, it was a step up, because you couldn’t run the report at all. And now, you could, but you couldn’t print it.
Where’s the Print Button?
Adam: You have a very charitable interpretation. My interpretation involves actually the lag time involved and bugs. Where it was, like, you knew that this thing would come back, but it might not land on your plate. So, it’s like, I can put this out, and it’ll get out there.
Code reviews, were not really an important thing. So, you could get this change out. And then, that person who’s complaining would get the report to run, but you would know a week from then, or somebody would be like, “Where’s my print button?” And there’d be a new bug in. But it would land on somebody else.
Don: That’s what happened, yeah, the client complained.
Adam: Yeah, that second iteration, it landed on you. And then, you went in spelunking through source control. And we’re like…
Don: Yeah.
Adam: What happened? Where’s the print button? And then, you just saw, commit, that was like fixing the duh, duh, duh. And it just deleted it?
Don: Yeah, I know that’s exactly what happened. I never got to talk to him about why he did it. Say, we’re a different team in a different time zone. And we didn’t really speak.
Adam: Probably, part of the problem…
Don: So, it was more like, “This is, yeah, this is my issue. So, I got to figure out how to fix it.” And I went through the code to see okay, did it ever have a print button? Because that’s the thing, there was no print button there. And that was suspicious. It’s like, they’re complaining about a print button not being there, it’s like, maybe there wasn’t one because there clearly isn’t now. Surely, no one just removed it. Yes, somebody did remove it as part of a fix to the report.
Adam: It’s one of those times where you think the customers crazy, you’re like, “Didn’t support vet this? like, oh, somebody said, hey, there’s a button missing. Yeah, we’re not going to remove a button. What are you talking about?”
Don: What are you talking about? That would never… No one would do that.
Adam: We started off with Wing Commander, yeah.
Don: Yeah.
Adam: Okay. So, what? Is it my turn now? I guess.
Don: Yeah. That was all there was to that issue is just that… So, the guy hex edited in their message because he didn’t have time…
Adam: I think it’s a great hack. Right?. And it doesn’t really have ramifications necessarily, like the print button. I mean, I guess if you wanted some really cool, finishing the game screen, you can’t do that. But otherwise, there’s no ramifications.
Don: Yeah, like I remember playing Wing Commander and getting that message, but I just thought it was done. Games in that era where… Sometimes, wonky, and you just kind of rolled with it.
Polyglot Code
Adam: All right. So, me, the next one I got is polyglot computing. Yeah, the Wikipedia page is called polyglot computing, but I’m going to call it polyglot code. So, this is going to seem a bit like a quine again. So, some polyglot code is code that is a valid program in more than one programming language.
So, it’s like you have a file and you can run it as a Java program. But you can also run it as a C# program or something. Actually, those are very similar to each other.
Don: Okay.
Adam: So, the one on Wikipedia is the program is a valid C program, but it’s also a valid PHP program.
Don: And does that mean like the syntax that’s used in it is interpretable in both languages the same way?
Adam: So, the way this works is with a lot of horrible tricks, so it’s like, in some ways, a more complicated puzzle than the quine one. So, C has that preprocessor, where you can say, like, if the verbose is greater than two, printf, this message or something. And so, that allows you to intersperse, like that’s commonly done, just like, “Hey, we want to have verbose mode where we print lots of log messages.”
So, but you can do all kinds of things with the preprocessor. You could say, like #define { return or something. And now, all of a sudden, all your left parens are actually returned statements, which would just make your program very hard to understand. But it’s still a valid C program, because it runs as a first pass, and rewrites all these statements, right?
Don: Mm-hmm (affirmative).
Adam: So, the interesting thing is that, this pound sign, or hash symbol, I don’t know what people call it now. But that’s also a comment in many languages. If you put down a pound sign, then that’s often a full line comment. So, you can just use this trick to do a lot of weird things.
So, you could put a whole bunch of #define statements that changed things that are commonly found in a PHP program to actually be translated into something that’s commonly found in the C program. And the PHP program will ignore all those as comments and just run normal PHP, but the C program will translate that PHP program, using the preprocessor macro back into a C program. Coming up with one of these will be very difficult, right?
Don: Yeah, it’s one of those mental puzzles again.
The C PreProcessor as a Python Interpreter
Adam: And so, you could imagine having a Python program. And then, at the top of it, you have all these preprocessor macros that the Python will ignore, because they are comments. And they actually changed the Python program, they actually rewrite arbitrary Python to be C.
So, then, you can now write stuff. I don’t know if this is actually possible. But you can now write Python code. And when you run it, you can run it without a Python interpreter, you can actually feed it into C, because your preprocessor macros are, in fact, acting as a weird compiler and compiling your Python down into C.
Don: Yeah, that’s cool.
Adam: You certainly wouldn’t be able to bring in any libraries or anything like that. But yeah, this is polyglot code. And in that case, you’re doing things that have the same output. But often polyglot code, they don’t do that at all. So, they actually have two programs that do two different things, and use some tricks to do it.
So, there’s a programming language called whitespace. It’s actually written by Edwin Brady, who I interviewed on this podcast. I think it was more of a joke thing that he produced. So, in whitespace, the only input to it are various forms of whitespace. So, like a tab or space, or like a carriage return or a new line. Any other input is ignored. So, any characters that aren’t whitespace are basically, comments.
Don: It’s like the inverse of what you normally expect, right?
Adam: Yeah.
Don: Because normally, compilers ignore whitespace. And now, that’s the only thing.
Adam: Yeah, which makes it fabulous for this polyglot code thing. So, you can write a program that does whatever. And if the language is not whitespace specific, then you can encode whatever whitespace program you want into however, you space of that program.
Don: Yeah. So, there’s like, the same program, but it’s encoded all in the negative space of…
Adam: Yeah, or it could be a completely different program. You could…
Don: If you wanted it to be a quine.
Adam: If you want it to be a quine, then it needs to output itself. That will be interesting. So, polyglot, quine. So, it would be two languages. So, each program can be run as two languages at once. And then, they both have to output the exact same thing twice.
Don: Yeah.
Adam: Yeah, and then maybe you can add a polyglot quine relay. So, then, it’s like, it’s always two languages that produced two other languages that produce two… Yeah.
Don: Now, you’ve just tied together all three of your ideas into one thing.
The Code Golf Stack Exchange
Adam: Wait, wait, I’m going to keep going here. Are you familiar with code golf?
Don: No, no, I’m not familiar with code golf.
Adam: Code golf has very little to do with normal golf. Code golf is usually, they give you some programming challenge, given a list of numbers, add them up and print the result. But the challenges do it in as few characters as possible. So, it’s like, it’s golf in the sense that a low score, the lower the score, the better. So, it leads to some very unreadable code. It’s just like, you want to get rid of all the whitespace, you want to jam everything together.
Don: Yeah.
Adam: And so, like stack exchange. The Stack Overflow site. They have like a sister site, that’s a code golf site where people post. They’re just using the Stack Overflow format, but for a different thing. So, they’ll post a question, and then people post as answers their code golf solutions. And they have all kinds of strange…
Don: Okay.
The Polyglot Answer Chaining Challenge
Adam: This type of puzzle thing is right in their wheelhouse. So, on there, somebody posted this following challenge:
Adam - narrated:
Add a language to a polyglot. This is the answer chaining challenge in which each answer builds on the previous answer. I recommend sorting by oldest thread in order to be sure about the order in which the posts are made.
The task, the nth program submitted to this challenge must run N different languages, specifically, all languages added in the previous answers plus one more. The program must output one, one run with the first language used. Two, one run with the second, and so on and so forth. For example, the first answer could print one when run in Python. The second answer could output one when run in Python. And then, two one run in JavaScript. The third answer would be one run in Python. Two, with run in JavaScript. Three, one run in some other language.
Adam: The first guy has it easy. You just write a program that prints the number one.
Don: Yeah.
Adam: Okay. So, the first guy, that’s easy. So, okay, I just print out in Python, like print one. Second guy, maybe this whitespace language, we were thinking of, maybe that could work. Third, I’m trying to think.
Don: I have a suspicion that the responses to this are not, there’s not a lot of them. Because it gets harder as it goes. So, I’m pretty sure, yeah, I’m pretty sure that the responses topped out around like, maybe five or six.
Adam: Because yeah, after whitespace. Maybe, you could do the whole preprocessor thing we were talking about. So, yeah, you use these predefined. Yeah, after that, I run out of ideas. So, the thing that I found said that they had 101.
Don: Wow, that’s way more than I thought there would be.
Adam: Yeah, it’s crazy. So, I’m looking now at the 100th. So, the 100th is using a programming language called Brainbool, which I have never heard of. There’s definitely at least 144 by the looks of it. Yeah. And I could keep scrolling, but I can’t tell.
So, that’s crazy. It does seem like a lot of these languages are ones I’ve never heard of. Somebody created a programming language specifically for the purposes of embedding inside of answering this question. I mean, which is…
Don: Boy, you haven’t heard of Brainbool? Come on.
Adam: That’s not exactly a quine but it’s very quine related.
The Actually Portable Executable
Adam: Okay, so here’s my next one, there is something called the Actually Portable Executable. So, why can’t a program that’s created for my Mac, run on your Windows computer?
Don: Because the architectures are different.
Adam: But if we both have like an x86 Intel CPU. It has the same architecture.
Don: Apple is not doing that anymore. They’re coming their own new chips.
Adam: Mine is an old-fashioned.
Don: Okay. You have an old-fashioned one. Okay. That’s actually news to me. I didn’t know that was because I thought that they would have been able to execute the same instructions.
Adam: So, the interesting is, the CPUs can execute the same instructions, but it’s like, the operating systems are different, and have different assumptions. So, if I take a look at EXE file from Windows, and I put it on my Mac, and I double click on it, it won’t know what to do with it. It’ll say like, this is not the format that I expect an executable to be in, right?
Don: Okay.
Adam: Just the Mac, and Linux and Windows have different assumptions about what an executable should look like. Just imagine, like headers at the top that says, “Windows executable or something,” right?
Don: Yeah.
Adam: And so, if a file says…
Don: It’s like when the browsers all have their different engines. They would all take a different look at client side code and interpret it differently.
Adam: Yeah, yeah. And then, another problem is, obviously, if you were trying to pop up a Windows dialog box, whatever, like system calls you would make to do that, they’re obviously not going to work on my Mac. On Linux, there is what’s called libc, also on my Mac. And probably, also, on Windows too, at least under that WSL. It’s like the old school standard library for C. It’s been around for a long, long time.
And so, that’s another limitation is that, if I’m trying to run something from Linux that’s on Windows, and it tries to call like the libc program that opens a network socket or something, that just doesn’t exist, unless you’re running under WSL2. But, so this person named Justine Toney found this… Came up with this little trick. And it’s a little bit like our polyglot code.
Justine’s Trick
So, the thing she found is that, the whatever the headers that go at the top that tells something that it’s a Windows executable, that you can put those at the top of a Unix shell script. And the shell script tool ignore them. So, it’s a bit like a polyglot code. So, it’s like, you put the headers that say, “This is a Windows executable.” And then, below that, you put a Unix shell script.
And then, so on Windows, you have a normal windows executable. It has the header, it skips the shell part, and it just starts executing the program. On Linux, it contains the shell script. And what the shell script says, is to reopen the program itself, and it makes some changes to it, so that it’s now a properly formatted Linux executable, and then it launches it.
Don: Okay.
Adam: So, what she in fact, did was find a way to make an executable that’s like this polyglot code. One is the Unix shell. And then, the other is the Windows headers. And then, you’re right, when you get down to the CPU, when you get touch to the machine code, if you have the same CPUs, the same instructions will do the same thing, right?
Don: Yeah.
Adam: It’s all that other stuff, like the system calls, and the headers and whatever.
Don: Whatever changes she has to make to that executable to make it compatible would mean that, you would have to ditch all of the operating system specific code of that executable, because I mean, there’s no way that you can open a Windows dialog on a Mac.
Adam: Yeah, exactly. So, she says, that this is only good for standard in and standard out and opening sockets. So, you would have to build up everything besides that yourself. But even those things, even opening a network socket is different across Mac, and Linux and Windows. It’s certainly across Windows and Mac, they’re different.
So, she made a small translation layer. Basically, something that looks like this libc, but that can run on Windows. And so, basically, she ends up with this big command that she can pass to the C compiler, and it produced these executables that are valid on all three systems. I don’t know who she is, but maybe she was part of this polyglot code competition. And she was like, “Wait a minute, if you can encode… If you can make something…”
Don: I’m going to come up with a practical use for this.
Adam: Yeah. And it is very practical, maybe. I mean, I’m not sure how stable it is. If one side changes, all of these portable code things are dependent upon very exacting interpretation. Ignoring certain things and interpreting other certain things and understanding them exactly. But a pretty cool usage of this format.
Don: The program that you write that’s going to be interpreted by the three different operating systems is going to be pretty narrow in scope.
Adam: Yeah, but it’s the use of this polyglot code. So, these things do have practical use, I guess, if you can call that practical. And then, okay.
All Roads Lead to the C Compiler
Don: Oh, here we go. The finale.
Adam: So, I interviewed before Brian Kernighan. So, Brian Kernighan, who I interviewed and Dennis Ritchie and Ken Thompson, and a bunch of other people, I guess. They created Unix and the C programming language at Bell Labs, back in the 70s. But Ken Thompson definitely created a lot of what became Unix, which almost all modern computers are now based on. And he also created this B language. And then, Dennis Ritchie created this C language.
And so, the C language is responsible for all the C type programming languages we use. You’re writing things in Scala, it’s running on the JVM. The JVM runtime is probably written in C++, which is an extension of C. So, at some point, when you run a program, C is involved somewhere.
Don: All roads lead to Rome.
Adam: So, somewhere C is at the base. Your Scala program is great and fancy and all but somewhere, there is a runtime that runs in that was written using C. It’s the base layer. So, Ken Thompson, he got a Turing Award for his involvement in Unix, and he gave this talk called on Trusting Trust.
And so, there’s a talk and a paper. It’s very whimsical, I guess. But it’s also like a punch in the gut, because what he was trying to say is that, you can’t trust computers, and you can’t trust computer programs that you haven’t written yourself. And when he meant written yourself, he meant written yourself at the level of assembly.
And so, he showed why. So, the base C compiler that compiled the C++, that compiled the JVM machine that runs your Scala code, it has to be compiled itself. That C compiler has to be compiled.
Don: Yeah.
Adam: So, I mean, what are you going to compile that in? So, you need another language to do it. So, at some point, you have to bootstrap this process. You need a base compiler that can compile the first version of C.
Don: Yeah, like the proto compiler, the compiler of all compilers. Yeah.
Adam: The very first C compiler was written for, I think, for this old machine called the PDP-11. And they had to write the C compiler for that using PDP-11 assembly. So, they had to use the machine instructions of that particular CPU to build the C compiler. And then, once they had that, they could compile C in it.
And you can imagine a similar process happening for every new CPU architecture. There’s ways to cross compile. So, that doesn’t necessarily have to happen on every new CPU. But, basically, at some point, this base compiler is compiled, and then further versions are compiled from that. So, it’s like a chain. And if you’re thinking this sounds a little bit like a quine, then maybe, you see where we’re going here, right?
Don: I thought, I knew we get to that. Yeah.
Adam: Basically, I looked at this list. And I started reading through things. And there was a lot of quines there.
Don: It sounds like you read an article about quines, and you really liked them. And now, everything is a quine.
Reflections on Trusting Trust
Adam: Exactly. So, Ken proposes this exploit in his paper. So, the first thing is, he says, “Okay, in my C compiler, because okay, I’m getting an award for creating Unix and you guys all think it’s great, but how can you trust it?” He’s like, “So, in my C compiler, I can put this line.” And it says, “Whenever you’re at the login screen, and you’re checking the password, just also check for this other password.” Just like hard code in Ken’s password into the login.
Don: The super user backdoor.
Adam: Yeah. Right. And so, every Unix is compiled using C. And then, so every Unix implementation that uses that compiler will have that backdoor. And you wouldn’t be able to find that, if you looked at the Unix source code, you wouldn’t be able to see the backdoor. Because the backdoor isn’t actually in the operating system source code, it’s in the compiler. So, you can’t see it, right?
Don: Right. It adds it during the compilation.
Adam: Yeah. So, but you can look at the compiler and see that that backdoor is there. So, if you read the source of your compiler, I mean, I don’t tend to do that.
Don: Chances are somebody has, and somebody would have been like, “Hey, what’s this all about?” And there would have been an article about it. There would have been a bunch of news, CNN headline on like, tech radar.
Adam: Exactly. Right. So, and the paper is called Reflections on Trusting Trust. And yeah, it was 1984. So, he called this first thing where he’s just going to put in this thing that always checks for his username. He called this a Trojan horse. And that since became an industry standard term. I mean, he didn’t invent the horse of the Trojans.
Don: Oh, okay. (sarcastic) He didn’t. I’m sorry.
Adam: But he applied it to computers and gave it this term. So, it’s like, this was a trick that he’s embedded in the source code. But yeah, as you say, you can just go and look at the C compiler and see that that’s there. So, this is where he gets a little bit tricky.
Detect When Compiling the Compiler
Adam: So, the next idea is, hey, what if I add something to the C compiler that can tell when it’s compiling the C compiler? Because as we said, the C compiler has to be compiled, right?
Don: Right.
Adam: And there’s this bootstrap process that leads all the way from the C compiler to your JVM. So, the C compiler will look and tell when it’s compiling itself. And when it’s compiling itself, and it’s producing the assembly code, then what it can do is, you can take the assembly code that Ken’s original Trojan horse would generate. And the compiler can detect whether it’s compiling the C compiler, and it can add in that code. So, it will add in that assembly.
Don: It’s one level removed now.
Adam: It’s one level removed now, right?
Don: Yeah.
Adam: So, now, if you could take the C compiler, you could remove the backdoor, but you compile it with a version that has this level that adds it in. And now, your result, like the source code won’t have the backdoor. But the backdoor will be in the result. But this bootstrap process continues. So, the problem is, the step after that when you have another C compiler.
Ken Thompson’s Quine
So, when you compile that C compiler, again, then you’re going to lose it. So, the trick that we need here is something like a quine. We need some way to reproduce this change. So, what he comes up with is, we need to detect, as we said, when we’re compiling the C compiler, so that we can put in this assembly that is the Trojan horse. But we also, once were detecting that we’re inside of a C compiler, let’s also insert the code of ourselves back in as assembly code.
You add in this code to your compiler that adds in the Trojan horse and adds in the code that adds in the Trojan horse, and re-adds in itself. When you compile something with that, you can take out all that nonsense, but it’ll get added back in. And every time after that, whenever you compile it, it will be there in the assembly, but it’ll never be in the source code.
Don: Right.
Adam: So, he gives this…
Don: Unless you read all the compilers…
Adam: You would have to be like, yeah, you’d have to go back to the base one and check it, right?
Don: Yeah. So, it illustrates this point that you can’t trust it unless you’re at least aware of all of the code between you and the actual assembly.
Adam: Yeah, you can’t just look at the source code of your compiler. You have to look at the source code of your compilers compiler, and all the way back, right?
Don: Yeah.
Can We Trust Compilers?
Adam: And this is a scary thought. But I think it’s like, especially a scary thought, because this was a talk given by the guy who built the C compiler, and built Unix. So, in a way…
Don: I’m pretty sure that after that talk, a bunch of people started looking at compilers.
Adam: In a way…
Don: But, wait a minute, the guy who made it said that he could put whatever he wanted in it, we wouldn’t know, we got to go look.
Adam: Yeah. Yeah, in a way, he was saying, like, “I didn’t do this. But how would you know, if I did?”
Don: It would have been there. It would have been very easy. That’s all I’m going to say.
The Multics Security Audit
Adam: So, before Unix, there was this project called Multics. Yeah, the Brian Kernighan podcast I did, you can listen to it here. But more, it was somewhat of an unsuccessful project, at least not as successful as Unix. But they were trying to get the military to use it, I guess. And the military did some audit. And at that time, operating systems of this nature were like a wild, crazy concept.
And one of the audits from the military actually suggested this as a potential problem. They’re like, “Okay, this operating system is great, and we can audit the code. But how do we know that there isn’t something in here from the thing that it was compiled with?” So, actually, in fact, Ken didn’t come up with the idea himself. And I think it shows that quines are… They’re practical somehow, maybe not, they don’t come up all the time.
But there is uses for them and very odd uses. This is an assembly level quine, where it needs to reproduce itself using assembly, generation by generation. Actually, I don’t think there’s a lot of uses for quines. But I think that when there is, there probably something really powerful. Something really strange and odd.
Don: If you let Adam talk long enough, he’ll talk himself out of a point he was trying to prove. It’s like, I think that quines can be very useful. But, maybe not.
Adam: Yeah, I don’t know how they’re useful. But there’s something weird here, right?
Don: And very specific.
A Different Perspective on Computing
Adam: Yeah. It’s like, something… A lot of times, we think about computing, like, what’s the best way to present this problem, or what’s the fastest way to solve this. And quines have a… They have a totally different perspective on computation. The success of my program is not the result, or it’s not how beautiful it is, it is actually how it self-replicates. It’s a very different perspective, yeah.
I didn’t get into computer programming because I knew it was going to be a really good job or anything. It was a fluke. I got into it because I took a class where we were… It was a class in high school about programming. It was in turbo Pascal. And we just build things, and they were fun. And we built little games. And…
Don: Yeah, I had a similar class with object-oriented Turing.
Adam: Oh, there you go. Right. I think I had one with Turing two, which is like, I think it’s a weird programming language that they only used in Ontario in the 90s. It’s very unclear.
Don: Specifically, only for grade nine, high school students.
Just Build Werid Things
Adam: Yeah. It didn’t take the world by storm. But yeah, man, it was fun. And I feel like there’s… I don’t know, these like quines. They make me think back to this time of just building fun things, I don’t know. Just like, so much of stuff about computer programming is like, what’s the best way to scale some giant service, or what’s the best way to represent business requirements? Or how do we be truly agile? Or it’s all like, who cares, right?
I just want to do the coolest stuff, like I want to make. Just the idea of code that you can make reproduce after the source code is gone. That’s insane. I’m going to write this thing, and then delete the code, and then it’s still going to persist. That’s a wild idea.
Don: That is. That’s pretty crazy.
Adam: Yeah. And so, I don’t know what the practicality of any of this is, but it’s beautiful in a weird way. And I think that, one thing I always wanted to do with the podcasts that I probably haven’t done as much as I’d like, is people who do weird and impractical things with computers. Okay, that guy name who made his 128 programming language, like loop.
Don: Yeah.
Adam: That is a very, like… He’s doing it for some weird aesthetic kicks or something. This isn’t… Nobody is paying him. You know what I mean?
Don: Yeah, yeah. No, I hear you. It’s like, back when I started just building small programs that did weird things, or the unknown, right? Trying to feed something into something and seeing what happened.
Adam: I know, right. Just build weird things and have fun.
Don: Yeah.
Adam: So, this seems like a good place to end things. So, if you’re listening, build weird things. And subscribe to the podcast and to the newsletter, which I’m trying to start. I haven’t sent out any newsletter so far, but I will. And if you like this episode, let us know. And we can decide whether we should do more like this in the future. And until next time, thank you so much for listening.
Sticher
Overcast
Dec 02, 2024
42
min