Module While_ast

Abstract syntax for the while language

module Var : sig ... end

For referring to named storage locations, we use the Var module which ensures that each variable of type t is a record with name and a unique internal identifier to prevent any clashes.

type aexp =

1. | Int of int
   (*

   integer constant

   *)
2. | Var of Var.t
   (*

   variable

   *)
3. | Add of aexp * aexp
   (*

   addition

   *)
4. | Sub of aexp * aexp
   (*

   subtraction

   *)
5. | Mul of aexp * aexp
   (*

   multiplication

   *)

The aexp type represents integer-valued expressions in the While language. It includes literal constants and has three basic binary operations: addition, subtraction, and multiplication. Each constructor takes one or two sub-expressions of type aexp, allowing arbitrarily nested arithmetic trees (for example, (x + 2) * (y - 1)).

type bexp =

1. | True
2. | False
3. | Eq of aexp * aexp
   (*

   equality

   *)
4. | Le of aexp * aexp
   (*

   less than or equal

   *)
5. | Gt of aexp * aexp
   (*

   striclty greater than

   *)
6. | Not of bexp
   (*

   negation

   *)
7. | And of bexp * bexp
   (*

   conjunction

   *)

The bexp boolean expression captures logical predicates used in conditionals and loops. It provides the Boolean constants (True, False), comparison operators over arithmetic expressions -- equality (Eq), less-than-or-equal (Le), and greater-than (Ge) -- as well as logical negation (Not) and conjunction (And).

With nesting, one can form complex expressions such as (v <= 5 && !(v == 0)).

type stmt =

1. | Skip
2. | Assign of Var.t * aexp
3. | Seq of stmt * stmt
4. | If of bexp * stmt * stmt
5. | While of bexp * stmt
   (*

   Finally, the stmt type defines the statements of the While language. Skip is a no operation; Assign updates a variable from an arithmetic expression; Seq composes two commands sequentially; If chooses one of two branches based on a boolean test; and While repeatedly executes its body while a condition holds.

   *)

val pp_aexp : Stdlib.Format.formatter -> aexp -> unit

val pp_bexp : Stdlib.Format.formatter -> bexp -> unit

val pp_stmt : Stdlib.Format.formatter -> stmt -> unit