How Can Currying Be Done in C++

Is there a way to do currying in C?

I found a paper by Laurent Dami that discusses currying in C/C++/Objective-C:

More Functional Reusability in C/C++/Objective-c with Curried Functions

Of interest to how it is implemented in C:

Our current implementation uses existing C constructs to add the currying mechanism. This was much easier to do than modifying the compiler, and is sufficient to prove the interest of currying. This approach has two drawbacks, however. First, curried functions cannot be type-checked, and therefore require careful use in order to avoid errors. Second, the curry function cannot know the size of its arguments, and counts them as if they were all of the size of an integer.

The paper does not contain an implementation of curry(), but you can imagine how it is implemented using function pointers and variadic functions.

How can currying be done in C++?

In short, currying takes a function f(x, y) and given a fixed Y, gives a new function g(x) where

g(x) == f(x, Y)

This new function may be called in situations where only one argument is supplied, and passes the call on to the original f function with the fixed Y argument.

The binders in the STL allow you to do this for C++ functions. For example:

#include <functional>
#include <iostream>
#include <vector>

using namespace std;

// declare a binary function object
class adder: public binary_function<int, int, int> {
public:
    int operator()(int x, int y) const
    {
        return x + y;
    }
};

int main()
{
    // initialise some sample data
    vector<int> a, b;
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);

    // here we declare a function object f and try it out
    adder f;
    cout << "f(2, 3) = " << f(2, 3) << endl;

    // transform() expects a function with one argument, so we use
    // bind2nd to make a new function based on f, that takes one
    // argument and adds 5 to it
    transform(a.begin(), a.end(), back_inserter(b), bind2nd(f, 5));

    // output b to see what we got
    cout << "b = [" << endl;
    for (vector<int>::iterator i = b.begin(); i != b.end(); ++i) {
        cout << "  " << *i << endl;
    }
    cout << "]" << endl;

    return 0;
}

How would you curry in C

This was the answer I was looking for.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

/* Type defining the function returns */
typedef uint32_t (*addCur)(uint32_t ad);
typedef addCur (*multiply)(uint32_t m);

multiply multiplyAndAdd(uint32_t x) {
    addCur doMultiply(uint32_t m) {
        uint32_t mx = m*x;

        uint32_t doAdd(uint32_t c) {
            return mx + c;
        }

        return doAdd;
    }

    return doMultiply;
}

int main(int argc, char **argv) {
    uint32_t a = 4, b = 5, c = 6;

    if(argc > 1)
        a = atoi(argv[1]);
    if(argc > 2)
        b = atoi(argv[2]);
    if(argc > 3)
        c = atoi(argv[3]);

    uint32_t result = multiplyAndAdd(a)(b)(c);
    printf("result: %d\n", result);

    return 0;
}

It helped to type define the return type of each method. This enables the methods to be more legible. In turn, this allowed me to chain the returns of each method easier.

As mentioned in the comments, this is potentially dangerous code as there is no guarantee that the stack allocated functions will even exist when the function returns. But I was merely mused at the prospect of whether it could be done in theory without significant amount of code.

Functional Programming (Currying) in C / Issue with Types

An interesting question and I took a look at the paper in the answer cited (More functional reusability in C/C++/Objective-C with Curried functions).

So following is a suggested path to where you might want to go. I do not think this is truly a Curried function as I do not fully understand what the paper is talking about, not being a functional programmer. However, doing a bit of work, I find an interesting application of some of this concept. I am not sure this is what you want on the other hand, it kind of blows my mind that you can do this in C.

There seemed to be two problems.

First of all was to be able to handle arbitrary function calls with arbitrary argument lists. The approach I took was to use standard C Library variable arguments functionality (va_list with the va_start(), va_arg(), and va_end() functions) and to then store the function pointer along with the provided arguments into a data area so that they could then be executed at a later time. I borrowed and modified how the printf() function uses the format line to know how many arguments and their types are provided.

The next was the storage of the function and its argument list. I just used a struct with some arbitrary size just to try out the concept. This will need a bit more thought.

This particular version uses an array that is treated like a stack. There is a function that you use to push some arbitrary function with its arguments onto the stack array and there is a function that will pop the top most function and its arguments off of the stack array and execute it.

However you could actually just have arbitrary struct objects in some kind of a collection for instance a hash map and that might be very cool.

I just borrowed the signal handler example from the paper to show that the concept would work with that kind of an application.

So here is the source code and I hope it helps you come up with a solution.

You would need to add other cases to the switch so as to be able to process other argument types. I just did a few for proof of concept.

Also this does not do the function calling a function though that would seem on the surface to be a fairly straightforward extension. Like I said, I do not totally get this Curried thing.

#include <stdarg.h>
#include <string.h>

// a struct which describes the function and its argument list.
typedef struct {
    void (*f1)(...);
    // we have to have a struct here because when we call the function,
    // we will just pass the struct so that the argument list gets pushed
    // on the stack.
    struct {
        unsigned char myArgListArray[48];   // area for the argument list.  this is just an arbitray size.
    } myArgList;
} AnArgListEntry;

// these are used for simulating a stack.  when functions are processed
// we will just push them onto the stack and later on we will pop them
// off so as to run them.
static unsigned int  myFunctionStackIndex = 0;
static AnArgListEntry myFunctionStack[1000];

// this function pushes a function and its arguments onto the stack.
void pushFunction (void (*f1)(...), char *pcDescrip, ...)
{
    char *pStart = pcDescrip;
    AnArgListEntry MyArgList;
    unsigned char *pmyArgList;
    va_list argp;
    int     i;
    char    c;
    char   *s;
    void   *p;

    va_start(argp, pcDescrip);

    pmyArgList = (unsigned char *)&MyArgList.myArgList;
    MyArgList.f1 = f1;
    for ( ; *pStart; pStart++) {
        switch (*pStart) {
            case 'i':
                // integer argument
                i = va_arg(argp, int);
                memcpy (pmyArgList, &i, sizeof(int));
                pmyArgList += sizeof(int);
                break;
            case 'c':
                // character argument
                c = va_arg(argp, char);
                memcpy (pmyArgList, &c, sizeof(char));
                pmyArgList += sizeof(char);
                break;
            case 's':
                // string argument
                s = va_arg(argp, char *);
                memcpy (pmyArgList, &s, sizeof(char *));
                pmyArgList += sizeof(char *);
                break;
            case 'p':
                // void pointer (any arbitray pointer) argument
                p = va_arg(argp, void *);
                memcpy (pmyArgList, &p, sizeof(void *));
                pmyArgList += sizeof(void *);
                break;
            default:
                break;
        }
    }
    va_end(argp);
    myFunctionStack[myFunctionStackIndex] = MyArgList;
    myFunctionStackIndex++;
}

// this function will pop the function and its argument list off the top
// of the stack and execute it.
void doFuncAndPop () {
    if (myFunctionStackIndex > 0) {
        myFunctionStackIndex--;
        myFunctionStack[myFunctionStackIndex].f1 (myFunctionStack[myFunctionStackIndex].myArgList);
    }
}

// the following are just a couple of arbitray test functions.
// these can be used to test that the functionality works.
void myFunc (int i, char * p)
{
    printf (" i = %d, char = %s\n", i, p);
}

void otherFunc (int i, char * p, char *p2)
{
    printf (" i = %d, char = %s, char =%s\n", i, p, p2);
}

void mySignal (int sig, void (*f)(void))
{
    f();
}

int main(int argc, char * argv[])
{
    int i = 3;
    char *p = "string";
    char *p2 = "string 2";

    // push two different functions on to our stack to save them
    // for execution later.
    pushFunction ((void (*)(...))myFunc, "is", i, p);
    pushFunction ((void (*)(...))otherFunc, "iss", i, p, p2);

    // pop the function that is on the top of the stack and execute it.
    doFuncAndPop();

    // call a function that wants a function so that it will execute
    // the current function with its argument lists that is on top of the stack.
    mySignal (1, doFuncAndPop);

    return 0;
}

An additional bit of fun you can have with this is to use the pushFunction() function within a function that is invoked by doFuncAndPop() to have another function you can put onto the stack with its arguments.

For instance if you modify the function otherFunc() in the source above to look like the following:

void otherFunc (int i, char * p, char *p2)
{
    printf (" i = %d, char = %s, char =%s\n", i, p, p2);
    pushFunction ((void (*)(...))myFunc, "is", i+2, p);
}

if you then add another call to doFuncAndPop() you will see that first otherFunc() is executed then the call to myFunc() that was pused in otherFunc() is executed and then finally the myFunc() call that was pushed in the main () is called.

EDIT 2:
If we add the following function this will execute all of the functions that have been put onto the stack. This will allow us to basically create a small program by pushing functions and arguments onto our stack and then executing the series of function calls. This function will also allow us to push a function without any arguments then push some arguments. When popping functions off of our stack, if an argument block does not have a valid function pointer then what we do is to put that argument list onto the argument block on the top of the stack and to then execute that. A similar change can be made to the function doFuncAndPop() above as well. And if we use the pushFunction() operation in an executed function, we can do some interesting things.

Actually this could be the basis for a Threaded Interpreter.

// execute all of the functions that have been pushed onto the stack.
void executeFuncStack () {
    if (myFunctionStackIndex > 0) {
        myFunctionStackIndex--;
        // if this item on the stack has a function pointer then execute it
        if (myFunctionStack[myFunctionStackIndex].f1) {
            myFunctionStack[myFunctionStackIndex].f1 (myFunctionStack[myFunctionStackIndex].myArgList);
        } else if (myFunctionStackIndex > 0) {
            // if there is not a function pointer then assume that this is an argument list
            // for a function that has been pushed on the stack so lets execute the previous
            // pushed function with this argument list.
            int myPrevIndex = myFunctionStackIndex - 1;
            myFunctionStack[myPrevIndex].myArgList = myFunctionStack[myFunctionStackIndex].myArgList;
        }
        executeFuncStack();
    }
}

EDIT 3:
Then we make a change to pushFunc() to handle a double with the following additional switch:

case 'd':
  {
     double d;
     // double argument
     d = va_arg(argp, double);
     memcpy (pmyArgList, &d, sizeof(double));
     pmyArgList += sizeof(double);
   }
break;

So with this new function we can do something like the following. First of all create our two functions similar to the original question. We will use the pushFunction() inside one function to push arguments that are then used by the next function on the stack.

double f1 (double myDouble)
{
    printf ("f1 myDouble = %f\n", myDouble);
    return 0.0;
}

double g2 (double myDouble) {
    printf ("g2 myDouble = %f\n", myDouble);
    myDouble += 10.0;
    pushFunction (0, "d", myDouble);
    return myDouble;
}

New we use our new functionality with the following series of statements:

double xDouble = 4.5;
pushFunction ((void (*)(...))f1, 0);
pushFunction ((void (*)(...))g2, "d", xDouble);
executeFuncStack();

These statements will execute first the function g2() with the value of 4.5 and then the function g2() will push its return value onto our stack to be used by the function f1() which was pushed on our stack first.

What is the advantage of Currying in C#? (achieving partial function)

The advantage of Currying in C# is that it allows C# developers to develop in a Functional Programming style.

Think about LINQ. A LINQ query allows you to pass in a method as a parameter:

someCollection.Where(x => x.someVal == 1);

x.someVal == 1 gets evaluated as a function and then Where uses the return value in its own execution.

It's an example that most .NET 3 developers are familiar with, but few realize that they're dabbling in Function Programming. Without the ability to Curry, LINQ wouldn't be possible.

...hopefull that makes up for my smart-ass comment.

Stopping generic C++14 `curry` function recursion

The minimal changes required to make this work in Clang is

auto bound_f = [=](auto... xs) -> decltype(f(x, xs...))
//                            ^^^^^^^^^^^^^^^^^^^^^^^^^
{
     return f(x, xs...);
};

using last_step = std::integral_constant<bool,
                                         is_zero_callable<decltype(bound_f)>{}>;
//                                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Explicitly specifying the return type should make it SFINAE-friendly and capable of being detected by is_zero_callable. Unfortunately, GCC is unhappy with this, probably due to a bug.

A generic lambda is basically a class with a templated operator(), so we can just write it ourselves:

template<class F, class T>
struct bound_function {
    F f;
    T arg;
    template<class... Args>
    auto operator()(Args... args) const -> decltype(f(arg, args...)){
        return f(arg, args...);
    }
};

Note that I'm imitating the semantics of the generic lambda here and making the operator() const. A full-featured implementation will likely want to overload on constness and value categories.

Then

auto bound_f = bound_function<TF, decltype(x)>{f, x};

works in both GCC and Clang, but has a theoretical problem: when only f(arg) is valid (and not with extra arguments), then instantiating bound_function (which instantiates a declaration of its operator()) is ill-formed NDR because every valid specialization of operator()'s declaration requires an empty parameter pack.

To avoid this, let's specialize bound_function for the "no further arguments needed" case. And since we are computing this information anyway, let's just express it in a member typedef.

template<class F, class T, class = void>
struct bound_function {
    using zero_callable = std::false_type;
    F f;
    T arg;
    template<class... Args>
    auto operator()(Args... args) const -> decltype(f(arg, args...)){
        return f(arg, args...);
    }
};

template<class F, class T>
struct bound_function<F, T, void_t<decltype(std::declval<const F&>()(std::declval<const T&>()))>> {
    using zero_callable = std::true_type;
    F f;
    T arg;
    decltype(auto) operator()() const {
        return f(arg);
    }
};