You are here: irt.org | FOLDOC | linear function
A recursive function is linear if it is of the form
f 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 ht
h (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 /= bottomthen
for 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)
Nearby terms: linear address space « linear argument « linear assignment « linear function » Linear Graph Notation » linear logic » linear map
FOLDOC, Topics, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ?, ALL