Definitions
We define an arithmetic expression as a combination of variables, numerical values and operations over these values. For example, the arithmetic expression 2 + 3 uses two numeric values 2 and 3 and an operation +. The syntax of an expression specifies the allowed combinations of expressions. Each expression has a meaning (or value), which is defined by the evaluation of that expression. Evaluation is a process where expressions composed of various components get simplified until eventually we get a value. For example, evaluating 2 + 3resultsin5.
Syntax
The conceptual structure of an expression is called the abstract syntax. The particular details and rules for writing expressions as strings of characters is called the concrete syntax, e.g. MathML. The abstract syntax for arithmetic expressions is very simple, while the concrete syntax can include additional punctuation and other lexical features.
Abstract Syntax
The abstract syntax of expressions can be represented by the following EBNF grammar:
Expr ::= Number Real
| BinOp B Expr Expr
| UnOp U Expr
B ::= + | - | * | / | ^
U ::= neg | abs | atan | asin | acos | sin | cos | exp | ln |
sqrt | tan | cosh | sinh | tanh | gamma | lgamma | log10 | log2 where Number, BinOp, UnOp indicate the different kinds of expressions: numeric value, binary operation and unary operation, respectively, and the set of binary and unary operations are the the usual arithmetic operators on real numbers.
Variables and Substitution
Arithmetic expressions contain variables in addition to constants and arithmetic operations. Thus we will need to extend the abstract syntax of expressions to include variables. We can represent variables as an additional kind of expression. The following data definition modifies Expr to include a Variable case:
Expr ::= Number Real
| BinOp B Expr Expr
| UnOp U Expr
| Variable Symbol
(B and U as before)
Further, in order to assign a meaning to a variable in a particular context, we will define the association of a variable x with a value v as a binding, which can be written as x \mapsto v. Bindings can be represented as pair. For example, the binding of x \mapsto 5 can be represented as (symbol\;"x",\;5).
Substitution
The substitution operation replaces a variable with a value in an expression. Here are some examples of substitution:
- substitute (x \mapsto 5) in (x + 2) \rightarrow{} (5 + 2)
- substitute (x \mapsto 5) in (2) \rightarrow{} (2)
- substitute (x \mapsto 5) in (x * x + x) \rightarrow{} (5 * 5 + 5)
- substitute (x \mapsto 5) in (x + y) \rightarrow{} (5 + y)
If the variable names don't match, they are not substituted. Given the syntax defined for expressions, the process of substitution can be defined by cases:
simpleSubstitute (var, newVar) exp = subst exp
where
subst (Number r) = Number r
subst (BinOp B a b) = BinOp B (subst a) (subst b)
subst (UnOp U a b) = UnOp U (subst a) (subst b)
subst (Variable name) = if var == name
then Variable newVar
else Variable name
Environments
There can be multiple variables in a single expression. For example, evaluating (2 * x + y) where x = 3 and y = -2 results in 4.
A collection of bindings is called an environment. Since a binding is represented as a tuple, an environment can be represented as a list of tuples. The environment from the example above would be
env = [ ("x", 3), ("y", -1) ]
An important operation on environments is variable lookup. Variable lookup is an operation that given a variable name and an environment looks up that variable in the environment. For example:
- lookup (x) in (env)\rightarrow3
- lookup (y) in (env)\rightarrow-1
The substitution function can then be redefined to use environments rather than single bindings:
substitute env exp = subst exp where
subst (Number r) = Number r
subst (BinOp B a b) = BinOp B (subst a) (subst b)
subst (UnOp U a) = UnOp U (subst a)
subst (Variable name) = case lookup name env of
Some r => Number r
| None => Variable name
Local Variables
It is also useful to allow variables to be defined within an expression. We will define local variables with a let expression:
let x = 1 in 2*x + 3
Local variable declarations are themselves expressions, cand can be used inside other expressions:
2 * (let x = 3 in x + 5)
Local variable declarations can be represented in the abstract syntax by adding another clause:
Expr ::= ...
| Let Symbol Expr Expr
When substituting a variable into an expression, it must correctly take into account the scope of the variable. In particular, when substituting for x in an expression, if the expression is of the form let x = e in body then x should be substituted within e but not in body.
simpleSubstitute (var, val) exp = subst exp
subst (Let x exp body) = Let x (subst exp) body1
where body1 = if x == var
then body
else subst body
In the Let case for subst, the variable is always substituted into the bound expression e. But the substitution is only performed on the body b if the variable var is not the same as x.
Evaluation
TODO
Summary
Here is the complete definition, substitution and evaluation using an expression language with local variables.
Expr ::= Number Real
| BinOp B Expr Expr
| UnOp U Expr
| Variable Symbol
| Let Symbol Expr Expr
simpleSubstitute (var, val) exp = subst exp where
subst (Number r) = Number r
subst (BinOp B a b) = BinOp B (subst a) (subst b)
subst (UnOp U a b) = UnOp U (subst a) (subst b)
subst (Variable name) = if var == name
then Number val
else Variable name
subst (Let x exp body) = Let x (subst exp) body1
where body1 = if x == var
then body
else subst body
evaluate (Number r) = r
evaluate (BinOp + a b) = (evaluate a) + (evaluate b)
...
evaluate (UnOp sqrt a) = sqrt (evaluate a)
...
evaluate (Let x exp body) = evaluate (simpleSubstitute (x, evaluate exp) body)
evaluate (Variable x) = Error