Teenage Haskell
twdkz.wordpress.com
twdkz.wordpress.com
What would be more interesting however, would be to teach a student Haskell first, and then introduce a language such as Python. Would they think Python was stupid or would they be grateful that all of a sudden they could use a for loop?
Or traumatize them forever away from the field of programming.
> Would they think Python was stupid or would they be grateful that all of a sudden they could use a for loop?
I would love to know the answer to this, regardless of my own biases. But Haskell really does require discipline to use, and the kids would probably appreciate the more lax nature of Python.
So, what made learning Haskell a good experience I think was mainly the strong type system. You could basically even early on use functions you barely knew what its name meant solely based on its type signature. It also made the progress of writing a program very nice, you write it and then it fails, you go back and try fix it, and when it compiles it usually worked.
There are some things to keep in mind though. Wild recursion is really the GOTO of functional languages, it's important to teach how to use the generalized folds and traversals early on. Secondly it is important to have simple analogies to concepts such as functors, monoids and monads etc. If you make sure to not care about these strange names then you can go pretty far by just trying to make the type signatures stick together, and it's not important for a beginner to grasp these directly either.
Python was quite smooth to learn coming from Haskell, the syntax is similar and it simply felt like programming in Haskell's do-blocks. It was very easy to get quickly going, I managed to write a little script talking to a JSON API almost directly after reading the official tutorial. I also digged a little bit into the realm of OOP, I wrote a simple game using Kivy. It felt quite nice actually, I could get some code re-use, although it was harder to get that (as newbie) than in Haskell.
EDIT: Something like typed Racket might been even better when I think about it, since Racket got a lot of resources for complete beginners. Then you get the benefit of easy to use syntax too, although syntax is probably not the biggest problem when starting out. For the record I usually recommend Python or Racket when people ask me where to start, because in the end I don't think it matter much what language you go with first, just make sure not to limit the paradigm of languages you learn afterwards.
In short, Scheme (Racket) is regarded as a superior beginner's language because of its simplicity, together with the ability to explore various paradigms (including OO).
Beginners in Scheme subsequently did better with Java than those who started solely with Java.
I think there's a deep lesson in that...
But Haskell really is functional programming, there is no way to accidentally create an easy to use OO-style library. And then there are the monads....
I remember the day I sat down, worked through some examples, and grokked monads. I said, "That's it?"
That's not to say that they can't be hard to learn. I just don't think that they're _inherently_ hard to learn, and I think that they're sufficiently different enough from 'more traditional' CS concepts that said other concepts can hamper your ability to learn them. I suggest http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/ba... if you're still trying to figure them out.
Fun story: one time I had to suddenly explain monads to an English professor, because she overheard me say the word and said, "wait, Leibnitz?"
That was a good 20 years ago, but I just ran into a current student who told me that's still the case, and they still hate it as much as we did.
On topic:
I sometimes wonder if the wins from FP languages are lost on the people not already scarred by the pitfalls of imperative programming. I wonder the same about someone starting with Python instead of something more wordy and cumbersome. I don't think you really can appreciate the ease of use if you haven't already written tons of boilerplate or type information because the compiler is stupid.
At the same time you don't know the price of the ease you're getting, so there is a warped perspective on both the ease of programming and the performance of languages.
Haskell, I think, exists in a sort of middle ground where it's actually really fast but extremely expressive. Maybe someone uninitiated in programming won't have as many problems formulating functional solutions to problems in Haskell too.
The reality was that the tools were slower and buggier than others, the programs different (and slower) but no simpler and the bugs different but stilly just as buggy.
When presented so mindlessly and categorically, any claims of superiority instantly lose credibility. When reality is taken into account, even more so.
This aside, you seem to be talking about the languages themselves, so let's go ahead:
> the tools were slower
Which tools are these? I don't see this as a systematic failure of FP languages.
Which language were you presented with? Did they explain what you're trading your speed of execution for?
I'm asking these questions because it doesn't really seem like you got it and this supposedly being 20 years later it seems like you're purposefully not getting it. In these discussions I find that a lot of people believe FP proponents to be very unpragmatic, but I find that in most cases, such as this one, there is little to no concession made on the "other side".
Most FP languages are not suitable for performance sensitive tasks and most people will admit this. For most other tasks, though, they're just going to allow you to work faster and get to where you're going with less hassle.
I would like to point out that I'm not saying FP languages are just better overall or that an FP language is always the best choice, but I am saying that the principles they employ and teach undeniably are the best. The alternative isn't as much a principle as it is a lack of principle. Flipping individual switches and modifying memory is just not caring.
"doesn't seem like you got it" ... "purposefully not getting it" ... "principles [..] undeniably the best".
No, you like those principles best, and that's about the most you can say. We don't even have solid criteria with which to make that call, never mind there being any type of consensus as to which is "best" (except within specific communities, but with each community having a different consensus and the most closed-minded of these communities usually the most sure of themselves).
Just to head off more ignorant comments: I aced those courses, as well as a few more including the elective "foundations of FP" and did my oral exam on Backus's FP calculus, which inspired me to come up with Higher Order Messaging: http://en.wikipedia.org/wiki/Higher_order_message
I also did some courses on algebraic specification and graph grammars (related to category theory), as well as formal specification with Z (yes, aced those as well). While useful in certain very constrained areas, these techniques trade making the smaller problem better (spec -> code) for making the larger problem ( actual problem -> spec ) infinitely worse.
Of course, functional techniques are a part of my toolbox, as they should be for any professional. However, if they were the only contents or even the majority of my toolbox, I couldn't do what I do and have been doing for the last quarter century.
BS principles are not better than no principles.
Or principles that tie your hand around your back for that matter. And functional principles do that for a lot of cases, with respect to performance, memory impact etc.
Functional languages are not some kind of 2x or 10x multiplier of a programmers abilities. In fact most of the things that made LISP interesting have been ported since ages in modern non-functional languages, from GC to closures, and even macros.
>Most FP languages are not suitable for performance sensitive tasks and most people will admit this. For most other tasks, though, they're just going to allow you to work faster and get to where you're going with less hassle.
Not the case in the real world.
For one, this BS idea forgets all about ecosystems and libraries. Python will let you work faster and get where you're going with less hassle. Functional languages that have 1/10 the libraries available, and in various stages of abandonment because of lack of programmers will not.
>The alternative isn't as much a principle as it is a lack of principle.
Really? For one, what all "FP languages" do when they run, is "flip individual switches and modify memory". The way they model the program is just an abstraction (and a leaky one) from what happens in the machine.
Second, I thought the Church-Turing thesis shows that lambda calculus is equivalent to the Turing machine way, for one.
Third, where did you get the idea that non-FP languages don't have principles? Smalltalk, for one, sure has tons of unifying principles behind it. Prolog. Erlang.
And if Algol was good enough for Dijkstra, modern, 10-times better algol derivatives are good enough for me. Especially if they also have adopted tons of functional paradigms, which you can get to opt to use when it makes sense for your design, and not have them forced upon you.
I recently have been putting a lot of time into learning Haskell and it is amazing. The type system gives me so much confidence, and I have now reached a stage where writing Haskell programs is as concise and fast as writing Python programs, with a lot less bugs and a lot more extensiblity. The thing is that defaults matter. With Python, sure you can achieve a lot of this stability by using a lot of assertions, but who want's to do all that work to write a simple script. With Python, I used to have write once code that I would use for a task and chuck away. With Haskell and its abstractions, I reuse almost all of my code. I have completely replaced Python with Haskell as the programming language I use to do my daily work.
Sure, Haskell is very different from conventional programming languages and initially hard to learn since we all just want to change state. However, personally this style was surprisingly easy to internalize. Instead of modifing data, you are passing it through a series of pipes, transformers and filters to get your final result. It is very easy to reason this kind of code, though with laziness, Haskell makes it hard to reason about its exact performance.
> Really? For one, what all "FP languages" do when they run, is "flip individual switches and modify memory". The way they model the program is just an abstraction (and a leaky one) from what happens in the machine.
Well, all Python programs manage pointers in the end, and flip individual switches and modify memory, so functions and objects and all of that jazz are just leaky abstractions. We should all go back to assembly, or even better, flipping switches.
I believe the IO Monad to be a wonderful abstraction for what happens inside the machine. Monads are wonderful abstractions in general, and first learning how normal monads like the list, State and Maybe monads work is an amazing experience, but realizing how IO is just a special case of the State monad is mind blowing.
> Second, I thought the Church-Turing thesis shows that lambda calculus is equivalent to the Turing machine way, for one.
Yes they are equivalent just as Brainfuck is equivalent to Python, or C to Java, or Fortran to Smalltalk. These are all Turing Complete languages, so obviously they are equivalent!
> And if Algol was good enough for Dijkstra, modern, 10-times better algol derivatives are good enough for me. Especially if they also have adopted tons of functional paradigms, which you can get to opt to use when it makes sense for your design, and not have them forced upon you.
If assembly was good enough for Knuth, why are we not using that? x86 is good enough for me. Why are Algol derivatives forcing me to use the imperative style of code? Why can't I use a modern functional language and and use imperative, unsafe, statefull code when it makes sense for my design?
The problem is that defaults matter, and separating unsafe and safe code has a lot of advantages. Also, IMHO functional code is just easier to read and much cleaner. Instead of writing step by step instructions to the computer, we tell it what to do in a more declarative manner, because the lower abstractions can easily be separated out. Eg:- the canonical quicksort in Haskell [0]
[0] http://www.haskell.org/haskellwiki/Introduction#Quicksort_in...
The whole point of Quicksort is being a fast and in-place sort. That's its entire reason for being (the name kinda gives it away). An algorithm that's slow and not in place is not Quicksort and not "the essence" of Quicksort either. It's some other sort ("Slowsort"?) loosely inspired by a cursory reading of Qicksort and not understanding what Quicksort is about and why it is "quick".
The whole thing is somewhat typical though: "We have discovered that the essence of <well-known-thing> is <completely-different-thing>". No, you have discovered a mapping function from <well-known-thing> to <completely-different-thing> That's not the same as "the essence".
No, there are plenty of people who will debate this, programming languages academics even. There is a vocal FP crowd that fawns over elegance, but there are plenty of other people who are more pragmatic about it.
> I sometimes wonder if the wins from FP languages are lost on the people not already scarred by the pitfalls of imperative programming.
Pity the poor programmers who get things done, write huge beautiful systems, all without worshiping lambdas? And by taking shortcuts ala side effects as a way to making things easier.
> Maybe someone uninitiated in programming won't have as many problems formulating functional solutions to problems in Haskell too.
It depends on how much math they have behind them. You take a mathemegician, sure, but a high schooler who is still having trouble with pre-calc?
Very much so, and also depends very much on the problem at hand. Yes, compilers and yet another RB-Tree implementation can be great in FP. Most real-world problems aren't that. In fact, most real world problems I have encountered (and see) tend to be massively about manipulating state. Often they do little else than shuffle data around.
I sometimes think "computers" are misnamed, because they do so little actual "computation". "Data around-shufflers" might be more appropriate.
The functional programming language is Opal, a language developed at the TU Berlin, it has barely any documentation, a compiler that only works on Linux and OS X, that is if it works because it has quite a few bugs, it further comes with a REPL that sometimes produces failures the compiler doesn't and tooling is non-existant.
So as a new CS student you have to learn using Linux and setup a development environment by yourself with barely any documentation to go on. You then continue learning only the very basics of programming such as what functions are, if statements, recursion, big O complexity, a little bit of parsing and though it's called differently: monads. At the end of the semester you then develop a renderer for a regular subset of HTML that includes only <html>, <head>, <body>, <title> and <p style="text-align: {left, right, center, justify};">.
On top of that the language has a couple of weird features: Every function can be used as any kind of operator if the number of arguments fits. This means that the parser has often problems figuring out precedence rules and you end up adding parenthesis around every expression just to be on the safe side.
Number literals also don't exist. There is a pre-defined set of functions which don't take an argument and produce a number such a 1-12 or so, n^10 for a few n, and a couple of 2^n for a few n. All other numbers have to be explicitly converted from strings. In practice this means you do the latter all the time so 1 turns into ("1"!).
Furthermore variables are defined by name and type. You can have two variables called foo in the same scope, if they have a different type and depending on how foo is used (Opal has type inference) one of the variables is chosen.
The prior feature is effectively necessary because Opal also doesn't have polymorphic functions. It has polymorphic "Structures". A Structure is file you can import, within that file you can define a set of variables that are polymorphic, the types of which are defined by however is importing it either explicitly or implicitly through type inference.
This is pretty much like how you might use the pre-processor in C to achieve polymorphism.
Have I mentioned by the way that a Structure is actually just a header like in C? In the Structure you only define the types of the API, the implementation is in a different file.
So a functions like map requires writing two separate files. Luckily it's in the stdlib.
Overall these features are fine, if everything works nicely but if you have an error somewhere, the compiler can emit massive difficult to understand errors, not unlike what a C++ compiler might produce for code that uses templates heavily.
The language and the choice to use that language is heavily critized by pretty much all students, functional programming however is not. In fact pretty much everyone would prefer if Haskell (which is the functional programming language closest to Opal) were used. The only reason it's not, is that the current prof for that class lead the team who developed the language.
So we were spared that particular disaster, which was and is sold using the same "unquestionable superiority" rhetoric. Instead we dealt with Hope. As in "I Hope it will finish in the next 15 minutes". "It" being a 10-30 line program. Usually it didn't, instead producing a largish coredump.
Our Sun 3-50 diskless workstations didn't help, but hey, Turbo Pascal could compile + execute a hundred lines of code in a second or two on the Z80 card in my Apple II+, a computer with several orders of magnitude less CPU/memory than those Suns.
Later we also used another language, I think it was Miranda. That introduced us to the joys of type inference. Magical when it works, completely inscrutable when it doesn't, especially since you don't get feedback on the cases that do work.
The big problem here is not that the tools were buggy and the languages less than fully thought out, that is fine, if presented that way. The problem is the complete disconnect between rhetoric ("perfection", "everything else is steaming pile of manure") and reality (sort of the opposite).
In the meantime, tools have certainly improved a lot (ghc/ghci on my MacBook Pro are quite tolerable), but the disconnect between rhetoric and reality is still there, because everything else has also improved.
Consider Opal itself: an FP language (so one of the domains FP is actually good at) in active development for more than a quarter of a century by teams using magical, all-conquering, flawless-marvels-of-correctness-producing FP unicorn-technology by teams of programmers that are experts in said technology. And it is, quite frankly, a steaming pile of manure.
EDIT: Hope: http://en.wikipedia.org/wiki/Hope_(programming_language)
FP hasn't been given as much attention as imperative programming languages, especially not when it comes to the important last step of language development, which turns ideas that are nice in theory into tools that are actually convenient to use.
Java is a good example for how much that matters. The language is inelegant and makes it impossible to express yourself concisely nevertheless the tooling is incredibly good, so good that it makes up for quite a few surprises.
A FP IDE that for example shows you inferred types and type errors while you are writing the code, would already help a lot as it could much better visualize the problem, than a compiler that has to describe an error purely with text.
FP languages are not perfect, no language is but they have the potential to be much more powerful in lot of ways than imperative languages. Lisp is a good example for this although it's also a good example that such power can corrupt people to use macros in awful ways.
In any case when it comes to the rhetoric especially from professors, you have to take into account that they have spent their entire life specializing on what they are doing. Of course they are excited by what they are doing and even if they aren't they have a good reason to lie to themselves consciously or not because the alternative is acknowledging they wasted their life on bullshit. They are biased and that's ok, you just have to be aware of it.
Turbo Pascal for example was written by a single guy, Anders Hejlsberg, in about 2 years for several platforms in assembly language, and included an integrated (though primitive) text editor/IDE.
Smalltalk was taken from ST-72 to ST-80 in 8 years, with small teams that also had to invent/implement complete VMs, operating systems, bitmap graphics engines, GUI framework(s) and sophisticated IDEs. You write that it would be nice to have an FP IDE so it could give you better feedback (or were you talking about an existing FP IDE). These guys built the live IDE (even better than types for direct feedback) in a fraction of the time. Does OPAL still compile to C? Does it still use Tk?
Think about Ruby, Python, etc.
I could go on (the VPRI stuff is also amazing), but I think you get the idea: it seems that not only can you be a productive member of society without FP, it sure looks like people can be a lot more productive without FP than with it.
Java is not really a good example of anything. Certainly not of an OOPL: "Java is the most distressing thing to happen to computing since MS-DOS." "If the pros at Sun had had a chance to fix Java, the world would be a much more pleasant place. This is not secret knowledge. It’s just secret to this pop culture." — Alan Kay (who coined the term "object oriented")
I don't quite get why you see LISP as an example for the power of FP, it is a multi-paradigm language with some functional elements, and most of its power comes, AFAIK, from its meta-system.
And HOFs like map or fold have been in other languages since the dawn of time, they're certainly in Smalltalk.
In terms of rhetoric, Peter Pepper might seem like an outlier, but as far as I can tell he is not. You can see it in this very thread: if you don't buy the self-evident awesomeness, it must be because "you didn't understand" and "refuse to understand", it cannot possibly be because you legitimately have a different point of view.
Another example. I watched the following talk by Simon Peyton Jones on data parallel Haskell:
https://www.youtube.com/watch?v=NWSZ4c9yqW8
Interesting stuff. But he has to go and say it: "this is only possible in a pure FP language like Haskell". Hand raised in the auditorium. "Actually, this sort of thing is pretty common in the HPC community, in FORTRAN [under some specific name]". And of course he can't just shut up and read up on things he obviously doesn't know about, he has to retort: "well, that means that it is nothing but a variant of Haskell at this point". Ouch! And finally, at the end of the talk he gives some numbers. It turns out that this amazing thing that's only possible in Haskell needs 6 cores to match the performance of a single core C program. 6:1. That's absolutely pathetic, especially when compared to what the HPC FORTRAN guys are doing. So maybe he shouldn't be lecturing them, they know this stuff a lot better then he does.
Now don't get me wrong, the talk was interesting and thought provoking, but the mismatch between grandness of the rhetoric and the paucity of the results was its usual epically proportioned self.
Object thinking is easier to wrap one's head around than mathematical formal thinking, but that's just because the former uses the brain's innate linguistic hardware (we learn to talk without much effort) while the latter requires training and practice.
Here's the latest course description: http://media.collegeboard.com/digitalServices/pdf/ap/ap-comp...
Just had a look at the curriculum of the Portuguese university I graduated from, a couple of decades ago and they still teach OOP, FP, LP across multiple languages.
The same can be said about using Python et al as the first programming language. How many people quit an introductory course to programming because they didn't like (say) the style of programming in Python, but could get an interest in it if the language being taught was some FP one (or maybe a logic programming language, etc.)? It's kind of hard to tell, because students who get turned away from an introductory course on programming probably aren't going to look up (or even know about) "programming paradigms" and see whether there are alternatives.
Granted, how long would these people survive in the job market if they were able to be "traumatized" by some imperative language? There are certainly more imperative language jobs (or, they tend more to imperative style than FP style) in the job market, it seems. But even if they wouldn't like working as a programmer, they can still use it as a hobby if they like.
I was the TA on the Edinburgh Haskell course over a couple of years, and took the attitude that, whether the students are any good at maths, they've at least seen it before, and so it was something I could use to bootstrap their understanding of the code they wrote.
The Edinburgh course is very nicely paced. Students aren't thrown in at the deep-end. In the first tutorial we had them composing pictures along similar lines to that shown in the OP. By the third tutorial, they're using their repertoire of maps, filters and folds to do basic web scraping. The most advanced stuff we assess them on is writing recursive functions on recursive data-types, like a function that takes a simple mathematical expression and evaluates it. Come the final exam, they can pretend they'd never heard the word "monad."
Interesting question. My first language was (Common) Lisp. Not sure if it was a good or bad choice (wasn't a choice really, more of a coincidence), or if those terms even apply. Anyway, I'm fairly certain it took me much longer than necessary to get my first projects done (hint: some of them were never finished). I spent a lot of time trying to express my ideas in a functional style -- avoiding the loop macro, avoiding side-effects whenever possible etc. Slowly but surely drifting away from the actual problems I had set out to solve.
The feeling I got when I discovered Python is very accurately described in that xkcd comic which pops up in your browser when you type "import antigravity" in the interpreter. Then again, if Lisp was a detour on the path to becoming an "efficient and productive programmer", it was certainly a deeply interesting one which left me hungry for more -- I'm learning Haskell now (who isn't?) and am enjoying it immensely.
[1] http://www3.imperial.ac.uk/computing/teaching/courses/120_1
They would probably be at least as mystified by infinite loops as Python programmers are by space leaks.
Perhaps Python programmers would be baffled by time leaks instead :)
If you go through A Gentle Introduction to Haskell[0] I think you'll see it's a pretty simple language. There aren't that many parts of core Haskell to learn about.
Perhaps the abstractions such as Monad and Functor are more complex, but they don't seem anymore complex than some of the design patterns used to accomplish what they're used for.
Now, true, the syntax is much more complicated than Scheme. You can operators and precedence and all that. But while definitely complex, it is mostly consistent with math notation. I tried to teach with Scheme first (following www.bootstrapworld.org) before I created this, and I found the change in syntax from what they are used to can be a real obstacle for children. This is also consistent with the comment about MIT moving to Python, which similarly has much more complex but familiar syntax.
'All members of this [ALGOL] family are made from more or less the same material and for the same kind of programmers - those who love the machine more than the problem.'
Contrast with Lisp: 'a language that would help programmers solve problems without forcing them to think about the elements of a machine.'
So it really depends on one's interpretation of 'Computer Science', and the choice of what to prioritize from the subject: engineering or ideas.
But something else you wrote brought to mind this rather interesting statement from - of all places! - the introduction to Michael Barnsley's famous book, 'Fractals Everywhere':
'In deterministic geometry, structures are defined, communicated, and analysed, with the aid of elementary transformations such as affine transformations, scalings, rotations, and congruences. A fractal set generally contains infinitely many points whose organization is so complicated that it is not possible to describe the set by specifying directly where each point in it lies. Instead, the set may be defined by "the relations between the pieces." It is rather like describing the solar system by quoting the law of gravitation and stating the initial conditions. Everything follows from that. It appears always to be better to describe in terms of relationships.'
So, rather than condescending, I find this interesting: these are two dissimilar approaches to solving problems.
Your comment about baking an apple pie 'without being able to state any specific steps how to do it but instead describing the pie as some set of interrelationships of the ingredients' was also an excellent statement of the differences between these points of view.
Barnsley's perspective was that relationships may indeed be a better way to describe structures. His concern was fractals, but perhaps the analogy extends to the logical structures that comprise a program.
You can claim that it's interesting that there are these two approaches, but the quotation you gave was definitely condescending, because it flatly states that one approach is better than the other, despite the widespread success of the latter. The argument that it's good to abstract as much as possible from the machine is interesting, but to me it is by no means obvious.
I don't really see the relation with fractals. Although it is an interesting quotation, the relation of fractals to real world phenomena is often very dubious.
All functional languages can express a sequence of steps. More yet, on most of them you can later decide to transform the sequence, instead of just generating code from it.
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.
Now that i am brainstorming anyway. Something like http://scratch.mit.edu would be so much nicer if it were a functional language! Instead of confusing blocks that maintain state every block is just a standalone welldefined function and combining blocks is just functional composition and application! I think it would be reaallt easy for a kid to digest mentally: blocks have inputs and outputs, thats it.
Does anybody know if there are projects tjat accomplish this?
Scratch would be impossible to use as a functional language, especially for the logo-style turtle procedural behavior they are aiming at.
Here's what it looks like: http://brick.cs.uchicago.edu/Courses/CMSC-16100/2013/lecture...
The normal introductory CS course is taught in Scheme. Actually teaching - even acknowledging the existence of - functional programming was a major reason I chose that department.
Can someone explain this line?
So, if "a" and "b" are pictures "a & b" is typechecking.
To be more precise, if you account for currying, it says that the & operator takes a Picture and returns a Picture -> Picture function. This function can then be applied to a Picture to yield a Picture. It's as I explained above but with an intermediate step.