Theory of Computing - Part 3b: The Operating System (Cont.)

API: Application Programmer Interface

An API is a documented group of software components that can be called by application programmers as needed to extend their abilities. In the context of an operating system, the system APIs are a phone book of features that are available for your application to use. These APIs allow the programmer to access hardware and devices, take input and output from the user and, in the case of a Graphical User Interface, draw windows, cursors, and other interface elements without having to create the code for that directly.

Unlike other aspects of computing, which only care about the compiled binary instructions and are agnostic about how you reach them, APIs are language dependent. While the code that is called when your program uses the API is a compiled binary, the function call to use that code has to be made using the same language as the API and linked to your code by the compiler before it will work.

Function Calls Explained

While it may work slightly differently for different languages, all modern languages have a way for a programmer to place blocks of code in a separate area called a function. This separation allows the code to be reusable and to be independent of whatever is happening in the main body of code that is calling the function.

Each function has a signature or header that gives it a specific name and tells the compiler (and the programmer) what the function needs in order to run properly. For example, a function that returns the average of two numbers could be called "average (x,y)", and could require two floating point numbers "x" and "y" as input values and return a floating point value as its output.

Another major difference between older systems, which had "subroutines" instead of "functions", but which worked similarly, is in the way the processor handles the execution of these instructions. In the older systems, the subroutine was called using a jump command, which tells the processor to go to a specific address in the program memory and execute the instructions there, followed by a different jump command at the end of the subroutine which told the processor to jump back to the location that called it.

Modern programs instead push the memory address of the command that called the function onto a data structure in memory known as a "stack", or in this context "the call stack". The processor then pops the data stored back off of the "call stack" when given the command to return so that it will know which memory location to go to and continue executing.

This means that the function no longer has to keep track of the specific memory location to return to, unlike with subroutines. Also, when creating the entry in the call stack, each set of variables used by the function have their own separate copy. This means you can call a function multiple times by different actively running sections of code without having one section of executing code interfere with what is happening in another section of code even if they both are making calls to the same function at roughly the same time. Of course, too many levels of function call can create a different error, known as a "stack overflow", which would cause the kernel to kill the process. This generally only happens under recursive function calls that are not properly ended and result in a kind of infinite loop. See this article for more details.

API Calls In Detail

The first step to making an API call correctly happens when you are writing and compiling the code. Each API has all of the allowed functions stored in separate header files that your program can link to when building it. These header files tell the compiler what each function needs to be called correctly. Assuming you have correctly linked your source code and made your call to the API, then at run time the processor will run the code exposed by the API exactly the same as any normal function created by your program. That is, it will push the memory address and variables used by the code calling the API function onto the stack, and then execute the API code which has already been loaded into memory by the kernel either at system startup, for common functions, or at application startup. When the code is finished executing, it will send a return command which pops the stack in order to get the memory location and variable state and loads the values returned by the function into the memory locations indicated when you made the function call. The processor will then go to the next instruction in memory and continue execution from there.

So, in summary, an API is a way for your code to call a function that is used in the operating system and to add its functionality just as you would import a function you created on your own, only without needing to know too much of the details about how it works. As long as you call the API correctly, it should work with your code and allow it to use the system to extend your program's functionality.

Theory of Computing Part 3a: The Operating System

To quote the wikipedia article, an operating system is "a collection of software that manages the computer hardware and provides common services for computer programs." This collection has evolved much more slowly than the programming tools mentioned earlier. This is primarily because early computers were limited to one program at a time and were much more hardware dependent, so there wasn't as much to manage.

Another article, on the history of operating systems covers this evolution in depth. What I will be covering in this post is more about the operating system's role in mediating between the hardware, the user, and the computer program. This will include an explanation of process management, programmer APIs, and a look at how the OS mediates the user interaction with the programs running on the computer. Unfortunately, it is hard to do this without a sizable amount of jargon so this entry will be more technical than some of the other entries.

The role of the OS

Up until now, the mental picture of how a computer does what it does is fairly straightforward. The processor reads a program as binary signals from memory, and executes the instructions it is given. There are still plenty of embedded systems or multi-controllers that work pretty much exactly that way. However, as the hardware has grown more complex, this picture has evolved into something different.

Instead of having the computer run each program one at a time on a blank slate, the computer runs a root program, called the kernel when it first starts up. The kernel manages which programs are allowed to run, how much access they have to the processor, how much memory they are allowed, what other devices or resources they have access to, etc.

Process Management

On a modern computer system, when your computer program runs, it is not given complete control over everything that is happening on the computer. Rather it is expected to follow a set of rules and is only allowed some of the processor time, and the kernel acts as the traffic cop, pushing programs into the processor queue when their supposed to and killing any process that doesn't obey the rules.

One good example of this is memory management. As mentioned before, when running a program, the processor loads each instruction from memory, executes that instruction, and then goes to the next instruction in memory and executes it, continuing until aborted.

As far as the program is concerned, the memory space is completely sequential and limited only by the address system of the computer. This is quite different from what happens under the surface as the kernel only allows the program to have a certain amount of memory address space, and if it tries to access memory outside of this space, the program is killed. Moreover, while the program uses addresses sequentially starting at 0, the actual hardware memory addresses are often mapped into a random system for security reasons, and the memory is converted from the program's internal memory address system, to the physical memory address by the kernel.

This same sort of management happens with processing time as well. While your program may act like it has completely control over the processor and is constantly being accessed, the kernel itself has final say over how many instructions get executed and it periodically sends its own instructions, or that of background processes through the processor while your program is running. If your program fails to relinquish control after a certain period of time, the kernel will kill the process.

In summary, the kernel in an OS is yet another example of a layer of abstraction in computing. When convenient, programmers can write their code pretending that it is the only thing being ran on the computer and it doesn't need to share resources or deal with memory issues. And the code will work just fine because the kernel takes of the nuts and bolts of actually interacting with the processor and any other hardware. However, if the programmer needs to do something more complex, as you will see in the next post, that the operating system is waiting to help.

Theory of Computing - Part 2b: The Software (cont.)

Compiled Programs

At this point, computers are still very large, very specialized machines. A program is written in assembly language for the specific device. You can share programs between identical computer models, but sharing programs between different types of computer depends upon whether they have shared processor instruction sets and assembler languages or not. Of course, most computers are specialized enough that no one cares, but some early computer scientists come to the conclusion that it would be very useful if you could take a program in a single language and build it for any device you want. Thus the compiler is born.

So what is a compiler and how is it different from an assembler program?
At their core, both an assembler and a compiler are computer programs that take a human readable computer program and convert it into low level instructions that can be executed by a computer.
However, a compiler is more complicated in that:

1. The programming instructions a complier takes in do not directly correspond to the operation codes required by any processor.
2. The output of a compiler may not be in any machine specific language. Instead, they can be converted from something similar to assembly called object code into machine specific instructions.
3. As you will see, a compiler generally has more steps involved when translating from the programming language to the binary executable, and the process has become more involved over time.

How a compiler works

As mentioned earlier, the a compiler is a computer program that takes another computer program as input. However, unlike an assembler, this program can be written in a language that is independent of the processor instructions, and can therefore be more human readable. However, to go from "X = Y + Z;" to something that can be ran on a computer, takes many more steps.

The first step is to read through the program and break it down into pieces that can be converted into object codes. This is called parsing the program and it involves taking certain key words and symbols and replacing them with one or more non-ambiguous symbols which can be used to differentiate identifiers (like "X", "Y", "Z" in the example above), operators (like "+" and "=") or structural statements (like the ";" which represents the end of the statement") that are present in the program. From there, you can tell if there are errors made by the programmer which result in something that can't be converted into machine code.

After parsing the program, and determining that the program is valid, the compiler then proceeds to analyze and optimize the intermediate code and convert it into object code, depending upon the compiler, and later machine executable code.

Variations on this theme

This has basically brought us up to the 50s and early 60s in terms of chronology. Computer software has moved from a completely hardware dependent model that talked directly to the processor to a device independent model that is completely oblivious of what the processor needs and is only interested in satisfying the compiler. While developments in language and hardware have allowed programmers to harness more powerful machines without needing to get involved in the nuts and bolts of the processor, the concept of how programming works is not that different. You take the problem you want to solve, break it into steps, describe those steps using the programming language you want, and let the compiler convert it into machine language. However, there are two important variations that have allowed programmers to move completely away from the need for a static compiler at all. They are: Interpreted languages, and Virtual machine coding.

Interpreted languages

As mentioned before, a compiler is a computer program, that takes a different computer program as input and converts it into machine language. Early on, many programmers asked themselves, what would happen if we simply eliminated that last step? Instead of outputting a machine language, what if we just had it execute the instructions as if they were part of its own process?

The result was a way of developing programs that were simple and device independent but allowed computer programmers and operators to solve small problems without the overhead of a compiled program. As interpreted languages have evolved, it has also allowed programmers to be almost completely divorced from the boundaries of the machine. As long as the person who wrote the interpreter knew when and how to convert and define your code, you could write code that completely blurred the boundaries between letters, numbers, operations, etc. Much of the Internet is built on device independent code like this. The only downside is, it takes much more memory and processor time than the same code would take if compiled directly. So it would be completely useless for the intensive memory and data applications that computers were originally designed to be good at, but great for smaller and more casual applications.

Virtual machines

The other question some programmers asked themselves is, what would happen if, instead of outputting machine code for a specific device, we had the compiler output binary code that could be compiled to instructions for a "virtual" processor which then quickly converts from there to device specific instruction codes? This is the concept of a virtual machine, and it solved the problem of device independent code taking up too much memory and processor time. However, you then have to make your language generic enough that it can be used on everything from a computing array to a cell phone processor, which still makes it less popular and useful for many applications. And, so, while there are a number of virtual machines, the language and machine used most often is Java.

Software concluded.

Hopefully, this has given you some insight into how computer software works, why a computer has software at all, and why you are now able to write in a single language and have it be ran on many different kinds of machines without any problems. The next topic will cover what an operating system is, why it is necessary, and what it does for programmers and users.

Theory of Computing - Part 2a: The Software

While it is undoubtedly useful to calculate mathematical solutions to problems quickly and accurately a computer's real usefulness stems from the fact that it can be set up to solve abstract problems without actually changing any circuitry. This was not a happy coincidence but was a planned design based on applied mathematics.

The Theory Behind General Computing

The idea for a computer program has its roots in a concept known as a Turing Machine. This theoretical machine is essentially a device that reads actions from a strip of tape, performs those actions according to a rule table and then, depending upon the action, writes the result back to the same strip of tape. In his paper explaining the concept, Alan Turing went on to prove mathematically that a machine like this could, theoretically, be used to compute the answer to any problem that can be computed by a machine.

How Stored Program Computers Work

While computers in general have never worked exactly like a Turing machine, the way they do work is very similar. That is, they go to the section of memory set aside for the computer program, read a step from memory, perform a valid operation based on that step, and then write the result back into program memory.

The "rule table", is a series of circuits that incorporate the various operations the computer can perform. Each circuit is laid out according to the Boolean logic mentioned previously. The processor starts by reading an action code (i.e. a voltage pattern corresponding to a binary number) from the program memory. It then activates the circuit that corresponds to that action number, first setting up the input voltages depending upon the type of operation. The computer then "reads" the corresponding output voltage performing the action and writing the result back into program memory. The computer then goes to the next space in program memory where it reads the next action and performs it. This continues until the end of the program.

This brings us up to around the era of the punch card and vacuum tube computer. Where you would set up everything you need the computer to do, run the program, and take in the result. There are a number of different changes in computing that take place that complicate the model considerably. The first, is the development of programming languages to take over the tedious process of using operation numbers and translate it into something more human-friendly.

Assembly Programming

Assembly programming was a very early development. At the hardware level, a computer program requires everything to be written in binary numbers, referring to the action (also called "operation" or "op") code you want to perform as a binary, and referring to any space in program memory by binary number. This is both tedious and error prone, so early programmers quickly developed a separate computer program that takes a computer program written in a structured language (called "Assembler" and converts it to binary machine code.

Assembly language is not too complicated, as it basically takes each operation the computer supports and assigns it a mnemonic, e.g. it takes "ADD" and replaces it with the binary or hexadecimal operation number for addition on that machine. The assembler program also allows you to define a symbol, like "A" or "B" and have it replace that with the binary number for the memory address. So you could write a program line that says "Add A B" and the assembly program would read that in and replace it with the required binary instructions, e.g., "0A 01 02".

Assembly programming is still used in some specialized applications, but the main reason to cover it is because this is where you see the beginnings of the layers of abstraction used in modern computing. Instead of writing directly for the processor, you write one program that is used as the input for another program, which outputs the binary you need. This abstraction is important in that it allows you to develop complex behaviors by combining two simpler ones. You also see the roots of computer programming languages in the mnemonics used to describe computer operation codes, which are arbitrary in terms of what the computer needs to work, but meaningful to human programmers.

At this point, I'm going to split this into another post as it's becoming unwieldy. So, to be continued...

Theory of Computing - Part 1: The Hardware

People like to think of computers as little black boxes where tiny ones and zeros get passed around until the answer is found. Or maybe, as a tiny circuit board that solves problems that are put to it. You can get away with this because, in a sense, that is exactly how they work. But not really. While the roots of a computer as a universal (mathematical) problem solver go back a 150 years or more, the computer we think of today is a product of the semiconductor.

The Role of the Semiconductor

A semiconductor is an electronic component that allows electricity to flow differently in one direction than it does in the other. This allows part of the circuit to store discrete states (“on” or “off”) as opposed to continuous analog states used in other types of electrical components.

Adding different kinds of semiconductor components to the circuit allows you to take the voltages of the stored states and combine them in a predictable way. This is how a computer does mathematical operations. However, these circuits are not laid out arbitrarily, but are based on a specific type of mathematics called Boolean Algebra.

The Math in the Machine

Boolean Algebra (which was developed in the 1850s) is a type of Mathematics based not on Natural Numbers (like 1, 2, 3, 4, … ), but on two values ‘1’ or “True” and ‘0’ or “False”. Rather than doing traditional operations, like addition or subtraction, you combine them logically using operations like “AND”, “OR”, and “NOT”. For example, 1 AND 1 = 1 since both input values are true, but 1 AND 0 = 0, since one input value is true and one is false.

This logic works extremely well with semiconductors since you can create a different type of transistor to correspond to each conceivable type of Boolean operation, and you can then combine these transistors so that they perform these operations and output a voltage equivalent to the correct mathematical result for any given input voltages.

Moreover, as long as the inputs are translated into on/off voltages, these operations can represent anything from simple addition to complex mathematical functions, as long as you string the transistors together correctly. Not only that, but a large portion of the Boolean algebra was devoted to taking standard mathematical operations and translating them into strings of Boolean operations. Which means that as long as you build the circuit to follow the Boolean logic, you can use it to perform most conceivable ordinary mathematical functions.

And that's what the processor in a computer is: a group of circuits that correspond to mathematical operations that can be called upon as needed. If you need to do simple addition, we've got a circuit for that! Need to compare two values and show which is greater? We got a different circuit for that! Need to compute the cosine of a given value: we can do that too!

The real question that follows from that is: how do we move from a simple calculator to a more general problem solver? And the answer is Software!

Theory of Computing - Introduction

While I have come across many good resources explaining different aspects of computing, and I'm sure there are more I haven't come across, I have yet to find a clear explanation that is both comprehensive and not filled with too much jargon for the lay person to understand. That is the goal I am aiming for with this (relatively short) series and we'll see how close I get to it.

To break it down by topic, we'll start with:

1. The Hardware.
2. The Software.
3. The Operating System.
4. Networking.
5. Mobile Computing.

---

Non-Standard Disclaimer:
(aka Surgeon General’s Warning for Pedantic Nitpickers)

The goal of this project is to concisely explain computing in theory, and somewhat, in practice. As such, be warned, there maybe things that are imprecise, misleading, that you consider to be inaccurate, or that actually are inaccurate.

However, ranting about it won't help because I'm not actually listening. What you should do instead is write your own response, publish it on your own web page and hope that people pay attention to whatever your “correct” information is instead of my “hopelessly muddled” version.

Where's Your Fourth American Republic Now??

I know I said I was going to go ahead with the theory of computing series, but a response to this piece of tribalistic nonsense has been sitting around for years, and I've decided to put it up now. History has already rebutted the article with both the past election and also with the completely lack of political realignment that the author says was "inevitable", but I think it's important as the fallacious spirit behind it seems to still be alive and well.

While I suppose anyone who has taken High School level U.S. History can agree that there are, roughly, three American "republics", the article begins its take with a complete misreading about the "death" of the first republic, i.e., the U.S. Civil War. The author claims that the civil war and its aftermath was primarily about State's rights and deciding that the nation came before individual states. He even goes so far as to say that it was this reasoning that led "a generation of southern West Point graduates [to follow] their states into secession in 1861."

But this is simply not true. The war was not primarily about State's Rights, but about a disagreement over enforcement of a change that threatened the livelihoods of the agrarian south. The South didn't go to war to protect the idea of a separate and intact "Virginia" or "Alabama", but because to not fight meant they would lose their plantations which was their primary source of wealth and which were unsustainable without slavery. State's Rights was merely the legal framework they used to try and settle the issues without violent conflict. They lost that claim through ordinary politics, and then they went to war, but if the issue was anything less important than the foundation of their entire economic and social structure at the time, there likely would not have been a war.

The increased national identity and reorganization of federalism was simply the result of having to organize these huge national armies over years of war and reconstruction. It was much harder for most people to continue to view a national conflict through the prism of individual states when they all had to fight in unison to win so they dropped that idea and instead pushed towards greater union. The way this worked out was similar to how WWII planted the seeds of racial equality as having to fight alongside diverse kinds of people broke down racism on one end, and being treated as equals in the army made the Black G.I. want to be treated as equals at home.

Another huge misreading was the author's take on the Great Depression and the transition from the "Second" to the "Third" American republic. The New Deal coalition was not so much a collection of "special interests" as it was the mobilization of the have-nots, who lost everything, against the haves. So, to rebut one of the key points in the analysis, the party that presides over a depression is not the one that loses the mandate, but rather the one that loses the mandate is the one that does the worst job of meeting the needs of those affected by the crisis. Only when no one meets these needs does a major swing take place and a new group seizes control of one or both of the parties.

This is readily apparent when you realize that the Republican Party of 1930 is dead. That coalition, which entirely favored the rich and big business never came back. What has replaced it is a party that links the rich and powerful with the populists, which used to be part of the Democrats but were ran out by differences with liberal wing of the party. If this was merely about government as arbiter of special interests, the populists would have no reason to do so as they did. And, in fact, it is this new fusion that is causing alot of the disfunction in the current GOP as the Republican leadership has to serve the populists' needs in order to get elected, even though alot of what the leadership wants to accomplish is contrary to the populists economic interests. So the leadership is forced to placate alot of extreme views in order to be seen as accepted, but they don't care as much about them as they do about the financial rear-guard action regarding taxation and regulations.

This also shows why there has not been some kind of major realignment in government structure in the last four years. The necessary condition for any kind of "New Republic" is a government that ignores or undermines the interests of a large number of people. That hasn't happened in the last four years and likely won't happen any time soon as the division is so close that neither party can afford to ignore or make unhappy any part of their coalition.

The author's incorrect prediction about both the political realignment and the nature of any future political action comes from a misunderstanding of what the "Third republic" is about. The "Third republic" is about equality of opportunity and a move towards large government solutions to problems, like environmental degradation or large financial crises, that are too large for any one segment of society to handle on its own. The other issues he lists, like pork spending and special interest capture, are not a product of the "Third Republic" but are a function of the unprecedented wealth America and the West has enjoyed since the 1950s and the parasites that are always attracted by it. To put it simply, under the "Third republic", pork spending is a luxury, clean air, clean water, and a safety net for the old and the sick is not.

This same sort of thing happened in the "Second republic" as well, only the big players then were business oligarchs. What ended their government capture was a combination of financial crisis and the rise of populism which led to increased regulation and accountability. What makes this time different is that the people who should be acting as a damper, that is, the populists in the GOP, are hugely dysfunctional and have been captured by a nihilistic ideology that forces them to keep moving away from government accountability instead of helping the government to find workable solutions. While the end result could be a "Fourth republic", I think the more likely outcome is that the fever finally breaks and the hard decisions about what to cut, or which taxes to raise, and what other limits to place on government can finally be made.