Programming grimoire [1]::are programs real?

In the previous article we have set the scene with a little dash around the history of ‘magic’ and ‘science’, talking about how the latter emerged out of the former. We learned a little about how electromagnetism was divined to be this universe’s magic, and then we said it gets rather complicated on the scale of us humans, because it is a ‘substrate for abstractions’. Then we gave some obeisances to the founders of our order.

All of that is ‘just’ context.

It’s time to get to it. We would like you to understand what programs are, and what it means to write them.

  1. what is a program?
    1. instructions
    2. the wider world
    3. a home for programs
    4. programs in boxes
    5. so do programs exist?
  2. first orb to ponder

what is a program?

A modern computer is generally speaking doing a lot of ‘things’ at once. We tend to call these ‘things’ processes or programs. You can find out what your computer is doing in a few ways.

Once you’re in there, there will be a long list of mysterious things that are being done by your computer. So what are they?

Well, let’s start by saying programs kinda don’t actually exist… at least, ‘below certain levels of abstraction’.

instructions

Every modern computer processes things we call ‘instructions’. There is a long list of things that a particular computer knows how to do, each of which has a number.

We’re starting somewhere in the middle of the great chain of abstractions that makes up a computer. We could start lower, with logic gates; we are going to build higher. But starting with instructions is a nice place to get a sense for how things really work.

None of this is stuff you need to memorise: we will deal with this indirectly, through programs.

“Inside” the computer somewhere there “is” a long list of instructions we want it to carry out, not unlike a recipe. We can represent it like this, in “machine code”. For example, here is some code for an x86-64 processor that reads two numbers and adds them together:

89 7c 24 0c
89 74 24 10
01 fe

You can read this as saying ‘run instruction 0x89 with the values 0x7c, 0x24, and 0x0c, then run instruction 0x89 with the values 0x74, 0x24 and 0x10, then run instruction 0x01 with the value 0xfe’. (The prefix 0x… means the values are all written in hexadecimal.)

Nobody in their right mind would try to make sense of a program this way (nobody was in their right mind in the 40s, least of all the people who invented computers), so in 1947 Kathleen and Andrew Donald Booth invented the first assembly language and gave all these numbers special names to make it more readable. With x86-64 assembly, the above reads:

mov    DWORD PTR [rsp+0xc],edi
mov    DWORD PTR [rsp+0x10],esi
add    esi,edi

which can be read as: ‘move the thirty-two-bit value from the memory address at (stack pointer + 0x0c) into the edi register, then move the thirty-two bit value from the memory address at (stack pointer + 0x10) to the esi register, then add the esi and edi registers together, storing the result in the esi register’. A program called an assembler can turn this special language into the numbers above.

That’s still very complicated, nearly every word in that sentence is jargon! However, this is what computers are actually doing. All the electronics that exists in a computer, all the logic gates and transistors, have been very carefully put together in order to make it possible to decode and run these instructions. Everything else we are going to do will ultimately be boiled down into instructions like this.

Different types of computers have different instruction sets. A modern PC will almost certainly be running x86-64; an android phone or Apple computer will almost certainly be running some variant of ARM. A small, embedded device might be running RISC-V. Older computers ran lots of other architectures. In theory, it is actually possible to make a computer with just one instruction, such as subleq.

In no case do the instructions have any notion of what program they are associated with. So where do programs come into it?

the wider world

Single instructions on their own are not good for very much. We added two numbers together, so what? We need some other instructions to come together and read that number we just calculated, and do something with the result. By feeding the results of one instruction into another instruction, we get complicated behaviour. A modern computer might run a few billion instructions in a second.

By arranging a whole bunch of instructions just so, we can describe a process to achieving some desired result. For example, a very basic program could ask you for two numbers on the screen, and then add them together, and then put the result on the screen. This analogises pretty well to a ‘magic working’. You have some intent, and you arrange a bunch of symbolic elements to create a process that will fulfill that intent.

Hold on a minute, where did this screen come from? This is a new character in our story, isn’t it?

So far we’ve talked about the inside of a CPU in isolation. But a CPU on its own is just an unbelievably expensive paperweight. A modern computer has a whole bunch of parts. At absolute minimum, to be useful we need: motherboard, CPU, memory, and some kind of connection to the ‘outside world’. This could be a screen (for a desktop PC or phone), but it could just be a network connection (for a server), or a motor (for an embedded microcontroller), or some other weird thing.

So, using various protocols, the CPU that is carrying out our program has some way ‘talk to’ the other parts.

The memory may be the most important. Inside the CPU there is only a very, very small amount of space to store information. Anything that needs to stick around needs to go into memory. Many different types of physical electric circuit can qualify as memory, but the important thing is that it is ‘random access’, meaning the CPU can look up or store a value anywhere, given just a number which we call an address. The CPU activates wires (circuit board traces) called the ‘address lines’ to send a signal to the memory controller, which looks up that address, and sends back the contents.

What about the connection to the outside world? Well, the motherboard’s job is to take signals from the CPU and decide what to do with them. There are various ways this can be accomplished. It may simply be accomplished with the same ‘write to memory’ instruction, but for certain addresses, the motherboard jumps in and says ‘actually that address means we need to pass this data here’. Or there might be special lines and special instructions just for talking to hardware.

In the old days, you would have a manual that comes with your computer and tells you what you need to do to interact with the other components. In those days, a computer would just run one program.

Nowadays, there are millions of different configurations of computer your display might want to run on. You don’t want to know about all the details. You probably also want to run multiple programs at once. This is where the operating system comes in.

a home for programs

The operating system is, roughly, the program which runs all the other programs. It provides a context in which programs can ‘talk to’ each other in standardised ways.

Some of those programs control ‘talking to the hardware’, and it will have specialist programs for all the different types of hardware that it might run on, which we tend to call ‘drivers’. This is nice because you can just write a program to target a specific operating system, which has just one standard way of doing things. For example, if you want to play a sound, a program can ask the operating system to translate your ‘please play a sound for me’ command into device-specific instructions for the particular sound hardware of this computer.

How do you have all these programs running at once? You sorta don’t. On a single-core CPU, it’s like this: you run a little bit of one program, then you put the state of that program into memory and jump to where you left off on another program, and then again for the next program… This is called multitasking. The process of putting one program away, and loading another to execute for a little while, is called a ‘context switch’.

So the distinction between different programs lives in the operating system. The operating system becomes the ‘environment’ in which other programs frolic. But to the CPU, the operating system and the programs inside it are all combined into one huge, non-stop stream of instructions.

programs in boxes

Within an operating system you have the idea of a thing called a ‘file’, which is really at the most fundamental level just a name which the programs can interact with. Usually, that name refers to a chunk of data. And usually, it will have some extra information which will help the operating system figure out what program might understand this file, called ‘metadata’. But other ‘things’ can be ‘files’ too. On Linux (and other Unix-derived systems), all sorts of things can be spoken to as files, including hardware devices, running programs, random number generators…

Still, sticking with the familiar: if a file is ‘just a bunch of data’, one type of file is an ‘executable file’. This is a file containing instructions, like we’ve discussed above. Different operating systems have different ways to format this file. On Linux, files are elves… sorry, they are ELF binaries. On Windows, they are some version of exe. On Android, it’s an APK, and so on.

Whatever they are, they store the recipe of instructions that ‘belong to’ one particular program. Besides conforming to the format, there is nothing special going on here. It’s pile of data, the same as an image or video or anything else. Without knowing how to read it, most of the contents would look like random noise. But the operating system knows how to decode it: it copies the program’s instructions into memory, makes a note of this program amidst the list of running programs, and jumps the CPU to the beginning to start doing whatever the program tells it to do.

so do programs exist?

What we’ve described so far is how an abstraction becomes real.

We want to imagine there are lots of little things, which we call programs, running inside the computer. If that were the case, we can conclude that they ought to behave in certain ways. So we wrote a program that follows those rules.

If we did our job right, if we cover all the little details, then we get a situation as if the world inside the computer is segmented into little things, which can be passed around as files, and each one is running on its own and passing little signals to the others.

This is how we perform magic. We work out what we want to happen, and make something on the ‘level below’ conform to the rules. In computers, there is only ever as if. We build as if on top of as if on top of as if until the stack of abstractions is so tall we can hardly see the bottom anymore. We can build entire notional computers on ‘as if’, which we call ‘virtual machines’; in theory it should be impossible for a program to know that it is running on a virtual machine as opposed to ‘directly on the hardware’. (In practice there are subtle ways to tell.)

Sometimes the abstraction fails. For example, one ‘as if’ that we want to enforce is that programs have different levels of security privilege. The ‘kernel’ is allowed to do things that ‘user space’ programs cannot. The ‘user space’ programs must ask nicely for the kernel to do something, like give it some memory, and before it does, the kernel will check to make sure all the relevant rules are being followed. For example, I can’t just snoop around for sensitive information that other programs might be processing.

But if there is a mistake in how the kernel is written, I might be able to trick it into doing something it wasn’t designed to do, take control, and do whatever I want: steal information, impersonate people, etc. Computers are really horny to compute. Computational power can sneak through all sorts of weird ways. Later on we might learn about things like ‘ROP gadgets’ and ‘weird machines’, where fully Turing-complete computers form inside programs more or less by accident.

This is known as the abstraction ‘leaking’. It is not enough to know what ‘as if’ rules a program is following. A complete story describes both the intent of the program and where the reality differs from the intent.

first orb to ponder

Later in this series we might pose multiple-choice questions. However, I don’t think this stage needs it. Instead, some things to think about.

ffmpeg is a program which does things with video and audio. You can run ffmpeg on many different platforms: Windows, Linux, etc., and many different architectures, and there are many different versions.

Conventionally, we tend to think of some portion of these as mostly being ‘the same program’. But what makes that the case? Perhaps we can think of…

Now imagine changing these things. Maybe you rename it to ffmpreg. Maybe you modify the source and recompile it, maybe you rewrite it from scratch but somehow do such a good job it does the exact same thing.

Which ones are still ‘the same as’ ffmpeg? There isn’t a right answer.

Comments

Add a comment
[?]