PLT11 course -- assignment 6

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

# 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
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