Arity

Arity

In logic, mathematics, and computer science, the arity Listeni/ˈærɨti/ of a function or operation is the number of arguments or operands that the function takes. The arity of a relation is the dimension of the domain in the corresponding Cartesian product. The term springs from such words as unary, binary, ternary, etc.

The term "arity" is primarily used with reference to functions of the form f : VS, where VSn, and S is some set. Such a function is often called an operation on S, and n is its arity.

Arities greater than 2 are seldom encountered in mathematics, except in specialized areas. The Logarithm function has an argument and a base: logb(N). Arities greater than 3 are seldom encountered except in theoretical computer science. In computer programming there is often a syntactical distinction between operators and functions; syntactical operators usually have arity 0, 1 or 2.

In mathematics, depending on the branch, arity may be called type, adicity or rank. In computer science, arity may be called adicity, a function that takes a variable number of arguments being called variadic. Unary functions may also be called "monadic"; similarly, binary functions may be called "dyadic".

In linguistics and in logic, arity is sometimes called valency, not to be confused with valency in graph theory.

Contents

Examples

The term "arity" is rarely employed in everyday usage. For example, rather than saying "the arity of the addition operation is 2" or "addition is an operation of arity 2" one usually says "addition is a binary operation". In general, the naming of functions or operators with a given arity follows a convention similar to the one used for n-based numeral systems such as binary and hexadecimal. One combines a Latin prefix with the -ary ending; for example:

  • A nullary function takes no arguments.
  • A unary function takes one argument.
  • A binary function takes two arguments.
  • A ternary function takes three arguments.
  • An n-ary function takes n arguments.

Nullary

Sometimes it is useful to consider a constant as an operation of arity 0, and hence call it nullary or point-free.

Also, in non-functional programming, a function without arguments can be meaningful and not necessarily constant (due to side effects). Often, such functions have in fact some hidden input which might be global variables, including the whole state of the system (time, free memory, ...). The latter are important examples which usually also exist in "purely" functional programming languages.

Unary

Examples of unary operators in mathematics and in programming include the unary minus and plus, the increment and decrement operators in C-style languages (not in logical languages), and the factorial, reciprocal, floor, ceiling, fractional part, sign, absolute value, complex conjugate, and norm functions in mathematics. The two's complement, address reference and the logical NOT operators are examples of unary operators in math and programming. According to Quine, a more suitable term is "singulary",[1] though the term "unary" remains the de facto usage.

All functions in lambda calculus and in some functional programming languages (especially those descended from ML) are technically unary, but see n-ary below.

Binary

Most operators encountered in programming are of the binary form. For both programming and mathematics these can be the multiplication operator, the addition operator, the division operator. Logical predicates such as OR, XOR, AND, IMP are typically used as binary operators with two distinct operands.

Ternary

From C, C++, C#, Java, Perl and variants comes the ternary operator ?:, which is a so-called conditional operator, taking three parameters. Forth also contains a ternary operator, */, which multiplies the first two (one-cell) numbers, dividing by the third, with the intermediate result being a double cell number. This is used when the intermediate result would overflow a single cell. The dc calculator has several ternary operators, such as |, which will pop three values from the stack and efficiently compute x^y \mod z with arbitrary precision. Additionally, many assembly language instructions are ternary or higher, such as MOV %AX, (%BX,%CX), which will load (MOV) into register AX the contents of a calculated memory location that is the sum (parenthesis) of the registers BX and CX.

n-ary

From a mathematical point of view, a function of n arguments can always be considered as a function of one single argument which is an element of some product space. However, it may be convenient for notation to consider n-ary functions, as for example multilinear maps (which are not linear maps on the product space, if n≠1).

The same is true for programming languages, where functions taking several arguments could always be defined as functions taking a single argument of some composite type such as a tuple, or in languages with higher-order functions, by currying.

Other names

  • Nullary means 0-ary.
  • Unary means 1-ary.
  • Binary means 2-ary.
  • Ternary means 3-ary.
  • Quaternary means 4-ary.
  • Quinary means 5-ary.
  • Senary means 6-ary.
  • Septenary means 7-ary.
  • Octary means 8-ary.
  • Nonary means 9-ary.
  • Polyadic, multary and multiary mean any number of operands (or parameters).
  • n-ary means n operands (or parameters), but is often used as a synonym of "polyadic".

An alternative nomenclature is derived in a similar fashion from the corresponding Greek roots; for example, niladic (or medadic), monadic, dyadic, triadic, polyadic, and so on. Thence derive the alternative terms adicity and adinity for the Latin-derived arity.

These words are often used to describe anything related to that number (e.g., undenary chess is a chess variant with an 11×11 board, or the Millenary Petition of 1603).

Notes

See also

References

  • Quine, W. V. O. (1940), Mathematical logic, Cambridge, MA: Harvard University Press 

External links

A monograph available free online:


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • arity — noun /ˈæɹɪɾij,ˈeəɹɪɾij/ The number of arguments or operands a function or operation takes. For a relation, the number of domains in the corresponding Cartesian product. Syn: adinity, adicity, type, rank …   Wiktionary

  • arity — n. total number of items involved in a particular relationship; number of arguments taken by a particular function (Computer Programming); number of arguments taken by a predicate (Linguistics) …   English contemporary dictionary

  • arity — noun the number of arguments that a function can take • Topics: ↑logic • Hypernyms: ↑number …   Useful english dictionary

  • Boolean algebras canonically defined — Boolean algebras have been formally defined variously as a kind of lattice and as a kind of ring. This article presents them more neutrally but equally formally as simply the models of the equational theory of two values, and observes the… …   Wikipedia

  • Structure (mathematical logic) — In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it. Universal algebra studies structures that generalize the algebraic structures such as… …   Wikipedia

  • First-order logic — is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic (a less… …   Wikipedia

  • Logical connective — This article is about connectives in classical logic. For connectors in natural languages, see discourse connective. For connectives and operators in other logics, see logical constant. For other logical symbols, see table of logic symbols. In… …   Wikipedia

  • Operation (mathematics) — The general operation as explained on this page should not be confused with the more specific operators on vector spaces. For a notion in elementary mathematics, see arithmetic operation. In its simplest meaning in mathematics and logic, an… …   Wikipedia

  • Prolog — infobox programming language paradigm = Logic programming year = 1972 designer = Alain Colmerauer implementations = BProlog, ECLiPSe, Ciao Prolog, GNU Prolog, Quintus, SICStus, Strawberry, SWI Prolog, YAP Prolog, tuProlog dialects = ISO Prolog,… …   Wikipedia

  • Tree automaton — A tree automaton is a type of state machine. Tree automata deal with tree structures, rather than the strings of more conventional state machines. The following article deals with branching tree automata, which correspond to regular languages of… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”