2

I'm new to compiled languages. I'm learning C. I'm used to coding in python.

I was wondering if there was any equivalent, or replacement method in compiled langues for functions able to create a function, and to return it.

In python one can write:

def genAdder (p):
    def adder (n):
        return n + p
    return adder

addFive = genAdder(5)
print(addFive(7))     # prints 12

Is it possible to do such a thing in C, or C++, or any other compiled language ? If yes, does it involve code generation during execution ? If no, are there replacements for situations where this is useful ? (It can be used for performance purposes, to avoid re-doing computations)

3
  • 7
    All currently existing Python implementations have compilers, i.e. are compiled. – Jörg W Mittag Oct 18 '16 at 21:02
  • 6
    And there is at least one interpreter for C. The point being that compilation and interpretation are properties of the implementation, not the language. – 8bittree Oct 18 '16 at 21:08
  • 1
    Just to clear up some terminology: functions are first-class in a language if we can pas functions to or return functions from other functions. A function that actually does accept or return a function is called higher-order. Functions are first-class in Python. The function genAdder you wrote is an example of a higher-order function, which returns a closure - the return function adder will close over the variable p. – gardenhead Oct 19 '16 at 4:14
6

Yes, many compiled languages support higher order functions. No, they rarely if ever do runtime code generation.

In C, "function pointer" is the appropriate search term. C++ also supports function pointers, though there's a number of alternative approaches (and libraries) to support similar behavior. Though they generally aren't as clean as other languages' support for this sort of thing due to their history. Java and C# especially handle this better.

And of course actual functional languages have great support for this, and are often compiled.

As for using p in the inner definition, that is a closure. They are well studied, and well known. When I used C++ boost::bind supplied a mechanism to do something similar. In these languages, you generally need to make a new object/class to hold the "stored" variable, and the sub-function.

5

Many compiled languages support this. C does not.

The feature you're looking for is called a "lexical closure", or "closure" (or sometimes "lambda," because language designers love using different words for the same concept in different languages) for short.

It doesn't involve code generation at runtime; it involves code transformation at compile-time. A compiler supports closures (nested functions) by rewriting the code into an object class whose state is the set of variables it "closes over" from the outer scope (hence the name, closure,) and whose code is the nested function, and then transparently instantiating an object of that class that can be used as a function.

The exact details of how this is done varies from one language to another, but the basic pattern is pretty consistent. Even Python does it in a very similar way, except it doesn't bother creating a class for the generated function/state object.

The C language specifically has no support for closures, and it's not likely to ever get any either, because the sort of code rewriting required to make them work violates the design philosophy of the language, that everything that the code does when executed should be easily apparent by reading the source.

14
  • 4
    I was under the impression that lambda referred exclusively to anonymous functions (which might not necessarily be closures) – Jack Oct 18 '16 at 20:11
  • 6
    Downvoting because your explanation of higher-order functions is incorrect, or at the very least misleading. Not only did you not distinguish lambdas from closures (and btw, the term "lambda" predates the term "closure" by a good chunk), but you assume an implementation of closures that is irrelevant to their definition. – gardenhead Oct 18 '16 at 20:25
  • 2
    @gardenhead There is no meaningful semantic difference between lambdas and closures; the only difference is in the style of how they're written and which language (with its accompanying preferred vocabulary) you're using. And the explanation of the implementation of closures is important for the OP to understand how this can be done without runtime code generation. Obviously there are other ways to do it, but I'm trying not to overcomplicate an answer to a question that was asked at a beginner's level. – Mason Wheeler Oct 18 '16 at 20:28
  • 2
    @MasonWheeler Do you really not know the definition of a higher-order function? Here you go. A higher-order function is one that either takes a function or returns a function. Please tone down your accusations, because you're the one who doesn't know the terminology. And that's not the reason I downvoted you. I already stated the reasons in my initial comment. – gardenhead Oct 19 '16 at 2:50
  • 2
    @gardenhead, I'm reading the same question as you: I just read the body of the question too. A good answer to that question would (a) not mention HOFs, as they aren't relevant, (b) would clarify the OP is really asking about closures, not just returning functions from another function, (c) would clarify that Python doesn't generate code at runtime for such situations and (d) would explain that C doesn't support closures. This answer does all that, thus is a good answer and you are wrong to downvote it. – David Arno Oct 19 '16 at 7:14
4

The code below is valid C# - without the ceremony - tested on LinqPad:

Func<int, Func<int, int>> getAdder = (p) =>
    new Func<int, int> ((n) => n + p);

Func<int, int> addFive = getAdder(5);
Console.WriteLine(addFive(7)); // prints 12

While it is true the C# is (usually) compiled JIT, this snippet doesn't require code generation at runtime, just at compile time. The code will instead create hidden anonymous classes to hold the methods.

The compiler will create the following structure (assuming the method with the above code is Main):

[System.Runtime.CompilerServices.CompilerGenerated]
private sealed class adderClass
{
    public int p;
    internal int adderMethod(int n)
    {
        return n + this.p;
    }
}

[System.Runtime.CompilerServices.CompilerGenerated]
[Serializable]
private sealed class getAdderClass
{
    public static readonly getAdderClass Instance;
    static getAdderClass()
    {
        Instance = new getAdderClass();
    }
    internal Func<int, int> getAdderMethod(int p)
    {
        return new Func<int, int>(new adderClass{p = p}.adderMethod);
    }
}

public void Main()
{
    var getAdderFunc = new Func<int, Func<int, int>>(getAdderClass.Instance.getAdderMethod);
    var adderFunc = getAdderFunc(5);
    Console.WriteLine(adderFunc (7)); // prints 12
}

The above code was also tested on LinqPad. I added the names of the classes and members for illustrative purposes. The compiler will use names such as <>c__DisplayClass0_0 which can't be produced by regular code.

As per Func, the implementation uses a reference to the target object and a pointer to the method, that pointer can't be obtained with regular C#, instead Func and other delegate types provide a safe abstraction.

I want to reiterate that the transformation presented above happens at compile time, not at runtime.


About the utility of delegate types, they are how events works in .NET.

2
  • 1
    Still plenty of ceremony there :D Func<int, Func<int, int>> getAdder = p => n => n + p; (although, I'd probably write it as a method Func<int, int> getAdder(int p) => n => n + p;) – porges Oct 19 '16 at 3:37
  • @porges and that's why I currently don't do code golf. – Theraot Oct 19 '16 at 14:31
3

Note that the code itself never changes. It won't suddenly change to return n * p, for example. You just have to remember the value of p when genAdder was called. What actually gets returned here is a data structure containing the current value of p, and a function pointer to some fixed code containing the fixed definition of adder. If you want to actually generate new code, you have to use compile or eval.

Note that your python version doesn't actually generate any new code every time the function is called either. That would be extremely inefficient. It will generate the closure code only once, just like compiled languages. The only difference is it waits until the first time it is needed at runtime.

2

In languages that don't support closures, because the function can't "grab" values out of closure context you have to mind what are your data requirements, and build them on the fly. Your example greatly exposes that. Calling genAdder has to make a heap allocation somewhen to store the value 5. In C++ your adder would be a dedicated class with an int field. In C you would have something like:

public int *alloc_adder_data (int value){
     //shove a malloc call here, return pointer
}
public int call_adder (int *adder_data, int num){
     return num + *adder_data
}

Then, if you had to use the adder as a first class value somewhere, like for example to map it on a list or whatnot, you can use the function pointer to call_adder and pass it to the map function (this is about when you want to fly back to the sweet python days).

1

C++11 now supports lambdas, and the code you've written in your question can be written in C++11 like this:

std::function<int(int)> genAdder(int p)
{
    return [p](int n) { return n + p ; };
}

void main()
{
    auto addFive = genAdder(5)
    count << addFive(7);     # prints 12
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.