Foundations of programming

Lecture One - Introduction to programming

Introduction

Course Name: Foundations of programming / introduction to programming

Lecturer: dr Marcin Witkowski

Laboratories: dr Paweł Skórzewski

HomePage: http://mw.home.amu.edu.pl/

Classes site: http://mw.home.amu.edu.pl/zajecia/PPR2017/PPR.html

WorkPlan

  1. Introduction, types of programming languages, pseudocode
  2. Variables, pointers.
  3. Datatypes and collections
  4. Simple instructions
  5. Data structures
  6. Functions and procedures
  7. Input / Output
  8. Debug
  9. Operators, Iterators
  10. Polymorphism
  11. Functional / object oriented programming
  12. Advanced topics, threads
  13. Software development process, agile, tdd
  14. Final Test during last classes: about 30 open/close quentions - mostly closed.

Slides (via HTML)

Click RIGHT / LEFT to change the slides

Click B / S to make the font smaller / bigger .

Click A to see all slides on a single page.

Click F11 to go full screen and back

Click UP / Down to see stuff below / above

Programming

Programming

Programming (dict.) - The process of developing and implementing various sets of instructions to enable a computer to do a certain task. These instructions are considered computer programs and help the computer to operate smoothly.

via: http://www.businessdictionary.com/definition/computer-programming.html

Dijkstra: "Originally we were obligated to write programs so that a computer could execute them. Now we write the programs and the computer has the obligation to understand and execute them."

Ways of presenting the program

Story

The number of present_students is the sum of the students in the class (add 1 for each student).

Diagram

a10

Flowcharts

Round elements stands for Start/End points.

Rectangular elements are used for operations.

Diamond elements are used for conditions.

Simple conditions can model loops and batch processing

a

Code

int present_students = 0;
for(auto student : studentsInTheClassRoom){
    present_students++;
}
printf("%d",present_students);

Pseudocode

Pseudocode is a structured language for describing algorithms.

It allows the designer to focus on the logic of the algorithm without being distracted by details of language syntax.

Pseudocode is not a rigorous notation, since it is read by other people, not by the computer.

You define the level of details you include in the pseudocode (is it a single operation or a method like search).

Simple Examples

If students grade is greater than or equal to 50

Print "passed"
    else
Print "failed"

Print means show something to the user (preferably on screen)

Set present_students to 0
For Students in the classroom 
    present_students <- present_students + 1
endFor
Print present_students

Pseudocode elements

It has been proven that three basic constructs for flow of control are sufficient to implement any "proper" algorithm.

SEQUENCE is a linear progression where one task is performed sequentially after another.

IF-THEN-ELSE is a decision (selection) in which a choice is made between two alternative courses of action.

WHILE is a loop (repetition) with a simple conditional test at its beginning.

Example - sequence

READ width of a rectangle
READ height of a rectangle
COMPUTE area of a rectangle

Example if-then-else

IF number of points > 50 THEN
    Student PASS
ELSE
    Student Failed
ENDIF

Example while

WHILE student_grade < 50
    do_more_exams()
ENDWHILE

Extra (but) useful stuff

It is often useful to include three more constructs:

REPEAT-UNTIL is a loop with a simple conditional test at the bottom.

CASE is a multiway branch (decision) based on the value of an expression. CASE is a generalization of IF-THEN-ELSE.

FOR is a "counting" loop.

Example repeat-until

REPEAT
    exams()
UNTIL students_grade >= 50

Example case

CASE  grade  OF
    A       : points = 90
    B       : points = 80
    C       : points = 70
    D       : points = 60
    F       : points = 50
ENDCASE

Example for

FOR students in classRoom
    present_students++
ENDFOR

Keywords

Some words like FOR, CASE, NEW, IF, ELSE have special meaning. We call them keywords

You need to know what they stands for.

You don't want to use them for different purposes.

List of the keywords for C++:

a2

Formatting conventions

Whichever way of presenting the program you choose there additional things to care for.

max = 0
sum = 0
count = 0,

WHILE true,
    READ age
    IF age == 0 THEN
        BREAK
    END IF
    IF age > max THEN
       max = age
    END IF
        sum = sum + age
        count = count + 1
    END WHILE


average = sum / count


IF count == 0 THEN
    PRINT "There was no input"
ELSE
    PRINT max, average
 END IF
 
max = 0 sum = 0 count = 0,
WHILE true,
READ age,
IF age == 0 THEN BREAK
END IF
IF age > max THEN max = age
END IF
 sum = sum + age,
count = count + 1
 END WHILE
 average = sum / count
 IF count == 0 THEN PRINT "There was no input"
 ELSE PRINT max, average
 END IF

Good practices

function foo() {
    if ($maybe) {
        do_it_now();
        again();
    } else {
        abort_mission();
    }
    finalize();
}
function foo()
{
    if ($maybe)
    {
        do_it_now();
        again();
    }
    else
    {
        abort_mission();
    }
    finalize();
}
studentsCounter;
listIterator;
averageOverLastWeek;
findBestInClass();
computeAverage();
NightShift;
FastCar;
DAYS_IN_THE_WEEK();
NUMBER_OF_SHIFTS();
a += b , c = 0; (a == b)
if (value) {, public class A { 
for (int i = 0; i < length; i++) 
(int) value , (String) value

History of programming

The binary numbering system works just like the decimal numbering system, with two exceptions: binary only allows the digits 0 and 1 (rather than 0-9),

aj

Binary encoding is not efficient enough for up-to-date requirements that is why although we can convert between decimal and binary, the conversion is not a trivial task. The hexadecimal (base 16) numbering system solves these problems.

History of programming

Programmers write instructions in various programming languages, some directly understandable by computers and others requiring intermediate translation steps. Hundreds of computer languages are in use today. These can be divided into three general types:

a. Machine Language

b. Low Level Language

c. High level Language

Machine language

Machine language is the “natural language” of a computer and such is defined by its hardware design. Machine languages generally consist of strings of numbers (ultimately reduced to 1s and 0s) that instruct computers to perform their most elementary operations one at a time.

Low Level Language

Machine Language were simply too slow and tedious for most programmers. Instead of using strings of numbers that computers could directly understand, programmers began using English like abbreviations to represent elementary operations. These abbreviations form the basis of Low Level Language. In low level language, instructions are coded using mnemonics.

DIV
ADD
SUB
MOV

A utility program called an assembler is used to translate assembly language statements into the target computer's machine code.

High level Language

To speed up the programming process, high level language were developed in which simple statements could be written to accomplish substantial tasks. Translator programs called compilers convert high level language programs into machine language.

Example

Source language:

5 * (9 + 12)

Assembly language (Intel x86):

mov eax,9
mov ebx,12
add eax,ebx
mov ebx,5
mul eax,ebx

Machine language (in Hex, approximately...):

B8 09 00
BB 0C 00
03 C3 
BB 05 00
F7 03

How is Programming Code Transformed into an Executable?

We depend on tools such as compilation and interpretation in order to get our written code into a form that the computer can execute.

Code can either be executed natively through the operating system after it is converted to machine code (via compilation) or can be evaluated line by line through another program which handles executing the code instead of the operating system itself (via interpretation).

Compilation vs Interpretations

Compiled

The major advantage of compiled languages over interpreted languages is their execution speed.

Examples of pure compiled languages include C, C++, Erlang, Haskell, and more modern languages such as Rust and Go.

The downsides are: in order to run a program written in a compiled language, you need to first manually compile it. Compiled languages are not platform-independent, as the compiled machine code is specific to the machine that is executing it.

cj

Interpreted

Examples of some common interpreted languages include JavaScript, PHP, Perl, Ruby, and Python.

Advantages: Platform independence, Reflection (ability to modify at runtime), Dynamic typing, Smaller executable program size, Dynamic scoping (elastic memory assigning and maintain).

The main disadvantage of interpreted languages is a slower program execution speed compared to compiled languages.

ij

Hybrid

Examples of hybrid languages include Java and the .Net framework.

The first step is to compile the current program from its human-readable language into bytecode. Bytecode is a form of instruction set that is designed to be efficiently executed by an interpreter and is composed of compact numeric codes, constants, and memory references.

The largest benefit of bytecode languages is platform independence which is typically only available to interpreted languages, but the programs have a much faster execution speed than interpreted languages.

hj

Compiler

Compiler - program that reads a program written in one language (the source language) translates it into an equivalent program in another language (the target language) checks for the presence of errors in the source program

ac

A compiler translates source language to assembly language. Compilation can be slow because it is not simple to translate from a high-level source language to low-level languages.

An assembler translates assembly language to machine language.

Compilation

image

Two primary phases

  1. Analysis: tokenize, parse, generate simple intermediate code (type checking)
  2. Synthesis: optimization (instructions in context), code generation, linking and loading

Lexical (linear) analysis

Lexical - of or relating to words or vocabulary of a language as distinguished from its grammar and construction Identifies tokens (keywords, identifier names, integers, etc.) of the programming language Token – sequences of characters that have a collective meaning.

int a;
inty b;

Syntax (hierachical) analysis

Syntax - the way linguistic elements (e.g. words) are put together to form constituents (e.g. sentence, phrase, clause) Also called "parsing". Usually the grammatical phrases are represented by a "parse tree"

for(int if (a == b))

Semantic

Semantic - of or relating to meaning in language. Checks for semantic errors gathers type information for the subsequent code generation phase uses hierarchical structure (determined by the parser) to identify the operators and operands of expressions and statements.

int a = 0;
char z = 'z';
double k = z+a;

Synthesis

Optimization - Find adjacent store-reload instructions, evaluate common sub-expressions, move static code out of loops, allocate registers, etc.

Code generation - Generate assembly or machine code.

Linking and Loading - Resolve external references between separately compiled units. Make sure that all references are relative to beginning of program. Load program into memory.

Linking

Linker (link-editor) connects:

Object files (.obj) from the program modules.
Additional library files.
Creates the executable (.exe file) program.
Usually uses relocatable addresses within the program.

Allows the program to run in different memory locations. Allows time-sharing and virtual memory.

Compiler errors

Each compiler phase can fail with a characteristic error.

"hello

Parse errors

(4 * (y + 5) - 12))

Type errors

sort(45)

Errors on later phases are not commonly supported.

A good compiler finds an error at the earliest occasion.

Usually, some errors are left to run time:

array index out of bouns
bugs

C++

image

C++

The Linker is used to connect subroutines that are not contained in the original code.

image

Summary

image