Cryptography Lessons
Tracy r reed   |  

Functional Programming

Lately, in addition to learning more about python I have been doing a lot of reading about functional programming (as opposed to imperative programming).

I have talked with some of you about this in recent
meetings. It used to be that hardware was too slow to support
functional programming or really any high level language. LISP was the
first functional and high level language to be used. LISP was conceived
of in 1956 and fully implemented and useful by 1962. The performance of
LISP on the hardware of the day seems to have given the whole class of
languages a bad name and doomed them to obscurity. Other than AI
research and some universities, almost everyone dumped LISP for C and
similar languages. But the benefits of this method of programming
combined with much faster hardware which renders the overhead of high
level languages irrelevant seems to be causing a comeback. I think it is
time to take another look at functional programming and many people seem
to be doing so. The amount of functional programming activity in the
FOSS world these days is pretty impressive. It is definitely a different
way of thinking about programming so it will take some getting used to.

Functional programming in general has appeal for a number of reasons.

The first is that it is primarily based upon the mathematical idea of a
function. As computers are inherently logical/mathematical devices I
find this appealing. Specifically it involves lambda calculus and the
idea that you can implement the equivalent of Turing complete
functionality using the composition of functions.

They are functions in the sense that they always produce the same and
only one output for a given input, just like the mathematical definition
of a function.

There are no side-affects which can make your programs non-deterministic
and hard to debug. You never say things like a=b. Instead you evaluate a
function which returns b whenever you would have otherwise used a. But
even this does not really explain it properly. You will have to do some
reading on your own to get it. The book "The Little Schemer" is a pretty
good introduction to the theory of functional programming. It is mind
bending and enlightening at the same time. Having finished that book I
am now slowly working my way through "Simply Scheme" after which I hope
to tackle "The Structure and Interpretation of Computer Programs". Once
done with all of that I should have a pretty solid grounding in
functional programming in Scheme and be able to take on other functional
programming languages.

These ideas together mean you get code that is much more likely to do
what you intended and only what you intended which makes it great for
mission-critical applications which require stability and high
availability. They also mean it is closer to being possible to
mathematically prove the correctness of your programs. You still can't
actually prove it for anything but the simplest of programs but it gets
us closer and I think that is a worthy goal.

With functional programming you describe the problem itself rather than
an implementation of the problem and the computer works the rest out for
you. I find this pretty amazing. And because of this programs written in
a functional language tend to be much shorter. A program written in an
imperative programming language tends to be 5-10 times the length. Less
code means less opportunities for bugs and debugging.

With cpu's getting faster and getting wider in terms of parallelism due
to multi-core designs functional programming is in a prime position to
take full advantage of the capabilites of the new cpu's. Parallelizing a
functional program is easy because the nesting of the functions clearly
delineates what depends on something else and which things can be run
safely in parallel.

I have been reading about Lisp, Scheme, Haskell, and Erlang. Note that
Lisp is not a "purely functional" language in that you can also do
imperative programming with it. But the rest are purely functional. Some
day I am going to have to pick one for serious learning. As I mentioned,
I have a few books on Scheme already so it is in the lead. But the
succinctness and mathematical foundations of Haskell are appealing. I
just recently began learning about Erlang. Erlang was written originally
created by Ericsson and they use it on their phone switches and other
devices that need high reliability. It seems to have the advantages of
Haskell plus it has very strong concurrency support (threads done in a
safe and sane way: no locks or shared memory, only message passing), has
an emphasis on highly reliable code, you can patch it on the fly without
stopping the program (nice for upgrading those switches that require 5
9's of uptime), can be used to do distributed programming in a
transparent way, and has built in support for a distributed database
called Mnesia. That is pretty much all I know about it so far, haven't
written any code yet. But I look forward to trying it out. We really do
have an embarrassment of riches when it comes to programming languages.

I never really appreciated the value of RSS until I got the Sage plugin
for Firefox. Now I get a very useful feed of info from a number of good
sites. One of these sites is: which
always has lots of very good discussion on functional programming and
language design. I found out about Erlang through this site. Check out which has direct download and
torrent links to "Erlang The Movie". They demonstrate some rather neat
features of the language. The video itself, made in 1990, reminds me of
an episode of Fawlty Towers or Are You Being Served? Watch it and I
think you will see why. :)

"Hello Joe. Hello Mike. Hello Mike. Hello Robert. Hello Joe, Hello Mike.

I am working on a wiki page with lots of links to functional programming
resources. I will post a link to it when I have it a little further
along. I will post some functional programming examples here eventually