Function Representation

Functional code uses the machine stack for function return addresses.

A function type object is an abstract class with a pure virtual method called apply which returns a representation of the codomain and accepts a representation of the domain.

A function is derived from its type and implements the apply method.

Function closures in Felix are pointers to function type objects, therefore all functions of the same type are represented by a pointer to the same C++ class. The actual function is called by virtual dispatch.

The function class constructor is used to store a pointer to the thread frame object and the display, which is the list of the most recent activation records of the ancestors of the function at the time the closure was created. The function can use the display to access the ancestor local variables.

The objects pointer to by the display members can be either function or procedure frames. Here is an example.

Felix code:

noinline fun k(z:int) = {
  fun f(x:int) = {
    var y = x;
    return  y + z;
  }
  return f;
}

Function types

//TYPE 52224: int -> int
struct _ft52224 {
  typedef int rettype;
  typedef int argtype;
  virtual int apply(int const &)=0;
  virtual _ft52224 *clone()=0;
  virtual ~_ft52224(){};
};

Function class:

struct thread_frame_t;

//FUNCTION <50810>: k int -> (int -> int)
//    parent = None
struct k {
  thread_frame_t *ptf;

  int z;
  k(thread_frame_t *);
  k* clone();
  _ft52224* apply(int const &);
};

//FUNCTION <50812>: k::f int -> int
//    parent = k<50810>
struct f: _ft52224 {
  thread_frame_t *ptf;
  k *ptrk;

  int x;
  int y;
  f  (thread_frame_t *, k*);
  f* clone();
  int apply(int const &);
};

Function apply methods:

//FUNCTION <50812>: k::f: Apply method
int f::apply(int const &_arg ){
  x = _arg;
  y  = x; //init
  return y + ptrk->z ;
}

//FUNCTION <50810>: k: Apply method
_ft52224* k::apply(int const &_arg ){
  z = _arg;
  return (new(ptf->gcp, f_ptr_map) f(ptf, this));
}

Clone methods:

//FUNCTION <51331>: k: Clone method
  k* k::clone(){
  return new(*PTF gcp,k_ptr_map,true) k(*this);
}

//FUNCTION <51333>: k::f: Clone method
  f* f::clone(){
  return new(*PTF gcp,f_ptr_map,true) f(*this);
}

Constructors:

//FUNCTION <51331>: k: Constructor
k::k(thread_frame_t *ptf_) ptf(ptf_) {}


//FUNCTION <51333>: k::f: Constructor
f::f
  (
    thread_frame_t *ptf_
    k *pptrk
  )
  ptf(ptf_), ptrk(pptrk) {}

The symbol gcp is a pointer to the garbage collector profile object. The symbol f_ptr_map is a pointer to the static run time type information for f which is associated with the store allocated for the closure of f created to the collector can trace it. This is necessary because the closure of f contains a pointer to a closure of k, as well as the thread frame object.

The type of k is elided because Felix knows the function not formed into a closure, this is an optimisation.

The clone method (not show) invokes the copy constructor, it is used when calling the function to ensure the initial state is invariant. This may be necessary if the function is called twice through the closure, particularly if it is recursive.

Non-Yielding Generators

A non-yielding generator has the same representation as a function, except that the clone method returns this instead of a pointer to a heap allocated copy of the class object.

Whilst function values stored in variables are cloned to ensure they have an invariant initial state, generators aren’t, to ensure internal state is preserved between calls.

Yielding Generators

A yielding generator is a generator with a yield statement. Yield returns a value and saves the current program counter.

The apply function body is called then the function jumps to the saved program counter. Note that the parameter is set to the argument of each invocation.

gen f (var x:int) = {
  var i = 10;
  while i > 0 do
    yield x;
    --x; --i;
  done
  return 0;
}

var k = f;

var v = k 4;
while v > 0 do
  println$ v;
  v = k 2;
done

This program prints 4 once then 1, nine times.

The usual way to write generators is to use a higher order function:

gen f (var x:int) () = {
  while x > 0 do
    yield x;
    --x;
  done
  return 0;
}

var k = f 4;

var v = #k;
while v > 0 do
  println$ v;
  v = #k;
done

The header looks like this:

//FUNCTION <51331>: f int -> (unit -> int)
//    parent = None
struct f {
  thread_frame_t *ptf;

  int x;
  f(thread_frame_t *);
  f* clone();
  _ft52601* apply(int const &);
};

//FUNCTION <51333>: f::f'2 unit -> int
//    parent = f<51331>
struct _fI51333_f__apos_2: _ft52601 {
  thread_frame_t *ptf;
  int pc;
  f *ptrf;

  _fI51333_f__apos_2  (FLX_FPAR_DECL f*);
  _fI51333_f__apos_2* clone();
  int apply();
};

The apply method looks like this:

//FUNCTION <51331>: f: Apply method
_ft52601* f::apply(int const &_arg ){
  x = _arg;
  return
    new(*ptf->gcp,_fI51333_f__apos_2_ptr)
      _fI51333_f__apos_2 (ptf, this)
  ;
}

//FUNCTION <51333>: f::f'2: Apply method
int _fI51333_f__apos_2::apply(){
  switch (pc) {
    case 0:
    continue__ll_x_102_L51335:;
      if(!(0 < ptrf->x))
        goto break__ll_x_102_L51336;
      pc = 52614
      return ptrf->x;//yield
    case 52614:
      {
      int* _tmp52615 = (int*)&ptrf->x;
      --*((_tmp52615));
      }
      goto continue__ll_x_102_L51335;
    break__ll_x_102_L51336:;
      return 0;
  }
}

With gcc compiler, a computed goto is used instead of a switch.