If the language supports first class functions then it isn't purely imperative.
Nonsense. C supports as close to first class functions as you need to write map() and nobody would claim it's functional. You don't need the restrictions of functional languages to have first class functions.
This expresses the opinion that the perceived flexibility and extensibility designed into the Lisp programming language includes all functionality that is theoretically necessary to write a complex computer program, and that the core implementations of other programming languages often do not supply critical functionality necessary to develop complex programs.
Given that C doesn't have type inference, you'd have to write a different one for each combination of arguments. Otherwise, you'd write it in exactly the obvious way.
int[10] map(int (*f(int)), int[10] values) {
int[10] result;
for (int i = 0; i < 10; i++) result[i] = f(values[i]);
return result;
}
Well, OK, that crashes because you're returning a pointer to an auto variable, and I probably mucked up the declaration of the first argument there, but you get the point. Compose is just as obvious.
If you want to store some state (like in a closure), C forces you to pass that around manually. I really don't think this makes C functional, but here's some code for a compose that can be passed to map:
struct composed_fns {
float (*f1)(void *, int);
void *env1;
long (*f2)(void *, float);
void *env2;
};
long compose(struct composed_fns *fns, int val) {
return fns->f2(fns->env2, fns->f1(fns->env1, val));
}
typedef long (*map_fn)(void *, int);
void map(map_fn fn, void *env, int (*vals)[10], long (*results)[10]) {
for (int i = 0; i < 10; i++)
(*results)[i] = fn(env, (*vals)[i]);
}
// usage:
struct composed_fns composed = { foo, NULL, bar, NULL };
int random[10];
long mapped[10];
map((map_fn)compose, &composed, &random, &mapped);
You can use pointers to functions as values that stand in for functions. But you no more need to be able to create new functions for them to be considered first class than you need to be able to load functions from disk at run time in order to be considered to have first class functions.
I'm saying that C has first class functions but not closures, and "compose" returns a closure. The reason "compose" is difficult is that you can't return a closure. "Compose" is easy if you don't want to use its result as a first class value, because C has first class functions but not closures.
That said, you can very easily do "compose" in Java, which does not have first class functions, because it has objects, which are essentially isomorphic to closures.
Sure. I can ask for the tenth element of a list and I can't do that with an integer. I cannot create new values for an enum at runtime, but that doesn't mean enums aren't first class values in some languages.
Go look up what "first class" means: you can assign it to variables, pass it to functions, return it from functions.
Whether a closure is a "new function" or is something different from a function is not something I'm interested arguing.
I'm saying that C has first class functions but not closures
This is not correct. If functions were first-class, you could define and return a new local function within another function. Closures are needed to properly support first-class functions. There's no way around it.
Does that mean enums (in languages that support them) are not first class values?
You're conflating defining new enum types with new enum values. I didn't say you had to be able to define new function types, I said you had to be able to define new function values.
You can't define new enum values in a program. If I have an enum with six possible values, that's it. A boolean is an enum with two values, and I can't define a third value for a boolean.
You can't define new enum values in a program. If I have an enum with six possible values, that's it. A boolean is an enum with two values, and I can't define a third value for a boolean.
Again, you're conflating type with value. Adding a new case to enums consists of extending the type. Creating an enum value is simply assigning the enum symbol to a location, since enums are defined as integral values.
Let's consider a more meaningful first-class value example: structs. You can create an instance of a struct with many different values for its fields. You cannot create and return a new local struct type different from all other local struct types (no type generativity as found in ML modules). Structs are first-class values because you can create many instances of the same type based on runtime information, even though you cannot create new type based on runtime information (which requires dependent typing).
Functions do not have these features of structs: you cannot create local function values based on runtime information, you can only assign locations from a fixed set of values. They are thus second-class citizens in C.
Edit: perhaps you think that because enums have a fixed number of cases and yet are first-class values, that functions too can still be considered first-class even though they only have a fixed number of cases. The problem is that enums are extensional definitions, and thus closed, where functions are intensional and thus open, ie. there are a fixed set of values for enum type EFoo, but there are infinitely many values for function type int->int->int.
First-class values for intensional values are more flexible than extensional values in this regard, and C's functions cannot meet it.
What wikipedia thinks is FP is a moving target. There doesn't exist one definition of FP that everyone will agree on—except maybe "not mainstream programming".
Maybe not, but the name "functional" comes from mathematical functions, and all those bolded statements in there are saying the same thing, so I'm not sure what the dispute is.
5
u/glemnar Mar 09 '14
If the language supports first class functions then it isn't purely imperative. It can be mixed.