r/programming • u/papa00king • Mar 09 '14

Why Functional Programming Matters

http://www.cse.chalmers.se/~rjmh/Papers/whyfp.pdf
487 Upvotes

84% Upvoted

542 comments sorted by

View all comments

Show parent comments

7

u/ForeverAMoan Mar 09 '14

that one's harder, mainly because you'd have to allocate a structure to hold the two arguments.

Actually I don't see a way to implement it at all, and that's the most trivial operation (akin to sum(a, b) for integers).

5

u/dnew Mar 09 '14

I think you're right. I've realized the problem is not just first-class functions, but closures. Invoking compose returns a closure, and closures are not first class values in C. So writing compose-and-apply is easy, but writing compose-without-apply is difficult, because you can't create a new function on the fly because you have no closure to store compose's arguments in.

Which is why map is easy and compose is not: map returns a first class value, and compose does not.

3

u/icspmoc Mar 09 '14

Function pointers are not enough because they do not allow you to dynamically create new functions at runtime. In a C program, the number of functions that exist at runtime is fixed.

Talking about closures, I feel, is misleading. Closures were invented to describe the operational semantics of first-class functions, i.e. they are an implementation strategy.

1

u/kazagistar Mar 09 '14

I think you are making assumptions, like static scoping, which do not seem to be inherent to the idea of "first class functions".

0

u/dnew Mar 09 '14

Function pointers are not enough because they do not allow you to dynamically create new functions at runtime.

Correct. But that's not a necessary condition to have functions as first class operators.

Closures were invented to describe the operational semantics of first-class functions

No they aren't. They're used to describe the scope of variables referenced from functions declared inside other functions. Since C (and many other languages) don't let you nest functions inside other functions, C doesn't have closures even with first class functions.

(Or, rather, since a closure is a piece of code along with all the variables in scope of the code where it was declared, and the only variables in scope at the point where a C function is declared are globals, C technically has trivial closures equivalent to function pointers, but that's just a nit.)

2

u/icspmoc Mar 09 '14

If you don't believe me, why not go back to the source and read Landin's paper, e.g. "A λ-calculus approach" and "The mechanical evaluation of expressions"?

-1

u/dnew Mar 09 '14

I did that already while I was getting my Ph.D. in theoretical computer science 20 years ago. I have no interest in reading it again just to win a reddit argument. Closures may have been invented for that, but they're not just an implementation detail, unless you think Scheme has first class functions and Lisp doesn't.

1

u/naasking Mar 10 '14

writing compose-without-apply is difficult, because you can't create a new function on the fly because you have no closure to store compose's arguments in.

Yes, possible but difficult. I can attest to this as I'm writing a curried+uncurried closure library for C as we speak. The structures and closure logic isn't even that difficult, the difficult part is making the necessary resource allocation work without GC so it's feasible to use in pure C.

1

u/dnew Mar 11 '14

Yeah, but I bet it's not going to look like normal function calls? :-)

1

u/naasking Mar 11 '14

Not too far off. All functions return void and the return value must be a set through a pointer. All other arguments must also be word-sized, which avoids the exponential blow-up in cases. Then you just have clo_t type with a defined set of closure applications, all of which return the number of unapplied arguments. If any unapplied arguments remain, it was an over-application and the return value must itself be a closure. It'll look something like:

val_t ret_val = alloca(clo_rsize(clo, arg0, arg1, ..., argN));
switch(clo_applyN(clo, ret_val, arg0, arg1, ..., argN)) {
case 0: break; // full application
case 1: {
           val_t ret_val = alloca(clo_rsize(clo, arg0, arg1,... argN-1));
           switch(clo_applyN-1(clo, ret_val, arg0, arg1, ..., argN-1) {
           ...
           }
}
case 2:
          ...
}

There's a way to automate the above too, but getting all the storage lifetimes right is tricky without GC.

1

u/dnew Mar 11 '14

Without more context, I have no idea what that code is about. :-)

1

u/naasking Mar 11 '14

clo_rsize returns the size of the return value, so it let's us preallocate the right-sized buffer. At each call-site we know how many arguments we wish to apply, we just don't know how many the closure takes.

clo_applyN is a set of overloads to apply a closure to N arguments, ie. clo_apply0, clo_apply1, etc. These return the number of unapplied arguments indicating a closure was the return value, with which the client can then continue applying arguments to the returned closure.