Why study programming languages

By the third year of a computing degree you have written programs in several languages: Python in CMPUT-174, C in CMPUT-201, and a mixture of Python, Java, Rust, Go and JavaScript in CMPUT-274. Each time, you learned a language by using it. This course takes a different view. Instead of learning yet another language, we study languages themselves: how their syntax is described, how their meaning can be defined precisely, how names and scopes work, what types guarantee, how evaluation order changes behaviour, how memory is managed, and how all of this is implemented. By the end you will have written several small interpreters and a type checker, and you will be able to read a language specification the way an engineer reads a blueprint.

CMPUT-274 asked 'which paradigm fits this problem?' and showed functional, object-oriented, concurrent and logic styles from a programmer's seat. Here we move to the designer's and implementer's seat. The questions become: what exactly does this construct mean, how would I implement it, what would go wrong if I changed it, and how can I prove it does what I claim? CMPUT-272 supplies the logic and induction we lean on for proofs. Two later courses go further: CMPUT-415 builds a complete compiler with industrial parsing and code generation, and CMPUT-474 studies the theory of computation, including what no language can decide.

Why learn about languages rather than just a language?

There are practical reasons. Programmers who understand how features are implemented choose them more wisely: they know why a recursive function in Python can overflow the stack while the same function in Scheme cannot, why a Java generic cannot be instantiated with int, and why Rust refuses code that C would happily compile. Understanding languages also makes new ones easy to learn. Rust's traits, Swift's protocols and Haskell's type classes are variations on one idea; once you know the idea, each new syntax is a small step.

There are also reasons that go beyond using languages. A surprising amount of everyday software is a language implementation in disguise: configuration formats, query languages, template engines, spreadsheet formulas, build files, regular expressions and the rules engines used in insurance and payroll systems. Every one of them needs a grammar, a parser, an evaluator and good error messages. Engineers who can design a small, clean domain-specific language often replace thousands of lines of fragile code with a few dozen lines of readable rules. Finally, language design is where many of the deepest ideas in computing meet: logic, mathematics, human factors and hardware.

Criteria for judging a language

Robert Sebesta's widely used textbook groups language evaluation criteria under readability, writability, reliability and cost, and the categories remain useful. Readability asks how easily a program can be understood, which depends on simplicity (few ways to say the same thing), orthogonality (features combine without surprising exceptions), sensible data types and clear syntax. Writability asks how easily a program can be created, which depends on expressiveness and abstraction. Reliability asks whether programs behave as intended, which depends on type checking, exception handling and the absence of dangerous aliasing. Cost covers training programmers, writing and compiling programs, running them, and maintaining them for decades.

These criteria often conflict. C is highly writable and fast but less reliable, because array bounds and memory lifetimes are left to the programmer. Ada and Rust are more reliable but take longer to learn. Perl's slogan 'there's more than one way to do it' helps writability but can hurt readability, while Python's guiding principle that 'there should be one obvious way to do it' pushes the other way. A language designer is always choosing which costs to pay.

# Orthogonality: can features be combined freely?  Two small probes in Python.
# 1. Functions are values, so they can go anywhere a value can.
fs = [abs, len, str.upper]
print([f(x) for f, x in zip(fs, [-3, "abc", "hi"])])

# 2. But statements are not expressions: 'if' cannot appear where a value is expected,
#    so Python adds a second, expression-only form.
x = 7
parity = "odd" if x % 2 else "even"        # conditional expression
print(parity)

# 3. Assignment became an expression only in Python 3.8 (the walrus operator).
data = [3, 8, 1, 9]
if (m := max(data)) > 5:
    print("max is", m)

[3, 3, 'HI']
odd
max is 9

A brief history of language families

The first high-level languages appeared in the 1950s. Fortran (1957), designed at IBM by John Backus's team, showed that compiled code could be nearly as fast as hand-written assembly, and it is still used in weather and climate models. Lisp (1958), created by John McCarthy, introduced recursion as a central tool, garbage collection, and code that is itself data. COBOL (1959) brought English-like syntax to business data processing and still runs many banking and government systems. ALGOL 60 gave us block structure, lexical scope and the first language defined with a formal grammar, the Backus–Naur form we use in lesson 2.

The 1960s and 1970s split languages into families that remain recognizable today. Simula 67, from Norway, introduced classes and objects; Smalltalk at Xerox PARC made everything an object. C (1972) at Bell Labs gave systems programmers a portable language close to the machine. ML (1973) at Edinburgh brought polymorphic type inference, the topic of lesson 8, and Prolog (1972) from Marseille made logic a programming language, the topic of lesson 11. Later decades added C++ (1985), Haskell (1990, a pure lazy functional language designed by committee), Python (1991), Java and JavaScript (both 1995), C# (2000), Go (2009), Rust (2015 for version 1.0) and Kotlin and Swift in the 2010s.

The influences cross freely. Rust borrows algebraic data types and pattern matching from ML, traits from Haskell's type classes and syntax from C. JavaScript's first-class functions come from Scheme, a Lisp dialect, while its name and syntax came from Java for marketing reasons. Python's comprehensions come from Haskell and SETL. Studying the families helps you see that 'new' features are usually old ideas in new clothes.

The same computation in five languages

Here is one small computation, the sum of the squares of the odd numbers from 1 to 9, written in the styles you met in CMPUT-274. Every block below was compiled and run on this course's build machine, so the outputs are real. Observe how much of each program is about what to compute and how much is about how to compute it.

# Sum of the squares of the odd numbers from 1 to 9, written three ways in one language.
nums = range(1, 10)

# 1. imperative: a mutable accumulator and a loop
total = 0
for n in nums:
    if n % 2 == 1:
        total += n * n
print("imperative :", total)

# 2. functional: compose filter, map and a fold
from functools import reduce
print("functional :", reduce(lambda a, b: a + b, map(lambda n: n * n, filter(lambda n: n % 2, nums))))

# 3. declarative comprehension: say what, not how
print("declarative:", sum(n * n for n in nums if n % 2))

imperative : 165
functional : 165
declarative: 165

import java.util.stream.IntStream;

public class Squares {
    public static void main(String[] args) {
        int total = IntStream.rangeClosed(1, 9)
                             .filter(n -> n % 2 == 1)
                             .map(n -> n * n)
                             .sum();
        System.out.println("Java: " + total);
    }
}

Java: 165

fn main() {
    let total: i32 = (1..=9).filter(|n| n % 2 == 1).map(|n| n * n).sum();
    println!("Rust: {}", total);
}

Rust: 165

package main

import "fmt"

func main() {
	total := 0
	for n := 1; n <= 9; n++ {
		if n%2 == 1 {
			total += n * n
		}
	}
	fmt.Println("Go:", total)
}

Go: 165

const total = Array.from({length: 9}, (_, i) => i + 1)
  .filter(n => n % 2 === 1)
  .map(n => n * n)
  .reduce((a, b) => a + b, 0);
console.log("JavaScript:", total);

JavaScript: 165

All five print 165. The differences are in the abstractions each language offers and in what happens underneath. Python interprets bytecode, so its loop costs much more per step than Rust's, which the compiler reduces to a few machine instructions. Java compiles to bytecode for the Java virtual machine, which then compiles hot code to machine code while the program runs. JavaScript engines do something similar. Lesson 10 looks inside these runtime systems.

How languages are implemented

Language implementations fall along a spectrum. A compiler translates the whole program into another language, usually machine code, before it runs; C, C++, Rust and Go are typically compiled this way. An interpreter runs the program directly, reading and executing it step by step; early BASIC and shell scripts work like this. Most modern languages use a hybrid: the source is compiled to an intermediate form such as bytecode, which a virtual machine then interprets or compiles further. CPython, the standard Python, compiles to bytecode and interprets it. The Java virtual machine and JavaScript engines such as V8 interpret bytecode at first and use just-in-time compilers to translate frequently run code to machine code.

A language is not the same thing as its implementation. Python has CPython, PyPy (with a just-in-time compiler) and MicroPython for microcontrollers. Java can be compiled ahead of time with GraalVM native images. Being careful about this distinction matters: 'Python is slow' really means 'CPython running this program is slow'. In this course we write interpreters, because they show the meaning of a language most directly.

What it means to define a language

A complete language definition has several layers. Lexical syntax describes the words: identifiers, numbers, keywords and operators. Concrete syntax describes how words form phrases, usually with a grammar. Abstract syntax describes the essential tree structure of programs, without parentheses and semicolons. Static semantics describes the rules checked before running, such as scoping and typing. Dynamic semantics describes what programs do when they run. Pragmatics covers conventions, idioms and the standard library. Lessons 2 to 8 take these layers one at a time.

Definitions range from informal prose to fully mathematical. Most language standards, such as the ISO C standard and the Python Language Reference, are carefully written English. A few languages have formal definitions: Standard ML has a mathematical definition of both its static and dynamic semantics, and WebAssembly's specification is written with formal rules and has been mechanically checked in a proof assistant. Formal definitions remove ambiguity; the C standard's many cases of 'undefined behaviour', which compilers may treat in surprising ways, show what informality can cost.

# A first interpreter: a reverse Polish notation (postfix) calculator.
# The "language" has numbers and four operators; the "machine" is a stack.
def run_rpn(program):
    stack = []
    ops = {"+": lambda a, b: a + b, "-": lambda a, b: a - b,
           "*": lambda a, b: a * b, "/": lambda a, b: a / b}
    for token in program.split():
        if token in ops:
            b, a = stack.pop(), stack.pop()      # note the order: a op b
            stack.append(ops[token](a, b))
        else:
            stack.append(float(token))
        print(f"  {token:>3}  stack = {stack}")
    if len(stack) != 1:
        raise ValueError("malformed program")
    return stack[0]

print("3 4 + 2 * means (3 + 4) * 2")
print("result:", run_rpn("3 4 + 2 *"))

3 4 + 2 * means (3 + 4) * 2
    3  stack = [3.0]
    4  stack = [3.0, 4.0]
    +  stack = [7.0]
    2  stack = [7.0, 2.0]
    *  stack = [14.0]
result: 14.0

The postfix calculator above is a complete, if tiny, language implementation. Its lexical syntax is 'tokens separated by spaces'; its abstract syntax is just the sequence of tokens; its semantics is defined by the loop, which pushes numbers and applies operators to the top two stack entries. Postfix notation needs no parentheses or precedence rules, which is why stack machines such as the Java virtual machine, WebAssembly and CPython's bytecode interpreter use it internally. In lesson 2 we handle ordinary infix expressions, which need a grammar and a parser.

Worked examples