# Church Basics: Exercises

## Calling functions

Church is a variant of the functional programming language Scheme.

You call functions like this:

(function arg1 arg2 arg3)

For example, (+ 1 2) would return 3. Try running it:

(A) Write the computation $3 \times 4$ in Church (* is the multiplication function).

(B) Write the computation $3 \times (4 + 6)$ in Church (make sure the result is 30).

(C) Write the computation $3 \times [4+ (6/7)]$ in Church (make sure the result is $\approx$ 14.57)

(D) Write the computation $3 \times [4+ (6/7)^2]$ in Church. The Church function (expt a b) will give you $a^b$. See here for a list of available Church functions (be warned that this list is slightly obsolete). Make sure the result is $\approx$ 14.20.

(E) Convert this Church expression into an arithmetic expression:

(F) Convert this Church expression to an arithmetic expression:

Note the particular indentation style (called pretty-printing). To clarify the structure of a function call, the arguments can split up across different lines but kept vertically aligned:

(+ (* 3
(+ (* 2 4)
(+ 3 5)))
(+ (- 10 7)
6))


The online editor will automatically pretty-print for you. If for some reason it screws up, you can manually indent according to this style by pressing the TAB key.

(G) Why doesn't this code work?

Some functions in Church can take an arbitrary number of arguments. For instance, + can take just 1 argument:

or 2 arguments:

or 15 arguments:

Such functions are called variadic functions.

## Defining variables and functions

You can use (define <variable> <value>) to define variables, e.g.:

(define x 3)
x


Note that in current versions of Church, your program always needs to return something. (define ...) doesn't return anything, so code that only has defines will result in an error (try running it to see):

We could fix this problem by just returning a symbol, 'foo at the end:

In Church, symbols are things preceded by a single quotation mark; they're kind of like strings.

There are two ways to define functions in Scheme, the short way and the long way. They look like this:

The short way has this basic form:

(define (<name> <argument-name-1> <argument-name-2> ...) <whatever function does to arguments>)

Note that the short way looks similar to function application, except that we surround it within a define statement to give meaning to this particular function application.

The long way has this basic form:

(define <name> (lambda (<argument-name-1> <argument-name-2> ...) <whatever function does to arguments>))

Note that the long way looks like we're defining a variable, except that the value of this variable is given by the special form (lambda (...) ...). This lambda object is the actual function and you can in fact use it to define functions that don't have names associated with them, so-called anonymous functions (you will see an examples of this in the section below on Map and Fold).

(A) Using the short way, write a function $f(x, y) = (x + y)^{x - y}$ and use it to compute $f(5,3)$:

Now fill in the blank for defining $f$ the long way; make sure that you get the same answer for $f(5,3)$

(B) Below, we have already defined $h(x,y) = x + 2y$. Using the short way, write a function $g(x, y, z) = x - y \times z$ and use it to compute $g(1, 4, h(6,3))$.

Now define $g$ using the long way; make sure that you get the same answer for $g(1, 4, h(6, 3))$

(C) The (if <condition> <true-clause> <false-clause> ) special form is used for if-else statements. For instance, it's used below to define a function that returns yes if the first argument is bigger than the second and no otherwise.

In Church, the Boolean values true and false are represented by #t and #f (so (> 5 1) would return #t and (> 5 7) would return #f).

What does the function below do?

(D) Scheme and Church are functional programming languages, so functions have a special place in these languages. Speaking very loosely, if you think of variables as nouns and functions as verbs, functional programming languages blur the noun-verb distinction. A consequence of this is that you can treat functions like regular old variables. For instance, in the function below, there are three arguments - thing1, thing2, and thing3. thing1 is assumed to be a function and it gets applied to thing2 and thing3:

Write a function, f, that takes three arguments, g, x, and y. Assume that g is a function of two variables and define f so that it returns 'yes if $g(x,y) > x + y$, otherwise 'no. Use it to compute $f(\times, 2.6, 1.2)$.

(E) In the previous problem, we defined f as a function that takes in a function as one of its arguments. Here, we are going to define a different sort of function, one that takes in normal values as arguments but returns a function.

You can think of this function as a "factory". You hand this factory a number, num, and the factory hands you back a machine. This machine is itself a function that takes an number, x, and tells you whether x is larger than num.

Without running any code, compute ((bigger-than-factory 5) 4) and ((bigger-than-factory -1) 7).

The functions we've defined in parts (D) and (E) are called "higher order functions". A function $f$ is a higher order function if it satisfies at least one of the following:

• it take one or more functions as an input
• it outputs a function

(F) What does this function do?

## Pairs, lists, and apply

Two important data structures in Scheme/Church are pairs and lists. A pair is just a combination of two things, a head and a tail. In Church, if you already have x and y, you can combine them into a pair by calling (pair x y):

Observe that this code returns the result (3 . 9) - you can recognize a pair by the dot in the middle.

Lists are built out of pairs. In particular, a list is just a sequence of nested pairs whose last element is '() (pronounced "null"). So, this would be the list containing 'a, '6, 'b, 'c, 7, and 'd:

Of course, stringing together a bunch of pair statements gets tedious, so there is a shorthand - the list function:

An alternate way of specifying the above list is using the quote syntax:

(A) The following code tries to define a list but gives an error instead. Why?

(B) Using list syntax, write a list of the even numbers between 0 and 10 inclusive.

(C) Using quote syntax, write a list of the odd numbers between 1 and 9 inclusive.

Some useful functions on lists:

• (length lst) returns the number of items in a list.
• (null? lst) returns true if a list is empty, false otherwise
• (first lst) returns the first item of lst, while (rest lst) returns everything but the first item of lst. For convenience, second, third, fourth, fifth, sixth, and seventh are also defined.
• (append lst1 lst2 ...) will put lists together:

Note that append is a variadic function.

Lists can contain lists, e.g.:

This nesting property is useful because it allows us to represent hierarchical structure. Note that calling length on the above function would return 5 (not 7) - length only counts the top-level items. You can remove all the nesting from a list using the flatten function (so (length (flatten '( 1 2 3 (4.1 4.2 4.3) 5))) would return 7).

Sometimes, you'll want to call a variadic function, but you don't know how many arguments you will have in advance. In these cases, you can keep around a list of arguments and use apply to call the variadic function on that list. In other words, this:

(+ 1 2 3 4 5 6 7)

is equivalent to this:

(apply + '(1 2 3 4 5 6 7))

(D) Without running any code, guess the result of each expression below. Some of these expressions have intentional errors embedded - see if you can spot them.

(pair 1 (pair 'foo (pair 'bar '() ))

(pair (1 2))

(length '(1 2 3 (4 5 6) 7))

(append '(1 2 3) '(4 5) '( 7 (8 9) ))

(length (apple pear banana))

(equal? (pair 'a (pair 'b (pair 'c '() ))) (append '(a b) '(c)))

(equal? (pair 'd (pair 'e (pair 'f 'g))) '(d e f g))


Check your guesses by actually running the code. If you made any mistakes, explain why your initial guess was incorrect.

## Map and fold

Two common patterns for working with lists are called map and fold (fold also sometimes called reduce).

Map takes two arguments, a function, $f$ and a list, $\{x_1, x_2, x_3, \dots , x_n\}$ and returns a list with $f$ applied to every item of the list, or $\{ f(x_1), f(x_2), ..., f(x_n) \}$. In the example below, we map square (which squares numbers) over the first five natural numbers:

Fold takes three arguments, a function $f$, an initial value, $x_0$, and a list, $\{x_1, x_2, \dots, x_n\}$, and returns $f(x_n, \dots, f(x_3,f(x_2, f(x_1, x_0)))$. In the example below, we define a function that computes the product of a list:

Note the use of the anonymous function here - we don't care about using this function outside the context of the fold, so we can just use it anonymously.

(A) Write my-sum-squares using fold. This function should take in a list of numbers and return the sum of the squares of all those numbers. Use it on the list '(1 2 3 4 5)

(B) Write my-sum without using fold - use map and apply:

## Recursion

One benefit of functional programming languages is that they make it possible to elegantly and concisely write down interesting programs that would complicated and ugly to express in non-functional languages (if you have some time, it is well worth understanding the change counting example from SICP). Elegance and concision usually derive from recursion, i.e., expressing a problem in terms of a smaller subproblem.

Here is a very simple recursive function, one that computes the length of a list:

(A) How does my-length work?

(B) Below, my-max is intended to be a recursive function that returns the largest item in a list. Finish writing it and use it to compute the largest item in '(1 2 3 6 7 4 2 9 8 -5 0 12 3)

(C) Write a version of my-max using fold.