Reinvention of Programming

The complexity of software systems has grown beyond human scale. My intuition tells me that this complexity could be reduced by a few orders of magnitudes with a better design.

This animated gif is just an illustration of a 5 orders of magnitudes difference (x 100000) between the size of an algorithm and its extension. The size of the gif file is ~1600000 bytes but it was produced by a 16 byte long dos program.

My goal is to simplify programming to human scale and to make programming common knowledge like elementary mathematics.

Mathematics can be built upon the concept of ‘algorithm’ instead of the concept of ‘set’, which is already known. Addition, multiplication, straightedge and compass construction are algorithms which primary school children learn. It would be just one step further to teach what an algorithm is in general and how to construct algorithms.

My plan has the following steps:

These subtasks are still too complex to follow. For the first task, my idea is to go back in time when programs were simpler and reimagine programming from grounds up.

Going back 30 years in time (September, 2021)

Time travelling is possible. I already did it. I put aside my smartphone. I started to use nano, a text editor similar to Pico from 1989. I switched to alpine, an email client similar to Pine from 1992. The hardest step was to switch to elinks, a web browser similar to Lynx from 1992.

I could spend most of the time using just these programs on my computer. They were refreshingly simple to use, and I was surprisingly effective with them.

Using my own system (October, 2021)

The programs nano, alpine and elinks were simple enough for me to rewrite, especially because I used only a fraction of their features.

Instead of replicating their look-and-feel, I replaced alpine and elinks with my own solution, a Haskell source file containing 500 lines of code. (I reused programming libraries to do the lower level steps of receiving and sending emails and getting web pages.)

500 lines of code is so small that I can have full control over my email client and my web browser. I can change the code whenever I want. I can try out new ideas tailored for my workflows, which is a very good feeling.

I could replace nano too, but I decided to do that later, because I arrived to the point where I can reimagine what an operating system is, which is a lot more interesting! But before that I had to stop for starting my Patreon project.

Patreon project start (November, 2021)

We don’t have universal basic income, so I looked for an alternative. I chose Patreon because it gives enough independence and freedom for me, and it has very little bureaucracy.

Donate via Patreon

You can read my short CV on my homepage. Donate me if you are interested in the outcome of this project. I can work 40 hours per week on this project if I reach €1500 per month.

I log your questions and my answers to them on the questions and answers page.

I will monthly report my progress. From the first report, my work will be open sourced with documentation such that partial results can be reused in independent projects.

Reimagine operating systems (Plan)

High-level virtual machine

A virtual machine is a computer program which provides functionality of a physical computer. If I imagine a computer, I don’t have to build it to try it out; I can create a virtual machine instead.

I imagine a computer which has instructions for receiving and sending emails, getting web pages, receiving keyboard input and writing characters on the screen.

How I write a high-level virtual machine for this imaginary computer?
I use programming libraries written by others. Most of my time will be spend on designing the interface (the instructions) of the virtual machine, not on the implementation.

Why do I need a high-level virtual machine?
Its advantage is that I can develop prototype operating systems on it much faster. The disadvantage is that the prototype operating systems cannot change the way emails are received, for example, but that is fine for me, because I can focus on more interesting details instead. Later I can make the virtual machine lower level gradually to get closer to the real machine.

Interpreter-based operating system

I write an operating system which looks like an interpreter. An interpreter is a program which evaluate expressions given by the user line-by-line. For example, in the following interaction user input is marked with the ‘>’ character:

> 2 + 2
> 13 + 2 * 3

In the interpreter, one can name expressions like this:

> a = 6
> b = a + 4
> c = a * b
> c

Here a, b, and c are numbers. There are texts, lists and records with operations on them. For example, emails can be stored in a list of email records:

> emails = [ {from = "[email protected]", to = "[email protected]", body = "Hi Divip"}
           , {from = "[email protected]", to = "[email protected]", body = "Hi XY"}
> length emails
> body (last emails)
"Hi XY"

My interpreter-based operating system is similar to a shell with the following key differences:

How do I write this interpreter-based operating system?
I will reuse an existing interpreter, the Glasgow Haskell Compiler interpreter. Instead of lots of implementations, significant part of my time will be spent to work out the semantics of the operating system.

Why do I need this interpreter-based operating system?
This operating system is not user friendly, but usable, and it will serve as the theoretical base of the following, more user friendly operating systems.

Custom text-based user interfaces

The interpreter in the previous operating system communicates with the user by parsing text user input as expressions and printing expressions as text output for the user.

This can be enhanced in several ways:

I am going to implement the last option, probably in several steps. The semantics of UI will be based on my previous work on interactive programs.

I define two named UI expressions, alpine and elinks. They will have similar look-and-feel to the alpine email client and the elinks web browser.

I rewrite the interpreter (i.e. the operating system itself) as a UI expression. I expect that after this step I will have a beautiful and succinct definition of what an operating system is.

Robust and efficient code generation (Plan)

So far I didn’t consider the efficiency of my operating system. If I want to reinvent programming, my operating system should be faster than its competitors.

I love Assembly because it is fast, I love abstractions because they help to express my ideas and I love strong type systems because they enforce principles and prevent many kinds of bugs.

Unfortunately, if we generate the machine code from a high-level representation, there is no guarantee for the efficiency of the generated code. Sophisticated heuristics are used for efficient code generation, but heuristics are never robust: a seemingly innocuous change in the high-level representation may have a dramatic effect on the efficiency of the generated code.

There is no good code generator for all use cases, so the solution is to build the code generator from reusable blocks for each single program or for each problem domain.

It is very easy to mess up a code generator, unless the type system prevents wrong plugging of building blocks similar to certifying compilation.

First I formalise the semantics of the x64 machine code. I need only a subset of the x64 machine state, instructions and addressing modes. I plan to support SSE instructions to beat code generators like the code generator of GHC.

I define a code generator for my operating system. During this I don’t have to struggle with compiler bugs, because strong typing will prevent most of them. First I define combinators for location independent code generation. Then I introduce the stack and implement a simple static register allocator. I implement combinators for code sharing (subroutines). I implement combinators for dynamic memory allocation and a simple garbage collector. I implement tuples and tagged union data types which are parametric in the representation of their parts.

The Fibonacci function would look like this with my code generator combinators:

doWhile : (s : Rep) → (a : Type) → (a → a) → (a → Bool s) → a → a
doWhile = …

fib n = fst (fst (
    doWhile  IP  (Pair Unboxed (Int Reg) (Pair Unboxed (Int Reg) (Int Reg)))
        ((n, (x, y)) ↦ (n-1, (y, x+y)))
        ((n, _) ↦ n ≠ 0)
        (n+1, (1, 0))

(Bool IP) means that the Boolean value is determined by the instruction pointer, so it does not have to be stored in any other register or memory location. (Int Reg) means that the integer is stored in a register. Unboxed pairs take no extra space at all. Type checking would guarantee that the generated code uses the prescribed representations, otherwise type checking would fail with an error.

I generate code for my operating system with my code generator combinators. Note that at this point my operating system is still very simple because it is implemented on the top of a high-level virtual machine.

Back to present (Plan)

I implement primitives in the high-level virtual machine for drawing widgets, tracking mouse and touchpad input, playing sound and capturing camera input. Alternatively, I can make a virtual machine running in the browser. Its advantage is that the virtual machine would be much simpler and it would be platform independent.

I use the new primitives to add a graphical user interface to my operating system. I expect that I don’t have to redesign the basic principles of the operating system in this step.

Programming as common knowledge (Plan)

I think programming should be common knowledge like elementary mathematics or literacy.

I think that this is feasible. Primary school children in Hungary learn elementary arithmetic, straightedge and compass construction and lots of other algorithms. It would be just one step further to learn what an algorithm is. In fact, they should learn constructive mathematics which is based on the concept ‘algorithm’ instead of the concept ‘set’. I don’t believe that I can change the education system, but I believe that I can write a free mobile game to teach programming.

In the game the children will be introduced into a quite simple world. They will gain power as they level up in the game. When they finish the game they can put together applications to help them in real-life tasks.