Imperative Programming PDF

# Chapter 2 Basics of Imperative Programming ## Main Memory/Random Access Memory (RAM) - Stores both programs and the data that the programs operate on. - Consists of memory cells. - Each memory cell stores a binary data word with a fixed number of bits. - Memory cells are numbered consecutively s...

# Chapter 2 Basics of Imperative Programming ## Main Memory/Random Access Memory (RAM) - Stores both programs and the data that the programs operate on. - Consists of memory cells. - Each memory cell stores a binary data word with a fixed number of bits. - Memory cells are numbered consecutively starting from 0. - The number of a memory cell is called its address. - This architecture was first described in 1945. - The main memory can read or write any given memory cell using its address, in arbitrary order. - In "random access memory", "random" is used in the sense of "arbitrary". ## Central Processing Unit (CPU) - Controls the working of the computer and executes the program. - Consists of: - Control Unit: coordinates the other components of the computer and is in charge of running the program. - Arithmetic Logical Unit (ALU): contains the circuitry to perform arithmetic and logical operations. - Program Counter: a memory cell that stores the memory address of the next instruction in the current program. - Clock Generator: generates an electronic signal that synchronizes all the components of the computer. ## Input/Output (I/O) - Consists of physical devices that connect the computer to the outside world, e.g., keyboard, mouse, USB port, screen, network connector, sound card, and many more. ## Bus system - Consists of electronic connections that transport data, addresses, and the clock signal between the other three components. ## Basic Operation of a Computer - Once turned on, a computer starts to execute instructions from main memory. - This is done by repeating the following machine command cycle indefinitely, until the computer is turned off: - **FETCH:** The control unit uses the bus to send the contents of the program counter to the main memory. The main memory reads the memory cell with this address and uses the bus to send the contents back to the control unit. This represents the next instruction that needs to be executed. - **DECODE:** The control unit looks up the code for the instruction in a table and fetches additional operands from main memory, if necessary. - **EXECUTE:** The control unit coordinates the other components in order to perform the desired instruction, e.g., perform a calculation, a logical operation, or a comparison in the ALU; transfer data in the main memory; perform an input/output operation; or more. After this, the control unit updates the program counter to the next instruction. The next instruction is typically the instruction after the current one (sequential execution); but for certain instructions, it may be specified by an operand (jump) or by the result of comparison (conditional branch). - **REPEAT:** Begin the next cycle, for the next instruction. ## Assembly Languages - Provide a simple textual representation of the numerical machine language of a given computer. - Introduce mnemonics: short names for machine language instructions, such as ADD, SUB, MUL, CMP, BNZ, IN, OUT, and many more. - They provide a simple syntax for operators, memory references, and control structures. ## High-level Languages - Put the focus on the human who performs the programming task, and not on the machine that executes the instructions. - The goal is to have a formal artificial language that allows humans to solve algorithmic problems easily and efficiently. - The language should be close to how humans actually speak. - At the same time, it should have enough formal structure so that it can be processed by a computer. - They provide more structure and are easier to understand. - They provide language features that help humans to avoid and detect programming errors early in the development process. - High-level languages depend less on the concrete hardware: programs that are written in a high-level language can be used on computers with differing hardware and architectures. ## Expressions - Almost every high-level programming language has a notion of an expression. - An expression is a syntactic construct that has two crucial properties: a type and a value. - The type of an expression determines the range of possible values and the set of the possible operations. - Every programming language has its own specific collection of types. - Commonly, there are types that represent integral numbers, fractional numbers, truth values, characters, text, and more complicated data items. - The value of an expression is the specific result that is obtained by performing the computations that the expression describes. - A basic task in every programming language is to determine the value of a given expression, i.e., to evaluate the expression. ### Types of Expressions - **Constant expressions:** directly represents a single value. - Examples: 0, 1.5, "Informatik", True. - **Arithmetic expressions:** consist of numbers and basic numerical operations that are familiar from elementary school. - Examples: 1+2, 1.5*2/3. - **Boolean expressions:** consist of comparison operators, truth values, and logical operators. - Examples: 3<5, 7>2, True and not False, True or False, 3<5 and 7>2. - **Conditional expressions:** consist of three parts: a Boolean expression (the condition) and two arbitrary expressions (the yes-expression and the no-expression). - Examples: 0 if 3-5 else 10, 20 if 12>560 else 10. - **Function calls:** Python has built-in functionality that is represented as functions. - A function can receive zero, one, or more arguments, and it returns a result that depends on the parameters. - Functions can be used in expressions. - The type of such an expression depends on the function that is used. - Examples: len("Hallo"), abs(-1), int(2.7) ## Imperative Programming - **Imperative programming languages:** have the same structure as low-level languages, but at a higher level of abstraction. - An imperative program is a sequence of instructions that change the state of the computer. - Examples: C, C++, Java, C#, Pascal, Python, Rust, and many others. - **Declarative programming languages:** try to hide the underlying hardware completely. - They use another (mathematical) abstraction as the guiding idea for writing a program. - Examples: logic programming languages (based on mathematical logic; for example, PROLOG), functional programming languages (based on mathematical functions; for example, Haskell, ML, or Scala), or query languages (based on mathematical relations; for example SQL). - **Multi-paradigm programming languages:** combine ideas of different paradigms. - Examples: Python and Scala. ## Instructions of an Imperative Programming Language - **Assignments:** affect the state of the main memory, by creating, changing, or erasing data items. - **Control flow:** affect the state of the program counter, by controlling the order in which the instructions of the program are executed. - **Input and output:** affect the state of the input/output devices, by reading from or writing to devices in the outside world. ## Assignments - Assignment instructions are of the form: ``` name = expression ``` - Executing an assignment instruction first evaluates *expression* and then assigns the resulting value to a variable identified by *name*. - The precise interpretation of this process varies from programming language to programming language. - In Python, after evaluating *expression*, Python creates a new data object and stores it in the memory. This data object represents the type and the value that result from *expression*. The variable *name* is then associated with the data object. - A variable in Python can be thought of as a label that can be used to identify different data objects. - The type of a variable is a property of the data object and not of the variable name. - The same variable name can be associated with different data objects of completely different types. - Python is dynamically typed, which means the programmer is responsible for keeping track of the type of data object each variable is currently associated with. ### Reference Semantics - *name1* becomes synonymous to *name2*. - After the assignment instruction is executed, the identifiers *name1* and *name2* refer to the same data object in memory. - This is the interpretation that is used in Python. ### Value Semantics - A copy of the data object that *name2* refers to is made and associated with *name1*. - After the assignment instruction, *name1* and *name2* refer to two different data objects that have the same type and value. - This is the interpretation that is used in programming languages like C, C++, or Pascal. ## Input and Output - Input/Output instructions allow the program to communicate with the outside world (e.g., the user, the file system, the network, a screen, a speaker). - The precise details of input/output instructions vary widely from programming language to programming language. - They also depend on the precise nature of the outside world. ### Instruction for Outputting a Text onto the Screen - **print(arg1, arg2, ..., argk)** receives an arbitrary number of arguments. - Each argument is an expression. - The arguments are evaluated, and each result is converted to a string. - The strings are concatenated, separated by spaces. - The resulting string is then displayed on the screen. - *print* interprets certain control sequences that may appear in the argument strings, e.g., \n creates a new line, or \t performs a tab-operation. ### Instruction for Reading an Input from the Keyboard - **input(string)** outputs *string* onto the screen and reads an input from the keyboard. - The input is terminated by the return key. - The input is stored as a string object and can be assigned to a variable. - To convert the input string manually to another type, use the functions *int(.)* or *float(.)*. ## Control Flow - Using expressions, assignments, and input/output instructions, we can already write interesting imperative programs. - To obtain more powerful programs, we need instructions that allow us to adapt our program to the input data. - These instructions affect the control flow of the imperative program. - They change the order in which the instructions of the program are executed. - Control flow instructions modify the program counter in the CPU. ### Types of Control Flow Instructions - **Jumps:** the most direct way to affect the control flow in an imperative program. - To use a jump instruction, write a label in front of the instruction that you would like to jump to. - At another point in the program, write *goto* or *jump*, followed by the name of the label. - When the *goto*-instruction is executed, the imperative program continues with the instruction after the given label. - Jumps can lead to unstructured code that is hard to understand, hard to maintain, and hard to debug. - Modern imperative languages follow a structured programming approach and do not allow full-fledged *goto*-instructions. - Jumps are allowed only in very limited ways, e.g., in the context of exceptions or in the form of *break* or *continue* instructions in the context of loops. - It's bad programming style to use jumps. - **Conditional execution:** indicate that a certain sequence of instructions (called a *block*) should be executed only if a certain condition is met. - We can test for several conditions, and we can also provide a block for the case that no condition is met. - In Python, conditional execution is handled through the *if* construct. - The syntax is as follows: ```python if condition1: Block1 elif condition2: Block2 elif condition3: Block3 ... else: Blockn ``` - **Loops:** allow us to execute a sequence of instructions (a *block*) several times. - **for-loops:** allow us to iterate over all elements of a given domain or range. - There is typically an index variable that successively goes through all the possible values of the range, in order. - Syntax in Python: ```python for variable in range: Block ``` - *range* can be anything that contains a set of elements that we can iterate over. - One common scenario is that *range* consists of integers. - Written in Python as *range(a,b,s)*, representing the (ordered) sequence of numbers that is obtained by starting with *a* and repeatedly adding *s*. - The sequence stops when we meet or pass *b* (this last number is not included). - *s* may be negative, which means that we count downwards. - If *s* is positive and *b*≤*a*, or if *s* is negative and *b*>*a*, the range is empty. - If we omit *s*, then it defaults to 1. In this case, *range(a,b)* consists of all numbers from *a* (included) to *b* (excluded). - We can also use *range(a)*, which represents all numbers from 0 to *a*-1. - Another example of a range is a string. In this case, the variable is associated to all the characters that appear in the string, in order. - **Conditional loops/while-loops:** consist of a condition and a *block*. - The number of times the *block* is executed is controlled by the condition. - In Python, there is only one conditional loop. - The condition is necessary for continuation. - The condition is tested before the *block* is executed. - Syntax: ```python while condition: Block ``` - *condition* is a Boolean expression. It is evaluated first. - If the value is *False*, the execution continues after the *while* construct. - If the value is *True*, *Block* is executed. - The process continues until *condition* is evaluated to *False*. ## Error Handling - Computer programs need to have a capability to handle errors. - **Abort the program:** When an error occurs, the program is terminated, and we return to the operating system. All data is lost, and the program needs to be restarted. - Default behavior in many programming languages, including Python. - **Introduce a special value that indicates that an operation could not be executed as expected.** - Examples: - NaN (not a number): can indicate that a division through 0 has occurred. - *None*: returned by *int(input(...))* if the string input cannot be interpreted as an integer number. - This behavior is not implemented in Python, but it can be found in other languages like C. - **Use an error handling mechanism (SIGNAL, interrupt).** - Define a special error handler that is called whenever an error occurs. - The task of the error handler is to determine the cause of the error and to try to fix it. - The program is resumed at the position where the error has occurred, and it tries to repeat the critical operation. - If the error happens again, the error handler is called again, etc. - This mechanism is implemented in many operating systems but is not the default behavior in Python. - **Exceptions:** a structured way to deal with errors that tries to separate the actual code and the error handling mechanism. - They are similar to a global error handler, but work at a fine-grained level. - In Python, the general syntax is as follows: ```python try: block except: error handler ``` - Put the critical operation(s) into a *try-block*. - If the operations are executed without problems, the execution continues after the exception construct. - If an operation in the *try-block* causes an error, the *try-block* is aborted, and execution continues with the *error handler*. - The error handler is executed, and the program continues after the exception construct. - The error handler might provide a default value, might continue, or might be in a loop that is repeated until the operation succeeds.