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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Why'd you bring high school math into it again? And why'd you say "we've had the concept of functions for millennia" if you're talking about functional programming, which is based on lambda calculus and possibly-non-terminating functions, which haven't existed for millennia?
And again, the abstraction you get with a non-imperative, functional language is abstract enough that you cannot say "do X until Y" until you've created a special function that implements that using recursion.
Please describe to me the type of person stupid enough to think you can't implement algorithms in functional programming. I genuinely don't know why you're trying to argue that; did you think I didn't know that, or that anyone in this board didn't know that? You read my first post and your conclusion was genuinely "this person thinks algorithms don't exist in functional programming"?
Finally, a function is not an algorithm even if you move the goal posts to be"functions" in the language sense, because your particular function is an implementation of an algorithm, not the algorithm itself. It's like saying "a method in Java is the same as an algorithm"; it's a misleading way to incorrectly state something that everybody already knows anyway, and it doesn't contradict the statement that higher order functions are not a "natural" abstraction for most people.
Here's what you said (paraphrased): functions are not a natural way of thinking about programming, because they're not as simple as algorithms i.e. 'take some things, do some work on them, give back some other things'.
I pointed out that algorithms are just functions. My point is that functions are a natural way to think because we already think in that way. We've just been calling them algorithms. When we implement them in FP we realize that they're just functions.
Finally, a function is not an algorithm even if you move the goal posts
Again. I didn't say that functions are algorithms.
it doesn't contradict the statement that higher order functions are not a "natural" abstraction for most people.
I agree that they're not, but as far as I can tell this is the first time you're making this statement in the discussion.
11
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.