I never tried Haskell, or 'functional programming". To be honest, I don't even know what functional programming is.
Can someone explain how is it different from Python or C (the only two languages I did little coding with)?
In C or Python, a "variable" is a storage location in which you can place different values at different times. This is completely different from mathematics, where "x" doesn't equal something different just because you progress to the next step of computation. (But "x" might refer to something different in a different context, such as when evaluating a function with a different argument; that's the sense in which it varies.)
Similarly, in mathematics, there's no such thing as a function that returns something different each time you evaluate it, or that gives one result on Wednesday but a different result on Friday, or that even gives no result at all but causes letters to appear on a nearby computer screen. Yet in C or Python, all of these things are called functions.
At first, it might seem surprising that you can do much programming without the C or Python version of functions and variables. But:
1. You can do more than you think without reassigning variables or using functions that aren't "real" functions in the sense of mathematics, and
2. Of course, in the end, all languages - including functional languages - do have a way to create boxes to store values over time, or to perform actions that make things appear on computer screens. It's just that in a functional language, these things are not the basic bread and butter tools of programming to the extent that they are in C or Python. So you have variables and functions (in the mathematical sense), and you also have other things that act like storage locations and actions, but you only use the latter when you have a real need for them.
That's the general character of the difference. There is, of course, a lot of detail that I am leaving out in a response on a web site.
The reason people were speculating about whether this would work better with people not yet accustomed to programming is that it's often thought that experience in an imperative language (like C or Python) leads you to naturally try to do things with actions and storage locations, even when it's not necessary... and then it can get frustrating and confusing to work in a language where most things are actually not done that way. There's a theory that says if you maybe learned the functional way first, you wouldn't find it as frustrating.
I'm of two minds about that. I spent a year teaching Haskell with this system (I'm the Chris Smith mentioned in the article), and I found that it's partly true that students don't get as frustrated... sometimes. But there are other cases where students naturally fall into trying to do things in imperative ways, despite not having past experience in a programming language. I actually think, computer programming aside, that this is one of the things that trip up kids in math classes. So it's not just programming languages where this comes up: a lot of teachers present math as step-by-step processes, as well. Essentially, they introduce imperative programming without the computer. This is what happens when teachers tell students that parentheses are about what to do "first", instead of about which sub-expressions are meaningful on their own. Partly, I think this is just how the human mind works, too, and it's an inherent tendency that we have to overcome to really "get" algebra and other mathematics in a deeper sense than knowing how to do specific problems. It's still frustrating, then, for kids to adapt to having to describe processes using equations and expressions, which at their core do not list things to do, but instead describe and state facts about relationships between quantities.
I still think it's an important skill to learn. Indeed, I'm a lot more interested in teaching that kind of reasoning than I am about teaching computer programming. That's why I made changes in the new CodeWorld (the site discussed in this article) that are designed to deliberately thwart students who try to think of their programs as sequences of actions, and encourage those who think in terms of compositional expressions.
>>>Similarly, in mathematics, there's no such thing as a function that returns something different each time you evaluate it, or that gives one result on Wednesday but a different result on Friday
I don't get this example. If the function is f = t, where t is time, then f will give different results on Wed and Fri.
In both math and Python, a function such as Square = x*x will return exactly the same thing as long as x does not change.
>>>This is completely different from mathematics, where "x" doesn't equal something different just because you progress to the next step of computation
When I do math (such as algebra, or calculus), I think of a variable x as a container that can hold any value. This is exactly how I think of a variable in C or Python.
For example, I can build a graph of a parabola in Python. The way my code does it is pretty much the same as if I did it by hand with a pencil: I assign multiple values to x, and find corresponding values for y.
I can't quite pinpoint the source of my confusion...
I assume you meant something like f(t) = t?
If so, then right, if you pass in the current time as a parameter to the function, then the result can depend on it. But in Python, you don't pass in the current time. That's because "function" means something entirely different in Python.
In math, at the simplest possible level [1], a function is a set of ordered pairs, with the property that no two different ordered pairs have the same first element. That's all there is to it. So when I write f(x) = 3x - 5, that's just shorthand for saying that f is the infinite set { (0, -5), (1, -2), (2, 1), (1/2, -7/2), ...}. That's all there is to it. There's no sequences of operations, no process, etc. It's just a set of ordered pairs.
Python's functions, on the other hand, are at their core a sequence of instructions. Some of those instructions (like loops or conditionals) have other sequences of instructions as components. They share an environment, which consists of storage locations called local variables. A Python function is actually a pretty complex thing, when you get down to it.
You could model Python's functions using standard mathematics, if you play some tricks: add hidden parameters, give interpretations to the results in terms of physical effects, etc. But this just tells you that math is powerful enough to model Python functions (and, well, anything else) in terms of its much simpler ideas. It doesn't mean that those ideas are the same as the things in Python that go by the same name.
> For example, I can build a graph of a parabola in Python. The way my code does it is pretty much the same as if I did it by hand with a pencil: I assign multiple values to x, and find corresponding values for y.
Okay, but you're describing the process of drawing the parabola. In math, f(x) = 3x^2 + 2x + 1 isn't a process for drawing a parabola. It is a parabola. So f, here, is itself the set of ordered pairs, which make up a parabola if you treat them as points on the coordinate place. That's the basic difference.
[1] Okay, for the pedants out there, this depends on your choice of foundations. I'm assuming the standard interpretation using ZFC, but a similar point would apply if you prefer a different foundational theory.
However, math and computing are not the same. How can you possibly represent a concept of an infinite set in a computer language? After all, any computer is a Turing machine, and the sequence of instructions is the very foundation of computing (at least that's how I think about it).
It's interesting: I see many replies to my question, however no one has been able to show me a clear example of some code in FP language, side by side with the same code in Python or C, and point out how the FP code is better (in any way).
I learned programming concepts by studying computer architecture, and after I wrote bunch of MIPS assembly, I could clearly see how C makes my life easier. Then I looked at Python, and I could see, for example, how a concept of a class/object makes my life easier compared to C. So now I'd like to see how FP can make my life easier compared to C or Python. I still don't get it.
In this particular case, the point was that I created an educational tool for teaching mathematics. It happens to involve a programming language; but the goal isn't to train computer programmers. It's to teach math. So the language used is one that lets you describe functions and quantities the same way as you would in math, and mostly avoids the need to think about a computer doing some sequence of operations.
From that key idea of HOF, other stuff arises, like the lean towards immutability. Which gives rise to things like recursion.
This is why functional programming in non-FP languages gets cumbersome. While they can "do" FP, all the other things you want aren't supported or require a ton of effort. Whereas in an FP language, those other things (immutability, recursion, pure functions, etc.) are treated better.
FWIW I've written a series (looking at C# specifically) on my blog http://www.atrevido.net/blog/2007/08/12/Practical+Functional...
But I think the blog may be messed up and it was written nearly 7 years ago when I was far less experienced with FP. There's probably far better intros out there.
That said, one thing that's more common in FP than anywhere else is an adherence to the notion that a variable stands for an "unknown" and not a mutable slot. Thus, you cannot assign to a variable but instead can only define it within a context.
x = 3
x = x + x
Typically, functional languages operate by giving "first class" domain to functions (thus their namesake). What this means is that you can both create and define functions as though they were mere values like integer or characters. To do so, to say define a function of one argument which doubles that argument, you use what's called abstraction
x . x * x
(x . x * x)(3)
3 * 3
9
square = x . x * x
square(3)
(x . x * x)(3)
3 * 3
9
λ x . x * x
So why does all this matter? In short, variables which behave as unknowns instead of mutable slots are very easy to reason about and functions as first class values are very expressive. When affixed to many of the other trappings of normal languages you have a very powerful basis for programming.
>>>a variable stands for an "unknown" and not a mutable slot. Thus, you cannot assign to a variable but instead can only define it within a context.
I'm struggling to understand this. A variable in C is also 'unknown' until you assigned a value to it. Do you, or do you not, assign a value to a variable in FP? If not, then what do you mean when you write "x = 3"?
>>>variables which behave as unknowns instead of mutable slots are very easy to reason about and functions as first class values are very expressive.
Can you show me an example? A short FP code that illustrates your point when compared to an equivalent code in Python or C?
To break down the difference, consider the idea of names versus the idea of "boxes" or "slots". In some languages those two concepts are undistinguishable because names always refer to locations in memory. In "functional"[1] languages they are separate.
As an example, consider a function in a hypothetical language
def foo (y, x):
let z = get(x)
assign(x, y*y+z)
let box = newBox(1)
let inp = 3
foo(box, inp)
let newVal = get(box)
print(newVal)
I'm being really explicit about the idea of things being "named" by variables instead of just "being" variables. I'm also being really explicit about the notion of how boxes undergo mutation. The reason I do this is to isolate this "naming" property and show how simple it is. Variables-as-unknowns are merely names of values given to them in some context. Usually this is either a function abstraction or a let
let x = 3
# now, here, the name `x` refers to a value `3`
def foo(x):
# now, here, the name `x` refers to some value that
# will later be passed to `foo`
[1] For this given definition of "functional"
Your hypothetical language - is it functional? Because if it is, I don't see how it's different from C. If it's not, can you show me the equivalent code in a functional language?
This is how I understand your code example:
def foo (y, x): let z = get(x) assign(x, y*y+z)
Jump to address 'foo', passing a value stored in register y, and an address stored in register x. Load value at address(x) to register z, then manipulate values of y and z, and store the result at address(x). So far so good.
let box = newBox(1) let inp = 3 foo(box, inp) let newVal = get(box) print(newVal)
Allocate memory for an int, put 1 in there, and store a pointer at register 'box'. Next, put 3 into register 'inp', and jump to 'foo', passing values at 'box' and 'inp' as x and y (registers don't change). 'Foo' updates the value at the address which we refer to as 'box' or 'x', and we load this value to register 'newVal', and print it.
The way I see it, if you are using a concept of a 'slot' or a 'box' in your code, you have to use some name (label) to refer to the address of this slot. This label would be the name of a pointer in C, or the name of a variable in Python. If you are using a variable which stores a value directly, the name of such variable points to a register.
How can you separate a name from what it points to? What would it mean, and most importantly, why would you want to do that?
Imagine a (rather useless) program that prints a number.
x = 5 x+=2 print x print x
this prints the number 7 2 times
in the 'context' definition of equality, which we'll denote using let * = ..., each of those assignments generates a context, which I'll show using indentation.
let x = 5 let x = x + 2 print x print x
These two programs do the same thing. However, using names as mathematical variables instead of 'boxes', there is another program we can create using the same 'sequence' of expression tokens (thus giving us greater expressive power).
let x = 5 let x = x + 2 print x print x
this program prints 7, and then it prints 5. In other words, we are able to access previous values of our 'variable' x if we want to, whereas this is not the default behavior of a system with mutable variables. This has an added benefit, not really shown in the previous example, of providing zones of protection from interference from the rest of the program. For example, I can always be assured that within the first context, x will always mean 5, and within the nested context, that x will always mean 7. No function or outside line of code can impact the value that x takes on. This really shines when programming in a team - this gives you assurance that to change the output of your section of the code, another teammate will have to directly alter your code. This localizes the source of future bugs in this code to always be in this section of the code, drastically simplifying the debugging process.
To make these contexts space efficient, modern functional programming compilers analyze when a program no longer needs access to previous value (because they will never again be used in the future), and marks it as 'garbage' to be collected later.
To try and rephrase it one more time - A mutable variable is an actual location in memory. Anyone sharing access to this location in memory in effect has a communication channel open to all of the other linking bits of code. This can be a powerfully simplifying abstraction, in some cases, which is why functional languages generally still provide it by many means, including (in Haskell) the State and IO monads. However, as a default model of resource usage, mutable variables are a poor choice. Generally speaking, you don't really want all parts of the code to be talking to one another. As programmers, whether using procedural, object-oriented, or functional programming, minimizing this kind of communication can help minimize the impacts of future changes. This is why object-oriented languages have private methods and variables, and why there is a trend towards object composition over object inheritance to define more complex behaviors, because both decouple the resulting subsets of code and make them more robust to external forces. Mathematical variables simplify our attempts to achieve this by cutting off the default route for breaking these hierarchical assumptions - shared communication.
The different contexts you're describing look similar to the global/local variables with the same name. For example, I had this problem in C, where I defined a global var and wanted to modify it inside a function. Which failed, because a local var with the same name was created: http://stackoverflow.com/questions/19214293/unable-to-modify... So in this example, 'immutability' was precisely what I didn't want in my program.
Can you please provide a concrete example where this 'feature' is useful?
Also, you're saying "A mutable variable is an actual location in memory". What about the name of immutable variable in FP? How is it implemented? How/where its value is being stored?
The key is to focus on what you can't do. Pointers in C do provide a similar UI to "boxes" that I was describing. But their plain values aren't the same. Consider
int main() {
int x;
x = 3;
x = 4;
printf("x = %i\n", x);
}
$ gcc test.c -o test
$ test
x = 4
main =
let x = 3
in let x = 4
in print x
$ ghc --make test.hs
$ test
4
We could demonstrate this with the following program perhaps
main =
let x = 3
in print ((let x = 4 in x) + x)
$ ghc --make test.hs
$ test
7
The trick with figuring out FP is that it actually feels more restrictive at first. It's a typically higher-level form of expression. You can obviously simulate it all in C (FP languages might even compile down to C) but the goal is to determine what kinds of things can be expressed in the FP language itself.
To learn more, I highly suggest learning just the basics of Haskell or OCaml. Scala would probably suffice as well, though I don't know it as well to say.
Generally, the idea I'm talking about is often called "immutability" (though it's slightly different). Programming with immutable things tends to be easier to reason about because names do not change what they refer to within a context (like x changing from 3 to 4 in the C program).
For example, here's a problem I had in C when I used a local variable with the same name as a global variable: http://stackoverflow.com/questions/19214293/unable-to-modify...
You're saying: "immutable things tends to be easier to reason about because names do not change what they refer to within a context" Can you please provide an example of that? Maybe some code where this 'feature' is useful? Your example of let x = 3 in print ((let x = 4 in x) + x) shows what you mean, but it does not show why would I want to do that.
Thank you very much for your effort to help me understand.
* Higher-order functions
* Pure functions / referential transparency
* Immutability
* A powerful type system
* A declarative style (expression-based)
(Some of the above concepts are closely related, and some people may feel there are other important ones I left out)
A functional programming language is loosely-defined as a language which makes programming in the above style possible, feasible, or easy.