Abstract syntax trees

Abstract syntax trees (AST) are the tree representations of the symbolic expressions in programming languages. F# can provide an elegant representation of symbolic expressions as trees. In order to evaluate an expression tree, we need to traverse it in post-order. A simple expression tree for the statement can be represented as follows:

Like the mathematical expression tree (a specialized abstraction syntax tree) in the preceding example, an expression in a programming language is typically composed of variables and operators.

type expression =
  | Integer of int
  | Var of string 
  | Addition of expression * expression 
  | Multiply of expression * expression ;;

Therefore, the expression tree for the statement can be represented as follows:

type expression =
  | Integer of int
  | Var of string 
  | Addition of expression * expression
  | Multiply of expression * expression;;

let expr = Addition (Multiply(Integer 2, Integer 3), Integer 1)

F# does not have a built...