<memory management> /kash/ A small fast memory holding
	recently accessed data, designed to speed up subsequent access
	to the same data.  Most often applied to processor-memory
	access but also used for a local copy of data accessible over
	a network etc.

	When data is read from, or written to, {main memory} a copy is
	also saved in the cache, along with the associated main memory
	address.  The cache monitors addresses of subsequent reads to
	see if the required data is already in the cache.  If it is (a
	{cache hit}) then it is returned immediately and the main
	memory read is aborted (or not started).  If the data is not
	cached (a {cache miss}) then it is fetched from main memory
	and also saved in the cache.

	The cache is built from faster memory chips than main memory
	so a cache hit takes much less time to complete than a normal
	memory access.  The cache may be located on the same
	{integrated circuit} as the {CPU}, in order to further reduce
	the access time.  In this case it is often known as {primary
	cache} since there may be a larger, slower {secondary cache}
	outside the CPU chip.

	The most important characteristic of a cache is its {hit rate}
	- the fraction of all memory accesses which are satisfied from
	the cache.  This in turn depends on the cache design but
	mostly on its size relative to the main memory.  The size is
	limited by the cost of fast memory chips.

	The hit rate also depends on the access pattern of the
	particular program being run (the sequence of addresses being
	read and written).  Caches rely on two properties of the
	access patterns of most programs: temporal locality - if
	something is accessed once, it is likely to be accessed again
	soon, and spatial locality - if one memory location is
	accessed then nearby memory locations are also likely to be
	accessed.  In order to exploit spatial locality, caches often
	operate on several words at a time, a "{cache line}" or "cache
	block".  Main memory reads and writes are whole {cache lines}.

	When the processor wants to write to main memory, the data is
	first written to the cache on the assumption that the
	processor will probably read it again soon.  Various different
	policies are used.  In a {write-through} cache, data is
	written to main memory at the same time as it is cached.  In a
	{write-back} cache it is only written to main memory when it
	is forced out of the cache.

	If all accesses were writes then, with a write-through policy,
	every write to the cache would necessitate a main memory
	write, thus slowing the system down to main memory speed.
	However, statistically, most accesses are reads and most of
	these will be satisfied from the cache.  Write-through is
	simpler than write-back because an entry that is to be
	replaced can just be overwritten in the cache as it will
	already have been copied to main memory whereas write-back
	requires the cache to initiate a main memory write of the
	flushed entry followed (for a processor read) by a main memory
	read.  However, write-back is more efficient because an entry
	may be written many times in the cache without a main memory
	access.

	When the cache is full and it is desired to cache another line
	of data then a cache entry is selected to be written back to
	main memory or "flushed".  The new line is then put in its
	place.  Which entry is chosen to be flushed is determined by a
	"{replacement algorithm}".

	Some processors have separate instruction and data caches.
	Both can be active at the same time, allowing an instruction
	fetch to overlap with a data read or write.  This separation
	also avoids the possibility of bad {cache conflict} between
	say the instructions in a loop and some data in an array which
	is accessed by that loop.

	See also {direct mapped cache}, {fully associative cache},
	{sector mapping}, {set associative cache}.

	(1997-06-25)

<file system> An element of data storage in a {file system}.

	The history of computing is rich in varied kinds of files and
	{file systems}, whether ornate (e.g., {Macintosh file system}
	for a well-known case) or deficient (e.g., many simple
	pre-1980s file systems don't allow {directories}).

	However, the prototypical file has these characteristics:

	* It is a single sequence of bytes (but consider {Macintosh}
	{resource forks}).

	* It has a finite length, unlike, e.g. a {Unix} {device}.

	* It is stored in a {non-volatile storage} medium (but see
	{ramdrive}).

	* It exists (nominally) in a {directory}.

	* It has a name that it can be referred to by in file
	operations, possibly in combination with its {path}.

	Additionally, a file system may associate other information
	with a file, such as {permission} bits or other {file
	attributes}; timestamps for file creation, last revision, and
	last access; revision numbers (a` la VMS), and other kinds of
	{magic}.

	Compare: {document}.

	(1997-04-08)

1. <mathematics> A {set} containing a certain number of
	objects selected from another set.

	The number of combinations of r objects chosen from a set of n
	is

		n C r = n! / ((n-r)! r!)

	where "n C r" is normally with n and r as subscripts or as n
	above r in parentheses.

	See also {permutation}.

	2. <reduction> In the theory of {combinators}, a combination
	denotes an expression in which {function application} is the
	only operation.

	(1995-04-10)

<games> [Unix] A Dungeons-and-Dragons-like game using
	character graphics, written under BSD Unix and subsequently
	ported to other Unix systems.  The original BSD "curses(3)"
	screen-handling package was hacked together by Ken Arnold to
	support "rogue(6)" and has since become one of Unix's most
	important and heavily used application libraries.  Nethack,
	Omega, Larn, and an entire subgenre of computer dungeon games
	all took off from the inspiration provided by "rogue(6)".  See
	also {nethack}.

	[{Jargon File}]

1. <file system> {hard link} or {symbolic link}.

	2. <hypertext> {hyperlink}.

	(1997-10-22)

1. The {supervisor} program or {operating system} on a
	computer.

	2. The entire computer system, including input/output devices,
	the {supervisor} program or {operating system} and possibly
	other {software}.

	3. Any large program.

	4. Any method or {algorithm}.

	[{Jargon File}]

<software> Instructions for a computer in some programming
	language, often {machine language}.  The word "code" is often
	used to distinguish instructions from {data} (e.g. "The code
	is marked 'read-only'") whereas "{software}" is used in
	contrast with "{hardware}" and may consist of more than just
	code.

	(2000-04-08)

<World-Wide Web> (URL, previously "Universal") A {standard}
	way of specifying the location of an object, typically a {web
	page}, on the {Internet}.  Other types of object are described
	below.  URLs are the form of address used on the {World-Wide
	Web}.  They are used in {HTML} documents to specify the target
	of a {hyperlink} which is often another HTML document
	(possibly stored on another computer).

	Here are some example URLs:

	 http://www.w3.org/default.html
	 http://www.acme.co.uk:8080/images/map.gif
	 http://www.foldoc.org/?Uniform+Resource+Locator
	 http://www.w3.org/default.html#Introduction
	 ftp://wuarchive.wustl.edu/mirrors/msdos/graphics/gifkit.zip
	 ftp://spy:secret@ftp.acme.com/pub/topsecret/weapon.tgz
	 mailto:fred@doc.ic.ac.uk
	 news:alt.hypertext
	 telnet://dra.com

	The part before the first colon specifies the access scheme or
	{protocol}.  Commonly implemented schemes include: {ftp},
	{http} (World-Wide Web), {gopher} or {WAIS}.  The "file"
	scheme should only be used to refer to a file on the same
	host.  Other less commonly used schemes include {news},
	{telnet} or mailto ({e-mail}).

	The part after the colon is interpreted according to the
	access scheme.  In general, two slashes after the colon
	introduce a {hostname} (host:port is also valid, or for {FTP}
	user:passwd@host or user@host).  The {port} number is usually
	omitted and defaults to the standard port for the scheme,
	e.g. port 80 for HTTP.

	For an HTTP or FTP URL the next part is a {pathname} which is
	usually related to the pathname of a file on the server.  The
	file can contain any type of data but only certain types are
	interpreted directly by most {browsers}.  These include {HTML}
	and images in {gif} or {jpeg} format.  The file's type is
	given by a {MIME} type in the HTTP headers returned by the
	server, e.g. "text/html", "image/gif", and is usually also
	indicated by its {filename extension}.  A file whose type is
	not recognised directly by the browser may be passed to an
	external "viewer" {application}, e.g. a sound player.

	The last (optional) part of the URL may be a query string
	preceded by "?" or a "fragment identifier" preceded by "#".
	The later indicates a particular position within the specified
	document.

	Only alphanumerics, reserved characters (:/?#"<>%+) used for
	their reserved purposes and "$", "-", "_", ".", "&", "+" are
	safe and may be transmitted unencoded.  Other characters are
	encoded as a "%" followed by two {hexadecimal} digits.  Space
	may also be encoded as "+".  Standard {SGML} "&<name>;"
	character entity encodings (e.g. "&eacute;") are also accepted
	when URLs are embedded in HTML.  The terminating semicolon may
	be omitted if &<name> is followed by a non-letter character.

	{The authoritative W3C URL specification
	(http://www.w3.org/hypertext/WWW/Addressing/Addressing.html)}.

	(2000-02-17)

What many users feel for computers.

	"I don't really love computers, I just say that to get them
	into bed with me". (Terry Pratchet)

	[What did you expect in a computing dictionary?]

	(1995-05-10)

<character> "/".  Common names include: (forward) slash;
	stroke; {ITU-T}: slant; oblique stroke.  Rare: diagonal;
	solidus; over; slak; virgule; {INTERCAL}: slat.

	Commonly used as the division {operator} in programming, and
	to separate the components in {Unix} {pathnames}, and hence
	also in {URLs}.  Also used to delimit {regular expressions} in
	several programs.

	(1996-09-24)

1. <programming> A collection of identically typed data items
	distinguished by their indices (or "subscripts").  The number
	of dimensions an array can have depends on the language but is
	usually unlimited.

	An array is a kind of {aggregate} data type.  A single
	ordinary variable (a "{scalar}") could be considered as a
	zero-dimensional array.  A one-dimensional array is also known
	as a "{vector}".

	A reference to an array element is written something like
	A[i,j,k] where A is the array name and i, j and k are the
	indices.  The {C} language is peculiar in that each index is
	written in separate brackets, e.g. A[i][j][k].  This expresses
	the fact that, in C, an N-dimensional array is actually a
	vector, each of whose elements is an N-1 dimensional array.

	Elements of an array are usually stored contiguously.
	Languages differ as to whether the leftmost or rightmost index
	varies most rapidly, i.e. whether each row is stored
	contiguously or each column (for a 2D array).

	Arrays are appropriate for storing data which must be accessed
	in an unpredictable order, in contrast to {lists} which are
	best when accessed sequentially.

	See also {associative array}.

	2. <architecture> A {processor array}, not to be confused with
	an {array processor}.

	(1995-01-25)

1. <mathematics> A {function}, f : A -> B, is injective or
	one-one, or is an injection, if and only if

		for all a,b in A, f(a) = f(b) => a = b.

	I.e. no two different inputs give the same output (contrast
	many-to-one).  This is sometimes called an embedding.  Only
	injective functions have left inverses f' where f'(f(x)) = x,
	since if f were not an injection, there would be elements of B
	for which the value of f' was not unique.  If an injective
	function is also a {surjection} then is it a {bijection}.

	2. <reduction> An injection function is one which takes
	objects of type T and returns objects of type C(T) where C is
	some {type constructor}.  An example is

		f x = (x, 0).

	The opposite of an injection function is a {projection}
	function which extracts a component of a constructed object,
	e.g.

		fst (x,y) = x.

	We say that f injects its argument into the data type and fst
	projects it out.

	(1995-03-14)

1. <networking> A {bang path} or explicitly routed {Internet
	address}; a node-by-node specification of a link between two
	machines.

	2. <file system> {pathname}.

	3. <operating system>  The list of directories the kernel
	(under {Unix}) or the command interpreter (under {MS-DOS})
	searches for {executables}.  It is stored as part of the
	{environment} in both operating systems.

	Other, similar constructs abound under Unix; the {C}
	{preprocessor}, for example, uses such a search path to locate
	"#include" files.

	[{Jargon File}]

	(1996-11-21)

1. <database, information science> A user's (or {agent}'s)
	request for information, generally as a formal request to a
	{database} or {search engine}.

	{SQL} is the most common {database query language}.

	2. <character> {question mark}.

	(1997-04-09)

<programming> A sequence of {data} values, usually {bytes},
	which usually stand for {characters} (a "character string").
	The {mapping} between values and characters is determined by
	the {character set} which is itself specified implcitly or
	explicitly by the environment in which the string is being
	interpreted.

	The most common character set is {ASCII} but, since the late
	1990s, there has been increased interest in larger character
	sets such as {Unicode} where each character is represented by
	more than eight {bits}.

	Most programming languages consider strings (e.g.
	"124:shabooya:\n", "hello world") basically distinct from
	numbers which are typically stored in fixed-length {binary} or
	{floating-point} representation.

	A {bit string} is a sequence of {bits}.

	(1999-12-21)

1. <hardware> An electrical conductor.  For distances larger
	than a breadbox, a single line may consist of two electrical
	conductors in twisted, parallel, or concentric arrangement
	used to transport one logical signal.

	By extension, a (usually physical) medium such as an {optical
	fibre} which carries a signal.

	(1995-09-29)

<programming> A program which executes other programs.  This
	is in contrast to a {compiler} which does not execute its
	input program (the "{source code}") but translates it into
	executable "{machine code}" (also called "{object code}")
	which is output to a file for later execution.  It may be
	possible to execute the same source code either directly by an
	interpreter or by compiling it and then executing the {machine
	code} produced.

	It takes longer to run a program under an interpreter than to
	run the compiled code but it can take less time to interpret
	it than the total required to compile and run it.  This is
	especially important when prototyping and testing code when an
	edit-interpret-debug cycle can often be much shorter than an
	edit-compile-run-debug cycle.

	Interpreting code is slower than running the compiled code
	because the interpreter must analyse each statement in the
	program each time it is executed and then perform the desired
	action whereas the compiled code just performs the action.
	This run-time analysis is known as "interpretive overhead".
	Access to variables is also slower in an interpreter because
	the mapping of identifiers to storage locations must be done
	repeatedly at run time rather than at compile time.

	There are various compromises between the development speed
	when using an interpreter and the execution speed when using a
	compiler.  Some systems (e.g. some {Lisps}) allow interpreted
	and compiled code to call each other and to share variables.
	This means that once a routine has been tested and debugged
	under the interpreter it can be compiled and thus benefit from
	faster execution while other routines are being developed.
	Many interpreters do not execute the source code as it stands
	but convert it into some more compact internal form.  For
	example, some {BASIC} interpreters replace {keywords} with
	single byte tokens which can be used to {index} into a {jump
	table}.  An interpreter might well use the same {lexical
	analyser} and {parser} as the compiler and then interpret the
	resulting {abstract syntax tree}.

	There is thus a spectrum of possibilities between interpreting
	and compiling, depending on the amount of analysis performed
	before the program is executed.  For example {Emacs Lisp} is
	compiled to "{byte-code}" which is a highly compressed and
	optimised representation of the Lisp source but is not machine
	code (and therefore not tied to any particular hardware).
	This "compiled" code is then executed (interpreted) by a {byte
	code interpreter} (itself written in {C}).  The compiled code
	in this case is {machine code} for a {virtual machine} which
	is implemented not in hardware but in the byte-code
	interpreter.

	See also {partial evaluation}.

	(1995-01-30)

1. <database> One or more large structured sets of persistent
	data, usually associated with software to update and {query}
	the data.  A simple database might be a single file containing
	many {records}, each of which contains the same set of
	{fields} where each field is a certain fixed width.

	A database is one component of a {database management system}.

	See also {ANSI/SPARC Architecture}, {atomic}, {blob}, {data
	definition language}, {deductive database}, {distributed
	database}, {fourth generation language}, {functional
	database}, {object-oriented database}, {relational database}.

	{Carol E. Brown's tutorial
	(http://accounting.rutgers.edu/raw/aies/www.bus.orst.edu/faculty/brownc/lectures/db_tutor/db_tutor.htm)}.

	2. <hypertext> A collection of {nodes} managed and stored in
	one place and all accessible via the same {server}.  {Links}
	outside this are "external", and those inside are "internal".

	On the {World-Wide Web} this is called a {website}.

	3. All the facts and rules comprising a {logic programming}
	program.

	(2005-11-17)