What was the first computer program you wrote?
For me, it was generating the first 100 prime numbers using the Sieve of
Eratosthenes. I had preceded that with many failed attempts at a problem my instructor had given me – parse a string of characters for valid decimal numbers. I couldn’t understand the purpose of the problem, or how to go about it. It all seemed silly and superfluous. But generating prime numbers was what did it for me. I understood the problem well enough to bother only about getting it work on my computer. It was a moment of epiphany when I realized that all I need to do to solve a problem of my interest is to carefully think about a set of instructions for the machine and the machine will faithfully, tirelessly follow them to get me an answer. This happened in 1993. I was not a teenager- I came late to computer programming – I had just finished my Bachelor’s in physics. But the delight of seeing those numbers getting printed on the screen resonated in my soul for days ahead. I was smiling and giggling with myself. All I could think of was about the next program I should write for that machine. Over the years, it has been rare to match that joy of my programming dawn.
I wrote my first program in K&R C. And I became a reluctant learner of new programming languages and dialects. Around me, I saw my friends wax eloquent about this awesome language or that nifty feature – but for me, it was always a question of show me a problem that you can do in the new language/dialect and I cannot do in C!! As a result, I stayed monotheistic in my programming practice for a very long time. And later, even when I stumbled into the deviations of C++ and Perl, I was still a programmer of the C DNA – Literals, Variables, Operators, Statements, For/While Loop, and the If/Else/Switch – these I cherished as valuable and worth knowing. The rest were mere details…..
What I didn’t realize then, and appreciated much later, was that the C Language describes an abstract (Von Neumann) machine which was very close to a real physical computer of 1970’s. Incredibly, it still helped my intuition as I wrote my programs in 1990’s. In other words, the language put very little in between the programmer and the real physical machine. Much water has flown through river Ganga since, and many new languages have become flavor of the seasons, but I find this aspect of the C Abstact Machine Model amazing!!
Now the variety of abstract machines for programming languages is an interesting subject in itself and I found this paper [1] very informative. However its description of C/C++ is very terse – everything for popular imperative languages is binned under the Algol60 family. On the other hand, the entire C++11 specification [2] claims to be the description of an abstract machine for the language. Here is the quote from section 1.9 (the as-if rule) –
The semantic descriptions in this International Standard define a parameterized nondeterministic abstract machine. This International Standard places no requirement on the structure of conforming implementations. In particular, they need not copy or emulate the structure of the abstract machine. Rather, conforming implementations are required to emulate (only) the observable behavior of the abstract machine …
an implementation is free to disregard any requirement of this International Standard as long as the result is as if the requirement had been obeyed, as far as can be determined from the observable behavior of the program. For instance, an actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no side effects affecting the observable behavior of the program are produced
That’s quite a mouthful and best avoided if you want to stay sane. Instead let me describe the abstract machine in simple, practical terms for a C/C++ programmer. The machine consists of a CPU (or better let’s call it the C++ALU) which executes program statements, atomically, serially one at a time. The C++ALU interacts with a Memory for operations on objects. Objects are entities living in Memory and these operations are for creation, manipulation, and destruction of objects. There are facilities for IO for the CPU through a separate subsystem. One can examine the machine state (defined by objects in memory) before and after every statement execution.
If you are familiar with modern computer architecture, you’ll quickly realize that this is a ridiculous machine compared to a real x86 platform on which we program. For example – there is no notion of memory/cache hierarchy, or machine registers, or machine operations, or out-of-order instruction pipeline, or multiple instruction issue etc. Also no virtual memory, system calls, traps, privilege modes etc. But even then, a beginning C/C++ programmer will benefit if she behaved as if she wrote her programs for the abstract machine.
For instance, let’s write the simplest valid C++11 program (first.cpp) – what I call the C++ALU’s NOP instruction. A program which does nothing. Here it is :
int main() {}
In all the examples, I use g++ 4.8.1 on a x86_64 Cygwin Machine and set the compiler options to -Wall -Werror -std=c++11. It comes as a surprise to many that main need not return a value, but the program is valid C++11 nevertheless. If you remove the return type, that is not valid C++11 by the standard, and the compile fails. If you change the return type to anything other than int, that is not valid C++11 either. main is a special function in C++11, it need not explicitly return. The default, implicit behavior is return 0.
Back to the first.cpp. Here is the compile command:
g++ -Wall -Werror -std=c++11 -g first.cpp -o first.exe
What should the size of the executable be? It is just a NOP instruction – so just one x86_64 instruction – say 64 bits, that is 8 bytes. du -b first.exe gives it as 62352 bytes!! Well that -g compile option puts a lot of debug information (symbol table) in the exe, so if I compile without -g, I get the size as 61660 bytes!! If I explicitly tell the compiler to remove the entire symbol table by a -s command switch, the executable size still comes to 6656 bytes!! Even if I try adding the size optimization switch -Os the size doesn’t go below 6656 bytes on my machine. That is an inflation of 832x from our original estimate of 8 bytes!!
This additional executable size comes from C++ runtime and standard library linked into your executable. Therefore, the first thing to realize is that programming a NOP in C/C++ is not like assembly – there is a runtime overhead which comes from the language itself. An objdump -d first.exe will show you in disassembly that our NOP program has lots of real x86 instructions to execute!!
To make matters more tractable, let’s just compile the program into an object file with
g++ -Wall -Werror -std=c++11 -s -Os -c first.cpp -o first.o
We’ve just compiled our source without linking the standard libraries and runtime. du -b first.o now gives 864 bytes!! Now we are getting somewhere. objdump -d first.o shows us the actual x86 instructions:
first.o: file format pe-x86-64
Disassembly of section .text.startup:
0000000000000000 main: 0: 48 83 ec 28 sub $0x28,%rsp 4: e8 00 00 00 00 callq 9 main+0x9 9: 31 c0 xor %eax,%eax b: 48 83 c4 28 add $0x28,%rsp f: c3 retq
That is 5 x86 instructions with 16 bytes.
REFERENCES
- Stephan Diehl, Pieter Hartel, Peter Sestoft – Abstract machines for programming language implementation, 1999, http://www.inf.ed.ac.uk/teaching/courses/lsi/diehl_abstract_machines.pdf
- ISO C++ Standard, https://isocpp.org/std/the-standard
ambleinrubble 