A recursive function is linear if it is of the formf x = if p x then q x else h f xwhere h is a "linear functional" which means that(1) for all functions, a, b c and some function hth (if a then b else c) = if ht a then h b else h cFunction ht is known as the "predicate transformer" of h.(2) If for some x,h ( y . bottom) x/=bottomthenfor all g,ht g x=True.I.e. if h g x terminates despite g x not terminating then ht g x doesn' t depend on g.See also linear argument.(1995-02-15)