Check out section 2.2 where he compares different models to state machines and expresses how they can be mapped. In particular look at the BNF grammar one, where he talks about production rules.
In functional languages (especially pure ones) there is the notion of "reductions" which are rewrite rules for the language. So in Scheme (to pick a concrete language) an expression like:
(+ 5 2)
Is reduced by applying the addition operation:
(+ 5 2) => 7
Or (with a suitable definition of factorial to continue his example):
;; using his Program 3 in Scheme instead of C
(define (factorial i)
(if (= i 1)
1
(* i (factorial (- i 1)))))
(factorial 7) => (if (= 7 1) 1 (* 7 (factorial (- 7 1)))) ;; because we substitute 7 for i
=> (if #f 1 (* 7 (factorial (- 7 1)))) ;; reducing (= 7 1) => #f
=> (* 7 (factorial (- 7 1))) ;; reducing (if #f e_t e_f) => e_f
=> ...
Each of these arrived at by applying a reduction rule (in this case there's only one reduction rule available at each point).
This is analogous to his discussion of BNF grammars. The state transitions are moving from an expression e to an expression e' where some reduction rule has been applied to e.
EDIT: Grammar and comments describing application of reduction rules.
I can see that making a call to a sub-function and returning from, it to the calling function means the state of the execution has changed. But it means the state of the engine that evaluates the functions. As was said earlier the functions themselves do not have a state.
I don't think anybody would try to model a state-machine by making each state-change they want to model a call to a sub-function. The engine evaluating the function-expressions has its state but the functional program itself does not, it just has it code, arguments, and result. It can be in one of the states
1. Not Called
2. Calculating the result
3. The result has been calculated.
> 1. Not Called 2. Calculating the result 3. The result has been calculated.
That describes an oracle, not a purely functional program. A program describes a process (whether the program is purely functional or totally imperative). The state of the process can be captured in progress because, well, it's a process. There is a series of steps which are applied to produce the calculated result.
In purely functional programs, that would be the reduction rules. Each application of a reduction rule produces a new state (in essence the remaining computation to be performed).
In functional languages (especially pure ones) there is the notion of "reductions" which are rewrite rules for the language. So in Scheme (to pick a concrete language) an expression like:
Is reduced by applying the addition operation: Or (with a suitable definition of factorial to continue his example): Each of these arrived at by applying a reduction rule (in this case there's only one reduction rule available at each point).This is analogous to his discussion of BNF grammars. The state transitions are moving from an expression e to an expression e' where some reduction rule has been applied to e.
EDIT: Grammar and comments describing application of reduction rules.