---
title: 'Programming Fundamentals'
source: 'https://academia.sh/en/courses/programming-fundamentals'
language: en
updated: '2026-08-17T04:39:42+00:00'
license: 'CC BY-SA 4.0'
lessons: 18
outcomes:
    - 'Uses the concepts of variable, control flow, function and data type independently of any language'
    - 'Analyzes a problem in pseudocode and translates it into a program'
    - 'Constructs the base case and the reduction step of a recursive solution correctly'
---

# Programming Fundamentals

A prerequisite-free introductory course that builds the concepts of variable, control flow, function and recursion without tying them to any particular language.

## Program, Value and Variable

What a program is, how values are bound to names, and building expressions with the basic data types.

### What Is a Program

Source: https://academia.sh/en/courses/programming-fundamentals/what-is-a-program

The input-process-output model, execution order, the distinction between statements and expressions, and error types.

The previous course established how a computer executes instructions: the processor
fetches, decodes, and executes bit patterns in memory. This course looks at the same
process from the other end — from the perspective of the person who writes the text
that produces those instructions.

This lesson asks: what does a program define, and what parts is it made of?

#### Input, Process, Output

A program defines a transformation with three components:

- **Input:** Data to be processed. It can come from the keyboard, a file, the
  network, or directly from within the program itself.
- **Process:** The steps that lead from input to output.
- **Output:** The result produced. It can be written to the screen, saved to a file,
  or passed to another program.

This course will use the same concrete problem from start to finish: **finding the
average and the largest value of a sequence of measurements.** Because the problem is
simple, every new concept can be introduced on familiar ground.

The problem's components are these: the input is a sequence of numbers, the process
is summation and comparison, and the output is two numbers.

#### Execution Order

Program text is read from top to bottom, and lines are executed in the order they are
written. At first glance this seems too obvious to state; it has two consequences,
however.

First, a value must be produced before it is used. Second, the same program run with
the same input gives the same output every time. This property is called
**determinism**, and it is the foundation of programs being testable.

Determinism has one condition: the program's behavior must depend only on its input.
A program that reads the clock, generates a random number, or pulls data from the
network can give a different result on the same call. Because such sources make a
program harder to test, they are restricted and kept separate from the rest of the
code; the software quality curriculum treats this distinction under the heading of
testability.

Order changes only through control flow structures — conditionals and loops are the
subject of the next topic. The previous course showed the hardware counterpart of
this: the program counter advances to the next instruction at every step, and branch
instructions write a different address into it.

#### The First Program

The following program computes the average of two measurements:

```python
# Input: two measurements
measurement_1 = 12
measurement_2 = 18

# Process: total and average
total = measurement_1 + measurement_2
average = total / 2

# Output
print(average)          # 15.0
```

Each of the five lines is a **statement**: it performs an action when executed. The
first four statements produce and store a value; the last one writes to the screen.

Lines beginning with `#` are **comments**; they are not executed. Comments are for
the reader and should be reserved for explaining **why** the code does something, not
what it does. What the code does is already written in the code itself.

Examples in this course will be given in Python. The concepts covered — variable,
conditional, loop, function — do not belong to any specific language, however; every
general-purpose language has a counterpart for them. Syntax changes; the concept
stays.

#### Running a Program

Program text resides in a file. Running the file starts the chain defined in the
previous course: the text is translated, instructions are produced, and the processor
executes them. There are two ways to start this chain.

**Running as a file** means giving the source file's name to the language's runner.
The program runs from start to finish and then stops. In this course, the output
produced will be written to the screen with `print`.

**Running interactively** means writing statements one at a time and seeing the
result immediately. It is useful while learning: what an expression produces can be
tried out without writing a program. Most examples in this course can be run either
way.

Taking input from outside is also a statement:

```python
text = input("Measurement: ")     # reads a line from the user
print("Entered:", text)
```

The `input` call pauses the program, waits for a line, and returns what was read
**as a string**. Even when a number is entered, the result is a string; it must be
converted before any numeric operation can be performed on it. This detail will be
taken up in this topic's final lesson.

For the sake of being reproducible, this course's examples mostly give input directly
within the code. In real programs the source of input varies; the
input–process–output structure does not.

#### Statement and Expression

Separating these two concepts pays off throughout every lesson that follows.

An **expression** produces a value. `12 + 18` is an expression; its value is $30$.
`measurement_1` is also an expression; its value is whatever that name is bound to.

A **statement** performs an action. `total = measurement_1 + measurement_2` is a
statement: it computes the expression on the right and binds the result to a name.

The practical consequence of the distinction is this: expressions can be nested
inside one another, statements cannot.

```python
average = (measurement_1 + measurement_2) / 2      # expression inside expression: valid
```

A statement has no result; this is why the form `x = (y = 3)` is invalid in many
languages. Some languages treat assignment as an expression too and allow this — a
language design decision, and a well-known source of error: writing an assignment by
mistake instead of a comparison produces a program that is valid but wrong.

#### Error Types

Programs can fail in three distinct ways, and each corresponds to a distinct stage.
The previous course's lesson on compilation stages gave the source of this
distinction.

**Syntax error:** The text does not conform to the language's grammar. The program
does not run at all.

```python
average = (measurement_1 + measurement_2 / 2      # unclosed parenthesis
```

**Runtime error:** The text is valid, but an operation is requested that cannot be
carried out during execution.

```python
divisor = 0
average = total / divisor              # division by zero
```

These errors stop the program while it is running. Where it stopped is reported
along with the error message.

**Logic error:** The program runs, produces no error, but gives the wrong result.

```python
average = measurement_1 + measurement_2 / 2       # 12 + 9 = 21.0  — expected 15.0
```

This third kind is the most expensive, because it does not announce itself. Due to
operator precedence, the line above performs the division first; the result is
numerically plausible and produces no warning. Only someone who knows the expected
value notices.

The only defense against logic errors is independently checking the result:
comparing against a hand-computed example, trying edge cases, and tests. The software
quality curriculum treats the systematic form of this defense.

#### Program and Algorithm

One last distinction: an **algorithm** is the steps that solve a problem; a
**program** is those steps written in a particular language. The same algorithm
gives different programs in different languages; different algorithms can be chosen
for the same problem.

This distinction serves a practical purpose: if a program does not work, one can ask
separately whether the problem is in the solution or in how the solution is written.
The two questions are investigated in different places.

For computing an average, the algorithm is one sentence: sum the values, divide by
their count. Which language the program is written in does not change that sentence.
The correctness and cost of algorithms is the subject of a separate course in this
curriculum.

#### Summary

- A program defines a transformation made of input, process, and output components.
- Statements execute in the order they are written; the same input gives the same
  output.
- An expression produces a value, a statement performs an action; expressions can be
  nested.
- Comments are not executed and are reserved for explaining why the code is written
  the way it is.
- A syntax error prevents the program from running at all, a runtime error stops
  execution, and a logic error silently produces the wrong result.
- An algorithm is the solution itself; a program is its expression in a language.

#### Next Step

The program above used names like `measurement_1` without defining what they are.
How does a name get bound to a value, when does that binding change, and what
happens in memory? The next lesson takes up the concept of a variable together with
the memory model established in the previous course.

### Variables and Binding

Source: https://academia.sh/en/courses/programming-fundamentals/variables-and-binding

How a name is bound to a value, the meaning of assignment, two models of variables, and naming conventions.

The previous lesson wrote `measurement_1 = 12` and said that it stores a value. This
lesson fills in that statement: how is the bond between a name and a value
established, when does it change, and what does it correspond to in memory?

The question runs deeper than it looks, because languages model this bond in two
different ways, and the difference between them produces observable consequences in
later lessons.

#### Assignment Is a Binding Operation

The statement `measurement_1 = 12` executes in two steps:

1. The **expression on the right** of the equals sign is evaluated; a value is
   produced.
2. That value is **bound to the name** on the left.

Order matters. The statement `total = total + 5` looks like a meaningless equation in
mathematics; as a program it is clear: the expression on the right is computed first
(adding $5$ to the old value), and then the result is bound to the same name again.

For this reason the equals sign here means "bind," not "equals." Some languages use a
separate symbol such as `:=` to avoid the confusion; the equality test, in turn, is
usually written `==`.

#### What a Variable Holds: Two Models

Languages model a variable in two different ways. The difference becomes clear when
considered together with the memory model established in the previous course.

**The memory-cell model.** A variable is a named region of memory reserved for a
particular type. Assignment changes that region's contents. The variable's address is
fixed for its entire lifetime; what changes is the bit pattern inside it. Most
low-level languages use this model.

**The name-object binding model.** Values sit in memory as independent objects; a
variable is a label attached to one of those objects. Assignment does not change the
object's content; it moves the label to a different object. Multiple labels can be
attached to the same object.

The observable difference between the two models shows up in whether two variables
share the same data:

```python
a = [1, 2, 3]      # a list object; 'a' is bound to it
b = a              # 'b' is bound to the same object; no copy
b.append(4)

print(a)           # [1, 2, 3, 4]  — also visible through 'a'
print(a is b)      # True          — same object
print(a == b)      # True          — same content

c = [1, 2, 3, 4]
print(a is c)      # False         — different objects
print(a == c)      # True          — same content
```

The `is` operator asks about **identity**: are two names bound to the same object?
The `==` operator asks about **equality**: is their content the same? Confusing the
two questions is a common source of error in programs that work with shared data.

This distinction will come up again in the lesson on passing arguments to functions;
the "by value or by reference" discussion there is a direct consequence of the two
models here.

The way to break sharing is to produce an explicit copy. Copying itself has two
depths: a **shallow copy**, which copies only the outer shell, and a **deep copy**,
which copies the entire nested structure. In a shallow copy the inner objects are
still shared; this is a common reason data assumed to be copied changes unexpectedly.
Since the cost of copying grows with the size of the data, the choice between sharing
and copying is a design decision.

#### Rebinding and Order

A name can be bound to different values over the course of a program. This brings
with it an order-related trap: swapping the values of two variables cannot be done
with two direct assignments.

```python
x = 3
y = 7

# Wrong: x's old value is lost after the first assignment.
x = y
y = x
print(x, y)        # 7 7  — no swap happened

# Correct: a temporary name is used.
x, y = 3, 7
temp = x
x = y
y = temp
print(x, y)        # 7 3
```

Some languages support multiple assignment, and the swap collapses to a single line
(`x, y = y, x`); since the right side is fully evaluated before binding takes place
in this form, no temporary name is needed. This syntactic convenience does not change
the underlying rule.

#### An Undefined Name

What happens if a name is accessed before it is bound? The answer depends on the
language's variable model, and this is the second observable difference between the
two models.

In the name-object binding model, the name is not yet bound to any object; accessing
it gives an explicit error:

```python
# print(total)     -> runtime error: 'total' is not defined
total = 0          # bound first
print(total)       # 0
```

In the memory-cell model, space has already been reserved for the variable, and a bit
pattern already sits there. If the language does not zero out the reserved space, the
value read is a meaningless leftover pattern from previous use. The program may or
may not crash; it can give a different result on every run.

The danger of this second case is that the error has no symptom. For this reason,
languages that use this model either require an initial value, produce a compiler
warning, or automatically zero out the reserved space.

The general rule is the same under both models: **a variable is bound to a
meaningful value before it is used.** Putting the initial assignment on the same
line as the declaration makes this rule visible.

#### Naming

Names follow the language's rules and the team's conventions.

**Rules** belong to the language and are mandatory: which characters a name can
start with, whether case is distinguished, which words are reserved. Keywords such as
`if` or `while` cannot be used as variable names.

**Conventions** belong to the team and exist for readability:

- A name states **what the variable holds**: `total`, `measurement_count`, `largest`.
- Single-letter names are used only in narrow, conventional contexts (such as a loop
  counter).
- An abbreviation is spelled out if it cannot be assumed familiar to the reader.
- A single naming convention is used within a project; the same concept is not
  referred to by two different names.

Choosing names is not decoration. Code is read more often than it is written; names
determine the effort every reader of the code spends. The software design curriculum
details this topic under the heading of clean code.

#### Constants

Some names must stay bound to the same value for the entire run of the program: a
conversion factor, an upper bound, a configuration value. These are called
**constants**.

Languages handle this in two ways. Some languages enforce constancy: reassigning a
constant is a compile error. Others rely on convention alone — the name is written in
uppercase, and it is expected not to be changed.

```python
MEASUREMENT_LIMIT = 100        # treated as constant by convention
```

The benefit of using a constant is that it prevents the same value from being
repeated in multiple places in the code. When the value changes, a single line is
updated; numbers scattered through the code do not need to be hunted down. Its
second, less obvious benefit is loading the name with meaning: the number `100`
appearing in a condition tells the reader nothing, while the name
`MEASUREMENT_LIMIT` states what the bound represents.

#### Summary

- Assignment evaluates the expression on the right first, then binds the result to
  the name on the left; the equals sign means binding, not equality.
- Languages model a variable in two ways: a named memory cell, or a label attached
  to an object.
- Multiple names can be bound to the same object; `is` tests identity, `==` tests
  content equality.
- The order of rebinding matters; a swap requires a temporary name or multiple
  assignment.
- Naming rules belong to the language, conventions belong to the team; a name should
  state what the variable holds.
- Constants gather repeated values into a single point.

#### Next Step

This lesson bound names to numbers and to lists, and the two were seen to behave
differently. What exactly does a value's type determine, though, and how many types
are there? The next lesson takes up the basic data types and the operations each of
them supports.

### Basic Data Types

Source: https://academia.sh/en/courses/programming-fundamentals/basic-data-types

The concept of type, integers, real numbers, booleans, strings, and null values; static and dynamic typing.

The previous lesson bound a name to a number, then to a list, and the two behaved
differently. The list had an `append` operation; the number did not. The name for
this difference is **type**.

This lesson defines the concept of type and introduces the basic types that have a
counterpart in every programming language.

#### What Is a Type

A **type** specifies two things together:

1. Which values are valid — the set of values.
2. Which operations are defined on those values.

The integer type's set of values is the integers within a certain range; its
operations are things like addition, subtraction, and comparison. The string type's
values are sequences of characters; concatenation and search are defined, subtraction
is not.

The previous course's conclusion applies directly here: memory contains only bit
patterns, and meaning comes from the interpretation rule applied to a pattern.
**A type is exactly that interpretation rule.** The programming-language answer to
whether the pattern `0x41424344` is an integer, a real number, or text is that
value's type.

#### Integers

The integer type carries numbers with no fractional part. Two facts established in
the previous course apply here: fixed-width integers have a range, and overflow
occurs once that range is exceeded.

Languages diverge on this point. Some use fixed width and handle overflow either by
wrapping or by raising an error. Others — Python is one of them — grow integers as
large as needed; the only limit is memory.

Two division operations must be distinguished:

```python
print(7 / 2)        # 3.5   — real division
print(7 // 2)       # 3     — integer division (rounds down)
print(7 % 2)        # 1     — remainder
print(-7 // 2)      # -4    — rounding down also applies on the negative side
```

The rounding direction of integer division differs between languages: some round
toward zero, some round down. In code that works with negative numbers, this detail
changes the result.

#### Real Numbers

The real number type carries fractional values in floating-point representation. The
previous course's warning applies here as well: values are approximate and are not
compared with equality.

```python
print(0.1 + 0.2 == 0.3)                    # False
print(abs((0.1 + 0.2) - 0.3) < 1e-9)       # True  — comparison with tolerance
```

Practical rule: quantities that require precision, such as money, are not held in
floating-point types; decimal-based types, or integers carrying the smallest unit,
are used instead.

#### Booleans

The boolean type has only two values: true and false. These values are usually not
written directly; they are produced by comparisons.

```python
measurement = 12
print(measurement > 10)          # True
print(measurement == 10)         # False
```

Boolean values are the input to the conditional branching in the next topic. A
condition "being true" means it produces a value of this type.

Many languages also allow non-boolean values to be used in a condition: zero, an
empty string, and an empty collection count as false; everything else counts as
true. This convenience can reduce readability; code is less prone to
misunderstanding when what a condition tests is written explicitly.

#### Strings

The string type carries sequences of characters. The previous course's lesson on
character encodings gave the detail underlying this type: a string is a sequence of
code points, and it is turned into bytes in memory according to an encoding.

```python
name = "value"
print(len(name))             # 5    — code point count
print(name[0])               # v    — indexing starts at zero
print(name.upper())          # VALUE
print("value" + " " + "1")   # value 1
```

Indexing starting from zero is a convention common to most languages, and it comes
from address arithmetic: an index states how many elements have been advanced past
the start.

In many languages strings are **immutable**: a string's content cannot be changed,
only a new string can be produced. This is why string concatenation is expensive
inside a loop; every concatenation creates a new object.

#### Collections

Types that hold a sequence of values instead of a single value form the input to the
course's shared problem:

```python
measurements = [12, 18, 7, 25, 14]     # list: ordered, mutable
print(len(measurements))               # 5
print(measurements[0], measurements[-1])   # 12 14
print(sum(measurements) / len(measurements))   # 15.2
print(max(measurements))               # 25
```

This lesson introduces collections only enough to use them; their internal
structure, costs, and selection criteria are the subject of the **Data Structures**
course.

#### Immutable and Mutable Types

Types are also distinguished by whether their values can be changed after creation.

An **immutable** value's content cannot be changed after it is created. Numbers, and
strings in most languages, belong to this class. Every operation that looks like a
change in fact produces a new value.

A **mutable** value's content can be updated in place. Lists belong to this class.

```python
text = "value"
new = text.upper()
print(text, new)          # value VALUE  — the original string did not change

measurements = [12, 18]
measurements.append(7)
print(measurements)             # [12, 18, 7]  — the list changed in place
```

The distinction gains weight when combined with the sharing rule from the previous
lesson. If two names are bound to the same object and the object is of a mutable
type, a change made through one is also visible through the other. If the object is
immutable, no such surprise occurs: since a change produces a new object, the other
name stays bound to the old value.

For this reason, shared data requires care when working with mutable types;
immutable types, in contrast, are safe to share. The same observation will be
repeated in the lesson on passing arguments to functions.

#### Null Value

Most languages have a special value that denotes the state of "no value." This value
expresses a result that has not yet been computed or could not be found.

The cost of this convenience is that this value can turn up in unexpected places:
code that tries to operate on a null value raises a runtime error. Some languages
address this risk at the type level and mark values that may be null with a separate
type, so that whether the check was performed can be tested at compile time.

#### When Type Is Checked

Languages test type compatibility at two different times.

**Static typing:** Types are known and checked during compilation. An incompatible
operation is caught before the program ever runs. In exchange, types must be
declared or inferred.

**Dynamic typing:** Type information is carried on values, and checking happens at
run time. The syntax is shorter; in exchange, the same error stays invisible until
the relevant line executes.

```python
number = 5
text = "5"
print(number + number)         # 10
print(text + text)             # 55   — string concatenation
# print(number + text)         # runtime error: incompatible types
```

The error in the third line surfaces under dynamic typing only once that line runs.
Under static typing, the same expression would have been rejected before running.
The principle established in the previous course's lesson on compilation stages
applies here as well: the question is **when** the error is seen.

#### Summary

- A type specifies the set of valid values together with the operations defined on
  them; it is the programming-language name for the interpretation rule applied to a
  bit pattern.
- Integer division comes in two forms, and the rounding direction varies between
  languages.
- Real numbers are approximate; they are compared with tolerance rather than
  equality.
- Boolean values are produced by comparisons; a null value denotes absence and is a
  source of runtime errors when left unchecked.
- Strings are sequences of code points; in immutable types every change produces a
  new value, in mutable types the content is updated in place.
- Static typing catches errors before running, dynamic typing catches them while
  running.

#### Next Step

Types have been defined; it is now time to build expressions from these values. The
next lesson takes up arithmetic, comparison, and logical operators, along with the
operator precedence rules that — in an earlier lesson — were the source of a logic
error.

### Operators and Expressions

Source: https://academia.sh/en/courses/programming-fundamentals/operators-and-expressions

Arithmetic, comparison, and logical operators; precedence, associativity, and short-circuit evaluation.

The first lesson gave an example of a logic error: the expression
`measurement_1 + measurement_2 / 2` did not give the expected average. The error
came from not knowing in which order the operators are applied.

This lesson defines those rules. The rules repeat across languages with small
differences; what is common is that precedence agrees with the conventions of
mathematics.

#### Arithmetic Operators

| Operator | Meaning | Example | Result |
|---|---|---|---|
| `+` | addition | `12 + 18` | 30 |
| `-` | subtraction | `18 - 12` | 6 |
| `*` | multiplication | `6 * 7` | 42 |
| `/` | real division | `7 / 2` | 3.5 |
| `//` | integer division | `7 // 2` | 3 |
| `%` | remainder | `7 % 2` | 1 |
| `**` | exponentiation | `2 ** 10` | 1024 |

The remainder operator is used more often than it appears: whether a number is even
(`n % 2 == 0`), a counter cycling at fixed intervals, and distributing values across
a fixed number of buckets are all written with this operator.

#### Comparison Operators

Comparison operators produce a boolean value: `==`, `!=`, `<`, `>`, `<=`, `>=`.

Writing the equality test as `==` is meant to distinguish it from assignment,
written `=`. Confusing the two produces a program that is valid but wrong in some
languages; for this reason many languages forbid assignment inside a condition.

The distinction established in the previous lesson holds here too: `==` tests
content equality, `is` (or its counterpart) tests whether it is the same object.

Some languages allow comparisons to be chained:

```python
measurement = 12
print(0 < measurement < 100)          # True  — two comparisons and a logical 'and'
```

This notation is readable but not universal; in most languages the same expression
gives a result different from what is expected, because `0 < measurement` is
computed first and its result is then compared with `100`.

#### Logical Operators

Three logical operators combine conditions:

| $a$ | $b$ | `a and b` | `a or b` | `not a` |
|---|---|---|---|---|
| false | false | false | false | true |
| false | true | false | true | true |
| true | false | false | true | false |
| true | true | true | true | false |

This table is identical to the bit-level AND/OR tables from the previous course. The
difference is that these operators work on the entire expression, not on individual
bits.

#### Short-Circuit Evaluation

Logical operators have a distinguishing behavior: once the result is determined, the
right side is **never evaluated**.

- In the `and` operator, if the left side is false, the result is false; the right
  side is not examined.
- In the `or` operator, if the left side is true, the result is true; the right side
  is not examined.

This is not merely a speed optimization, it is a programming tool: the condition
required for the right side to run safely is secured by writing it on the left.

```python
divisor = 0

# The division never happens because the left side is false; no error occurs.
if divisor != 0 and 10 / divisor > 1:
    print("large")
else:
    print("condition not met")      # condition not met

measurements = []

# The first element is not accessed because the left side is true.
if len(measurements) == 0 or measurements[0] > 10:
    print("empty or first measurement large")   # empty or first measurement large
```

If the order of the two conditions is swapped, the programs raise a runtime error.
The order of conditions is therefore a matter of correctness, not style.

#### Precedence and Associativity

**Precedence** determines which of two different operators is applied first;
**associativity** determines which direction operators of the same precedence group
in.

The commonly used precedence order, from highest to lowest:

| Order | Operators |
|---|---|
| 1 | `()` grouping |
| 2 | `**` exponentiation |
| 3 | unary `-` (sign) |
| 4 | `*`, `/`, `//`, `%` |
| 5 | `+`, `-` |
| 6 | comparisons |
| 7 | `not` |
| 8 | `and` |
| 9 | `or` |

```python
print(2 + 3 * 4)          # 14   — multiplication first
print((2 + 3) * 4)        # 20   — grouping changes precedence
print(2 ** 3 ** 2)        # 512  — exponentiation right to left: 2 ** (3 ** 2)
print(-2 ** 2)            # -4   — exponentiation before unary minus: -(2 ** 2)
print(10 - 3 - 2)         # 5    — subtraction left to right: (10 - 3) - 2
print(True or False and False)   # True — 'and' first
```

The logic error from the first lesson is explained by this table: in the expression
`measurement_1 + measurement_2 / 2`, division is at order four and addition at order
five; division is performed first.

Practical rule: knowing the precedence rules is necessary, but relying on the reader
knowing them is not advisable. Using parentheses where confusion is possible does not
substitute for knowing the rule — it makes the rule visible.

#### Compound Assignment

Updating a variable based on its own value is written so often that languages offer
a short notation for it:

```python
total = 0
total = total + 12       # explicit form
total += 18               # compound assignment: same operation
print(total)              # 30

counter = 10
counter -= 1                 # 9
counter *= 2                 # 18
counter //= 5                # 3
print(counter)                # 3
```

Compound assignment is not an operator but a notational shorthand: `a += b` means
`a = a + b`. The shorthand has two benefits — the variable name is written once
(lowering the chance of assigning to the wrong name), and the reader sees at a
glance that the update is on the same variable.

This equivalence thins out for mutable types: in some languages, compound
assignment updates the existing object in place instead of producing a new one. In a
shared list this difference produces observable consequences; the distinction is an
extension of the rule established around immutability.

One warning: compound assignment is also a statement, not an expression. It has no
value; it cannot be placed inside another expression.

#### Same Operator, Different Meaning

An operator's meaning depends on the types it is applied to:

```python
print(3 + 4)              # 7        — numeric addition
print("3" + "4")          # 34       — string concatenation
print([1, 2] + [3])       # [1, 2, 3] — list concatenation
print("ab" * 3)           # ababab   — repetition
```

The same symbol performing a different operation across different types is called
**operator overloading**. It provides convenience; in exchange, code that assumes
the wrong type can silently produce an unexpected result. A `+` operation performed
without knowing whether a value taken from the user is a number or a string is the
typical example of this.

This connects directly to the next lesson's subject: what happens when a value's
type differs from what is expected?

#### Summary

- Among the arithmetic operators, integer division and remainder are used
  frequently in numeric problems.
- Comparison operators produce a boolean value; `==` tests content equality and is
  not assignment.
- `and`, `or`, and `not` combine conditions; their truth tables are identical to
  their bit-level counterparts.
- In short-circuit evaluation the right side does not run once the result is
  determined; the order of conditions affects correctness.
- Precedence determines which operator is applied first, associativity determines
  how operators of the same precedence group; exponentiation associates right to
  left.
- The same operator can carry different meanings across different types.

#### Next Step

What happens when different types meet in an expression? Can a string be added to a
number, how is a real number converted to an integer, and what is lost in these
conversions? The next lesson takes up type conversion and the consequences of a
lossy conversion.

### Type Conversion

Source: https://academia.sh/en/courses/programming-fundamentals/type-conversion

Explicit and implicit conversion, lossy narrowing, conversion errors, and input validation.

The previous lesson showed that the same operator carries a different meaning
across different types. One question remains: what happens when different types
meet side by side in an expression?

The answer is one of three options: the language performs the conversion on its
own, it waits for the programmer to request it explicitly, or it rejects the
operation. This lesson's subject is these three behaviors and the cost of
conversions.

#### Explicit Conversion

In **explicit conversion**, the programmer requests the conversion by naming the
target type:

```python
print(int("12") + 1)          # 13     — string to integer
print(float("3.5") * 2)       # 7.0    — string to real number
print(str(12) + "1")          # 121    — integer to string
print(int(3.9))               # 3      — real number to integer
```

The advantage of explicit conversion is that it is visible: whoever reads the code
knows a conversion is happening here, and in which direction.

The fourth line calls for attention. Converting from a real number to an integer
does **not round, it truncates**: the fractional part is discarded.

```python
print(int(3.9), int(-3.9))    # 3 -3   — truncation toward zero
print(round(3.9))             # 4      — rounding is a separate operation
print(round(2.5), round(3.5)) # 2 4    — halves round to the nearest even number
```

The last line is a detail worth knowing in numeric code: half values always
rounding up is not universal. A common rule is rounding halves to the nearest even
number; this prevents a large number of roundings from drifting upward in total.

#### Implicit Conversion

In **implicit conversion**, the language performs the conversion on its own to make
the types compatible:

```python
print(3 + 2.5)                # 5.5    — the integer was promoted to a real number
print(type(3 + 2.5))          # <class 'float'>
```

The conversion here is **widening**: an integer can be represented within the set of
real numbers. Implicit conversions in the widening direction are generally safe.

Languages diverge in how much implicit conversion they allow. Some languages allow
only safe widenings; others convert almost any type into any other. In the second
group, an expression such as `"3" + 4` raises no error and silently produces a
result — and what that result is varies by language. The convenience comes at the
cost of the error going silent.

Python sits close to the first of these two extremes: it promotes between numbers,
but refuses to add a string to a number and raises an error.

#### Lossy Conversion

Some conversions lose information. Three typical cases:

**Loss of fraction.** Going from a real number to an integer discards the
fractional part; converting back does not give the old value.

**Range overflow.** A wide integer may not fit into a narrow type. In fixed-width
languages the result wraps; the previous course's lesson on overflow showed why
this happens silently.

**Loss of precision.** Large integers can exceed the mantissa width of real-number
representation:

```python
big = 10 ** 23
print(float(big) == big)      # False
print(int(float(big)))          # 99999999999999991611392
```

The value has silently changed; there is no error message. The bound stated in the
lesson on floating-point numbers becomes observable here.

Practical rule: conversions in the narrowing direction are written explicitly and
their justification is known. In languages that allow implicit narrowing, compiler
warnings are kept enabled.

#### Conversion Errors

Conversion is not always possible. If a string does not represent a number, the
conversion raises an error:

```python
# int("three")   -> runtime error: invalid number representation
# int("3.5")     -> runtime error: not an integer representation
print(int(float("3.5")))          # 3  — in two steps: real first, then truncation
```

This is the rule when working with data coming from the outside world: user input,
file contents, and network responses are **not converted without being validated**.
There are two common patterns.

The first is to attempt the conversion and catch the error:

```python
def to_number(text: str, default: int = 0) -> int:
    """Converts text to an integer; returns the default if conversion fails."""
    try:
        return int(text)
    except ValueError:
        return default

print(to_number("12"))         # 12
print(to_number("three"))         # 0
print(to_number("three", -1))     # -1
```

The second is to test the format before converting:

```python
text = "12"
if text.isdigit():
    measurement = int(text)
    print(measurement + 1)              # 13
```

Which of the two patterns is chosen depends on whether the error is an expected
case or an exceptional one. An invalid value in user input is an expected case; a
program's own generated data being invalid is exceptional.

#### From Input to Number: A Complete Example

The fact that external input arrives as a string and must be converted for numeric
processing brings together every part of this topic. Through the course's shared
problem:

```python
# Input: text with one measurement per line (imagine it was read from a file)
raw_lines = ["12", "18", "7", "twenty", "25", ""]

measurements = []
skipped = 0

for line in raw_lines:
    text = line.strip()                # discard leading and trailing whitespace
    try:
        measurements.append(int(text)) # convert to a number and add if valid
    except ValueError:
        skipped += 1                   # otherwise count and move on

print(measurements)                        # [12, 18, 7, 25]
print(skipped)                             # 2
print(sum(measurements) / len(measurements))   # 15.5
print(max(measurements))                   # 25
```

The program contains three separate decisions, and all three rest on the concepts
established in this topic: the input is cleaned (string processing), converted
(explicit conversion), and invalid values are counted separately (error handling).

There is also a fourth decision, and it is easy to overlook: should invalid lines
be skipped, should the program stop, or should they be filled with a default value?
This is a question of the problem, not of the language. How missing values are
handled in measurement data is a separate topic in the data analytics curriculum.

How the `for` loop works is the subject of the next topic; here it is enough to
read it only as far as each line being processed in sequence.

#### A Silent Trap: Strings That Look Like Numbers

A value that looks numeric staying as a string leads to a situation that raises no
error but gives the wrong result:

```python
print("12" < "9")             # True   — string comparison: character by character
print(12 < 9)                 # False  — numeric comparison
print(sorted(["12", "9", "100"]))    # ['100', '12', '9']
print(sorted([12, 9, 100]))          # [9, 12, 100]
```

A second example of the same class is that number notation varies by region. The
decimal separator is a period in some notations and a comma in others; the
thousands separator varies similarly. A language's standard conversion function
usually accepts only one notation; if text coming from a user or an external source
does not conform to that notation, the conversion fails, or — worse — reads only
part of the number. For this reason, the notation external data arrives in must be
known, and the conversion must be performed according to that notation.

Strings are compared character by character; the character `"1"` comes before the
character `"9"`. If measurements read from a file are sorted without being
converted, the result is lexicographic order, not numeric order. This is a typical
example of the logic-error class from the first lesson: the program runs, raises no
error, and gives the wrong result.

#### Summary

- In explicit conversion the target type is stated by the programmer; the language
  performs implicit conversion on its own.
- Converting a real number to an integer does not round, it truncates; rounding is
  a separate operation, and the rule for half values can vary between languages.
- Conversions in the widening direction are safe; those in the narrowing direction
  can lose fraction, range, or precision, and this loss is silent.
- Converting a string to a number can fail; external input is not converted
  without being validated.
- Strings that look like numbers are compared character by character, and this
  changes the result of sorting.

#### Next Step

This topic has completed values and building expressions from them. Programs do
not only flow from top to bottom, however: they branch on a condition and repeat.
The next topic takes up the structures that direct flow — conditional branching and
loops.

## Control Flow

Conditional branching, loops, and designing a solution with pseudocode.

### Conditional Branching

Source: https://academia.sh/en/courses/programming-fundamentals/conditional-branching

Condition-dependent execution, multi-way selection, writing readable conditions, and mapping-based dispatch.

The programs written so far have followed a single path from start to end: each
statement executed once, in its turn. Most problems, however, require different
behavior depending on the situation. If a measurement is above a limit, a warning
should be given; if it is below, nothing should happen.

This lesson covers how flow splits based on a condition. The previous course showed
its hardware counterpart: a comparison instruction sets flags, and a conditional
branch instruction changes the program counter only if the condition holds. Every
construct here ultimately reduces to those instructions.

#### One-Way and Two-Way Selection

The simplest form is a block that executes only when a condition holds:

```python
measurement = 25
LIMIT = 20

if measurement > LIMIT:
    print("limit exceeded")      # limit exceeded
```

A condition is any expression that produces a logical value. If it does not hold, the
block is skipped and flow continues below it.

In two-way selection, a block to run when the condition does not hold is also defined:

```python
if measurement > LIMIT:
    status = "high"
else:
    status = "normal"

print(status)                    # high
```

Which statements a block covers is shown differently by language: some use curly
braces, some close the block with a keyword, Python uses indentation. The notation
varies; the meaning is the same — the set of statements to execute depending on the
condition is marked off.

In languages that use indentation, one warning applies: indentation is not mere
formatting but meaning. A statement believed to be inside the block but whose
indentation has shifted always runs regardless of the condition. This is a common
instance of the logic error class defined in the first lesson.

#### Multi-Way Selection

When there are more than two cases, conditions are chained. In the chain, **the first
condition that holds wins**; the rest are never tested.

```python
def classify(measurement: int) -> str:
    if measurement < 10:
        return "low"
    elif measurement < 20:
        return "medium"
    elif measurement < 30:
        return "high"
    else:
        return "extreme"

print(classify(7), classify(12), classify(25), classify(40))
# low medium high extreme
```

The order of the chain determines the meaning of the conditions. The second branch's
condition `measurement < 20`, read on its own, is also true for the value $5$; but by
the time it is reached, the first condition is known not to hold, meaning
`measurement` is at least $10$. Every branch implicitly carries the negation of all
the ones before it.

This is why reordering breaks the program. The following chain produces "extreme" for
**every** value of `10` or more — including `12`, where "moderate" is expected — because
its first condition stands at the front and never leaves the narrower one a turn:

```python
def classify_wrong(measurement: int) -> str:
    if measurement >= 10:        # broad condition placed first
        return "extreme"
    elif measurement < 20:
        return "medium"
    else:
        return "low"

print(classify_wrong(12))        # extreme  — expected "medium"
print(classify_wrong(25))        # extreme  — correct for this value
```

The practical rule: conditions are ordered from the narrowest case to the broadest;
the most general case is collected in the `else` branch. If the chain has no `else`
branch at the end, input that satisfies no condition passes through silently, doing
nothing — this is where overlooked cases typically hide. The last branch of every
chain should state explicitly what happens for unexpected input.

#### Writing Readable Conditions

As a condition grows more complex, code readability drops quickly. Three habits
prevent this.

**Using the logical value directly.** Writing `if condition == True` is unnecessary;
`condition` is already a logical value. Adding the comparison lengthens the expression
and risks accidentally turning into an assignment.

**Naming the condition.** A long condition is bound to a variable that states its
meaning:

```python
measurement, temperature = 25, 80

# Hard to read:
if measurement > 20 and temperature > 75 and not (measurement > 40):
    print("warning")

# Named:
limit_exceeded = measurement > 20
too_hot = temperature > 75
within_safe_range = measurement <= 40

if limit_exceeded and too_hot and within_safe_range:
    print("warning")             # warning
```

**Simplifying negation.** Nested negations are flattened using De Morgan's laws: the
expression `not (a and b)` is equivalent to `(not a) or (not b)`. Which of the two
forms to choose is decided by which one states the problem more directly.

#### The Conditional Expression

Conditional branching is a statement: it performs an action, it does not produce a
value. Many languages, by contrast, also offer a form that **produces a value**
depending on a condition. The difference between the two forms is a direct
application of the statement–expression distinction from the first lesson.

```python
measurement = 25

# Statement form: the status variable is bound separately in each branch.
if measurement > 20:
    status = "high"
else:
    status = "normal"

# Expression form: a single binding, the condition selects the value.
status = "high" if measurement > 20 else "normal"
print(status)                    # high
```

The expression form improves readability in short cases where a value is bound to one
of two options: the variable is written once, and the binding is visibly in a single
place.

It also has a limit. If the branches are long, nested, or contain side effects, the
expression form becomes unreadable. The criterion is this: if the condition selects a
**value**, use the expression form; if it selects an **action**, use the statement
form.

#### Nested Conditions

Conditions can be nested inside one another. As depth grows, reading gets harder; each
level adds an assumption the reader must keep in mind.

Condition stacks more than three levels deep are usually a sign that two separate
problems are being solved in the same place. The standard way to reduce depth is to
rule out invalid cases first and exit early. This pattern is revisited under the name
**guard clause** in the functions topic; its counterpart here is turning nested
branches into a flat chain.

#### Mapping-Based Dispatch

If a condition chain is nothing but a single value compared against constants, many
languages offer a dedicated construct for it — switch-based selection or pattern
matching. The construct's name and capabilities vary by language.

An approach that offers an alternative to the chain is moving the selection into data:

```python
UNIT_FACTOR = {"mm": 0.001, "cm": 0.01, "m": 1.0}

def to_meters(value: float, unit: str) -> float:
    if unit not in UNIT_FACTOR:
        raise ValueError(f"unknown unit: {unit}")
    return value * UNIT_FACTOR[unit]

print(to_meters(25, "cm"))       # 0.25
print(to_meters(1500, "mm"))     # 1.5
```

This form's advantage is that adding a new unit is a data change, not a code change. A
condition chain grows longer with every new case; a mapping table stays the same.
This difference becomes more pronounced as the number of decisions grows; in the
software design curriculum, the same idea is expanded under the heading of replacing
conditionals with polymorphism.

The selection criterion is this: if the cases are fixed and few, a condition chain is
clear; if the cases grow or change at run time, a mapping is preferred.

#### Summary

- Conditional branching executes a block of code only when a condition holds; a
  condition is an expression that produces a logical value.
- Block boundaries are shown differently by language; in languages that use
  indentation, indentation is part of the meaning.
- In multi-way selection, the first condition that holds wins; every branch implicitly
  carries the negation of the ones before it, and reordering breaks the program.
- Conditions are made readable by naming them and simplifying negations; a logical
  value is not compared with `== True`.
- When a single value is compared against constants, a mapping table can replace a
  growing condition chain.

#### Next Step

Branching determines which path flow takes, but it executes each path only once. The
measurement sequence in the shared problem, however, requires the same work for every
element. The next lesson covers loops, which execute the same block repeatedly, and
the guarantee that a loop terminates.

### Loops

Source: https://academia.sh/en/courses/programming-fundamentals/loops

Iterating over a collection, counted and conditional loops, the termination guarantee, and the accumulator pattern.

The course's shared problem was finding the average and the maximum of a sequence of
measurements. Until now, this has been done with built-in functions. This lesson
defines the structure that does the same work step by step: the **loop**.

A loop makes a block of code execute more than once. How many times it executes is
either known in advance or depends on a condition; this distinction determines the
types of loops.

#### Iterating Over a Collection

The most commonly used form is advancing through a collection's elements in order:

```python
measurements = [12, 18, 7, 25, 14]

for measurement in measurements:
    print(measurement)
# 12 / 18 / 7 / 25 / 14   (each on its own line)
```

The loop variable (`measurement`) is bound to the next element on every iteration. As
many iterations run as there are elements; there is no need to keep a counter, query
the length, or check a bound.

This form's advantage is that it makes off-by-one errors impossible. In loops with a
manually managed counter, the most common error is processing one element too few or
too many; iterating directly over the collection eliminates this class of error.

#### The Counted Loop

Some problems need not the element itself but its **position**: processing the first
three measurements, walking two arrays at once, or repeating a fixed number of times.

```python
for i in range(5):
    print(i, end=" ")
print()                      # 0 1 2 3 4

for i in range(len(measurements)):
    print(f"measurement {i}: {measurements[i]}")
# measurement 0: 12 ... measurement 4: 14
```

Counting starting from zero and leaving the upper bound **excluded** is a common
convention: `range(5)` produces five values, and the last one is $4$. The benefit of
this arrangement is that `range(len(array))` gives exactly the valid indices.

If only the position number is needed, a counted loop is the right tool. If both the
position and the element are needed, most languages offer a construct that provides
both together; looking the element up by index again is unnecessary work.

#### The Conditional Loop

When the number of iterations is not known in advance, a conditional loop is used. The
condition is tested before every iteration; when it no longer holds, the loop ends.

```python
remaining = 100
round_count = 0

while remaining > 1:
    remaining = remaining // 2   # halves on every iteration
    round_count += 1

print(round_count)           # 6
```

This loop finds how many times a number can be halved. The number of iterations is
not known at the start; it depends on the initial value. The same calculation is also
the source of the cost in the binary search example from the previous course.

One variant of the conditional loop tests the condition at the **end** of the
iteration, so the body runs at least once. The pattern of asking the user until a
valid value is obtained requires this form.

#### The Termination Guarantee

Nothing guarantees that a loop will stop; the person writing the program must ensure
it. The rule is: **on every iteration, there must be a change that moves toward
making the condition false.**

In the example above, `remaining` shrinks on every iteration and heads toward zero;
values between zero and one make the condition false. This decreasing quantity is the
loop's justification for termination.

If no such justification can be established, the loop can run forever:

```python
remaining = 100
while remaining > 1:
    remaining = remaining // 2
    if remaining == 3:
        remaining = 100      # jump backward: the decrease guarantee is broken
```

This loop never ends. The program stays running, keeps the processor busy, and does
not terminate unless stopped from outside. Because an infinite loop produces no
runtime error, it falls into the logic error class defined in the first lesson.

Deliberate infinite loops also exist: a server, while waiting for requests, does not
intentionally stop. In that case, exit comes not from the loop condition but from the
break statements covered in the next lesson, or from an external signal.

#### The Accumulator Pattern

The most common use of loops is accumulating a value across iterations. The pattern
consists of three steps: initialize the accumulator, update it on every iteration,
use it after the loop.

```python
measurements = [12, 18, 7, 25, 14]

total = 0                        # 1. initial value
for measurement in measurements:
    total += measurement         # 2. update on every iteration

average = total / len(measurements)   # 3. use the result
print(total, average)            # 76 15.2
```

The choice of initial value is the operation's **identity element**: zero for
addition, one for multiplication. An incorrectly chosen initial value silently
produces a wrong result.

Finding the maximum value follows the same pattern, but the initial value requires
more care:

```python
largest = measurements[0]        # the first element is taken as the starting point
for measurement in measurements:
    if measurement > largest:
        largest = measurement

print(largest)                   # 25
```

Starting from zero here would be wrong: if all the measurements were negative, the
result would incorrectly come out as zero. The correct starting point is the array's
first element — and this assumes the array is **not empty**. An empty input is the
standard edge case for this kind of code and must be handled before the loop.

The course's shared problem has thus been solved without built-in functions: two
loops, two accumulators.

#### The Loop Invariant

Termination is only one of two questions about a loop; the second is correctness —
why is the result correct once it ends?

The answer is given by the concept of the **loop invariant**: a statement that
remains true at the start and end of every iteration. The invariant of the
accumulator loop is this — *`total` is the sum of the elements visited so far.*

The invariant is tested in three places. It is true before entering the loop (no
element has been visited, the total is zero). Every iteration preserves it (one
element is visited, that same element is added to the total). Once the loop ends,
every element has been visited; the invariant then states that `total` is the sum of
all the elements. That is the desired result.

These three steps prove the loop's correctness without tracing individual iterations.
The invariant of the loop that finds the
maximum is written the same way: *`largest` is the maximum of the elements visited so
far.* Writing this statement also explains why the initial value must be the first
element — if it started at zero, the invariant would already be false before entering
the loop.

The habit of writing invariants is the foundation of correctness proofs for
algorithms, and it is formalized in the **Algorithms** course.

#### Nested Loops

A loop's body can contain another loop. Every iteration of the outer loop runs the
inner loop in full; the total number of iterations is the product of the two.

```python
for i in range(3):
    for j in range(2):
        print(i, j, end="  ")
print()
# 0 0  0 1  1 0  1 1  2 0  2 1
```

Multiplicative growth is the main cost of nested loops: every new level multiplies
the amount of work. This observation is the starting point of the concept of
algorithmic complexity and is formalized in the **Algorithms** course. The intuition
sufficient for this course is this: as data grows, the cost of nested loops grows far
faster than that of single-level loops.

#### Summary

- Iterating over a collection processes elements in order and eliminates off-by-one
  errors.
- A counted loop is used when the element's position, not the element itself, is
  needed (counting starts at zero, the upper bound is excluded); a conditional loop is
  used when the number of iterations is not known in advance.
- A loop's termination is guaranteed by a change on every iteration that moves toward
  making the condition false; without such a change, the loop runs forever.
- The accumulator pattern has three steps: initialize, update on every iteration, use
  afterward; the initial value is the operation's identity element, and it is the
  first element when searching for a maximum.
- The loop invariant is a statement that stays true on every iteration, and it
  justifies a loop's correctness without tracing individual iterations.
- In nested loops, the total number of iterations grows multiplicatively.

#### Next Step

Loops flow from start to end, but sometimes a decision must be made partway through
an iteration: exiting early once the target is found, or skipping an invalid element
and continuing. The next lesson covers the statements that redirect loop flow from
the inside, and their effect on readability.

### Loop Control

Source: https://academia.sh/en/courses/programming-fundamentals/loop-control

Break, continue, the search pattern, and readability when exiting nested loops.

The previous lesson introduced loops as structures that flow from start to end: the
condition is tested, the body runs, it repeats. Some problems require breaking this
pattern. Once the value being searched for is found, looking at the remaining
elements is unnecessary; an invalid element should be skipped without being
processed.

This lesson covers the statements that redirect loop flow from the inside, and their
effect on readability.

#### Break

The break statement ends a loop without waiting for its condition. Flow continues
immediately below the loop.

```python
measurements = [12, 18, 7, 25, 14]
LIMIT = 20

for measurement in measurements:
    if measurement > LIMIT:
        print("first measurement exceeding the limit:", measurement)   # 25
        break
```

The justification for break is not only speed. Written without `break`, this loop
would find the **last** measurement exceeding the limit; when what is sought is the
first one, exiting is part of the meaning.

Infinite loops also get their exit from here: the condition is written as always
true, and the decision to exit is made at some point inside the body. This form is
preferred when the exit condition is computed partway through the iteration.

#### Continue

The second statement ends the current iteration early and moves to the next one. The
loop does not terminate.

```python
raw = [12, -1, 18, -1, 25]

total = 0
counted = 0
for measurement in raw:
    if measurement < 0:      # marker for an invalid measurement
        continue
    total += measurement
    counted += 1

print(total, counted)        # 55 3
```

The same work can also be written by wrapping the body in a condition block. The
choice between the two forms is made by looking at indentation depth: the continue
statement rules out invalid cases first and keeps the rest of the body flat. If the
body is long, this is a clear gain.

#### The Search Pattern and the Not-Found Case

The most common use of break is search. Search's hidden question is always the same:
**what happens if what is sought is not found?**

```python
def find_first_exceeding(measurements: list[int], limit: int) -> int | None:
    """Returns the first measurement exceeding the limit; returns None if there is none."""
    for measurement in measurements:
        if measurement > limit:
            return measurement
    return None               # loop ended without exiting: not found

print(find_first_exceeding([12, 18, 7, 25, 14], 20))    # 25
print(find_first_exceeding([12, 18, 7], 20))            # None
```

The `return None` on the last line handles the case where the loop is exhausted. If
this line were forgotten, the function would silently return an empty value, and the
caller would encounter an unexpected value instead of understanding that the search
failed.

There are three ways to report a not-found case, and the choice depends on what the
caller will do: return a special value, raise an error, or return a "was it found"
flag together with the result. The first option is the most common; but the returned
value must be checked, otherwise the empty-value problem defined in the basic data
types lesson arises.

Some languages offer a separate block that runs when the loop ends without ever
exiting early; it makes it possible to write the same work without a flag variable.
This construct is not universal.

#### The Flag Variable

When break is unavailable or not suitable, carrying the result in a logical variable
is a common pattern:

```python
found = False
for measurement in [12, 18, 7]:
    if measurement > 20:
        found = True
        break

print(found)                 # False
```

The flag reports, once the loop ends, which way it was exited. The pattern is
correct, but its cost is readability: the reader has to track where the flag is set
and where it is read. If the search can be pulled out into a function, returning
directly is usually clearer.

#### Breaking Out of Nested Loops

A break statement ends only **its own loop**. In a two-level search, exiting the
inner loop does not stop the outer one.

```python
matrix = [[1, 2, 3],
          [4, 5, 6],
          [7, 8, 9]]

def find_position(matrix: list[list[int]], target: int) -> tuple[int, int] | None:
    """Returns the target's (row, column) position; None if there is none."""
    for i, row in enumerate(matrix):
        for j, value in enumerate(row):
            if value == target:
                return (i, j)       # exits both loops at once
    return None

print(find_position(matrix, 6))     # (1, 2)
print(find_position(matrix, 99))    # None
```

There are three options. **Pulling the code into a function and using return**, as
above, is the most readable: a single statement exits every level. Using a **flag
variable** requires a separate exit condition at every level and quickly becomes
unreadable as depth grows. Some languages offer a **labeled break**; which loop to
exit is written explicitly.

This is the first example of functions being used not only for reuse but also to
**simplify flow**. The next topic covers this tool in detail.

#### Modifying the Loop Variable

One warning: modifying a counted loop's variable inside the body does not have the
expected effect in many languages, or it breaks the termination guarantee. In the
same way, modifying a collection while it is being iterated over — adding or removing
an element — leads to undefined or surprising behavior.

The safe pattern is to collect changes in a separate collection and apply them after
the loop ends:

```python
measurements = [12, -1, 18, -1, 25]

valid = [measurement for measurement in measurements if measurement >= 0]   # a new list is produced
print(valid)                 # [12, 18, 25]
print(measurements)          # [12, -1, 18, -1, 25]  — the original list is unchanged
```

The notation in the last example is a shorthand form of a loop, and it has a
counterpart in many languages. It reduces filtering and transformation operations to
a single line; when the condition grows complex, an explicit loop stays more
readable.

#### Break and Lazy Iteration

The gain from break is proportional to the number of elements not processed. If the
collection is already sitting in memory, the gain is only time. But if elements are
**produced on demand**, break also eliminates the cost of the elements never
produced.

This mode of production is called **lazy iteration**: values are not precomputed and
collected in a list; they are computed on demand, one iteration at a time.

```python
def measurement_source():
    """Produces values on demand; not all of them are held in memory at once."""
    for base in range(1, 1_000_000):
        yield base * 3

for value in measurement_source():
    if value > 20:
        print("first exceeding:", value)   # first exceeding: 21
        break
```

The loop exits on the seventh iteration; the remaining values are never computed. The
same work could also be done by first building a list of a million elements and then
searching it — the result is the same, the cost is not comparable.

The distinction is decisive for large data sources: the difference between reading an
entire file into memory and processing it line by line is an application of the same
idea.

#### Summary

- Break ends a loop without waiting for its condition; it is part of the meaning in
  problems that search for the first match.
- The continue statement ends only the current iteration, and ruling out invalid
  cases first reduces indentation depth.
- In the search pattern, the not-found case is handled explicitly; the special value
  returned must be checked by the caller.
- A flag variable is an alternative to break, but it adds tracking overhead for the
  reader.
- Break ends only its own loop; in nested loops, the most readable solution is to
  pull the search out into a function and use return.
- Modifying a collection while it is being iterated over is not safe.

#### Next Step

Up to this point, control structures were written directly as code. For a complex
problem, the solution itself is designed first, then translated into code. The next
lesson covers writing a solution independent of any language — pseudocode — and how a
solution is tested before it is turned into code.

### Pseudocode

Source: https://academia.sh/en/courses/programming-fundamentals/pseudocode

Writing a solution independent of any language, testing it with a manual trace table, and identifying edge cases.

The previous three lessons introduced control structures directly through code. For a
complex problem, the order reverses: the solution is designed first, then translated
into code. Designing directly in a language's syntax requires thinking about two
different problems — "what to do" and "how to write it" — at the same time.

This lesson defines the ways to write a solution independent of any language, and to
test it before putting it into code.

#### What Pseudocode Is

**Pseudocode** is a way of writing a solution close to natural language, but with
enough precision that its steps leave no ambiguity. It is not compiled, it is not
run; it is read.

It has no strict syntax, but common conventions exist:

- An arrow, or the phrase "let ... be", is used for assignment.
- Blocks are shown with indentation.
- Loops and conditions are written out plainly: *for each measurement*, *if ... then*.
- Language-specific details — library names, type declarations, memory management —
  are left out.

The measure is this: two people reading the pseudocode must understand the same
behavior — this text, written before any code, is where the solution is discussed. If
ambiguity remains, it is not detailed enough; if it approaches a language's syntax, it
is more detailed than it needs to be.

#### Analyzing the Problem

The problem must be understood before writing pseudocode. Four questions do this
work:

1. **What is the input?** Its type, range, and validity conditions.
2. **What is the output?** A single value, a collection, or a side effect.
3. **Which cases are special?** Empty input, single-element input, equal values,
   invalid values.
4. **How would I solve it by hand?** Putting the steps into words over a small
   example reveals the solution itself.

The fourth question is the most productive. Someone computing the average of five
measurements by hand uses an accumulator pattern without realizing it: the numbers
are summed in order, then divided by five.

#### The Shared Problem in Pseudocode

The course's shared problem — the average and the maximum — is written in pseudocode
like this:

```
INPUT: measurements (list of numbers)
OUTPUT: average (number), largest (number)

if measurements is empty
    report error: "empty input"

total ← 0
largest ← measurements[0]

for each measurement in measurements
    total ← total + measurement
    if measurement > largest
        largest ← measurement

average ← total / number of measurements
return average and largest
```

This text contains no detail belonging to any language; yet every step is single and
leaves no room for debate. Notice that the empty-input check is done **before** the
loop: initializing the `largest` variable with the first element assumes the list is
not empty.

The same pseudocode uses two accumulators in a single loop instead of two loops. This
is a design decision: the data is walked once, and two results are produced together.

#### Tracing by Hand

A solution's correctness can be tested before it is translated into code, using a
**trace table**. In the table, each row shows an iteration, each column a variable.

For the input `[12, 18, 7]`:

| Iteration | measurement | total | largest |
|---|---|---|---|
| start | — | 0 | 12 |
| 1 | 12 | 12 | 12 |
| 2 | 18 | 30 | 18 |
| 3 | 7 | 37 | 18 |
| result | — | 37 | 18 |

The average is $37 / 3 \approx 12.33$; the largest is $18$. The results match the
hand calculation.

A trace table catches two kinds of errors: a wrong initial value and a wrong update
order. For example, if `largest` were initialized to zero, the table would
immediately show the result coming out as zero for an input where all measurements
are negative.

The method is slow and cannot be applied to large inputs; that is not its purpose
either. An input of three or four elements is enough to expose most logic errors. The
same table can also be built on a running program during debugging: printing the
values of variables on every iteration is having the program itself produce the
trace table.

#### Edge Cases

A solution working on ordinary input is not enough. Edge cases are where a solution's
assumptions break down:

| Edge case | Behavior in this problem |
|---|---|
| Empty list | Average is undefined; an error is reported |
| Single element | Average is that element, largest is that element |
| All values equal | Largest is that value |
| All values negative | Largest is the least negative one |
| Very large values | The total can exceed the type's range |

The last row connects to the previous course's overflow lesson: a total accumulating
in a fixed-width type produces a silently wrong result if it goes out of range.

Listing edge cases is also listing the tests that will be written later. In the
software quality curriculum, this is called boundary value analysis.

#### Decomposing the Problem into Subproblems

The shared problem fit into a single pseudocode block. Real problems do not; a
solution can neither be written nor traced as a single piece.

The standard method is **decomposition**: the problem is broken into subproblems,
each doing a single job. A program working with measurement data can be decomposed
like this:

```
read(source) → raw lines
extract(raw lines) → valid measurements, skipped count
summarize(measurements) → average, largest
report(average, largest, skipped) → output text
```

Each of the four steps can be written separately, tested separately, and when one
changes, the others are unaffected. The criterion for splitting is whether a step can
be described in a single sentence: a step doing two jobs joined by "and" should
probably be split in two.

The counterpart of this decomposition in code is functions. Naming a step in
pseudocode corresponds to defining a function in code; decomposition is therefore a
design task done before any code is written.

#### From Pseudocode to Code

Translation means writing the target language's counterpart of every line of
pseudocode:

```python
def summarize(measurements: list[int]) -> tuple[float, int]:
    """Returns the average and the largest of the measurements."""
    if not measurements:
        raise ValueError("empty input")

    total = 0
    largest = measurements[0]

    for measurement in measurements:
        total += measurement
        if measurement > largest:
            largest = measurement

    return total / len(measurements), largest


print(summarize([12, 18, 7]))          # (12.333333333333334, 18)
print(summarize([12, 18, 7, 25, 14]))  # (15.2, 25)
```

The first output matches the values computed by hand in the trace table — this is
proof that the translation was done correctly.

During translation, decisions that were not in the pseudocode appear: how to report
an error, how to return two values together, what the types will be. These decisions
belong to the language and are not a deficiency of the pseudocode; they are details
the pseudocode **deliberately leaves out**.

#### Summary

- Pseudocode is a way of writing a solution independent of any language and without
  leaving ambiguity; its measure is that two readers understand the same behavior.
- Problem analysis is done with four questions: input, output, special cases, and the
  by-hand solution.
- A trace table tests a solution without running it; a wrong initial value and a
  wrong update order are caught this way.
- The list of edge cases is also the list of tests to be written later.
- The decisions that appear during translation from pseudocode to code belong to the
  language; pseudocode deliberately leaves these details out.

#### Next Step

The solution in the last example was wrapped in a `def` block and named
`summarize`. This construct has been used without explanation up to now. The next
topic defines functions: how parameters and return values work, in what region names
are valid, and what happens when a function calls itself.

## Functions and Abstraction

Function definition, argument passing, scope rules, and recursion.

### Function Definition and Call

Source: https://academia.sh/en/courses/programming-fundamentals/function-definition-and-call

Parameter and argument, return value, the call stack, the guard clause, and the criteria of a good function.

The last lesson of the previous topic established that breaking a problem into
subproblems is part of solution design, and that functions are its code counterpart.
This lesson defines that counterpart.

A function encloses a piece of work in a named, reusable unit — a two-way contract: the
caller knows what to provide, the function knows what to return.

#### Definition and Call

A function definition specifies three things: its name, the values it accepts, and its
body.

```python
def average(measurements: list[int]) -> float:
    """Returns the arithmetic mean of the measurements."""
    return sum(measurements) / len(measurements)


print(average([12, 18, 7]))        # 12.333333333333334
print(average([10, 20]))           # 15.0
```

The `measurements` in the definition is a **parameter**: a name in the body that
receives a value at the call. The `[12, 18, 7]` in the call is an **argument**: the
value bound to it. The two terms are often confused; the distinction is between what is
expected and what is given.

The definition itself is not executed; it only defines the function. The body runs only
when the function is called, so an error inside it may not surface until then.

#### Return Value

The `return` statement does two things: it ends the function and produces a value. The
value takes the place of the call; because of this, a call is an **expression** and can
be placed inside other expressions.

A function can return more than one value, usually by collecting them into a single
compound value:

```python
def summarize(measurements: list[int]) -> tuple[float, int]:
    """Returns the mean and the largest value together."""
    largest = measurements[0]
    for measurement in measurements:
        if measurement > largest:
            largest = measurement
    return average(measurements), largest


mean, largest_value = summarize([12, 18, 7, 25, 14])
print(mean, largest_value)          # 15.2 25
```

There are also functions that return no value, called to perform an action such as
printing to the screen or saving to a file. This distinction is **command–query
separation** in the software design curriculum: a function changes state or returns a
value, not both.

#### Default and Keyword Arguments

Parameters can be given a default value; if the call does not specify one, the default
is used.

```python
def over_limit(measurements: list[int], limit: int = 20) -> list[int]:
    """Returns the measurements that exceed the limit."""
    return [measurement for measurement in measurements if measurement > limit]


print(over_limit([12, 18, 7, 25, 14]))            # [25]
print(over_limit([12, 18, 7, 25, 14], 10))        # [12, 18, 25, 14]
print(over_limit([12, 18, 7, 25, 14], limit=15))  # [18, 25]
```

The syntax in the last line supplies the argument by name. This has two benefits: an
ordering mistake becomes impossible, and the value's meaning is visible in the call — a
noticeable gain in readability for calls passing numbers or boolean values.

One warning: a mutable default value leads to surprising behavior in many languages,
since the default is created once and shared across calls. Choosing immutable defaults
avoids this trap.

#### The Call Stack

The last lesson of the previous course established that every call pushes a frame onto
the stack. This lesson covers the side of that mechanism visible to the programmer.

When a call is made, control passes to the body; the return address, arguments, and
local variables are held in the frame. When `return` executes, the frame is released
and control resumes at the call site.

When calls nest, frames stack on top of one another. When `summarize` calls `average`,
the second frame is pushed atop the first; when `average` returns, only its own frame
is released.

The practical counterpart of this stack is the trace accompanying error messages: which
function called which, from outermost to innermost. This is the first thing to read
while debugging; the error's line sits at the bottom, how execution arrived there
above it.

#### Preconditions and the Guard Clause

The conditions a function's input must satisfy to work correctly are called
**preconditions**. The precondition of `average` is that the list must not be empty;
on an empty list, the division becomes division by zero.

Preconditions are handled at the **start** of the function. This style is called a
**guard clause**:

```python
def average(measurements: list[int]) -> float:
    """Returns the mean of the measurements. The list must not be empty."""
    if not measurements:                          # guard clause
        raise ValueError("measurement list is empty")
    return sum(measurements) / len(measurements)
```

The guard clause eliminates the invalid case immediately, leaving the main work
unindented. Wrapping the entire body in an `else` block gives the same result with
different readability. This is the simplification promised in the conditional
branching lesson.

The second decision is what to do with invalid input: raise an error, return a special
value, or produce a default result. The choice depends on the caller's needs; what
matters is documenting the contract and applying it consistently.

#### Writing the Contract

A function's contract lives in its signature and its documentation. The description at
the start of the body contains everything the caller needs to know:

- **What it does** — one sentence, with an action verb.
- **Parameters** — their meaning, units, and valid ranges.
- **Return value** — what it represents.
- **Error conditions** — which error is produced under which condition.
- **Side effects** — if any, stated explicitly.

```python
def over_limit(measurements: list[int], limit: int = 20) -> list[int]:
    """Returns the measurements that exceed the limit, in a new list.

    measurements: the measurement values; not modified.
    limit: the comparison threshold; defaults to 20.
    returns: the measurements greater than the limit, in their original order.
    """
    return [measurement for measurement in measurements if measurement > limit]
```

The scope of the documentation is proportional to visibility: a helper used only within
its own module can settle for a single line; an interface exposed outward deserves the
full contract.

Every assumption left out of the documentation becomes a detail the caller must guess
at. Whether the function modifies the list is a typical example, and the subject of the
next lesson.

#### A Good Function

The technical definition of a function is simple; the criteria for a good function,
however, have formed through experience:

- **It does one thing.** If its name is built with "and" (`compute_and_print`), it
  should probably be split in two.
- **Its name states what it does.** A reader of the call should know what will happen
  without reading the body.
- **It is short.** The length rule is not strict; the criterion is a body readable on a
  single screen, in a single breath.
- **It takes few parameters.** As parameter count grows, the probability of writing the
  call correctly falls.
- **It has no surprises.** It produces no side effect that its name does not state.

All of these criteria, with their justifications, are treated in the **Software Design
and Architectural Principles** curriculum. What suffices here is knowing they exist and
asking them while writing a function.

#### Summary

- A function encloses a piece of work in a named, reusable unit; the parameter states
  the expected name, the argument the given value.
- `return` ends the function and produces a value; a call is an expression usable
  inside other expressions.
- Default and keyword arguments shorten the call and make it readable; mutable default
  values are a trap.
- Every call pushes a frame onto the stack; the trace in an error message is a view of
  that stack.
- Preconditions are handled at the start of the function with guard clauses; what to do
  with invalid input is part of the contract.

#### Next Step

When a list is given to a function, is a change made inside the function visible to the
caller? The answer depends on the language and the type of the value, a direct
consequence of the two models introduced in the variables lesson. The next lesson takes
up argument passing.

### Passing by Value and by Reference

Source: https://academia.sh/en/courses/programming-fundamentals/passing-by-value-and-by-reference

Argument-passing models, the visibility of an in-function change from outside, and the discipline of side effects.

When a list is given to a function, is an element added to it inside the function
visible to the caller? The answer is not "it depends"; it depends on **precise rules**,
a direct extension of the two models introduced in the variables lesson.

This lesson defines those rules and distinguishes the three confusing terms.

#### The Three Models

**Pass by value.** A **copy** of the argument is bound to the parameter; no change
inside the function affects the outside. For large data, the copy has a cost.

**Pass by reference.** The parameter is bound to the caller's variable **itself**; if
the function assigns it a new value, the caller's variable changes too.

**Pass by value of object reference.** The parameter is bound by **copying** the
object's address. The function and caller share the same object; assigning a new
object to the parameter changes only the local binding.

The third model is the most common and the most confused. It has two observable
consequences that appear to contradict each other:

```python
def append_in_place(values: list[int]) -> None:
    """Appends an element to the given list: the change is visible from outside."""
    values.append(99)

def rebind(values: list[int]) -> None:
    """Assigns a new list to the parameter: the outside is not affected."""
    values = [0, 0, 0]

measurements = [12, 18]

append_in_place(measurements)
print(measurements)          # [12, 18, 99]  — the object changed

rebind(measurements)
print(measurements)          # [12, 18, 99]  — the binding changed, not the object
```

The difference in one sentence: **modifying the object is visible from outside;
rebinding the name is not.** The function accesses the object the caller's variable
points to, not the variable itself.

#### No Difference for Immutable Types

The distinction established in the types lesson is useful here: the content of an
immutable value cannot be changed, so the first behavior is impossible.

```python
def increment(number: int) -> int:
    number += 1            # only the local binding changed
    return number

value = 10
print(increment(value), value)      # 11 10
```

Numbers, strings, and similar immutable types therefore behave the same way under
every model. The confusion arises only with mutable types.

#### Side Effect

The trace a function leaves in the outside world, apart from its return value, is
called a **side effect**: modifying an argument, updating a global variable, printing
to the screen, writing to a file.

A side effect is not inherently bad; a program must eventually act. The problem is a
side effect being **unexpected** — a function named `average` sorting the list
produces a change the caller did not account for.

It is possible to write the same task under two different contracts:

```python
def sorted_copy(measurements: list[int]) -> list[int]:
    """Returns a NEW sorted list; the input is not changed."""
    return sorted(measurements)

def sort_in_place(measurements: list[int]) -> None:
    """Sorts the given list IN PLACE; returns no value."""
    measurements.sort()

a = [12, 18, 7]
b = sorted_copy(a)
print(a, b)              # [12, 18, 7] [7, 12, 18]

sort_in_place(a)
print(a)                 # [7, 12, 18]
```

Both forms are legitimate. What matters is that the contract is visible in the name and
documentation. Functions that modify in place typically return no value — command–query
separation from the previous lesson applied in practice. A call that both returns a
value and modifies its input mixes the two contracts.

#### Variadic Arguments

For some functions, the number of arguments is unknown in advance. Languages provide a
syntax that collects the remaining arguments into a single collection:

```python
def largest(*values: int) -> int:
    """Returns the largest of the given values. At least one value is required."""
    if not values:
        raise ValueError("at least one value is required")
    largest_value = values[0]
    for value in values:
        if value > largest_value:
            largest_value = value
    return largest_value

print(largest(12, 18, 7))          # 18
print(largest(*[12, 18, 7, 25]))   # 25  — the list was unpacked into separate arguments
```

The asterisk in the second call **unpacks** a collection into separate arguments. The
same symbol collects arguments in a definition and distributes them in a call — the two
uses are reverse of each other.

The cost of this flexibility is a less precise contract: argument count cannot be read
from the signature. If the arguments have different meanings — one a limit, another a
list of measurements — separate parameters are always clearer. Variadic arguments suit
only values of the **same type and equivalent role**.

#### Defensive Copy

If a function stores data it receives, and the caller modifying it later would cause a
problem, the function must make a copy. This is called a **defensive copy**.

```python
class MeasurementRecord:
    def __init__(self, measurements: list[int]) -> None:
        self.measurements = list(measurements)     # defensive copy

outside_list = [12, 18]
record = MeasurementRecord(outside_list)
outside_list.append(99)                      # the outside list changed

print(record.measurements)                   # [12, 18]  — the record was not affected
```

Without the copy, the record's content could be silently changed from outside. The
`class` structure here is only an example in this course; it is introduced properly in
the paradigms topic.

The cost of the copy is memory and time. The shallow–deep copy distinction from the
variables lesson applies here too: copying only the outer shell of nested structures
does not fully break the sharing.

The same problem exists in the opposite direction: a function returning its stored
collection directly leaks internal state. The caller can modify the returned collection
and update the object's internals without going through its rules. This is the
return-side counterpart of the defensive copy: the collection handed out is either
copied or presented as an immutable view.

A third option is carrying the data in an immutable type; such data need not be
copied, and sharing it is safe. This preference of the functional programming approach
will be treated in the paradigms topic.

#### Writing the No-Modification Promise into the Type

Some languages allow declaring, at the type level, that a parameter will not be
modified; an operation in the body that modifies it then produces a compile error.

This has two benefits: the contract lives in the signature rather than the
documentation, so the reader need not consult it, and the promise becomes provable — a
line added to the body later cannot silently break it.

In languages without such a declaration, the same promise is protected only by
documentation and review discipline. Preferring immutable types is then the most
reliable way to make it enforceable.

#### Determining Which Model Is in Use

Which model a language uses can be determined with two small tests:

1. **Assign a new value** to the parameter. If the caller's variable changes, pass by
   reference is in use.
2. **Modify the object in place.** If this is visible on the caller's side, the object
   is being shared.

If neither is visible, it is pass by value; if only the second is visible, it is pass
by value of object reference — the shortest way to determine the model without
documentation.

#### Summary

- In pass by value, a copy is passed; in pass by reference, the caller's variable
  itself is passed; in pass by value of object reference, the address is copied and the
  object is shared.
- The most common model is the third: modifying the object is visible from outside,
  rebinding the parameter is not.
- This distinction is not observed with immutable types; the confusion arises only with
  mutable types.
- A side effect is any trace beyond the return value; the problem is not its existence
  but it being unexpected.
- Both the in-place-modifying contract and the new-value-producing contract are
  legitimate; the choice is made visible in the name and the documentation.
- Data to be stored is given a defensive copy; immutable types remove this need.

#### Next Step

Names defined inside a function body are not visible from outside; names from outside,
however, can be read from inside the body. What is the exact definition of these
visibility rules, and if a name is defined in more than one place, which one wins? The
next lesson takes up the rules of scope and lifetime.

### Scope and Lifetime

Source: https://academia.sh/en/courses/programming-fundamentals/scope-and-lifetime

Name lookup order, shadowing, writing to global state, the lifetime of local variables, and closures.

The previous lesson showed that a function can modify objects from outside. This raises
a natural question: which variable does a name written inside a function body refer
to, and are names defined there visible from outside?

The subject of this lesson is **scope** — the region where a name is valid — and
**lifetime** — the interval during which a value exists. The two are often confused;
one concerns visibility, the other duration.

#### Local Scope

Names bound inside a function body are **local**: they are visible only within that
body and disappear when the function returns.

```python
def summarize(measurements: list[int]) -> float:
    total = 0                     # local name
    for measurement in measurements:         # the loop variable is local too
        total += measurement
    return total / len(measurements)

print(summarize([12, 18]))            # 15.0
# print(total)                        -> error: 'total' is not defined here
```

This is a direct consequence of the memory layout lesson in the previous course: local
variables live in the call frame, released on return. The benefit of locality is
isolation — two separate functions can use the same name without affecting each other.

#### Name Lookup Order

When a name is used in a body, the language searches for it in a specific order:

1. **Local scope** — the body of this function.
2. **Enclosing scope** — the body of the outer function, in nested definitions.
3. **Global scope** — the outermost level of the module.
4. **Built-in names** — the names the language itself provides.

The search stops at the first place the name is found; if a name is defined both
locally and globally, the local one wins inside the body.

```python
LIMIT = 20                          # global

def count_over(measurements: list[int]) -> int:
    count = 0                       # local
    for measurement in measurements:
        if measurement > LIMIT:           # read from the global name
            count += 1
    return count

print(count_over([12, 25, 30]))   # 2
```

**Reading** from a global name is unrestricted; writing to one is different, and is the
subject of the next section.

#### Shadowing

Using the same name locally as an outer name is called **shadowing**. The outer name
becomes inaccessible; it does not disappear, it is merely not visible in that region.

```python
LIMIT = 20

def incorrect_use(measurements: list[int]) -> int:
    LIMIT = 5                       # shadows the outer name
    return len([m for m in measurements if m > LIMIT])

print(incorrect_use([12, 25, 30]))   # 3   — not the expected 2
print(LIMIT)                          # 20  — the global value did not change
```

Shadowing is not always a mistake; it can be used deliberately in short bodies. It
becomes a source of errors when it goes **unnoticed**: the reader assumes the outer
value while the code uses the local one. The criterion from the naming lesson applies
here too — distinct concepts get distinct names.

#### Writing to Global State

A function modifying a global variable falls into the side effect category from the
previous lesson and is generally avoided. Most languages make this deliberately
awkward: writing to a global name requires an explicit declaration; otherwise the
assignment creates a new local name.

The rationale for avoiding this has three parts. The function's behavior stops
depending only on its arguments; the same call can return a different result depending
on the global state's history. Testing becomes harder, since a test must reset state on
every run. When two threads concurrently modify the same global value, the result
depends on ordering.

The alternative is to **take** the needed value **as an argument** and **return** the
result. This makes the function independent and testable.

Constants are an exception to this rule: global values that do not change can be shared
and improve readability.

#### Lifetime and Closures

Scope specifies visibility, lifetime specifies duration. The two usually coincide: a
local variable arrives with the frame and leaves with it.

There is one case where this coincidence breaks down: if a function defined inside
another accesses a local variable of the outer function, that variable must continue
to exist even after the outer function returns. This structure is called a **closure**.

```python
def limit_checker(limit: int):
    """Produces a function that decides based on the given limit."""
    def exceeds(measurement: int) -> bool:
        return measurement > limit        # the outer 'limit' was captured
    return exceeds

over_twenty = limit_checker(20)
over_ten = limit_checker(10)

print(over_twenty(25), over_twenty(15))   # True False
print(over_ten(15))                       # True
```

When the call to `limit_checker` ends, its frame is released, but the value of `limit`
continues to exist: the produced function accesses it. In the terms of the previous
course, the captured value lives on the heap, not the stack, and it is not collected as
long as the accessing function exists.

**Modifying** the captured value from the inner function requires a separate
declaration. The rule is the same as for global names: an assignment without the
declaration creates a new local name instead of updating the outer one. This is a
common source of errors in closures that keep a counter: an inner function writing
`count = count + 1` treats `count` as local, so the read on the right also goes to the
local name, and the call stops with an error for reading a local name that has no value
yet.

Closures are a simple way of producing behavior through a parameter; the
object-oriented approach meets the same idea by storing state in an object. The
comparison of the two will be made in the paradigms topic.

#### Modules and Namespaces

Global scope is not as broad as it appears: every source file has its own namespace. A
name defined in one file is not automatically visible in another; it must be imported.

Importing establishes a new binding to the name; there are two forms, and their effect
on readability differs:

```python
import math                      # access through the module name
print(math.sqrt(16))             # 4.0

from math import sqrt            # bring the name directly into our own namespace
print(sqrt(16))                  # 4.0
```

In the first form, where `sqrt` comes from is visible in the call. In the second, the
call is shorter, but the name's source is no longer visible, and two sources carrying
the same name can shadow each other.

Namespaces are the structural way of preventing collisions: two different modules can
use the same name with different meanings. The larger-scale version is package and
namespace hierarchies, detailed in the language curricula.

The rule concerning global scope applies here too: mutable state at the module level is
accessible from anywhere in the file, producing the same testing and concurrency
problems.

#### Keeping a Variable's Lifetime Short

One practical rule summarizes this entire lesson: **a name is defined in the narrowest
region it needs.** A variable used inside a loop is defined inside the loop; a variable
belonging to a function is defined inside the function.

This rule turns scope into a design tool. Narrow scope has three benefits: fewer names
for the reader to keep in mind, a bounded region where a name can change, which makes
debugging easier, and a lower probability of shadowing and name collisions.

#### Summary

- Names bound in a function body are local and disappear along with the call frame.
- Name lookup starts at local scope, continues through enclosing and global scope, and
  ends with built-in names; the first one found wins.
- Shadowing makes the outer name inaccessible; its danger lies in going unnoticed.
- Writing to global state makes a function independent of its arguments and complicates
  testing; the value is taken as an argument and the result is returned.
- A closure is an inner function that captures a local variable from the outer
  function; the captured value continues to exist after the outer call ends.
- Names are defined in the narrowest region they need.

#### Next Step

A function calling itself creates an interesting situation on the call stack: multiple
frames of the same function exist at the same time. The next lesson takes up
recursion — the base case, the reduction step, and stack depth.

### Recursion

Source: https://academia.sh/en/courses/programming-fundamentals/recursion

The base case and the reduction step, expansion on the call stack, infinite recursion, and its cost.

If a function can call another function inside its body, it can call itself as well.
This is permitted by definition, and it is called **recursion**.

This idea, which appears circular at first glance, becomes clear once the call stack is
understood: each call has its own frame, so multiple calls to the same function can
exist at once, each with independent variables.

#### Two Required Parts

Every recursive definition consists of two parts:

**Base case:** The smallest case, answered directly without recursion.

**Reduction step:** The step that transforms the problem into a smaller instance of the
same problem.

If either part is missing, the solution does not work. Without a base case, the calls
continue indefinitely; if the reduction does not make the problem smaller, the base
case is never reached.

```python
def factorial(n: int) -> int:
    """Computes the value of n!. n must not be negative."""
    if n < 0:
        raise ValueError("negative value")
    if n <= 1:              # base case
        return 1
    return n * factorial(n - 1)     # reduction: n decreases to n - 1

print(factorial(5))        # 120
print(factorial(0))        # 1
```

Writing the base case as `n <= 1` gives the correct answer for both $0$ and $1$, and
guarantees that every non-negative input reaches the base case.

#### Expansion on the Stack

Executing the call `factorial(4)` proceeds as frames accumulate on top of one another
and are then resolved in reverse order:

```
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * 1))          ← base case reached
= 4 * (3 * 2)
= 4 * 6
= 24
```

The lines going upward show the calls expanding, and the lines going downward show the
returns being combined. At the deepest point, four frames are on the stack at the same
time; each has its own value of `n`.

This is the clearest example of the frame model established in the previous course: `n`
is not a single memory cell; it exists separately in the frame of each call.

#### Infinite Recursion

When the base case is forgotten, or when the reduction does not make the problem
smaller, calls accumulate and the stack runs out.

```python
def broken(n: int) -> int:
    return n * broken(n - 1)     # no base case

# broken(5)  -> recursion limit exceeded error
```

This behavior was defined in the memory layout lesson of the previous course: every
call adds a frame, none of them return, and the space allocated for the stack runs out.
In languages with a runtime guard, a controlled error is raised; in those without one,
the process is terminated.

The error message typically contains the same function name hundreds of times — this is
the distinctive signature of infinite recursion.

#### Naturally Recursive Problems

Recursion is the natural solution when the problem itself is defined recursively. The
sum of a list of measurements can be defined this way: *the sum of an empty list is
zero; the sum of a non-empty list is its first element plus the sum of the rest.*

```python
def total(measurements: list[int]) -> int:
    if not measurements:                        # base case: empty list
        return 0
    return measurements[0] + total(measurements[1:])   # reduction: one fewer element

print(total([12, 18, 7]))     # 37
print(total([]))              # 0
```

This solution is a direct translation of the definition; it is easy to read. In
exchange, it copies the rest of the list on every call and opens as many frames as
there are elements — a loop performing the same task works with a single frame and no
copying.

Where recursion is genuinely superior is in problems where the data itself branches:
traversing tree structures, scanning directories with their subdirectories,
divide-and-conquer algorithms. These structures are the subject of the **Data
Structures** and **Algorithms** courses; most solutions there are written recursively.

#### Cost and Repeated Computation

Recursion has two costs: memory per frame and extra processing per call. A third, more
insidious cost is **the same computation being repeated**.

The direct recursive definition of the Fibonacci sequence is the canonical example of
this.

```python
def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))          # 55
```

While computing `fib(5)`, `fib(3)` is computed twice and `fib(2)` three times. As the
input grows, the number of repetitions grows exponentially; computing `fib(30)` makes
more than a million calls.

The solution is to store the computed values:

```python
def fib_memoized(n: int, memo: dict[int, int] | None = None) -> int:
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n in memo:                 # already computed, do not recompute
        return memo[n]
    memo[n] = fib_memoized(n - 1, memo) + fib_memoized(n - 2, memo)
    return memo[n]

print(fib_memoized(30))             # 832040
```

The precondition for memoization is that the function always produces the same result
for the same input; the result of a function that depends on state beyond its input
cannot be stored this way. This technique is called **memoization**, and it is the
foundation of dynamic programming; it is treated in its general form in the Advanced
Algorithms course. The lesson here is that recursion gives the structure of a solution
but does not bring efficiency on its own.

#### Mutual Recursion

Recursion is not limited to a function calling itself directly. Two functions calling
each other can also form a recursive structure; this is called **mutual recursion**.

```python
def is_even(n: int) -> bool:
    if n == 0:
        return True
    return is_odd(n - 1)

def is_odd(n: int) -> bool:
    if n == 0:
        return False
    return is_even(n - 1)

print(is_even(4), is_odd(4))     # True False
```

This example exists to illustrate the concept; the same question is answered in a
single step with the remainder operator. The real use of mutual recursion is in
structures where interdependent definitions are naturally mutual — parsers processing
grammar rules are the typical example: an *expression* definition refers to a *term*
definition, which refers back to *expression*.

The base case rule applies here as well, but it becomes harder to verify: the guarantee
of termination must be found not in a single function but across the entire chain of
calls.

#### Recursion or Loop

The criteria for choosing:

| Criterion | Recursion | Loop |
|---|---|---|
| The problem definition branches | Natural | Requires manual stack management |
| Progress is linear | Pays a frame cost | Cheaper |
| Depth grows with the input | Risk of hitting the stack limit | No limit |
| Readability | Close to the definition | Close to the steps |

The general rule: **use recursion if the problem is defined recursively, use a loop if
the repetition is linear.** Every recursive solution can be converted to a loop; the
conversion may require maintaining a stack manually.

#### Summary

- Recursion is a function calling itself; because each call has its own frame, the
  variables do not mix.
- Every recursive definition contains a base case and a reduction step; if either is
  missing, the solution does not work.
- Calls accumulate on the stack, expansion stops at the base case, and the returns are
  combined in reverse order.
- Infinite recursion exhausts the stack; its signature is the repeated function name in
  the error message.
- Recursion is natural for branching structures; a loop is cheaper for linear
  repetition.
- Recomputing the same subproblem can produce exponential cost; memoization removes
  this repetition.

#### Next Step

In linear recursion, the frame cost appears unavoidable. The situation changes,
however, when the call is the last operation in the body: opening a new frame is no
longer necessary. The next lesson takes up this special form — tail recursion — and its
equivalence to a loop.

### Tail Recursion

Source: https://academia.sh/en/courses/programming-fundamentals/tail-recursion

The call in tail position, transformation with an accumulator parameter, frame reuse, and equivalence to a loop.

The previous lesson showed that, in linear recursion, every call carries a frame cost —
a cost that is not always unavoidable. Under a specific form, no reason remains to keep
the frame.

The subject of this lesson is that form and its equivalence to a loop.

#### Tail Position

A call is in tail position if it is the **last operation** the function performs: no
work remains once it returns, and the returned value is passed directly outward.

The factorial from the previous lesson does not satisfy this condition:

```python
def factorial(n: int) -> int:
    if n <= 1:
        return 1
    return n * factorial(n - 1)      # the multiplication happens AFTER the call returns
```

In the last line, the recursive call is not the last operation; its result will be
multiplied by `n`. The calling frame must therefore wait until the inner call returns,
holding the value of `n` and where to return to.

The tail form of the same computation moves the work not yet done into an
**accumulator parameter**:

```python
def factorial_tail(n: int, accumulator: int = 1) -> int:
    """Computes the value of n! in tail-recursive form."""
    if n <= 1:
        return accumulator                       # base case: return the accumulator
    return factorial_tail(n - 1, n * accumulator)   # last operation: the call itself

print(factorial_tail(5))     # 120
print(factorial(5))          # 120  — the same result
```

The multiplication now happens **before** the call, while the argument is prepared.
Because no work remains once the call returns, there is no need to preserve the
calling frame.

#### Why the Frame Is Not Needed

A frame is kept for two things: the return address and local values. In tail position,
since the inner call's return value passes directly outward, the caller's return
address and the inner call's are the same. Local values are no longer needed either;
all have moved into the arguments.

Consequently, instead of opening a new frame, the existing frame can be **reused** — a
transformation called **tail call optimization**. When applied, the stack does not grow
regardless of recursion depth.

#### Language Support Is Not Universal

Whether this optimization is performed depends on the language and its implementation,
part of the language's definition rather than a detail of speed. Some languages
guarantee it, allowing deep tail recursion to be written safely; some do not apply it
at all.

Python is among the languages that do not apply it; even a function written in tail
form hits the recursion limit as the depth increases:

```python
# factorial_tail(5000)  -> recursion limit exceeded error
```

The rationale is a design choice: preserved frames keep the error trace complete and
debugging easier, at the cost that deep recursion cannot be used.

The conclusion: writing in tail form does not, by itself, guarantee depth. Whether the
language performs this optimization must be known.

In runtimes where the recursion limit can be raised, this appears to be a solution, but
is not: the limit exists to warn before the actual stack space runs out, and raising it
can turn a controlled error into an uncontrolled crash. The correct solution is taking
a depth that grows with the data out of recursion entirely.

#### Equivalence to a Loop

The relationship between tail recursion and a loop is mechanical: accumulator
parameters correspond to loop variables, the reduction step to updates, and the base
case to the loop condition.

```python
def factorial_loop(n: int) -> int:
    accumulator = 1
    while n > 1:                 # the negation of the base case
        accumulator = n * accumulator    # the arguments of the recursive call
        n = n - 1
    return accumulator

print(factorial_loop(5))       # 120
```

All three versions produce the same value; the difference lies only in syntax and
stack behavior — the loop version uses a single frame and recognizes no depth limit.

The correspondences map one by one: the accumulator to the loop variable, the negation
of the base case to the loop condition, the recursive call's arguments to updates in
the body. This mapping also gives the recursive counterpart of the loop invariant — the
meaning the accumulator carries at every call is precisely the loop invariant.

This equivalence also explains what tail call optimization does: the compiler applies
the transformation automatically, and the resulting code is the loop version's code.

#### Converting Non-Tail Recursion to a Loop

Every recursive solution can be converted to a loop, but if the call is not in tail
position, the conversion is not mechanical. The work remaining after the call must be
stored somewhere, and once the frame is removed, that responsibility passes to the
program: **the stack is maintained by hand.**

Traversing a tree-like structure is the typical example of this. The solution below
flattens nested lists without using recursion:

```python
def flatten(data: list) -> list[int]:
    """Reduces nested lists to a single level; uses no recursion."""
    result = []
    pending = [data]                       # parts still to process
    while pending:
        part = pending.pop()
        if isinstance(part, list):
            pending.extend(reversed(part))   # append in reverse to preserve order
        else:
            result.append(part)
    return result

print(flatten([1, [2, [3, 4]], 5]))    # [1, 2, 3, 4, 5]
```

The `pending` list here does the work the call stack does in the recursive version,
holding the parts not yet processed. The code grows longer and readability drops; in
exchange, the depth limit disappears and memory use becomes controllable.

The criterion is clear: if the depth grows without bound with the input, and the
language does not perform tail call optimization, the stack is maintained by hand.

#### Which Form, and When

The choice among the three forms depends on context.

**Direct recursion** is the closest to the problem definition and the easiest to read.
It is preferred when the depth is small and bounded.

**Tail form** is the right choice for deep repetition in languages that guarantee the
optimization. Adding an accumulator parameter drops readability somewhat, so the
accumulator-carrying version is usually placed in a helper function, keeping the outer
interface simple:

```python
def factorial_clean(n: int) -> int:
    """The outer interface is simple; the accumulator detail is hidden."""
    def helper(k: int, accumulator: int) -> int:
        if k <= 1:
            return accumulator
        return helper(k - 1, k * accumulator)
    return helper(n, 1)

print(factorial_clean(5))       # 120
```

This style directly applies the inner-function idea from the scope lesson: the helper
is not visible from outside, and it makes sense only within its own context.

**A loop** is the safe choice in languages without an optimization guarantee, and where
depth grows with the input.

This threefold choice also explains language design preferences. Languages
prioritizing immutability treat recursion, rather than rebinding a loop variable, as
the primary tool of repetition; there, tail call optimization is a necessity, not a
convenience. Languages treating the loop as primary suffer no deficiency from skipping
the optimization — writing the same task with a loop is already expected. Which path a
language chooses determines what its code looks like; this relationship is the central
idea of the next topic.

#### Summary

- A call is in tail position if it is the function's last operation; no work remains
  after it returns.
- Direct recursion is converted to tail form by moving the work not yet done into an
  accumulator parameter.
- In tail position, the calling frame can be reused; this transformation is called tail
  call optimization.
- Whether the optimization is applied depends on the language and is not universal;
  writing in tail form alone does not guarantee depth.
- The conversion between tail recursion and a loop is mechanical: accumulators become
  the loop variable, the base case becomes the loop condition.
- The accumulator detail is hidden from the outer interface by moving it into an inner
  helper function.

#### Next Step

This topic established the function as a tool of abstraction: work is named, input and
output are bound to a contract, and scope is isolated. The function is not the only
tool of abstraction. The next topic will compare three separate approaches to
organizing programs — structured, object-oriented, and functional — and solve the same
problem with each of them.

## A Survey of Programming Paradigms

The distinguishing ideas of the structural, object-oriented, and functional approaches, and the criteria for choosing a language.

### Structural Programming

Source: https://academia.sh/en/courses/programming-fundamentals/structural-programming

Building programs with sequence, selection, and iteration; abandoning the jump statement and top-down decomposition.

The structures used throughout this course — sequential statements, conditional
branching, loops, and functions — belong to a particular organizing philosophy. That
philosophy is called **structural programming**, and its looking natural does not mean
it was accepted without dispute; it is the outcome of a debate.

This topic compares three organizing approaches. Each answers differently the question
of what units a program is divided into and how those units communicate. All three can
solve the same problem; their differences show up as programs grow.

#### Three Structures Suffice

The core claim of structural programming is this: every computable program can be
written using only three control structures.

- **Sequence:** Statements executed one after another.
- **Selection:** Following one of two paths depending on a condition.
- **Iteration:** Repeating a block depending on a condition.

That these three suffice is a formally proven result. Its practical meaning is that no
fourth structure — in particular, a statement that jumps to an arbitrary point in the
program — is needed.

#### The Problem with the Jump Statement

Early languages included a statement that allowed jumping directly to a desired line of
the program. At the hardware level this is natural: as seen in the previous course, a
branch instruction is nothing more than writing a new address into the program counter.

The problem shows up in readability. In a program written with unrestricted jumps, which
paths can reach a given line cannot be determined by reading the text. Reasoning about
the value of a variable at that point requires examining every path that reaches it, and
the number of paths grows quickly with the number of jumps.

Structural control structures solve this problem by definition: each structure has
exactly one entry and one exit. A block is entered only at its start and left only at
its end. This constraint makes it possible to understand what a block does by looking at
the block itself.

Early-exit statements — breaking out of a loop, returning early from a function — are a
controlled relaxation of this constraint. What sets them apart from unrestricted jumping
is that their targets are fixed and structural: an exit always goes to the end of the
structure it is inside.

#### Top-Down Decomposition

The second component of structural programming is breaking the problem down step by
step. The process starts at the top: the program is broken into a few high-level steps;
each step is broken into its own substeps; the breaking stops once each piece is small
enough to be written directly.

The decomposition in the pseudocode lesson follows exactly this method. For the running
problem:

```
summarize(measurements)
├── validate(measurements)     → empty?, valid?
├── add_up(measurements)       → total
├── find_largest(measurements) → largest
└── average(total, count)      → average
```

Each node corresponds to a procedure. The top-level procedure knows what the lower-level
ones do; it does not know how they do it. This information hiding limits how far a
change propagates: when the inside of `find_largest` changes, its caller is unaffected.

#### The Structural Solution to the Common Problem

```python
def validate(measurements: list[int]) -> None:
    """Checks that the measurement list is processable."""
    if not measurements:
        raise ValueError("measurement list is empty")


def add_up(measurements: list[int]) -> int:
    total = 0
    for measurement in measurements:
        total += measurement
    return total


def find_largest(measurements: list[int]) -> int:
    largest = measurements[0]
    for measurement in measurements:
        if measurement > largest:
            largest = measurement
    return largest


def summarize(measurements: list[int]) -> tuple[float, int]:
    """Returns the average and the largest value."""
    validate(measurements)
    return add_up(measurements) / len(measurements), find_largest(measurements)


print(summarize([12, 18, 7, 25, 14]))     # (15.2, 25)
```

The structure of the solution matches the decomposition tree exactly. Each procedure
does one thing, can be tested on its own, and its name says what it does.

#### Grouping Procedures

As decomposition continues, the number of procedures grows into a flat list. A second
organizing layer is needed: related procedures are collected into the same **module**.

A module is the practical counterpart of the namespace defined in the scope lesson.
Procedures that work with measurement data sit in one module, reporting procedures in
another. A module boundary does two things: it separates names, and it documents which
procedures change together.

A module also has an interface. Procedures exposed to the outside are separated from
helpers used only internally; this separation is the same internal-versus-external
visibility distinction from the previous course's binding lesson. Exposing few
procedures to the outside makes changing the inside of a module easier.

This organization is what keeps structural programming workable in large programs: the
program is no longer read as a hierarchy of procedures but as a **relationship between
modules**. The scaled-up version of the same idea — components and layers — is the
subject of the **Software Architecture** curriculum.

#### Data and Procedures Kept Separate

The distinguishing feature of this approach is that **data and the procedures that
operate on it are defined separately.** The `measurements` list is a data structure;
`add_up` and `find_largest` are independent procedures that operate on it. Data travels
to procedures as an argument.

In small programs this arrangement is clear and needs no extra concept. As a program
grows, two difficulties appear.

First, which procedures a data structure can be used with is written nowhere in the
code; the relationship rests on convention alone. Passing the same list to the wrong
procedure is an error the language does not prevent.

Second, the rules of a data structure — its invariants — are preserved in a scattered
way. The rule "the measurement list is never empty" has to be re-checked in every
procedure that uses the list; when one procedure forgets, the rule is silently violated.

These two difficulties are the starting point of the next lesson: the idea of gathering
data and the behavior that operates on it into a single unit.

#### The Testability Gain

A less-discussed but decisive consequence of decomposition is testability. A single long
procedure can only be tested by running it from start to finish; decomposed procedures
can each be tested independently.

In the solution above, `find_largest` can be tested without reading a file, writing to
the screen, or depending on any other step: a list is given, the returned value is
compared against the expected one. Edge cases — a single-element list, all equal values
— are tested with the same ease.

This gain grows when procedures are **pure**: a procedure that looks at nothing beyond
its input and leaves no trace outside requires no setup to test. The same observation
becomes the core idea of a paradigm in this topic's third lesson.

#### Where Structural Programming Stands

Structural programming was not invalidated by the paradigms that followed; it became
the ground they were built on. The method of an object-oriented class and the function
of a functional language are both written, on the inside, with sequence, selection, and
iteration.

For this reason, the question of "which paradigm" is asked not at the level of control
structures but at the level of **what units a program is divided into**. The structural
answer is the procedure.

#### Summary

- Structural programming holds that every program can be written with sequence,
  selection, and iteration; these three suffice.
- Unrestricted jumping makes it impossible to trace which paths reach a given point;
  structural control structures have a single entry and a single exit.
- Early-exit statements are a controlled relaxation of this constraint because their
  target is fixed.
- Top-down decomposition breaks a problem into procedures; the top-level procedure knows
  what the lower level does, not how it does it.
- Keeping data and procedures separate is simple in small programs, but in large
  programs it makes preserving the relationship and the invariants harder.
- Decomposed procedures can be tested independently; related procedures are grouped
  into modules to establish name separation and a boundary for change.

#### Next Step

Gathering data and the procedures that operate on it into a single unit answers directly
the two difficulties that emerged at the end of this lesson. The next lesson introduces
the basic concepts of the object-oriented approach and solves the same problem again,
this time through an object.

### Introduction to Object-Oriented Programming

Source: https://academia.sh/en/courses/programming-fundamentals/introduction-to-object-oriented-programming

Combining data and behavior, class and object, encapsulation, preserving invariants, and the idea of an interface.

The previous lesson ended with two difficulties: which procedures a data structure
belongs to is written nowhere in the code, and the rules of a data structure have to be
preserved separately in every procedure that uses it.

**Object-oriented programming** answers both difficulties with the same move: it
gathers data and the behavior that operates on it into a single unit. This unit is
called an **object**.

#### Class and Object

A **class** is the definition of an object type: it states which data it will carry and
which operations it will support. An **object** is a concrete instance produced from
that definition.

The distinction mirrors the one between a type and a value: a class is a template, an
object an individual produced from it. A single `MeasurementSeries` class can produce
hundreds of independent objects, each with its own data and shared behavior.

```python
class MeasurementSeries:
    """Carries a sequence of measurements together with the operations on it."""

    def __init__(self, measurements: list[int]) -> None:
        if not measurements:
            raise ValueError("measurement list cannot be empty")
        self._measurements = list(measurements)   # defensive copy

    def add(self, measurement: int) -> None:
        self._measurements.append(measurement)

    def average(self) -> float:
        return sum(self._measurements) / len(self._measurements)

    def largest(self) -> int:
        largest = self._measurements[0]
        for measurement in self._measurements:
            if measurement > largest:
                largest = measurement
        return largest

    def count(self) -> int:
        return len(self._measurements)


series = MeasurementSeries([12, 18, 7, 25, 14])
print(series.average(), series.largest(), series.count())   # 15.2 25 5

series.add(30)
print(series.average(), series.largest())                   # 17.666666666666668 30
```

In the structural solution, `add_up`, `find_largest`, and the data stood apart; here
they are gathered into a single unit. The calling style also changes: instead of
passing data to a procedure, a message is sent to an object.

#### Encapsulation and Invariants

An object's data is closed to direct access from the outside; access happens only
through the operations the object offers. This is called **encapsulation**.

The reason for encapsulation is not secrecy but **preserving invariants**. The
invariant of the `MeasurementSeries` class is this: *the measurement list is never
empty.* This rule is preserved in two places — it is checked at creation, and no
operation is offered that would empty the list.

In the structural solution, preserving the same rule required a separate check in every
procedure that used the list. Here the rule sits in a single place: the owner of the
data.

This continues the defensive-copy discussion from the previous topic: without the copy
in the constructor, changing the outside list could violate the invariant. An operation
returning data outward would need to return a copy for the same reason.

#### Interface and Implementation

The set of operations an object exposes to the outside is called its **interface**; how
those operations are carried out is its **implementation**. The caller knows only the
interface.

The value of this distinction is that the implementation can be changed freely. Instead
of recomputing the largest value from scratch on every call, `MeasurementSeries` could
keep it updated as elements are added; because the interface stays the same, not a
single line of the calling code changes.

This is a stronger form of the information-hiding idea from structural decomposition:
there, the inside of a procedure was hidden; here, the representation of the data is
hidden as well.

#### Relationships Between Objects

A single object is rarely enough; a program is built as a network of objects sending
each other messages. Relationships take two basic forms.

**Composition** is one object carrying another as its part. A report object that stores
a measurement series holds the series inside itself and manages its lifetime.

**Collaboration** is one object knowing another and sending it messages; the two live
independently.

```python
class Report:
    """Produces a readable summary from a measurement series."""

    def __init__(self, series: MeasurementSeries) -> None:
        self._series = series                 # collaboration: series was created outside

    def text(self) -> str:
        return (f"{self._series.count()} measurements, "
                f"average {self._series.average():.1f}, "
                f"largest {self._series.largest()}")


series = MeasurementSeries([12, 18, 7, 25, 14])
print(Report(series).text())    # 5 measurements, average 15.2, largest 25
```

The `Report` class does not know the inside of the series; it uses only its interface.
This is the object-to-object counterpart of the interface–implementation distinction
from the previous section, and it gives the deciding criterion for design: **the less
one object depends on the internal structure of another, the less a change propagates.**

The direction of the dependency is also a decision. Here the report depends on the
series, and the series knows nothing of the report; adding a new report format
therefore never changes the series. Had the dependency run the other way, every new
report type would have required changing the series as well.

#### Inheritance and Polymorphism

Two more concepts belong to this approach and are only introduced here.

**Inheritance** is one class extending the definition of another. Shared behavior is
written once in the parent class; subclasses add the differences.

**Polymorphism** is the same message behaving differently across different object
types. A caller can invoke the same operation without knowing the exact type of the
object it is dealing with; which implementation runs is decided by the object.

The practical consequence of polymorphism is that conditional chains disappear: logic
that says "behave differently by type" is distributed into separate classes instead of
an `if` chain. This is the object-oriented counterpart of the lookup-table approach from
the conditional-branching lesson.

Using the two correctly — in particular, knowing when to prefer composition over
inheritance — is the subject of the **Software Design and Architectural Principles**
curriculum.

#### Identity and Equality

Because objects carry state, the word "same" carries two meanings. The identity–equality
distinction from the variables lesson turns into a design decision here.

Should two measurement series that carry the same values be considered equal, or only
when they are the same object? The answer depends on what the object represents.

**Value objects** — a date, a monetary amount, a coordinate — are defined by their
content; two instances with the same content are equal, and they are usually made
immutable.

**Entity objects** — a user account, an order — are defined by their identity. Two
accounts are different accounts even if every field matches; what distinguishes them is
identity.

Without this distinction, searching and comparing in collections produces unexpected
results. Languages generally let a class define its own equality behavior; without that
definition, the default is identity comparison.

The distinction between value and entity objects is one of the core concepts of
domain-driven design and is expanded in the **Software Design and Architectural
Principles** curriculum.

#### When It Fits, When It Does Not

Object-oriented organization is strong where a problem naturally contains **entities
with state**: an account, a connection, a document, a game character. These entities
have rules, and the rules must stay with the data.

By contrast, building an object for a stateless pure transformation adds an unnecessary
layer. An operation that adds two numbers does not need a class.

The second criticism concerns scale: because objects carry state, a program splits into
many pieces of mutable state. As objects hold references to one another, tracing how far
a change spreads becomes harder. This observation is the starting point of the next
lesson.

#### Summary

- The object-oriented approach gathers data and the behavior that operates on it into a
  single unit.
- A class is a definition; an object is a concrete instance produced from it.
- Encapsulation limits access to data to an object's own operations; its purpose is to
  preserve invariants in a single place.
- Separating interface from implementation allows the internal structure to be changed
  without affecting the caller.
- Inheritance shares common behavior; polymorphism selects behavior by type without a
  conditional chain.
- The approach is strong for entities with state; it adds an unnecessary layer for pure
  transformations, and mutable state that spreads at scale is a cost.

#### Next Step

If tracing mutable state becomes harder, the counter-idea that comes to mind is
obvious: never change state at all. The next lesson introduces the functional approach,
which treats computation as value transformation, and solves the same problem a third
time, this time without changing a single value.

### Introduction to Functional Programming

Source: https://academia.sh/en/courses/programming-fundamentals/introduction-to-functional-programming

Pure functions, immutability, functions used as values, transformation chains, and confining side effects.

The previous lesson noted that objects carry state and that a program splits into many
pieces of mutable state. Tracing how far a change spreads becomes harder as the program
grows.

**Functional programming** answers this problem at the root: never change values.
Computation is not updating something that already exists but **producing** a new value
from the input.

#### The Pure Function

A function is **pure** if it satisfies two conditions:

1. It always returns the same result for the same input.
2. It has no observable side effect — it does not change its argument, does not update
   outside state, does not print to the screen.

```python
def average(measurements: list[int]) -> float:      # pure
    return sum(measurements) / len(measurements)

total_count = 0

def dirty_average(measurements: list[int]) -> float:   # not pure
    global total_count
    total_count += 1                                    # outside state changed
    measurements.sort()                                 # argument changed
    return sum(measurements) / len(measurements)
```

Purity has four practical consequences. A function can be tested independently of its
context: input goes in, output is checked. Its result can be memoized — the memoization
technique from the recursion lesson only holds for pure functions. Because its calls are
independent of one another, it can be run in parallel across threads. And reading it
requires looking only at itself; there is no need to know the state of anything remote.

#### Immutability

Purity's precondition is that values are not changed. Instead of adding an element to a
list, a **new list** is produced that contains the old elements plus the new one.

```python
measurements = [12, 18, 7]

extended = measurements + [25]           # a new list was produced
print(measurements, extended)            # [12, 18, 7] [12, 18, 7, 25]

sorted_measurements = sorted(measurements)   # a new list
print(measurements, sorted_measurements)     # [12, 18, 7] [7, 12, 18]
```

At first glance this means a copying cost. Functional languages reduce this cost with
**persistent data structures**: the new version shares the unchanged parts of the old
one, and only the changed path is copied. These structures are covered in the data
structures course.

The gain of immutability is that the sharing problem from the variables lesson
disappears. Sharing an immutable value is safe; no one can change it out from under
someone else. The same reasoning also removes the need for a defensive copy.

#### Functions Are Values

The second core idea of the functional approach is that a function is also a value: it
can be bound to a variable, passed as an argument, returned as a result. The closure
example from the scope lesson was the first application of this.

A function that takes or returns a function is called a **higher-order function**.
Three occur in nearly every language:

- **Map:** Passes each element through a function, producing a new sequence of the same
  length.
- **Filter:** Selects the elements that satisfy a condition.
- **Reduce:** Collapses a sequence into a single value with a combining function.

```python
from functools import reduce

raw = [12, -1, 18, -1, 25, 14]

valid = list(filter(lambda m: m >= 0, raw))            # filter
print(valid)                                             # [12, 18, 25, 14]

metric = list(map(lambda m: m / 100, valid))            # map
print(metric)                                             # [0.12, 0.18, 0.25, 0.14]

total = reduce(lambda a, b: a + b, valid, 0)             # reduce
largest = reduce(lambda a, b: a if a > b else b, valid)

print(total, total / len(valid), largest)                # 69 17.25 25
```

These three operations are named versions of the accumulator pattern. In the loop
version, what is being done is buried in the body; here, the name of the operation is
visible directly: is it filtering, transforming, or totaling.

The starting value of reduce is the same issue as the identity-element discussion from
the loops lesson; if no starting value is given for an empty sequence, the reduction is
undefined.

#### Composition

Small, pure functions are chained so that the output of one becomes the input of the
next. This chain is called **composition** and is the basic organizing form of
functional programs.

```python
def valid_ones(measurements: list[int]) -> list[int]:
    return [m for m in measurements if m >= 0]

def average(measurements: list[int]) -> float:
    return sum(measurements) / len(measurements)

def summary(raw: list[int]) -> tuple[float, int]:
    """Produces the average and the largest value from raw data; changes nothing."""
    valid = valid_ones(raw)
    return average(valid), max(valid)

raw = [12, -1, 18, -1, 25, 14]
print(summary(raw))              # (17.25, 25)
print(raw)                       # [12, -1, 18, -1, 25, 14]  — input unchanged
```

In the object-oriented solution, data sat inside an object and changed through
messages; here, data flows between functions and each step produces a new value.

#### Lazy Evaluation

Transformation chains tend to produce an intermediate collection at every step: filter
produces one new list, map another. If the input is large, these intermediate results
take up unnecessary space in memory.

The lazy iteration introduced in the loop-control lesson solves this problem: values
are produced as they are requested, and each step of the chain flows through a single
element at a time. No intermediate list is ever created.

The second consequence of laziness is that **infinite sequences** can be defined. The
first five elements of a sequence with no end can be taken; because the elements not
taken are never computed, the computation is finite even though the definition is not.
Some functional languages make laziness the default behavior; in most languages it is
offered as a separate construct.

Its cost is that **when** the computation happens becomes uncertain: it runs not when
the chain is built but when the result is requested. Combined with side-effecting code,
this leads to behavior whose order cannot be predicted — which is why laziness is
discussed together with pure functions.

#### Where Side Effects Go

A program with no side effects at all is useless: a result has to be written somewhere,
an input has to be read from somewhere. The functional approach does not ignore side
effects; it **moves them to a boundary**.

The common layout is this: the core of the program consists of pure functions, an outer
shell handles input and output. The shell reads data, hands it to the core, writes the
returned result. This keeps the entire business logic testable; the part that is hard
to test is kept thin.

This layout applies not only in functional languages but in any language. That none of
the computation functions written throughout this course print to the screen was a
deliberate application of this separation.

#### Limits

The functional approach has costs of its own. Problems that are inherently stateful — a
game's current state, whether a connection is open — require turning state into a value
and producing a new version at every step; this can, at times, produce an unnatural
model.

Performance also does not always come for free: although sharing persistent structures
is good, updating a mutable array in place is generally cheaper.

For this reason, most languages do not commit to a single paradigm. Combining a pure
core with a stateful edge, objects together with functions, is common practice.

#### Summary

- A pure function returns the same result for the same input and has no side effect;
  testability, memoization, and parallelism all follow from these two conditions.
- Immutability means producing a new value instead of updating one; it makes sharing
  safe and removes the need for a defensive copy.
- Functions are values; map, filter, and reduce are named forms of the accumulator
  pattern.
- Composition is the chaining of small pure functions and is the basic organizing form
  of a functional program.
- Side effects are not ignored but moved to the boundary of the program: a pure core, a
  stateful shell.
- The approach carries a cost for inherently stateful problems and where in-place
  updates are cheap.

#### Next Step

All three paradigms solved the same problem, and all three are supported with
different weight across different languages. The final lesson of the course takes up
the axes along which a language differs and how to choose a language to learn, then
states which course carries forward the concepts built in this course.

### Choosing a Language

Source: https://academia.sh/en/courses/programming-fundamentals/choosing-a-language

The design axes that separate languages, criteria for choosing a first language, and knowledge that transfers.

This course built its concepts without tying them to a particular language; the
examples were written in a single language, but nothing explained was specific to it.
The question that closes the course is this: what separates languages from one another,
and which one should a learner start with?

The question has no answer of the form "which language is best." Languages are designs
that have chosen different trade-offs; what they gain on one axis, they pay for on
another.

#### Why Languages Diverge

Every language is designed to make a particular set of problems easier, and that choice
makes something else harder. A language that offers control close to the hardware
leaves memory management to the programmer; a language that prioritizes safety
restricts that same control. A language that offers fast writing defers part of its
errors to run time.

For this reason, the question to ask when comparing languages is not "which is better"
but **"which trade-off has it chosen."**

#### Distinguishing Axes

The distinctions touched on throughout the course are the axes that position languages:

| Axis | Ends | Where it appeared in the course |
|---|---|---|
| Type-checking time | Static ↔ dynamic | Basic data types |
| Type strictness | Closed to implicit conversion ↔ open | Type conversion |
| Memory management | Manual ↔ automatic collection | Memory layout (previous course) |
| Execution model | Compilation ↔ interpretation ↔ virtual machine | Compilation chain (previous course) |
| Mutability | Immutable by default ↔ mutable by default | Functional approach |
| Paradigm weight | Object-centered ↔ function-centered ↔ multi-paradigm | This topic |
| Concurrency model | Threads ↔ event loop ↔ message passing | Operating system concepts |

Learning a language means learning its position on these axes. Syntax is picked up in a
few days; what is actually being learned is which errors the language prevents and
which ones it leaves to the programmer.

An eighth axis is not technical but is decisive: the **ecosystem**. A language's
libraries, tools, and accumulated community knowledge set the boundary of what problems
can be solved with it. Even good language design does not help if no library exists for
the target domain — the work then begins before the language choice does.

#### Choosing a First Language

When starting to learn, the choice is made by looking at the **learning experience**
rather than the power of the language. Four criteria are useful.

**Feedback speed.** Seeing the result of written code in a short time speeds up
learning. Long compilation and setup steps are extra overhead for a beginner.

**Quality of error messages.** A good message states what the problem is, where it is,
and what was expected. At the beginner level, this teaches more than a tutorial does.

**Visibility of concepts.** Some languages show this course's concepts openly: type
declarations, scope rules, memory behavior. Others hide them; this brings convenience
but delays learning the concepts.

**Applicability.** Being able to produce something useful with the language learned in
a short time sustains continuity.

These criteria do not point to a single language, and they should not. What matters is
staying with the chosen language long enough for the concepts to settle; switching
languages often results in relearning syntax each time without ever reaching the
concepts.

#### What Transfers and What Does Not

How much knowledge carries over when moving to a new language depends on what was
learned.

**What transfers:** the whole of this course. Variables and binding, the concept of
type, control flow, the loop invariant, the function contract, scope rules, recursion,
the distinguishing ideas of the paradigms. These belong to programming, not to a
language.

**What does not transfer:** syntax details, standard library names, tool-chain
commands, language-specific idioms. These are relearned in every language and take
little time to relearn.

The ratio shifts with experience: in a first language, almost everything looks new; by
a third language, what remains to be learned is only the position on the axes and the
syntax. For this reason, time spent on a first language is an investment that carries
over to every language that follows.

A useful criterion when choosing a second language is that it **differs clearly from
the first on some axis**. Learning a statically typed language after a dynamically
typed one shows the concept of type from both sides; a manually managed language after
an automatically managed one makes the memory model visible.

#### Problem Domain Narrows the Choice

Choosing a language for a project is a different question, and it generally leaves less
freedom. The deciding factors are the languages the target platform supports, the
libraries the domain requires, the team's existing knowledge, and maintainability.

The last factor usually weighs the most. Code is read and maintained far longer than it
takes to write; a language the team can read is a better choice than a technically
superior language no one on the team knows.

#### Languages Change

A language is not a tool fixed at the moment it is chosen; it evolves across versions.
New constructs are added, mistaken decisions are corrected, some features are dropped.

This evolution produces one more axis that separates languages: **backward-compatibility
policy.** Some languages treat keeping old code running as the top priority and live
with their mistaken decisions as a result. Others accept breaking changes for the sake
of a clean design and pass the migration cost on to large codebases.

The practical consequence is that part of what is learned depends on the version.
Concepts are permanent; which version a given construct is available in is not. For
this reason, sources and documentation state explicitly which version they describe,
and code states explicitly which version it targets.

The same principle applies to dependencies: libraries are versioned too, and
compatibility rules work the same way. Version management is the subject of the
**Software Development Practice** curriculum.

#### Wrapping Up This Course

The course started from the concept of a program and arrived at three organizing
approaches. In order: a program is an input–process–output transformation; values are
bound to names, and their types state which operations are defined on them; flow is
directed by conditions and loops, and every loop has a termination reason and an
invariant; functions name work and bind it to a contract, isolate scope, and make
recursion possible; paradigms determine which units these pieces are gathered into.

The same problem — summarizing a series of measurements — was solved four times over
the course: by hand with a loop, broken into procedures, through an object, and with
pure functions. All four worked correctly. The difference between them is not speed but
**how they respond to change** — and that is the criterion that becomes decisive as a
program grows.

#### Summary

- Languages are designs that have chosen different trade-offs; comparison is done with
  the question "which trade-off has it chosen," not "which is better."
- Type-checking time, type strictness, memory management, execution model, mutability,
  paradigm weight, and concurrency model are the main distinguishing axes; the
  ecosystem is a decisive factor that is not technical.
- Feedback speed, quality of error messages, visibility of concepts, and applicability
  are the criteria for a first language choice.
- Concepts transfer between languages; syntax, library names, and tool commands do not.
- A second language makes an axis visible when it differs clearly from the first on
  that axis.
- Platform, libraries, team knowledge, and maintainability are decisive when choosing a
  language for a project.

#### Next Step

Throughout this course, data was always kept in ready-made collections: a list was
given, and it was traversed. How is a collection actually stored, why is searching fast
in some structures and slow in others, and which structure suits which operation? The
next course — **Data Structures** — takes up these questions and brings together the
memory model from the previous course with the abstraction tools from this one.