CSCI 3055U: Programming Languages
1 Introduction to the course
This course is an introduction to the development, theories and principles of programming languages. Through a survey of the historic development of programming languages, we will gain a deeper understanding of the design of modern programming paradigms.
By the end of the course, students should have improved proficiency in programming by choosing the most suitable language and language features for the job.
2 Course Outline
2.1 Part I: Theory of Computation
2.1.1 History of computation
We will cover the historic development of computation, both in terms of the formalisms of computation and the practical systems and languages of computation. We will introduce Turing Machine and \(\lambda\)-Calculus as the foundations of computation, and demonstrate how they can be used to solve problems. Finally, we will examine the limitations of computation by demonstrating the existence of non-computable problems.
2.1.2 Programming with Lambda Calculus
Lambda Calculus (LC) is the foundation of functional programming. We will cover the expressive power of LC by enumerating through the standard programming constructs using the primitive rules of LC. In particular, we will cover:
- integer arithmetics
- boolean logic
- iteration and recursion
- list based data structures
2.2 Part II: Functional Programming
2.3 Lisp
Lisp is a natural syntax for LC. We examine the Lisp programming language through its syntactic simplicity and its runtime environment. In particular, we will focus on the unique features of Lisp, namely treating code as data, and the macro system.
2.4 Clojure
We pick Clojure as the primary functional language as it is a Lisp dialect while being able to interface with Java and JVM natively. We will discuss Clojure in detail:
- data description in Clojure
- general programming with recursion and higher order functions
- data pipelines in Clojure
- macros
2.5 Part III: Type Systems
2.5.1 Types
We will introduce type systems by examining its role in static analysis. We will examine the basic elements of a type system:
- primitive types
- composite types and functional signatures
- generics and polymorphism
We will also study the standard algorithms for type checking and type inference using unification.
2.5.2 Kotlin / Scala
Elements of Kotlin and Scala will be used to demonstrate the elements of a strongly typed object oriented programming language (OOP). Both Kotlin and Scala emphasize to be pure OOP langauges, and thus they have subtle differences from Java. Many advanced programming patterns in Kotlin and Scala rely on such pure OOP design of the language.