Functional Programming and Free Software
Posted 17 Dec 2000 at 22:54 UTC by jao
Being til now an "imperative programmer" (C, C++, Java, Perl and a little
bit of Python), I've turned my attention to the functional paradigm, and
was thinking of learning one of the well-known functional languages (FLs):
Lisp, eLisp or Scheme. But then, some questions spring to my mind: is it worth
the effort?, will functional languages suit me well when developing
Free Software?...
<p>
As far as I know, the only FL-based program which is widely used is Emacs.
But, despite the fact that it is an impressive piece of software and, as
such, a testament of the power of FP, it is hard to find any other popular FS
application exploiting this power.
</p><p>
FLs usage seems to be reduced to extension languages (as in the case
of Scheme/Guile), and academic circles. One would say that
"real world" programming is left to imperative languages: am I wrong?,
and, if not, why is this so? Does FP in any way hinder productivity?
</p><p>
As I said, I'm learning functional programming, and have found it
a refreshing and beatiful paradigm. But, my ultimate goal being
to contribute to the FS community, I was wondering if FP is worth the effort:
what do you think?
And, while I am on it, which FL do you think is better suited for
production code? One would say that Scheme (being GNU's favourite) is
a sure bet, but I have repeatedly read that Common Lisp is the right
choice for middle and large sized programs...</p>
There are a number of reasons why Lisp hasn't become popular. Some are
unjustified, some not.
The worst problem is probably that many people don't believe that Lisp
programs can be as efficient as programs written in C. Often this bias
is based on seeing Lisp interpreters such as in emacs, without realizing
that Lisp code can be compiled to machine code too. Benchmarks have
shown numeric applications written in Lisp to be even faster than in C,
and comparable in performance to FORTRAN (in C, there is the problem of
aliasing pointers, which makes some forms of optimization impossible).
Also, some people believe that Lisp is too high-level for some
applications, such as writing device drivers. The Lisp machines from the
80s show that it is possible to build a machine that runs nothing but
Lisp right down to the hardware.
But most people who dislike Lisp do it because of the syntax. Lisp
advocates will claim when asked that the prefix syntax as it is is a
good thing, because it is easy to parse. But many people, and I am one
of them, argue that when trading off ease of use to the programmer and
complexity in the compiler, it is better to choose complexity in the
compiler.
But development didn't stand still. In the beginning of the 90s Apple
started work on a language for the Apple Newton, in cooperation with a
company named Harlequin (vendor of the LispWorks compiler), and the
Carnegie Mellon University (where the CMU Lisp compiler originated). The
language, named Dylan, was based on Common Lisp, but recent developments
in compiler theory were taken into account, and the object system was
modified to make fast method dispatch possible. Dylan started out with a
Lisp-style syntax, but moved to a more programmer-friendly infix syntax,
which rather resembles Pascal.
Dylan never made it to the Newton, and the project was cancelled during
Apples meager years. But both the Harlequin and the CMU implementation
live on. The former is available from Functional Objects, the latter was
published by CMU under a BSD-style license, and is now being maintained
by the Gwydion Dylan hackers.
Gwydion Dylan d2c generates C code from Dylan, and is of course written
in Dylan.
I think Dylan could have a bright future, because it enables the
programmer to struggle with the problem, instead of the language.
I think there are a number of reasons - many of them good - why
functional languages aren't used in free software.
1) Much free software is system-level software.
As andreas points out, it may be unfair to say that FP are a poor choice
for system-level software. But the most compelling reasons writing a
system-level app in 'C' over any FP is that the Unix API was written
with C in mind.
2) Legacy Support.
Modern compiler researchers often do their work in SML or OCaml - they
are "the best tool for the job" when it comes to optimizing compilers.
So why isn't GCC written in an *ML language? GCC has been in
development for years. There would simply be too much work involved in
re-writing the best in an *ML language - it would be years before you
saw the benefit, and support for new features would grind to a halt.
3) No killer apps.
Unix is the "killer app" of C. If it wasn't for Unix, C might be an
obscure language. Likewise, MFC is a killer app for C++ in the Windows
world. Now, this is kind of a chiken-and-egg argument, but do you see
how this is really a chaotic system? If one or two programmers choice a
different language for some apps way back when, this would have a _huge_
impact on what languages people were using today.
3) Few volunteers, few users.
There is plenty of free software for functional languagse that just
didn't catch on. Why? Because there are fewer functional programmers
(not so much with LISP or Scheme, which are relatively popular, but
moreso with the *MLs), there are fewer volunteers in projects.
But perhaps more importantly, by using a functional language you are
limiting your target audience. You're pretty much guaranteed that your
target audience will have a C compiler on their system. What about a
LISP compiler? Scheme interpretter? More problems: many functional
languages were designed to be used interactively, not as stand-alone
programs. (Again, reducing the utility). While some have argued in
this forum that you should write software for yourself alone, we cannot
forget the psycology of the situation. As Albert Einstein said, "only a
life lived for others is worth living." If you have few or no users,
would you really continue toiling away for years? decades?
4) Too abtract
The workhorses of imperative programming are "if", "for" and "while".
Raise your hand if you know what those mean. The workhorses of
functional programming are "if", "map", "apply", "foldl" and "foldr".
Raise your hand if you know that _those_ mean. Aha. Just as I thought ;)
5) Availability of debugging tools.
Don't diss this. Sometimes it's better to pick an aweful language just
because it has better debugging tools. While interpretted or
interactively incrementally compiled interfaces are nice, they don't
always replace a single-step debugger or a stack trace (NB: some
compiled functional languages don't even have stacks; and in
lazy-functional language "print" diagnostics don't do what you think
they would!!!)
6) Speed
A previous poster said, on some numerical applications LISP can be
faster than C. In general, languages without pointers, or where
pointers are discouraged (Fortran, LISP, the *MLs) compilers can make
better optimizations and thus make faster code.
But the problem is you have to make a compiler with those optimizations
;) Not easy. While Allegro Common LISP might be a speed deamon, I
don't know if any free LISP compilers do as good.
So, I don't think the "speed" label is necessarily inaccurate - I think
that FP languages *were* slower for a long time. Now, with very good
GLP'ed compilers for the *ML's being widely available, I don't know if
this is as true anymore.
Scheme, E-Lisp and Common Lisp are not functional. They all have
mutating primitives. So, first, let's just toss those out of
the house of functional languages. Among the functional languages
the most known are Haskell and ML, with OCaml starting to gain on
popularity. The reason that there is so little free software using
those is the same reason there is so little non-free software
written in those: must programmers don't know them. So, to change
that, just learn a language, and start coding...
Why are so few applications on your system written in Perl or Python?
Well, probably the same reason -- programmer support.
Do you want a language that promotes the use of a functional style,
or one that requires it? Lisp has mutators (that's assignment, more or
less) but that doesn't mean you have to use them. Good Lisp style tends
to avoid them.
<PLUG> CMU Common Lisp supports the ANSI CL standard (modulo bugs), is
available for Linux, compiles to native code, and includes a foreign
function interface for calling into C. Third-party libraries (also
free) include web servers, database integration glue (with an
object-relational layer), XML parsers, X widget toolkits, and CORBA
stuff (under development). Downside: a deliverable application is about
20Mb currently, so it's not so great for small programs. See http://ww.telent.net/lisp/
for some starting points. And there are other CMUCL users (and
developers) here on Advogato ...
</PLUG>
moshez: SML and OCAML have mutators, too. Neither is
pure functional. But, generally, people call them functional languages
anyway; they encourage a functional programming style. That's why LISP
and Scheme are often placed in the same category.
Scheme, posted 19 Dec 2000 at 16:37 UTC by jschauma »
(Observer)
I just had the questionable pleasure of having to deal with Scheme in
one of my CS classes ("Theory of Programming Languages"). What I learned
(with respect to Scheme) boils down to this: "Scheme can be used to
write an interpreter for Scheme or a subset of Scheme".
I know,
this i certainly not the whole truth, but it's the jist of what I found
out about Scheme. I learned some other useful stuff, so that class was
not entirely wasted time. But be warned, I started dreaming
recursively after finishing the final project. ;-)
Some time ago I wrote cgiemail, free software
that sent e-mail from HTML forms according to a format specified in a
template file, e.g.
To: strangeman@chasm.big
Subject: questions three
What is your name? [yourname]
What is your quest? [quest]
What is your favourite colour? [colour]
The syntax was extremely simple and intuitive. However, as I added
features, the syntax got less simple. Inputs could be prefixed with
required- to throw an error if left blank. A dollar sign
denoted CGI environment variables. A percent sign was used for
formatted printing. I anticipated using more special characters as
features were added. It could have evolved into an ugly programming
language.
I was looking to clean up the syntax, and decided that a function
should be
spelled out rather than having its own special character. I wanted to
preserve the simple [inputname] syntax, and just have one special
character that indicated a function name rather than a variable name
would follow. I also wanted to have a means of combining functions.
So, perusing my keyboard for that one special character I happened on
the parens and remembered Scheme from a Computer Science course 10 years
earlier. That syntax turned out to be a perfect fit. Scheme's syntax
looks a lot like an imperative sentence in English, but with less
ambiguous grouping: (verb object1 object2 ...). And as a bonus, the
simple [inputname] syntax would also work, as a variable name all by
itself is a valid Scheme expression.
I now use Scheme almost daily in my day job, writing web/database
applications used by hundreds of coworkers. It's fun! I understand the
concerns about Scheme syntax if your application involves a lot of math,
but for the small amount of math in your typical web application, it's
fine.
Type systems!, posted 19 Dec 2000 at 20:10 UTC by brother »
(Journeyer)
When I got to talk about functional programmin, one of the ost important points is the type system
Hindley-Milner typing is one of the best things about ML. It really speeds debugging up. Rember "Well-typed programs doesn't go wrong"
I've heard about people developing in ML/Haskell or some other nice language and then rewriting it in C before showing it to the manegers. No-one has been fired for choosing C or C++.
BTW: I use map alot when I'm coding perl
Common Lisp supports pretty much any programming paradigm you want. The ANSI standard specifies a Functional (lambda),
Imperative (do, loop), and Object Oriented (defclass, defmethod, defgeneric, MOP) language, and you can get packages which add
Logic programming (as in Prolog) into the mix. That's one of the greatest features of CL, IMO: you can mix and match whatever
programming styles are right for the problem you're facing. Throw in the ability to do completely arbitrary syntax transformations
(defmacro) into the mix, and you see why I don't see much need for any other language.
I guess CL has seen much more use in commercial software because it's so powerful that you really need to become a good
programmer to make good use of it (if you weren't a good programmer before learning CL, you'll find that you're becoming a better one
while you learn it). It's not easy for someone to just jump into some project written in CL and add a small feature in (however, a
well-designed program might allow it to be done more easily than in any other language). There are a number of projects (75+) related to
CL or other languages in the Lisp family on sourceforge.net, just look at this page.
In my university they were very pro-functional. Perhaps half of the
courses were done in Standard ML. There were two problems with this.
First, CSCI100, the C/C++ course was brutal on those who didn't know
the language. One semester simply isn't enough time to master C++ and
most students suffered through it. The next 2 courses were generally
ones that built off of the C++ course and by the end of those most
students were pretty comfortable. Then they pull the rug out from
under you and hit you with Common Lisp, Prolog, and Standard ML. I'd
say 85%+ hated it, they suffered for so long to learn C++ that they
just didn't have it for another language. There was a bias created by
the way they were taught and this is a pretty high calibre (top 3)
school.
Second, I heard at least 2 profs go on the record and say that if
anything will matter in 30 years it will be functional programming
because of its mathematical basis. Object modeling will matter because
it matches our mental models, in theory, but as for implementation
functional programming is the only thing we have now that we have
really really strong reasons to believe will never go out of style.
(Assuming that you think that it has ever been in style) I can't
disagree with that, in fact I believe that and as someone who has done
compiler work I appriciate it even more. Most people on the other hand
don't always see software and programming as a mathematical science.
The ability to prove something or write a program that can prove
something just isn't a factor for most programmers, they want to do a
job and just get it done. This is another education issue.
Lastly, Standard ML is pretty volatile. They are changing the language
in fairly big ways pretty often. I've had to change code 3 times over
the last few years because new ML compilers wouldn't read it. I
believe OCAML is more stable, I believe it has GTK+ bindings and
compiles in to fast native code. I can't comment on Haskell or Erlang
and I won't comment on Scheme or Lisp but ML is still a moving target.
That makes it difficult to win a lot of people over. I think they are
moving in the right direction with the basis library and by adding
libraries and frameworks to the language but they are still changing
syntax and that doesn't give me the green light to start implementing a
huge program in it if I know I'm going to change everything in 9 months
because the syntax has changed, it's not a big problem so much as a
headache I just don't want to deal with.