Tuesday, February 07, 2017

The perverse anti-functionalism of CLRS algorithms

Cormen, Leiserson, Rivest and Stein's Introduction to Algorithms (CLRS) is now the dominate textbook for algorithm courses. As I've been working on implementing their algorithms from their book in Python,  I've been struck by how often they espouse an non-functional anti-pattern.

Functional programming asserts that a program should consist mostly of "pure functions," which have no side effects, and always return the same output given the same input. In particular, if we pass a function f a data structure x as an input, f should leave x alone, and return a new data structure y as its output.

Of course at times, if we are not dogmatic functional programmers, we may indeed want to modify x, for instance, if x is huge in size, and we don't want the memory cost of creating a y that is essentially a new copy of x with a few modifications, and we have no further need of the original x.

But, as I argued long ago, even code in languages that are not primarily functional can be rendered much more concise by adhering to functional programming guidelines, so long as one isn't twisting the language too perversely to adhere to them.

CLRS, on the other hand, seem to have an ingrained bias towards pseudo-code functions that modify their arguments in place, and return nothing, even when it would be trivial to write the function as a pure function. This preference is baffling to me: are none of the authors familiar with the idea of functional programming? Or is there a reason they ignore the idea, despite being familiar with it?

9 comments:

  1. Sorry, have to nitpick:

    Of course at times, if we are not dogmatic functional programmers, we may indeed want to modify x, for instance, if x is huge in size, and we don't want the memory cost of creating a y that is essentially a new copy of x with a few modifications, and we have no further need of the original x.

    That's not an issue of pure functional programming -- pure FP means there are no *logical* mutations or *logical* side effects; the compiled implementation is still free to accomplish the logical specification with physical mutations.

    You can have a pure functional program where the compiler recognizes that it doesn't need both x and y in memory at the same time and therefore uses the same block for both of them. Or where it recognizes that one object is a strict subset of another immutable one and reuses the bigger for the smaller.

    With that said, in practice, if you want to ensure that the compiled program *will* do it the memory efficient way, you will have to deviate from the pure FP model, but they're not directly at odds like you suggest here.

    ReplyDelete
    Replies
    1. Immutable data is usually considered part of the FP paradigm: https://miles.no/blogg/why-care-about-functional-programming-part-1-immutability

      Delete
    2. As above: yes, *logically* immutable data (which that link is talking about), not *physically* immutable data. As in, the logical specification of the problem does involve explicitly telling a variable to change its value. That's not the same thing as your program never overwriting the memory!

      If your interpretation is correct, it would mean FPers have to keep buying new RAM, because their program can't use any memory that another variable already used.

      The fact that a function's logical specification -- in accordance with FP -- returns a "different" object doesn't mean the program must use a different block of data! Those are different levels of abstraction.

      In exactly the same way, FP code has the side effects of electricity consumption and CPU register change when executed. And structured programming doesn't use GOTO, but you better believe the compiled code has JMP instructions.

      Delete
    3. "That's not the same thing as your program never overwriting the memory!"

      Yes, and...

      "If your interpretation is correct, it would mean FPers have to keep buying new RAM, because their program can't use any memory that another variable already used."

      Silas, variables *go out of scope*, and then are garbage collected.

      "The fact that a function's logical specification -- in accordance with FP -- returns a "different" object doesn't mean the program must use a different block of data!"

      If the arg passed in has not gone out of scope, it sure does!! Again, please look up "data immutability".

      Delete
    4. See any explanation of how Haskell implements prepend; the fact that you returned a "different" list does not mean it has to use completely different memory for the new list; the program will store a reference to the original list and avoid duplication.

      I can "read about data immutability" from now until eternity and it wouldn't change that :-p

      Delete
    5. 'the fact that you returned a "different" list does not mean it has to use completely different memory for the new list; the program will store a reference to the original list and avoid duplication.'

      I've been reluctant to say this so flatly, but since you are going to be persistent: you have no clue what data immutability means. You have totally missed what I was saying in my post, and are offering "counter-examples" that have nothing to do with what I was talking about. AND, you're paying absolutely no attention when I try to set you straight in the comments.

      Delete
    6. What the hell, let me try one more time:

      I'm going to use vaguely lispish syntax, since I don't know Haskell syntax in particular:

      (def B '(1 2 3))
      (def A (prepend 0 B))

      What does B equal after these two lines?

      Delete
  2. From what I've seen Python seems to be anti functional in its orientation. I don't understand it but it seems to be true. Oh and Hi Gene; been years and years.

    ReplyDelete
    Replies
    1. Hello Scott: Python supports several functional features. Van Rossum doesn't like map or recursion much: that is true. But you can pass functions as first-order objects, and do map another way, so you can write a fairly functional program in Python.

      Delete

Euphemisms II

It's not just abortion where these euphemisms bug me either. I think it is sometimes OK to euthanize your pet, but... you did not "...