Exercises 4: Operational semantics, interpreter

Programming Languages 2010

1. Trace the evolution of the state (the values of variables) when executing the following program statement by statement.

  int main () 
  {
    int low,hi,mx ;
    low = 1 ;
    hi  = low ;
    mx  = 20 ;
    printInt(low) ;
    while (hi < mx) {
      printInt(hi) ;
      hi  = low + hi ;
      low = hi - low ;
      }
  }

2. Write the big-step semantic rules for if statements, both with and without else. Take care of all possible side effects that expressions can have.

3. if statements without else are easy to translate into if statements with else. Show how.

But the inverse is more tricky. Show a counterexample to the following translation

     if (exp) stm1 else stm2   ==> if (exp)  stm1
                                   if (!exp) stm2

and give a one that always works.

4. Consider the subset of JVM consisting of the following instructions.

    bipush n  -- push byte constant n
    iadd      -- add two integers; pop the operands and push the result
    imul      -- multiply two integers; pop the operands and push the result
    istore x  -- store value in stack address x and pop it
    iload x   -- push value from stack address x
    dup       -- duplicate the top of the stack
    iprint    -- print the top-most integer and pop it 
                 (macro for an ``invokestatic/runtime/iprint(I)V``)

Trace the evolution of the stack with the following code.

    bipush 6
    istore 0
    bipush 5
    iload 0
    dup
    iadd
    iadd
    dup
    iprint
    istore 0

Hint: if you do question 5 first, you will get this one for free!

5. Write an interpreter for the subset of JVM consisting of the instructions in the previous question. Notice that you only need integer values in the stack.

You can use pseudocode or real program code. Is your interpreter closer to big step or small step semantics?