Re: Haskell, anyone?

[Hadrien Grasland <hadrien.grasland@gmail.com>]

Le mercredi 18 novembre 2015 10:23:15 UTC+1, Paul Rubin a écrit :
> > My message was about the fact that a program with recursion is about
> > as hard to read and understand as an old-fashioned program featuring
> > gotos. Actually harder...  Your counterpoint was that recursive code
> > is easy to *write*,
> 
> I don't find the recursive version harder to read.  In the goto version,
> the variable is changing while the thing runs, so at one place it's 5
> and at another place it's 4, and I have to keep track of that, and it's
> potentially exponentially worse when there's more than one variable
> changing.  In the recursive version, the values don't change.  Yes you
> have to be aware of possible stack consumption but that becomes second
> nature, and there are also tools that can monitor your code for space
> consumption to catch any problems.

What I am saying is that even if values are indeed immutable in functional languages, recursion is used as a way to cheat the system and make them change on a conceptual level. That when you recurse into a list, what you mean is really "okay, now let's start over from the beginning of this function, this time considering the tail of the list instead of the full list".

For example, if you wanted to explain the factorial to a student who has never been exposed to the concept, chances are that your first approach wouldn't be to write on a blackboard

"fact n = n * fact (n-1)
fact 1 = 1"

Instead, you would start with a human-readable definition that looks like this :

"fact n = n * (n-1) * (n - 2) * ... * 2 * 1"

Then you would explain how, concretely, such a quantity is computed using some iterative algorithm, which itself may either be recursive and use an implicit accumulator in the form of the program's stack, or use a loop and an explicit accumulator.

In any case, if you are using a machine which can only perform one binary operation at a time, you will always need an accumulator to compute the final result. In functional programming, what you've done is essentially to forbid yourself from explicitly manipulating the accumulator. You leave it to the implementation instead. That's an interesting choice... but someone trying to understand a recursive program will still need to "play the computer" and figure out what the machine is doing with its mutable accumulators at some point.


> > readability and ease of writing are different goals, which are often
> > at odds with each other. I believe they are in the case of loops vs
> > recursion.
> 
> It's probably mostly a matter of what you're used to.  If I look at a
> Swedish web page and can't understand much of it, that's because I don't
> know the language, not because of the style or ideas in it.

I would gladly challenge this claim by picking two large groups of 10 years old who have never been exposed to imperative programming yet, trying to explain to each of them how to do compute something using accumulators and recursion, and comparing how much time it takes and what the average success rates are. But I'm lacking the resources ;)

The thing is, our world is imperative. We don't exist, then we are born, then we are alive, then we die, then we stay dead. The horrible events that happened in Paris this week-end cannot be erased by moving up the call stack. The state of things around us keeps changing, and we learn mathematics by moving our fingers, drawing schematics on mutable paper, and writing down equations. In that sense, I believe that imperative constructs better match the world we are used to living in, and should thus be easier to learn and understand.

This does not mean that there isn't a benefit to the functional ways. But I don't think that we can handwave away their additional complexity with a simple "it depends on what you're used to". Functional constructs are, indeed, less intuitive, and according to Occam's principle such extra learning complexity deserves a good motivation (which I believe most functional programming fans will be happy giving anyway).


> > And I believe there is also such a usability compromise at work when
> > you need to give up on data structures which everyone knows about, and
> > use more sophisticated and obscure ones, because your programming
> > language does not support very well the conventional abstractions.
> 
> Again it's a matter of what you're used to and what you consider
> conventional.  There are some intro classes being taught with Haskell
> and ML these days, and SICP back in the day used Scheme in
> mostly-functional style.  If you're writing concurrent programs you
> should know about those immutable structures anyway.

I'm writing programs for massively parallel GPU processors, and last time I checked Blelloch's scan was still one of the most efficient algorithms ever devised for performing cumulative sums on these architectures. But what that algorithm does to data would most certainly make any fan of immutability shiver...


> > So far, my impression is that in the philosophy of functional
> > programming, it is okay to sacrifice readability and make the life of
> > newcomers harder by using highly sophisticated abstractions even when
> > they are not strictly necessary,
> 
> I'd say Haskell is at the high end of the sophistication scale for
> general-purpose languages, so that critique applies more to it than to
> (say) Scheme or ML.  But IMO that sophistication also makes it the most
> enlightening for programmers trying to expand their technical range.
> Ocaml may be more practical and I want to try using it sometime.

Well, I'm learning OCaml using a pretty nice MOOC which has been set up by my former university. If you're interested the address is

https://www.france-universite-numerique-mooc.fr/courses/parisdiderot/56002/session01/about

I guess it's now a bit late to join this session, but given its immense success, I'm pretty sure that they will schedule another next year if you're still interested :)

Oh, and if you end up on a French page by mistake, don't fear. There should be a way to change the language somewhere, and even if the FUN website is bilingual, this class is taught in English.