CIS 425 Homework VIII

Understanding Labels (Extra Credit!)

Simple Labels and Goto

In a language with goto, the target of a jump is typically specified by a label.

------------------------------------------------------------------------
...
L: ... // this statement is labelled L
...
goto L; // this causes the control flow to go to the statement labelled L
...
------------------------------------------------------------------------

In the absense of nested scopes, labels and jumps are simple. In general they are a bit subtle. To see the problem consider the following C program:

------------------------------------------------------------------------
#include < stdio.h >

void main () {
  int flag = 0;
  { 
    int i=1;
  L: printf ("i = %d\n", i);
    if (flag) return; 
    else { 
      int i = 2;
      printf ("i = %d\n", i);
      flag = 1;
      goto L;
    }
  }
}
------------------------------------------------------------------------

Executing the second statement labelled L, prints i=1, then: we enter a new block, declare a new variable called i, print i=2, and jump back to the outer scope to print i. But which i? Note that the C compiler managed to restore the correct environment during the jump so that last printf statements prints i=1!

Based on this example, and on your understanding of closures, what is, conceptually speaking, the representation of a label?
The example above shows what happens when you jump from an inner block to an outer block. C does not allow you to jump from an outer block to an inner block but languages as old as Algol 60 allowed this. Write an example in pseudo-C that would illustrate jumping inside a block, and explain how your program would execute and what values it would return or print.

Setjmp/Longjmp

The C library routines setjmp and longjmp generalize labels and goto in the following sense. A setjmp is a like a label and a longjmp is like a goto, but unlike basic labels and gotos, setjmp and longjmp work across functions and can communicate values during the jump. Here is an example,

------------------------------------------------------------------------
#include < stdio.h >
#include < setjmp.h >

/*
 buffer used for communicating results from the point 
 we are jumping from to the point we are jumping to
*/
jmp_buf k; 

/* 
 a silly function that performs a few recursive calls, and then jumps
 to the point labelled with setjmp (which is in main)
*/
int f (int i) {
  if (i == 0) longjmp(k, 42);
  else return i*f(i-1);
}

void main () {
  /*
   the setjmp does two things: 
   1. it returns 0 
   2. it sets a label to which a longjmp can later jump
  */
  int result = setjmp(k);
  switch (result) {
  case 0: f(5); break; // normal execution goes here
  default: printf("f(5) = %d\n", result); break; // we get here by longjmp 
  }
}
------------------------------------------------------------------------

The program prints 42.

Write a program using setjmp/longjmp which does a conventional recursive binary search of an array but that immediately jumps out with the result when found.

Try running the following program and explain what's going on based on your understanding of closures:

------------------------------------------------------------------------
#include < setjmp.h >

jmp_buf k; 

int f (int i) {
  if (i == 0) return setjmp(k);
  else return i*f(i-1);
}

void main () {
  int result = f(5);
  longjmp(k,42);
}
------------------------------------------------------------------------

Visited

times since September 21, 1999 (or the last crash).

sabry@cs.uoregon.edu