Yesterday I was asked a question about functional programming from someone in my department. This person is in the real time systems group, and their programming language is Ada (although they are not really a programmer).
The question I was asked was about cache locality, but that question was just a red herring inspired by a complete misunderstanding about what functional programming was. The impression they had was that it was just Ada without procedures. So I tried to explain "in a nutshell" what functional programming was. It's not an easy task!
I didn't go on about things like purity and referential transparency - these concepts might mean something to an experienced software engineer (they can see how it would make nicer interfaces) or a mathematician (more like maths), but to someone who does timing analysis, it doesn't.
So I wanted to try and get across a few of the core concepts:
1) No assignment (technically no destructive assignment, but that is the only type they know). The example they wanted me to show them "in a functional style" was:
x := 1;
x := x + 1;
In a functional style there are a couple of ways to do this:
x = 1
y = x + 1
Of course, order is irrelevant
y = x + 1
x = 1
Neither really capture the idea they were looking for. However, in a purely functional style we don't write silly stuff, so thanks to the purity we can just write:
y = 2
The great thing is that we can know that the answer is 2, because beta reduction is valid.
So after (probably failing) to dismiss destructive assignment, I moved on:
2) No sequencing, no "one thing then the other". This was again quite hard to get across. I gave the example of quicksort, showing that sequence was not necessary.
I then challenged them to write quicksort in Ada, which is really quite hard to do. Obviously to do a quicksort only on Integer takes loads of lines before you even get to the sorting bit. Since I had been teaching generics earlier, this showed how superior Haskell is for generics.
I think I was quite a bit less successful at explaining this one. The only way you can show sequence is not necessary is by writing an OS, a compiler, a web server etc in Haskell - all of which have been done. Unfortunately I only had a small piece of paper so couldn't write any of those.
3) Then we got back to the question of timing analysis - if you spend all day doing timing analysis you start to believe that everything else is less important. I got asked if my PhD in "software engineering" was just writing programs. I took great pains to explain that programming language research is not writing an interface to a database in Java.
Anyway, if you want to spend all day doing timing analysis, Haskell is probably not the right language to pick :) So at this point I decided to screw with their mind:
I asked them to predict how long this would take:
sort "neil"
They guessed O(n log n), I said O(1). If you never need the result of sort, it never gets executed - take the example:
if null (sort "neil") then 1 else 0
The idea of lazy evaluation was starting to mess with their head, so they decided to try and rephrase the question. They are interested in the worst case time, so can you treat it as the time to fully evaluate all the components.
The answer is a definite no!
[1..]
The above expression takes infinite amount of time to evaluate
[1..] !! 3
Therefore under their interpretation, this takes an infinite amount of time, but it doesn't. It's much quicker than that.
I don't think they understand that many of the concepts about functional programming, or how to use it in practice, but I think they do now realise it is not just "another programming language" - its an entirely separate entity.
Subscribe to:
Post Comments (Atom)
16 comments:
Why don't you tell them what a monad is? This will be really cruel.
Haskell wasn't so strange for me since I had seen Prolog before and that had opened my eyes to the idea that you can write code that doesn't do anything, it just describes something. Letting go of imperative programming was the hard part. (The really perverse thing in Haskell is that the imperative programming--monads--seems to be the hardest part.)
Lazy evaluation has nothing to do with functional programming. You can get it in imperative languages as well.
Again, monads have nothing to do with functional programming.
I'm not sure lazy evaluation in an imperative language makes much sense. Imperative languages nearly all rely on side effects which wouldn't be guaranteed to happen with lazy evaluation.
Lazy evaluation is more difficult to master in imperative languages, but it is certainly doable.
A controlled and simple lazy evaluation strategy in the imperative context is delayed writing to the disk.
I don't think Monad's is fair on them, their brain would pop. Plus it's confusing to say there is no assignment, then show them something that looks a lot like assignment.
I wouldn't normally have brought up lazy evaluation, but since they were 100% focused on "worst case execution time", lazy evaluation is a nice spanner in the works.
No desctructive assignment? What are my IORefs then? No sequencing? What are my monads for then?
Functional programming as a concept does not rely on interacting with the world, and does not require IO or IORefs. If you start by teaching someone what Imperative Haskell (TM) looks like, then they'll never know the beauty of pure Haskell.
"I then challenged them to write quicksort in Ada, which is really quite hard to do."
Huh? I did it as an excercise. It's no harder than doing it in C if you understand Ada generics.
"The example they wanted me to show them "in a functional style" was:
x := 1;
x := x + 1;
You could have pointed out that this code is pointless unless you do something with x afterwards.
As for sequencing, Haskell does have the 'sequence' function...
Nice post, I guess. Could you consider doing one about describing Ada to a Haskell programmer? In particular I'm wondering about Ada as a possible replacement for C and C++, if I'm looking for something with Haskell-like type safety but able to operate with C-like machine resource constraints.
solrize: I don't think I'd recommend Ada to anyone who wasn't writing something to run on a resource constrained embedded chip. It's really quite a horrid language...
I wrote a fully generic QuickSort in about 100 lines; it would be MUCH shorter if a) it were not generic and b) if I gave no thought to picking pivots.
What is your basis for saying Ada is a horrid language? In my experience it is a far better language than C or C++ because it offers language tools that help prevent errors such as a strong type system.
Hi, in Ada as follows
function sort (xs : ArrayInt) return ArrayInt is
begin
if xs'length <= 1 then return xs;
else
declare
pivot : constant integer := xs(xs'length/2);
begin
return sort(filter(xs, pivot, greater)) &
filter(xs, pivot, equal) &
sort(filter(xs, pivot, less));
end;
end if;
end sort;
An Ada real-time programmer would not do it this way, though. Do you know, why?
It is always interesting again and again, how people are locked in their world.
Ada folks: learn a bit of functional programming!
Haskell folks: be open for other domains (realtime, embedded)!
Another version with a kind of "closure" and "named lambda-like" local functions.
function sort (xs : ArrayInt) return ArrayInt is
begin
if xs'length <= 1 then return xs;
else
declare -- my kind of "closure"
-- with three "named lambda-like" functions defined where needed
pivot : constant integer := xs(xs'length/2);
function greater (x:integer) return boolean is (pivotx);
begin
return sort(filter(xs, greater'access)) &
filter(xs, equal'access) &
sort(filter(xs, less'access));
end; -- Ende of declare block
end if;
end sort;
Oh, please note: the parameter xs of sort is immutable anyway by default. No need
to make it constant explicitely.
And: the generic version needs a bit more; can't just write "Ord" as in Haskell,
but have to specify that <, >, = must be available.
Genericity in Ada is usually statically resolved during compile time. Quite nice,
when flying in an airplane... How is it done in Haskell? Please help me with this,
I really would like to learn about.
Let's bring together the functional and the realtime world, in order to learn as
much as possible from those thinking in the other world!
Sorry, identation was lost in my comment. Thanks, if somebody could tell me, how to correct this with the restrictions of the HTML tags.
Post a Comment