As promised, a tutorial going over the basics (very basics) of programming.
Some examples are provided in pseudocode, as well as in a cpp file attached.
A straightforward programming tutorial
by Ian ("jjz")
Introduction
Programming is pretty fun, at least to me. I enjoy learning languages and I enjoy learning the concepts behind making a fast, condensed, bug free, and highly human-readable program. I want to try to pass on some of what I have learned to readers here in the form of a short tutorial that goes over the basics in programming.
The darker side of things
Why do we need all these different high level programs and all types of data structures in the first place? Why didn't we just stay with the very basics, assembly, that translated directly into machine code. Wait, stop right there. Assembly? Machine code? High level programs? Data structures? Sure, many of you may know what I just said; however, I think some people might be scratching their heads here.
Let me give you a bit of background on how computers work, and where assembly, machine code, high level languages, and data structures come into play.
Computers, at their heart, compute. A computer is the processor. Not the monitor, harddrive, or any other peripherals. You give the computer instructions, it follows them, and then spits out an answer. The processor contains various components all made out of transistors that are assembled together to form logic gates. Transistors are the lowest level of abstraction in a computer. You can, technically, abstract more; however, this is not done. Transistors are small devices that can, basically, switch voltages from 0 to 1 or the other way around. This is a very simple description of a transistor and there is quite a bit more to explain; however, I am going to be brief with the description of low level computing until I reach the higher level areas like data structures and high level languages. Logic gates are simply collections of transistors in series or parallel that take electrical signals and actually use them for logic. Such as converting a 0 to a 1 (NOT GATE).
The most basic of programming
Now, let's go up the abstraction ladder a bit here and talk about machine language and assembly. For some reason people often consider machine language and assembly the same thing. I do not understand why this is. Machine language is 1s and 0s stringed together to form an instruction for the processor. Instructions can be various lengths depending on the architecture. That is not important for this tutorial, what is important is to understand that dealing with 1s and 0s is annoying for a computer scientist and slow, thus assembly was born.
Assembly is our first real human-readable language! It makes that "110" something that makes sense, like "LD". What is LD you ask? Well, not that you really need to know; however, it is an example of an instruction that loads a value into a register. Of course, most common architectures use a much more complex instruction set (the set of commands understandable by the processor) than just LD, LW, ADD, MUL, etc. The point is, assembly is an abstraction. We don't need to know what that "110" is anymore and why it is 110 and not 100. We just need to know that we are loading something into a register. This is what I have been trying to get at, abstraction. All programming languages, to an extent, came about because of the need to abstract further and further away from low level areas, in order to increase the rate at which code can be spit out by a programmer.
Modern languages
Now we can jump to modern languages! C, C++,
VB, SmallTalk, Python, Java, the list goes on. I will not be focusing on a specific language, and if I give code it will most likely be in pseudocode. I will provide some code examples in the form of attachments, and these will be in C or C++.
Let me get you introduced to some basic concepts in programming that are used universally and will come in handy while programming.
1)
Data structures: These are arranged sets of data in memory that can be used to more easily represent something, such as a list. Examples include arrays, linked lists, trees, the list goes on and on.
2)
Loops: These are built into the compiler to allow easy traversal of a data structure like those mentioned above. Examples include the while loop, for loop, for each loop, do while loop, etc.
3)
Recursion: Not every language supports recursion; however, it is extremely useful and most modern languages do support it. Anything recursive can in fact be done with a loop; however, recursion can often offer a much more eloquent solution to a problem than a loop. The downside is that recursion can, depending on the language, grow a stack and take up memory. It can, depending on the language, be considerably slower than loops as well.
4)
Structures / Objects: Structures are user defined types that can hold multiple pieces of data. Objects are an abstraction of structures and provide more functionality. Not all languages support objects, though most support some sort of structure declaration.
5)
Functions / procedures: Functions are sections of enclosed code that begin at some address and are executed sequentially in memory. Of course, code branches and such can change where the execution takes place. Functions return some type of value. Procedures are functions without a return value, (void in C, C++, System::Void in C++.NET).
6)
Variables: Variables hold data. Integers, doubles, floats, characters, objects, structures, whatever.
7)
Pointers: Pointers point to data that is in memory. Variables often hold pointers, although they can hold the actual data as well.
8)
If, if else, else: Statements that take execute code enclosed after them only if a certain condition is met.
9)
Switch: A functionality available in most languages that works similar to an if / else if / else statement; however, it can only evaluate equality (in most languages...).
Now that I have introduced to you some of the basics of languages, let me go into more explanation for each. I will introduce them in a manner which is easy to understand.
Section 1
Variables
As I explained, variables hold data. Variables can hold pointers to data as well; however, the pointers are in fact data themselves. Pointers are generally 32 bits (a bit is a value of either 1 or 0) or 64 bits long depending on if the target operating system you are compiling (to compile is to transform human-readable code down to assembly) is 32 bit addressable (meaning there are 2^32 unique addresses for memory) or 64 bit addressable, respectively.
Variables are required for programming, even all the way down to the assembly level in the form of registers. Registers are basically hardware variables. Some can be used by assembly programmers, others are reserved for system use. Anyway, you need variables because you need a way to store a result and use it later on. I will now give an example as to how variables could be used, in pseudocode.
Code:
Integer var1 := 50
while (var1 >= 0) {
Print var1
var1 := var1 - 1
} Why do you need a variable for this code to work properly? Well, how are goin going to subtract from a result if you do not have that result stored? That is what this variable is doing. It starts a result off as 50, then calculates the new result as 50 - 1 = 49, then 49 - 1 = 48, etc, until it hits 0 (which it will print). Without some way to store data, this type of code would not be possible. This is very basic code and is used very often in some form or another in programming.
Section 2
Pointers
Now that we have variables down, time to understand the difference between plain old data stored in variables and pointers to that data stored in variables.
In the above example, I show a variable that is storing data that you can manipulate directly. This is what most beginning programmers deal with, as they find pointers complex for some reason (I honestly have never understood why). I think pointers are very important, and thus I will explain them earlier than most CS professors would in a real life setting. Now, I will give the example above, but using pointers. I will define it as a pointer by using the * symbol.
Code:
Integer* pvar1
*pvar1 := 50
while (*pvar1 >= 0) {
Print *pvar1
*pvar1 := *pvar1 - 1
} This code works the same exact way as the original code that used var1, except I am dealing with a variable that holds a pointer to the data (50, in this case), instead of the data itself. In order to access the data that the pointer points to, or in any way modify this data, I must dereference the pointer. To dereference a pointer means getting accessing the memory address that the pointer points to so that it may be read from or written to. I dereference it by using a * in front of the variable name.
I will provide working code (in C), as an attachment, that will show variables that hold either data or pointers to data in action.
Section 3
Structures
Structures are types that the user defines in order to represent something more complex than a simple character, integer, float, whatever. They allow you to hold multiple data types and access them through one variable that holds the structure (or pointer to the structure). I will now give an example of a structure in action, in pseudocode.
Code:
Struct File {
String mExeName
String mDescr
Long mSector
Long mSize
}
Struct File file
file.mExeName := "C:\WINDOWS\ATI2DAG.SYS"
file.mDescr := "This is an ATI driver file that likes to infinite loop."
file.mSector := 1950
file.mSize := 6195 This is a structure that holds some information about a file. Perhaps an old operating system used something similar, although definitely more complex. I define the structure "File" as containing two strings and two longs (a long is basically two integer sizes. an integer is usually 32 bits wide, so a long is usually 64 bits wide). I then use the structure in a variable, and assign various values to the members of the structure. A structure is yet another type of abstraction. It is also a data structure.
Section 4
Arrays and Linked Lists
An array is what it sounds like, an array of data. The catch is that this data must be of the same type and contiguous. Data held in an array can be accessed by index, which generally starts from 0. Pointers to an array point to the beginning of that array in memory. Here is an example of an array in action.
Code:
Char[6] hello
hello[0] := 'h'
hello[1] := 'e'
hello[2] := 'l'
hello[3] := 'l'
hello[4] := 'o'
hello[5] := NULL
while (*hello != NULL) {
Print *hello
hello := hello + sizeof(Char)
} This code creates a string out of an array of characters. The array is set to size 6, with the last slot in the array being a NULL character that signifies the termination of the array. This is a security measure and is how character arrays have been handled for a long time. After the array of characters has been created, a loop is executed that prints out the array of characters to spell "hello". Since we are dealing with a pointer here (as I said, a variable holding an array is a pointer to that first element in the array), and I do not want to go over other loops yet, I am forced to use the NULL character as it is intended, as a termination character for a loop. I dereference hello, check what is there, and if it is not the NULL terminator then I print what is there and increment hello's position. Since hello is a pointer, I have to increment its position accordingly. Some languages support pointer addition (meaning that if I did hello := hello + 1, it would convert the 1 to sizeof(Char)), and some don't. Basically, memory is addressable by word (like a byte, for example), where as our actual data might be many bytes in size. In the code I provide above, if memory is addressable by byte and Char is a byte in size (as is usually the case for both), then hello := hello + 1 will always work as intended. However, if we are dealing with, let's say, an integer, which is 32 bits wide (4 bytes), then we would either have to do hello := hello + 4 or hello := hello + sizeof(Integer). sizeof(Integer) is safer since the size of an type can change from platform to platform.
A linked list is just a structure that has a pointer to another one of the same structure as one of its members. This allows for non-indexed traversal. Here is an example:
Code:
Struct Node {
Integer data
Node* next
}
Struct Node cur
cur.Data := 5
cur.Next := (Struct Node*)allocate(sizeof(Struct Node))
cur.Next->Data := 6
while (cur != NULL) {
print (String)cur.Data
cur := cur.Next
} Of course, you can have a previous link as well; however, I will not go into that. The allocate function I show allocates a place on the heap (where memory that is allocated at runtime and can be deallocated stays) for another node.
Section 5
Loops
While loops, for loops, do while loops, for each loops, etc. The syntax may differ; however, the goal is the same. Loops are for itterating a piece of code until a condition is met. Whether that condition be the end of the collection that is being itterated (the case with a for each loop) or a boolean argument evaluating to false (the case with a while, do while, for loop). Let me give some examples:
Code:
while (true) {
Print "truth"
}
for (Integer i := 0 to 5) {
Print (String)i
}
do {
Print "truth"
} while (true)
Collection strings := {"test", "hello", "whew"}
for each (String str in strings) {
Print str
} Which loops execute forever? Reread the first paragraph and it should be obvious.
Section 6
Conditional Statements
If / else if / else statements are crucial for creating a computer program. They allow you to ignore sections of code if an expression does not evaluate to true. Let me give an example:
Code:
Integer i := 5
if (i = 6) {
Print "NEVER EXECUTES"
} else if (i = 5) {
Print "ALWAYS EXECUTES"
} else {
Print "NEVER EXECUTES"
} The expression for the if statement evaluates to false, thus the block of code is skipped. The expression for else if evaluates to true, thus that block is executed and the the else is ignored. In an if / else if/ else statement, as soon as one statement evalutes to true, even if the others evaluate to true as well, they are ignored. This is not the case if only ifs are used. For example,
Code:
Integer i := 5
if (i = 5) {
Print "ALWAYS EXECUTES"
}
if (i != 0) {
Print "ALSO ALWAYS EXECUTES"
} Both if statements' expressions evaluate to true, and both are executed. However, if the code is as such:
Code:
if (i = 5) {
Print "ALWAYS EXECUTES"
} else if (i != 0) {
Print "IGNORED"
} Even though both expressions evaluate to true, the first one is the only one that is executed.
Section 7
Switch statement
Another statement, similar to if / else if / else, is the Switch statement. switch takes in a variable (generally, not an expression) and checks the value of that variable against cases. If a a case is met, the code enclosed in that case is executed. In c/c++, all cases after that are also executed unless you use "break" at the end of the code segment. This is not that important for general programming, though. Here is an example of a switch statement in action:
Code:
Integer i := 9
switch(i) {
case 3:
Print "NEVER EXECUTES"
case 8:
Print "NEVER EXECUTES"
case 9:
Print "EXECUTES"
} In most languages, a switch statement cannot take an expression like (i > 5). It can only take a variable and check equality. Why use a switch over an if / else if / else then? Because switch statements can only check for equality, they are executed faster than an if / else if / else statement.
Section 8
Procedures and Functions
Procedures and functions are used in virtually every language and provide another level of abstraction by allowing you to put a name to a code sequence that gets the purpose of that code sequence across easily. Procedures are functions that do not return a value. Both procedures and functions can take parameters, which are generally pass-by-value (meaning that the value stored in the variable passed as a parameter is what is actually stored in the parameter); however, can be pass-by-reference (the pointer to the variable passed as a parameter is copied to that parameter) and perform operations on the values stored in those parameters. Here is an example of a procedure and how to call it:
Code:
Procedure printString(String str) {
Print str
}
String str := "Can you?"
printString(str) Here is an example of a function and how to call it and use its return value:
Code:
Function Integer printString(String str) {
Print str
return strlen(str)
}
String str := "Yes, I can."
Integer ret := printString(str) The variable "ret" gets the length of the string "str" printed by the function "printString".
Section 9
Recursion
Recursion involves the use of procedures or functions, so naturally, it shall come right after them in this tutorial. Some people find recursion hard for some reason; however, it is very simple. Basically, recursion is just executing the same function within that function. For example
Code:
Procedure printString(String str) {
if (strlen(str) > 0) {
Print str
printString(Copy(str, 0, strlen(str)-1))
}
} What does this procedure do? If the length of the string passed as the parameter "str" is greater than zero then the string "str" is printed, and printString is called with a copy of the string "str" beginning at index 0 and having a length of the original str - 1. This will go on until the length of "str" is zero. If you do not have a terminating case (in this example, if the string length is zero or smaller than the procedure terminates), the recursion will go on forever and you will get a (most likely, depending on the language) stack overflow exception. A stack is kept in memory for a currently executing function. This stack holds the variables used by the function, its return value (if it has one), and its return address (what section of code executes after it). The stack, for most languages, grows with each function execution, and can thus overflow the area designated for it. When this happens, you get a stack overflow exception.
Section 10
Object Oriented Programming (OOP)
I will go over OOP very fast. They really deserve an entire text dedicated to them. A very very long text at that. OOP centers around Classes and their instantiated (created) form, Objects. Objects are structures with the added ability of function execution specific to that object and various Object Oriented Programming (OOP) ideas applied to the object. Such ideas include "inheritance" (if an object inherits from another object, that object gets all of the inherited object's members (variables and functions)), "encapsulation" (an object's private members are for its own use and are only accessible from functions designated as getter/setter functions. An object's methods should perform operations on data contained in the object and parameters passed with the function), "abstraction" (Classes that cannot be instantiated (created); however, hold a blue print for other classes to inherit the characteristics of that abstract class), and "polymorphism" (Being able to take more than one type of object and perform actions on it). To accomplish polymorphism, late/dynamic/runtime binding is used. This means that the type of the object is determined at runtime and the most specific function for that object is executed when requested. Here is an example of a class (blueprint used for an instantiated object)
Code:
Class File {
private:
String mExeName, mDescr
Long mSector, mSize
public new(String strExeName, String strDescr) {
mExeName := strExeName
mDescr := strDescr
}
public:
property String ExeName {
Function String get() {
return mExeName
}
Procedure set(String value) {
mExeName := value
}
}
property String Descr {
Function String get() {
return mDescr
}
Procedure set(String value) {
mDescr := value
}
}
property Long Sector {
Function Long get() {
return mSector
}
Procedure set(Long value) {
mSector := value
}
}
property Long Size {
Function Long get() {
return mSize
}
Procedure set(Long value) {
mSize := value
}
}
} Seciton 11
Exercises
Now that you have the basics down, let's go on to some situations where you need to choose something to use from what you have learned. I will give the answers at the end of this text; however, try to figure it out yourself first. These are arranged by difficulty. The first one, to do correctly (of course, real OS fs is much more complex), will take 2-3 minutes. The last one, to do correctly, can take 2-3 hours.
Situation 1: You are coding an operating system and are on the file system management. You want to create a data structure that represents a file on the operating system. What would that look like?
Situation 2: You are coding snake (the game). How would you represent the snake? Remember, you have to be able to update his position correctly.
Situation 3: You want to calculate fibonacci at n. What is the best way to go about this?
Situation 4: You want to find the shortest path from point A to every other point in a graph (a graph is just a collection of edges and vertexes, where vertexes are connected by edges). What is the best way to go about this?
Situation 5: You are designing a memory management system for an operating system. How would you go about this?
APPENDIX A: Answers to excercises
Questions and comments, as always, are welcomed.
-Ian (jjz)
Tech Discussion 
Programming Tutorial 
Linear Mode
