Learning Functional Programming through Multimedia

ijones writes "Andrew Cooke recently reviewed for Slashdot Purely Functional Data Structures, which is on my book shelf next to The Haskell School of Expression: Learning Functional Programming through Multimedia by Paul Hudak from the Yale Haskell Group. In his review, Cooke presented an overview of some available functional programming languages, such as OCaml, SML, and of course Haskell. Havoc Pennington once called Haskell 'the least-broken programming language available today.' Haskell is a purely functional, lazy, statically typed programming language. You can read more about Haskell itself here." Read on for ijones' review of The Haskell School of Expression. The Haskell School of Expression: Learning Functional Programming through Multimedia author Paul Hudak pages 363 publisher Cambridge University Press rating 9 reviewer Isaac Jones ISBN 0521644089 summary Learn to program in a functional style in Haskell by implementing graphics, music, and robots simulations.

As the title implies, The Haskell School of Expression introduces functional programming through the Haskell programming language and through the use of graphics and music. It serves as an effective introduction to both the language and the concepts behind functional programming. This text was published in 2000, but since Haskell 98 is the current standard, this is still a very relevant book.

Haskell's standardization process gives us a window into two different facets of the community: Haskell is designed to be both a stable, standardized language (called Haskell 98), and a platform for experimentation in cutting-edge programming language research. So though we have a standard from 1998, the implementations (both compilers and interpreters) are continually evolving to implement new, experimental features which may or may not make it into the next standard.

For instance, the Glasgow Haskell Compiler has implemented a meta-programming environment called Template Haskell. Haskell is also easy to extend in directions that don't change the language itself, through the use of Embedded Domain-Specific Languages (EDSLs) such as WASH for web authoring, Parsec for parsing, and Dance (more of Paul Hudak's work) for controlling humanoid robots.

Before we get too far, I should offer a disclaimer: The Haskell community is rather small, and if you scour the net, you may find conversations between myself and Paul Hudak or folks in his research group, since I use some of their software. That said, I don't work directly with Hudak or his research group.

In fact, the small size of the Haskell community is a useful feature. It is very easy to get involved, and folks are always willing to help newbies learn, since we love sharing what we know. You may even find that if you post a question about an exercise in The Haskell School of Expression , you'll get a reply from the author himself.

I consider this book to be written in a "tutorial" style. It walks the reader through the building of applications, but doesn't skimp on the concepts (indeed, the chapters are meant to alternate between "concepts" and "applications"). In some ways, the code examples make it a little difficult to jump around, since you are expected to build upon previous code. The web site provides code, however, so you can always grab that and use it to fill in the missing pieces.

For readers who wish to use this book as a tutorial, and to implement all of the examples (which is highly recommended), I suggest that you grab the Hugs interpreter and read the User's Guide while you're reading the first few chapters of The Haskell School of Expression. Hugs is very portable, free, and easy to use. It also has an interface with Emacs. Unfortunately, some of the example code has suffered from bit-rot, and certain things don't work out-of-the-box for X11-based systems. The bit-rot can be solved by using the "November 2002" version of Hugs. This is all explained on SOE's web page.

The Haskell School of Expression should be very effective for programmers who have experience in more traditional languages, and programmers with a Lisp background can probably move quickly through some of the early material. If you've never learned a functional language, I highly recommend Haskell: Since Haskell is purely functional (unlike Lisp), it will more or less prevent you from "cheating" by reverting to a non-functional style. In fact, if you've never really looked at functional programming languages, it may surprise you to learn that Haskell has no looping constructs or destructive assignment (that is, no x = x + 1). All of the tasks that you would accomplish through the use of loops are accomplished instead through recursion, or through higher-level abstractions upon recursion.

Since I was already comfortable with recursion when I started this book, it is hard for me to gauge how a reader who has never encountered recursion would find this book's explanation of the concept. The Haskell School of Expression introduces recursion early on, in section 1.4. It is used in examples throughout the book, and if you follow along with these examples, you will most certainly be using it a lot. The introduction seems natural enough to me, but I note that Hudak does not give the reader any extra insight or tricks to help them along. Not to worry, though; recursion is very natural in Haskell and the reader may not even notice that they are doing something a little tricky.

The use of multimedia was a lot of fun for me, and should quickly dispel the myth that IO is difficult in Haskell. For instance, Hudak has the reader drawing fractals by page 44, and throughout the book, the reader will be drawing shapes, playing music, and controlling animated robots.

Any book on Haskell must be appraised for its explanation of monads in general and IO specifically. Monads are a purely functional way to elegantly carry state across several computations (rather than passing state explicitly as a parameter to each function). They are a common stumbling block in learning Haskell, though in my opinion, their difficulty is over-hyped.

Since input and output cause side-effects, they are not purely functional, and don't fit nicely into a function-call and recursion structure. Haskell has therefore evolved a way to deal safely and logically with IO through the use of monads, which encapsulate mutable state. In order to perform IO in Haskell, one must use monads, but not necessarily understand them.

Some people find monads confusing; I've even heard a joke that you need a Ph.D. in computer science in order to perform IO in Haskell. This is clearly not true, and this book takes an approach which I whole-heartedly agree with. It gets the reader using monads and IO in chapter 3 without explaining them deeply until chapters 16 (IO) and 18 (monads). By the time you get there, if you have heard that monads are confusing, you might be inclined to say "how is this different from what we've been doing all along?" Over all, I was pleased with the explanation of monads, especially state monads in chapter 18, but I felt that the reader is not given enough exercises where they implement their own monads.

If you're worried that drawing shapes and playing music will not appeal to your mathematic side, you will be pleased by the focus on algebraic reasoning for shapes (section 8.3) and music (section 21.2), and a chapter on proof by induction (chapter 11).

After reading this book you will be prepared to take either of the two paths that Haskell is designed for: You can start writing useful and elegant tools, or you can dig into the fascinating programming language research going on. You will be prepared to approach arrows, a newer addition to Haskell which, like monads, have a deep relationship to category theory. Arrows are used extensively in some of the Yale Haskell group's recent work. You will see a lot of shared concepts between the animation in The Haskell School of Expression and Yale's "Functional Reactive Programming" framework, Yampa. If you like little languages, you'll appreciate how useful Haskell is for embedded domain-specific languages. It may be even more useful now that Template Haskell is in the works. Andrew Cooke described Purely Functional Data Structures as a great second book on functional programming. In my opinion, The Haskell School of Expression is the great first book you're looking for.

You can purchase Learning Functional Programming through Multimedia from bn.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.

Comments

Two words: mod_haskell

[Anonymous Coward]

If there's no Apache module for it, it's not a real language. End of discussion.

It may teach you how to functionally program,

[Savatte]

but chugging mountain dews and microwaving hot pockets are things that have to be learned through experience. Books are always a great source, but the lifestyle behind the teachings of the book can't be taught.

Good book, but won't get you up and running

[Ben Escoto]

I've read this book and think this is a good book for learning Haskell (perhaps the best one) and that it explains monads well.

However, it won't get the reader fully up and running as a productive Haskell programmer, because for that it is basically required that you master the GHC's (Glorious/Glasgow Haskell Compiler) standard library. Otherwise you won't know how to use a fast unboxed array, etc. This library is actually intelligently designed, but it is poorly documented, and there are lots of quirks for people who aren't totally familiar with Haskell yet. The best way to learn still seems to be to read the Haskell newsgroup and look at other people's code.

But Haskell is an extremely interesting language and well worth learning IMHO.

Re:Good book, but won't get you up and running

[johnnyb]

Very cool! I've been into functional programming a lot, but have never been able to get my mind fully around monads. All of the documentation available seems to assume that you already know what they are.

Is there any good stuff on monads for beginners on the web?

Re:Good book, but won't get you up and running

[Godeke]

Herein lies the rub in getting adoption of any of the more "esoteric" (read: not procedural) languages into the mainstream: libraries that require "understanding" of the functional model. After spending years interviewing programmers I can safely say that most barely remember the functional languages they were taught (if they were taught). Try to then force them to use an "alien" library that works in a functional way, and you might as well ask them to chop their arms off and thresh wheat.

I sometimes suspect that .NET may be the only hope of getting functional programming adopted by the maininstream. Currently the CLI has limitations that hamstring functional languages, but Microsoft has actually been bothering to try to rectify those problems. If they do, I would *love* to run ocaml or Haskell with the .NET infrastructure to back up the boring routine work. For that matter *any* major libarary of functionality accessable to a functional language.

Re:Good book, but won't get you up and running

[jovlinger]

Ask again in comp.lang.functiona;l the boffins there are pretty good at explaining this precise question (a VFAQ).

For now, think of monads as bathroom fixtures and monad combinators as plumbing.

You COULD implement variables with state by creating a purely-functional assoc-list and explicitly threading it through your code. The state monad does that for you automatically, by forcing you to write your code as higher order functions, and by linking up the plumbing for you behind the scenes.

As a much simpler example, consider exception handling, were instead of returning a value of type t, a function that can fail returns the type (Maybe t), indicating failure or a returned result.

datatype Maybe t = Fail | Ok t

you could write code like so:

case (funone ...) of
Fail -> Fail
| Ok r -> case (funtwo .. r .. ) of
Fail -> Fail
| OK s -> ....

All that fail handling gets old pretty quick. Instead, wouldn't it be nicer to write

runM (bindM (funone ...)
(\r-> bindM (funtwo .. r ..)
(\s -> ... )))

In haskell, this can also be written:

runM (funone ... `bindM` \r->
funtwo .. r .. `bindM` \s ->
...)

(or also using do syntax, but I really don't like that)

bindM is a monad combinator, the (\x -> ...) are monads. runM encapsulates the whole monad as a normal value.

unitM :: a -> Maybe a
bindM :: Maybe a -> (a -> Maybe b) -> Maybe b
runM :: Maybe a -> a

these are normal functions, no magic needed (written here using case rather than pattern matching to highlight similarity to above code)

unitM r = Ok a
runM m = case m of
Fail = error "oops!"
| Ok r = a

bindM m f = case m of
Fail = Fail
| Ok r = (f r)

(./'s ecode tag is Borken, I think)

... anyway, so what? The cool thing here is that in the case of IO (where instead of doign exception pattern matching, the monad combinators pass a representation of the whole external world), we can prove that the code inside the monads cannot ever directly access the world representation. Thus, the world is single-threaded through the computation. This is good, because then we can skip passing a representation, and just do the IO operations directly on the real world. So we can actually do side-effecting operations in a pure language.

if this doesn't seem like magic, you are either much to smart, or have missed something.

Re:Good book, but won't get you up and running

[jovlinger]

I thought that the CLI security model was inherently incompatible with the sort of low-level stack and closure manipulation you need to either get tail-recursion of laziness.

Re:Good book, but won't get you up and running

[Anonymous Coward]

Try F#. It's OCaml ported to .NET.

Re:Good book, but won't get you up and running

[Godeke]

MSDN Academic Alliance has some articles on progress being made on using functional languages on the CLI. Microsoft seems to be aware that there is value here, but they are moving cautiously.

Re:Good book, but won't get you up and running

[smittyoneeach]

One interesting point on the haskell website was that SQL is almost a functional language.
I, for one, do all kinds of wild data gymnastics in SQL, and wonder if more could be done to 'get people in the door' with SQL DML statements as a lead-in.
Always wanted to do more with functional programming, wondering if EMACS Lisp might prove more immediately fruitful...

Re:Good book, but won't get you up and running

[3.1415926535]

For those not in the know, the "do" construct that jovlinger so greatly dislikes allows you to write that big mess of lambdas and bindM applications as simply

do
r <- funone ...
s <- funtwo ... r ...
...

providing a very elegant syntax for sequential operations while keeping the whole thing nicely pure.

Re:Good book, but won't get you up and running

[peripatetic_bum]

A better book for functinoal programming is actually one about python.Its called http://www.amazon.com/exec/obidos/tg/detail/-/0321 112547/qid=1079471944/sr=8-1/ref=sr_8_xs_ap_i1_xgl 14/102-3354031-2256126?v=glance&s=books&n=5078 46 Text Processing with Python and while it only deals with 'text'. The author explains that tends to cover almost everything we do with computers these says and goes on to explain that pyhton is kind of schizophrnic in that while it is ver object oriented, It is also very functional-programming-ly :) oriented. Its just the python doesnt tend to showcase that side, but within the developers there is a strong bent towards functional programming. Anyway, I find the book extremely useful when I need to learn the best way to do something python and highly recommend it to anyone that wants to develop their python skills and/or learn functional programmign since he explains it very well. Thanks for reading

Re:Good book, but won't get you up and running

[johnnyb]

This looks really good! I'm printing it off right now.

Re:Good book, but won't get you up and running

[Godeke]

SQL is a declarative language, which is probably why it feels functional. Declarative languages allow the user to specify *what* you want, and then the underlying engine determines *how* to get it. SQL in some ways is closer to PROLOG, which is a declarative logic language (in fact, it is trivial to create SQL like queries in PROLOG).

Functional languages can implement declarative syntaxes easily, but the real defining factor is that functions are "first order" objects, which can be applied, manipulated and passed. Frankly, if SQL had first order functions, many wild data gymnastics would be vastly simpler. I grumble at the lack of code reuse in SQL (and I say that as a big fan of the ease of use of SQL on the whole). For example, in SQL I must repeat my subquery every time I wish to apply it.(1) Calculations must be specified both in the select list and the conditional if they are used in both places, instead of being defined once and the results being available (some SQL dialects have workarounds for this). Recursion is right out (a hallmark of functional languages is heavy use of recursive functions) which makes navigating tree structures a total bear (PSQL has extensions for trees, but not very clean ones).

Perhaps future developments that bring SQL closer to the true relational model (which has deep roots in set theory) which would make it possible to bring it closer to a true functional language as well. I think SQL would benefit wildly from the ability to define common structures (functions) and yet be able to apply the optimizer to the end result.

(1) Footnote: T-SQL has "user defined functions", but the impose a nasty overhead because they are not part of the query optimization process.

Re:Good book, but won't get you up and running

[Anonymous Coward]

Well, Microsoft Research Labs does have F# available, with some integration into Visual Studio .Net. Not sure how/if it's usable by #Develop, Eclipse, et al.

Re:Good book, but won't get you up and running

[Anonymous Coward]

Most people think of a tree and implement it in SQL essentially as a one-way linked list, i.e., RecordID, ParentRecordID. These just are a PITA to navigate.

Others (Joe Celko, for one "SQL For Smarties") have proposed that a L-R list would work better, in that instead of storing the connection points, you are storing the edges as L-R pairs. The only problem is updating the L and R keys on inserts and deletes would require either triggers or using stored procedures to maintain the key list, so this would bog down greatly for OLTP systems. But they certainly are a dream to query up *and* down the tree, unlike the single linked list implementation!

And, they would probably work better than Oracle's functions that support hierarchical queries.

Re:Good book, but won't get you up and running

[k_head]

Actually user defined functions are pretty common. PGSQL has them as does mysql.

Re:Good book, but won't get you up and running

[k_head]

Geez. Here I thought perl was hard to read.

Re:Good book, but won't get you up and running

[Kouzdra]

There is interesting connection exists beetwen monads, comprehension syntax and databases & SQL. For example, see the:

"Comprehension Syntax"
http://sdmc.lit.org.sg:8080/~limsoon/psZ/ blstwsigm odrecord94.ps.gz

and more papers about Kleisli DBMS - for example:
http://sdmc.lit.org.sg:8080/~limsoon/psZ /bntwtcs95 .pdf.gz

on http://sdmc.lit.org.sg:8080/~limsoon/limsoonpapers .html

PS: Comprehension syntax is syntax like the:

[ a*b | a - list1, b - list2]

Comprehesions have a close correspondence with monads. In Haskell (before Haskell-98) comprehension actually was the syntax sugar for monadic operators -

do
a - list1
b - list2
return a*b

is monadic equivalent of the previous expression (it's really works and does the same thing - Haskell lists are Monad's) and is very natural and flexible syntax for database queries (expamples can be found in "Comprehenstion syntax" paper). Underlying semantic also interesting.

This is because other, may be even more interesting, property of Monads: Monad is the formalisation of "collection" abstraction. List (threated as Monad) can be viewed as set of states of nondeterministic "world" with many "parallel" and forking "thread's of execution".

In another interesting paper about monads application "Monadic parser combinators" (see on http://www.cs.nott.ac.uk/~gmh/bib.html, this page also contains many other functional stuff), monads are used in this way for backtracking implementation in parser.

Re:Good book, but won't get you up and running

[Godeke]

The twenty thousand dollar question is: does PGSQL and mysql actually use them in the optimization step? As far as I know they do not (and I am positive that T-SQL does not), which means if you query other tables, instead of converting them into a join, or a subtable scan, the function just gets blindly executed for every row. This makes them far less useful than if the optimizer were able to treat them as part of the actual query (i.e., useful for expressing redundent mathmatical operations, but not for more complex uses.)

For example, I have seen someone write a UDF that calculated the total of the invoice lines on an invoice (not the real example, but functionally equivelent). If you run a SUM(lineamount) with a left join into the invoice line table, the optimizer will do a lot of work for you. The UDF instead just was called on each record in the result set, and was two orders of magnitude slower when used on a report. That means a 0.3 second query becomes a 30 second query.

Re:Good book, but won't get you up and running

[k_head]

My guess is that the optimization does not go that far. I don't know how it could really. If each invocation (per row) gives a different answer then you probably can't really optimize it anyway. Maybe if they included a keyword so you can let the compiler know it's a static number. For example select myfunc(param) STATIC, mycol from mytable. That way the compiler would know to run the function only once.

Learning Haskell is too easy.

[karmaflux]

They've got a whole course online! FOR FREE!

The 'bottom' operator

[Anonymous Coward]

Haskell is perhaps best known for its use of the bottom operator. When parenthetised, its ASCII representation looks kinda like a...

Well, I'll let you be the judge: (_|_)

Re:The 'bottom' operator

[Anonymous Coward]

if 8==D (_|_)

The day I can...

[lpangelrob2]

Multimedia?

The day I can use Haskell to compile and output Flash files I'll be happy. Or cry. I'm not sure which at this point.

Re:The day I can...

[Anonymous Coward]

Oddly enough...

I am working on a Haskell library that allows you to write haskell programs that output SWF files. It includes a scheme->SWF byte-code compiler so you can use scheme instead of action script.

Sorry, no URL.

Re:The day I can...

[lpangelrob2]

Oddly enough... I am working on a Haskell library that allows you to write haskell programs that output SWF files....

Yup. I'm crying.

:)

Haskell

[ultrabot]

Anyone noticed how incredibly unpractical Haskell is? It sacrifices too much by taking the FP purity too far.

Also, apparently the Haskell people are way too intimately associated with Microsoft (isn't Cambridge some kind of Microsoft stool pigeon these days?). One just *has* to suspect that they are up to no good. We need to inspect this connection further before giving them the benefit of a doubt ;-).

Yes, I truly felt like burning some of that Karma of mine :).

Re:Haskell

[machead526]

Cambridge? Try New Haven. And, while the Yale CS department sends its fair share of CS undergrads to Microsoft, I'm not aware of any evidence that the faculty is too cozy with the company. (Disclosure: I graduated the Yale CS department six years ago, and went to work for Microsoft for a few years.)

no SMP support

[Anonymous Coward]

lack of SMP support in Erlang and Haskell really makes them hard to choose for enterprise projects.

Some more useful Haskell resources

[tmoertel]

If you're interested, I recently gave a short talk about Haskell for the local Perl Mongers. The slides and notes are available online here: Haskell for Perl Hackers.

If you want to see some Haskell code, I have some more concrete examples here:

• PXSL -- Parsimonious XML Shorthand Language, which is implemented in Haskell. (Haskell sources)
• A concurrent port scanner in one page of Haskell
• Cheating Hangman in Literate Haskell (and Perl)

I have written a lot of little projects in Haskell. You can find some of them in links from my user info page.

Also, one of the best resources on Haskell is the HaWiki: HaWiki.

Do give Haskell a try. It is an amazing programming language.

Re:Some more useful Haskell resources

[Anonymous Coward]

Have never seen haskell before so this might be a stupid question. is there a typo, should:

Higher-order functions (2)

Haskell's map is a true higher-order function:
incList = map (1 +)
incList [1,2,3] ) => [2,3,4]
flip map [1,2,3] (1 +) => [2,3,4]

realy be:
flip map [1,2,3] (1 +) => [4,3,2]
?

Re:Some more useful Haskell resources

[Anonymous Coward]

no

Why isn't Haskell more popular?

[Chilliwilli]

I just can't understand why it's not used more. Personally I feel I was taught Haskell too early.. I was taught in my first weeks at uni before I even knew C. At the time I really struggled, all I knew about programming was BASIC and Haskell seemed alien and I hated it and dismissed it completely until recently. Now that I have much more experience of programming and functional languages I sometimes wonder why I ever touch C++ or Java. If I'd be taught Haskell in my penultimate or final year of university I'm pretty sure I'd have taken to it far more kindly.

Re:Why isn't Haskell more popular?

[ameoba]

It seems strange to introduce functional programming early & then abandon it for imperative programming. The general trend, when introducing FP early is to carry it through the early part of the curriculum to help stress the importance of doing things right & somewhat separate the theory from 'real world' work (it also puts people on a more even basis and prevents the PHP/VB/HTML kiddies from being able to pretend they know everything comming into the program). Some good arguments can be made towards this approach, but I think the real secret to a good CS program is having good professors who care about their work and motivated students; the language of instruction isn't really too important (unless it's exceptionally bad).

OTOH, when you see FP towards the end of the program, it's generally a case of "here's some things that we think you should be familiar with so you can sound educated at cocktail parties". In my case, it was "Programming Paradigms" class that talked about functional & logical programming (SML and Prolog) along with various abstract/theoretical language design ideas (and the professor introduced the unit on Prolog by saying "It's an interesting toy language but I can't see ever actually using it for anything productive").

Re:Why isn't Haskell more popular?

[Dusty]

I just can't understand why it's not used more.

I'd guess because implementing recursive programs on a CPU isn't very efficient. The usual technique involves pushing the parameters on to the stack on every function call, leading to a stack that's full of data that's identical or almost identical. 'Destructive assignments' (i.e. i++) inside a loop are a much better match for the CPU's architecture.

Re:Why isn't Haskell more popular?

[pHDNgell]

I'd guess because implementing recursive programs on a CPU isn't very efficient. The usual technique involves pushing the parameters on to the stack on every function call, leading to a stack that's full of data that's identical or almost identical. 'Destructive assignments' (i.e. i++) inside a loop are a much better match for the CPU's architecture.

You should probably consider looking at assembler output from ocamlopt before saying stuff like this. Recursive loops are very efficient there. Although things like i++ are actually popular in OCaml, it's not necessarily done, and doesn't seem to add much efficiency.

(Can't speak for ghc, but I assume it's similar).

Re:Why isn't Haskell more popular?

[TwistedGreen]

Ah, I don't really believe in any special 'formula' for learning. You either understand it, compartmentalize it, and use that understanding when you deem it appropriate... or you're missing something. Sure, a certain order can make this process easier, but in the end it shouldn't make a big difference. You're aware of your knowledge and your habits, and that's the first step. The next is adjusting them!

Using this 'habits' reason just seems to me like an excuse. If it really is worth it, embrace it! Why keep yourself in old ruts just for the sake of comfort?

I personally find functional programming to be quite deliciously elegant. I've dabbled in Scheme and yum, it's good stuff. You're right... it should be used more.

Re:Why isn't Haskell more popular?

[jovlinger]

The problem is that haskell is lazy.

yes, this is a real problem. I've spoken w/ some of the implementors, and they really thought that strictness analysis would get them a whole lot more.

Lazyness sucks not so much for speed (but this is indeed an issue), but for interacting with foreign functions, and mostly because it breaks tail-recursion. You don't often notice, because haskellers tend to use programming idioms which don't rely solely on tail-recursion.

It also makes predicting the performace of your program almost impossible. Chris Okasaki mentions that most lazy programs are analysed as if they were strict.

A second, smaller problem is that haskellers are really smart. really really smart. This makes easily approachable texts pretty thin on the ground. Two sentences in, you're being bombarded by catamorphisms, anamorphisms, and monoids.

Bird and Wadler is a really nice introductory text.

Re:Why isn't Haskell more popular?

[GnuVince]

Most functional programming language implementations optimize tail-recursion, so it's not a problem. For example, in O'Caml, a non-tail-recursive factorial function looks like this:

let rec fact n =
if n <= 1 then 1
else n * (fact (n - 1));;

But, as you can see, the answer is kept on the stack, so that particular function can overflow. However, consider this one:

let fact n =
let rec fact_aux acc n =
if n <= 1 then acc
else fact_aux (acc * n) (n - 1)
in
fact_aux 1 n;;

Since the answer is always kept in acc, it's an iterative process, so it will never overflow if the compiler optimizes it. O'Caml does it, Scheme implementations do it, I think Haskell does it, many Common Lisp implementations do it, etc. So it's not a problem.

Re:Why isn't Haskell more popular?

[samweber]

This is an example of one of my pet peeves: the "argument via stupid compiler". It's not actually the case that "the usual technique involves pushing the parameters...." -- that's just an explanation of recursion that is often given to first-year undergrads. Any compiler that actually implements a functional language this way would be considered unbelievably broken.

The problem is that not only are compilers much more intelligent than people usually give them credit for, but CPUs these days do so much prefetching and pipelining that it is very hard for a person to predict what instruction sequences would actually be most efficient.

Re:Why isn't Haskell more popular?

[lordholm]

Usually compilers can detect this and treat recursive calls as loops instead of as function calls. I know that some C-compilers do this. In-fact, it is imperative in functional programming to be familiar with tail recursion and lazy evaluation.

If you don't know about these terms, then don't make any comments about the efficiency of functional languages.

By the way, treat languages as tools. I know Haskell, Erlang, C/C++/Objective-C, Java, PHP, Pascal, Python, MPD, AppleScript and 5 variants of assembler. What do I do with all these languages? Well I pick one that is suitable for the task at hand. And if none of them fits my needs, I pick a language that suits my needs and learn it.

Oh well, I'm ranting... but you probably get my point.

Re:Why isn't Haskell more popular?

[Anonymous Coward]

if you're looking at assembly anyway, you might also look at the output of i++;

i don't know of any assembly instructions that say, store word + 1 at address, do you?

Re:Why isn't Haskell more popular?

[BetaJim]

Speaking for myself: I've read about Haskell several times in the past three or four years and started reading some tutorials. The problems that I have is that the syntax is atrocious; it is worse than Perl!

Maybe I'll try again after I finish playing around with Ruby ;)

Re:Why isn't Haskell more popular?

[Junks Jerzey]

I'd guess because implementing recursive programs on a CPU isn't very efficient.

A naive seat-of-the-pants answer. I assume you're basing this on some old saw you've heard repeated somewhere>

Re:Why isn't Haskell more popular?

[Dusty]

A naive seat-of-the-pants answer. I assume you're basing this on some old saw you've heard repeated somewhere

Nope. It was my experience of implementing a heuristic tree search algorithm for permutation groups in Prolog, back in 1988. The recursive version would run out of stack. I ended up using an iterative solution, as AFAIR tail recursion reduced the stack usage but not enough to stop it from running out.

I'd be interested to see a way of implementing recursion (purely for my own entertainment) that doesn't use a stack.

Re:Why isn't Haskell more popular?

[moanads]

The reason why functional programming languages (not just Haskell) aren't popular is a bit of a Catch-22 situation. Most people try to learn a new language because it adds value to their resume or because something they're working on demands it. In the former case they always lean towards the so called mainstream languages - C/C++/C#/Java/... In the latter case, they probably don't care which language they're forced to learn and abandon it once their work is done. So a language doesn't get adopted unless it goes mainstream. But for a language like Haskell, it's difficult to go mainstream unless it gets adopted.

This does not in any way mean that an implementation of an idea in a functional language is necessarily slower than one in a say C/C++. See for e.g. Yaws . Phil Wadler has some information on functional language use in industry here. Galois Connections uses functional languages like Haskell/ML and there are several companies which use Erlang.

Re:Why isn't Haskell more popular?

[Rick BigNail]

Stackless Python?

Re:Why isn't Haskell more popular?

[Anonymous Coward]

Maybe the problem is not that Haskellers are really really smart, but that the majority of computer programmers are really really stupid.

Re:Why isn't Haskell more popular?

[Anonymous Coward]

Declarative programming is alien, this is why its not been adopted. Declarative languages undermine what the average joe knows about writing software. I personally think this is great, but it is often a very jarring experience. Thinking about how you normally write software.... only inside out, is understandably foreign. The word 'programming' its self is implicitly imperative. I think its a human bias to the concept of programming. People are impatient, they want to tell the machine to do things. Functional/Declarative programming is more like asking questions than giving orders.

Re:Why isn't Haskell more popular?

[Dusty]

Stackless Python?

Thanks for the link. Unfortunately from reading the article and according to Stackless Reincarnate:-

Stackless was a controversial modification to Python, separating its execution stack from the C execution stack, the C-stack.

Stackless Python still uses a stack to control its execution.

News at 11.

[ultrabot]

They've got a whole course online! FOR FREE!

Wow. That's indeed a good argument to scrap all those undocumented OSS languages we have been using for the past 10-15 years.

Graphical Programming and Learning

[stuffduff]

When I first started learning new languages I used to rewrite pong in them. It was very easy to 'see' if the code did what it should or didn't. That kind of feedback can really speed up the learning curve. I'm glad to see that the method hasn't been entirely lost.

Today, if you don't have enough flashy multimedia to attract the user to stay and look at what you have to say, you never even get your foot in the door. Chances are that someone who has taken the time to learn to both use the technology and apply it in a meaningful way probably has something to say.

With a generation of multimedia oriented programmers available I expect to see a much higher degree of interactivity in many different areas, from thing like mouse gestures to multi-dimensional navigation metaphores where we can simultaniously demonstrate our interests and our abilities so that we can arrive at the appropriate 'step' in whatever process we are trying to achieve.

Re:Graphical Programming and Learning

[gauchopuro]

Funny you should mention pong.

This book contains paddleball in something like 20 lines of code. The book's website provides the code in an archive, in the file Fal.lhs. It is mixed in with the rest of the code for the functional animation module; the version presented in the book itself shows just the paddleball portion. I found it very interesting that programs with this degree of complexity could be implemented with so little code.

Audience

[bobthemuse]

Since I was already comfortable with recursion when I started this book, it is hard for me to gauge how a reader who has never encountered recursion would find this book's explanation of the concept.

Who is the target audience for this book? I would assume programmers, of at least moderate experience. It's not like there are thousands of script/VB kiddies jumping over themselves to learn functional languages. Makes me wonder, how many semi-experienced programmers are there out there who aren't comfortable with using/understanding recursive functions?

Re:Audience

[Ben Escoto]

Who is the target audience for this book? I would assume programmers, of at least moderate experience.

Actually, the book is targeted mainly at novices (although experienced programmers who have never seen Haskell will also learn). In fact, the author even mentions high school students. This is from the preface (page xvi):

All the material in this textbook can be covered in one semester as an advanced undergraduate course. For lower-level courses, including possible use in high school, some mathematics may cause problems, but for bright students I suspect most of the material can still be covered.

So obviously an intimate knowledge of red-black trees is not required.

Here We Again

[myownkidney]

I haven't got the exact figures, but I reckon 99% of all code written out there must be written in Imperative (sometimes pseudo OO) languages. There must be SOME reason functional languages are not so popular.

Functional language are only good in theory. Sure, you can easily write programs in them, but they abstract over how the program is executed. And the programs are going to be executed in an imperative manner; machine code is imperative, remember?

Thus, there's a MASSIVE performance loss when a functional programming language is executed on any of the existing processors. Because the compilers can't think and optimise the code to best fit the imperative model. Where as the human being s can. That's why we should stick to imperative programming languages.

The day someone actually invents a function processor, we could start promoting these fringe langauges. Till then, let's keep Haskell as part of CS811

Thank you for listening. That's the end of my rant.

Re:Here We Again

[Chris_Jefferson]

There are I think two main reason procedural languages are more popular.

a) inertia. Till quite recently much programming was done in assembler, and procedural languages used to map much better to assembler code efficently. I would argue that as processors become more complex this is actually becoming increasing less true.

b) It's much easier to hack out some program in procedural language and then hack bits of it randomly until it kind of works. Programming in functional languages requires more thought.

Also, I feel it is important to say that as time goes by functional languages are catching up with speed with C (and even surpasing it in some places). This is because we are damn good at writing optimisers nowadays and functional languages frequently allow compilers to make a lot more assumptions.

For example in C, imagine we have the following function:

void foo(int& i) {
if(i==1) g();
if(i==2) h();
}

(The & would be more useful in the case where i was a more complex structure of course!)

In C, we have to assume that the call to g() may have changed the value of i. In a functional language this is not true.

Re:Here We Again

[Anonymous Coward]

So why aren't you promoting your site anymore?

For those who are interested, these are the 'headlines' on his stupid site:

Student Discovers Love Potion

AIT Scientists Discover New Planet

AIT Hosts the Olympics

CENSORED Article on Gender Rights Activism

No More Pirated Software in Thailand?

Re:Here We Again

[Tellarin]

You forget at least two things,

Functional languages are indeed used in production environments like Erlang from Ericsson for instance.

And there used to be Lisp machines.

So there are languages used in the "real" world and there "is/was" hardware available.

Re:Here We Again

[Waffle Iron]

I think that this choice of approaches to programming is similar to the choice in electrical engineering between solving problems in the time domain vs. frequency domain.

To me, functional programming is similar to the frequency domain. There are certain problems that are almost impossible to solve in the time domain that are trivial to solve in the frequency domain. However, the frequency domain is harder to understand, and the real universe actually operates in the time domain. Moreover, some problems that are trivial in the time domain blow up when analyzed in the frequency domain.

There few if any EEs who would advocate discarding all time domain calculations in favor of the alternative. That also applies to tools; few people would throw away their oscilliscopes just because they have a spectrum analyzer available.

That's what bothers me about "pure" languages of any form. You're intentionally throwing away some of the available tools to prove a point.

Sometimes a functional approach can provide an extremely powerful way to solve a problem with a tiny amount of code. However, sometimes another part of the same program would be better done in a more mundane fashion. The functional style's tendency to make you think about every problem "inside out" and to make you solve every problem in a "clever" way can get to be grating. I like to keep the option to use each style as needed, so I prefer languages that support features from a variety of programming styles.

Re:Here We Again

[Florian Weimer]

I haven't got the exact figures, but I reckon 99% of all code written out there must be written in Imperative (sometimes pseudo OO) languages.

There are lots of applications implemented in Excel spreadsheets. The stuff some people (who consider themselves non-programmers) do with Excel (or any other spreadsheet) is just amazing.

Excel is a bit limited (especially if you don't use VBA), but it's certainly some form of functional, purely applicative programming.

Re:Here We Again

[Ed Avis]

Thus, there's a MASSIVE performance loss when a functional programming language is executed on any of the existing processors.

There's also a massive performance loss with many imperative languages when compared to C. Impure functional languages like OCaml or Scheme can give programs that run about half as fast as C when using a decent compiler. This compares favourably to Java or Perl (among others).

The day someone actually invents a function processor, we could start promoting these fringe langauges.

There have been Lisp Machines - okay, Lisp isn't a purely functional language but it is high-level and some of the same arguments apply. However, your point of view is a bit odd. There should be a processor with features mapping directly to language constructs before you can start using that language? People have tried this in the 1980s and earlier, with processors optimized for running Modula-2 or similar, but on the whole it turned out to be better to make general-purpose CPUs and write compilers for them. It's not as if current CPUs are a particularly good match for C's abstractions; a language with built-in lightweight parallellism could work well with hyperthreading, for example. In any case, even if the language and CPU are horribly mismatched and everything runs a hundred times slower, that could easily be fast enough for the application. CPUs are getting cheaper but programmers, on the whole, are not.

Do you also discourage the use of Perl, or shell scripts, or Tcl, or Java? Or is it just functional languages that you don't like because they do not map to existing processors?

Re:Here We Again

[talleyrand]

I haven't got the exact figures, but I reckon 99% of all code written out there must be written in Imperative (sometimes pseudo OO) languages. There must be SOME reason functional languages are not so popular.

Hmmmmm

SELECT
*
FROM
PROGRAMMING_TYPES PT
WHERE
PT.name NOT IN ('functional', 'imperative')

>>> DECLARATIVE
(1 row(s) affected)

Yeah, I guess there's only two types of programming languages out there and clearly the previous code is only used in research/academic environments.

Re:Here We Again

[Ben Escoto]

Thus, there's a MASSIVE performance loss when a functional programming language is executed on any of the existing processors. Because the compilers can't think and optimise the code to best fit the imperative model. Where as the human being s can. That's why we should stick to imperative programming languages.

You are exaggerating the performance penalty. See for instance the old version of The Great Computer Language Shootout where Haskell is ranked faster than Java. Of course those benchmarks don't tell the whole story and should be taken with a grain of salt. In my experience though, Haskell is only about 4 times slower than C, compared to, for instance, Python, which is about 20 times slower (I am a big python fan, so this isn't a criticism of Python).

Just as plenty of people are willing to put up with Python's slowness in exchange for better debugging, faster development, dynamic typing, etc., I think plenty of people would benefit by moving from C to Haskell, which is purely functional, has a great type inferencing system, never seg faults, etc.

One final note is that Haskell programs can often be optimized in Haskell itself and approach C speeds. This is because Haskell is compiled and statically typed and can deal with unboxed elements and so forth. This is a big difference from Python and other dynamically typed languages where optimization sometimes must be done in C for best results.

Re:Here We Again

[Anonymous Coward]

Sorry, but here you are completely mistaken (and I am a bit amazed how this post got ranked so high). By using a reasonably advanced compiler for a functional language, and knowing how to write good functional code (highly nontrivial issue), one can typically get 50% - 150% of the performance of GNU GCC. Just look at the figures in the "Great Compiler Language Shootout".

Yes, it is easy to write slow code in functional languages. Especially for beginners who do not know or care about the fine print. But those one usually should not ask for their judgement, right?

When I saw LISP for the first time, I also could not imagine how something like that could ever be compiled to efficient machine code. By now, I do know, and I also know how to use the benefits of functional programming to implement freaky performance tricks virtually no imperative programmer would ever think about.

Re:Here We Again

[e aubin]

b) It's much easier to hack out some program in procedural language and then hack bits of it randomly until it kind of works. Programming in functional languages requires more thought.

This is nonsense. Functional programming almost always requires less thought because:

They are garbage collected

Programs tend to be much shorted

There are fewer assignments

Type systems catch a huge number of stupid mistakes

Functional programming is only feels harder because your are forced to correct your errors (instead of silently failing).

It might be hard (only at first) to wrap your head around higher-order functions, but all of you java programmers do the same thing (with ugly syntax) when you create inner classes.

For example in C, imagine we have the following function:

void foo(int& i) {
if(i==1) g();
if(i==2) h();
}

In C, we have to assume that the call to g() may have changed the value of i. In a functional language this is not true.

That is not true. If you were to transliterate this into caml, then the type of i would be a reference to foo, which g() could still change. Odds are though, you will very infrequently need to pass a reference.

Re:Here We Again

[Craig Davison]

For example in C, imagine we have the following function:

void foo(int& i) {
if(i==1) g();
if(i==2) h();
}

That's C++, not C. You cannot pass by reference in C. Plus we don't have to assume that the call to g() may have changed the value of i. The fact that you're passing it to foo() leads me to believe that it's not declared globally, outside of foo(), g() and h().

Did you mean to pass i to g()? Also, what's your point? I don't get it.

Re:Here We Again

[jovlinger]

Troll?

Anyways, ocaml is quite performant; when people compare its performace to that of C, people aren't really stretching the truth.

Compiling strict languages like scheme and ML to machine code is possible. Doing it well is harder, but several very good compilers exist.

Perhaps you meant _lazy_ functional languages? There are some bigger performance problems in that world, true; see a post above.

Lastly, is performance the only benchmark we use for selecting languages? Is it even the most important one? I surely hope not.

Re:Here We Again

[dubious9]

"Thus, there's a MASSIVE performance loss when a functional programming language is executed on any of the existing processors. Because the compilers can't think and optimise the code to best fit the imperative model. Where as the human being s can. That's why we should stick to imperative programming languages."

If this discussion was 25 years ago it would have been "OO languages? They are only good it theory. Sure you can easily write programs in them, but they abstract over how the program is executed. Besides, OO is slow!!"

But through the use of OO we have seen that programming at a higher level is better. Compilers get better all the time. Moore's Law has kept. There are few places in a program where you really need speed. There are notable exceptions (graphics, higher math, real time) but there is no reason to assume compiler theory won't advance to the level that we can write games and OS'es in Java.

The speed argument becomes much less of a factor when you can be more expressive with a language.

"Because the compilers can't think and optimise the code to best fit the imperative model. Where as the human being s can."

Err... if human being s (sic) can, then they can abstract and automate. Computers don't "think" at all, they are only good at what we've figured out at automating. If we can do it, there's no reason why computers can't either. In short if a programming paradigm works, then it makes sense to invest in it. Optimization will come later.

Re:Here We Again

[jovlinger]

Optimizing Haskell by choice unboxings and strictness annotations is against the whole point of the language (*). More imporatantly, it is close to impossible for anyone but the compiler-writer to get right.

Predicting how a lazy program will perform is hard, and figuring out where it hurts is even harder. This is in part due to the massive restructurings the compiler does. One small annotation may be sufficient for the compiler to infer a function's strictness. Knowing where to put the annontation, tho, is nigh guesswork. Then I refactor the function, and there goes my strictness again.

But, this _is_ preferable to writing in C, I'll agree with you there.

(*) However, I think the worker-wrapper transformation may be the most beautiful optimization I've ever seen.

Re:Here We Again

[HeghmoH]

I haven't got the exact figures, but I reckon 95% of all operating systems out there must be a version of Windows. There must be SOME reason alternative OSes are not so popular.

Alternative OSes are only good in theory. Sure, you can easily get a basic install up and running, but they depend too much on arcane instructions. The OS will ultimately be used by a human; humans are visual, remember?

Thus, there's a MASSIVE usability loss when an alternative OS is used by any normal person. Because Windows is best adapted to how humans think and work. That's why we should stick to Windows.

The day someone actually invents an alternative OS that a normal person can use, we could start promoting these fringe languages. Till then, let's keep Linux as part of CS811.

(My apologies, I don't mean to be insulting, just point out the flaws in the argument with some good old sarcasm.)

Re:Here We Again

[JohnsonJohnson]

I haven't got the exact figures, but I reckon 99% of all code written out there must be written in Imperative (sometimes pseudo OO) languages. There must be SOME reason functional languages are not so popular.

This was also true of procedural languages versus assembly prior to the mid '70's, true of COBOL versus other languages prior to the early '80's, true of C versus OO languages prior to the mid '90's...

It's not just for mutual funds that the past is a poor predictor of the future.

Functional language are only good in theory. Sure, you can easily write programs in them, but they abstract over how the program is executed. And the programs are going to be executed in an imperative manner; machine code is imperative, remember?

Although the register machine at the heart of most people's computer operates explicitly on state it does not mean it maps naturally to an imperative style of programming. For starters, the CPU is generally tightly constrained with respect to data types and the number of state values of which it can keep track, versus typical imperative (especially in imperative OO languages) code which assume infinite memory resources and types of arbitrary complexity. Secondly, for FPGA type computing, functional style programming is often a better fit.

Thus, there's a MASSIVE performance loss when a functional programming language is executed on any of the existing processors. Because the compilers can't think and optimise the code to best fit the imperative model. Where as the human being s can. That's why we should stick to imperative programming languages.

As is oft pointed out, there's a performance penalty to any newer/less widely deployed technology when adapted to older hardware. Over time that disappears (reiterate past as a poor predictor comment here). Would you hire a programmer who'd spend 99% of their time writing and optimising machine code, or a programmer who intelligently evaluates the available computing/development platforms (probably ending up with C++ or Java) and writing a relatively modern OO style program to run your new mission critical $7 billion production center? Note that the more details the programmer is responsible of keeping track of (down to making sure they remember the binary representations of the 2-300 instructions a modern processor can execute) the more likely they are to introduce bugs/errors.

The day someone actually invents a function processor, we could start promoting these fringe langauges. Till then, let's keep Haskell as part of CS811 Thank you for listening. That's the end of my rant.

Re:Here We Again

[NoOneInParticular]

Indeed, this is C++, but can you prove from this snippet that i does not refer to a global variable that g() might tinker with? This is what a compiler has to figure out, and the aliasing problem (which is what the point was about) does not render itself to easy analysis.

Re:Here We Again

[dasmegabyte]

Another thing to remember is that while processor speeds double fairly often, programmer speeds are a constant given a distinct set of tools. If picking a language that executes slower allows a programmer to write more software in a given period of time, then that language is superior choice for all but the most time sensitive applications.

In other words, I don't want to waste time fucking around with pointers when I could be working on something more pertinant to the task at hand. I don't care HOW my matrix gets sorted. I just care that it does. If I waste some cycles, so what? This computer performs 53 MILLION in between each monitor refresh. If writing in a more abstract language permits me to get twice as much done per day of programming (and in my experience, it's more like 5-10 times), I'm willing wait.

Besides, while computers may no be able to "think," code optimization is not reasoning as much as it is pattern based. In fact, modern refactoring tools are better optimizers than most programmers, because they know more of these patterns. And unlike human programmers, refactoring tools aren't tempted to glaze over modern day essentials like bounds or type checking, resulting in fewer bugs and better security.

Re:Here We Again

[Irfy]

I wonder - have you ever made a really, really massive project? Have you ever been thinking of the factors that are involved in one? Perhaps the _development speed_ is one factor? Perhaps functional code is cca 5 to 10 times smaller than an equivalent imperative code?

It's no wonder why errors are far more easily detected in functional programming languages.

I can only deduce that your particular programming experience always had to do with either 1. Projects with upto (say) 20.000 source lines 2. Projects with an extreme accent on run-time performance.

There is the other part of the world where development speed, reliability, verifiability (let's introduce the other half of the declarative programming paradigm - Prolog) is at a higher stake, than run-time performance.

You have been looking at "the code out there" very selectively.

Re:Here We Again

[gnalre]

Its easy to write fast computer programs.
while(1){} will run extremely fast. Not a lot of use however.

However what is difficult is to write large side effect free computer systems.

Functional languages will do that for you efficiently. Don't get hung up with speed it is not always that important. If it is write the bits that are in C and assembler, but do the bits that are not in a higher level language.

The day someone actually invents a function processor, we could start promoting these fringe langauges. Till then, let's keep Haskell as part of CS811

You mean like this...
www.erlang.se/euc/00/processor.ppt

However it is has been promised for a number of years and it never seems to quite get here...

Re:Here We Again

[sploxx]

Yes, and maybe this is a reason for looking at LISP and it's dialects?
See e.g. scheme.

It supports and *encourages* functional programming but also has "set!"-operators, is almost "syntax-free" and by using macros you can adapt scheme to whatever "programming paradigm" which will pop up in the next years.

Re:Here We Again

[ameoba]

Well, if you want to get into it, functional languages are a subset of declarative languages. If you take Prolog and write a program where you only define one variant of each predicate (or use lots of cuts as the first term of a predicate) you get semantics strikingly similar to something like SML (without the typing).

Re:Here We Again

[BiteMeFanboy]

Functional language are only good in theory. Sure, you can easily write programs in them, but they abstract over how the program is executed. And the programs are going to be executed in an imperative manner; machine code is imperative, remember? Bullshit. They're not used because the flood of people into CS for the money are too stupid to understand it. Functional langauges are a much better choice BECAUSE they abstrat a lot of the details away. Thus, there's a MASSIVE performance loss when a functional programming language is executed on any of the existing processors. Because the compilers can't think and optimise the code to best fit the imperative model. Where as the human being s can. That's why we should stick to imperative programming languages. Wrong again jerkoff. You might want to do some research before spouting off at the mouth. A compiler can be designed to optimize a functional language, and they have been The day someone actually invents a function processor, we could start promoting these fringe langauges. Till then, let's keep Haskell as part of CS811 What like the scheme processor? Or Lisp machines? It's already been done. I wish you children would stfu and learn something before voicing opinions on topics you aren't even remotely qualified to speak on.

Re:Here We Again

[CvD]

Thank you for this bright note in this Haskell fanatic infested thread. I'm surprised that this book review actually made it to the front page of Slashdot. Haskell is so obscure outside the academic, it surprises me that there are so many replies to this story.

Yes, I too have had Haskell forcibly thrust upon me as a requirement to graduate from my university. And not just 1 course, no, 3 are required! An introduction to functional programming would be okay. To give you an idea of their existence and how they work.

No, I don't like Haskell. And yet at the university seem to catch a few souls every year who for some incomprehensible reason take to liking it and keeping the Haskell infestation alive.

Bah... /rant

Re:Here We Again

[Anonymous Coward]

Another thing to remember is that while processor speeds double fairly often

My processor speed hasn't increased at all for a few years, but my programming speed has. Of course, I bought my processor and you can only rent programmers.

programmer speeds are a constant given a distinct set of tools.

That's not true. Programmer speed varies by unit, and does actually increase gradually over time, as does the population average. The rate is drastically less than the population average for processors though.

If picking a language that executes slower allows a programmer to write more software in a given period of time, then that language is superior choice for all but the most time sensitive applications.

Maybe. That depends how many times the program will be run. Programmer time is not infinitely more expensive than computer time.

Save $20,000 paying programmer time, or save 5,000 customers paying $500 each to upgrade their equipment to run your code?

I don't care HOW my matrix gets sorted.

I would care very much if someone decided that everything should use bubble sort. (MSVC's STL uses heapsort in rare cases, which tends to make cache worthless. Luckily it's rare cases.)

Learning about functional programming...

[rthille]

way back when in college, the most interesting thing was that the program couldn't do I/O during the execution, only as an exit value. That makes useful daily programs difficult to write in a 'purely functional' language. The review talks about monads being a solution, but I can't see that putting something on the screen our worse a printer is something that can be undone. Therefore, I/O must be a side-effect, so how can a real 'purely functional' language like haskel do I/O?

Re:Learning about functional programming...

[Ben Escoto]

way back when in college, the most interesting thing was that the program couldn't do I/O during the execution, only as an exit value. That makes useful daily programs difficult to write in a 'purely functional' language. The review talks about monads being a solution, but I can't see that putting something on the screen our worse a printer is something that can be undone. Therefore, I/O must be a side-effect, so how can a real 'purely functional' language like haskel do I/O?

Good question. There have been a variety of different alternatives proposed. For instance, some earlier functional languages took the entire program being a single function from the input (conceived of as a linked list) to the output (another linked list). However, since linked lists can be lazily generated in pure functional programming languages, this model does not imply that all the output must happen before all the input. The program would read the input and generate the output as it went along.

But the monad model is considered more flexible. Basically IO monads are just a way to use the type system to force a strict division between thinking (which is purely functional) and acting (which is imperative).

For instance, in C, it is possible that getchar() != getchar(). They can be compared because they are both ints. This is obviously non-functional (remember the definition of a function?). In Haskell, though, getChar isn't a function to ints, is a function to int monads (type IO Char). And you can't compare IO Chars, so getChar == getChar raises a type error. Voila, no functional violations. Similarly, any result which has a side effect or reads from the environment ends up with type IO.

Re:Learning about functional programming...

[jcupitt65]

Monads are like continuations, if you've ever programmed in that style with C.

Functions are passed their usual arguments, plus an extra parameter which is the thing that should be called after this function has done its work. This function parameter can have a lot of extra stuff inside it which represents the 'state' of the system.

It's rather like chopping your functional program into two parts: you have somthing a bit like an imperative programming language (but which is still pure functional) for the IO, and plain 'ol functional everywhere else.

Re:Learning about functional programming...

[Anonymous Coward]

The Key is that Monads impose a rigid sequencing. You're allowed side effects when you can prove that the results act in a certain functional way. (ie irrespective of evaluation order).

I once asked Hudak to come to philly from Yale and give a talk, and he did (at Drexel, a place I did a tour of duty at...) He was the best speaker we ever had, and a really cool guy. I spent the day walkin around penn/drexel with him.

Re:Learning about functional programming...

[Ed Avis]

The way you do I/O in Haskell is that the main program has type 'an IO action'. So for example,

main = putStrLn "hello"

If you wanted to write two strings, you could use use the >> operator which glues two IO actions together. Or if you wanted to read a string and then write it, you would use a function of type 'IO String' to read a string - the type means 'an action which does something and returns a string' - and then glue it with >>= onto a function of type 'String -> IO ()' meaning 'make an IO action from a string'. It's weird, but workable (and there is syntactic sugar to avoid typing all these operators). All the way along you are just making these IO actions and returning them. You can quite easily put a bunch of IO actions into a list, or otherwise manipulate them - they don't get performed unless they become part of the 'main' action.

Re:Learning about functional programming...

[Anonymous Coward]

(1) Create a "plan" what to output, what to output afterwards, what to input, how to process that input and create output depending on it.

(2) The "language" for such plans is a (not-so-special) certain data type, called IO. The basic operation on plans is concatenation: you have a plan to get A, and, provided you have A, a plan to do B with it. Then, you construct a plan that gets A and processes it to B.

(3) You construct these plans lazily. This is haskell, after all.

(4) Anything else you need is a magic location that allows you to execute plans. Not that we would not know something like this from C: its magic entry point where a plan that resides at that particular location is executed is called main().

Re:Learning about functional programming...

[Ben Escoto]

Monads are like continuations, if you've ever programmed in that style with C.

Functions are passed their usual arguments, plus an extra parameter which is the thing that should be called after this function has done its work. This function parameter can have a lot of extra stuff inside it which represents the 'state' of the system.

You are mistaken, or at least explaining things in a confusing way. Contiuation passing style and monads aren't related. In Haskell you can using monads without using continuations or vice-versa.

Monads exploit the type system, not an extra argument. For instance the Haskell function putStr has type String -> IO (). There is no need to pass any extra parameter; you just pass it a string, and it prints it, returning a null value. Another way to do IO is to have a special "world" object that functions pass between each other (is this what you're describing?) but there are obvious drawbacks to this. For instance, what if a function modified the world object, and then passed back both the new and old versions?? Then your program would have to duplicate the world...

Re:Learning about functional programming...

[scrytch]

> Therefore, I/O must be a side-effect, so how can a real 'purely functional' language like haskel do I/O?

I/O is not a "side" effect, it is a specified effect, not something that happens "along with" some other value being computed. It is however not deterministic, so it's contained within the I/O monad. Nondeterminism is one of the things monads are good for.

Basically any time you need something done in a sequence, whether it's executing "commands", reading input, producing output, or just producing a list, you use a monad (thankfully the syntax sugar for list monads makes the monad invisible).

Re:Learning about functional programming...

[jovlinger]

see earlier posts about monads.

appart from monads, IO can be done either by continuations: (read (\x->E) as anonymous function taking argument x, with body E)

(openfile "filename" (\openfileresult ->
... process filename contents ...
(writefile "filename" somevalue (\writeresult ->
if (resultOK writeresult) (print "done" (\printres ->
....

This works because each IO function takes an additional argument -- what to do next. That way, there is no way to 'rewind' the computation.

Another way is to write your program so that it emits a sequence of IO requests, and gets back a stream of IO responses.

An imperative program might look like so


void main(IORequest out, IOResponse in) {
out.add(new FileOpenRequest('foo'));
File fooF = ((FileResponse)in.next()).getFile(); ...


The problem with this approach is that we have to be careful not to attempt to read from the response stream until we have generated a request. Inherent in how this is done is that it is impossible to revoke a request once it is in the request stream; so we can't rewind here either.

In a functional language, we realise that the return value of a function is its output stream, and the argument the input stream:


main :: [IOResponse] -> [IORequest]


Which looks completely screwy. The requests are the result?.

Both continuations and iostreams are purely functional AND a PITA to use. Luckily, both can be expressed as monads.

Re:Learning about functional programming...

[jcupitt65]

Maybe it was confusing :-(

I was trying to explain it from an implementation point of view: monads are implemented with continuations, and many C programmers will have come across them.

Re:Learning about functional programming...

[Anonymous Coward]

Would you care enlightening us about the definition of a function you allude to ? Do you have any pointer on the subject ?
I fail to see why being able to compare a function results between them is non-functional.

Re:Learning about functional programming...

[Anonymous Coward]

Okay, nevermind, I found what you meant here : http://en.wikipedia.org/wiki/Functional_programmin g

Some free alternatives

[Ben Escoto]

If you want to learn Haskell here are my suggestions in order:

1. Why functional programming matters by John Hughes. An oldie but goodie, this can get you motivated to actually learn the language.
2. Hal Daume's Haskell tutorial is very complete, free and much better than the "Gentle Haskell Introduction" which isn't very gentle at all.
3. The Haskell Language definition is the official language description.
4. GHC's library reference, which you will use constantly on anything non-trivial.
5. The foreign language interface manual. Since Haskell has a small library you will probably need to call functions written in C a lot to get anything done. Luckily, Haskell's foreign function interface is quite nice.

Re:Some free alternatives

[kwoff]

> 3. The Haskell Language definition

Perhaps better would be a link to the page
where you can download it as PDF or PS:
http://haskell.org/definition/

New vs. Old

[moberry]

I think that there is a problem with newer programmers going into a language such as say, java, or C#. When i learned programming i learned C++ in ms-dos. We wrote our own string classes, used pointers, learned ADT's like, linked lists, and binary trees. Nowadays in java you write a program and use everyone elses stuff. there is a linked list class in Miscrosoft's .NET framework. Nothing is ever written from scratch anymore. IMHO you cant learn actual programming without getting into the nitty gritty your self.

Re:New vs. Old

[Abcd1234]

Meh. A decent computing science course will have an extensive class in data structures, usually implemented in C, in which you'll likely cover at least linked lists and trees, followed by a second, more extensive course on general algorithms, in which you'll cover heaps and other more advanced data structures. If it doesn't, it ain't worth enrolling in. *shrug*

Of course, after you've learned *how* a linked list is implemented, you should never have to roll your own. And if you do find yourself rolling your own, you should seriously question *why* before continuing, as there are many high quality, well tested implementations already floating around (for example, glib).

Re:New vs. Old

[ThosLives]

Ah, I would say that "writing a program" by putting together other people's building blocks is not programming but code assembly. I would actually say that most "programmers" out there really don't know how to program, and that's why we have lots of the issues present today. It does take a clarification on how literal you want to be with the verb "to program" because people who stack up components are programming in the strictest sense. However, I fear that few and far between are the folks who can code a full GUI in 32 K of RAM (GEOS for the Commodore64).

I would wager that most of the "true" programmers are those in imbedded systems and the like who actually have to generate the building blocks and frameworks of any language. The rest are something else - not to nock their contributions to the application world - but I think that some distinction ought to be made.

Re:New vs. Old

[pHDNgell]

Ah, I would say that "writing a program" by putting together other people's building blocks is not programming but code assembly. I would actually say that most "programmers" out there really don't know how to program, and that's why we have lots of the issues present today.

Um, no. Writing a program is always assembling building blocks unless you always start by writing an assembler for your target hardware.

The good programmers are the ones who assemble the correct building blocks the right way. The people who reinvent the linked list for every project are the ones who cause us the most problems (and yes, I've reinvented many linked lists in the past).

Once you break free from the mentality that you must always make your own malloc(), printf(), hashtables, trees, linked lists, etc... you can move on to higher level issues like the actual application you're working on.

Re:New vs. Old

[SmackCrackandPot]

If every generation is forced to start from scratch, where does progress come from? What of "standing on the shoulders of giants"? Because they might find something that everyone else has missed. You should consider algorithms to be like gold mining - most of the ground has already been well excavated, explored and mapped, but there are always areas that have still been unclaimed. Unless you know how CPU's operate, you don't know how to write efficient algorithms. You can't build complex systems out of basic components unless you know how each will interact with the others.

And more importantly, if the skills required to perform a task are reduced to "code assembly"; that type of work will more than likely be outsourced.

Re:New vs. Old

[Anonymous Coward]

Good post.

Re:New vs. Old

[dasmegabyte]

This is crap.

First off, what do you consider "real programming?" I always felt it was the ability to take an input, process it, and create an output. You don't need to understand ANYTHING about data structures to do that.

Or is it not "real programming" unless you avoid all of the convenient shortcuts which permit programmers to do things that are more complex than the addition and transformation of bytes?

You don't need to understand the cellular biology behind tree growth to be a carpenter. I'm sure it might help a little, but you can build some fairly impressive structures without knowing anything.

Similarly, when .NET's IList derived classes (there are dozens, each with its own specific purpose, from strong typing to execution speed to in memory size) have some twenty common functions that represent hundreds of lines of code you never have to optimize, debug or even think about, what does it matter? With .NET, I can write code to instantiate, fill, sort and output a hundred lists in the time it takes you to make and debug one linked list from scratch.

Which is why I choose not to waste my time.

Languages

[benjiboo]

Do people think it's a good thing for a C++/Java/.NET programmer to go back to the drawing board for a few months and learn stuff like functional programming? I thought about coming up with a syllabus for myself of C, Haskell, LISP and Perl (which just evades me....)

Re:Languages

[pHDNgell]

Do people think it's a good thing for a C++/Java/.NET programmer to go back to the drawing board for a few months and learn stuff like functional programming?

Absolutely. It's a tragedy to go through life as a programmer without knowing FP. The more you learn about programming in general, the better you will be a programming.

I thought about coming up with a syllabus for myself of C, Haskell, LISP and Perl

I always recommend against perl. Very few people understand perl (no matter what they tell you), and I've yet to see a significant perl program without several significant bugs because of lack of proper exception handling or ambiguity (stuff like if($var) where $var can be false on what would otherwise be considered valid input).

I'd definitely recommend python instead if you want to learn some scripting (maybe ruby if you like stuff that looks like perl, but has a more reasonable philosophy).

C, like any other assembler, is OK to learn, but shouldn't be used for much of anything except to write extentions in high level languages.

Haskell is good. OCaml is good. Scheme is a good lisp derivative that's small enough to learn pretty easily.

You might want to add smalltalk and/or objective C in there. Smalltalk is pure OO (the OO version of Haskell, if you will). Objective C is C with smalltalk-style OO. When combined with the NeXTSTEP frameworks, you can learn a lot of very useful patterns.

A big part of functional programming is programming without side effects. Learning to program without side effects can greatly help you create more stable applications.

Re:Languages

[primus_sucks]

You might want to check out Scala. It is a combination of OO and fuctional that compiles to Java byte code (and supposedly will support .Net compilation in a few weeks). It also lets you interact with existing Java/.Net code.

Re:Languages

[Anonymous Coward]

I generally agree with the previous poster (go back and learn new languages, avoid perl, C is good to know but not to use unless you're doing embedded programming).

However, I think he artificially group of Ruby and Perl/Python, and an artificial separation of Ruby and Smalltalk/Objective C.

To quote a Smalltalk and Ruby programmer I talked to: "They're the same language with different syntaxes".

Ruby use a fairly traditional syntax, with deep OO semantics - everything is an object and is fully handled as such[1]. Procedural and functional programming just "fall out" of the complete OO implementation.

Perl and Python, on the other hand, has "bolted on" OO, with at least Perl hurting a lot under this (for Python I don't know - I do not program Python yet, and find it hard to motivate myself to learn it given that those that know both that I've talked prefer Ruby as a language - though they also note that Python has a better interpreter, docs, and more libraries.)

Eivind.

[1] There are two exceptions I know about: The state for the particular operator .. is not handled as an object, and the actual code is not available at all from the language. Function and method objects are, though.

Re:Languages

[pHDNgell]

That's probably accurate. If it's true that Ruby and Smalltalk are the same language with different syntax, then that would be why I haven't given ruby a try. The syntax looks too much like perl.

It's Real

[Vagary]

mod_haskell

Re:It's Real

[Richard W.M. Jones]

It's also real (and a lot further developed than mod_haskell):

mod_caml

Rich.

Re:Learning *Functional* programming?

[ameoba]

I think these guys have you covered.

Counter-Rant

[Vagary]

OCaml, which is not purely functional but still closely related to Haskell, is nearly as fast as C. Haskell somewhat acts as a testbed for ideas in the ML language family, and future versions of OCaml are expected to include many features that were first implemented in Haskell. I'd also suggest that Haskell is a good introductory language for future OCaml programmers as it ensures they won't just try and use OCaml like a weird imperative language.

OTOH, it is theoretically possible to automatically multithread purely functional programs, especially if they're lazy like Haskell. So it could end up being a very important language on multi-processor and distributed systems.

Finally, Haskell has an excellent foreign function interface for when you need C-like performance and control.

Re:Counter-Rant

[koh]

Funny, that's exactly what teachers were saying about ADA in my time... ;)

Re:Counter-Rant

[Vagary]

In retrospect, don't most people admit that Ada was a really good language for its time? And you're right to be skeptical, but it's not impossible that I'm right. :)

Re:Counter-Rant

[koh]

You're right, ADA was probably one of the greatest languages of its time (and still is ;)

Constructs like "task A requires B" are quite powerful indeed... too bad the only platforms this language is used for are missiles ;)

Re:Learning *Functional* programming?

[happyfrogcow]

Above message is especially redundant, and not even funny. It's an exact duplication of a post from a previous functional programming thread on /.

Don't miss it!

[Anonymous Coward]

If you liked

"Learning Functional Programming through Multimedia"

be sure to check out our new title:

"Learning Esperanto through Yoga"

Re:Don't miss it!

[Anonymous Coward]

lol. good one. =)

It Works Like This:

[Vagary]

Short answer: IO is an exit value, just like you said.

Long answer:
Monads are a pattern for hiding a state that gets passed from a sequence of functions. For example, when you assign to a variable in an imperative language, the value of that variable in the implicit state is updated and all future phrases accessing that variable will get the new value. If you're using a Haskell state monad it works the same way, but you need to explicitly specify which phrases can be executed in the future (using sequencing operators much like C's semicolon). Effectively Haskell monads allow all imperative constructs except for backwards jumps (goto).

The Haskell IO Monad is a purely functional mechanism for ensuring that modifications of the RealWorld are done in the correct order. It is implemented to call system calls which have real side-effects, but wrapping IO in a monad ensures that you can still reason about the order the side-effects will occur in. Since Haskell is lazy, these side-effects won't actually be triggered until necessary, either because the program needs an input value or it exits.

(I can give examples if anyone wants, but the resources at haskell.org may be more helpful.)

Are Functional Libraries Different?

[Vagary]

I haven't really given it much thought, but I've heard claims that functional libraries are designed very differently from imperative libraries and therefore .NET's (which is, lets face it, designed for C#) will not fit perfectly with CLI functional languages. Of course a functional-style wrapper around the .NET libraries could be written, but then we might as well be using the meager native functional libraries we already have.

Do you have any feeling for how well F# or H# will get along with the .NET API?

Re:Are Functional Libraries Different?

[Godeke]

Playing with F#, the entire library is accessable. Obviously, in some ways using these libraries funnels those sections of the program into a more procedural mind set, but other sections work very well.

C# and F# interop has a link on how to call C# from F#. However, it is interesting that F# uses some of the OCaml library *in addition* to the .NET libraries, as obviously OCaml has functionality specifically for manipulating functional structures, which is still valuable for F# programmers.

Avalibility?

[MountainLogic]

Does Haskal or oCamal have supported production grade ports to Palm OS or other small/embedded platforms?

The How Obfuscates The Why

[Vagary]

In my program, the algorithms class was at the start of second year, so many students were still not comfortable with pointers. As a result, most people spent so much time struggling with the implementations that they didn't get a chance to sit back and appreciate the structures.

In Haskell, structures like linked lists and binary trees are implemented with a single line of code. Yes, you don't see the actual memory addresses being used, but these are also barriers to understanding.

I'd advocate algorithm classes completing an implementation of linked lists in C (if this wasn't done in the C introductory class), then moving to a higher-level language for everything else. Because after all, once you've implemented one data structure in C, it's not difficult to implement them all.

Some questions and comments

[Anonymous Coward]

I've never done functional programming. The most esoteric I've ever gotten is Scheme:). From what I understand of functional programming you tend to describe what you want to do and let the compiler set up the low-level stuff for you. Am I wrong here? I think many more people would be more inclined to try out functional programming with one of the functional languages that target something like Microsoft's IL. That way they can still use the class libraries. Maybe functional programming doesn't integrate so well with IL(maybe it needs some lower level IL constructs to really be expressive), but if someone wrote a VS.NET plugin it might lower the fear factor in learning something new. I hear there are functional languages that do target IL right now. Any comments?

Mallocing a 'large chunk'

[cheezit]

This statement, from the 'more about Hskell' link:

"Furthermore, malloc is fairly expensive, so programmers often malloc a single large chunk of store, and then allocate "by hand" out of this."

I've seen this type of statement elsewhere in defense of non-C languages. And yet I've very rarely seen this done in code that wasn't either in 1) an embedded system or 2) a device driver or kernel module.

In those cases where I have seen this in application code, it has been accompanied by lots of other newbie gaffes. I'd question the sanity of anyone who thinks that a user-level app will benefit from a hand-coded heap manager.

But perhaps there are exceptions...does anyone actually do this routinely?

Re:Mallocing a 'large chunk'

[jovlinger]

I wonder if not partially filled arrays fall into this category.

Bit of a stretch, tho, I agree.

Re:Mallocing a 'large chunk'

[Anonymous Coward]

Yes. Many memory managers try to minimize wasted space rather than optimizing for speed. In fact, IIRC some there was some controversy over a few SPEC95 benchmarks because some platforms got hammered for making this tradeoff.

If you're writing software for which speed is of the utmost importance, and you're willing to waste some extra memory, you can often gain a lot. This is particularly true if your allocator doesn't have to be thread-safe.

I actually think it makes programs easier to write. You no longer have to avoid dynamic memory allocation because it is slow, so you can write generally cleaner code outside the allocator.

Re:Mallocing a 'large chunk'

[cheezit]

Sure, where speed is critical I could see this. But most of the time the apps that I have seen that do this are newbies trying out their CS homework.

Given a choice I try to use the stack wherever possible (but not alloca(); I've been burned). This can increase the image size at runtime and effectively preallocates a bunch of space in a more structured way. But it's not a replacement for truly dynamic allocation.

Re:Mallocing a 'large chunk'

[cheezit]

Like a sparse array? If done right it should only need extra memory for an intermediate hash table. If someone wants a superfast array it might be truly sparse.

Re:Mallocing a 'large chunk'

[alienmole]

I think this practice goes beyond embedded systems, device drivers, and kernel modules. You'll find this sort of thing quite routinely in data structures (or classes, in the C++ case) implemented in libraries. I.e. some data structure, say a hash table, will heap allocate a big chunk, and use it up bit by bit - even when the structure itself could easily support incremental allocation. There are good reasons to do this sort of thing, having to do with allocation cost, heap fragmentation, and locality of reference. The latter can have performance effects on things like CPU the effectiveness of the CPU cache.

However, this is probably a lot less common in "end programmer" code, as it should be. It used to be a lot more common, I suspect, because machines were slower, had less memory, and the negative effects of relying blindly on heap allocation for everything were more evident. A lot of "sins" are covered today (or are no longer sins) by the speed of processors & memory.

Re:Mallocing a 'large chunk'

[igomaniac]

This is pretty standard practice in computer games, especially for consoles... On another note, I question the sanity of people who use C languages for something else than embedded systems, performance critical applications or kernel modules... (I worked in the games industry for 7 years)

Last year I found myself extending an automated theorem prover written in Haskell, and actually _enjoying_ it... Haskell is very good for solving complicated problems, most of the time you find that if you manage to write down what you're thinking it actually works right away (although writing it down can be pretty hard). Unfortunately, even with monads, I find it is a bad match for the kind of event model employed in most GUI's... Now if only it was a bit easier to link Haskell with programs written in other languages I could make the GUI in Visual Basic and the rest of the program in Haskell ;-)

Re:Mallocing a 'large chunk'

[Anonymous Coward]

I'm a formor video game programmer, both on consoles and PCs, now a graduate student working on my PhD. I've also done stints as a system admin and web developer using Perl/Java and whatever.

I can say that nearly every video game I've ever worked on did this, malloc is too slow, period. One of the first things you need to do when making a game is eliminate as much interaction with the operating system as you can, those calls are too expensive. Anyone who has taken a class in operating systems knows about the costs of context switching. I believe this is why microsoft originally came up with the idea of DirectX and its relatives. Direct as in you get direct access to the hardware. Do you want a framerate or not was the bottom-line question.

The only exceptions I've experienced in the video games I've worked on were those for the original playstation. Wherein the machine specs were so tight dynamic allocation wasn't used at all. Everything was statically allocated and the role of every byte of memory carefully mapped out. This all may sound strange to some programmers out there, but you wouldn't believe some of the gymnastics I've seen in good game code.

In my other realms of experience, I've not seen this phenomena however.

Eh?

[pjt33]

What's the link between Cambridge and Haskell?

Re:God-fearing Muslims tormented by American SLUTS

[Anonymous Coward]

Berkley...Distribution...Software...Model?
What the devil are these *BSD weenies up to?
I thought NetCraft said they were dead?
What is this BDSM thing all about? Is it cool, or is it whack?

Re:Sad news ... Stephen King dead at 56

[Anonymous Coward]

I love the smell of a classic troll in the afternoon...it smells like... /. ...

Never segfaults?

[frostfreek]

What good are you, if your program segfaul

segmentation violation
comment terminated

Going to say the same thing

[Rick and Roll]

Yeah, GTK/Gnome really does suck. I think someone should write a paper, "GTK/Gnome considered harmful for GUI building". I found a Tetris program written in Ada (a language which provides excellent software engineering facilities), and found that upon entering my name, pressing the Enter key did nothing. So I figured, I'll just go into the docs and figure out how to make it the default.

Thirty minutes of searching around for it and expirementing with it, with no success, and I put the project on hold. I couldn't believe how confusing it was! And in the sample code, it was broken.

I intentionally limit my time with GTK apps, because it encourages me to forget useful keyboard combinations. "Esc" doesn't close a dialog box.

Not to mention it's slow and bloated, and full of crashes and potential for buffer overruns, since it uses a C object system, with type-unsafe macros, rather than a real object system, where type-checking is done completely at compiler time.

You could use a binding to keep yourself from creating new bugs, but I don't recommend it. What we need is a new GUI toolkit for 'nix, made in a better suited programming language (such as Java or Ada).

Re:Going to say the same thing

[k_head]

Why not swing?

Re:Going to say the same thing

[Rick and Roll]

Not fast enough, in my experience, for power users. Java takes too long to start up. It also isn't very Unix-like, in that only files ending in .class can be executed.

Plus, I consider Java to be a real pain in the butt, Pre-1.5. I have a compilers class in Java now. I am having to do way too much casting.

Impressions of Haskell

[Woogiemonger]

Well, I haven't touched Haskell but I read the description provided in the link. The "size of code" example is silly. For implementing quick sort, good programmers would use componentized logic, a good deal of which has been written for you. As for the pointer safety, Java or managed C++ handles that. Haskell curiously reminds me of prolog though. As for performance, it is very much still important in my opinion. Code for the usual ecommerce form and non realtime messaging apps I would think can use Haskell, but multimedia networking, game programming, and any form of high-volume content processing apps has to choose the higher performance language. I'm guessing though that Haskell supports linking C++ code just fine.. someone want to confirm this so I don't have to read more? Thanks :)

Re:Impressions of Haskell

[Reducer2001]

Here's my impression of Haskell:

That's a lovely dress you're wearing today Mrs. Cleaver.

Haskell lets you do both

[tmoertel]

Waffle Iron wrote:

That's what bothers me about "pure" languages of any form. You're intentionally throwing away some of the available tools to prove a point.

Well, Haskell isn't throwing anything out. You can do both purely functional and imperative programming with Haskell. It's just that Haskell's designers went deep enough into the theory to come up with an elegant way to bring the functional and imperative worlds together (category theory and monads). So you need not give up the benefits of one to have the other.

Take a look at this one-page TCP port scanner that I wrote in Haskell. Imperative and functional styles mixed together, with neither sacrificing for the other.

To use your time- and frequency-domain metaphor, Haskell is the well-educated EE who can use both kinds of analysis -- and slide between the two with ease.

Re:Haskell lets you do both

[greenrd]

You can do both purely functional and imperative programming with Haskell.

Yes, you can. Which is why, surely, it is incorrect to describe Haskell as a language which doesn't have x=x+1. Surely, the truth is, it forces you to do x=x+1 in a different way, and dissuades you from doing it at all. But you can still use imperative style if you really need to.

The people who say that Haskell does not permit imperativeness are really lying.

One more tutorial (karma whoring)

[Lulu of the Lotus-Ea]

Lots of other comments, as well as the story, have pointed to a number of good tutorials and introductions. I'd like to recommend also the one I wrote for IBM developerWorks. I believe my tutorial is a bit better for real beginners to FP than are most of the others out there.

Anyway, you can find it at IBM dW(free registration required) or at my own Gnosis Software site.

Totally false

[Tom7]

I guess this is a troll, but I can't resist:

Functional language are only good in theory.

This is totally not true. I build real programs that do real stuff in SML every day.

Thus, there's a MASSIVE performance loss when a functional programming language is executed on any of the existing processors.

This is also completely false. Optimizing high-level languages is often easier, because there is more semantic information to exploit (types, higher-order code). My SML programs typically run about 20% slower than a C counterpart, while being much shorter, more frequently correct, and more secure.

Haskell, SQL and relational algebra

[bringert]

You might want to have a look at HaskellDB which is a Haskell library for writing statically checked queries using a relational algebra-like syntax. It lets you write things like:

r <- table time_reports
u <- table users
restrict (r!userid .==. u!uid)
project (last_name << u!last_name # activity << r!activity)

A challenge for Haskell hackers

[Paul Crowley]

Here's a simple C function which finds the inverse of a permutation, in linear time.

void invert_permutation(
int in[],
int out[],
int len
) {
int i;

for (i = 0; i < len; i++)
out[in[i]] = i;
}

Write the same function in Haskell, in linear time. Use whatever representation of a list seems natural for you.

I set this very simple problem to every pure functional programming enthusiast I meet, including several professors at a University known for that sort of thing. I've yet to hear a good answer...

Re:A challenge for Haskell hackers

[Anonymous Coward]

Trivial, even for a Haskell beginner like me. We'll use arrays, just as in the C example:

invert:: Array a b -> Array a b
invert ins = array (a,b) (zip (elems ins) [a..b])
where (a, b) = bounds ins

Builds a new array with the same dimensions (indices from a..b), initializes it with a list of tuples that gets created using "zip" which takes the elements of the input array as the indices of the output array. Note: the signature in the first line is optional.
Nice, isn't it?

Re:A challenge for Haskell hackers

[Anonymous Coward]

I think the following should work:

invertPermutation :: (Array Integer Integer) -> (Array Integer Integer)
invertPermutation ar =
let
swap (x,y) = (y,x)
in
array (bounds ar) (map swap $ assocs ar)

I'm not sure about the complexity of the function 'array' but I think that a good implementation could be linear.

Re:A challenge for Haskell hackers

[Anonymous Coward]

You're kidding, right? It depends, of course, on your representation of a permutation; let's take [(Int, Int)] as our permutation type. So the permutation on three elements that reverses it is [(1,3),(2,2),(3,1)].

invert :: [(Int,Int)] -> [(Int,Int)]
invert = map (\(a,b) -> (b,a))

Now, if you want to use [Int] as a representation, so that the example permutation is [3,2,1], then you need to first add the indices (linear time), reducing it to the previous problem, and then extract the corresponding list. Therein lies the rub.

It's not the imperative nature of the permutation algorithm that's magic; it's that C provides a primitive for (it seems) constant-time array access. Provide such a primitive in Haskell (see the Array class) and you have essentially the same linear-time algorithm. In fact, the Array section of the Haskell 98 report provides the following example:

-- Inverting an array that holds a permutation of its indices
invPerm :: (Ix a) => Array a a -> Array a a
invPerm a = array b [(a!i, i) | i <- range b]
where b = bounds a

Re:A challenge for Haskell hackers

[scrytch]

> Write the same function in Haskell, in linear time

Using unboxed types I could probably transliterate that code, but I'm kind of rusty in Haskell. I just find it more interesting that I could probably crash your process by passing -1 for len.

Re:A challenge for Haskell hackers

[scrytch]

s/-1/a sufficiently high value/ ... was thinking "unsigned" for whatever reason. The fact that you're working on raw memory here and generally don't have a choice but to was of course my point.

Re:A challenge for Haskell hackers

[Paul Crowley]

Interesting - have you timed it to make sure it's really linear time? Several solutions got proposed by experienced ML hackers last time I tried to do this, and I took the liberty of timing them; I found they were all quadratic time.

I don't have a Haskell implementation to hand, though, so I can't time it - let me know what you get. If you can do it to a million-element array almost immediately, it's linear time...

Re:A challenge for Haskell hackers

[Paul Crowley]

You can crash the code by passing a bogus "permutation", as well as various other nasties.

It would have been a fairer comparison in Python, which automatically bounds-checks arrays. I used C because it's more widely spoken.

Re:A challenge for Haskell hackers

[Paul Crowley]

The magic is in the imperative part - the code depends on being able to randomly access an array updating it as it goes. But it seems that Haskell provides a special piece of magic to work around this sort of problem: an array creator which will initialise the array from a sequence of (index, value) pairs in arbitrary order. If that's what's going on (as it appears) and it works in linear time, then the challenge is answered.

I'd be curious to know how long Haskell has had this feature - I first proposed this problem in around 1992.

Re:A challenge for Haskell hackers

[Anonymous Coward]

import Array

invPerm1 :: (Ix a) => Array a a -> Array a a
invPerm1 a = ixmap (bounds a) (\i -> a ! i) a

invPerm2 :: (Ix a) => Array a a -> Array a a
invPerm2 a = array b [(a!i, i) | i <- range b]
where b = bounds a

-- The second example is taken right out of The Haskell 98 Library Report under the Arrays section.

Book recommendations

[dsplat]

I thought about coming up with a syllabus for myself of C, Haskell, LISP and Perl (which just evades me....)

I'd like to strongly recommend some books. The first is Modern C++ Design by Andrei Alexandrescu. The second is On Lisp by Paul Graham. In conjunction with that, you will need an introductory text on Lisp if you don't already know it and a good book on C++ templates. While I don't know what the best Lisp text currently in print is, I'd be willing to give Graham's ANSI Common Lisp a try on the strength of his other book. And C++ Templates: A Complete Guide by Vandevoorde and Josuttis illuminates a lot of dark corners in templates and explains some new features.

In the end, the goal is to understand how many times Graham and Alexandrescu are talking about the same things using very different languages. C++ templates are in many important ways a compile-time, functional macro language on top of C++ that implement many of the features of Lisp macros. For what it's worth, Bruce Eckel has mentioned this generic programming link in the context of discussing Java generics.

Re:Here We Again -- Choices

[Lucas Membrane]

There are a few possiblities: Nemerle is functional version of C#. Felix is functional version of C/C++. Scala is functional version of Java with .Net version coming. Schlep translates scheme to readable C. Cyclone is a safer C with some functional features.

Can you honestly say..

[Peaker]

That you prefer this code to the C alternative, in terms of readability, maintainability, error-proneness, etc?

Sure, I don't like using C for general-purpose programming as much as the next HLL programmer, but FP languages are simply mind-boggling, and no - that's not a good thing.

Re:Can you honestly say..

[Anonymous Coward]

Perhaps a more readable version for someone coming from the C version would be like this:

invert ins len = array (1,len) [(to,from)|(from,to)<-assocs ins]

And yes, that looks to me to be a lot more readable, maintainable, and less error-prone than the C one.
But then again, I thought that about the original.

-Greg

Re:Can you honestly say..

[alienmole]

I don't think the OP's solution was the most transparent, but that's not Haskell's fault.

It's simply wrong to assume that because you see code you don't understand when you're looking at an advanced language that you don't know, that those languages "are simply mind-boggling, and no - that's not a good thing".

What those languages are, are different than what you're used to. There's a reason for that - what you're used to is largely an ad-hoc collection of crap that evolved before people understood what computers were really about. Now, we have good models for things like abstraction and control flow and structure in languages, but unfortunately, languages like C and Java and C# don't even begin to take advantage of these models.

Really, you shouldn't focus on learning FP languages. Focus instead on learning basic computing principles, as you'll find in a book like SICP. Once you understand basic computing principles, you'll understand why and how functional languages make sense, and why ultimately, the crappy languages we have today will evolve in that direction. You already see it happening, in fact, as various languages slowly absorb academic features that have been around for decades - it just happens very slowly. You can get a jump on the next 30 years of language evolution by learning something about the underlying principles, right now.

Haskell is just one possible expression of functional principles, and it's one that emphasizes purity and syntactic conciseness. That doesn't always result in the most friendly code. Neither of these constraints are fundamental to functional languages in general. You might find ML, or Scheme, or Erlang, or OCaml more to your taste. But if you ignore FP because you think it's mind-boggling, you're simply admitting that you're not serious about programming.

Re:Can you honestly say..

[Peaker]

You're assuming that because I saw a piece of Haskell as Mind-boggling - that I do not know advanced computing principles or am not serious about programming.

I am very serious about programming, and have accumulated a bit of knowledge and expertise along the way.

I do know and kinda like Scheme, and have tried approaching Haskell, ML and OCaml. These languages, however, always seemed to take more effort/LOC's and have far less practical code-bases available to them than Python, for example. They also have far steeper learning curves.

Python fits the way most human minds work, including those of experienced programmers, like myself or the more-experienced Eric Raymond.

Pure FP languages are more about purity than practical advantages and purity just doesn't justify the disadvantages, when you are not going to prove your program correct anyways.

As a sidenote, calling C "crap that evolved before people knew what computing was about" is at best inaccurate, as C was designed around the way computers operated as a portable assembly - with obvious knowledge of what computers are about.

Re:Can you honestly say..

[alienmole]

Python fits the way most human minds work, including those of experienced programmers, like myself or the more-experienced Eric Raymond.

Sorry, but this is nonsense. How much experience have you had with imperative languages, and how much with functional? Same goes for ESR, no matter how experienced he is. In fact, more experience can be a disadvantage here. What you're describing is simply what happens when a particular approach has become ingrained. People who are introduced to functional languages first find the imperative approach unnatural, not to mention buggy (unfettered variable mutation tends to seem abhorrent, for good reason).

I agree that the *pure* FP languages have practicality issues. But your original post broadened to cover FP in general, and that's what I'm taking issue with.

You talked about whether practical code bases are available. I'm not suggesting that everyone can switch to functional languages right now, or that they should. I'm saying that languages are evolving in directions that the functional and academic languages have long recognized as important, and that the functional languages have more coherent models for just about every feature that traditional languages offer. The FP languages are almost more important for learning about these models, than they are for actual programming right now.

Object-orientation in traditional languages is an unholy mess, for example, an example of the kind of ad-hoc crap I was talking about. You'll get more insight into what OO is attempting to achieve if you examine Haskell's typeclasses (or you can play with them in Scheme, via this post).

Re LOC, if you compare apples with apples, functional languages are usually better at LOC than traditional languages, and that's part of their point. They support higher levels of abstraction, which is one of the reasons people think they're mind-boggling. Many people can't deal with the abstraction, so they prefer to hand-code similar stuff over and over. So yeah, if you write naive code in a functional language and don't take advantage of its features, you'll have higher LOC - but that's once again the effect of someone with only imperative language experience using something they're unfamiliar with.

Another reason to learn about functional programming is because if you accept the features that the imperative languages give you as models, you're being screwed. For example, Stackless Python adds continuations to Python, and Perl 6 is supposed to get continuations, and there's a version of Javascript with continuations, but in all cases it's a kind of bizarro-world implementation of the feature, which can entirely put people off from important concepts. An example of this happening is with Python's lambda, which messed up the lexical scope issue and so makes people think lambda isn't particularly useful.

In fact, one person who claims that imperative languages fit human minds better is Guido van Rossum. He says that because he has a certain model already burnt into his brain. It's ironic that he said it about recursion, which is one of the things that actually makes all sorts of programming much easier and more manageable, once you understand how to use it. Anyway, if you want to be smarter than Guido van Rossum, you need to learn more about FP. Otherwise, you're doomed to be learning from people like him, and unfortunately, they're just confused.

Make no mistake: all of this "more natural for humans" stuff is just your brain rebelling against having to deprecate any of the investment you've already made in learning imperative languages, and having to invest effort in starting from scratch learning a different model. Don't kid yourself that you know anything true about these other languages, until you've actually put in the effort to learn them to the point where programming in them feels natural.

Re:Can you honestly say..

[Peaker]

An example of this happening is with Python's lambda, which messed up the lexical scope issue and so makes people think lambda isn't particularly useful.

Python lambdas are just syntatic-sugar around nested functions (defined just as normal functions). In fact, Guido regrets putting them in the language, as he thinks you should use a nested-def instead.

I think you are quite out-of-touch with current Python, because since Python 2.1, Python has had useful nested functions with lexical scoping. There is a slight ugliness issue about assigning into new variables in the containing scope, but they are slight. I use nested functions in my Python code _all the time_, they're one of the most useful features in Python.

It seems to me that you are attracted more to FP languages because of their coherency. That indeed is a huge plus, however I think you might be missing out on the reason of the "ad-hoc" feel most "imperative"* languages have.

Languages like Python, C and others (excluding C++), usually have a bit of historic baggage (That adds up in _every_ practical language), but mostly they feel ad-hoc, because they are attempting to solve an ad-hoc problem: Providing a useful platform to develop arbitrary programs that work on arbitrary machines.

A set of arbitrary demands usually results in an "ad-hoc" solution, though that is not really an obstacle to actual development in real-world projects (Excluding perhaps formal proofs).

I feel very comfortable writing Functional-style python (combinations of map/filters/lambdas, now more coherently put with list/generator comprehensions), and yet I still prefer to write some of my code in more imperative style.

Object-orientation in traditional languages is an unholy mess, for example, an example of the kind of ad-hoc crap I was talking about. You'll get more insight into what OO is attempting to achieve if you examine Haskell's typeclasses (or you can play with them in Scheme, via this post).

Nobody actually agrees these days on what OO actually means. The most common definition states support for:
A) Encapsulation
B) Inheritance
C) Polymorphism

Basically this is attempting to achieve better modularity and reusability of code, and in some cases (Smalltalk, Python, Ruby) it is very successful, so I don't exactly see what you mean.

The real-world test [amounts of useful working code created out there] also seems to indicate that Python (without commercial giants backing it) is beating the hell out of Lisp, Haskell, and soon Java as well. If FP languages are so much more powerful and save so much work, why are they failing this test?
When answering this, please keep in mind that Python was just recently in the same position of Haskell, or even worse, in terms of popularity and available code libraries.

Footnotes:
* Scheme is more like Python than it is like Haskell, so I really cannot see why you'd name Python imperative while naming Scheme a FP.

Re:Can you honestly say..

[alienmole]

Addressing your footnote first:

Scheme is more like Python than it is like Haskell, so I really cannot see why you'd name Python imperative while naming Scheme a FP.

That reveals a lot about your knowledge of FP. FP is not just having a grab bag of functions like map, filter, reduce, or list comprehensions, or anything like that. That's superficial surface stuff, but it's the underlying semantics that are important.

The first problem with Python & FP is simply that it's not an expression-based language. It's fundamentally imperative in the sense that programs consist of sequences of statements, which rely on mutable state to communicate. This alone prevents you from writing real functional programs in Python, and is also one of the major issues which makes programs harder to reason about, harder to debug, and buggier. (As an aside, this is one of the areas in which Python's lambda is broken - they are restricted in what can appear in them.)

Although Scheme allows this sequence-of-statements programming style, good Scheme code doesn't use it. Scheme is expression-based, and programs can be composed of nothing but referentially-transparent expressions. This alone makes Scheme functional, and is more or less the flip side of the issue which makes Python non-functional.

Anything you can do in languages like Haskell or ML can be implemented quite directly in Scheme, using macros. The reason this is possible is that all of these are based on lambda calculus, at their core. The same can't be claimed of Python.

The second problem with Python is that it doesn't handle recursion well, and its built-in data structures like lists are not recursive structures. Although Stackless Python does a better job of supporting recursion at a low level, it still doesn't fix the data structure issue. Recursive programs which process recursive data structures are a fundamental feature of functional languages, and Python just doesn't do that well.

So, when you say "I feel very comfortable writing Functional-style python, and yet I still prefer to write some of my code in more imperative style", you're talking about using some fairly superficial functional features embedded in a fundamentally imperative language. No offense, but I'm afraid you're an example of one of my pet peeves, which is that people are going around thinking this is "functional", and based on that, feeling assured that imperative makes more sense. Of course it does, in an imperative language! What's happening is that people are being discouraged from learning about important and powerful programming concepts and techniques, because they think they already have them. You've been conned.

What you call the real-world test reflects what people have been brought up on - a result of the evolution of computing to date. It's like the days before engineers knew how to build bridges that didn't shake themselves apart. Heck, I was brought up on it myself - all I learned at university were imperative languages. You can't change the training of millions of programmers overnight, or all the legacy code that's in use.

As I said, I don't even think people should or could all switch to functional languages right now, because those languages haven't evolved in terms of libraries and tools to support the applications that most people need to write. However, I do think that anyone who considers themselves a good programmer and doesn't want to stagnate, should make a real effort to learn more about functional programming - more than you can learn within an imperative language like Python. The knowledge you gain will translate back into your program designs, and you'll design and write better code as a result.

The real-world situation now can be compared to what it was 10 or 20 years ago. You could have said the same things you're saying about "real world" back then about features like automatic garbage collection, or object orientation - and people did say those things. They said they w

"memory pool" pattern

[Julian Morrison]

I've seen something like that, as a form of garbage-collection, when C is used in a stateless, quick-cycling system like HTTP. Malloc a big chunk of memory, perform operations wastefully within it (allocate with no attempt to free or reuse), then free the whole chunk at the end of the cycle (eg: after the HTTP response).

This program uses that pattern: http://www.annexia.org/freeware/rws/

There's a flaw there, IIRC

[Estanislao Mart�nez]

See for instance the old version of The Great Computer Language Shootout where Haskell is ranked faster than Java.

IIRC, the reason this was so is because, given the test design, Java incurred a very large penalty for each test, from starting up its environment. Once the shootout's implementor figured out a way to factor this out (use a Hello World benchmark to measure startup time), Java's CPU performance shot up very close to the top.

Haskell for .NET

[fatcat1111]

I sometimes suspect that .NET may be the only hope of getting functional programming adopted by the maininstream.

Haskell is available for .NET now, using Mondrian.

Or, you can can access the Framework's libraries with Hugs98 for .NET.

Conceptual leap

[Julian Morrison]

Okay, disclaimer, I barely know any functional programming, and that's in ocaml. But despite that, I think I've made a conceptual leap here that might help clarify what's going on in regard of all this "IO as a return value" stuff.

In C you write programs. C values are values. C functions return a value.

In Haskell, you write program generators. Haskell values are "the capability to, later, if necessary, generate a value" - in other words, a piece of code that can be called. A Haskell function application wraps its operands (which are code) in itself, and returns "the capability to, later, if necessary, compute the application of this function" - more code.

When your "main" in Haskell returns an "IO value", what it's actually returning is a generated program which will finally be called to actually do the IO.

Have I got this right? Functional gurus, please comment.

OK, a harder challenge :-)

[Paul Crowley]

Thanks for bringing this feature to my attention, by the way. I'd be interested to see if you can use it to solve the next challenge, which was actually the one that inspired this challenge and arose from a real problem in Prolog programming: fairly generating a random permutation, given a source of random integers of arbitrary size. I don't immediately see a way of doing it, but perhaps you do.

Here's source code, in Python this time:

def random_permutation(len):
res = range(len)
for i in range(1, len):
j = random_int(i + 1)
res[i], res[j] = res[j], res[i]
return res

Good Leap

[Vagary]

As far as I can tell, that is indeed a very insightful way of looking at it.

At the semantic level: In denotational semantics, a program is a function with side-effects. A Haskell program without side-effects (all the input comes in, then all the output goes out) defines a mathematical function.

At the implementation level: A Haskell program with IO is the specification of a sequence of system calls. A monad with branching and other constructs is an instance of a superclass of straight monads.

However, a C program isn't necessarily that different: it still needs to be called as a function by the kernel. Haskell simply has another layer of abstraction because functions (and therefore programs) are first-class entities. And, of course, it's much easier (although not automatic) to ensure that programs are full rather than partial functions in Haskell.