Getting started with FC++

Contents:

• Downloading and Compiling
• Library Layout
• What are "Functoids"?
• Monomorphic direct functoids
• Beyond monomorphic functoids: "Generic" function objects
• Polymorphic direct functoids
• Example
• Predefined Functionality
• Lazy lists
• Currying (specialization)
• List functions
• Function composition
• Common FC++ Programming Idioms
• Closures
• Indirect functoids
• Advanced/newer features
• Index of Concepts and Primitives

Downloading and Compiling

For a quick example, download the example/test files from the FC++ web page (the test files are separate from the main library). All these files have been tested and compile/run with no problems using g++ (see the compilers page for more info about which compilers do/don't have enough template support to compile FC++). For instance, you can compile Y.cc using the command line:

   g++ -I"fc++ path" -o Y Y.cc

Library layout

config.h     Auto-detects certain compilers/versions to deal with compiler bugs
curry.h      Has the bindMofN() functoids, the curryN() operators, and Const()
full.h       Defines FullN functoid wrappers and makeFullN()
function.h   The indirect functoid classes (FunN) and supporting implementation
lambda.h     The guts of lambda(), its special syntax, LEType
list.h       The List class and its support functoids
monad.h      Defines operations like unit(),bind(); instances like List,Maybe
operator.h   Operators like Plus, many conversion functions, misc
pre_lambda.h A number of forward decls and meta-programming helpers
prelude.h    Functions found in the Haskell Standard Prelude
ref_count.h  Reference-counting pointer classes
reuse.h      The ReuserN classes (which make recursive functoids more efficient)
signature.h  Classes like FunType (used for nested typedefs)
smart.h      Smartness infrastructure and FunctoidTraits class

What are "functoids"?

   First list:  (1, 2, 3)     -\
   Second list: (2, 4, 6)     --> transform() ->  Result list: (3, 6, 9)
   Function:    plus<int>()   -/

The key idea in the example above is that plus<int>() is a function object, which can be passed as an argument to another function. If we had instead wanted to multiply the respective values in the lists in our previous example, we would have passed multiplies<int>() (and gotten the list (2,8,18) back as a result). In the STL, plus and multiplies are examples of "Adaptable Binary Functions". These are function objects which use nested typedefs to name the argument types and result types of the functions. These typedefs enable many of the STL algorithms to work.

In FC++ we use the term "functoids" for function representations. Thus, functoids are classes that are used to represent functions. There are two different kinds of functoids in FC++: direct functoids, and indirect functoids. Each kind of functoid is good for a different purpose. Direct functoids are essential in FC++ programming and will be described here. Indirect functoids will be described later.

Monomorphic direct functoids

Monomorphic direct functoids in FC++ are very similar in functionality to STL adaptable function objects. For example, we could define a function object named "divisible" as

   struct Divisible : public CFunType<int, int, bool> {
      bool operator()( int x, int y ) const { return x%y==0; }
   } divisible;

   divisible( 10, 5 )    // returns true
   divisible( 10, 4 )    // returns false

Note the inheritance from CFunType<int, int, bool>. This is what makes Divisible a monomorphic direct functoid. A monomorphic direct functoid expressing a k-argument function should inherit from a class CFunType<A1, A2, ..., Ak, R>, where A1, ..., Ak are the argument types for the function and R is its return type. The inheritance is used to provide typedefs for the argument types and result types (here the template arguments <int,int,bool> will get named something like Arg1Type, Arg2Type, and ResultType, respectively). Of course, you could "manually" make your classes support the same conventions as monomorphic direct functoids, instead of inheriting from a class like CFunType<...>, but this would be inconvenient.

Note that the above definition differs from an STL-style function class in that we inherit from CFunType rather than from binary_function.
 

Beyond monomorphic functoids: "Generic" function objects

Monomorphic direct functoids are the basis of all functoids in the FC++ library, but they have several limitiations (just like function objects in STL). The most important limitation is that the signatures (argument types and result types) of the objects named by plus<int>, multiplies<int>, and divisible, are all fixed. What if we want to create a truly "generic" function object? For example, what if we want to pass "plus" to an algorithm, but not specify the argument type--if the algorithm happens to be applied to integers, we'll use integer-plus (addition), if the algorithm is applied to strings, we'll use string-plus (concatenation), etc.--how can we do that?

We can easily make a generic function template in C++, like

   template <class T>
   T generic_plus( T x, T y ) {
      return x+y;
   }

but template functions cannot be passed as arguments (we cannot pass the value generic_plus to another function, because it is merely a name, not a value). On the other hand, the standard C++ functor:

   template <class T>
   struct plus : public binary_function<T,T,T> {
     T operator()(const T& x, const T& y) const { return x + y; }
   };

is a class template that requires us to instantiate it with types in order to use it; we cannot talk about just plain plus, we must talk about plus<int> or plus<string>. (Actually, so-called "template-template parameters" do provide a way to decouple the name plus from its type parameter, but this idea does not generalize or scale to provide a general solution framework.) So does this mean all is lost, and that there's no way to talk about generic (polymorphic) function objects in C++? No! Polymorphic direct functoids in FC++ provide the answer.

Polymorphic direct functoids

Direct functoids can be used to describe polymorphic function objects. The key is an idiom that wraps a function template inside a class, so that we can create a concrete object that is still templatized when called as a function. Here's the idea, applied to an addition function:

   struct AlmostPlus {   
      template <class T>
      T operator()( const T& x, const T& y ) const {
         return plus<T>()( x, y );
      }
   } almost_plus;

We've named this "almost plus" because we're not quite done yet. But the general idea is clear. Now we have created an object that can be passed via parameter, and this object is a polymorphic function object in that it can work on multiple types, thanks to the member function template. We've jumped the first hurdle.

Now the only problem is this: as we mentioned above, to enable many higher-order functions, the function objects need to be "adaptable"--that is they need nested typedefs to describe the signature of the function (to name the argument types and result types). How can we do that for our new function object? Using templates, of course!

   struct Plus {
      template <class T, class U>
      struct Sig : public FunType<T,U,T> {};
   
      template <class T>
      T operator()( const T& x, const T& y ) const {
         return plus<T>()( x, y );
      }
   } plus;

Here Sig is a nested template struct, which defines the needed typedefs. It inherits FunType, which, in the case of two arguments, is (roughly) defined as

   template <class A1, class A2, class R>
   struct FunType {
      typedef R ResultType;
      typedef A1 Arg1Type;
      typedef A2 Arg2Type;
   };

Now our solution is complete. If an algorithm gets passed plus as a parameter, and the algorithm intends to pass integer arguments to it and wants to know what the result will be, the algorithm can refer to

   Plus::Sig<int,int>::ResultType

Sig is effectively a "type computer". By using this idiom throughout the library, higher-order polymorphic functions can deduce result types of polymorphic function objects using the general form

   FunctionObject::Sig<ArgumentTypes>::ResultType

We can now summarize all the requirements for direct functoids. To create your own template functoids, you need to create a class with both a template operator() and a Sig member structure template. The operator() will allow your functoid to be polymorphic. The Sig member should be a template over the argument types of the function you want to express. That is, Sig can be used to answer the question "what type will your function return if I pass it these argument types?" For instance, for the two-argument function Plus, Plus::Sig<int, int>::ResultType will be the type returned by Plus for two integer arguments. Sig members are essential in order for other (pre-defined or user-defined) FC++ functoids to be able to interoperate with your functoid. If the direct functoid is monomorphic, there is no need to explicitly define a Sig structure--instead one can be inherited from a CFunType class, as described earlier.

Polymorphic direct functoids can be converted into monomorphic ones for a fixed type signature. This is done using the operators monomorphizeX of FC++ (where X is the number of arguments that the functoid takes). For instance, a monomorphic version of Plus, above, for integer arguments can be obtained using the expression:

   monomorphize2<int, int, int>(plus)

(though there is rarely a reason to do this).

---

Example

   List<int>  li = list_with(1,2,3);
   List<bool> lb = map( even, li );
   // now lb is the list (false,true,false)

  struct Map { 
    template <class F, class L> 
    struct Sig : public FunType<F,L, 
      List<typename F::template Sig<typename L::ElementType>::ResultType> > {}; 

    template <class F, class T> 
    typename Sig<F, List<T> >::ResultType 
    operator()( const F& f, const List<T>& l ) const { 
      if( null(l) ) 
        return NIL; 
      else 
        return cons( f(head(l)), curry2( Map(), f, tail(l) ) ); 
    } 
  }; 

In reality, the signature of map could be somewhat simplified. Instead of:
    List<typename F::template Sig<typename L::ElementType>::ResultType>
one could write:
    List<typename RT<F, typename L::ElementType>::ResultType> >
RT (stands for "Return Type") is just a template that computes the return type of its first argument when it is called with arguments of types equal to the other arguments of RT.

Predefined Functionality

Lazy Lists

FC++ implements a lazy list data structure. Lazy data structures have their data computed when needed, and not in advance. In essence, the data structure holds both data and code that is used to produce more data. This code is called transparently when the extra data are needed. For instance, one can define an infinite list, and only the part that is actually needed will ever be produced. The FC++ lazy lists are compatible with STL algorithms (lazy list iterators support the protocol for STL input iterators) and several conversions are supported between STL data structures and FC++ lazy lists.

We saw an example of lazy list usage in the code for map, above. We reproduce some of this code here:

    template <class F, class T>
    typename Sig<F, List<T> >::ResultType
    operator()( const F& f, const List<T>& l ) const {
      if( null(l) )
        return NIL;
      else
        return cons( f(head(l)), curry2( Map(), f, tail(l) ) );
    }

This code for map produces lazy lists. The lazy-list specific elements in the code above are List, null, NIL, cons, head, and tail. List (note the capitalization) is the C++ type for the lazy list and it is a template parameterized by the type of elements stored in the list. null is a function testing whether the list is empty. NIL is a constant representing an empty lazy list (of any type of stored element!). cons is a function creating a new lazy list node from the data the node will store and the code that produces the rest of the lazy list. head returns the data stored in the first node of a list. tail returns the list beyond the first node of a given list. In the above code, map creates a new list (using cons) that contains as its first node the data produced by function f when applied to the first element of list l (that is, f(head(l)). The rest of the result list is produced by applying map again using function f and the rest of the input list (that is, tail(l)).

Currying (specialization)

Note how the curry2 operator is used in the above code. curry2 takes a a 2-argument functoid as its first argument. It produces a specialized functoid that binds the first arguments of curry2's first argument to the rest of the arguments of curry2 (however many they are). That is, curry2(Map(), f, tail(l)) creates a new functoid that does the same computation as map(f, tail(l)). The new functoid takes no arguments (as we have fully specialized map by supplying two arguments). curry2 could have been called with 2 arguments, e.g., map and a function, in which case it would only fix the first argument of map and produce a 1-argument functoid that can be applied to a list.

In general, FC++ supplies curryN operators (N is an integer constant up to a predefined maximum) that specialize the first arguments of an N-argument functoid. Additionally, FC++ provides operators bindXandY...ofN  that specialize (i.e., fix) the X-th, Y-th, etc. arguments of an N-argument functoid. For instance,  bind1and3of3(f, 2, 4) will fix the first and third arguments of a 3-argument functoid f to 2 and 4, respectively.

Note: in recent revisions of the library (since version 1.2), functoids are curryable by default. See the currying page for more info. As of version 1.5, currying is now subsumed by full functoids.

Other List Functions

There is a lot of functionality (i.e., algorithms) for lazy lists defined by FC++. These functions are mostly re-implemented from functional language libraries, especially the Haskell Standard Prelude. We will not exhaustively document these functions here, but the FC++ examples are an excellent way to become familiar with them. The most common such functions include map, foldl, foldr, scanl, scanr, iterate, drop, cycle, replicate, length, at, until, filter, concat, take, etc.

Function Composition

A way to produce new functoids in FC++ is by composing existing functoids. The functoid class that composes two existing functoids is Compose1. (An instance of it is defined and it is called compose.) For instance, the expression:

   compose(head, tail)

creates a new functoid that implements the composition of head and tail--i.e., an operation returning the second element of a list. More importantly, that composition is polymorphic, exactly the same way as head and tail are polymorphic: it can be applied to (homogeneous) lazy lists holding elements of any type.

Common FC++ Programming Idioms

Closures

A common idiom in functional programming is encapsulating code together with the data that it operates on. This is called "creating a closure". Encapsulation is also the basis of object-oriented programming, so creating closures in FC++ should seem quite intuitive if you are a C++ programmer. To create a closure in FC++, one needs to create a functoid class (implementing a function) and add data members to this class. The constructor for the functoid class can then be used to initialize this data. Hence, an FC++ closure is just a functoid object (an instance of a functoid class) and closing just means creating a functoid object.

The FC++ implementation contains multiple examples of closure usage (hint: look for classes named <Something>Helper in the FC++ code). Consider the implementation of the curry2 function (discussed earlier). curry2 called with 2 arguments returns a new functoid object, that specializes curry2's first argument by fixin its first argument. That new functoid object is really a closure, as it needs to hold the value for the specialized argument. The implementation is shown below and the extra elements of a closure functoid (member variables, constructor) can be seen clearly:

 template <class Binary, class Arg1>
 class binder1of2 {
    Binary f;
    Arg1 x;
 public:
    binder1of2( const Binary& a, const Arg1& b ) : f(a), x(b) {}

    template <class Arg2>
    struct Sig :
       public FunType<Arg2,typename Binary::template Sig<Arg1,Arg2>::ResultType> {};

    template <class Arg2>
    typename Binary::template Sig<Arg1,Arg2>::ResultType
    operator()( const Arg2& y ) const {
       return f(x,y);
    }
 };

Indirect Functoids

Even more seriously, however, not being able to define variables over direct functoids means that there is no way to store direct functoids in dynamic data structures. For instance, one cannot create a (homogeneous) list of direct functoids--that is a list whose every member is a potentially different functoid (but they all have the same signature).

Indirect functoids address the above problems. All indirect functoids are subclasses of a class FunN, where N is the number of arguments that the indirect functoid takes. Indirect functoids are usually created from monomorphic direct functoids using the makeFunN operators in FC++. (Indirect functoids can also be created explicitly by subclassing the FunNImpl class, but this functionality will not be covered here.) If "plus" and "multiplies" are monomorphic direct functoids from integers to integers, a typical use of indirect functoids would be:

   Fun2<int, int, int> f = makeFun2(plus);
   cout << f(3, 5) << endl;      // Prints 8
   f = makeFun2(multiplies);
   cout << f(3, 5) << endl;      // Prints 15

   Fun2<int, int, int> f = makeFun2(monomorphize2<int,int,int>(plus));
   cout << f(3, 5) << endl;      // Prints 8
   f = makeFun2(monomorphize2<int,int,int>(multiplies));
   cout << f(3, 5) << endl;      // Prints 15

   Fun2<int,int,int> f = plus;

Advanced/newer features

The tutorial here does not address all of the features of the library. The site map contains a list of all of the pages on the FC++ web site; visit each page to learn about all of the features.

---

Index of Concepts and Primitives

bindXandY...ofN
CFunType
Compose1, compose
curryN
FunX (indirect functoid superclass)
FunType
makeFunX
monomorphize
RT
Sig structure template

Last updated on May 29, 2003 by Brian McNamara