# Symbols, Environments and Expression Evaluation

Symbolic computing is fundamentally concerned with *symbols*, the atomic tokens of a notation that represent some concept related to the symbolic computing domain.

*Operator*symbols such as`*`

,`+`

, and`-`

of algebraic expressions represent some specific operation in the domain.*Keyword*symbols such as`if`

and`else`

in programming languages often signify control structures.*Identifier*symbols often represent arbitrary values depending on the context of a given application. The variables and function names of a programming language are typical.

## Environments and Evaluation

*Symbol environments* (also called *symbol tables* in some applications) define mappings from symbols in the notation system to particular values in the domain.

*Association lists* are a simple data structure that can be used to implement environments in symbolic computing applications.
An association list is simply a list of key-value pairs.
For example, an association list mapping "color codes" to numeric values might be written as follows.

color_codes = [("black", 0), ("brown", 1), ("red", 2), ("orange", 3)]

Given such an association list, the Haskell built-in operation "lookup" can retrieve the value associated with a symbol.

Prelude> :t lookup lookup :: Eq a => a -> [(a, b)] -> Maybe b Prelude> lookup "red" [("black", 0), ("brown", 1), ("red", 2), ("orange", 3)] Just 2

### Evaluation of Algebraic Expressions

In an algebraic expression such \(4x^2+3y\), we may want to evaluate the expression in the context of an environment mapping symbols to numeric values. For example, we might want to evaluate the expression just given in the context of the association list `[('x', 7), ('y', -1)]`

.

Using the `lookup`

function we can write a recursive evaluator for our algebraic expression domain. Recall our domain structure"

```
data ME = Num Int
| Var Char
| Group ME
| Add ME ME
| Sub ME ME
| Mul ME ME
| Power ME Int
| Neg ME
deriving (Show, Ord, Eq)
```

We can implement an `evalmath`

function as follows.

evalmath :: [(Char, Int)] -> ME -> Maybe Int evalmath env (Num n) = Just n evalmath env (Var c) = lookup c env evalmath env (Group g) = evalmath env g evalmath env (Add f g) = case (evalmath env f, evalmath env g) of (Just x, Just y) -> Just (x + y) _ -> Nothing evalmath env (Sub f g) = case (evalmath env f, evalmath env g) of (Just x, Just y) -> Just (x - y) _ -> Nothing evalmath env (Mul f g) = case (evalmath env f, evalmath env g) of (Just x, Just y) -> Just (x * y) _ -> Nothing evalmath env (Power f n) = case (evalmath env f) of (Just x) -> Just (x ^ n) _ -> Nothing evalmath env (Neg f) = case (evalmath env f) of (Just x) -> Just (-x) _ -> Nothing

We can now use `evalmath`

to perform calculations.

*Main> evalmath [('x', 7), ('y', -1)] (Add (Mul (Num 4) (Power (Var 'x') 2)) (Mul (Num 3) (Var 'y'))) Just 193