Circular Programs.

Recursion is usually seen in function definitions. Recursive data-structures can also be defined in (lazy) functional languages. The Hamming numbers are defined to be all products of 2, 3 and 5 only, all numbers of the form:
 i    j    k
2  × 3  × 5,   i,j,k>=0
The sequence begins 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... . Note that 7, 11, 13, 14 are not in the list.

The Hamming program (below) defines a list which begins with the first Hamming number `1':

hamm = 1 :: ...
If you take a Hamming number and multiply it by 2, 3 or 5 you get another Hamming number. A moment's thought reveals that all Hamming numbers, except 1, can be obtained in this way. The program therefore continues by merging the results of multiplying the members of the list by 2, 3 and 5.
merge (mult 2 hamm) (merge .... )
The merge and multiply functions are quite conventional. The program below never terminates but continues to print Hamming numbers until it runs out of space or is killed. If some finite part of the list were printed then such a program would terminate normally.
let rec
 merge = lambda a. lambda b.
   if hd a < hd b then (hd a)::(merge tl a b)
   else if hd b < hd a then (hd b)::(merge a tl b)
   else (hd a)::(merge tl a tl b),

 mul = lambda n. lambda l. (n* hd l)::(mul n tl l)

in let rec
 hamm = 1 :: (merge (mul 2 hamm)
             (merge (mul 3 hamm)
                    (mul 5 hamm)))

in hamm

{\fB Hamming Numbers. \fP}

The merge and multiplication functions can be thought of as processes communicating by streams (lists) of values. The initial value `1' has to be injected to start the calculation. Many operating systems and other useful programs have similar structures where graphs of processes communicate through streams.

Exercise: Modify the program above so that it prints only the first 20 Hamming numbers and then stops.

[Previous Page] [Next Page] [Index] © L. Allison, Dept. of Computer Science, Monash University