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