Functional Programming and Computation—Exploring the foundations of Computer Science (CS4110.01)

Darcy Otto

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.

Learning Outcomes:
-Grasp the Principles of Functional Programming: By the end of the course, you will be proficient in writing, debugging, and analyzing functional programs in Scheme, utilizing constructs like lambda functions, higher-order functions, and recursion.
-Understand Church's Account of Computation: You will work through Church’s paper on lambda functions, and be able to articulate the relationship between functions and computation, highlighting its significance for computational problems.
-Grapple with the Church-Turing Thesis: You will consider, critique, and form perspectives on the Church-Turing Thesis, appreciating its pivotal role in bridging the realms of Computer Science, Mathematics, and Logic.
-Connect Functional Programming to Computation: You will draw connections between specific programming constructs (such as fixed-point combinators) and overarching theories of computation, emphasizing the relationship between theory and practice.

Delivery Method: Fully in-person
Prerequisites: At least one course in Computer Science or Mathematics. Interested students should contact Michael Corey ( for registration.
Course Level: 4000-level
Credits: 4
M/Th 1:40PM - 3:30PM (Full-term)
Maximum Enrollment: 20
Course Frequency: Every 2-3 years

Categories: 4000 , All courses , Computer Science , Four Credit , Fully In-Person , New Courses , Updates