Functoids In Cpp

FunctoidsInCpp is about the library Functional Programming in C++ (FC++) written by Brian McNamara and Yannis Smaragdakis which is described at http://people.cs.umass.edu/~yannis/fc++/ and http://cgi.di.uoa.gr/~smaragd/fc++/ and also mentioned in CppTemplateMetaprogramming (book).

The library includes polymorphic functoids and also a language for LambdaExpressions. The user can convert a function into a full functoid which can be curried. The intention of the original authors was to provide for programming in the style of HaskellLanguage within CeePlusPlus.

There is an interesting history, in that it was considered a few years ago for inclusion in the BoostLibraries. This was not proceeded with, but has lead to a situation where there exists a boostified version which uses the boost namespace. This is not now being actively developed, but there are extensions being made to the previous version FC++.1.5 with a view to a new release. This involves increasing the maximum number of parameters on functions and functoids from 3 to 4. I have made use of this to build LazyEvaluation into my software for CliffordAlgebra.

-- JohnFletcher

This is one of the HeaderOnlyCeePlusPlusPackages.

February 2007 There is now a sourceforge site for this software at http://sourceforge.net/projects/fcpp. For the moment this is a release of the last version on the old web site. Further versions are being planned.

February 2008 I have gone on extending this to provide for more parameters. 4 and 5 parameters functions are well supported, and work now extends to 6 and 7 parameters. This may seem extravagant. They are needed for the implementation of the FunctionalPatternSystemForObjectOrientedDesign - see ObjectFunctionalImplementation.

November 2009 I have been developing VariadicFunctoidsInCpp. This extends FunctoidsInCpp so that there can be functoids (e.g. plusN) with an arbitrary number of arguments. I have also been exploring interworking with the BoostLambdaLibrary, using methods similar to the interworking with the StandardTemplateLibrary already in FC++. See an example of this on VariadicFunctoidsInCpp.

December 2009 I have extended the work on ObserverPatternInCeePlusPlus to include LazyPtrProxy.

January 2010 I have been working on extending LogicProgrammingInCpp. That is quite interesting, as the code turns out to be a very good example of ContinuationPassingStyleInCeePlusPlus.

I have also found a page here on FunctionalReactiveProgramming. That set me off to see if anyone had ever done work on this in C++. Most of the work on I have found so far has been based on HaskellLanguage and that means that (I think) it should be possible to build it on top of the FC++ implementation of a good deal of Haskell primitives. So far I have only found one such paper which is SpecifyingBehaviorInCpp. If anyone else knows anything about this or further work please contact me.

May 2011 I have added invcompose (inverse composition) based on work on the pages FunctionalComposition and InverseFunctionalComposition.

March 2012 I am having some problems with FC++ when compiling with CeePlusPlusEleven. The problem occurs when working on lists with members which are std::pair. The copy constructor is deleted, see ImplicitlyDeletedCopyConstructor, so the code does not compile. I have now overcome these problems, working with Clang(CeeLanguageFamilyFrontEnd) as the compiler. I am now looking at a new version of FC++ using the new facilities of CeePlusPlusEleven. This is looking quite promising.

June 2012

An era has ended with the removal of the original FC++ web site which has been there for many years. It is clear that FC++ has been influential on the ideas of others who have put together a number of other libraries, many of them included in the BoostLibraries although it never has been. BoostPhoenixLibrary in particular acknowledges it. It is interesting that the lambda now included in CeePlusPlusEleven is not polymorphic.

November 2013

I have been working to understand better the monads implemented in FC++. I had previously added an Either monad. I have now found some interesting things in PatternsInFunctionalProgramming which has lead me to include some new functoids in the prelude.

Warning In the code as released, some functions on a non terminating lazy list will never return. One obvious example is the following:

  length(enumFrom(1));

There is an exception mechanism but it has not been used for this. I am putting a maximum length on the list type and then throwing an exception to avoid a computer crash.

February 2014

For years, as you can read above, I have been working away quietly on this, and not making any impression on anyone. I started to think that there was synergy between FC++ and some of the BoostLibraries and in particular the BoostPhoenixLibrary. As a result of my expressions of interest I have now become the maintainer of the BoostPhoenixLibrary and will be looking for ways to use FC++ there.

-- JohnFletcher

Example

   int bar(int a,int b,int c,int d)
   { cout << "baa baa baa baa" << endl; return 0; }
   int bar3(int a,int b,int c)
   { cout << "baa baa baa" << endl; return 0; }

For the above functions, the following are all defined to be valid C++ using FC++.

   Fun4<int,int,int,int,int> poobah = ptr_to_fun(&bar);
   Fun3<int,int,int,int> poobah3 = ptr_to_fun(&bar3);
   bind1and2and3and4of4( poobah, 1,1,1,1) ();
   bind1and2and3and4of4( poobah ) (1,1,1,1) ();
   bind1and2and3of3( poobah3, 1,1,1) ();
   bind1and2and3of3( poobah3)(1,1,1) ();
   poobah3 (1,1,1);

Binders exist for all combinations of the parameters e.g. bind2of3, bind1and3of4 etc.

A full functoid version can be as follows.

  namespace myimpl {

  struct XBAR {
    template<typename U, typename V, typename W, typename X> struct Sig;
    // For the moment assume all the same
    template <class T> struct Sig<T,T,T,T>: public FunType<T,T,T,T,T> {};
    template <class T>
    T operator()( const T& a, const T& b, const T& c, const T& d) const {
      cout << "baa baa baa baa" << endl;
      return T(0);
    }
  } xbar;

  }
  typedef Full4<myimpl::XBAR> BAR;
  BAR newbar;

This defines a function called newbar which can be called with arguments of any type, all the same in this example.

   cout << newbar (1,1,1,1) << endl;
   cout << newbar (1.5,1.5,1.5,1.5) << endl;

I have been involved with these developments. The examples compile and run with GnuCpp. -- JohnFletcher

Usually it is illegal to specify template specialization within a class descriptor.

Do you have any reference for this statement? If so please post it here, as this is widely used in FC++. Note that the inner objects being specialised are structs, not member functions. -- JohnFletcher

Unless something has changed since the 2003 standard, template specializations must occur at the namespace scope, structs or otherwise. I'll admit to not keeping up with this... I know this only because it nipped me in the arse a few months back when I was playing around with TemplateMetaProgramming? (e.g. the all-combos 'nwise' file I wrote up). Visual Studio allowed it, but GCC 3.4 did not. I do not have a reference for it, but I recall being quite frustrated with it, and actually looking it up (I wanted to blame the compiler rather than my code...).

Further, the compile-time cost of doing so can be very high (given that return type can vary considerably based on the input types). This cost should be minimized by, as much as possible, sharing signatures between functoids... e.g. by using a typedef to a signature-generator structure that may be shared between many different functoids, or might be in a little detail namespace.

   struct xbar {
      typedef CPType siggen; // TMPL type that maps input-types to output type.
      // return_type<...> can handle all the gritty 'typename siggen::template gen<T,T,T,T>::type details'
      template<typename T> typename return_type<siggen,T,T,T,T>::type   
      operator()(const T& a, const T& b, const T& c, const T& d) {
         typename ltype<siggen,T,T,T,T>::type result(0);
         cout << "baa baa baa baa" << endl;
         return result;
      }            
   }; 

   XBAR()(1,1,1,1);
   XBAR()(1.5,1.6,1.7,1.8);

   // To get the nice little partial-application facilities you mentioned, you'll need to still wrap this effectively in Fun4.

The FC++ equivalent of what you are describing is the set of FunType template classes which define the return types. I am currently looking at the implications of ConceptCpp in the new proposed C++ standard, which will make some of this work much easier. See FunctoidsInCppWithConceptCpp. -- JohnFletcher

Even so, my experiences with TemplateMetaprogramming (in particular, with running out of memory when performing insertion-sorts and very-deep template method calls) has me suggesting you shift the internal template entirely out of the class. XBAR::Sig<T1,T2,T3,T4> is still different from FOOBAR::Sig<T1,T2,T3,T4> even if both inherit from FunType<T1,T2,T3,T4>. They'll each consume memory at compile-time. It might not seem like much (and it isn't), but it adds up quickly when performing TemplateMetaprogramming in certain manners... e.g. very deep function calls construction operators that use lots of N-type tuples and such.

The real trick is figuring out how C++ automatically recasts the inputs, and handling this detail in the signature generator... e.g. the siggen with 'double,float,int,long' as input types is quite possibly necessary.

   double d = 1.2;
   float  f = 1.3;
   int    i = 1;
   long   l = 2;
   XBAR()(d,f,i,l);

C++ might cast this to double,double,double,double or might complain, depending on implementation.

I have been using PromotionTraits to sort out this sort of problem. I have worked on this quite a lot since I wrote this page originally. -- JohnFletcher

Nasty meta-code, ain't it? ^_^

April 2012 I can now replace the promotion traits with use of auto and decltype from CeePlusPlusEleven.

Discussion moved to FunctoidsInCppDiscussion.

Examples of use are to be found at ContinuationPassingStyleInCeePlusPlus ContinuationPassingStyleInCppQuadraticEquationExample FunctoidsInCppExperiment

CategoryCpp CategoryCppTemplates CategoryFunctionalProgramming CategoryMultiparadigm