### Turing is Useless

Sep 14, 2014

HtDP aims for a paradigm shift in the teaching of programming. While traditional texts introduce the expressive power of the chosen programming language, HtDP presents systematic design strategies. Its exercises do not ask students to practice the use of some linguistic features but to apply design strategies. Put differently, HtDP ignores the expressive power of programming languages in favor of the constructive power of its design strategies. This idea deserves a close look, from instructors as well as students.

The Church-Turing thesis proclaims that all programming language have the same
expressive power. Mathematically speaking, Church and Turing say that
programming languages can express the partial recursive functions (on natural
numbers) and nothing else. A related theorem says that every partial recursion
function is expressible in an infinite number of ways in every programming
language. Pragmatically speaking, the thesis is completely useless at
best—

#### 1` `Traditional Texts

Traditional programming texts tend to follow a uniform strategy. Each part
introduces another some linguistic mechanisms of a language, explaining their
syntax and semantics. It then presents some sample problems that are best solved
with these new mechanisms. The exercises ask students to solve a range of
similar problems. For the early parts of a book, students can solve such
exercises with a copy-and-edit approach. In later parts, exercises may ask
students to show some creative spark. When such books propose projects, the
evaluation is often concerned with the visible creativity of the software
product, occasionally with the creativeness of coding, but barely—

Instructors know, and students often sense, that after some point, the programming language can express the same functions a Turing machine can compute. At that point, instructors of introductory programming courses can assign any problem they want. If it accidentally falls outside of the range of problems that the book has used and students have seen, they call those students who solve it "creative," and they tell the others that they will get it too, sooner or later.

#### 2` `HtDP

Unlike traditional texts, HtDP focuses on design strategies. For the first conceptual half, the design strategies are data-oriented. Starting from atomic data, e.g. booleans, chars, numbers, and strings, this half deals with intervals, enumerations, structures, and arbitrary unions until it reaches mutually referential nests of descriptions of data. For the conceptual second half, it deals with design strategies for abstraction, generative recursion, and the addition of design attributes, e.g., accumulators and state (edition 1).

HtDP introduces a new linguistic construct only in support of a design strategy or when the available language lacks expressive power. For example, the language of first-order recursive functions, enriched with structure definitions, completely suffices to deal with the data-oriented design strategies. To deal with abstraction properly, however, the chosen programming language needs functions as values. Similarly, if programmers wish to distinguish constants from variables, the programming language needs to support local definitions.

At first glance HtDP suffers from the same problem as the traditional approach.With an expressive type system for its teaching languages, HtDP could avoid this problem to some extent, but adding such rich types would also take the fun out of programming. Indeed, the language of first-order functions on numbers is introduced on the very first pages and an inspired student or instructor can easily find out that this language admits recursive functions. The fundamental difference is that HtDP explicitly offers an alternative to the usual way of writing "exercises that students ought to be able to solve with this language."

#### 3` `Instructors New To HtDP

to teach systematic design

the series of design recipes and the various design guidelines.

Using HtDP thus requires a different kind of effort from the instructors than traditional texts. In a traditional setting, an instructor switches from a text from a passé language to one that uses the latest teeange-heartbreak toy with total ease; he just uses the new syntax for the old problems. HtDP not only introduces book-specific teaching languages, it also wishes instructors to know how to solve each homework and exam problem with the design recipes available up to a certain section. Without writing solutions first, it is almost impossible to achieve this goal. As with everything else, this process eventually turns the design-first idea into an acquired trait, that is, the idea becomes second nature and instructors can "cruise" again.

The remaining sections illustrate this paradigm shift with some examples.

#### 4` `Part I: Why No Recursion

Design the function double-at-rate, which computes how many months it takes to double a given amount of money when a savings account pay a certain monthly interest rate.

; Number -> Number ; computes the number of months it takes to double ; a dollar at given interest-rate (check-expect (double-at-rate 1.0) 1) (define (double-at-rate interest-rate) (double (+ 1.0 interest-rate) 1.0)) ; Number Number -> Number ; computes the number of months it takes to double ; a dollar at given compounding factor c ; assume the initial value of current is 1.0 (check-expect (double 2.0 1.0) 1) (define (double c current) (cond [(>= current 2.0) 0] [else (add1 (double c (* c current)))]))

The function is to consume a plain number and produce one. Also, the problem statement does not mention anything concerning a partitioning of the number line.

The solution consists of two functions, even though the problem statement calls for one.

A moment’s reflection explains why it is difficult to create a one-function solution in BSL if the function is to implement the specified signature.

The functions produce a number, but we actually know that it is a "counting number," that is, a natural number.

The second function is expected to be supplied 1.0 as the second argument. If we know that, why is current an argument at all?

The second function refers to itself, something that does not come up at all in Part I.

Part I says that if numbers are considered atomic, the design knowledge comes
from the problem domain—

Plainly put, this problem falls completely out of scope for Part I.

A student who solves this problem should not receive (much) credit because at that point the solution uses "garage programming." The term is due to Fred Brooks. Conversely, the student does not understand why this design is appropriate and what the design misses. All of this becomes clear only once the course has covered the rest of the book.

Now assume the instructor finishes studying the entire text book. At that point, he would understand two points. First, the second function ought to be defined using the local expressions from Part III; doing so guarantees that the second argument is always 1.0. Second, the second function employs generative recursion, as found in Part V, and it should therefore come with a "termination argument."

; Number -> NaturalNumber ; computes the number of months it takes to double ; a dollar at the given interest-rate ; generative add the interest paid for the next period ; terminates if (> interest+principal 1.0) holds (check-expect (calculate (/ 0.06 12)) 139) (define (double-at-rate interest-rate) (local ((define c (+ 1.0 interest-rate)) ; Number -> Nat (define (double current) (cond [(>= current 2.0) 0] [else (add1 (double (* current c)))]))) (double 1.0)))

(require 2htdp/universe) (require 2htdp/image) (define-struct interest (rate current months)) ; Interest is (make-interest Number Number Number) ; INTERPRETATION (make-interest c r m) says that after m months ; one dollar has grown to c dollars when the compound rate is r ; Use clock ticks to simulate the passage of a month. ; Stop when the amount in the world structure has doubled. ; Number -> Number ; computes the number of months it takes to double ; a dollar at the given interest-rate (check-expect (double-at-rate-world (/ 0.06 12)) 139) (define (double-at-rate-world interest-rate) (interest-months (big-bang (make-interest (+ 1.0 interest-rate) 1.0 0) (on-tick compound) (to-draw show) (stop-when doubled?)))) ; Interest -> Interest ; pay one monthe worth of interest (check-expect (compound (make-interest 1.06 1.0 0)) (make-interest 1.06 1.06 1)) (check-expect (compound (make-interest 1.06 1.06 0)) (make-interest 1.06 (* 1.06 1.06) 1)) (define (compound i) (make-interest (interest-rate i) (* (interest-current i) (interest-rate i)) (add1 (interest-months i)))) ; Interest -> Boolean ; is current greater or equal to 2.0 (check-expect (doubled? (make-interest 1.06 1.0 0)) #false) (check-expect (doubled? (make-interest 1.06 2.0 10)) #true) (define (doubled? i) (>= (interest-current i) 2.0)) ; Interest -> Image ; show the current value of i as a text image (define (show i) (overlay (text (number->string (interest-current i)) 22 "blue") (square 500 'solid 'white)))

An imaginative student may design a world program to solve this problem. Figure 1 shows such a solution. If the student follows the program design recipe for worlds and the function design recipe for the clock tick handler, the solution deserves nearly full credit. The instructor should still challenge the student to justify the inclusion of (1) the number of months in the data representation of the world and (2) the inclusion of the compound rate. The former is justified because the number of months change as the world program runs.It is also an instance of the "accumulator in the data structure" idea discussed in Part VI but it is always justified by the world design recipe. The latter is necessary because the interest rate is an argument of double-at-rate-world and only then becomes a world-wide constant; see the introduction of local for an explanation.