Linear from FOLDOC

linear address space

A memory addressing scheme used in processors where the whole memory can be accessed using a single address that fits in a single register or instruction. This contrasts with a segmented memory architecture, such as that used on the Intel 8086, where an address is given by an offset from a base address held in one of the "segment registers". Linear addressing greatly simplifies programming at the assembly language level but requires more instruction word bits to be allocated for an address.

Last updated: 1995-02-16

linear argument

<theory>

A function argument which is used exactly once by the function.

If the argument is used at most once then it is safe to inline the function and replace the single occurrence of the formal parameter with the actual argument expression. If the argument was used more than once this transformation would duplicate the argument expression, causing it to be evaluated more than once.

If the argument is sure to be used at least once then it is safe to evaluate it in advance (see strictness analysis) whereas if the argument was not used then this would waste work and might prevent the program from terminating.

Last updated: 1994-11-03

linear assignment

assignment problem

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.

Linear Graph Notation

(LGN) A linearised representation of TCOL trees.

[B.W. Leverett et al, "An Overview of the Production Quality Compiler-Compiler Projects", TR CMU-CS-79-105, Carnegie Mellon 1979].

Last updated: 1995-01-23

linear logic

<theory>

A logic invented by Girard in 1987 that can be used in proofs related to resource usage.

http://brics.dk/LS/96/6/BRICS-LS-96-6/BRICS-LS-96-6.html.

[Wadler, P., "Is there a use for linear logic", ACM/IFIP PEPM Conference, 1991].

[Summary?]

Last updated: 2003-05-02

linear map

<mathematics>

(Or "linear transformation") A function from a vector space to a vector space which respects the additive and multiplicative structures of the two: that is, for any two vectors, u, v, in the source vector space and any scalar, k, in the field over which it is a vector space, a linear map f satisfies f(u+kv) = f(u) + kf(v).

Last updated: 1996-09-30

linear programming

<application>

A procedure for finding the maximum or minimum of a linear function where the arguments are subject to linear constraints. The simplex method is one well known algorithm.

Last updated: 1995-04-06

linear space

<mathematics>

A vector space where all linear combinations of elements are also elements of the space. This is easy for spaces of numbers but not for a space of functions. Roughly, this is to say that multiplication by numbers, and addition of elements is defined in the space.

Last updated: 2000-03-10

linear topology

<theory>

A linear topology on a left A-module M is a topology on M that is invariant under translations and admits a fundamental system of neighborhood of 0 that consists of submodules of M. If there is such a topology, M is said to be linearly topologized. If A is given a discrete topology, then M becomes a topological A-module with respect to a linear topology.

[Wikipedia]

Last updated: 2014-06-30

linear transformation

linear map

linear type

<theory, programming>

1. An attribute of values which are used exactly once: they are neither duplicated nor destroyed. Such values require no garbage collection, and can safely be updated in place, even if they form part of a data structure.

Linear types are related to the linear logic of J.-Y Girard. They extend Schmidt's notion of single threading, provide an alternative to Hudak and Bloss' update analysis, and offer a practical complement to Lafont and Holmström's elegant linear languages.

['Use-Once' Variables and Linear Objects - Storage Management, Reflection and Multi-Threading, Henry Baker. http://home.pipeline.com/~hbaker1/Use1Var.html].

["Linear types can change the world!", Philip Wadler, "Programming Concepts and Methods", April 1990, eds. M. Broy, C. Jones, pub. North-Holland, IFIP TC2 Working Conference on Programming Concepts and Methods, Sea of Galilee, Israel].

Last updated: 1995-03-03

Nearby terms:

line 666 ♦ linear address space ♦ linear argument ♦ linear assignment

Try this search on Wikipedia, Wiktionary, Google, OneLook.