Re: [boost] Re: Preliminary submission: FC++

From: Brian McNamara (lorgon_at_[hidden])
Date: 2003-07-28 23:43:21

Based on David's suggestion, I'll try to briefly define all the terms
I've used in my earlier post.

> Brian McNamara <lorgon_at_[hidden]> writes:
> > I have posted the first "boostified" version of FC++ to the YahooGroups
> > files section; it is called "fcpp".
> >    http://groups.yahoo.com/group/boost/files/
> >
> > ----------
> > Background
> > ----------
> > FC++ is a library for functional programming.  In FC++ we program with
> > "functoids" (classes which define operator() and obey certain other
> > conventions).  The library features include:

In the latest version of the library, we discriminate among a few kinds
of "functoids":
 - A "basic" functoid is a class which defines a (possibly templated) 
   operator() function, as well as a templated "sig" member structure.
   (The "sig" in FC++ is analogous to the "result" structure for
   the proposed result_of construct for computing result types.)
 - Most functoids are "direct" functoids, as they call their
   implementation function directly.  In contrast, "indirect" functoids
   use dynamic dispatch (virtual function call), in order to create
   function variables.  FC++ indirect functoids are almost completely
   analogous to boost::function objects:
      fcpp::fun2<int,int,int> f = fcpp::plus;  // select (int,int)->int
      f(3,2);   // yields 5
      f = fcpp::minus;
      f(3,2);   // yields 1
 - Indirect functoids must always be "monomorphic" (non-templated).
   That is, given an indirect functoid (like "f" above), it expects a
   fixed set of arguments types (e.g. "int"s).
 - Direct functoids can be "polymorphic" (templated).  For example, 
   fcpp::plus is polymorphic:
      plus(3,3);        // yields int 6
      plus(2.2,2.2);    // yields double 4.4
      plus(s,s);        // if s is std::string("foo"), yields "foofoo"
   Unlike indirect functoids, you can't create variable direct
   functoids.  The type of the object fcpp::plus is fcpp::plus_type.
 - "Full" functoids are basic functoids which have been wrapped by the
   fullN wrapper class.  Full functoids add extra FC++ functionality,
   like currying, lambda awareness, and infix syntax (see below).

(Note that the FP community uses "polymorphism" to mean "templates",
whereas the OO community uses the term to mean "dynamic dispatch".  
An unfortunate overloading of terms.  As you can see, we use the FP
definition throughout the FC++ documentation.)
  
> >  - higher order, polymorphic (template) functions (direct functoids)

Higher order functions are functions which take other functions as
arguments or return functions as results.  In FC++, since we represent
polymorphic (template) functions as direct functoids (which, unlike C++
function templates, are C++ objects which can be passed around as
parameters), we can implement functions which are simultaneously
higher-order and polymorphic.  An example is compose:
   // compose(f,g)(args) = f( g(args) )
If add_self is this polymorphic function:
   // add_self(x) = x + x
Then we can write
   compose( add_self, add_self )( 3 );   // yields 12
   compose( add_self, add_self )( s );   // yields "foofoofoofoo" (s as above)
(This feat was a novelty when FC++ was new, but is becoming more
mainstream in C++ now, owing to the more general knowledge of
techniques along the lines of result_of, which enables the result 
type of template functions to be named.)

> >  - lazy lists

More generally, a number of data structures and functions which employ
lazy evaluation.  As an example,
   fcpp::list<int> l = enum_from(1);
results in "l" being the infinite list of integers [1,2,3...].  The
elements in the list are not computed until they are demanded (lazy
evaluation).  

> >  - library of useful functions, combinators, and monads (mostly
> >    mimicking the Standard Library of the language Haskell)

"Combinators" are higher-order functions.  (Definitions of the term
"combinator" seem to vary from community to community.)  Monads cannot
be defined in a sentence or two, so I won't try.

(Much of FC++ was designed to imitate Haskell, which is kinda the
"cutting edge, mainstream" pure functional language.)  

> >  - currying

Given some 3-argument function "f":
   f(x,y,z)      // normal call
   f(x,y)        // new function "g", where g(z)=f(x,y,z)
   f(x)          // new function "g", where g(y,z)=f(x,y,z)
   f(x,_,z)      // new function "g", where g(y)=f(x,y,z)
   etc.
FC++ full functoids exhibit built-in currying.  This is basically a
terser syntax for what boost::bind does.

> >  - infix function syntax

Given a two-argument function "f":
   x ^f^ y      // same as f(x,y)
This is syntax sugar.  Often things like
   x ^plus^ 3
are easier to read than
   plus(3,x)
because it seems more natural.  (Haskell uses ` instead of ^)

Of course, if f is a 3-arg full functoid, then
   x ^f^ y    // new function "g", where g(z)=f(x,y,z)

> >  - dynamically bound functions (indirect functoids)

Described above.

> >  - effect combinators

Suppose "write_log" is a function which takes a string and writes it to a
log file, and "do_foo" is a function that does "something".  Then
   before( curry1(write_log,"about to call do_foo"), do_foo )
results in a new function which behaves just like do_foo() except that
it writes a message to the log file before executing.  "before" is an
"effect combinator"; it prepends an effect onto an existing function.

(Note that the construct "curry1(f,x)" creates a thunk of "f(x)", that is
   curry1(f,x)    // new function "g", where g()=f(x)
The name curryN is a historical misnomer; I should really change it in
the boostified version of FC++.)

> >  - interfaces to STL via iterators

E.g.
   fcpp::list<int> l( v.begin(), v.end() )
   ... l.begin() ...

> >  - ways to transform normal C++ functions/methods into functoids

   fcpp::ptr_to_fun( foo )
Results in a full functoid, regardless if "foo" is a function pointer,
or a method pointer, or an STL adaptable function, or whatnot.

> >  - a lambda sublanguage, with syntax for lambda, let, letrec,

Somewhat similar to boost::lambda (the lambda library), but with a
number of markedly different design decisions.

> >    do-notation, and monad comprehensions

More monad stuff I won't try to explain.

David also said:
> "polymorphic function" (please give *complete* definitions).  Also, I
> know the docs are going to discuss "2nd order polymorphic functions"
> at some point, if I can get that far.  Please define that too.

The functional programming community will sometimes talk about "rank-N
polymorphism", where N is some integer.  A (mildly) interesting feat is
to be able to implement this (I'm inventing random syntax; hopefully
you'll get the gist):

   // Use normal function notation.  
   // Use <> for tuples (e.g. <1,2> is a pair).
   let apply1( f, x ) = f(x,x)
   let apply2( f, x, y ) = < f(x,x), f(y,y) >
         
   // Example of rank-1 polymorphism
   apply1( plus, 3 )      // yields 6
   apply1( plus, "foo" )  // yields "foofoo"

   // Example of rank-2 polymorphism
   apply2( plus, 3, "foo" )      // yields < 6, "foofoo" >

Note that apply1() is polymorphic (it works on arguments of different
types), but inside apply1(), f is used only monomorphically.  Inside
apply2(), f is used polymorphically (used on two different types during
one invocation of the function).  Being able to implement rank-2
polymorphism in FC++ was somehow notable to the functional programming
community.  (In fact, FC++ (C++) implements arbitrary rank
polymorphism, since templates just get "expanded out" by the compiler
at compile-time.  Conversely, most FPL implementations use a uniform
representation, which makes rank-N polymorphism less straightforward to
implement.)

Hope that helps a bit.

I should note that the description above outlines the general
capabilities of the library, but says little about its actual contents.
The library defines probably 100 or so functoids and maybe 10 data
structures; most of these mimic Haskell's standard library and are just
your basic assortment of useful stuff for doing FP.

-- 
-Brian McNamara (lorgon_at_[hidden])