Cambridge Syllabus Notes

11.3 Structured Programming – Procedures & Functions

Learning Objective

Use the terminology associated with procedures and functions and write clear, efficient pseudocode that satisfies the Cambridge International AS & A Level Computer Science (9618) syllabus.

Key Terminology

Procedure (sub‑routine) – a block of code that performs an action but does not return a value.
Function – a block of code that performs an action and returns a single value to the caller.
Call (invocation) – executing a procedure or function from another part of the program.
Return – statement that ends a procedure/function; for functions it may supply a value.
Parameter (formal parameter) – a variable listed in the definition of a routine.
Argument (actual parameter) – the value or variable supplied when the routine is called.
Pass‑by‑value – a copy of the argument’s value is passed; changes do not affect the original variable.
Pass‑by‑reference – a reference (address) to the original variable is passed; changes do affect the caller’s variable.
Pass‑by‑value‑result (copy‑in / copy‑out) – a copy is passed in, and on return the final value is copied back.
Local variable – declared inside a routine; scope is limited to that routine.
Global variable – declared outside any routine; accessible from any part of the program.
Scope – region of the program in which a name is recognised.
Recursion – a routine that calls itself (directly or indirectly).
Modularity – breaking a program into independent, reusable procedures/functions.

Pseudocode Checklist (Cambridge style)

Concept	Cambridge‑style pseudocode
Procedure definition	`PROCEDURE ProcName(param1, param2)` `…` `END PROCEDURE`
Function definition	`FUNCTION FuncName(param1, param2) RETURNS datatype` `…` `RETURN value` `END FUNCTION`
Calling a procedure	`CALL ProcName(arg1, arg2)`
Calling a function	`result ← FuncName(arg1, arg2)`
Pass‑by‑value (default)	Arguments are listed normally; the routine receives a copy.
Pass‑by‑reference	Prefix the parameter with `REF` in the definition, e.g. `PROCEDURE Swap(REF a, REF b)`
Output parameter (alternative to a function)	Declare the parameter with `OUT`, e.g. `PROCEDURE GetMinMax(arr, OUT min, OUT max)`
Base case in recursion	Use an `IF … THEN … ELSE … END IF` construct that guarantees termination.

Procedures vs. Functions

Aspect	Procedure	Function
Purpose	Perform an action or series of actions.	Compute a value and return it.
Return value	None (may use `OUT` parameters).	Exactly one value (or a structured value).
Typical use	I/O, updating data structures, printing.	Mathematical calculations, data conversion, value lookup.
Invocation syntax	`CALL ProcName(arg1, arg2)`	`result ← FuncName(arg1, arg2)`
Effect on caller	May modify globals or arguments passed by reference.	Does not modify caller’s state unless arguments are passed by reference or `OUT` parameters are used.

Parameter‑Passing Mechanisms (Worked Examples)

1. Pass‑by‑Value

PROCEDURE Increment(x)               // x is passed by value
    x ← x + 1
END PROCEDURE

CALL Increment(a)                    // a is unchanged after the call

2. Pass‑by‑Reference

PROCEDURE Increment(REF x)           // x is a reference to the caller’s variable
    x ← x + 1
END PROCEDURE

CALL Increment(a)                    // a is now increased by 1

3. Pass‑by‑Value‑Result (Copy‑In / Copy‑Out)

PROCEDURE Swap(VALRES a, VALRES b)   // Cambridge uses VALRES for this mode
    temp ← a
    a ← b
    b ← temp
END PROCEDURE

CALL Swap(x, y)                      // x and y are swapped after the call

4. Output Parameters (alternative to a function)

PROCEDURE GetMinMax(arr, OUT min, OUT max)
    min ← arr[1]
    max ← arr[1]
    FOR i FROM 2 TO LENGTH(arr) DO
        IF arr[i] < min THEN min ← arr[i] END IF
        IF arr[i] > max THEN max ← arr[i] END IF
    END FOR
END PROCEDURE

CALL GetMinMax(data, low, high)      // low and high now hold the results

Scope and Lifetime (Illustrated)

INTEGER total ← 0                     // global variable

PROCEDURE AddToTotal(REF x)           // x is passed by reference
    INTEGER total ← 0                 // local variable shadows the global one
    total ← total + x                 // modifies the local copy only
    x ← x + 1                         // changes the caller’s variable
END PROCEDURE

CALL AddToTotal(total)                // global total remains 0 after the call

The local total exists only while AddToTotal is executing; the global total persists for the whole program.

Recursion Example (Factorial)

FUNCTION Factorial(n: INTEGER) RETURNS INTEGER
    IF n = 0 THEN
        RETURN 1
    ELSE
        RETURN n * Factorial(n - 1)
    END IF
END FUNCTION

Mathematical definition:

$$\text{factorial}(n)=\begin{cases} 1, & n = 0\\[2mm] n \times \text{factorial}(n-1), & n > 0 \end{cases}$$

When drawing a flowchart, show the call stack growing with each recursive call and shrinking as returns occur.

Efficiency Considerations (Exam‑Relevant)

Prefer functions for pure calculations – they avoid side‑effects and simplify reasoning.
Limit the use of global variables; they increase memory usage and can cause hidden dependencies.
If recursion is required, check whether a tail‑recursive formulation is possible – it can be transformed into an iterative solution with O(1) stack space.
Choose the most appropriate parameter‑passing mode:
- Use PASS‑BY‑VALUE** for read‑only data.
- Use REF only when the routine must modify the caller’s variable.
- Use OUT parameters for procedures that need to return multiple results.
Avoid unnecessary copying of large data structures; pass them by reference or as CONST REF if the language permits.

Benefits of Structured Programming

Improved readability and maintainability.
Easier debugging through isolated modules.
Facilitates code reuse via procedures and functions.
Supports top‑down design and stepwise refinement.

Common Mistakes to Avoid

Confusing procedures with functions – only functions return a value.
Over‑using global variables – reduces modularity and can cause side‑effects.
Choosing the wrong parameter‑passing mode – e.g., pass‑by‑value when the routine must modify the argument.
Omitting a RETURN statement in a function – leads to undefined behaviour.
Writing recursive routines without a reachable base case – results in infinite recursion.

1. Information Representation

Binary, Hexadecimal & Decimal

Binary (base‑2) – the fundamental representation used by computers.
Hexadecimal (base‑16) – a convenient shorthand for binary (4 bits per hex digit).
Two’s‑complement – method for representing signed integers.

Worked Conversions

Binary → Decimal
101101₂ = 1·2⁵ + 0·2⁴ + 1·2³ + 1·2² + 0·2¹ + 1·2⁰
          = 32 + 0 + 8 + 4 + 0 + 1 = 45₁₀

Hex → Binary
A3₁₆ = 1010 0011₂

Two’s‑complement (8‑bit) – find –23₁₀
23₁₀ = 0001 0111₂
Invert bits → 1110 1000₂
Add 1 → 1110 1001₂ = –23₁₀

BCD (Binary‑Coded Decimal)

Each decimal digit is stored as its own 4‑bit binary value.

Decimal 79 → BCD 0111 1001

Character Encoding

ASCII – 7‑bit code for 128 characters (e.g. ‘A’ = 01000001₂).
Unicode (UTF‑8) – variable‑length encoding that can represent every character in the world; backward compatible with ASCII.

Simple Compression – Run‑Length Encoding (RLE)

RLE replaces consecutive identical symbols with a count and the symbol.

Bitmap row: 111100001111
RLE output: (4,1) (4,0) (4,1)

Useful for teaching the idea of lossless compression (AO1).

2. Communication – Basic Networking

Network Types & Topologies

Type	Description
LAN (Local Area Network)	Small geographic area; usually Ethernet.
WAN (Wide Area Network)	Spans cities/countries; uses routers and public links.
Client‑Server	Dedicated server provides services to multiple clients.
Peer‑to‑Peer	All nodes can act as client and server.

Common Topologies

Star – all devices connect to a central hub/switch.
Bus – all devices share a single communication line (rare today).
Ring – each device connects to two neighbours; token passing controls access.
Mesh – multiple redundant paths; high reliability.

Physical Layer Basics

Ethernet – CSMA‑CD (Carrier Sense Multiple Access with Collision Detection).
Wi‑Fi – CSMA‑CA (Collision Avoidance) on the radio spectrum.

IP Addressing

IPv4 – 32‑bit address written as four decimal octets (e.g. 192.168.1.10).
Subnet mask – determines the network and host portions (e.g. 255.255.255.0).
IPv6 – 128‑bit address written in hexadecimal groups (e.g. 2001:0db8:85a3::8a2e:0370:7334).

Simple Subnetting Example

Network: 192.168.0.0 /24
Subnet mask: 255.255.255.192  ( /26 )
Resulting subnets:
  192.168.0.0 – 192.168.0.63
  192.168.0.64 – 192.168.0.127
  192.168.0.128 – 192.168.0.191
  192.168.0.192 – 192.168.0.255

Domain Name System (DNS)

Translates a domain name (e.g. www.cambridge.org) into an IP address.

Common Protocols (Table)

Protocol	Layer (OSI)	Purpose
HTTP	Application	Web page transfer
HTTPS	Application	Secure web transfer (TLS)
FTP	Application	File transfer
SMTP	Application	Email delivery
TCP	Transport	Connection‑oriented, reliable
UDP	Transport	Connection‑less, low‑latency
IP	Network	Routing of packets
ARP	Link	Map IP to MAC address

3. Hardware – Core Components & Logic Gates

Von Neumann Architecture

Single memory stores both data and instructions.
CPU fetches an instruction, decodes it, executes it, then repeats.

CPU Registers (simplified)

Register	Purpose
PC (Program Counter)	Address of next instruction.
IR (Instruction Register)	Holds the current instruction.
ACC (Accumulator)	Primary arithmetic/logic operand.
MAR (Memory Address Register)	Address of memory location to be accessed.
MDR (Memory Data Register)	Data being transferred to/from memory.
IX (Index Register)	Used for indexed addressing.

Fetch‑Execute Cycle (step‑by‑step)

1. MAR ← PC                // fetch address
2. MDR ← MEMORY[MAR]       // fetch instruction
3. IR  ← MDR               // decode
4. PC  ← PC + 1            // point to next instruction
5. Execute instruction in IR (e.g. ADD, LOAD, STORE)
6. Repeat

Logic Gate Symbols (required for AO1)

AND, OR, NOT, NAND, NOR, XOR, XNOR

Half‑Adder Example

SUM  = A XOR B
CARRY = A AND B

Students should be able to draw the gate diagram and produce the truth table.

4. Processor Fundamentals – Assembly & Bit Manipulation

Simple Assembly Language (generic)

Typical instruction format: OPCODE DEST, SOURCE

Sample Program (adds two numbers stored in memory)

        LOAD   ACC, NUM1      ; ACC ← NUM1
        ADD    ACC, NUM2      ; ACC ← ACC + NUM2
        STORE  RESULT, ACC    ; RESULT ← ACC
        HALT
NUM1    WORD   15
NUM2    WORD   27
RESULT  WORD   0

Two‑Pass Assembler Overview

Pass 1 – Scan source, build symbol table, assign addresses.
Pass 2 – Generate object code using the symbol table.

Addressing Modes (brief)

Immediate – operand is a constant (e.g. ADD ACC, #5).
Direct – operand is a memory address (e.g. LOAD ACC, VAR).
Indirect – address is stored in a register or memory location.
Indexed – base address + index register (useful for arrays).

Bit‑Manipulation Techniques

Masking – AND with a pattern to isolate bits.
lowByte ← value AND 0xFF
Setting a bit – OR with a mask.
value ← value OR 0b00001000 // set bit 3
Clearing a bit – AND with the complement of a mask.
value ← value AND NOT 0b00001000 // clear bit 3
Shifting – SHL (left shift) multiplies by 2ⁿ; SHR (right shift) divides (integer division).

5. System Software – Operating Systems & Language Translators

Operating‑System Functions (AO1)

Process management – creation, scheduling, termination.
Memory management – allocation, paging, segmentation.
File system – storage, retrieval, directory structure.
I/O control – drivers, buffering, interrupt handling.
Security – authentication, access control.

Language Translators

Translator	Purpose
Assembler	Converts assembly language to machine code.
Compiler	Translates a high‑level language to machine code (or intermediate code) in one step.
Interpreter	Executes high‑level code line‑by‑line; no separate machine‑code file.
Linker	Combines object modules into a single executable.
Loader	Places the executable into memory for execution.

Integrated Development Environment (IDE)

An IDE bundles a code editor, compiler/interpreter, debugger, and often a visual designer. It supports the software development life‑cycle (design, implement, test, debug, maintain) – a key point for AO3 (design & evaluate).

Simple Error‑Signalling Convention (used in exams)

PROCEDURE Divide(a, b, OUT result, OUT status)
    IF b = 0 THEN
        status ← -1          // error code: division by zero
        result ← 0
    ELSE
        result ← a / b
        status ← 0           // success
    END IF
END PROCEDURE

Students can test status after the call to decide whether to continue.

Summary Checklist for the Exam

Define and differentiate procedures and functions.
Write correct Cambridge‑style pseudocode for definitions, calls, and returns.
Identify the appropriate parameter‑passing mode and justify the choice.
Explain scope and lifetime of variables.
Design a simple recursive function with a clear base case.
Convert between binary, decimal, hexadecimal and two’s‑complement.
State the purpose of common network protocols and describe basic IP addressing.
Sketch the fetch‑execute cycle and label key CPU registers.
Write a short assembly fragment and explain its effect.
List at least three OS functions and three types of language translators.

Use the terminology associated with procedures and functions