Home Articles FAQs XREF Games Software Instant Books BBS About FOLDOC RFCs Feedback Sitemap
irt.Org

linear function

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 x

where 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 c

Function ht is known as the "predicate transformer" of h.

(2) If for some x,

	h (\ y . bottom) x  /=  bottom

then

	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

©2018 Martin Webb