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—because it provides no guideline whatsoever as to how to construct programs—and misleading at worst—because it suggests any program is a good program.Also see my Science of Computation paper on the expressive power of programming languages, but note that this essay makes a different (though related) point. Working software engineers must design their products in a systematic way, and HtDP aims to discourage students from their "tinker until it works" habits and imbue them with a "design attitude" from the very beginning.

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—and sometimes not at all—with the design strategies used to construct the software.

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

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

Part I says that if numbers are considered atomic, the design knowledge comes from the problem domain—and it is typically expressed as a formula. Alternatively, if the problem statement organizes numbers into intervals or enumerations, the function’s body consists of cond expression that matches this organization. The first function simply calls the second one, however, and this second function is recursive. While this form of recursion could originate from the domain, it would then have to be explained to the student within the problem statement, because HtDP teaches design as understood in computing and Part I does not mention it. Something is really wrong here.

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."

(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) #i1.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)))

Figure 1: A world program to compute compound interest

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.