▼How to Design Programs, Second Edition
►V Generative Recursion
On this page:
29 Designing Algorithms
30 Material for FSMs
    ← prev  up  next → 

V Generative Recursion

The functions we have developed so far fall into two broad categories. On one hand, we have the category of functions that encapsulate domain knowledge. On the other hand, we have functions that consume structured data. These functions typically decompose their arguments into their immediate structural components and then process those components. If one of the immediate components belongs to the same class of data as the input, the function is recursive. For that reason, we refer to these functions as (structurally) recursive functions. In some cases, however, we also need functions based on a different form of recursion, namely, generative recursion. The study of this form of recursion is as old as mathematics and is often called the study of algorithms.

The inputs of an algorithm represent a problem. Except for rare occasions, the problem is an instance of a large class of problems and the algorithm works for all of these problems. In general, an algorithm partitions a problem into other, smaller problems and solves those. For example, an algorithm for planning a vacation trip requires arrangements for a trip from our home to a nearby airport, a flight to an airport near our vacation spot, and a trip from that airport to our vacation hotel. The entire problem is solved by combining the solutions for these problems.

Designing an algorithm distinguishes two kinds of problems: those that are trivially solvableFor this part of the book, the word “trivial” is a technical term; see Designing Algorithms. and those that are not. If a given problem is trivially solvable, an algorithm produces the matching solution. For example, the problem of getting from our home to a nearby airport might be trivially solvable. We can drive there, take a cab, or ask a friend to drop us off. If not, the algorithm generates a new problem and solves those new problems. A multistage trip is an example of a problem that is non-trivial and can be solved by generating new, smaller problems. In a computational setting one of the smaller problems often belongs to the same class of problems as the original one, and it is for this reason that we call the approach generative recursion.

In this part of the book, we study the design of algorithms, that is, functions based on generative recursion. From the description of the idea, we know that this process is much more of an ad hoc activity than the data-driven design of structurally recursive functions. Indeed, it is almost better to call it inventing an algorithm than designing one. Inventing an algorithm requires a new insight—a “eureka.” Sometimes very little insight is required. For example, solving a “problem” might just require the enumeration of a series of numbers. At other times, however, it may rely on a mathematical theorem concerning numbers. Or, it may exploit a series of mathematical results on systems of equations. To acquire a good understanding of the design process, it is necessary to study examples and to develop a sense for the various classes of examples. In practice, new complex algorithms are often developed by mathematicians and mathematical computer scientists; programmers, though, must throughly understand the underlying ideas so that they can invent the simple algorithms on their own and communicate with scientists about the others.

29 Designing Algorithms

The rest of this chapter is under development. Use HtDP/1e in the meantime.

30 Material for FSMs

shows how to use a finite state machine as a tool for recognizing a specific pattern in strings or in sequences of keystrokes. If you wanted to recognize a different pattern, you would need to modify the program in an appropriate manner.

It should not surprise you that it is possible to create a data representation for FSMs or, equivalently, regular expressions. Once you have this data representation, you can write a program that recognizes any regular-expression pattern in a sequence of keystrokes. As it turns out, BSL+ is not quite powerful enough to implement a true generalization of the world program called for in exercise 100. Instead, the objective of this section is to design accept, a program that checks whether a list of key events is acceptable as specified by a (data representation of an) FSM. To design the full program, you will have to wait until we extend BSL+ to ISL

To get started, we need a data representation for FSMs. Every FSM consists of a finite number of states. It is common to label states with meaningful names but otherwise states have no direct attributes. Hence representing states as strings is a natural idea:

; A State (in an FSM) is a String.

When you read other books or articles, you may also encounter natural numbers or other representations.

An FSM itself has three critical attributes as far as we are concerned: its initial state, its possible final states, and transitions between states, which implicitly specifies the finite states of the FSM. A transition also has three attributes: the state in which a KeyEvent is acceptable; the list of KeyEvents that make the machine transition to another state; and the end state of the transition.

We introduce two distinct structure types to keep track of these attributes:
(define-struct fsm (initial finals transitions))
(define-struct transition (current keys next))
The data definitions for these two structure types just translate the informal prose from above into rigorous comments:

  ;; A {FSM} is

  ;;  racket[(make-fsm tech{State} tech{State*} tech{Transition*})]

  ;; A {Transition} is

  ;;   racket[(make-transition tech{State} tech{KE*} tech{State})]

  ;; A {State*} is one of:

  ;;  -- racket[empty]

  ;;  -- racket[(cons tech{State} tech{State*})]

  ;; A {Transition*} is one of

  ;;  -- racket[empty]

  ;;  -- racket[(cons tech{Transition} tech{Transition*})]

  ;; A {KE*} is one of

  ;;  -- racket[empty]

  ;;  -- racket[(cons tech{KeyEvent} tech{KE*})]

While this collection of data definitions appears to be complex, it is straightforward and representative of real-world problems. It may bother you that we need that many words to say that

  • A machine representation consists of an initial state, a collection of final states, and a list of transitions.

  • A single transition consists of the current state, plus the list of keys that a user may hit to reach the next state.

The next chapter explains why using this many words is actually bad and what we can do about it. For now, we have written down these three data definitions for lists of States, Transitions, and KeyEvents, and you will solve problems that process this kind of data.

In addition to the explicitly specified states of an FSM, we assume that it has one more: (define ER "error"), the error state. Whenever an FSM encounters an erroneous input, it transitions to this special state and stops running.

Exercise 332. Translate the finite state machine from exercise 100 into an element of FSM. Introduce separate definitions:

  • i0 for the initial state;

  • f* for the list of final states;

  • t* for the list of transitions.

Name the machine itself fsm0.

Now we are finally ready for the design of accept. Following the design recipe, we translate the problem statement and the data definitions into a signature, a purpose statement, and a dummy header:
; tech{KE*} FSM -> Boolean
; is the sequence ke of KeyEvents acceptable to fsm
(define (accept ke* fsm)
  false)
As requested, the function consumes a sequence of KeyEvents and an FSM, and like all function whose problem statements mention “whether,” it produces a Boolean. Given your current knowledge of design, however, you cannot design the (core of the) actual function. To create this function systematically from the problem statement, you need not just one but two additional pieces of program design knowledge: generative recursion and accumulators, which this book presents in Generative Recursion and Accumulators, respectively.

Exercise 333. Formulate functional examples for accept using your solution for exercise 332.

Figure 76 presents accept and aux, its auxiliary function. The former extracts the three pieces of the given FSM and hands them to aux together with the sequence of KeyEvents. The latter is the “workhorse” of the program. It use a four-pronged conditional to determine the situation that its inputs describe:

  1. (empty? ke*) means that the sequence of KeyEvents is empty. Since a sequence is considered acceptable if the current state of the program is a final state, the answer is just this test.

  2. (member? crt fnl*) asks whether some state crt is a member of the given list of final states. If so, the program has discovered an acceptable sequence of KeyEvents—up to this point. Note that if this were a world program, the stop-when clause would cause it to shut down.

  3. The third case, (stuck? trns* crt (first ke*)), uses another, yet-to-be-defined auxiliary function, possible?, to determine whether the list of transitions trns* specifies a successor state to crt for the first KeyEvent in the sequence. If not, the machine is considered stuck, meaning the sequence is unacceptable.

  4. Otherwise, we know that (1) the sequence of KeyEvents is not exhausted yet, (2) the current state is not a final state, and (3) trns* contains a transition in from crt to some other state for (first ke*).

As you can see, the last state uses a recursive call to aux to continue the exploration of the sequence of KeyEvents. Instead of crt, aux uses the state determined by next, a second auxiliary function. Your task is to design the two auxiliary functions.

Exercise 334. Design the function stuck?. Here is the wish list entry:
; Transition* State KeyEvent -> Boolean
(define (stuck? t* crt ke)
  false)
The function ensures that none of the transitions in t* has a current state c with ke a member of its keys.

Exercise 335. Design the function next. It comes with this wish list entry:
; Transition* State KeyEvent -> State
(define (stuck? t* crt ke)
  crt)
The function retrieves the next state from a (make-transition crt keys next) in t* if ke is a member of keys. If there is no such item in t*, signal the error "can't happen" because we assume that the function is called only when (stuck? t* crt ke) is false.

Exercise 336. Integrate your solutions to the preceding two exercises with the definitions in figure 76 and make sure all functions pass all their tests.

; tech{KE*} FSM -> Boolean
; is the sequence ke of KeyEvents acceptable to fsm
 
(check-expect (accept '("a" "b" "c" "d") fsm0) true)
(check-expect (accept '("a" "b" "c" "d" "e") fsm0) true)
(check-expect (accept '("a" "b" "left" "d") fsm0) false)
 
(define (accept ke* fsm)
  (aux ke* (fsm-initial fsm) (fsm-finals fsm) (fsm-transitions fsm)))
 
; tech{KE*} State tech{State*} Transition* -> Boolean
; is the sequence ke of KeyEvents acceptable to an FSM
; equivalent to (make-fsm crt fnl* trns*) ?
 
(check-expect (aux '("a" "b" "c" "d") i0 f0 t*) true)
(check-expect (aux '("a" "b" "c" "d" "e") i0 f0 t*) true)
(check-expect (aux '("a" "b" "left" "d") i0 f0 t*) false)
 
(define (aux ke* crt fnl* trns*)
  (cond
    [(empty? ke*) (member? crt fnl*)]
    [(member? crt fnl*) true]
    [(stuck? trns* crt (first ke*)) false]
    [else
     (aux (rest ke*) (next trns* crt (first ke*)) fnl* trns*)]))

Figure 76: Accepting regular expressions

    ← prev  up  next →