1 Introduction
1.1 Introduction to Programming Languages
Welcome to CMSC330. This course provides an introduction to the fundamental concepts of programming languages, with a strong emphasis on functional programming.
You have already encountered languages such as Java, C, and assembly. Today, a wide variety of programming languages are in use, including C++, Python, Ruby, JavaScript, Lisp, Scheme, Haskell, OCaml, and Racket. Although these languages differ substantially in syntax and programming style, most general-purpose programming languages are Turing complete. That is, they are capable of computing any function that can be computed by a Turing machine. Consequently, any computation that can be expressed in one general-purpose language can, in principle, be expressed in another. The primary distinctions among programming languages therefore concern not their computational power, but the ways in which programs are expressed, understood, and executed.
This course uses OCaml and Rust as vehicles for exploring these concepts. However, the ultimate goal is not mastery of any particular language, but a deeper understanding of how programs work and how to become a more effective programmer in any language, including those you may learn in the future.
The course is neither purely theoretical nor focused solely on programming details. Instead, it provides a conceptual framework for understanding how language constructs can be used effectively and how to design programs that are both correct and elegant.
By working with OCaml—a language that may be unfamiliar to you—you will learn to think beyond the syntax of any single language and to reason more carefully about program structure and behavior. The emphasis on functional programming is essential for learning how to write robust, reusable, composable, and elegant programs.
If you are still thinking, “I know how to solve this problem using Python. Why do I need to learn this unusual functional approach?”, I encourage you to read the following excerpt from Bret Victor’s The Future of Programming.
So the most dangerous thought that you can have as a creative person is to think that you know what you’re doing. Because once you think you know what you’re doing, you stop looking around for other ways of doing things. And you stop being able to see other ways of doing things. You become blind. You become like these guys over here, kind of coding along in binary. Someone shows them assembly language, somebody shows them Fortran, and they can’t even see it. It just goes right over their head. Because they know what they’re doing. They know what programming is. This is programming; that’s not programming. And so they totally miss out on this much more powerful way of thinking.
Many of the most influential ideas in modern programming languages are rooted in functional programming. This course will introduce you to a fresh and powerful way of thinking about software and offer you the opportunity to enjoy the process of building it.
1.2 Course Goals
Describe and compare features of different programming languages.
Understand fundamental concepts of programming languages.
Choose an appropriate language or style for a given task.
Write code that is clearer, shorter, more efficient, and less prone to bugs.
1.3 Course Activities
Different types of programming languages and their features.
- How languages are specified, including:
Syntax, which describes the structure of programs.
Semantics, which describes the meaning of programs.
- How languages are implemented, including:
Parsing using regular expressions and context-free grammars.
Key mechanisms such as closures, tail recursion, type checking, lazy evaluation, and garbage collection.
1.4 Topics Covered in the Course
Functional programming using OCaml.
Regular expressions and finite automata.
Context-free grammars and parsing techniques.
Lambda calculus and operational semantics.
Type checking, subtyping, and type Inference
Implementing language intrepreters
Rust and the idea of safe, zero-cost abstractions.
Scoping rules, type systems, parameter passing, and comparisons between language styles.