Menu

- Chapter 1 Distilled
- Introduction
- 1.1 - The Elements Of Programming
- Expressions
- Naming and the Environment
- Evaluating Combinations
- Defining New Functions
- The Substitution Model
- Exercises
- Predicates
- Conditional Expressions
- Example: Newton’s Method
- Functions as Black-Box Abstractions
- 1.2 - Procedures and the Processes They Generate
- Linear Recursion and Iteration
- Tree Recursion
- Orders of Growth
- Exponentiation
- Example: Testing For Primality
- 1.3 Higher Order Functions
- Project - Blackjack

- Chapter 2 Distilled
- Introduction
- Data Abstraction
- Everything From Nothing
- Abstractions In Clojure
- Clojure's Data Structures
- Data Abstraction, Revisited
- Escher
- Project - Escher
- Symbolic Data
- Representing Sets
- Huffman Encoding Trees
- Zippers

In general, programming languages impose restrictions on the ways in which computational elements can be manipulated. Elements with the fewest restrictions are said to have first-class status, an idea originally due to Christopher Strachey

Some of the “rights and privileges” of first-class elements are that they may be:

- Named by variables
- Passed as arguments to functions
- Returned as the results of functions
- Included in data structures

Lisps, unlike other common programming languages, awards functions full first-class status. This poses challenges for efficient implementation, but the resulting gain in expressive power is enormous.

The major implementation cost of first-class functions is that allowing functions to be returned as values requires reserving storage for a function’s free variables even while the function is not executing. In the Scheme implementation we will study in Section 4.1, these variables are stored in the function’s environment.

We have seen that functions are, in effect, abstractions that describe compound operations on numbers independent of the particular numbers. For example, when we write

```
(defn cube [x]
(* x x x))
```

we are not talking about the cube of a particular number, but rather about a method for obtaining the cube of any number. Of course we could get along without ever defining this function, by always writing expressions such as

```
(* 3 3 3)
(* x x x)
(* y y y)
```

and never mentioning cube explicitly. This would place us at a serious disadvantage, forcing us to work always at the level of the particular operations that happen to be primitives in the language (multiplication, in this case) rather than in terms of higher-level operations. Our programs would be able to compute cubes, but our language would lack the ability to express the concept of cubing. One of the things we should demand from a powerful programming language is the ability to build abstractions by assigning names to common patterns and then to work in terms of the abstractions directly. Functions provide this ability. This is why all but the most primitive programming languages include mechanisms for defining functions.

Yet even in numerical processing we will be severely limited in our
ability to create abstractions if we are restricted to functions whose parameters
must be numbers. Often the same programming pattern will
be used with a number of different functions. To express such patterns
as concepts, we will need to construct functions that can accept functions as
arguments or return functions as values. Functions that
manipulate functions are called *higher-order functions* .

Have a look at these two functions

```
(defn sum-integers [a b]
"compute the sum of the integers from a through b"
(if (> a b)
0
(+ a (sum-integers (inc a) b))))
```

```
(defn sum-cubes [a b]
"compute the sum of the cubes of the integers from a through b"
(if (> a b)
0
(+ (cube a)
(sum-cubes (inc a) b))))
```

These functions clearly share a common underlying pattern. They are for the most part identical, differing only in the name of the function, the function of a used to compute the term to be added .

We could generate each of the functions by filling in slots in the same template:

```
(defn <name> [a b]
(if (> a b)
0
(+ (<term> a)
(<name> (inc a) b))))
```

We would like our language to be powerful enough so that we can write a function that expresses the concept of summation itself rather than only functions that compute particular sums. We can do so readily by taking the common template shown above and transforming the 'term' slot into a formal parameter:

```
(defn sum-terms [term a b]
(if (> a b)
0
(+ (term a)
(sum-terms term (inc a) b))))
```

Notice we cannot `recur`

here as it is not in a tail position, trying
to do so helpfully throws

```
java.lang.UnsupportedOperationException: Can only recur from tail position
```

So we can us this to find the sum of the the first 10 cubes

```
> (sum-terms cube 1 10)
3025
```

Or the numbers 1 to 10

```
> (sum-terms identity 1 10)
55
```

`identity`

is a clojure built-in function that just returns whatever
you pass it

You can ask at the repl for the docs of a function

```
> (doc identity)
-------------------------
clojure.core/identity
([x])
Returns its argument.
nil
```

Or look at it's source, this comes in very handy

```
> (source identity)
(defn identity
"Returns its argument."
{:added "1.0"
:static true}
[x] x)
nil
```

Sometimes you only use a function once, and it is simple enough for it's purpose to be obvious without naming it, you can use an anonymous function

The function `square`

from before can be created with

```
(fn [x]
(* x x))
```

And can be called immediately

```
> ((fn [x] (* x x))
2)
4
```

Clojure even has a shorter form implemented as a reader macro

```
#(* % %)
```

For example to sum the first 10 squares we can

```
> (sum-terms #(* % %) 1 10)
385
```

If an anonymous function has more than one argument, they can be
referenced as `%N`

for each variable, eg

```
> (#(str %2 " " %1)
"arg1"
"arg2")
"arg2 arg1"
```

Take a look at this function

```
(defn adder [n]
(fn [m]
(+ m n)))
```

This function takes an argument `n`

and returns a function (using our anonymous
function syntax) that adds n to it's argument.

We can create a function `add-2`

```
> (def add-2 (adder 2))
#'user/add-2
> (add-2 11)
13
```

We can do things like create a function that takes a function and returns a function that calls it with it's arguments reversed

```
(defn flip [f]
(fn [x y]
(f y x)))
```

Take a look at `juxt`

and `complement`

, and try and create examples of their use.

Define a function double that takes a function of one argument as argument and
returns a function that applies the original function twice. For example, if
inc is a function that adds 1 to its argument, then
`(double inc)`

should be a function that adds 2. What
value is returned by

```
(((double (double double)) inc) 5)
```

Let f and g be two one-argument functions.

The *composition* of f and g, denoted $ f \circ g $ is defined to be the function

$$ x \rightarrow f(g(x)) $$

Define a function `compose`

that implements composition.

You should find that

```
> ((compose square inc) 6)
49
```

After you are done, take a peek at `(source comp)`

to see how clojure does it in
a variadic way

If f is a numerical function and n is a positive integer, then we can form the
n^{th} repeated application
of f , which is defined to be the function whose value at
x is

$$ f (f (\dots (f (x )) \dots )) $$

For example, if f is the function $ x \rightarrow x + 1 $
then the n^{th} repeated application of f is the
function $ x \rightarrow x+n $

If f is the operation of squaring a number, then the n^{th}
repeated application of f is the function

$$ x \rightarrow x^{2^n} $$

Write a function that takes as
inputs a function that computes f and a
positive integer n and returns the function that computes
the n^{th} repeated application of f . Your function should be
able to be used as follows:

```
=> ((repeated square 2) 5)
625
```