In
computer science, an
expression is a
syntactic entity in a
programming language that may be evaluated to determine its
value or fail to terminate, in which case the expression is undefined. It is a combination of one or more
constants,
variables,
functions, and
operators that the programming language interprets (according to its particular
rules of precedence and of
association) and computes to produce ("to return", in a
stateful environment) another value. This process, for mathematical expressions, is called
evaluation. In simple settings, the
resulting value is usually one of various
primitive types, such as
string,
Boolean, or numerical (such as
integer,
floating-point, or
complex). In
computer algebra, formulas are viewed as expressions that can be evaluated as a Boolean, depending on the values that are given to the variables occurring in the expressions. For example 8x-5 \geq 3 takes the value
false if is given a value less than 1, and the value
true otherwise. Expressions are often contrasted with
statements—syntactic entities that have no value (an instruction). tree, from a 1985 Master's Thesis Except for
numbers and
variables, every mathematical expression may be viewed as the symbol of an operator followed by a
sequence of operands. In computer algebra software, the expressions are usually represented in this way. This representation is very flexible, and many things that seem not to be mathematical expressions at first glance, may be represented and manipulated as such. For example, an equation is an expression with "=" as an operator, a
matrix may be represented as an expression with "matrix" as an operator and its rows as operands. See:
Computer algebra expression Computation A
computation is any type of
arithmetic or non-arithmetic
calculation that is "well-defined". The notion that mathematical statements should be 'well-defined' had been argued by mathematicians since at least the
1600s, but agreement on a suitable definition proved elusive. A candidate definition was proposed independently by several mathematicians in the 1930s. The best-known variant was formalised by the mathematician
Alan Turing, who defined a well-defined statement or calculation as any statement that could be expressed in terms of the initialisation parameters of a
Turing machine. Turing's definition apportioned "well-definedness" to a very large class of mathematical statements, including all well-formed
algebraic statements, and all statements written in modern computer programming languages. Despite the widespread uptake of this definition, there are some mathematical concepts that have no well-defined characterisation under this definition. This includes
the halting problem and
the busy beaver game. It remains an open question as to whether there exists a more powerful definition of 'well-defined' that is able to capture both computable and 'non-computable' statements. All statements characterised in modern programming languages are well-defined, including
C++,
Python, and
Java. To illustrate, executing a function call f(a,b) may first evaluate the arguments a and b, store the results in
references or memory locations ref_a and ref_b, then evaluate the function's body with those references passed in. This gives the function the ability to look up the original argument values passed in through dereferencing the parameters (some languages use specific operators to perform this), to modify them via
assignment as if they were local variables, and to return values via the references. This is the call-by-reference evaluation strategy. Evaluation strategy is part of the semantics of the programming language definition. Some languages, such as
PureScript, have variants with different evaluation strategies. Some
declarative languages, such as
Datalog, support multiple evaluation strategies. Some languages define a
calling convention. In
rewriting, a
reduction strategy or rewriting strategy is a relation specifying a rewrite for each object or term, compatible with a given reduction relation. A rewriting strategy specifies, out of all the reducible subterms (
redexes), which one should be reduced (
contracted) within a term. One of the most common systems involves
lambda calculus.
Polynomial evaluation A polynomial consists of variables and
coefficients, that involve only the operations of
addition,
subtraction,
multiplication and
exponentiation to
nonnegative integer powers, and has a finite number of terms. The problem of
polynomial evaluation arises frequently in practice. In
computational geometry, polynomials are used to compute function approximations using
Taylor polynomials. In
cryptography and
hash tables, polynomials are used to compute
k-independent hashing. In the former case, polynomials are evaluated using
floating-point arithmetic, which is not exact. Thus different schemes for the evaluation will, in general, give slightly different answers. In the latter case, the polynomials are usually evaluated in a
finite field, in which case the answers are always exact. For evaluating the
univariate polynomial a_nx^n+a_{n-1}x^{n-1}+\cdots +a_0, the most naive method would use n multiplications to compute a_nx^n, use n-1 multiplications to compute a_{n-1} x^{n-1} and so on for a total of \frac{n(n+1)}{2} multiplications and n additions. Using better methods, such as
Horner's rule, this can be reduced to n multiplications and n additions. If some preprocessing is allowed, even more savings are possible ==Types of expressions==