Consider (some of) what a function pointer has:
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:
- nest functions (named & anonymous/lambdas)
- refer to names from outer scopes
- partial application
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