Does function pointer have the same expressive power as function as parameter?

Question

In functional programming language, a function can be passed as an argument to another function. In programming language like C/C++, a function pointer referring to a function can be passed to a function that can invoke the external function through dereference.

Then, does function pointer have the same expressive power as function as parameter in functional programming language?

Answer 1

A function pointer (e.g. in C or C++) is only the address of some machine code (computing some function). It does know about any data except the constants embedded in the code, and the static data referenced by it.

Conceptually (e.g. in lambda-calculus) a function needs both some code to be computed, and some data to be accessed. So a function usually has bound variables, that is closed variables. Hence, a function is a mixture of code and data, that is, a closure. Practically speaking, a closure contains not only code (some "function pointer" à la C) but also data.

Notice that C++11 introduced closures, anonymous functions (a.k.a. lambda-expressions), and std::function.

Most (but not all) functional languages (e.g. Ocaml) prohibit comparing functions (that is, closures), because conceptually that would mean comparing the behavior of functions (and that is undecidable, read about Rice's theorem).

So closures are more expressive than function pointers. In this answer I claim that every function is conceptually a closure (in C, the closed values being the static data).

Because C does not have genuine closures (but n2030 is a proposal to add them to some future C2x standard), most libraries wanting "closures" are actually taking the convention that function pointers are passed as callbacks with some explicit client data (mimicking closed values); for a simple example look into GNU libc qsort_r(3). For a more complex example look into the source code and coding conventions of the GTK graphical toolkit.

From both an implementation and a theoretical point of view, closures are mixing (like objects) data and code. In the RefPerSys system this property is used, since it aims to generate more and more of its code.

Books like the Pi-calculus (by Davide Sangiori and David walker) ISBN 0-521-78177-9, or a Theory of objects (by Martin Abadi and Luca Cardelli) ISBN 0-387-94775-2 or Artificial Beings - the conscience of a conscious machine (by Jacques Pitrat) ISBN 9781848211018 or Types and Programming languages (by Benjamin Pierce) ISBN 9-780282-162098 or Theories of programming languages (by John Reynolds) ISBN 0-521-59414-8 or Christian Queinnec's Lisp in Small Pieces are explaining all that much better than I could do.

If you can afford going to some university library or buying books, I recommend reading them.

Answer 2

Consider (some of) what a function pointer has:

• type

and what you can do with it:

• pass it as an argument
• call it
• return it as result
• assign it to a variable/store it
• compare it to another pointer of the same type

Functions as parameters is only one of the operations on this list, thus is less powerful than function pointers. However, this merely indicates that the two aren't the proper features to compare when it comes to functional programming.

Functions as parameters is just one of the language properties of higher-order functions (HOFs), which can:

• accept functions as arguments
• call passed functions
• return functions

Additionally, in a typed language HOFs imply there are function types. Functional languages have all these, thus support HOFs. All the HOF properties are on the function pointer operations list, thus function pointers allow HOFs. Even without function pointers, some procedural languages support some or all of these (often the first two), sometimes with limitations. For example, Modula-2 supports function types and all three operations (with the limitation that the function values be top-level user functions, as opposed to system functions or nested functions), thus has higher order functions. (Modula-2 also supports function pointers, but no special operations on them beyond pointer operations (e.g. you can't call a function pointer, but you can dereference it and call the result).) ISO Pascal and Algol-60 allow functions as parameters, but don't have true function types or allow functions as return values, and, in some Pascal variants, functions are at most second-order (i.e. they can't take functions that take functions), thus these languages don't truly support higher order functions (though some compilers add at additional support as language extensions).

Even HOFs isn't the proper feature for comparison. Arguably, the defining feature of functional programming is support for first-class functions, which implies the following operations on functions and language features:

• higher order functions
• assign functions to variables/store functions
• create/combine functions

Despite having function passing, ISO Pascal and Algol-60 lack all these. In addition to HOFs, Modula-2 supports assignment (though values must be top-level functions), but not creation or combination.

Combining functions includes the composition operator, as well as other combinators. These combinators may exist at the language level, explicitly or implicitly (e.g. J's trains), or may exist idiomatically (generally as lambdas).

The only function pointer operation not among the first-class-function features is comparison. Many languages support at least reference equality, but some do not (e.g. F#). This is the potential expressiveness gap: first-class functions may not allow for comparison, and function pointers do not (in general) allow for creation & combination. Depending on the language, it may be possible to add a function comparison operator or function creation (combination easily follows from creation). Adding function creation is likely to be much harder, as it basically requires embedding a language processor. A language with function pointers but not first-order functions may have other language features (e.g. function objects in C++98 & C++03, which basically allow for function creation & combination; consider boost::function) or idioms (e.g. passing additional data along with function pointers in C, either as separate variables or bundled into structs) to make up for the lack.

Another area where first-order functions might have more expressive power than function pointers is typing. The only type-relation function pointers in C and C++ can have is type-equivalence. Function subtyping, if a language supports it, allows for expressions that can't be rewritten as type-safe expressions involving function pointers. You could still get a compilable expression using casting, but it won't be type-safe.

There are yet more features that crop up around first-class functions. These (can) include the following operations/features:

1. nest functions (named & anonymous/lambdas)
2. refer to names from outer scopes
3. currying
4. partial application
5. decoration

Sometimes, 1 & 2 are also included as essential sub-features of first-class functions. Not all are necessary, especially as you can implement some of them using others. Many of these have to do with creating new functions.

Nested functions, depending on the language processor implementation, may involve function creation. If the inner function definitions are evaluated each time the outer function runs, you have function creation. However, the language processor may evaluate the inner function definition only when evaluating the outer one, so that instead of creating a new inner function each time the outer one runs, it applies feature 2 and creates a new binding between the identifiers in the inner function to variables in the outer one. In functional languages, this means creating a new closure rather than a new function. Purely procedural languages probably create neither.

For example, Pascal supports nested named functions but not closures, and nested functions are compiled only once, when the rest of the source is compiled. A nested function can access the variables in the outer function, but only during the execution of the outer function (when its stack frame is active). The inner function cannot escape the outer function call.

Some of the above subfeatures can be combined in other ways to get other language features. For example:

• passing + (assignment|storage) = callbacks
• nested functions + returning + outer scope reference = closures

Answer 3

No, function pointers do not have the same expressive power as functions per se that can be passed as parameters, etc.

Thought you might want an answer under 5 pages in length.