Functionnal languages in the "real world"?

[GnuVince]

Are functionnal languages (Lisp, Scheme, ML, etc.) used within companies that produce software? Or is it all procedural and OO?

I really doubt that they are used, because functionnal languages require much more thinking. Also, one of the predilected (is it a real word in english?) form of repetition is recursion, but recursion can stack overflow and is often harder to represent (in one's head mainly) than a simple loop in a procedural language. No?

[sans-hubris]

I disagree that recursion takes more thought. That's only true if a person starts out using procedural languages and gets used to iterative thought.

Nonetheless, one of my professors says that a lot of compilers/interpreters were written in ML. I'm not sure how to go about verifying it, but I'll take his word for it.

[GnuVince]

Well sans (I hate calling you sans, what's your real name?), consider this O'Caml function:


let rec sq size =
if size = 0 then 0
else (size * size) + sq (size - 1)


If I rewrite it to use Big_int's (arbitrary length integers), when I input 1,000,000, I get a stack overflow error. Is there a way I could fix this? Using a simple while loop fixed the problem (but it isn't nearly as cute).

[PrBacterio]

Originally posted by GnuVince
Well sans (I hate calling you sans, what's your real name?), consider this O'Caml function:


let rec sq size =
if size = 0 then 0
else (size * size) + sq (size - 1)


If I rewrite it to use Big_int's (arbitrary length integers), when I input 1,000,000, I get a stack overflow error. Is there a way I could fix this? Using a simple while loop fixed the problem (but it isn't nearly as cute).

You have to make the function tail - recursive by passing it its state explicitly.

I think you'll find this version works better:
let tailsq n =
let rec sqiter accum n =
if n <= 0 then accum
else sqiter (accum + n * n) (n - 1)
in sqiter 0 n

This is then, in fact, equivalent to a simple loop, because tail-recursion is translated as a simple goto instruction.
Recursion is the more general construct: You can express iteration as well as (real) recursion with it.

[GnuVince]

Yup PrBecterio, your version works quite well! Thanks for the help. (By the way, would I be better off trying to make all my recursive functions tail-recursive?)

[PrBacterio]

GV: Yes it is always better to write a function in a tail-recursive fashion when possible. Note that this is NOT always possible; which is the actual distinction between iteration and recursion: Tail-recursion is just another notation, another "syntax" if you will, for iteration, whereas with "true" recursion some state has to be kept for each step, which is usually naturally organized into a stack. OCaml, as well as most other compilers for functional languages, optimize tail-recursion into a simple goto/jump instruction, making it equivalent to a loop. So tail recursion is then, in these languages, just the major and most flexible looping construct - and because it is, in fact, more flexible than any specific looping construct, most such languages don't even have any other looping constructs (see, Haskell, Clean). You can see this as well in OCaml where the two iterative looping constructs - the for and the while loop - are more of an afterthought, and, except for some very specialized cases, most of the time it is easier to use (tail-) recursion anyway. In OCaml, in most any case it is easier to use some local function for tail-recursion than a loop, except for the most simple case of looping over every element of an array with a for loop, because otherwise you will have to introduce some mutable references to simulate the notion of a "variable".

[edit]
Oh and as for your original post: Yes, sometimes some functional languages are, indeed, used in "the real world". Mainly Lisp, though (http://www.franz.com/success/customer_apps/animation_graphics/naughtydog.lhtml). Of course, there are lots and lots of different opinions as to why functional languages are used as rarely as they are (http://www.paulgraham.com/paulgraham/avg.html).

[Dru Lee Parsec]

Recursion is great if it creates code that is easier to read AND doesn't produce unreasonably slow code when it runs.

Example, doing an in-order walk of a binary search tree is easy to read when it's recursive. It can be written in a non-recursive way (and it would run quite a bit faster, or at least it does in C ) but it's not as easy for the programmer to understand.

Now, unfortunatly, the way recursion is taught in school is usually to find a value for N! (N factorial). A simple "for loop" is a much faster way to compute a factorial.

So don't just decide if you should use recursion based on speed. Also consider if it makes your code easier to understand.

[PrBacterio]

Originally posted by Dru Lee Parsec
Recursion is great if it creates code that is easier to read AND doesn't produce unreasonably slow code when it runs.

Example, doing an in-order walk of a binary search tree is easy to read when it's recursive. It can be written in a non-recursive way (and it would run quite a bit faster, or at least it does in C ) but it's not as easy for the programmer to understand.

Now, unfortunatly, the way recursion is taught in school is usually to find a value for N! (N factorial). A simple "for loop" is a much faster way to compute a factorial.

So don't just decide if you should use recursion based on speed. Also consider if it makes your code easier to understand.

While that is true for imperative/procedural languages, in most functional languages - that is, all those I know of except for Common Lisp - the compiler will optimize recursive functions to produce the same code as a simple loop where possible, and is guaranteed to do so if the function is tail-recursive (most Common Lisp compilers do this, too, but it is not guaranteed by the language spec, unlike it is with Scheme, ML/OCaml, Haskell and Clean), making a tail-recursive function just a different notation for loops. In fact, neither Haskell nor Clean even have looping constructs; they are completely built on tail-recursion. So is Scheme, but in Scheme there are built-in macros which provide some syntactic sugar to complete the circle; i.e. the DO looping construct in Scheme can be reduced to a simple tail-recursive let/lambda expression and is considered syntactic sugar (even though the R5RS does not prescribe how the DO syntax is to be implemented it does say it is only considered syntactic sugar). In most of those languages (again, except Common Lisp) it is considered good style to use tail-recursion instead of looping constructs, if any exist.

[jemfinch]

Originally posted by PrBacterio
GV: Yes it is always better to write a function in a tail-recursive fashion when possible.


Not necessarily -- in cases where you're sure you won't exceed the stack limit, using a function that's not tail recursive is often faster, since the tail recursive versions invariably require more arguments. You'll find this to be especially true in languages which compile to bytecode.


Note that this is NOT always possible


All functions can be written tail recursively, some just require more effort than others :) Any function that needs to do looping or iteration of any sort can always be written in CPS form and thus can be written tail recursively.

Jeremy

[PrBacterio]

Originally posted by jemfinch
All functions can be written tail recursively, some just require more effort than others :) Any function that needs to do looping or iteration of any sort can always be written in CPS form and thus can be written tail recursively.

Heh you're right of course. What I meant was, not all recursive functions can be written iteratively, i.e. without needing (stack) space: There are algorithms which need to accumulate state throughout their iterations. Continuation passing style just makes this state explicit, instead of keeping it implicitly on the stack.

[nobody]

Getting back to the original topic;

It isn't made by a company, but MLDonkey (written in ocaml , http://savannah.nongnu.org/projects/mldonkey/ ) is an application a lot of normal people use on their desktop systems.

Also, Viaweb (which later became Yahoo! stores, if I remember correctly) wrote their shopping/store software in lisp, and I found a nice article about that a while ago. I couldn't find the original, but I did find a copy at http://www.paulgraham.com/paulgraham/avg.html

[Ninja40]

In the comp.lang.functional newsgroup, this question is regularly asked.

As i've read, some companies may be using functional languages, but don't want others to know it. I see at least two reasons. for this :

1. functional languages are not trendy. People still believe that Lisp is a monster of the past, and if they've heard of them (a big if), they think that OCaml and Haskell are "toy" languages. If you try to sell a product, don't tell that it's written in Ocaml, Haskell or Lisp. The usual fear is slowness.
Trendy languages are Java (no matter the fact that it's slower than many functional languages), C# or C++. They are the languages that benefit from the largest communication campaign, and therefore, everything that is written in other languages is not serious (apart maybe from Ada and, of course, C).

Note that this misconception doesn't strike functional languages only. A language like Delphi suffers from the same misconceptions, although it is better than Visual Basic, much better than (and as fast as) Visual C++ (try the FruityLoops music sequencer/synthesizer or example, written in Delphi, almost entirely by one person only: http://www.fruityloops.com).

2. there are far less programmers knowing functional languages than C/C++/java/PHP/etc. They are harder to recruit. And since there are less jobs, learning such a language is not very useful for the career of a young software engineer. Functional Programmers might be less paid as well because of this.
One functional language which is used in large industrial projects is Ericsson's Erlang (http://www.erlang.org). I used to work at Nortel Networks on a very large project, and we were painfully writing C++ code, -without templates, because the compiler was a mess-, where Erlang would have been perfect (and certainly faster as well, given the architectural choices that were made) for this project, which is so late that it costs Nortel hundreds of millions of US$... And it seems that Nortel has used Erlang successfully on some of its core products, so I don't understand why they didn't use it for this project, apart from the fact that almost nobody knows Erlang in France.

3. Since most project chiefs don't know functional programming themselves, they don't want to risk embarking in a new project using this paradigm.

[sicarius]

Those are some very good points. Is there a lack of "enterprise" class libraries and utilities that adds to the adoption problem? Also, how well do functional languages interact with libraries written in procedural language?

To me, those seem like reasonable requirments for a company looking to switch paradigms.

[Ninja40]

Originally posted by sicarius
Those are some very good points. Is there a lack of "enterprise" class libraries and utilities that adds to the adoption problem? Also, how well do functional languages interact with libraries written in procedural language?

To me, those seem like reasonable requirments for a company looking to switch paradigms.

Yup, apart from slowness, this is also one reason for this fear.

Slowness is usually unjustified for most large projects, because they eventually get so clumsy that the resulting software is as slow or slower than would have been a better designed functional counterpart.
I guess this is more due to bad engineering than to the language itself. However, it is well-known lower-level languages allow for easier bad engineering practice than high-level ones.

Now, concerning the lack of libraries, this is another common fear. It is understandable for GUI based applications, but not for the heart of the application. Especially with large-scale industrial softwares (>50.000 lines of code), which often split the GUI from the core application (good practice). Usually, it is these kinds of softwares, mobilizing hundreds of man-years, that motivate the creation of a new language, like Erlang, in large companies.
Environments like Visual C++ tend to make it easy to mix the core application and its GUI, giving rise to unmaintainable bloatwares. I know, I'm working on such a big mess.

At least, working in one language like Lisp or O'caml for the core application and in another, like Delphi or VC++ for the GUI renders such a sloppy design impossible. And it allows more advanced functionalities.

Languages like O'Caml and Common Lisp come with large libraries, comparable to C++, so the lack of libraries only concerns GUIs at most.

[sicarius]

On the GUI front, I'm sure that a language like TCL would be able to help out. If the base of the application is fairly well written the speed of the GUI portion of the code really wouldn't matter as much.

[Ninja40]

There is binding for Tk in the standard O'Caml library.

BTW, the most widely used software written in a functional language is probably Emacs, which, I believe, is in a very large measure written in Emacs Lisp.