|
|
Log in / Subscribe / Register

Everything Your Professor Failed to Tell You About Functional Programming (Linux Journal)

[Posted January 31, 2006 by ris]

Here's an article on functional programming on Linux Journal. "In computer science, we enjoy using mathematic models, but the science still works if you violate the math. And, much to the dismay of purely functional programming enthusiasts, we almost always do. However, when we embrace the math, sometimes the loss in flexibility is more than compensated for by the increase in functionality."
to post comments

Nomads might make the mathematics *harder*

Posted Feb 1, 2006 0:13 UTC (Wed) by dps (guest, #5725) [Link] (8 responses)

When I learned computer science a functuional programming language just had functions (and fancy type systems). Neither print statement nor variables exist and writing an interactive program with apparent state is very painful (ML is one of the better known examples of such a language). Wadler would be half of the authors of a standard text.

Languages like ML have beatiful mathematics. A not so easy exam questions ran along the lines of "if xs is a finite list and + an assocative operator prove that foldl(xs, +)=foldr(xs, +)".

Nomads seems to gratitously introduce side effects in an impertive language, which will makes formal analysis more difficult---without side effects you can deduce what b=f(a); c=g(b) does from what f and g do. If f() or g() have side effects then tthese must be taken into account too.

Hint: If you find you do not know what f() or g() does, including any side effects, then your code needs fixing.

Nomads might make the mathematics *harder*

Posted Feb 1, 2006 0:55 UTC (Wed) by smitty_one_each (subscriber, #28989) [Link]

s/Nomads/Monads/ , or are you just feeling peripatetic?

For my brain, monads are easier than objects.

Posted Feb 1, 2006 2:27 UTC (Wed) by shapr (subscriber, #9077) [Link] (3 responses)

Monads are both purely functional and allow side-effects.

For in-depth explanations see the nomaware monads tutorial, or see a list of monad implementations in a variety of languages, including C++, Clean, Haskell, Java, Joy, Miranda, OCaml, Perl, Prolog, Python, Ruby, Scala, Scheme, Tcl, and XSLT.

In my experience, the monadic abstraction has several major advantages over the object abstraction, but I'd like to hear your thoughts on the matter.

For my brain, monads are easier than objects.

Posted Feb 1, 2006 19:14 UTC (Wed) by dps (guest, #5725) [Link] (2 responses)

Given that pure fuctional programming language have no variables side effects make no sense---the value of a function only depends on its arguments. This is one of the reasons the maths is beatiful.

Having written an intractive functional program, without using any imperative features (the language had none), I can tell that is possible but very difficult. There were no print statements and no need for them. The main loop was something along the lines of

foo(s,v)=(res(s) v)++foo(read, nstate(x) v)

If you are works the res(s) v computes the output due to s, so a prefix of the result can be computed immediately. The state has to be argument of foo because variables, and control flow, do not exist.

For my brain, monads are easier than objects.

Posted Feb 1, 2006 21:42 UTC (Wed) by dcoutts (subscriber, #5387) [Link]

In his paper "Tackling the Awkward Squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell", Simon Peyton Jones claims that "Haskell is the world's finest imperative prgramming language.

It is a slightly toung-in-cheek claim but if you read what he says you can see that is has some foundation.

I rely on Haskell's ability to manipulate imperative actions as any other value every time I write a Gtk+ GUI in Haskell. The resuling GUI code is generally shorter, clearer and safer than the equivalent program written in C or Java.

Take a look at Haskell's use of monads

Posted Feb 7, 2006 0:12 UTC (Tue) by tmoertel (guest, #29109) [Link]

Haskell uses monads (and its type system) to weave pure and impure computations together in a way that preserves the interesting properties of each. It is an elegant solution that gives I/O a first-class status without tainting the purity of the language. (Monads have proved themselves useful in many other regards, too.)

Regarding your earlier comment, "Having written an intractive functional program, without using any imperative features (the language had none), I can tell that is possible but very difficult," you might be surprised at how straightforward it is to do imperative programming in Haskell. Here, for example, is the code for a concurrent port scanner:

http://blog.moertel.com/articles/2004/03/13/concurrent-po...

Cheers,
Tom

Your claims about ML are inaccurate

Posted Feb 1, 2006 6:45 UTC (Wed) by ccshan (guest, #2723) [Link] (1 responses)

ML has print statements and variables. It does not make it painful to write an interactive program with apparent state.

Your claims about ML are inaccurate

Posted Feb 1, 2006 8:35 UTC (Wed) by eru (subscriber, #2753) [Link]

ML has print statements and variables.

That's why some functional language purists call ML an imperative language...

Nomads might make the mathematics *harder*

Posted Feb 1, 2006 22:13 UTC (Wed) by cgibbard (guest, #35654) [Link]

Monads actually are a purely functional abstraction. They don't mix side effects with the execution of code. If you're thinking of IO, in fact, all that the IO monad lets you do is describe IO actions purely functionally in terms of primitive ones. It doesn't let you execute these actions. At the end of it all, you define a main IO action, and it's the only thing which ever gets executed -- the runtime system evaluates the main expression into an IO action and runs the action as it's built.

IO isn't the only monad though. In contrast to IO, most monads have easy translations with no primitives that need to be defined externally to the language. For example, the type constructor of lists is a monad (and an incredibly useful one at that!). I don't think anyone would argue that lists have too many hard-to-reason-about side effects. The monad operations are just ordinary functions:

return x = [x]
x >>= f = concat (map f x)

This is actually the case with most monads -- you have monad operations which are just ordinary functions. Even in the so called state monad, you're just representing computations which may read from and modify some state of type s, before returning a value of type a as simple ordinary functions of type s -> (a,s). In that monad, we have essentially:

return x = \s -> (x,s)
x >>= f = \s -> let (v,s') = x s in (f v) s'

(often with a little wrapping, using a new data type to hold the functions of type s -> (a,s)). So again, this is just a way of wrapping up ordinary functional programming idioms -- in this case, the use of an extra parameter during recursion to accumulate some state.

Further, the monad operations satisfy a large number of nice algebraic laws, so they're quite easy to reason about. (Hey, they come from category theory, they'd have to satisfy *some* nice universal properties :)

There's nothing magical about monads, or their implementation. In fact, apart from the do-notation which is just syntax sugar, and the fact that IO is a monad in Haskell, they receive no special language support. If the Monad class wasn't defined in the Prelude, you could simply define it again for yourself.

One nice thing is that monads provide a good way to structure and reason about many combinator libraries. You get nicely polymorphic functions which work in any of these very different libraries and contexts, yet behave quite predictably, so you share more code.

If you'd care to read my article on monads, it's up at:
http://www.haskell.org/hawiki/MonadsAsContainers
which takes a different view of monads as simply a generalisation of container types.

too much for the next coder (Linux Journal)

Posted Feb 1, 2006 5:57 UTC (Wed) by b7j0c (guest, #27559) [Link] (3 responses)

amusing and intriguing. i have had brief epiphanies using haskell...one of those moments where you really think the world would actually be a better place only if...

back to reality, the world is hooked on worse-is-better, and you're far more likely to have to use a worse-is-better language like php (perhaps the quintessence of worse-is-better) or java than ml, haskell, or even ruby.

even in present-day tools its unlikely using monads would prove fruitful - the next coder to edit the file would probably just get confused and replace the section with something more mundane.

Re: too much for the next coder (Linux Journal)

Posted Feb 1, 2006 20:50 UTC (Wed) by nevyn (guest, #33129) [Link] (2 responses)

Just because you think X is better than Y doesn't make it a fact. What you are experiencing is "worse is worse", just the majority have a different evaluation of what is "worse" and what is "better".

Re: too much for the next coder (Linux Journal)

Posted Feb 1, 2006 21:18 UTC (Wed) by nevyn (guest, #33129) [Link] (1 responses)

I had wanted to link to worse is worse.

Re: too much for the next coder (Linux Journal)

Posted Feb 4, 2006 4:25 UTC (Sat) by pimlott (guest, #1535) [Link]

I have to say that article is muddled. The author doesn't refute anything in "Worse is Better", he merely refutes a straw-man view that some people might mistakenly associate with "Worse is Better". It would be a shame if anyone passed over Gabriel's wisdom because of this cliche-ridden response.

but the science still works if you violate the math.

Posted Feb 1, 2006 8:30 UTC (Wed) by Wol (subscriber, #4433) [Link] (4 responses)

Doesn't that tell you something?

If the science still works, then the maths must be "wrong". As in "it's not applicable, because it doesn't describe the real world".

Don't get me wrong, understanding the maths is important, but quite often I feel that (academics in particular) people have a habit of taking the Aristotelian road - "the maths is so perfect that it has to be right. All these experiments that prove the opposite surely only prove the scientists are incompetent".

As you may know, I think my discipline of databases suffers terribly from this at the moment :-)

Cheers,
Wol

but the science still works if you violate the math.

Posted Feb 2, 2006 7:09 UTC (Thu) by cgibbard (guest, #35654) [Link] (3 responses)

Your comments (and the related ones in the article) are a little confusing, as using mathematical (or other logical) tools to describe and predict the real world is what science does. I'll interpret your statements as best I can though.

If you mean that if programs don't in fact behave as mathematical models of them say they should, then perhaps the models should be changed, then you will occasionally be right, but in computer science, we have the strange situation that we have control over both the formalisation and the concrete things which we are studying (the hardware and software implementations of our formal plans).

It's far more often in computer science that one has bugs in an implementation than bugs in specification, since mathematical specifications for semantics are usually very high level and concise, and thus harder to get wrong. It may be possible to design something in such a way that it's unimplementable, but that's possible without any formalities, and it's also quite possible to create formal systems which take performance into account.

If you mean that even ignoring computer science, one can still write practical applications, you're also right to a certain extent, however, I'd argue that you'll have more trouble in the long run than if you didn't ignore it.

Having mathematical models of computation which follow strict rules is important as soon as you're writing a program which is very complex, or which needs to be very reliable. It becomes incredibly difficult to prove that your programs are correct if you're writing code in a language with poor algebraic properties. As a result, most people writing code in these languages, even for highly critical applications, are resigned to sitting down with a debugger and hoping to catch enough bugs that not very much goes wrong.

Even if you never actually write out a proof, the fact that it's easy to write proofs about the code means that various regularities exist in the language and design which help you to think about how the program works.

In a system with poor algebraic properties, the code that is there becomes harder to reason about, and so harder to maintain. If a new feature needs to be added, for example, it becomes more difficult to ensure that nothing else breaks. It's harder to refactor code, and harder to understand new code that you're reading.

Using systems with lots of nice properties, one can write code faster, with a greater degree of correctness, and it can still be very practical. One of my favourite examples is one from my own experience.

I wrote a pipeline scheduler and register allocator (initially for PowerPC/Altivec) in Haskell in about 3 weeks and ~600 lines of code and a comparable amount of documentation. That included a parser for an intermediate language. It performed quite well, producing all the possible schedules for a given piece of code at a rate of about 20 per second, greediest first.

In C, it would have likely taken 15000 lines (that's the judgement of my supervisor who was an expert C programmer), and I doubt very much I'd have had the ability to implement it in the time I had.

The reasoning that was necessary, and the code itself, were both greatly simplified by laziness and using a monad (the list monad in particular) to structure the computation. It was also very easy to extend in quite a lot of ways -- adding new pruning heuristics would be trivial (once you knew what the heuristics were), and adding support for other similar architectures, say Intel, would actually be relatively easy. (It would mostly just involve adding data on those architectures, and some code to handle any idiosyncrasies of the pipeline on that arch. You wouldn't even have to rewrite the parser, as it was generated dynamically from the data on the architecture.)

- Cale

but the science still works if you violate the math.

Posted Feb 2, 2006 9:06 UTC (Thu) by Wol (subscriber, #4433) [Link] (2 responses)

Your comments (and the related ones in the article) are a little confusing, as using mathematical (or other logical) tools to describe and predict the real world is what science does. I'll interpret your statements as best I can though.

If you mean that if programs don't in fact behave as mathematical models of them say they should, then perhaps the models should be changed, then you will occasionally be right, but in computer science, we have the strange situation that we have control over both the formalisation and the concrete things which we are studying (the hardware and software implementations of our formal plans).

What I'm saying is that, when the predictions made by the maths and the realities of experiment in the real world don't agree, we have this nasty tendency to assume that the experiment was wrong. We are seduced by the maths.

Your second paragraph falls extremely neatly straight into that trap :-) The program is a mathematical model, and of course the model of the program is a mathematical model :-) Let's assume they are both "correct" and self-consistent.

Your mistake is apparent from the claim "we have the strange situation that we have control over both the formalisation and the concrete things which we are studying". Let's assume we are studying a chemical reaction (ie something in the real world). And our reactor vessel blows up because there is a disagreement between what the model says should happen, and what actually did happen. Well, firstly and obviously, you don't have control over the concrete things you're studying - you've got a load of concrete blasted all over the environment that shouldn't have happened :-)

But anyway, what I'm saying, is that in this sort of situation we have the nasty habit of assuming that because the mathematical model is self-consistent and mathematically correct, that it must also be scientifically correct and the explosion was the result of a bug in the "real world". The fact that our model might simply be the wrong model is very difficult to come to terms with.

Cheers,
Wol

but the science still works if you violate the math.

Posted Feb 2, 2006 18:25 UTC (Thu) by cgibbard (guest, #35654) [Link] (1 responses)

However, I'm talking about computer science rather than chemistry. The fact that the situation is strange is that it doesn't happen in pretty much any other science. Sure, there are things even in CS which are outside of our control but for the most part, we write the programs as well as the models which specify how they should behave.

In physics, if our model fails, and we decide that we really liked it better, we can't change the universe to fit the model. In CS, quite often we can, since the computers and programs are just things which we built ourselves, and the models aren't fundamental to the universe, but abstractions of the machines' operation.

If I have some denotational semantics for the behaviour of a program, and the program doesn't actually follow those semantics in some way, then I may actually decide that I like the semantics, and change the program, or vice versa. More often than not, assuming that I wrote both of them, the high level mathematical description is closer to what I actually wanted, since it is usually an easier mechanism in which to describe behaviour.

Sure, there are some things in CS which are outside of our control. Sometimes we want to construct a semantics for something which we can't change. Sometimes we're discussing time or space complexities or other properties of programs for which there are real-world physical limitations.

However, to a fairly large extent, mathematical models are used in CS to help describe things which we ourselves have control over. At that point, which thing is actually correct becomes a matter of preference.

- Cale

but the science still works if you violate the math.

Posted Feb 3, 2006 8:38 UTC (Fri) by Wol (subscriber, #4433) [Link]

However, to a fairly large extent, mathematical models are used in CS to help describe things which we ourselves have control over. At that point, which thing is actually correct becomes a matter of preference.

Which, to me, says that Computer Science is obviously not Science :-)

As far as I'm concerned, though, if you have control of both the model and the implementation, and "which thing is actually correct becomes a matter of preference.", then computing is a game and not actually worth anything. You have a model. What is the model OF? If you're not modelling something in the real world, what's the point?

And therein lies the point of this discussion. You're interested in whether the model and the program are equivalent - a mathematical/academic obsession. I'm interested in whether the model actually matches the real world sufficiently to be of any use (and I find the current situation with databases a nightmare, precisely because all the research is going to meet your concerns, and none is going to meet mine. And I *DO* think reality and the model are sufficiently disjoint as to cause *real* problems).

Cheers,
Wol


Copyright © 2006, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds