# 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 | log2where 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