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

A Simple Imperative Language + Records

A Simple Imperative Language + Records

References

  • Running code for the program of this lecture is in Records.java.

Aims

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

Lecture

Recall that 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 began with a simple interpreter for a toy programming language. We now consider the changes that arise from the addition of records. Thus, we permit:

  1. Declaration of record types
  2. Creation of new records of a given record type
  3. Selection of record fields
  4. Use of records on the left and right hand side of expressions

Syntax

The syntactic feautures of our language are captured by the following grammar. For motivation, the sort of program that we are interested is exemplified by:

StudentCourseRecord = record 
int firstExamScore;
int secondExamScore;
int totalScore;
end;

StudentSemRecord = record
StudentCourseRecord course1;
StudentCourseRecord course2;
end;
StudentSemRecord r = new StudentSemRecord();
r.course1 = new StudentCourseRecord();
r.course1.firstExamScore = 25;
r.course1.secondExamScore = 35;
r.course1.totalScore = r.course1.firstExamScore + r.course1.secondExamScore;

r.course2 = r.course1;

In the C language, such things are known as structs. In familiar object-oriented terminology, we can think about them in this way:

  • record types are classes whose only members are public member variables
  • records are objects
  • fields are public member variables

The record type definitions in the previous example would look as follows in Java, and the rest of program would look the same.

class StudentCourseRecord {
public int firstExamScore;
public int secondExamScore;
public int totalScore;
}
class StudentSemRecord {
public StudentCourseRecord course1;
public StudentCourseRecord course2;
}

Formally, we proceed via the following BNF grammars. To simplify life for us, we will ignore type information. In this BNF grammar, we are a little bit more careful to separate L(eft) values and R(ight) values. L-values are those that can appear on the left hand side of an assignment statement, and R-values are those that appear on the right hand side of an assignment.

  • Record definitions are given by the BNF grammar:
    Defn ::= record
        FieldList
        end
    FieldList ::= fieldName, FieldList
      | fieldName
  • L-values (fields selected from records, as well as variables) are given by the BNF grammar:
    Lval := e.fieldName
      | variable
  • Expressions (R-values) are given by the BNF grammar:
    e := new C
      | Lval
      | const
      | e1 + e2
      | e1 - e2
  • Statements given by the BNF grammar:
    S ::= Lval = e
      | S1; S2
      | while (e) do S

We first formalize the intutive execution semantics of the toy language. As before, 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. In particular, in this initial first cut, we will begin by ignoring declarations. Also, in this new presentation

Recall that we viewed 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

Records are thought of in a similar light.

As before, we think of the state of the program, which we write S, as a map that associates identifiers with variable objects. Furthermore, as before, we distinguish evaluation and execution. In evaluation, there are two subcases, evaluating to an L-value and evaluating to an R-value.

There are two ways of having L-values. One is via variables and the second is via field selection.

  • The L-value associated with a variable name is the associated variable object.
  • The L-value associated with a selection e.f is obtained by first evaluating the expression e to an R-value, say r. Next, lookup on the record r with field name f is used to get the desired L-value.

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

Our earlier rules for evaluating R-values are presented again below..

  • Evaluating an L-value. In our setup, every L-value (say l) is a variable object that is obtained from the store M. Execute l.get() to compute the return value. This rule subsumes the earlier case for variables.
  • Evaluating e1 + e2: Evaluate e1 first, say to yield value v1. Evaluate e2 next, say to yield value v2. The required result is v1 + v2.
  • Evaluating e1 - e2: Evaluate e1 first, say to yield value v1. Evaluate e2 next, say to yield value v2. The required result is v1 - v2.
  • Evaluating constant c. Every constant evaluates to itself.

The rules for executing statements are as follows. They are similar to the ones seen before. The primary consequence of executing a statement still is the side effect on the store, ie. changes in the values of variables.

  • Executing an assignment statement L = e. Here L is an L-valued expression and e is an R-valued expression. The steps are as follows. First, evaluate the expression L to yield an L-value, say l. Next, evaluate the expression e to yield an R-value, say v. Next, use l.set(v) to change the value of the variable object.
  • Executing a sequence of statements "S1; S2" and a "while" loop are as before.

The execution rules are given in the following pictures:

Implementation

The entire code for the implementation of the imperative language with records is available.