Functional Programming and Free Software

Posted 17 Dec 2000 at 22:54 UTC by jao Share This

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>

Lisp and what we've learned from it., posted 17 Dec 2000 at 23:54 UTC by andreas » (Master)

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.

Functional Languages..., posted 18 Dec 2000 at 01:08 UTC by adubey » (Journeyer)

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.

Functional Languages, and Other Languages, posted 18 Dec 2000 at 12:35 UTC by moshez » (Master)

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.

Functional language vs functional style, posted 18 Dec 2000 at 13:47 UTC by dan » (Master)

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 for some starting points. And there are other CMUCL users (and developers) here on Advogato ... </PLUG>

"functional" or "pure functional", posted 18 Dec 2000 at 20:07 UTC by jaz » (Journeyer)

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. ;-)

lisp-like syntax perfect for web templates, posted 19 Dec 2000 at 18:47 UTC by brlewis » (Journeyer)

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

CL isn't just Functional, posted 30 Dec 2000 at 22:13 UTC by rjain » (Journeyer)

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, just look at this page.

Not many real functional programmers, posted 1 Jan 2001 at 19:13 UTC by Nelson » (Journeyer)

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.

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!

Share this page