Function - Study Notes

Chapter Summary

Subroutines, also known as functions, are the fundamental building blocks of computer programs. They are small, modular sections of code designed to perform specific tasks repeatedly, which improves code reusability and program structure. A function defines a mapping from inputs to a concrete output, binding values to names. In function specification, parameters act as placeholders in the function definition, while arguments are the actual values passed during execution. Functions can be pure (deterministic and free of side effects) or impure (dependent on or modifying external state).

Learning Objectives

• Explain the concept of function specifications, parameters, and arguments.
• Distinguish between interface and implementation in program design.
• Identify pure and impure functions and explain the nature of side effects.
• Analyze recursive functions using real-world algorithmic examples.

Key Concepts and Definitions

• Function: A unit of code that is defined within a larger code structure, containing statements that process inputs and produce a concrete output.
• Subroutine: A reusable block of code that performs a specific sub-task within a program.
• Parameter: A variable listed in a function's definition that acts as a placeholder for data.
• Argument: The concrete value passed to a parameter during a function call.
• Interface: A description of what an object or class can do without describing how it does it.
• Implementation: The internal instructions and logic that carry out the actions defined by the interface.
• Pure Function: A function that always yields the exact same result for the same arguments and causes zero side effects.
• Impure Function: A function whose return value depends on external state or modifies external variables, leading to side effects.
• Side Effect: An interaction with the outside world, such as modifying a global variable or external memory.
• Recursive Function: A function definition that calls itself to solve smaller instances of the same problem.

Worked Methods

Recursive Exponentiation

Calculating the power of a number is defined recursively by reducing the exponent. The method is defined as:

let rec pow (a: int) (b: int) : int := if b = 0 then 1 else a * pow a (b - 1)

For any base 'a' and exponent 'b' (where 'b' is greater than or equal to 0), the function multiplies 'a' by the result of the function called with the exponent decreased by 1, until the base case of exponent 0 returns 1.

Greatest Common Divisor (GCD)

The greatest common divisor of two integers can be recursively computed using the Euclidean algorithm:

let rec gcd a b := if b != 0 then gcd b (a mod b) else return a

This function recursively calls itself, passing 'b' as the new 'a' and 'a mod b' as the new 'b', until 'b' is 0, at which point 'a' is returned as the GCD.

Common Exam Traps

• Parameters vs. Arguments: Do not use these terms interchangeably on exams. Remember that parameters are defined in the function signature, while arguments are passed in during the function call.
• Type Annotation Syntax: When writing explicit type annotations, parentheses are mandatory around the parameters (e.g., (x: int)). Omitting them leads to syntax errors.
• Infinite Recursion: Every recursive function must have a clearly defined base case. Failing to specify a base case or setting an unreachable base condition causes infinite loops and recursion limit errors.
• Impure State Tracking: If a function accesses or modifies a variable defined outside its block (such as a global accumulator), it is impure even if it returns a value.

Exam Tips

• Understand that classes act as the interface, while the processed objects serve as the implementation.
• Use the let rec keyword combo when defining a recursive function, and just let for standard ones.
• Memorize the function type signature syntax: x -> y means input type is x and output type is y.