You are here: Home Teaching Comp 373/473 Handouts A Simple Imperative Language
Document Actions

A Simple Imperative Language

A Simple Imperative Language

References

  • Design Patterns and Object Oriented Programming, Pages 175-185
  • Running code for the program of this lecture is in SimpleImperative.java.

Aims

  • Design of an interpreter and programming environment for a simple imperative language

Lecture

We are leading towards building an interpreter for a language resembling Java with object like features. We are doing this with two aims in mind:

  • To understand an OO language from the "inside".
  • To understand better the rudimentary design patterns that we have learned by using them in the context of a small but somewhat sophisticated program.

As a prelude and a simple warmup exercise, we begin with a simple interpreter for a toy programming language.

Syntax

Our language has the following features:

  • Integer expressions given by the BNF grammar:
e ::= variable
  | const
  | e1 + e2
  | e1 - e2
  • Statements given by the BNF grammar:
S ::= x = e
  | S1 ; S2
  | while (e) do S

In the context of the lectures so far, we have made the following changes. We have added variables to expressions, thus we can handle cases like "x + 3", whereas earlier we could only write expressions such as "4 + 3". We have also introduced the assignment statement as a way to change the contents of a variable. In addition, we allow statements to be put in sequence. We also permit simple while expressions, where the guard is an expression and the loop body is executed while the gurad expression evaluates to a non-zero integer value.

Operational semantics

We first formalize the intutive execution semantics of the toy language. The point of doing this is to present the basic ideas in the interpreter without getting tied up in the programming details of the interpreter. In any case, these details are presented later in this lecture. Since our toy language has variables, we need to keep track of the state of variables. We view variables as objects with two capabilites:

  • get() returns the current value of the variable
  • set(int x) changes the current value of the variable to that of x

We think of the state of the program (memory store), which we write M, as a map that associates identifiers with variable objects.

The rules for evaluating expressions are quite simple.

  • Evaluating constant c. Every constant evaluates to itself.
  • Evaluating a variable whose name is x: Retrieve the variable object (say v) associated with x from the store M, by using M(x). The required result is computed by invoking v.get().
  • Evaluating e1 + e2: Evaluate e1 first, say to yield value r1. Evaluate e2 next, say to yield value r2. The required result is r1 + r2.
  • Evaluating e1 - e2: Evaluate e1 first, say to yield value r1. Evaluate e2 next, say to yield value r2. The required result is r1 - r2.

The evaluation rules are written out precisely in the following picture.

The rules for executing statements is as follows. In contrast to expression evaluation, statement execution does not yield a result. The primary consequence of executing a statement is the side effect on the store, ie. changes in the values of variables.

  • Executing an assignment statement: Consider the assignment statement x = e. In this e is an expression. The steps are as follows. First, evaluate the expression e to yield a result, say r. Next, retrieve the variable object (say v) associated with x from the store M, by using M(x). Perform v.set(r) to change the value of the variable object.
  • Executing a sequence of statements "S1; S2": Execute S1 first. When that terminates, execute S2.
  • Executing "while (e) do S": Evaluate e to yield a result r. If r is zero, the execution terminates. Otherwise, execute S and repeat the process.

The execution rules are given in the following pictures:

Note that the connection between the various statements is that they share a single store, ie. in the sequence of statements "x = 2; y = x + 1", the second reference to x reflects the effect of the first assignment because of the (shared) store between the two assignment statements.

The interpreter program

We now go ahead and write the interpreter program. While setting up the interpreter, we will actually go ahead and set up a tiny programming environment with primitive debugging facilities. The entire code is available.