5.2 Introduction to Functional Programming

Functional programming has its basis in λ-calculus and involves a set of tenets, including the use of a primitive list data structure, discussed here.

5.2.1 Hallmarks of Functional Programming

In languages supporting a functional style of programming, functions are first-class entities (i.e., functions are treated as values) and often have types associated with them—just as one might associate the type int with a variable i in an imperative program. Recall that a first-class entity is an object that can be stored, passed as an argument, and returned as a value. Since all functions must return a value, there is no distinction between the terms subprogram, subroutine, procedure, and function in functional programming. (Typically, the distinction between a function and a procedure is that a function returns a value [e.g., ], while a procedure does not return a value and is typically evaluated for side effect [e.g., ].)¹ Recursion, rather than iteration, is the primary mechanism for repetition. Languages supporting functional programming often use automatic garbage collection and usually do not involve direct manipulation of pointers by the programmer. (Historically, languages supporting functional programming were considered languages for artificial intelligence, but this is no longer the case.)

5.2.2 Lambda Calculus

Functional programming is based on λ-calculus—a mathematical theory of functions and formal model for computation (equivalent to a Turing machine) developed by mathematician and logician Alonzo Church in 1928–1929 and published in 1932.² The λ-calculus is a language that is helpful in the study of programming languages. The following is the grammar of λ-calculus.

These three production rules correspond to an identifier, a function definition, and a function application (respectively, from top to bottom). Formally, this is called the untyped λ-calculus.

5.2.3 Lists in Functional Programming

Lists are the primitive, built-in data structure used in functional programming. All other data structures can be constructed from lists. A list is an ordered collection of items. (Contrast a list with a set, which is an unordered collection of unique items [i.e., without duplicates], or a bag, which is an unordered collection of items, possibly with duplicates.)

We need to cultivate the habit of thinking recursively and, in particular, specifying data structures recursively. Formally, a list is either empty or a pair of pointers: one to the head of the list and one to the tail of the list, which is also a list.

Conceptual Exercises for Section 5.2

Exercise 5.2.1 A fictitious language Q that supports functional programming contains the following production in its grammar to specify the syntax of its if construct:

The semantics of an expression generated using this rule in Q are as follows: If the value of the first expression (on the right-hand side) is true, return the value of the second expression (on the right-hand side). Otherwise, return the value of the third expression (on the right-hand side). In other words, the third expression on the right-hand side (the “else” part) is mandatory.

Why does language Q not permit the third expression on the right-hand side to be optional? In other words, why is the following production rule absent from the grammar of Q?

Exercise 5.2.2 Notice that there is no direct provision in the λ-calculus grammar for integers. Investigate the concept of Church Numerals and define the integers 0, 1, and 2 in λ-calculus. When done, define an increment function in λ-calculus, which adds one to its only argument and returns the result. Also, define addition and multiplication functions in λ-calculus, which adds and multiplies its two arguments and returns the result, respectively. You may only use the three production rules in λ-calculus to construct these numbers and functions.

Exercise 5.2.3 Write a simple expression in λ-calculus that creates an infinite loop.

1. This distinction may be a remnant of the Pascal programming language, which used the function and procedure lexemes in the definition of a function and a procedure, respectively.

2. Alonzo Church was Alan Turing’s PhD advisor at Princeton University from 1936 to 1938.