Functional Programming and Computation—Exploring the foundations of Computer Science

Course Description

Summary

What is computation?  This is the question that birthed Computer Science as a discipline, and serves as the focal point of this course.  Our plan for answering it is twofold.  First, we will introduce functional programming through Scheme (a dialect of Lisp).  Unlike imperative languages, functional programming tends to emphasize techniques such as lambda functions, higher-order functions, recursion, and the use of immutable data.  We will explore each of these techniques, and discover their significance in diverse contexts. Second, we will use our understanding of functional programming to explore the nature of computation itself.  This will involve reading parts of Alonzo Church’s revolutionary article, “An Unsolvable Problem of Elementary Number Theory.”  We will see how the notion of computation emerges from his understanding of functions, and engage with the fundamental conjecture of Computer Science: the Church-Turing Thesis. This course is interdisciplinary in nature: we shall be learning skills in Computer Science (functional programming); but we will also be using these skills to explore serious questions at the nexus of Computer Science, Mathematics, and Logic.  By the course’s end, you will understand the principles of functional programming, and their connection to computation.  Additionally, you will gain insight into the Church-Turing Thesis and its foundational role in the discipline of Computer Science. No previous experience in Computer Science, Mathematics, or Logic is necessary to take this course.  However, you will be programming in Scheme and reading challenging texts in theory of computation; so your learning will be well-supported by having already taken a course that emphasizes symbolic thinking.  For this reason, at least one course in Computer Science or Mathematics is a prerequisite. Topics include: function composition, higher-order functions, lambda functions, recursion, primitive recursive functions, mu-recursive functions, combinatorial logic, fixed-point combinators, the Church-Turing Thesis, computation. Evaluation will be based on active engagement, projects, and a comprehensive final examination.