Menu Close

Articles

Basic Programming Concepts

This article is very important. We introduce basic concepts used in computer science to create computer programs. All programming languages are based on these concepts, so once you grasp them you can understand programming.

Basic programming concepts

Computer programs

Computer programs are step by step instructions that a computer can execute. Program execution will resolve a problem and communicate the result or will have a physical effect: for example printing a message to the computer monitor or moving the arm of a robot.

Turing Machine

A Turing Machine was invented by Alan Turing to break the German encryption machine Enigma. Enigma code was broken using the first universal computation machine that was named later computer.

Today we use term: Turing Complete to classify a computer language that can do what a Turing Machine can doTheoretical it can resolve any finite logical problem, by spiting it into simple operations.

State Machine

A “state machine”, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. A state machine can have a nice diagram that shows the initial state, the intermediate states and the final state of the machine.

State machines are useful to analyze and theorize the computation using abstract notations. In practice we use terms like “state”, “deterministic” from this theory. It is not so important to know this theory for making programs but is good to know where the terms are coming from.

Homework: read more about: finite state machine

Programming languages

Computer programs are created using a programming language. In computer industry there are many programming languages available, with different styles of programming, called programming paradigms.

Programming languages are written artificial languages created for humans to describe and resolve problems. A computer can read these languages and can convert them into executable instructions. In general, artificial languages are much more simpler than spoken languages but more precise.

The programming languages and computer languages are considered synonyms. However I think a computer language signify languages more close to the machine while programming language signify more abstract higher generation languages.

Example:

In the next example you can see a small Python program …

Language classification

Computer languages can be categorized by the complexity:

A: Close to machines

  • 1GL – First Generation:
  • 2GL – Second Generation

B: Close to humans

  • 3GL – Third Generation Language
  • 4GL – Forth Generation Language
  • 5GL – Fifth Generation Language

Examples:

  • Machine code is 1’st generation language;
  • Assembly is 2’nd generation language;
  • C is 3’rd generation language;
  • Java is 3’rd generation language;
  • SQL is a 4’th generation language;
  • Haskell is a 4’th generation language;

Learn a computer language

To learn a computer language you have to learn 3 things:

  • Logic – the reasoning process to resolve problems
  • Syntax – the words and rules of the language
  • Semantic – the program composition rules

Logical science

The logic was discovered by Greeks and formalized by Aristotle. Logic means thought or reason. Initially the logic was described only by philosophy. However in time a new mathematical branch was developed.

Logic is the science of truth. The purpose of logic is wisdom.

Logical Inference

The most important concept in logic is the inference also known as: deduction or implication. This is a conclusion we reach after we study the arguments or premises into a sentence. Inference is a way of thinking and reasoning.

Logical inference: Using valid arguments into a sentence we can derive a logical conclusion. Sound arguments will produce the same conclusion no matter who makes the arguments or who derive the conclusion.

The inference and reason do not work the same in all cultures. For example a Christian will not reach the same conclusion from a religious sentence as another person that is Buddhist or Muslim. The words may be interpreted in different ways and lead to different conclusions.

Most sentences are classified in two categories:

  • Imperative sentences
  • Declarative sentences

It is important to know that logic can’t create good inference from imperative sentences but only from declarative sentences. Imperative sentence is also a command from a superior entity or authority like Emperor, Queen, President or God.

By making inference from imperative sentences one culture can fall into irrational believes, wrong lows and social injustice. Logic can only work based on facts and solid arguments not on commands.

Fundamental logic rules and principles:

Let’s say we have an argument or a premise and a sentence. Following are some logic rules that can apply to these two:

  • Identity rule: An argument is identical with itself and not something else;
  • Contradiction rule: An argument cannot be true and false in same sentence;
  • Validity rule: An argument is valid if the truth of premises lead to truth of the conclusion.

Validity and Soundness

A deductive argument is said to be valid if takes a form that makes it impossible for the premises to be true and the conclusion nevertheless to be false. Otherwise, a deductive argument is said to be invalid.

A deductive argument is sound if and only if it is both valid, and all of its premises are true. Otherwise, a deductive argument is unsound. Unsound arguments are invalid.

Propositional Logic

The propositional logic study the relation between arguments and sentences. Deductive arguments can be propositions or sentences that can have Boolean values: True or False. This logic do not deal with the content of propositions but only with the relation between propositions.

In this rules we use A and B and P to represent logical propositions. Part of propositional logic are relations: IS, AND, OR, NOT. This relations have very precise rules that makes propositional logic a reliable theory.

Fundamental rules of Propositional logic:

These are rules that can’t be broken and are universal rules. Nobody can contradict these rules and these rules are universal in any culture and any language on earth. If you understand propositional logic you have done your first step toward understanding computer science.

For example:

  • If A is true and B is true then: P = A and B is also true.
  • If one of A or B is false then P = A and B is false.
  • If A or B is true then P = A or B is also true.
  • If A is true then P =  not A is false.
  • If B is false then P = not B is true.

Boolean algebra is the branch of algebra in which the values of the variables are the truth values true and false, usually denoted 1 and 0 respectively. This contrasts with general algebra that study other numbers not only the value 1 and 0.

Symbols:

Boolean algebra use symbols for logical operations and values 1 and 0 for truth values.

Logical Operations:

The table of truth shows you all possible combinations and the result for logical operators.

AB¬A¬BA ∧ BA ∨ BA ⊕ B
1001011
0110011
0011000
1100110

Fuzzy Logic

There is a logic that works not only with values 1=True and 0=False but we some values in between. Not everything is black or white but there is a gray area. This may be related to probabilistic values that are values between 0 and 1.

Predicate logic

Predicate logic study the things that are considered predicates and relations between the things. This is much more useful and powerful then the propositional logic. The things can be represented using data and values that can be connected with relational operators and symbols.

For example we can study numbers and relation between numbers using predicate logic. A number can be greater, equal or less than other number. Also a number can be different or not equal to other number.

We can use relational operators: >, <, = to show relation between numbers.

Example:

This is a simple program that is comparing 3 values and makes a logical deduction or decision. Decision statement in Python is “if”.

Data Symbols

In general a program manipulate data elements. We learn in school to count using Arabic digital numbers: 0,1,2,3,4,5,6,7,8,9. We also learn how to read and write text using Latin alphabet: Aa, Bb, Cc and so on. This is not the case in all cultures around the globe. Some cultures are using other symbols to represent numbers and text.

The mos popular encoding system for symbols is now known as Unicode. In the past we used different encoding for each country: ASCII, Extended ASCII. Now we use mostly: UTF16, UTF32 and UTF8.

Computer is using binary representations of “1” and “0” for encoding symbols. The “1” is usually a positive electrical charge while “0” represents no charge. It is similar to a light bulb. When light is on we can consider it logic = “1”. When lights is off we consider logic=”0″. 

Electronic devices can store data using specialized devices, components and methods: electrostatic, magnetic, optic etc. We cover some of these devices in CSH: Hardware class. The point is, computation is now digital. It is based on binary system.

Numeric Systems

A single storage unit is called bit. It can store exclusive: 0 or 1. Using multiple storage units grouped together  we can store combinations of 0 and 1. For example on two bit we can represent 4 combinations:  {00, 01, 10, 11}. This is called “binary” system. It has two digits: {0,1}.

If we pair up 3 bits we can represent more digits: {0,1,2,3,4,5,6,7} this kind of representation is called “octal” system, and is very rarely used.

We can use 4 bits and increase the number of combinations to 16 digits:  {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ,A ,B ,C ,D ,E ,F}. The first {0000 = 0} the last {1111 = F}. This representation is called “hexadecimal”.

As you can see there is not an exact match between the number of possible combinations and 10 digits. Therefore we have invented new digits: {A, B, C, D, E, F} sometimes these digits are represented using lowercase characters: { a, b, c, d, e, f }.

Computer science is using groups of 8 bits to represent numbers between (0..255) ≡ (00..ff). This is called “1 byte”= 8 bit. Two bytes used to represent a “1 word” = 16 bit. However this terminology was changed, now “1 word” = 32 bit. On 32 bit we can represent 4294967296 combinations.

Internal representation of numbers and symbols is different depending on the computer type, operating system and device. For now is suffice to know that “PC” encoding for example is different than “MAC” encoding.

Set of things

To understand the predicate logic we need to first understand a set of things. A set is a group of things that are unique represented and not duplicated. All things in a set can be similar or can have characteristics in common.

Things can belong to classes or category of things that have something in common. For example toys, animals, dogs, propel, furniture, homes. All this can be grouped into sets of things.

Predicate logic study the things and the relations between these things. For example a thing can belong to a set or do not belong to a set. Two sets can contain the same things or different things.

Sometimes we need to make a collection of things and sometimes the thing can be duplicated. In this case we have a list of things not a set because some of the things are not unique.

In mathematics there are 2 significant numeric collection types: Vector and Matrix. In Python we define a “List” that can have one or more dimensions.

Identifiers

When you create a program, you give names to things. These names are symbolic representations for data elements, structures or for expressions. You need a name so you can refer to data elements more easily, without repeating the data symbols themselves.

Example:

In this example we define a vector using a Python single dimension list and then check if an element is member of this list.

Identifier “sigil”

Sometimes a language uses some kind of prefix for variable names. This is called “sigil” and has the purpose to differentiate identifiers by purpose. For example in Ruby, the global variables use sigil “$”. That means all variables that start with “$” will be global variables while sigil “@” represent an object attribute.

In PHP all variables start with “$”, global or not global. Some developers find this rule annoying. In my languages Bee and EVE I use sigil “$” for global system constants and “@” for global system variables.

Type systems

Programming languages must deal with data. To do this, data is classified by category. For each category there are rules of representation and manipulation. This classification and the rules are called in computer science: “data system“. 

Data can be embedded into the program itself or it can be external. When embedded in the program, data is immutable. That means it is constant. You can change this kind of data only if you change the program.

External data is usually mutable. If is stored on a device that has R/W (Read & Write) capability like HDD (Hard Disk), or RW-CD (Read Write – Compact Disk). Sometimes a device can store external data in read only mode. For example optical disk or ROM (Read Only Memory) can store data that becomes immutable.

A variable represents data stored in RAM (Random Access Memory). We can alter value of this kind of data very easy, many times without wearing off the storage. In low level computation data is stored as bit: “0” or “1”, but a high level language you can store and manipulate abstract data types, for example: “numeric”, “string”, “boolean”, “date”, “time”.

Most computer languages do not have notion of measurement units. So a number can represent any kind of physical or abstract concept. For example: width, height, weight. Only “date” and “time” have measurement units. Computer scientists believe that a computer language becomes too complex if is dealing with measurement units.

Data Literals

Data literals are symbols or group of symbols that represent constant data. For example: 100 represent the number 100 written in decimal. There are numerous other notations for numbers, representing different data types.

A group of multiple data elements like a list or a data set can have a special literal created with alphanumeric symbols, delimiters and separators. Once you have learned these conventions, most languages will be easier to grasp since all are using same conventions.

ExampleTypeLiteral characters
‘a’Symbol(+-) & (0..9) & (a..z) & (A..Z)
‘Ω’Single quoted string(Δ Λ Φ Γ Ψ Ω Σ Π π ⊥ ǁ α β ɣ ε δ μ ω …)
“string”Double quoted string(∀ symbol)
0b11111111Binary number(0b) & (0,1)
12345Unsigned Integer number (N)(0,1,2,3,4,5,6,7,8,9)
-12345Signed Integer number (Z)(-+) & (0,1,2,3,4,5,6,7,8,9)
0xFFFFHexadecimal(0x) & (0,1,2,3,4,5,6,7,8,9) & ABCDEF
0xabcdHexadecimal(0x) & (0,1,2,3,4,5,6,7,8,9) & abcdef
U+FFFFUnicode code-point(U+) & (0,1,2,3,4,5,6,7,8,9) & ABCDEF
U-FFFFFFFFUnicode code-point(U-) & (0,1,2,3,4,5,6,7,8,9) & ABCDEF
0.05Floating  precision number (R)(-,.) & (0,1,2,3,4,5,6,7,8,9)
1E10Scientific notation for float numbers(-1E)& (0,1,2,3,4,5,6,7,8,9)
1e10Scientific notation for float numbers(-1e)& (0,1,2,3,4,5,6,7,8,9)

Expressions

You should be familiar with this concept from mathematics. In computer science there are 3 kind of expressions: Infix, Postfix and Prefix.  It is easiest to demonstrate the differences by looking at examples of operators that take two operands:

  1. x + y  : Infix
  2. + x y  : Prefix
  3. x y +  : Postfix

In these expressions x, y are operands while “+” is an operator. The most simple expressions are using one single operator and one operand. For example “-4” is an expression while “4” is not an expression but a single constant literal.  “2 + 4” however is an expression even if there is no variable involved.

Expressions can be combined in larger expressions using operators. Order of execution can be controlled using operator precedence and also round parenthesis (x+y). We will investigate this in our next examples:

Infix Expressions:

  • x+y+z
  • a + b / 2 + c * 2
  • (a + b) / (a * b) 
  • x ≠ y
  • a ≤ 5

Most computer languages are using infix expressions. You will learn details about literals and expressions in next course: CSP: Programming. Usually we describe literals and expressions as basic language concepts in first or second tutorial article about every computer language.

Read next: programming paradigms