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

(Ex 4.15 in the book)

Given a one-argument procedure `p`

and an object `a`

, `p`

is said to “halt” on `a`

if evaluating the expression `(p a)`

returns a value (as opposed to terminating with an error message or running forever).

Can you see it is impossible to write a procedure `halts?`

that correctly determines whether `p`

halts on `a`

for any procedure `p`

and object `a`

.

If you had such a procedure, you could implement:

```
(defn run-forever
(run-forever))
(defn (try p)
(if (halts? p p)
(run-forever)
'halted))
```

and now think about running `(try try)`

and show that any possible outcome (either halting or running forever) violates the intended behaviour of `halts?`

Although we stipulated that halts? is given a procedure object, notice that this reasoning still applies even if halts? can gain access to the procedure’s text and its environment. This is Turing’s celebrated Halting Theorem, which gave the first clear example of a non-computable problem, i.e., a well-posed task that cannot be carried out as a computational procedure.