Goals of Programming
What is programming for?
Programming describes a computation so it can be done mechanically. There are two fundamental building blocks:
- Expressions compute values (e.g.,
pi *. r *. r) - Commands cause effects (e.g., assignment, input/output)
Programs should be:
- Correct — giving the right answers
- Efficient — giving answers quickly
- Modifiable — easy to change as requirements evolve
Programming-in-the-small vs in-the-large
Programming-in-the-small concerns writing code for simple, clearly defined tasks. Expressions describe mathematical formulae (this was the original contribution of FORTRAN, the FORmula TRANslator). Commands describe how control flows from one part of the program to the next.
Programming-in-the-large concerns joining large modules to solve complex, messy tasks. As we code layer upon layer, we need mechanisms for one part of the program to provide interfaces to other parts.
Modularity mechanisms
Three main approaches to modularity have emerged:
| Mechanism | Description |
|---|---|
| Modules | Encapsulate a body of code, allowing outside access only through a programmer-defined interface |
| Abstract Data Types (ADTs) | A simpler version of modules; implement a single concept (e.g., dates, floating-point numbers) |
| Object-Oriented Programming (OOP) | Classes define concepts and can inherit from other classes; operations can be specialised across a family of related classes; objects are instances holding data |
OCaml has a sophisticated module system that can do many of the same things as classes. OCaml also includes an object system, though it is less commonly used than its module system.
Why OCaml?
OCaml is chosen for this course because:
- Interactive: code can be tried immediately in a read-eval-print loop
- Flexible data types: a rich type system with type inference
- Safe: hides the underlying hardware — a program can abort but it cannot crash
- Mathematically tractable: programs can be designed and understood without thinking in detail about how the computer runs them
- Immutable by default: distinguishes naming something from updating memory
- Automatic memory management: manages storage for the programmer
OCaml occupies a sweet spot combining efficiency, expressiveness, and practicality. It descends from ML, the meta language of Robin Milner’s LCF proof assistant (1972). The modern OCaml emerged in 1996 and has since attracted significant commercial and academic use.
Correctness and efficiency
A correct program that runs too slowly is not useful. Conversely, a fast program that gives wrong answers is dangerous. Throughout this course, we study both:
- How to write programs whose correctness follows from their structure (recursion justified by mathematical induction)
- How to analyse and improve efficiency using Big O notation and techniques like tail recursion and reduction in strength