Fundamentals

"Anyone can write code which a machine can understand - the trick is to write code which another human can understand." -- Martin Fowler

Introduction

• What is computer programming?
• What is a computer program?
• What is a programming language?
• Differences between languages (Currently popular languages Don't take it too seriously!)
• Compilers vs. Interpreters
• Creating a program
  1. Editing source files
  2. Compiling source files into object files
  3. Linking object files into executable files
• Executing the program
• Central Processing Unit (CPU)
  • Arithmetic and Logic Units
  • Registers
  • Cache memory
• Main memory

First C Programs (The Chicken and The Egg)

• A C program is essentially a collection of one or more functions.
• There must be a function named main; it must be in all lowercase.
• main is the program's starting point; it can call other functions by name
• There must be exactly one function named main in every program.

include files

function declarations (prototypes)

data declarations (global)

main function header
{
  data declarations (local)
  statements
}

other functions

int main(void)
{
}

int main(void)
{
  return 0;
}

Students that think that int main(void) can be changed to int main() are required to read this, as I'm not going to spend any more time on it. (Yes, I know that our textbook interchanges them, but you shouldn't.)

A second program in C that actually does something:

#include <stdio.h>

/* Say hi to the world */
int main(void)
{
  printf("Hello, World!\n");
  return 0;
}

Hello, World!

1. #include <stdio.h>
2.
3. /* Say hi to the world */
4. int main(void)
5. {
6.   printf("Hello, World!\n");
7.   return 0;
8. }

Editing, Compiling, Linking, and Executing

Edit/Compile/Execute Loop		Edit/Compile/Execute Loop Extended

Contrasting Languages at 3 Levels

a • b • (c + d)

C code (partial program)

int a = 1;
int b = 2;
int c = 3;
int d = 4;
int e = a * b * (c + d);

Assembly language (16-bit Intel x86)

Hand-coded assembler (80386 using GNU's assembler, comments start with # and are in bold)

.section .data
a: .long 1
b: .long 2
c: .long 3
d: .long 4
e: .long

.section .text
.globl _start

_start:
  movl a, %eax      #     a -> %eax
  movl b, %ebx      #     b -> %ebx
  imull %eax, %ebx  # a * b -> %ebx

  movl c, %eax      #     c -> %eax
  movl d, %ecx      #     d -> %ecx
  addl %eax, %ecx   # c + d -> %ecx

  imull %ebx, %ecx  # (a * b) * (c + d) -> %ecx
  movl %ecx, e      # put result in e

Machine language (Intel 80386)

Binary dump

0100110000000001000000110000000000000000000000000000000000000000 0001000000000001000000000000000000001100000000000000000000000000 0000000000000000000001000000000100101110011101000110010101111000 0111010000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000001110000000000000000000000000000 1000110000000000000000000000000011111100000000000000000000000000 0000000000000000000000000000000000000010000000000000000000000000 0010000000000000000000000110000000101110011001000110000101110100 0110000100000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0100000000000000000000001100000000101110011000100111001101110011 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 1000000000000000000000001100000001010101100010011110010110000011 1110110000011000100000111110010011110000101110000000000000000000 0000000000000000100000111100000000001111100000111100000000001111 1100000111101000000001001100000111100000000001001000100101000101 1110100010001011010001011110100011101000000000000000000000000000 0000000011101000000000000000000000000000000000001100011101000101 1111110000000001000000000000000000000000110001110100010111111000 0000001000000000000000000000000011000111010001011111010000000011 0000000000000000000000001100011101000101111100000000010000000000 0000000000000000100010110100010111111100100010011100001000001111 1010111101010101111110001000101101000101111100000000001101000101 1111010000001111101011111100001010001001010001011110110010111000 0000000000000000000000000000000011001001110000111001000010010000 1001000010010000100100001001000010010000100100001001000010010000 1001000010010000100100001001000000100001000000000000000000000000 0000101100000000000000000000000000010100000000000010011000000000 0000000000000000000010010000000000000000000000000001010000000000 0010111001100110011010010110110001100101000000000000000000000000 0000000000000000000000000000000011111110111111110000000000000000 0110011100000001011100110110100101101101011100000110110001100101 0010111001100011000000000000000000000000000000000000000000000000 0000000000000000000000000000000001011111011011010110000101101001 0110111000000000000000000000000000000000000000000000000000000000 0000000100000000001000000000000000000010000000000010111001110100 0110010101111000011101000000000000000000000000000000000000000000 0000000000000000000000010000000000000000000000000000001100000001 0110001000000000000000000000000000000010000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000001011100110010001100001011101000110000100000000 0000000000000000000000000000000000000000000000000000001000000000 0000000000000000000000110000000100000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000010111001100010 0111001101110011000000000000000000000000000000000000000000000000 0000000000000000000000110000000000000000000000000000001100000001 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000010111110101111101011111011011010110000101101001 0110111000000000000000000000000000000000000000000000000000000000 0010000000000000000000100000000100000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000101111101011111 0110000101101100011011000110111101100011011000010000000000000000 0000000000000000000000000000000000000000000000000000001000000000 0000010000000000000000000000000011111111

Now, which language would you rather work with?

Simple calculation:

int x = 5;
int y = 3;
int z = x + y;

or possibly like this: 

movl  $5, -12(%rbp)    ; put 5 into memory location x
movl  $3, -8(%rbp)     ; put 3 into memory location y
movl  -12(%rbp), %edx  ; put x into edx register
movl  -8(%rbp), %eax   ; put y into eax register
addl  %edx, %eax       ; add edx and eax registers, put result in eax register
movl  %eax, -4(%rbp)   ; put eax register into memory location z

Hopefully, you can see why people prefer to program in C rather than assembly. The end result is the same, but the amount of effort required from the C programmer is significantly less.

Putting It All Together

Step 1: Edit

Create a text file for this C code named simple.c. The size of this file is about 120 bytes (although this depends on the operating system and the type of whitespace used). You can use any text editor like, preferably Notepad++ (Windows only) or Geany (Windows, OS X, Linux, and others).

int main(void)
{
  int a = 1;
  int b = 2;
  int c = 3;
  int d = 4;
  int e = a * b * (c + d);

  return 0;
}

Step 2: Compile

The source code (text) is compiled into object code (binary) and saved in a file named simple.o. The size of this file will probably be between 500 and 2000 bytes (depends on the compiler and version). Using

gcc -c simple.c -o simple.o

Step 3: Link

The object file is linked (combined) with other object code and saved in a file named simple.exe. (The .exe is a Windows requirement as other operating systems don't require it.) The size of this file is about 10,000 bytes. (Again, depends on the compiler.)

gcc simple.o -o simple.exe

Step 3: Execute

Run the executable file by simply typing the name of the executable file (providing the .exe extension when executing it is optional under Windows):

simple

We can modify it to use the printf function and display the value of e after the calculations:

#include <stdio.h> /* printf */

/* Calculate some values */ 
int main(void)
{
  int a = 1;
  int b = 2;
  int c = 3;
  int d = 4;
  int e = a * b * (c + d);

    /* Display the result as an integer value */ 
  printf("%i\n", e);

  return 0;
}

Step-by-step:

Step 1 - Creating/Editing the source file (.c):

From the command line, invoke a text editor (e.g. notepad++) and create/edit the source file:

notepad++ simple.c

Just type the code above (or copy/paste) and save the file.

Step 2 - Preprocessing the source file (.i):

cpp simple.c -o simple.i

The output file (simple.i) contains the original source code, plus a lot of code from the stdio.h header file. The -o option tells cpp what to name the output file. The output file, simple.i must follow immediately after the -o option. (The file extension .i is the conventional way to name a preprocessed file.)

Note: The cpp command above stands for C pre-processor, NOT C plus plus.

Step 3 - Compiling to an assembly file (.s):

Use the GNU C compiler, gcc, to compile/translate the preprocessed file into assembly code.

gcc -fpreprocessed -S simple.i -o simple.s

Notes:

• The -fpreprocessed option tells gcc not to run the preprocessor because the file has already been preprocessed.
• The -S option (that's an uppercase 'S') tells gcc to only produce an assembly file instead of creating an object file.
• The -o option tells gcc what to name the output file. The output file, simple.s must follow immediately after this option. (The file extension .s is the conventional way to name an assembly file.)

Step 4 - Assembling into an object file (.o):

Use the GNU assembler (as) to assemble/convert the assembly file to object code.

as simple.s -o simple.o

The -o option tells the assembler, as, to name the object file simple.o (The file extension .o is the conventional way to name an object file.) To view the disassembled code, use either of these:

objdump -d simple.o
dumpbin /disasm simple.o

Step 5 - Linking to an executable file (.exe):

Use the GNU linker, ld (that's a lowercase 'L'), to link the object file with code from the standard libraries and create an executable named simple.exe

ld -m i386pep --wrap _Znwm --wrap _Znam --wrap _ZdlPv --wrap _ZdaPv --wrap 
_ZnwmRKSt9nothrow_t --wrap _ZnamRKSt9nothrow_t --wrap _ZdlPvRKSt9nothrow_t 
--wrap _ZdaPvRKSt9nothrow_t -Bdynamic --dll-search-prefix=cyg --tsaware 
/usr/lib/gcc/x86_64-pc-cygwin/4.8.3/../../../../lib/crt0.o 
/usr/lib/gcc/x86_64-pc-cygwin/4.8.3/crtbegin.o -L/usr/lib/gcc/x86_64-pc-cygwin/4.8.3 
-L/usr/lib/gcc/x86_64-pc-cygwin/4.8.3/../../../../lib -L/lib/../lib -L/usr/lib/../lib 
-L/usr/lib/gcc/x86_64-pc-cygwin/4.8.3/../../.. simple.o -lgcc_s -lgcc -lcygwin
-ladvapi32 -lshell32 -luser32 -lkernel32 -lgcc_s 
-lgcc /usr/lib/gcc/x86_64-pc-cygwin/4.8.3/crtend.o -o simple.exe

Notes:

• The lines above should all be on a single line at the command prompt.
• The exact command will depend on the version and location of the GCC C compiler on your computer. (This example is using version 4.8.3 of the compiler.)
• This command is Windows-specific and is different on other operating systems.
• You will rarely, if ever, need to type this cryptic line manually. (I've only done it once in my long career, and it was for this example!)
• The output shown (simple.i, simple.s, simple.o, and simple.exe) was generated under Linux. The output generated from Mac OS X and Windows would be similar.

Step 6 - Executing the program:

At the command prompt you just need to type the name of the executable file. On Windows type:

simple

or

simple.exe

On Mac or Linux type:

./simple

Usually, you don't need to supply the .exe file extension. The linker will add that automatically (on Windows) and leave it off for Mac and Linux. By omitting the extension:

-o simple

the linker will "do the right thing" based on the operating system.

Conclusion

gcc simple.c -o simple

Additional Compile Switches

To enable the compiler to perform a more thorough check of your source code, use the -Wall command line switch like so:

gcc -Wall -c simple.c -o simple.o

Now, if the compiler detects any potential problems or misuse of the C language, it will alert you with a warning message. For example, if I add the variable f like this:

  int a = 1;
  int b = 2;
  int c = 3;
  int d = 4;
  int f = 5; /* Add this variable, but don't use it anywhere */ 

  int e = a * b * (c + d);
  printf("%i\n", e);
  return 0;

I get this warning from the compiler:

simple.c: In function 'main':
simple.c:10: warning: unused variable 'f'

or, if I add something like this:

a + b - c;   /* Perform some calculation, but discard the value */ 

I get this warning from the compiler:

simple.c: In function 'main':
simple.c:11: warning: statement with no effect

Compile and Link in One Step

If you want to perform both compile and link steps with one command, don't provide the -c switch. This will compile and then link the program:

gcc simple.c -o simple.exe

However, if the compile step fails for any reason, the link step is skipped.

Other Useful Switches

If you want to generate the assembly output as above, use -S switch:

gcc -S simple.c 

This will produce a text file called simple.s which you can view with any text editor.

If you want to generate the preprocessor output directly from gcc, use -E switch:

gcc -E simple.c 

This will produce a ton of information to the screen. To capture the output so you can view it more easily, redirect the output to a file:

gcc -E simple.c > simple.out

The

  > simple.out 

causes the output to be written to a file (named simple.out) instead of to the screen. This file is a text file that you can view with any text editor.

Another Example

The C code: marathon.c: (with line numbers for clarity)

 1. #include <stdio.h> /* printf */
 2.
 3. /* Convenient definitions */
 4. #define YARDS_PER_MILE 1760
 5. #define KILOS_PER_MILE 1.609
 6.
 7. /* A marathon is 26 miles, 385 yards               */
 8. /* Prints the distance of a marathon in kilometers */
 9. int main(void)
10. {
11.   int miles = 26;    /* Miles in a marathon                 */
12.   int yards = 385;   /* Yards in a marathon                 */
13.   double kilometers; /* Calculated kilometers in a marathon */
14.  
15.     /* Convert miles and yards into kilometers */
16.   kilometers = (miles + (double)yards / YARDS_PER_MILE) * KILOS_PER_MILE;
17.
18.     /* Display the result on the screen */
19.   printf("A marathon is %f kilometers\n", kilometers);
20.  
21.     /* Return successful value to OS */
22.   return 0;
23. }
24.

Without line numbers (to copy and paste):

#include <stdio.h> /* printf */

/* Convenient definitions */
#define YARDS_PER_MILE 1760
#define KILOS_PER_MILE 1.609

/* A marathon is 26 miles, 385 yards               */
/* Prints the distance of a marathon in kilometers */
int main(void)
{
  int miles = 26;    /* Miles in a marathon                 */
  int yards = 385;   /* Yards in a marathon                 */
  double kilometers; /* Calculated kilometers in a marathon */
  
    /* Convert miles and yards into kilometers */
  kilometers = (miles + (double)yards / YARDS_PER_MILE) * KILOS_PER_MILE;

     /* Display the result on the screen */
  printf("A marathon is %f kilometers\n", kilometers);
  
    /* Return successful value to OS */
  return 0;
}

The assembly file named marathon.s (generated by: gcc -S marathon.c -o marathon.s)

The code above uses a few arithmetic operators. Many operators correspond with the ones you've seen in algebra. Here are a few binary operators:

Operator	Meaning
+	Add
-	Subtract
*	Multiply
/	Divide
%	Modulo (Remainder)

Computer Data Storage (Refresher)

• Computers represent information as patterns of bits (0's and 1's), known as base 2; e.g. 1011101000010101000111100011
• People use base 10; doesn't translate well into base 2
• Hexadecimal (base 16) works well with binary; computer programmers often work in base 16
• Group the bits into sets of 4 and translate into hexadecimal using the chart below

0	0000	4	0100	8	1000	C	1100
1	0001	5	0101	9	1001	D	1101
2	0010	6	0110	A	1010	E	1110
3	0011	7	0111	B	1011	F	1111

Character representations

The number above, 1011101000010101000111100011, translates into hex (BA151E3) and decimal (195,121,635) as:

Binary	1011	1010	0001	0101	0001	1110	0011
Hexadecimal	B	A	1	5	1	E	3
Decimal	195121635

Binary/Decimal converter (BinConverter.exe)

Lexical Conventions

There are different classes of tokens (lexical elements). In no particular order they are:

1. keywords
2. identifiers
3. constants
   • integers
   • characters
   • floating point
   • enumerations
   • string literals
4. operators (Lots!)
5. puncuators and separators

1. keywords
2. identifiers
3. constants
4. string literals
5. operators
6. puncuators

We will spend the entire course studying these aspects of the C language.

Identifiers

• Variables, constants, function names, and other elements of a C program are called identifiers; they are used to name things.
• Identifiers must contain only letters (upper- or lower-case), digits (0-9), and underscores ( _ ).
• They must begin with a letter or underscore. (Not a digit)
• There are certain words in C that have special meanings (keywords) and can't be used as identifiers. (e.g. int, float, const)
• C is a case sensitive language; upper- and lower-case letters are considered to be different. (e.g. SUM, Sum, sum are all different identifiers)
• Most compilers allow identifiers to be 31 characters or more in length. (You probably won't need more than that.)
• Use meaningful names, you will be glad you did (and your grade in this course will reflect it!)

Valid	Invalid	Invalid Reason
foo1	1foo	Doesn't start with a letter or underscore
_foo	$foo	1. Doesn't start with a letter or underscore 2. $ is illegal character
foo	foo$	$ is an illegal character
vaid_identifiier	invalid-identifier	- is an illegal character
a_long_and_valid_name	foo bar	Can't have spaces in identifier names
Int	int	int is a keyword

Good Identifier Names	Bad Identifiier Names
int rate;   int time;   int distance;   rate = 60;   time = 20;   distance = rate * time;	int x;   int y;   int z;   x = 60;   y = 20;   z = x * y;
#define PI 3.1416F   float radius = 5.25F;   float sphere_volume;   sphere_volume = 4.0F / 3.0F * PI * radius * radius * radius;	#define A 3.1416F   float id1 = 5.25F;   float id2;   id2 = 4.0F / 3.0F * A * id1 * id1 *id1;
double base = 2.75, height = 4.8;   double area_of_triangle = 0.5 * base * height;	double table = 2.75, chair = 4.8;   double couch = 0.5 * table * chair;

Keywords

auto	const	double	float	int	short	struct	unsigned
break	continue	else	for	long	signed	switch	void
case	default	enum	goto	register	sizeof	typedef	volatile
char	do	extern	if	return	static	union	while

Also, remember that C is case-sensitive so these keywords must be typed exactly as shown. int is not the same as Int or INT.

Constants

 int a = 1;
 float f = 3.14F;
 double d = 23.245;

Constant	Type
5	int
3.14	double
3.14F	float
'A'	int
"hello"	string