Introduction to Programming in ATS:
<<< PreviousDatatypesNext >>>

Example: Evaluating Integer Expressions

For representing integer expressions, we declare a datatype IEXP as follows: 

datatype IEXP =
  | IEXPnum of int // numeral
  | IEXPneg of (IEXP) // negative
  | IEXPadd of (IEXP, IEXP) // addition
  | IEXPsub of (IEXP, IEXP) // subtraction
  | IEXPmul of (IEXP, IEXP) // multiplication
  | IEXPdiv of (IEXP, IEXP) // division
// end of [IEXP]

The meaning of the constructors associated with IEXP should be obvious. A value of the type IEXP is often referred to as an abstract syntax tree. For instance, the abstract syntax tree for the expression (~1+(2-3)*4) is the following one: 

IEXPadd(IEXPneg(IEXPnum(1)), IEXPmul(IEXPsub(IEXPnum(2), IEXP(3)), IEXP(4)))

Translating an integer expression written in some string form into an abstract syntax tree is called parsing, which we will not do here. The following defined function eval_iexp takes the abstract syntax tree of an integer expression and return an integer that is the value of the expression: 

fun eval_iexp (e0: IEXP): int = case+ e0 of
  | IEXPnum n => n
  | IEXPneg (e) => ~eval_iexp (e)
  | IEXPadd (e1, e2) => eval_iexp (e1) + eval_iexp (e2)
  | IEXPsub (e1, e2) => eval_iexp (e1) - eval_iexp (e2)
  | IEXPmul (e1, e2) => eval_iexp (e1) * eval_iexp (e2)
  | IEXPdiv (e1, e2) => eval_iexp (e1) / eval_iexp (e1)
// end of [eval_iexp]

Suppose we also allow the construct if-then-else to be use in forming integer expressions. For instance, we may write an integer expression like (if 1+2 <= 3*4 then 5+6 else 7-8). Note that the test (1+2 <= 3*4) is a boolean expression rather than an integer expression. This indicates that we also need to declare a datatype BEXP for representing boolean expressions. Furthermore, IEXP and BEXP should be defined mutually recursively, which is shown in the following code: 

datatype IEXP =
  | IEXPcst of int // integer constants
  | IEXPneg of (IEXP) // negative
  | IEXPadd of (IEXP, IEXP) // addition
  | IEXPsub of (IEXP, IEXP) // subtraction
  | IEXPmul of (IEXP, IEXP) // multiplication
  | IEXPdiv of (IEXP, IEXP) // division
  | IEXPif of (BEXP(*test*), IEXP(*then*), IEXP(*else*))
// end of [IEXP]

and BEXP = // [and] for combining datatype declarations
  | BEXPcst of bool // boolean constants
  | BEXPneg of BEXP // negation
  | BEXPconj of (BEXP, BEXP) // conjunction
  | BEXPdisj of (BEXP, BEXP) // disjunction
  | BEXPeq of (IEXP, IEXP) // equal-to
  | BEXPneq of (IEXP, IEXP) // not-equal-to
  | BEXPlt of (IEXP, IEXP) // less-than
  | BEXPlte of (IEXP, IEXP) // less-than-equal-to
  | BEXPgt of (IEXP, IEXP) // greater-than
  | BEXPgte of (IEXP, IEXP) // greater-than-equal-to
// end of [BEXP]

Evidently, we also need to evaluate boolean expressions when evaluating integer expressions. The following two functions eval_iexp and eval_bexp for evaluating integer and boolean expressions, respectively, are defined mutually recursively as is expected: 

fun eval_iexp (e0: IEXP): int = case+ e0 of
  | IEXPcst n => n
  | IEXPneg (e) => ~eval_iexp (e)
  | IEXPadd (e1, e2) => eval_iexp (e1) + eval_iexp (e2)
  | IEXPsub (e1, e2) => eval_iexp (e1) - eval_iexp (e2)
  | IEXPmul (e1, e2) => eval_iexp (e1) * eval_iexp (e2)
  | IEXPdiv (e1, e2) => eval_iexp (e1) / eval_iexp (e1)
  | IEXPif (e_test, e_then, e_else) => let
      val b = eval_bexp (e_test) in eval_iexp (if b then e_then else e_else)
    end // end of [IEXPif]
// end of [eval_iexp]

and eval_bexp (e0: BEXP): bool = case+ e0 of
  | BEXPcst b => b
  | BEXPneg (e) => ~eval_bexp (e)
  | BEXPconj (e1, e2) => if eval_bexp (e1) then eval_bexp (e2) else false
  | BEXPdisj (e1, e2) => if eval_bexp (e1) then true else eval_bexp (e2)
  | BEXPeq (e1, e2) => eval_iexp (e1) = eval_iexp (e2)
  | BEXPneq (e1, e2) => eval_iexp (e1) <> eval_iexp (e2)
  | BEXPlt (e1, e2) => eval_iexp (e1) < eval_iexp (e2)
  | BEXPlte (e1, e2) => eval_iexp (e1) <= eval_iexp (e2)
  | BEXPgt (e1, e2) => eval_iexp (e1) > eval_iexp (e2)
  | BEXPgte (e1, e2) => eval_iexp (e1) >= eval_iexp (e2)
// end of [eval_bexp]

The integer and boolean expressions used in this example are all constant expressions containing no variables. Therefore, there is no need for an environment to evaluate them. I will present a more advanced example elsewhere to demonstrate how an evaluator for a simple call-by-value functional programming language like the core of ATS can be implemented.

<<< PreviousHomeNext >>>
Exhaustiveness of Pattern-MatchingUpParametric Polymorphism