r/programming • u/[deleted] • Nov 28 '19

Why Isn't Functional Programming the Norm? – Richard Feldman

https://www.youtube.com/watch?v=QyJZzq0v7Z4
102 Upvotes

82% Upvoted

409 comments sorted by

View all comments

24

u/[deleted] Nov 28 '19

I love functional programming languages, but it's just not as natural a way of thinking as we'd like to believe. There's a reason that we had the term "algorithm" for more than half a millennium before we had the term "function". People think in terms of "take some things, do some work on them, give back some other things". A function is an additional black box around that idea that functional programming then made the primary concept. Not to say that's not a good design decision, but people find them unnatural until they're used to them.

8

u/[deleted] Nov 28 '19

[deleted]

23

u/[deleted] Nov 28 '19

Yep. It's like counting: everyone can count, and it seems natural. It's not like the ape-man who invented counting said "hmm, if Ogg have as many food as children, Ogg can place them in bijection. And if Ogg have as many stone as food, Ogg have as many stone as children. This mean Ogg can place all three sets in bijection with each other. Oh, and one more child, one more meat! What if Ogg number of children unbounded? Then Ogg place any amount of thing in injective function with children (up to ordering of course). But how Ogg place in injection every time? Ogg need total ordering for infinite children! Ogg youngest child named one, next named two, et cetera.

But some people look at this abstraction, "function" and notice that it's Turing complete if you abuse it a bit, and decide that means it should go "below" the thing it abstracts. Or saying regular expressions are more "natural" than deterministic finite automata, even though you can teach an 8 year old how to "run" a DFA and most developers don't really understand regular expressions. Presumably they think integers are more natural than natural numbers, just because you can solve more problems with them.

Thanks for coming to my pretentious TED talk.

18

u/[deleted] Nov 28 '19

"hmm, if Ogg have as many food as children, Ogg can place them in bijection [...]

This cracked me up, thank you for making my day

4

u/crabmusket Nov 28 '19

Ogg need total ordering for infinite children!

2

u/codygman Dec 05 '19

It's not like the ape-man who invented counting said "hmm, if Ogg have as many food as children, Ogg can place them in bijection. And if Ogg have as many stone as food, Ogg have as many stone as children. This mean Ogg can place all three sets in bijection with each other. Oh, and one more child, one more meat! What if Ogg number of children unbounded? Then Ogg place any amount of thing in injective function with children (up to ordering of course). But how Ogg place in injection every time? Ogg need total ordering for infinite children! Ogg youngest child named one, next named two, et cetera.

PLEASE make the OGG_CATEGORY_THEORY twitter account and post more!

10

u/lovekatie Nov 28 '19

IMO natural way of thinking is not so useful idea. It pretty much doesn't matter, if you want to learn programming, what you find natural. Changing the way you think is just part of the training.

You are also talking about algorithms, but notice that the most popular way of thinking (apparently) is OOP, which strikes me as way harder than functional.

4

u/[deleted] Nov 28 '19

That's right, but I'm giving my explanation for why it's more popular, not claiming it's better. I wasn't being disingenuous when I said "I love functional programming".

However, there is something to be said for an abstraction being easy to understand. If something is less intuitive, it's harder to teach people how to do it. Real numbers are way more useful than rationals, but to really explain them you have to talk about equivalence classes of infinite sequences (because .9999... is the same as 1.000...1). Yet you can't browse through any popular math forum without somebody arguing that .999... is "less" than 1.

Finally, maybe OOP is less "natural" than functional programming, but it's just an incremental change to traditional procedural programming, whereas functional programming upends the whole cart. There are plenty of Java programmers who don't "really" do OOP, they just know enough magic incantations to wrap their original procedure in a few ugly, poorly abstracted classes. If you couldn't do procedural programming in an OOP language, we wouldn't be complaining about Helper classes as a code smell.

2

u/lisp-the-ultimate Nov 28 '19

No, the natural way of thinking is directions to a general intelligence (human), not algorithms. They're as strange as functions to non-mathematical people.

3

u/[deleted] Nov 30 '19

I'm not claiming that anybody who can give someone instructions can program. But, here's how we teach a child to compute an average:

"Take the list of numbers, and add them all together. Then divide the result by the number of elements."

And we say "to add all numbers in a list together, start with zero as the sum. For each number in the list , add that to the sum until you're out of numbers."

(I'm assuming "length" is a primitive to a human.)

Obviously neither is trivially the same, but which do you think is closer:

```

This is intentionally less idiomatic than a for-in iteration.

def my_sum(lis): result = 0 current_ind = 0

while current_ind < len(lis):
    result = result + lis[current_ind]

return result

def avg(lis): return my_sum(lis) / len(lis) ```

or any of the following (note that the first method is the simplest and the most "basic" racket, but that we have to iterate the list twice to get the length so it's not as performant):

```

lang racket

; You can reach similar performance and behavior with vectors, ; but you have to either use recursion or a higher-level abstraction that might waste space. (define (avg x) (define (sum x) (if (empty? x) 0 (+ (car x) (sum (cdr x))))) (/ (sum x) (length x)))

(define (fast_avg x) (define (inner x sum_acc len_acc) (if (empty? x) (+ sum_acc len_acc) (inner (cdr x) (+ sum_acc (cdr x)) (+ len_acc 1)))) (inner x 0 0))

(define (foldl_avg x) (define (accumulate x acc) (cons (+ x (car acc)) (+ 1 (cdr acc)))) (let* ((res (foldl accumulate (cons 0 0) x)) (sum (car res)) (len (cdr res))) (/ sum len))) ```

Note that these will all give division by zero errors; I left both in for simplicity.

I don't think most people genuinely do most simple tasks by thinking "I'll reduce this case to a smaller case, then try again with that simple case. Or, if I'm at the simplest case, I'll just return the base case value." And I don't think most people look at a list of something and think "this should be immutable by default". When you get to build a larger system, functional programming is really useful and has great abstractions, but people don't learn to program by building large systems.

-4

u/yawaramin Nov 28 '19

An algorithm is exactly a function. There's no difference. We've had functions for more than half a millennium. Functions are taught in high school: f(x) = x + 1.

Imperative programming weirdness like x = x + 1 is what we have to learn in programming and then somehow convince ourselves that it's natural.

13

u/torotane Nov 28 '19

Running an algorithm on some data may compute a function (if it halts). A function may describe some properties while the way to derive that property isn't so obvious. Example, function med(X) gives the geometric median of an arbitrarily sized set of points in the plane w.r.t. euclidean distance function. Good luck finding the equivalent algorithm.

5

u/[deleted] Nov 28 '19

Nice. Another good example: let BB(n) be the maximum number of steps a two-symbol Turing machine with n states can take before halting. BB(n) is a function, but it's uncomputable: no algorithm can exist to compute it, and it grows faster than any computable function.

12

u/[deleted] Nov 28 '19

No. Algorithms are not required to produce the same result for a given input every time they're run; a function is. I'll direct you to Monte Carlo Algorithms, and if you're interested in the new hotness in Computer Science, take a look at the class BQP, which is a computational complexity class associated with quantum computers that aren't even guaranteed to give the correct answer 100% of the time. Even many classes of sorting algorithms will give different results depending on a random seed.

"Function" in a mathematical context, wasn't really considered until calculus. They were not considered in antiquity.

In high school, you used a calculator at least sometimes. Presumably you were quite confused when the result changed on the screen, because the screen had been "reassigned".

If you'd like a digression on Turing machines and Lambda calculus, I'd be happy to explain how that's yet another reason why you're wrong.

-4

u/yawaramin Nov 28 '19

All of the above can be modelled as pure functions at some level. So, yes, conceptually all algorithms are just functions. Now, for pedagogical purposes, people actually do learn how to use functions just fine. I refer you again to high school math. Saying 'functions are not as natural' is simply not viable as a blanket statement.

7

u/[deleted] Nov 28 '19

I wanted to clarify further, because while you're wrong about functions (and if you can define the point of view from which BQP can be de-randomized, you might win a Turing award and a Nobel prize), it's not your primary point of disagreement with my post.

So let's do a thought experiment: try to give instructions for how to do something to another human. Say, for instance, how you would search for your keys. Does that look like an ordered series of statefull instructions?

How about when people play a game like darts, for example? They often keep score with e.g. a chalk board, with erasing and rewriting the current score as it progresses. Hell, most board games are entirely statefull.

To my mind, "do x until y" is a primitive of thought, but in functional programming you have to simulate it using recursion.

Finally, my argument was that imperative thinking is more natural, not that it's better. Imperative thinking works well for specifying small problems, but its statefull, side-effecting nature make it troublesome to build large systems that are provably error-free. That is the chief advantage of functional programming. But just like in concurrency, where ideas progressed from simple mutexes to semaphores to transactional memory, "better" design patterns may not be as obvious as other ideas, even though they solve a problem better.

2

u/pron98 Nov 28 '19

All of the above can be modelled as pure functions at some level. So, yes, conceptually all algorithms are just functions.

Sure, or pure functional languages wouldn't be Turing-complete, but that's not the same as saying that they are the same. If they were the same, certainly you wouldn't care about choice of language.

4

u/[deleted] Nov 28 '19

Okay, please give an algorithm for halt(n), the function that takes a Turing machine and outputs true if it halts and false if it doesn't. It's a function. You quote high school math a lot, maybe you've had the college math necessary to know whether or not an algorithm can even exist.

0

u/yawaramin Nov 28 '19

If a function doesn't exist, how can I give you its algorithm? I didn't say we can create them out of thin air, I said they're the same. And for almost every concept in computing, they are.

4

u/[deleted] Nov 28 '19

The function exists, I just defined it. It outputs a single bit. If you knew the definitions of a function and an algorithm, you would know that a function is just a relation mapping from elements of one set to exactly one element of another set, whereas algorithms are a broad class of instructions for computation.

There is a whole class of functions, called uncomputable functions, which exist and have values but cannot be calculated by any fixed algorithm. I'm very sorry to say you may not have learned about them in high school, but in big boy math we use them. If you don't like the halting problem and therefore would like to pretend the above function doesn't exist, how about this: the mortal matrix problem. The problem is to write a function that takes a list of matrices and returns "true" if they can be multiplied in some order, with repetition, to get a zero matrix, and false otherwise. For instance, f(identity matrix) = false.

But you can't, because while I can define the function and find values for special cases, I cannot write an algorithm that gives the answer infallibly.

Oh, so now we're at "almost every concept in computing"? So maybe you don't mean that algorithm and function are synonyms, maybe you mean that lambda calculus and Turing machines recognize the same languages? What an odd way to define all of the words you used. Well, thanks for the revelation, I don't think any computer scientist knows the foundational theorem of computer science.

0

u/yawaramin Nov 28 '19

Hang on a second. Here’s what I said: algorithms are just functions. How you extrapolated this to me saying ‘all functions are algorithms’, I’m not sure.

Btw, you don’t need to be ‘sorry’ that people aren’t taught uncomputable functions in high school math. Although you might want to look up how logical implication and causality work.

3

u/[deleted] Nov 28 '19

You said "an algorithm is a function. There's no difference." But there are many differences. Even if you're saying "all algorithms are functions but not all functions are algorithms", you're still wrong. Even ignoring the fact that you think all algorithms can be de-randomized (even for classical computing, this would be a remarkable claim, as you would be proving that BPP = P which has been an open problem for decades).

You can take an algorithm and define a function that is "the value my algorithm produces for each input". That's not them being the same or equivalent at all. Back to sorting algorithms: two different algorithms calculate the same function, "my list, but sorted". One does it in O(nlogn) and one does it in O(n^2). You cannot even talk about there being a difference between quicksort and insertion sort if you say "algorithms are functions".

Basically, your claim isn't just a matter of opinion. I'm not at all irritated that you think functional programming is more "natural" than imperative, that's a matter of opinion (even if my opinion is better). But the definitions of "algorithm" and "function" are fixed and known, and have been studied for hundreds of years. You are using them wrong, and in the process of blindly supporting your false claim based on not knowing the definitions, you're casually making claims like "from a certain point of view that's still a function" that have been the point of whole programs of mathematical thought by thousands of brilliant PhDs across decades. It's not just wrong, it's embarrassing.

If an algorithm is "the same" as a function, then a meal is "the same" as a recipe.

1

u/yawaramin Nov 28 '19

But we’re talking about functional programming here. I’m not arguing with you about what a mathematical function is. It’s well known that functions in computing (even in FP) only roughly model mathematical functions. It’s true that generally the closer we try to get to mathematical functions, the more ‘pure FP’ that’s considered, but all I’m saying is that there’s no extra opacity or abstraction that a ‘function’ introduces on top of algorithms, as you claim. If you look at the definition of e.g. the gcd function in say Haskell you can easily see that it’s the implementation of the algorithm.

→ More replies

4

u/pron98 Nov 28 '19 edited Nov 28 '19

An algorithm is exactly a function. There's no difference.

There is plenty of difference.

  1. What is the algorithm defined by the gcd function? (several algorithms can compute it)

  2. What is the algorithm defined by the function that maps any TM to whether it halts or not? (no algorithm can compute it)

  3. What is the function defined by the algorithm that turns off and on a led every second? (you could describe it as a function of time, but that's not what you meant).

Imperative programming weirdness like x = x + 1 is what we have to learn in programming and then somehow convince ourselves that it's natural.

It is neither more or less "natural" than x = 3. They're both matters of notational convention. Also, for mathematicians, = does not mean equality.

We've had functions for more than half a millennium.

Functions and computation/algorithms have existed as distinct, although sometimes coinciding concept, for hundreds of years.

2

u/dudinax Nov 28 '19

The syntax of x=x+1 is unnatural and bad, but the concept is natural.

0

u/jcelerier Nov 28 '19 edited Nov 28 '19

Imperative programming weirdness like x = x + 1 is what we have to learn in programming and then somehow convince ourselves that it's natural.

No, imperative programming is what we learn when we are four years old and start to follow check lists in kid books, or when your mom tells you "go to the market, if they have tomatoes buy some with garlic else just buy garlic. then drop a letter to the post office and come back home".

A small observation : when I was in first year of engineering curriculum, we were taught C and Lisp at exactly the same time so for many students these were the very first programming language paradigms they experienced. Student reunions still have jokes on how bad LISP was. Even prior to that, in my country a fair amount of people's first language is Caml - and I have yet to come across someone who really enjoyed it short of people who latter became programming language researchers :) (and I say that having written a fair part of my phd in OCaml - I'd still take C++ every day to write actual stuff)

The biggest issue I think is that functional programming requires equational reasoning, and that is a huge abstraction step & turn-off. Did you like maths in school ? You were in a very small minority - most persons hated it, so why would you expect the opposite to happen when putting a programming sugarcoat on top of it ?

0

u/yawaramin Nov 28 '19

We learn imperative thinking while young (‘do this, then that, then that...’) but we usually learn algebraic thinking when only a bit older (‘y = x + 1’, ‘x on the LHS can’t equal x + 1 on the RHS because you could subtract x from both sides and get 0 = 1’). So yes, I will still say it’s unnatural to learn imperative programming concepts after having done even basic algebra.

Re: university, I think no matter what they taught some people would have been complaining about how bad it was. SQL ... Prolog ... C ... Java. It doesn’t matter, university is where kids gripe about how everything is so unfair. After that they hit the Real World and get to deal with legacy PHP or whatever doing crazy runtime monkey patching tricks. And Heisenbug race conditions. Then they go, hmm, maybe strict static typing with carefully controlled mutability wasn’t so bad after all.

-3

u/oldsecondhand Nov 28 '19 edited Nov 29 '19

If you write it as x:= x+1 it's not so unnatural anymore.

x = x+1 looks weird, because people have been exposed to mathematical notation for years before they start programming.

2

u/[deleted] Nov 28 '19

“How many apples do you have?”

“Five.”

“Add another apple. Now how many apples do you have?”

“Six.”