BASIC's GOSUB/GRETURN with gcc


Abstract

This document describes a useless experiment that enable a C programmer to go back years and to use the GOSUB/GRETURN system used by the BASIC programming language. No one misses is (we hope) but we wanted to implement it to play a little with a gcc's extension known as "labels as values" and to a have a lot of fun!

Introduction

Sometimes ago, I was going around in CPAN. I do not remember was I was looking for... and I still do not know where I wanted to go.

The only thing that I remember is that I arrived on the Acme::Gosub page.

I would like to specify that the "Acme" namespace, in Perl, is used as a giant container for fun and almost useless things.

When I saw the package, I was astonished... I wanted it too... I wanted it in C!

BASIC's GOSUB/GRETURN

The GOSUB was an early system used by BASIC Language to implement function call. The programmer was able to write a piece of code that was needed many times once and to move to that code just calling it with GOSUB.

The difference between GOSUB and GOTO was that GOSUB stored the caller's position and was able to return to that point calling RETURN at the end of the function.

In many implementations the GOSUB system simply called the function without being able to pass parameters or to receive results back throughout the invocation of return.

More recent versions of the BASIC Language used the SUB/FUNCTION system that was more efficient and flexible.

What we need...

To implement the GOSUB/GRETURN system in C we have to fix some points:

and now, we are ready to begin.

Let's start: we do not want to use the longjump and this is the biggest issue. The only good substitute for longjump (in this case) is obviously goto.

The general idea is to create a system like the one shown below:

  ...
  goto function;
returnpoint:
  ...
function:
  x += 1;
  goto returnpoint;
the function is "called" and at the end of the execution of the function we jump back to the callee.

But... with just goto, we cannot call a function from multiple places and being able to remember where to jump back at the end of the function as in:

  ...
  goto function;
returnpointa:
  ...
  ...
  goto function;
returnpointb:
  ...
function:
  x += 1;
  goto ???; // where should I jump back?

I remember that a lot of time ago, going though the documentation of gcc (with no reason at all... apart from fun), I found a gcc extension that permitted to use "labels as values"... this sounds interesting...

gcc's "Labels as Values"

The gcc's "labels as values" system
described here in details is a simple extension of gcc that enable the labels that are typically used by gotos as values.

With this system, a goto's argument can be any variable of type void*. Moreover, the system is able to extract pointers from labels to be used in a later moment.

At this point, the labels, as any other variable, can be stored in data structures and retrieved later from the same structures.

Being able to store variables is the basis for the solution of the recursion and multiple calling point in the code: the return labels just need to be pushed inside a stack every time a label is called and the address where the code needs to jump back must be simple popped out of the stack... et voilá.

A little note about the gcc's "labels as values" system. I did not browse the code of gcc for that function, but, intuitively, it just takes pointers inside the code segment of memory, instead of pointers inside the data or stack memory. Then, the goto is not implemented with a jump instruction to a predefined address but to an address stored inside another cell of memory.

Stuff things together

Now, we start to implement all the system.

The return stack

As we told before, we want to be able to do recursion and we want to be able to call functions from multiple points without problems. To do this we need to implement a simple stack.

A simple stack is just a list in which we push and pop values from the head of the list or at your option the tail of the list.

We call our structure (in an excess of fantasy) a return point stack. Moreover we need just two functions: a push and a pop operations.

The implementation is straightforward:

typedef struct __basic_rp_stack {
  void *rp;
  struct __basic_rp_stack *next;
} __basic_rp_stack_t;

__basic_rp_stack_t *__rps = NULL;

void __rps_push( void *r ) {
  __basic_rp_stack_t *x = malloc( sizeof(__basic_rp_stack_t) );
  if(!x) abort();
  else {
    x->next = __rps;
    x->rp = r;
    __rps = x;
  }
}

void* __rps_pop( ) {
  if( !__rps ) abort();
  else {
    __basic_rp_stack_t *x = __rps;
    void *r = x->rp;
    __rps = x->next;
    free( x );
    return r;
  }
}

The type of the stack is __basic_rp_stack_t and it is just formed by a void pointer (the address) and a pointer to the next element in the stack (we will use the NULL value as the base of the stack.

We create the stack as a global variable inside the code and we call it __rps.

The __rps_push and the __rps_pop just insert and remove elements from the head of the list. In case of error (malloc failure and/or empty stack in extraction) the functions just call the abort function and exit the program.

We wanted the GOSUB/GRETURN system to be reentrant. To do this we use another extension of the gcc: the __thread keyword.

The __thread keyword, when used before a declaration of a variable, will use such variable like a "thread local storage".

The declaration of the return stack must be changed from:

__basic_rp_stack_t *__rps = NULL;
to:
__thread __basic_rp_stack_t *__rps = NULL;

Get the label, store it and then get it back...

Now, we have the stack and we need to put something in it!

In our idea we would like to write code like the following one, or some code that is equivalent to the following one:

  ...
  __rps_push( &&CALLER );
  goto FUNCTION;
CALLER:
  ...

FUNCTION:
  ...
  void *r = __rps_pop(); // extracts "CALLER"
  goto *r;

Or better we would like to write the code like this:

  ...
  GOSUB( FUNCTION );
  ...

FUNCTION:
  ...
  GRETURN;

To do this, we need to wrap the first code inside macros that are able to create the label for the code following the caller and to hide the push and pop operation.

To create a label for the caller we can use the trick of creating a label name using the number of the line at which we are executing.

C compiles offer the __LINE__ macro that stores the current line of code. We must just concatenate a prefix to the line number and we are done.

To concatenate two code strings at source level we need to use a two steps macro (or better two macros) to do so:

#define __C(a, b) a ## b
#define __U(p, q) __C(p, q)

  ...
__U( __rp, __LINE__ ):
  ...

The __C and __U macros (which stands for concat and unique) take two source strings and concatenate them into an unique name. In our case the two source strings are __rp (the return point) and the line where the return point is.

The Implementation of the GOSUB and GRETURN are just the mix of the macros seen before and the code that we would like to obtain:

#define __C(a, b) a ## b
#define __U(p, q) __C(p, q)

#define GOSUB( LABEL ) do { __rps_push( && __U( __rp, __LINE__ ) ); goto LABEL ; __U( __rp, __LINE__ ) : ; } while(0)
#define GRETURN do { void *__rp = __rps_pop( ); goto *__rp; } while(0)

The whole code!

The whole code is presented here:

#ifndef __BASIC_H__
#define __BASIC_H__

#include <stdlib.h>

typedef struct __basic_rp_stack {
  void *rp;
  struct __basic_rp_stack *next;
} __basic_rp_stack_t;

/* per thread basic return stack */
__thread __basic_rp_stack_t *__rps = NULL;

void __rps_push( void *r ) {
  __basic_rp_stack_t *x = malloc( sizeof(__basic_rp_stack_t) );
  if(!x) abort();
  else {
    x->next = __rps;
    x->rp = r;
    __rps = x;
  }
}

void* __rps_pop( ) {
  if( !__rps ) abort();
  else {
    __basic_rp_stack_t *x = __rps;
    void *r = x->rp;
    __rps = x->next;
    free( x );
    return r;
  }
}

#define __C(a, b) a ## b
#define __U(p, q) __C(p, q)

#define GOSUB( LABEL ) do { __rps_push( && __U( __rp, __LINE__ ) ); goto LABEL ; __U( __rp, __LINE__ ) : ; } while(0)
#define GRETURN do { void *__rp = __rps_pop( ); goto *__rp; } while(0)

#endif /*!__BASIC_H__*/

We inserted the whole code in a header file, calling it basic.h. Now, we are ready to test it.

Limitations of our system

The presented system has some limitations: after all, it is built on top of C using macros.

The first limitation is that the caller and the called code must be in the same function and this is due to a limitation of goto.

The second one is that it is not possible to write 2 calls on the same line:

  ...
  GOSUB( foo ); GOSUB( bar );
  ...
This because our system will generate the same return label for both invocations: the name of the return point is given by the line number inside the code.

Test it all!

The first test is to see if it works. The code below implements an increment. The code calls the inc 100 times and inc every time that it is called increments by one the x variable:

#include <stdio.h>
#include "basic.h"

int
main ( int argc, char **argv ) {
  int x = 0;
  int i = 0;

  for( i = 0; i < 100; ++i ) GOSUB( inc );

  printf( "x = %d\n", x );

  return 0;

 inc:
  ++x;
  GRETURN;

  return 1;
}

We compile and run it:

nids@crimson: basic$ gcc inc.c
nids@crimson: basic$ ./a.out
x = 100
nids@crimson: basic$

It works!!!!

The second test is to test recursion (and to test multiple callers of the sum function too). The code performs the summation of N elements recursively:

#include <stdio.h>
#include "basic.h"

#define NITEMS (5)

int
main ( ) {
   int x = NITEMS;
   int f = 0;

   GOSUB( sum );

   printf( "sum( 0 .. %d ) = %d\n", NITEMS, f );

   return 0;

  sum:
   if( x > 0 ) {
      f += x;
      --x;
      GOSUB( sum );
   }
   GRETURN;

   return 1;
}

We compile and run it...

nids@crimson: basic$ gcc sum.c
nids@crimson: basic$ ./a.out
sum( 0 .. 5 ) = 15
nids@crimson: basic$

It continues to work... incredible!

The third test is to check multi-threading: We repeat the test of inc in a multi-threaded environment:

#include <pthread.h>
#include <stdio.h>
#include "basic.h"

#define TN (5)

void*
th( void * y ) {
  int x = 0;
  int i = 0;

  for( i = 0; i < 1000000; ++i ) GOSUB( inc );

  printf( "tid(%ld) => x = %d\n", pthread_self(), x );

  pthread_exit( NULL );

 inc:
  ++x;
  GRETURN;
}

int
main ( int argc, char **argv ) {
  pthread_t t[TN];
  int ti;

  for( ti = 0; ti < TN; ++ti ) {
    pthread_create( &t[ti], NULL, th, NULL );
  }

  for( ti = 0; ti < TN; ++ti ) {
    pthread_join( t[ti], NULL );
  }

  return 0;
}

We run also this experiment and we are done...

nids@crimson: basic$ gcc inc_mt.c -lpthread
nids@crimson: basic$ ./a.out
tid(140022094514512) => x = 1000000
tid(140022077729104) => x = 1000000
tid(140022086121808) => x = 1000000
tid(140021973645648) => x = 1000000
tid(140021965252944) => x = 1000000
nids@crimson: basic$

It worked: each thread used its own return stack without messing up other threads' stacks.

Conclusions

In this document we learned something about the extensions of the gcc compile: namely the "labels as values" and the automatic thread local storage system enabled by the __thread keyword.

Moreover, we discovered how to implement a little return stack and call system using just macros and the gcc extensions. Our experiment has some limitations.

But the must important thing is that we had a lot of fun!