NEW MEXICO STATE UNIVERSITY
Department of Computer Science

Programming Languages Qualifying Examination
January 11th, 1999 -- 12-16pm

Let us consider an Object-oriented language. Each class is described simply by a list of attributes (e.g., you can think of a class as a list of variables in a typeless language). The language allows the manipulation of the class hierarchy using the following command:

• create_class(Name,Parent,Attributes): which creates a new class named Name, which is subclass of the class Parent, and contains the attributes Attributes. For example,
  
  create_class(Car,Vehicle,[brand,convertible?,..])
  creates the class Car, subclass of Vehicle.

You can assume that the language relies on a single-root hierarchy and performs single-inheritance.

Consider also the use of the class hierarchy in a simple imperative language, based on the following syntax:

Program	$\rightarrow$	Command
Command	$\rightarrow$	Command ; Command
	|	Id := Expression
	|	Id := new Class
	|	Id1.Id2 := Expression
	|	ClassOperation
Expression	$\rightarrow$	(Expression)
	|	Expression + Expression
	|	Numeral
	|	Id
	|	Id1 . Id2
ClassOperation	$\rightarrow$	create_class Id Id Attributes
Attributes	$\rightarrow$	Id
	|	Id , Attributes

The ClassOperation denotes the operations to modify the class hierarchy. The purpose of the operation new is to create an instance of the class Class. The expression and the assignment introduce the special case Id₁.Id₂ which allows to access the attribute Id₂ from the object Id₁. For example, the operation

mycar.wheels := 4

assigns the value 4 to the attribute wheels of the object mycar.

1.

[75 pts] Provide the denotational semantics for this language, with particular focus on formally modeling and using the class hierarchy and the objects created as instances of the classes (new operation). In particular:

• provide a formal description of the semantic algebras needed;
• provide the complete valuation functions for the language above.

Your valuation functions are required to perform error checking for all the operations associated with objects and classes (e.g., whenever an operation involving I₁.I₂ is performed the semantics should guarantee that I₂ is indeed an attribute of the object I₁).

You can rely on the overall structure of the denotational semantics for imperative languages presented in Schmidt's book for the various operations in the language above.

2.

[25 pts] Assume that an additional class operation is introduced:

• add_attribute(Class,Attribute) adds a new attribute, called Attribute to the existing class Class

Characterize the meaning of this new operation. Discuss how the new operation affects the semantics of the language (be precise and to the point). Point out precisely which components of the denotational semantics have to be modified to accomodate for the new operation.