PLT11 course -- assignment 6

(C) Ralf Lämmel, Andrei Varanovich, University of Koblenz Landau

Logistics

Assignment

The following positions can be approached independently.

Presentations by student teams would also just show ONE position.

(You may want to solve several positions to increase chances of presenting.)

1. A language with allocation

Let us consider a language with expressions (such as addition), variables, and assignments.

The variables, though, are of a special kind: they store pointers.

Accordingly, there is a language construct for "allocation" of memory cells.

There is a dereferencing construct so that the allocated memory cell can be accessed.

For example:

% Allocate cells and assign them to variables.
x = alloc;
y = alloc; 
r = alloc;

% Copy pointer from y to z.
z = y;

% Store values in the cells.
^x = 20;
^y = 22;
^r = ^x + ^z;

Execution of this program should result in r pointing to a cell that holds 42.

Disclaimer: the code is untested because the language, as of writing, is unimplemented.

Develop abstract syntax and operational semantics for this language.

You are welcome to also develop a type system for the language.

2. A stack-based language

Let us consider a stack-based language that can perform basic and compound operations as follows:

  • push x;: pushes integer x onto the stack.
  • dup;: duplicates the top-of-stack.
  • bubble i;: bubbles up the i-th element to the top-of-stack.
  • pop;: pops an element of the stack.
  • add;: replaces top-of-stack and second-on-stack by their sum.
  • mult;: replaces top-of-stack and second-on-stack by their product.
  • {o1 … on}: sequences of operations
  • whileNotZero o: executes o while top-of-stack is not zero.

For example, consider the following definition of factorial:

push 1; % initialize result
bubble 1; % make argument (second-of-stack) top-of-stack
whileNotZero 
{
 dup; % duplicate argument
 push -1; % prepare decrement
 add; % decrement
 bubble 1; % make argument top-of-stack
 bubble 2; % make intermediate result top-of-stack
 mult; % multiply argument and intermediate result
 bubble 1; % make decremented argument top-of-stack
}
pop;

Develop abstract syntax and operational semantics for this language.

Disclaimer: the code is untested because the language, as of writing, is unimplemented.

3. A type system for stack correctness

Develop a type system for the stack-based language.

The type of an operation denotes two values (m,d):

  • the minimum stack size m required.
  • the change d in stack size.

For instance, the factorial code is of type (1,0).

page revision: 11, last edited: 14 Dec 2011 15:36
Edit Tags History Files Print Site tools + Options