Programming Fundamentals

1Introduction

This lecture presents a program as a procedure that receives input and produces output. It describes execution in terms of state and control flow and explains the roles of variables, conditional branches, iteration, and functions.

2Basic Terms

An inputInput is data received from outside a program for use in a computation. An outputOutput is data presented outside the program as a computational result. Screen display, file access, and network communication are examples of inputoutputInputoutput; IO.

A stateState is the collection of values held by a program at a particular point during execution. A variableVariable is a name through which a program refers to a value. If a variable permits assignment, its associated value can be updated.

Control flowControl flow is the order in which the instructions of a program are executed. A conditional branchConditional branch selects the next operation according to the truth value of a condition, while iterationIteration repeats an operation under a specified condition.

A functionFunction is a named program component that receives input values as arguments, executes a sequence of operations, and returns a return value. Some languages also permit functions with no arguments or no return value.

3Describing Execution as State Transitions

If $$S$$S is a state and $$c$$c is one instruction, execution can be represented as a state transition

For example, if $$x=2$$x=2 in state $$S$$S, the assignment x := x + 1 produces a new state $$S^{\prime }$$S' in which $$x=3$$x=3. Here := denotes an update and is distinct from mathematical equality.

4Branching and Iteration

if p then A else B executes $$A$$A when condition $$p$$p is true and $$B$$B when it is false. while p do A executes $$A$$A while $$p$$p is true and then reevaluates $$p$$p. Designing an iteration requires distinguishing the state updated on each iteration, the continuation condition, and the property that must hold at termination.

total := 0
for each score in scores:
    total := total + score
return total

In this example, scores is the input, total is part of the updated state, and return total determines the output. Processing each of $$n$$n scores once performs $$n$$n additions. A subsequent lecture on computational complexity formalizes this analysis.

5Decomposition into Functions

A function can have a specification that states its purpose, accepted inputs, return value, and effects on state or I/O. Decomposing a large procedure into functions with clear responsibilities makes each component easier to verify independently.

However, not every function determines its return value solely from its input values. Functions may update shared state or perform I/O. The next lecture on functional programming examines this distinction in detail.

6Summary

• A program's behavior becomes clearer when its input, output, state, and control flow are distinguished.
• A conditional branch selects an operation, whereas iteration repeats an operation.
• Functions decompose a computation into units with explicit specifications.

7Next Lectures