2.3.2 Modeling Processes with J

We express the same example used in Section 2.3.1 using the J notation to show the expressiveness of J for modeling and recursive and iterative processes.

The fibonacci sequence 0 1 1 2 3 5 8 13, ... may be generated by the recursive definition:

fibonacci =: monad define script
if. y. < 2
  do. y.
  else. (fibonacci y. - 1) + fibonacci y. - 2
end.
)

When analyzing this recursive definition, it is useful to define a related function, fib_work, whose value, given an input n, is the number of times fibonacci is called when evaluating fibonacci n . It is easy to show that fib_work may be defined as:

fib_work =: monad define script
if. y. < 2
  do. 1
  else. 1 + (fib_work y. - 1) + fib_work y. - 2
end.
)

As in Section 2.3.1, fib_work, itself, generates the values of a kind of fibonacci sequence. If it is our goal to evaluate either of these functions for inputs greater than 25 to 30, it is necessary to convert these definitions to definitions which result in iterative processes. A recursive definition for fib_work which results in an iterative process is given by the definition:

fib_work_iter =: monad define 'fib_work_iter_helper 1 1 , y.'

fib_work_iter_helper =: monad define script
('a' ; 'b' ; 'count') =. y.
if. count = 0
  do. b
  else. fib_work_iter_helper (1 + a + b) , a , count - 1
end.
)

Again, as in Section 2.3.1, we may define the idea of a continuation. Suppose f is a compound expression and e is a sub expression of f. The continuation of e in f is that monad having input y., monad define '... y. ...' which contains the execution in f which remains to be done after evaluating the sub expression e. This means that the value of the entire expression f may be obtained by evaluating:

monad define '... y. ...' e.

Since the continuation of each recursive use of fib_work_iter_helper in the definition of fib_work_iter_helper is the identity function, fib_work_iter generates a more efficient iterative process so that:

   fib_work_iter 100x
1146295688027634168201x

The J numeric suffix "x" indicates that an exact numeric representation should be used in this computation.