View source for Reference (computer science)

{{Short description|Data type which allows a program to indirectly access a particular value in memory}}
{{About|the general concept in computing|the more specific concept in C++|Reference (C++)}}
{{More citations needed|date=November 2010}}

In [[computer programming]], a '''reference''' is a value that enables a program to indirectly access a particular [[datum]], such as a [[variable (computer science)|variable]]'s value or a [[record (computer science)|record]], in the [[computer]]'s [[memory (computing)|memory]] or in some other [[Data storage device|storage device]].  The reference is said to '''refer''' to the datum, and accessing the datum is called '''[[Dereference operator|dereferencing]]''' the reference. A reference is distinct from the datum itself.

A reference is an [[abstract data type]] and may be implemented in many ways. Typically, a reference refers to data stored in memory on a given system, and its internal value is the [[memory address]] of the data, i.e. a reference is implemented as a [[Pointer (computer programming)|pointer]]. For this reason a reference is often said to "point to" the data. Other implementations include an offset (difference) between the datum's address and some fixed "base" address, an [[array index|index]], or [[identifier]] used in a [[lookup]] operation into an [[Array data structure|array]] or [[table (database)|table]], an operating system [[Handle (computing)|handle]], a [[physical address]] on a storage device, or a network address such as a [[URL]].

==Formal representation==
A reference ''R'' is a value that admits one operation, <kbd>dereference</kbd>(''R''), which yields a value. Usually the reference is typed so that it returns values of a specific type, e.g.:<ref name=Sherman>{{cite book |last1=Sherman |first1=Mark S. |title=Paragon: A Language Using Type Hierarchies for the Specification, Implementation, and Selection of Abstract Data Types |date=April 1985 |publisher=Springer Science & Business Media |isbn=978-3-540-15212-5 |page=175 |url=https://books.google.com/books?id=tXzuooE8EVsC |language=en}}</ref><ref>{{cite web |title=Reference (Java Platform SE 7) |url=https://docs.oracle.com/javase/7/docs/api/java/lang/ref/Reference.html |website=docs.oracle.com |access-date=10 May 2022}}</ref>
<syntaxhighlight lang="java">
interface Reference<T> {
    T value();
}
</syntaxhighlight>

Often the reference also admits an assignment operation <kbd>store</kbd>(''R'', ''x''), meaning it is an [[Abstract data type#Abstract variable|abstract variable]].<ref name=Sherman/>

==Use==
References are widely used in [[computer programming|programming]], especially to efficiently pass large or mutable data as [[argument (computer science)|arguments]] to [[subroutine|procedures]], or to share such data among various uses.  In particular, a reference may point to a variable or record that contains references to other data.  This idea is the basis of [[indirect addressing]] and of many [[linked data structure]]s, such as [[linked list]]s. References increase flexibility in where objects can be stored, how they are allocated, and how they are passed between areas of [[code]]. As long as one can access a reference to the data, one can access the data through it, and the data itself need not be moved. They also make sharing of data between different code areas easier; each keeps a reference to it.

References can cause significant complexity in a program, partially due to the possibility of [[dangling reference|dangling]] and [[wild reference]]s and partially because the [[topology]] of data with references is a [[directed graph]], whose analysis can be quite complicated. Nonetheless, references are still simpler to analyze than [[Pointer (computer programming)|pointer]]s due to the absence of [[pointer arithmetic]].

The mechanism of references, if varying in implementation, is a fundamental programming language feature common to nearly all modern programming languages. Even some languages that support no direct use of references have some internal or implicit use. For example, the [[Evaluation strategy|call by reference]] calling convention can be implemented with either explicit or implicit use of references.

==Examples==
[[Pointer (computer programming)|Pointer]]s are the most primitive type of reference. Due to their intimate relationship with the underlying hardware, they are one of the most powerful and efficient types of references. However, also due to this relationship, pointers require a strong understanding by the programmer of the details of memory architecture. Because pointers store a memory location's address, instead of a value directly, inappropriate use of pointers can lead to [[undefined behavior]] in a program, particularly due to [[dangling pointer]]s or [[wild pointer]]s. [[Smart pointer]]s are [[opaque pointer|opaque data structures]] that act like pointers but can only be accessed through particular methods.

A [[Handle (computing)|handle]] is an abstract reference, and may be represented in various ways. A common example are [[file handle]]s (the FILE data structure in the [[stdio|C standard I/O library]]), used to abstract file content. It usually represents both the file itself, as when requesting a [[lock (computer science)|lock]] on the file, and a specific position within the file's content, as when reading a file.

In [[distributed computing]], the reference may contain more than an address or identifier; it may also include an embedded specification of the network protocols used to locate and access the referenced object, the way information is encoded or serialized. Thus, for example, a [[web services description language|WSDL]] description of a remote web service can be viewed as a form of reference; it includes a complete specification of how to locate and bind to a particular [[web service]]. A reference to a [[live distributed object]] is another example: it is a complete specification for how to construct a small software component called a ''proxy'' that will subsequently engage in a peer-to-peer interaction, and through which the local machine may gain access to data that is replicated or exists only as a weakly consistent message stream. In all these cases, the reference includes the full set of instructions, or a recipe, for how to access the data; in this sense, it serves the same purpose as an identifier or address in memory.

If we have a set of keys ''K'' and a set of data objects ''D'', any well-defined (single-valued) function from ''K'' to ''D'' ∪ {[[Nullable type|null]]} defines a type of reference, where ''null'' is the image of a key not referring to anything meaningful.

An alternative representation of such a function is a directed graph called a [[reachability graph]]. Here, each datum is represented by a vertex and there is an edge from ''u'' to ''v'' if the datum in ''u'' refers to the datum in ''v''. The maximum [[out-degree]] is one. These graphs are valuable in [[garbage collection (computer science)|garbage collection]], where they can be used to separate accessible from [[Unreachable object|inaccessible objects]].

==External and internal storage==
In many data structures, large, complex objects are composed of smaller objects. These objects are typically stored in one of two ways:

# With internal storage, the contents of the smaller object are stored inside the larger object.
# With external storage, the smaller objects are allocated in their own location, and the larger object only stores references to them.

Internal storage is usually more efficient, because there is a space cost for the references and [[dynamic memory allocation|dynamic allocation]] metadata, and a time cost associated with dereferencing a reference and with allocating the memory for the smaller objects. Internal storage also enhances [[locality of reference]] by keeping different parts of the same large object close together in memory. However, there are a variety of situations in which external storage is preferred:

* If the [[Recursive data type|data structure is recursive]], meaning it may contain itself. This cannot be represented in the internal way.
* If the larger object is being stored in an area with limited space, such as the stack, then we can prevent running out of storage by storing large component objects in another memory region and referring to them using references.
* If the smaller objects may vary in size, it is often inconvenient or expensive to resize the larger object so that it can still contain them.
* References are often easier to work with and adapt better to new requirements.

Some languages, such as [[Java (programming language)|Java]], [[Smalltalk]], [[Python (programming language)|Python]], and [[Scheme (programming language)|Scheme]], do not support internal storage.  In these languages, all objects are uniformly accessed through references.

==Language support==

=== Assembly ===
In [[assembly language]], it is typical to express references using either raw memory addresses or indexes into tables. These work, but are somewhat tricky to use, because an address tells you nothing about the value it points to, not even how large it is or how to interpret it; such information is encoded in the program logic. The result is that misinterpretations can occur in incorrect programs, causing bewildering errors.

=== Lisp ===

One of the earliest opaque references was that of the [[Lisp (programming language)|Lisp]] language [[cons|cons cell]], which is simply a [[object composition|record]] containing two references to other Lisp objects, including possibly other cons cells. This simple structure is most commonly used to build singly [[linked list]]s, but can also be used to build simple [[binary tree]]s and so-called "dotted lists", which terminate not with a null reference but a value.

=== C/C++ ===
{{Further|Reference (C++)}}

The [[Pointer (computer programming)|pointer]] is still one of the most popular types of references today. It is similar to the assembly representation of a raw address, except that it carries a static [[datatype]] which can be used at compile-time to ensure that the data it refers to is not misinterpreted. However, because C has a [[weak typing|weak type system]] which can be violated using [[Cast (computer science)|casts]] (explicit conversions between various pointer types and between pointer types and integers), misinterpretation is still possible, if more difficult. Its successor [[C++]] tried to increase [[type safety]] of pointers with new cast operators, a [[reference type]] <code>&</code>, and smart pointers in [[C++ standard library|its standard library]], but still retained the ability to circumvent these safety mechanisms for compatibility.

===Fortran===
Fortran does not have an explicit representation of references, but does use them implicitly in its [[call-by-reference]] calling semantics. A [[Fortran]] reference is best thought of as an ''alias'' of another object, such as a scalar variable or a row or column of an array. There is no syntax to dereference the reference or manipulate the contents of the referent directly. Fortran references can be null. As in other languages, these references facilitate the processing of dynamic structures, such as linked lists, queues, and trees.

===Object-oriented languages===
A number of object-oriented languages such as [[Eiffel (programming language)|Eiffel]], [[Java (programming language)|Java]], [[C Sharp (programming language)|C#]], and [[Visual Basic]] have adopted a much more opaque type of reference, usually referred to as simply a ''reference''. These references have types like C pointers indicating how to interpret the data they reference, but they are typesafe in that they cannot be interpreted as a raw address and unsafe conversions are not permitted. References are extensively used to access and [[Assignment (computer science)#Assignment in object oriented languages|assign]] objects. References are also used in function/[[Method (computer programming)|method]] calls or message passing, and [[Reference counting|reference counts]] are frequently used to perform [[Garbage collection (computer science)|garbage collection]] of unused objects.

===Functional languages===
In [[Standard ML]], [[OCaml]], and many other functional languages, most values are persistent: they cannot be modified by assignment. Assignable "reference cells" provide [[mutable|mutable variables]], data that can be modified. Such reference cells can hold any value, and so are given the [[polymorphism (computer science)|polymorphic]] type <code>α ref</code>, where <code>α</code> is to be replaced with the type of value pointed to. These mutable references can be pointed to different objects over their lifetime. For example, this permits building of circular data structures. The reference cell is functionally equivalent to a mutable array of length 1.

To preserve safety and efficient implementations, references cannot be [[Type conversion|type-cast]] in ML, nor can pointer arithmetic be performed. In the functional paradigm, many structures that would be represented using pointers in a language like C are represented using other facilities, such as the powerful [[algebraic datatype]] mechanism. The programmer is then able to enjoy certain properties (such as the guarantee of  immutability) while programming, even though the compiler often uses machine pointers "under the hood".

=== Perl/PHP ===
[[Perl]] supports hard references, which function similarly to those in other languages, and '''symbolic references''', which are just string values that contain the names of variables. When a value that is not a hard reference is dereferenced, Perl considers it to be a symbolic reference and gives the variable with the name given by the value.<ref>{{cite web|url=http://perldoc.perl.org/perlref.html#Symbolic-references |title=perlref |publisher=perldoc.perl.org |access-date=2013-08-19}}</ref> [[PHP]] has a similar feature in the form of its <code>$$var</code> syntax.<ref>{{cite web|url=http://www.php.net/manual/en/language.variables.variable.php |title=Variable variables - Manual |publisher=PHP |access-date=2013-08-19}}</ref>

==See also==
{{columns-list|
* [[Abstraction (computer science)]]
* [[Autovivification]]
* [[Bounded pointer]]
* [[Linked data]]
* [[Magic cookie]]
* [[Reference]]
* [[Weak reference]]
}}

==References==
{{Reflist}}

==External links==
{{Wiktionary|dereference}}
* [http://cslibrary.stanford.edu/104/ Pointer Fun With Binky] Introduction to pointers in a 3-minute educational video – Stanford Computer Science Education Library

{{Data types}}
{{Semantic Web}}
{{Web syndication}}

[[Category:Data types]]
[[Category:Programming language concepts]]
[[Category:Primitive types]]