Based on David's suggestion, I'll try to briefly define all the terms I've used in my earlier post.
> Brian McNamara <[EMAIL PROTECTED]> 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 ([EMAIL PROTECTED]) _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
