What About Functional Languages?

sdavies asks: "Functional languages like Scheme and Haskell are great! (here is a PS viewer) They give programmers new tools for elegance and abstraction. Unfortunately, to the legions of procedural programmers writing in languages like C/C++(/C#), Java, and VB, functional languages are considered obscure and impractical. What is your experience with functional languages, and what do you think is preventing them from being adopted into the mainstream?"

Why Functional Matters

I've always thought about submitting one of these "why not functional?" or "why not ML?" ask slashdots... but I think I know the answer.

My favorite functional language is ML (standard). It isn't "purely functional" like haskell (though we often write purely functional programs); it includes imperative features like assignment and arrays and IO, which are usually useful in real programs.

I work on an ML compiler here at CMU called TILT [cornell.edu] (which I'd like to think is one of the most advanced research compilers around), so I am sort of biased. But I also know what I'm talking about...

(Incidentally, the FoxNet Web Server [cmu.edu] is written entirely in standard ML, including the network stack (with ethernet, down to the hardware device driver)!)

Anyway, back to the question. Why does functional programming matter?

Programming functionally is closer to thinking in terms of math. Lots of algorithms and data structures are expressed more beautifully in a functional style. It's almost impossible to write gross hacks if you're programming functionally (most quick hacks actually turn out looking quite beautiful). Programming functionally has some direct advantages in this vein, and I find that I write better code faster when I write functionally. (I'll admit to hating it for a semester! But once I got used to it, I don't want to go back...)

There are some awesome features of most functional languages, most notably: Parametric Polymorphism and Higher Order Functions. (more rarely, such gems as functors and higher-order continuations (aka callcc; think a typed and higher-order setjmp). These all deserve their own posts to explain their incredible benefits. You are missing out if you've never written a program using these features.

But mostly, functional programming is useful for its indirect benefits. Let me explain some of these:

- Concurrency. Writing concurrent programs in a functional language is so much more natural. It's easier to avoid certain kinds of race conditions too, since you don't update variables in a functional language. SML/NJ [bell-labs.com] has an awesome concurrencly package called CML [bell-labs.com] .

- A powerful static type system and type safety. It's difficult to design a language (and many smart people have tried) that's imperative, type safe, and powerful. Features of functional languages like garbage collection and non-updatable values make it easier to define a language with a powerful type system. (in case you're still stuck in the 60s, type safety guarantees that your program CANNOT crash at runtime. No more uninitialized pointers, using memory after it's freed, bad casts, or other plagues of C++ programming).

A powerful static type system gets you a lot:

- Debugging. It's easier to find mistakes in your program. When I program in ML, I get a list of all the type errors in my program when I compile. I can go back and fix these before I have to run my program on test cases, etc. Debugging is so much easier. It's hard to explain how incredibly useful this is compared to programming in C++. Everyone who's used ML can attest to this fact: once your programs typecheck, they Just Work.

- Your programs run faster. Java has a somewhat more mature type system than C++ (it guarantees safety, for instance), but most of this is dynamic. That means all your objects are tagged, and these tags are checked frequently to make sure you're not doing anything wrong! There's no way the compiler can optimize these out; mistakes in the definition of the language (array subtyping) make tags necessary for type-safety. In ML, we don't have to tag values or check them at runtime. Yet we guarantee our programs run safely because we verify all of the types at compile-time!

- Compiler Technology Advances. Most research in programming languages and compilers these days is on languages with interesting type systems. We're seeing fewer and fewer improvements to C compilers, and lots of improvements on "advanced" programming languages. The type system allows you to make more optimizations, because the compiler has more information available to it. Some concrete examples:

Aliasing - a big problem for C/C++/Java compilers. If you've ever looked at the machine code they produce, you've seen this effect. "Why is it fetching that address again??" ... because two pointers may have pointed to the same thing, and in order to preserve the semantics of the language, redundant work is done. When you're not doing updates (functional programming), the compiler doesn't have to worry about aliasing.

Function Calls: Practically every C/C++ compiler treats functions as a black box. Languages with stronger type systems are able to optimize around function calls because much more information (types) are available.

Our TILT compiler that I mentioned earlier does something rather new: Each compilation phase transforms not only the program but its type. We keep the type information around even when we are dealing with assembly language! This enables us to perform some unprecedented optimizations.

- Machine independence. Making a type system usually means hiding away the details of the machine, and this usually means that the execution of your program is completely predictable. (Compare to C/C++ "undefined" behavior!) ML programs are extremely portable.

- Modularity. I was able to understand and start working on the (100,000 line+) TILT compiler in a matter of days rather than weeks because of ML's strong modularity features. The most interesting of these are:

Signature Ascription - This allows you to define abstract data types by naming a type and some operations on it (and their types). This is similar to header files in C (much more refined), but thanks to the type system, you can guarantee that the user can ONLY use your abstract data type the way you intended. They cannot cast, subclass, or use any other tricks to get at your datatype. (Some OO folks have solutions for this too, but they are not as elegant). This is awesome, because it helps you figure out where bugs are. I can attest that this really works; my project this summer is to change the way a very important module works... and so far, I have only experienced one observable effect of changing the representation!

Functors - This is somewhat like C++'s template system (but more refined); allowing you to write programs which operate on modules. (Ie, you give me a module which implements sets, and I'll give you back a module which implementes maps). This is very useful, and since all the work is done at compile-time, incurs no runtime cost.

- Proof-carrying code. You haven't seen this yet, but you will. What if you could download a program off the internet and run it, knowing that it won't do anything wrong? What if it wasn't subject to sandboxing (and slowdown) like Java apps? What if you didn't need to trust the source (certificats/signing)? Proof-carrying code carries a proof of its type-safety (and other safety metrics) with it; your computer verifies the proof and then runs the bare code! You can read more about this here [cmu.edu] .

Now here are some answers to the question of why not functional?

- RIGHT NOW, functional languages are slower (estimate 2x) than languages like C. Against a "modern" language like Java they fare rather well. Compiler technology is advancing and will fix this! I'd also argue that the other benefits (developer productivity, code maintainability) far outweigh the slowdown.

- Functional is weird for a lot of people. It took me at least 6 months to figure out why it was good, and I consider myself a pretty good hacker. Most people are more comfortable with imperative languages (at first...), possibly because that's usually their introduction to programming.

- There are not many commercial applications for functional programming yet (outside of Ericcson), and some people just program for money.

I would like to see the hacker types of the world pick up some new, interesting languages. Most of these languages don't have powerful marketing engines like Sun or Microsoft behind them, but hacker types are (usually) smart enough to see past that stuff!

Bloody Larry Wall ...

You sinner ... you must have written too much perl ... REAL programmers (that is, those at MIT) love to ignore the fact that human languages are above all context-sensitive (as Perl is to some extent), as opposed to Lisp variants which have completely context-free grammars.

Arrogance, infighting, zealotry (sound familiar?)

Arrogance. There is an annoying elitism among functional programming proponents, implying that all current Perl and Python and C++ programmers are wrong. Similarly, Linux zealots refuse to believe that multi-billion dollar corporations are being run using Windows 98 and NT.

Fragmentation and infighting. Some FP proponents insist that functional laziness is the key. Others think that laziness is unpredictable and does more harm than good. Some FP proponents insist that static typing systems are The Only Way. Others are very productive with dynamic typing and ignore the first group. Some FP proponents thing that uniqueness types or monads are the correct way to introduce the concept of state into a purely functional framework. Others don't care as much about purity, preferring to have imperative features readily available. Similarly, Linux zealots fight about distributions, text editors, and window managers.

Ignorance of what the market wants. Many FP language developers would prefer to do research on new type systems, rather than create useful libraries. Many think that language choice is more important than tool choice, as if ML would somehow be better at GUI-driven applications than Delphi. Similarly, Linux zealots think that operating system choice is more important than application choice, and many would prefer to live in a backward 1970s terminal window world without trying to understand why many people don't want to.

I see you've been 'Harperized' too. (corrected)

(Professor Robert Harper is one of the creators of Standard ML, and a very neat guy. BTW, if you could feed me some info on the TILT project, I'd love to study the compiler.. TILT is where the Python LISP compiler was about 8 years ago.)

I like SML a LOT, but there's a langauge which a lot of people aren't talking about. It's LISP. LISP has a public-domain compiler, an orphan of the Carnegie Mellon University lisp project from about 8 years ago. (CMUCL) [cons.org]

The compiler (Python) is fast; it compiles down to raw machine code, and it's performance is comparable to C, and has been for the last 5 years. (~30% slower at things like matrix multiplication, bench it yourself) [cons.org], which isn't bad for a compiler that's had a fraction of the effort of EGCS. It can use non-descriptor arguments and structures. [cons.org] It will also use type inference where it can (Roughly, the monomorphic subset of the type system of SML.)

Now, the language Common Lisp is exremely nice. It has a variety of built-in things like lists, hash tables, structures, vectors, multidimensional arrays... It's got a lot of declarative things too. Loops, 'foreach', 'set'... Lisp programs can't crash because it does typechecks too. (Though if Python infers that they're unnecessary, it'll omit them.)

It was the first object-oriented langauge to be standardized. CLOS (Common Lisp Object System) is amazing. You can have dispatch based on multiple arguments unlike java/C++ which is only polymorphic based on the first argument. And you've got multiple inheritence. With the MOP, you can even write your OWN OO system on top of it.

Because the syntax is simple, it makes it easy to have programmed transformations of code 'macros'
A simple example is a 3-way if-then. (:less, :greater, :equal).
A slightly more complicated example is adding in c-style for-loops. (done with the 'loop' facility)

For a fairly complicated example, there's a package called 'SERIES' which adds in the equivalent of pipes to the language. You 'pipe' data between routines and it transforms the code into minimum-sized loops and other iteration constructs.

For example, if I have a list of triangles. My code looks like I first transform all of the triangles, then texture them, then transform them. again. This requires creating lots of superflouis triangles. SERIES will automagically turn this into a single loop on each triangle 'tranform -- texture -- transform'. Except that it'll handle multiple argument functions that return multiple results, and it'll handle conditionals in the functions. Not all loops can be merged, but it'll do what it can.

[stanford.edu]
This is much like the one example of aspect-oriented programming, which was a realtime handwriting recognition program. It needed to do edge detects, averaging, convolutions. To do each operation in turn would have been horrific in time and space. The loops could be merged manually, but obfuscated the core algorithms and made it difficult to modify. The overhead of doing this transformation manually was a 50x code increase. From 700 lines to 35000 lines!

They implemented a new mini-langauge (Adding 'primitive' things like pointwise, convolve, etc to the language.) and used macro's do that merging automatically made the core algorithm obvious and trivial to change. The result was the core algorithm required only 700 lines of code, and another 1000 lines of code to do the merging and fusing of loops.. 2000 lines of code to do what took 35000 lines of code to do manually!

If you come from LISP, Aspect oriented programming is stupidly obvious. (If you don't, you think, 'wow' look at the cool stuff that they invented, and think that they created it.)

As a much much more complicated example, CLOS itself was implemented through macro's. Can you imagine a language powerful enough that you could 'transparently' layer a high-performance and very flexible OO system on top, WITHOUT REWRITING the underlying layer? Aspect oriented programming will never get this good. :)

Yet another plus of this is that you can runtime-generate and compile code. Want to compile that encryption inner loop to make a custom version for this key? It's as easy as


(defun twofish-make-fun (key)
(compile nil `#'(lambda (block) (twofish-encrypt block ,key)))


This works because the function 'twofish-encrypt' will be declared maybe-inline. Thus it'll be compiled as normal, but the source code will also be saved. Normally, a function call to it will invoke the unspecialized version. But if we compile a call to it that has known arguments, the compiler will fully specialize and inline it, and create a specialized assembly. (This is how CLOS is implemented.)

There are some nice advantages to having a simple syntax. :)

For hackers, there's the advantage that you can download ``Common Lisp The Language'' or the ``Common Lisp Hyperspec'' for a full specification of the language. No spending a hundred bux on a manual. (I'd give links, but I use my personal version so I don't know where to find them on the net anymore.)

Common LISP still has the features of a functional language. It has first-order and higher-order functions or closures. Python has a strong type system and it makes fast code. Your claim that LISP runs slow is false. :) Like SML, it's interactive and incremental compilation. You can redefine functions without quitting. You can even redefine functions that are running in a different thread.

In fact, LISP was found to be almost 50% faster than C/C++ on average. There was a study done about a year ago where they compared C++ and Java. [nasa.gov] Unlike other study's between langauges, they had a dozen people implement the same program in C++ and Java and then compared the results. They found what you'd expect, Java was slow and sucked memory.

These guys decided to repeat the study, only comparing LISP and Java. [nasa.gov] Although the fastest implementation was in C++, they found that Lisp programs, as a group, were over 50% faster than the C++ programs as a group. Also, development time was a fraction that of C++ or Java, and the number of lines of code was half. Not only that, the variability in the number of lines of code and development times was signifigantly reduced.

(Tom, I'll be back at CMU in a month, if you want to talk about this, or let me get my greedy hands on the TILT compiler. Send mail to [e-mail] if interested.)

(Objective) Caml may be a solution

There are tons of good reasons which can explain the failure of functional languages. Timing, installed basis, syntax familiarity, performance, fragmentation, worst-is-better (timing, again), marketing, etc...

I don't think Scheme can't change that. It has been around for 25 years now, hasn't really taken off, and is more fragmented than ever. Besides, many people are still reluctant toward this lisp-type syntax. I don't see why Haskell could change that either: it's nice, but it has a very small installed basis, which is not growing very fast. It cannot be used for system programming and big projects, and it suffers serious competition on smaller projects from fast-growing procedural "elegant" high-level languages, especially Python. Eventually, I don't see why Common Lisp should succeed now, after years of disappointments and decline.

Here's the problem: try to imagine a functionnal language, whose compilers bring performance that are far superior than Java compilers', and approximately as good as C++ compilers'. This language should be highly portable, suitable for Java-types applets, and have an object-orientation design at least as good ad Java's and CLOS. Its syntax should be more attractive than Lisp's, it should be interpreted and convenient to use and debug via a command-line interpreter just the way Python or Lisp dialects are, and in the same time, as mentioned above, compilable into a very fast executable code. It should also be able to interoperate wich C modules (and maybe others). And, besides all these qualities, it should also be much more than that, and bring other unique advantages.

Such a language exists, it is called Objective Caml [inria.fr]. One thing only is missing, the most important one, the installed basis. So there is a need to create the ecosystem. Here's a suggestion:

One could think of a new type of desktop environment which would be based on Objective Caml. Emacs users know that Emacs is an incredibly powerful and convenient Lisp environment, which is unfortunately limited to textual tasks, due to the limitations of Emacs Lisp (at the beginning, Emacs Lisp was supposed to be used solely as a macro language for an editor, and it has gone much beyond that). Imagine an environment in the spirit of Emacs (highly integrated, fully extensible, customizable, reconfigurable and reinterpretable when you use it, etc...), but whose scope would not be limited to textual tasks, and which could actually serve as a full "multimedia-hype-buzzword-whatever" universal desktop. To put it another way, try to imagine an Emacs type environment which would cover all the functionnalities of a, say, MacOS X or Windows user environment. It this is doable, then it's in Objective Caml.

Now, I know, I have a big mouth, and I should show some code. Anyway, comments appreciated.

Re:Formal correctness proofs.

Functional languages seem to lend themselves to formal correctness proofs.

Not necessarily. I once spent three years building a proof-of-correctness system for a dialect of Pascal (see "Practical Program Verification" in ACM POPL '83). The big problem is capturing the exact semantics of the language, which is not too hard for Pascal, probably possible for Java, and hopeless for C++. We did this by working on the output of the first pass of the compiler, which was a tree of psuedocode operations annotated with declaration information. Once you get down to that level, most of the ambiguity is gone. (At that level, you have operations like "pop two 16-bit operands off the stack, perform a 16-bit twos-complement add, and push the result. That's unambiguous.) Most of the material the user had to write to help the proof system was in the form of additional source statements in the Pascal program. So this is more of a language front end issue than a fundamental problem.

Moore's ACL2 is well-matched to LISP because he and Bob Boyer have an elegant formal mathematical system based on a subset of LISP (see their book "A Computational Logic" [amazon.com]. It's a truly constructive mathematics, like the Peano axioms, but machine-processable. Numbers are defined recursively, as (ZERO), (ADD1 (ZERO)), (ADD1 (ADD1 (ZERO))), etc. About four hundred theorems machine-proven theorems later, basic mathematics has been established. Very heavy going, but if you're into this stuff, it's a must-read.

It would be interesting to look at program verification again today. We have enough MIPS now. My verification runs on a thousand lines of Pascal used to tie up a VAX for 45 minutes. Today that would take about two seconds. You could work on proofs interactively. We were too early in 1982.

A good Java verifier (not that stupid thing that checks types and stacks during class loading) is quite possible. I don't think it would get much use, though. It takes too much math background to use such tools. Only a tiny fraction of today's programmers have the theory background. It's just not user-friendly.

Re:Scheme seems dumb in the respect that

I see this more as an academic issue.

The thing that the academics have grasped that the mareting suits haven't is that sometimes less is more. Goto is powerful, and powerful is never bad in a marketing context but it can be very bad from a maintainability context.

On the other hand, the thing that practicing programmers understand that academics don't understand is that sometimes, less is less.

I think functional languages are cool, and people should learn them/about them in school. But there's a reason they haven't caught on for non-trivial real world applications.

And, by the way, I don't consider scheme a functional language. You can program functionally in it, and it may even tend to encourage a more functional style, but I don't think that makes it functional.

Some practical issues

As others have mentioned, there's some issues with industry support, popularity with programmers, etc. Considering FP in an open-source context, however-- where the tools are free and languages like Scheme are alive and kicking-- there are still technical issues that make for abnormally high activation energy.

(These points apply to some variants of Haskell and ML I investigated a while back. I don't remember specifics, but these were the salient observations that resulted):

For one, the compilers are incredibly complex beasts. This wouldn't be so bad, if they weren't so ambitious as to generate native binaries themselves. Myself, I'm leery of anything that generates native machine code, that doesn't use a GCC backend. Maintaining a native code generator is a lot of never-ending work (machine architectures evolve constantly) and IMHO, not using GCC for that is a lost cause, in the long term.

More significantly, if the compiler's native code generator is the only way to get a native binary, you're basically requiring users to go through a MAJOR hassle (installing a full-blown compiler) just to run your program non-interpreted, if at all.

(If you want to know what I mean, try building the CVSup program-- written in Modula3-- from scratch. I almost had to do this, on IRIX. Let me just say: was I ever *GLAD* I managed to find a precompiled binary)

That's why I'm partial to compilers that generate C code (like SmallEiffel). It makes things easier for users, while still allowing them to generate binaries fully optimized for their architectures. And it works perfectly in a source package. You put in Makefile rules to convert Haskell/ML/etc. to C, and then the usual C->O rules, and distribute both the FP sources and C sources. Users will need the FP setup if they want to hack program code, but at least they need nothing more than a C compiler to get it up and running.

On a related note, there's also the issue of run-time libraries. Requiring anything that isn't the C library, or that can't be statically linked (without making hugeass binaries) is a lost cause. Again, it's an activation-energy thing. If you can't just download a binary and run it, then you're asking your users to do too much.

So, the ideal alternate language system would have to have at least the following bullets:

• Native code generation through a GCC backend. That way, the compiler maintainers only have to track GCC, and not the three or four machine architectures they happen to have in their lab. Not to mention, I know my stuff will run on anything GCC runs on, which would be just about every computer architecture in the known universe <g>
  
• Compilation to C. Java bytecode output a plus. Natively generated code could run faster, as the FP compiler would be better suited to the language features, but the C code should come in a close second.
  
• No run-time library, or at most nothing too formidable. It *must* be statically-linkable.
  
• Execution speed on the order of C/C++ code (not a problem for many implementations)
  
• Non-ugly interface to C/C++ libraries.
  

Not many alternate language implementations have all those features. SmallEiffel was one, I recall. I think there was one for Haskell, though I never got around to checking it out...

(Disclaimer: I haven't actually gotten into FP yet. I like what I've heard of it, and I do intend to delve into it sometime. I just don't want my non-C code to be a PITA for users because of technical issues like this. If it gives them grief, it should be because they can't think functionally, not because they can't build the damn thing!)

Re:Make C and Java functional

The reason why every statement doesn't return a value is because it is very inefficient -- basically it means that any value must be allowed to be undefined. modern CPUs don't have any support for this (on integers and pointers, at least. floating point has NaN), which means the "undefined" value must be recorded sepearatly and every operation has to check for it. This is ok in an interpreted language like Perl where you already have a lot of bookkeeping to do, but killer in a compiled/low run-time support language like C/C++.

Undefined values also make it harder to pick up many potential errors at compile time, which is the halmark of C++ philosophy.

Re:Why Functional Matters

Everyone who's used ML can attest to this fact: once your programs typecheck, they Just Work.

This is a myth. I agree that it does prevent certain types of errors, but not others. For example, suppose you have a function that draws a rectangle: rect(x,y,width,height). You forget and pass the parameters like this instead(x,width,y,height). The type system won't catch the error, because all the values are integers. These kinds of errors are at least as common. I'll agree that catching some errors is better than none, but the ones that are caught come at the expense of a possibly elaborate type system; a type system whose complexity may not be worth the benefit.

Rant: Formal correctness proofs - a misnomer.

I maintain that a correctness proof of a program - in the ordinary meaning of the words - is not possible. Consider:

What behavior is "correct" depends on the job to be done. (For instance: A perfectly correct implementation of "grep" is utterly broken if what you wanted was an implementation of "finger" or "gcc".)

Assume you had a perfect formal correctness proving tool or methodology. You must specify what it means for the program to be correct, in a formal language accessable to the tool/methodology.

This is exactly the process of writing a program. Did you write that program correctly? Prove it!

This is NOT to say that what are called "formal correctness proofs", or "correctness-proving tools", are useless. Quite the contrary - they're extremely valuable. They're just misnamed.

What these tools do is automate the comparison of two distinct descriptions of a portion (possibly all) of a design's behavior.

This is very important, because the only effective ways known to find and eliminate the bugs in a design amount to expressing it twice, in distinct forms that use distinct modes of thinking, and compare the two.

In the classic "manual" (though often machine assisted) approach to software development, the two expressions are the canonical specification documentation (the "spec" or "bible") and the source code. The spec is optimized for human readability, while the source code is optimized for processing by compilation tools.

In a large project they will be written by different people. In a small project the differences in language tends to create enough of a different mindset in a single person that they tend toward non-overlapping bug sets. In a very small project the "spec" may be the program comments. A good programmer comments well, not just to make things clear to others later, or to keep them clear to himself later, but to deliberately create this second mindset, reducing the chance for undiscovered bugs.

The source code does NOT strictly fall out of the spec. Instead the two co-evolve as the project procedes. The debugging/QA/verification process detects "bugs" which are defined as differences between the spec (or its non-canonical derivitaves) and the executable derived from the source code. The bugs are fixed either in the source code or the spec. A spec bug may be an ambiguity, an internal inconsistency, an ommission (including deliberate ommissions to allow flexibility to implementors, later filled in with the choice made), an error deriving non-canonical documents (such as comments or user documentation) from the spec, a misfeature, missing feature, unnecessary/difficult feature, or an adequate design choice that is later replaced by something considerably better discovered during implementation. A source bug is any program behavior that doesn't match the spec in a way that doesn't expose a spec bug.

What the so-called formal correctness proof tools can do is automate various aspects of the comparison. Once properly configured they can do, with machine-level reliability and speed, many of the same things that software QA people do. (For instance: Identify "edge" and "corner cases", determine that the behivor is right at and near the edge/corner, and generate inductive proofs that the behavior will be correct throughout the parameter ranges.) And once the tools themselves are debugged, they can do more of it, with less chance of error, than can be done by human effort. This also allows them to perform classes of testing that would be impractical without them, because of the manpower and time costs, because the complexity of the test would lead to errors and thus to missed bugs and bogus bug reports, or because they perform a class of test that is just not a good fit for a human mind.

Finally, formal tools provide additional specification languages, distinct from the implementation language, leading both to clarity of thought and a distinct mindset in the creation of the second expression of the program's behavior, and thus to less overlap of the bug set in the two expressions.

SQL - widely used functional languag

Well, SQL is a widely used functional language (4GL, a fourth generation language). Most people have a hard time to grasp the use of a non-procedural language: just think about it how long it took to get object-orientated languages to be applied widely. And even now, most languages that you find in programs are still 3GL. And even if you will see a program advertised as written in C++: most of the time this is written in C, but compiled with a C++ compiler. Which hardly counts as object-orientated. We are so used to program in 3GL that it will take us a long time to make full use of other concepts. This is even true for SQL: most people tend to program cursors where a shift to 4GL would be a lot better. It will just take time...

Then you have read bad Perl

Or else you never learned the language.

The "funny symbols" define a miniature grammar. Learn that grammar and it gives you guidelines about how to think about hashes etc. (Guidelines such as what you should name them.) Next use strict to stop pointing your gun footwards. Warnings exist for a reason. Turn them on as well. Finally avoid default variables except where they are necessary.

Now follow basic sane programming guidelines and Perl is perfectly readable.

It gets a lot better when you start using it like it was meant to be used. For instance the language is a list-oriented language for a reason. There are a lot of constructs that are syntactic sugar. Use them wisely. Note that map() and grep() give you all of the power of a pipeline without the problems of parsing and reparsing text, use them.

Now learn perldoc, use package namespaces, use Exporter, start taking advantage of the flexibility to make the style suit you...

Perl gives you rope. Yes. But don't judge the limits of the language by people who commit maintainability suicide...

Cheers,
Ben

Type safety.

I have to take a position distinct from both of those above.

[] once your programs typecheck, they Just Work

This is a myth.

I agree with the second poster on this point. But...

[the errors] that are caught come at the expense of a possibly elaborate type system; a type system whose complexity may not be worth the benefit.

Strong type checking in imperitive languages (particularly OO langues such as C++, but to a lesser extent non-OO languages such as ANSI C) is often criticized as being too restrictive and too complex. But in my direct experience, complaints that type-checking was too restrictive or onerous were mostly made by software "cowboys", whose code tended to be horribly bug-ridden. (I trust the second poster doesn't fall into that category.)

What strong type checking does is provide toolset support for catching design and implementation errors characterized by mismatched interfaces. When combined with a good OOP-style type declaration system you can express your intent clearly to the compiler - and to yourself and the other members of the project. The key to making it your friend is to understand it and use it in that way: Take a few moments to express the intended uses of your variables via types.

Mismatched operands are a symptom of lack of clarity of thought about what is going on at the interface. That lack of clarity leads to much more subtle bugs than just exchanging operands - bugs you can hunt for for days if they're not pointed out, but which jump out at you as soon as a compiler complains.

A good type system, properly used, doesn't normally get in your way. And in those rare cases where it does some languages (such as C++) give you a mechanism (such as cast to void or pointer-to-void, recast to alternative type) to explicitly override it, while expressing your intent to do so.

While my experience is primarily with imperitive languages, I suspect the same is true of functional languages - providing the type safety doesn't get in the way of code reuse (as it did to a small extent in C++ before templates, though this could be easily worked around with macros).

Re:Why Functional Matters

Yes, but that's bad design. You could have different types for co-ordinates, and for lengths. My experience with Haskell and ML has overwhelmingly led me to believe that strict type systems are a good thing.

Yes, but while types are a good thing, there's a limit. No one wants to take this to the extreme, and have a type for odd integers, a type for the number of students in a class (as opposed to the number of books in a library), and so on.

Oh, wow. What you say might sound so sensible, but, I am afraid, is so very wrong. My point is that once you really do embrace typeful programming (in the sense of Luca Cardelli, or beyond...), then all of these kinds of types might make perfect sense.

So, for starters, why not have a type that represents all and only the Odd Integers? One can think of plenty of mathematical situations where functions are defined only (or alternatively) for odd numbers rather than even numbers. In a type-impoverished system, you might have to litter your program with checks like (in pseudocode) "if ((x % 2) == 0) --we're doomed!". In a typeful environment, when you construct X as an odd integer, and use only operations defined for odd integers, then X *stays* odd, dagnab it. And that can be a huge win. Or let me put it this way: if you were programming on an architecture where valid addresses are only even integers (Motorola 68000 comes to mind?), then specialized types guaranteed to be even or odd could save you from doing something naughty.

As for distinguishing the types for numbers of students vs. number of books, again, why not make the distinction if it is important for your problem? I mean, if values of those two types occur in one program, then having them around could make it impossible for you to compute something like "number of students read by each book" when you obviously really meant to do something else.

After a while, being pedantic ceases to pay off. Actually, it ceases to pay off rather quickly, I think.

I'm not as sure as you are. I've seen too much buggy C code where there could have been a type error (but there wasn't) and too much confusion when everything's a string (so convenient until it all goes wrong) to think of anal retentive type use as merely pedantic.

I just didn't get it.

I took a course in Scheme and did alright - coding small things to do simple stuff is not that bad. Due to my personal limitations though, I just couldn't see how one could develop big, useful applications with them. I'm not saying that it couldn't be done but that years of procedural programming seems to have hardened my brain. For whatever reason, I just had trouble wrapping my head around it.

I've heard that functional languages are easier to learn for someone who has never programmed before. I think, however, that for people who have written a lot of procedural code, it's very difficult to get used to. Perhaps that's why: not enough people START with functional languages and, once you know procedural (or OOP), there's very little reason to switch since you can do most everything you need to. I guess you just choose your poison: Turing or Church.....

Correct

This lenghty post is all wrong.

I concur. My computability theory knowledge is mostly swapped to disk right now, but I know that a pure functional language can easily be Turing complete. There's a reason why the term "recursive function" is synonymous with "Turing-computable function".

Formal correctness proofs.

Functional languages seem to lend themselves to formal correctness proofs. I don't mean to imply that it is not possible with other languages, only that it is (IMO) somewhat "natural" for functional languages.

For instance, check out ACL2 [utexas.edu]. This is a LISP-derived system that can both execute code and do semi-automated correctness proofs of same. It works by having you propose correctness theorems about the code, and (cool part!) expressing those theorems in the same language as the code itself.

<trivia>ACL2 was used to validate parts of AMD's K5 and K6 FP operations after Intel's embarassing faux pas with the Pentium FP unit. I've heard that it was used even more extensively on the Athlon. (Strictly speaking, what ACL2 validated was a model of these processors, since the processors themselves are not actually written in ACL2's input languages.)</trivia>

--

The masses can't handle FP

Given that most of the certified "professional" programmers that I have bumped into during my last few years of consulting weren't quite up to the, er, daunting task of writing sensible code in VB -- or code that just plain worked, for that matter -- I doubt that they would understand, let alone appreciate, wonders like Scheme's call-with-current-continuation.

The legions of programmers who have entered the market recently only because they see it as a quick and easy way to make money aren't interested in taking on the more-disciplined, almost mathematical mindset that seems to allow for maximum immersion into functional languages. Rather, they'll do whatever M$ says is the best way to earn the big, easy bux.

And that's why FP languages aren't more mainstream. (Thank goodness that Perl has map! At least I can sneak FP into one corporate semi-approved language.)

Re:static typing

> it is harder to argue that ML is more productive
> than Erlang or pure Lisp, for example, based on
> static vs. dynamic typing.

Really? I find static typing to be a huge help in debugging my programs. I wouldn't give it up for anything! It may come at the intellectual overhead of learning the type system, but once you do it really does make sense.

Really :) Compared to C, both ML and Lisp provide interactive development, garbage collection, higher order functions, and less bookkeeping clutter. With all of that on the table, with both languages far beyond C in those ways, it is difficult to tell how much of an issue the type system plays in productivity. You will find many notable experts who prefer dynamic typing (Peter Norvig and Kent Pitman, for example), and you will find many other notable experts who prefer static typing. So it is more of a personal preference than anything else.

Re:Why Functional Matters

Many of these indirect benefits are not actually characteristic of functional languages, but are easily available in imperitive languages. Some examples:

- Concurrency. Writing concurrent programs in a functional language is so much more natural. It's easier to avoid certain kinds of race conditions too, since you don't update variables in a functional language.

OOP does this well, also. There are several approaches. One method is to use "actors" (objects whose instantiation represents a thread of execution, where message-send represents an actual intertask message rather than a function call).

A major part of preventing interthread trouble is to use a style where variables are private, manipulated by accessor functions. Then you can build the concurrency control into either the accessor or the inter-object messaging.

It's difficult to design a language (and many smart people have tried) that's imperative, type safe, and powerful.

Actually, it's been done. A notable example is C++. A problem, though, is that classes and books on C++ tend to put their focus on the wrong parts of the language, neglect to teach the use of types as a means of encoding programmer's intent.

Features of functional languages like garbage collection and non-updatable values make it easier to define a language with a powerful type system.

Non-updatable values ("const") are readily available in C++.

Genaralized garbage collection can be built on top of it with some effort. But the language supports four distinct storage regimes for objects (static, dynamic, member, and heap), rather than a garbage-collector-based language's one.

The politically-correct method for handling heap-allocated objects in C++ is with explicit allocation and freeing, then building (or importing by inheritance) appropriate automation for particular classes' usage patterns as appropriate.

Using garbabe collection as the primary has several problems:

- It leads to a style of constructing composite objects as a web of primitive heap-allocated objects, rather than a single object. This vastly increasing the storage management overhead.

- It has unfortunate interactions with finalization (destruction), a very important semantic construct in C++'s style of OOP.

- Garbage collectors tend to work well only for particular patterns of usage - and are usually optimized for program development. This leads to variable and hard-to-characterize latencies in time-critical production applications. (C++ lets you use GC only on those classes that need it, and to use distinct garbage collection schemes for different objects, according to their needs.)

(What keeps C++ from being a nearly ideal language for practical OOP is an obscure hole in the standard: The deliberate, explicit failure to specify which overriding of a virtual member function is invoked if one is called during construction/destruction of member variables of object type. It SHOULD be the derived class' version from the first executable statement of the constructor to the last of the destructor, and base class' version otherwise.)

- Machine independence. Making a type system usually means hiding away the details of the machine, and this usually means that the execution of your program is completely predictable. (Compare to C/C++ "undefined" behavior!)

This is the result of C++ inheritance of C's ambiguous primitive data types. The standard workaround (also available in C) is to construct a small, machine dependent include file that defines a set of unambiguous types (i.e. int_16, uint_32), then use THOSE instead of the primitives elsewhere in the code.

Signature Ascription - This allows you to define abstract data types by naming a type and some operations on it (and their types). This is similar to header files in C (much more refined), but thanks to the type system, you can guarantee that the user can ONLY use your abstract data type the way you intended. They cannot cast, subclass, or use any other tricks to get at your datatype.

For defining abstract interfaces: Abstract base classes. (One or more member functions are not defined until the concrete subclass.)

To protect the guts from tampering: private member variables and private functions.

Yes, you can get around the protection. C++ explicitly gives you enough rope to hang yourself. But you have to express your INTENT to violate the protection by a particular set of casts, or you end up buried in warning messages and NOT trashing the variable.

A couple of reasons:

• Functional languages are slower, as a rule, than imperative languages. Compilation, rather than interpretation, helps - but few functional languages can approach the speed of a well-written imperative program. Of course, there are many occasions where speed doesn't really matter, and even if it did it's limited by I/O, rather than CPU, but it's still a factor
• A lot of functional languages still have the element of research tool rather than real language about them - particularly in the area of their libraries and other associated bits. They don't support things like graphics toolkits, CORBA bindings, parser generators, database interfaces, and the like. Similarly, the toolchains are generally less sophisticated - while some very clever debuggers have been written for functional languages, they haven't been turned into real tools in many cases.
• A lot of people just don't get non-imperative languages. I taught Haskell as a first computer language at a university, and people frankly struggle with it - much more than they seem to with imperative languages.

I like functional languages - the project I'm working on uses them extensively, and Scheme is great to work in. It's a shame that they're not more widely used.

And, while we're naming our favourite alternative languages, you could try Mercury [mu.oz.au], a logic programming language designed for real-world programming. It compiles to C, it's got the best type checking of any language I've ever used, it's fast, and its compiler is good. The fact that it's developed at my former university has nothing to do with it :)

Haiku

(are(languages(These), nice)
(Easy(to_write(code(bug_free))))
(If(can(read(you, them)))))

WHAT!!!

SQL may be nonprocedural; it is not particularly functional, as:

• It does not make functions first class objects;
• It does not eschew side-effects.

SQL is not even strongly relational; see Darwen and Date's Foundation for Object/Relational Databases: The Third Manifesto. [amazon.com]

And see any of Joe Celko's [celko.com] books on SQL to see how weakly people tend to use what relational properties SQL has.

But as for calling SQL a "functional" language, while there may be some abtruse arguments by which some variation on it could be argued to be somewhat functional, it is certainly not recognized as such in the way that Haskell or ML are...

You are in a fashion industry

I've spent the last several years trying to explain to colleagues why they should start using another obscure-but-good language, Eiffel [elj.com], to no avail. Here is what I have learned. Note that this is not about the pros and cons of particular languages or paradigms, its about the way the programming language industry actually works.

The language industry is dominated by network effects. There are major costs with using a minority language, and for an individual project these completely outweigh the benefits, even when the benefits are very large. Hence it is generally far better to stay with a majority language. The costs of a minority language include:

• Support. Sure, you can get a GPL compiler for most languages, but on a project you don't want to have your coders digging into the code trying to fix a bug, you want them writing code. Support is something you outsource.
• Performance. Every minority language claims to be faster than C, but often isn't in practice. Whatever the truth, C and C++ are at least known quantities. Maybe the minority language will be faster, maybe slower. If its faster, well gee so what. If its slower then you have a major problem.
• Tool support. These days even small projects start by drawing UML diagrams and then converting these automatically into class templates. CASE tool vendors don't support minority languages. Ditto for testing and documentation tools. Little things like tying your compiler to your configuration control manager might potentially be major headaches. Again, its more risk that the PM can do without.
• Nobody ever got fired for buying C/C++/Java. If you are a PM this is a major issue. Every language is going to bring some headaches, but if you have chosen a minority language then these headaches can be turned into an excuse for project failure, and hence for hanging you out to dry.
• Trained staff in a minority language are going to be rare. This does not necessarily make them more expensive (nobody else wants them), but it does make recruitment much harder and more uncertain. Alternatively you have to train all your existing people in the new language. And for Functional Languages its not just another syntax, its a whole new way of thinking. The industry went through this with OO languages, and many PMs have vivid memories of reams of non-OO obfuscated C++ written by a bunch of C hackers who had been sent on a one week C++ course. Getting your head around a new paradigm can take months, and this is time that the project just does not have.

So, overall the PMs want to go with popular languages, not for PHM reasons, but for entirely rational local reasons. But rational local decisions turn into globally arbitrary decisions, as the entire herd gallops off in a random direction chosen only because most of the herd thought that most of the herd were headed that way.

The lesson of this is that if you want to introduce a language, you don't concentrate on making it a good language, you try to persuade the herd of programmers, PMs and tool vendors that your language is the Next Big Thing. The important point here is not how much the language will do for productivity, quality and cost, it is to create the perception that everyone else thinks that this language will be the next big thing.

There are two ways to do this. One way is to tackle the whole industry at once. For an object lesson in how to do this, see Java. For an object lesson in how not to do it, see Eiffel. Believe me, I know all about this. I have spent a long time giving presentations extolling the technical virtues of Eiffel, only to have my audience say "y Yes, but in the Real World....". In the Real World what counts is the network effects. And you know what? My audiences were right. It has taken me a long time to realise this.

The other more interesting and more promising way to introduce a new language is to identify a niche market and attack that. Once you have taken over your niche you can expand to nearby niches and start to build momentum. Python is doing exactly this in web serving, for example. Web serving is a good niche because lots of people do it, and productivity and quality generally count for more than raw performance. Projects also tend to be small, so experiments are not the Career Limiting Moves they are for large projects. Education can also be a useful niche if you can afford to take the long view, which is how Pascal, Basic and Unix got started.

Paul.

Experiences...

There is already an established Software Industry built on the principle of going with the majority. This means C-based "because everyone knows it" and mainstream Unix-based "because it's always worked so far".

The trouble with this is, in the big industrial scene, the quality of the code produced is abhorable. It is C, batch-produced, written to some Quality Idiot's idea of a "style guide" to be enforced in totally inappropriate ways. Such things as always checking for a symbolic name as the error return value from a function just go straight out the window, "oh no it's -1 if the host's not found, isn't it?".
What's even more worrying is that code is not built up with a view to reusability or expansion - things start out small and evolve features until you realise "we should've just used a database for this whole component", but instead of this you get "New! v3! with added triggers!", d'oh.)

I've gone from BASIC through C, C++, Perl and a limited amount of Tcl / Java, into Scheme and other Lisps. I don't find the fact that Lisp as a concept/family is >40 years old a block to it being *good*. It says in the preface to Graham's "ANSI Lisp" book that functional languages can embrace OO languages with minimal addition, and it's right.

But mostly I think it's fair to say that the masses can't cope with the idea of a function being a return-type in its own right (which is probably the defining feature of a pure functional language); they're too used to the "do this, then do that" chronological programmatic way of doing things, rather than saying "make this a list of things, map this function over the list, then this one..." and so on.

I'm learning Scheme. There are some very funky Scheme environments around - Guile, Kawa and Elk all bear lots of inspection; it's definitely coming to something when you can type 'java pig1' and it executes this:

(define (factorial x)
(if (= 0 x)
1
(* x (factorial (- x 1)))))

(map factorial '(1 2 3 4 5))

Unfortunately, the corporate scene doesn't seem to wish to spend the time on this. That's its sad lookout. I'm off to have some fun and party!

~Tim
--
.|` Clouds cross the black moonlight,

It's a entirely new way to think

I took a course on Programming Langauges, and we studied Scheme as our first language. It was a major hurdle for many people. This is probably because you have to think in functions and recursively, as opposed to the structured/imperative way of assignment.

The ultimate goal of functional languages is to have everything act as a function of it's inputs. Setting variables should not be necessary. However, it never works out that way. It would be hell to write that many functions. The spirit is still there, tho.

Probably the biggest problem was the fact that a function is a first-class value (i.e., it can be passed as a parameter, returned from a function and assigned to a variable). Writing functions within functions to take care of little recursive problems was a major stumbling block. Instead of single-stepping your way through an algorithm, you thought of a way to write an anoymous function inside another function to take care of a something. This function is not defined - it is created at run-time. The fact that you could return it was weirding people out as well.

Another thing that throws people for a loop is the lack of non-local exits. There is no return in Scheme (or Elisp. I don't know about Lisp, but I would imagine it is similar). Instead, you have a very generalized procedure called call-with-current-continutation that does everything return does and more. It actually allows you to save the state of your program, put it in a variable and use it again later. Thus, you can make generators for infinite data structures. This is hard to grasp, especially after two years of C/C++/Java.

The fact that everything is a list in Scheme and it is not typed can be a bit of a stumbling block.

Structured/imperative programming is a much more natural way to program - at first. When you get some practice in functional languages, you see how incredibly powerful they can be. (this is not to say C/C++ style languages aren't powerful. They just lack some really handy features functional languages have as primitives)

I think people avoid them because of the total paradigm shift that is involved. It really is quite a leap. There is no lack of literature on it, it's just not published by IDG Books or SAMS ;) The fact that it is not typed and makes it a little slower is also a factor. They also hate Lots of Infernal Stupid Parenthesis! =)

Woz

Functional Programming has a bad rap

I have used functional languages since the 70s. I put together a more-or-less complete implementation of Backus' FP in Rosetta Smalltalk running on a Z-80 (64K RAM, CP/M OS) around 1980, programmed in Interlisp until '87, bogged down trying to implement Common Lisp (which can be procedural or not, your choice) in Windows 3.1 (got just about done, then Steele brought out version 2 -- ugh!) about 1992. Currently I just write one-liners in Perl. What happened?

Mostly, there were no implementations. Plus it's sort of like the Micro$oft dominance -- all the good stuff was written in procedural languages (primarily C/C++), so why fight it? But the real question is why did procedural languages win?

What I don't believe is that it is harder or less natural to think functionally than procedurally. It's just what one is taught.

Like recursion, for instance. In my small experience teaching, I saw the light go on with regularity -- you just chip away at the problem, deal with some part of it, and then (recursively!) deal with the remaining simpler problem. Hmm, that doesn't seem so hard.

Most people don't think about transactional database programming as being like FP, but just think about it -- it's just like Backus' Applicative State Transitions, where one computes the proposed new state, validates it so far as possible, and then installs it as the basis for more computation.

Another thing to think about is the long-standing tradition in math of "recurrence" relations, like the Fibonnaci series, or approximations to pi, or whatever. Those are clear examples of things which could be thought of as iterative or recursive, just depending on the color of the lightbulb.

Re:Abstraction and Debugging tools

As far as user interfaces go, I wouldn't want to write them in SML, either! :)

I wouldn't call grep or wget simple (see the documentation if that's at all unclear!). I don't believe that those two in particular would be terribly bad, though. Performance would probably be really crummy, but I could imagine that some of the more mundane uses of wget (recusively mirroring a website) would come naturally to a functional language.

On the other hand, I think the user interface or presentation of a program should be well-separated from it's data structures or, more towards the dollars sign, its business logic. Why can't the application tier of an e-commerice site be SML-based? With the appropriate connectors (CORBA-based or otherwise) to databases and either a slew of HTML-generating code or some other connector to JSPs, I could see it happening. Would it catch on? I don't know. Java has positioned itself to work well like this. An event-driven program would probably crawl in SML, there are graphical toolkits for it, but I have never used them. If SML is used for the innards, however, it could be much more manageable.

Re:You are in a fashion industry

Excellent points. As an Eiffel "true believer", I would add one more: Nobody really cares about quality.

Programmers want "cool syntax" and "expressive freedom"; programming languages are for hacking with, not for the considered, careful implementation of software.

Corporations and organizations want quick and cheap results. As an all too typical example, the company I work for is on a CMM program to improve our software quality. The definition of "software quality" for our CMM program is that the software is "delivered on time and in budget". As Dilbert's PHB says, "Oh, and we need a banner which says 'Quality'."

Employees resist as well

Trained staff in a minority language are going to be rare. This does not necessarily make them more expensive (nobody else wants them), but it does make recruitment much harder and more uncertain.

A corollary to this is that programmers are going to be less willing to learn a language that no other employer is going to want. Having a few years of intensive (not an insult, just an example) Eiffel experience on your resume might just be a recipe for unemployment, whereas Java programmers are practically carjacked by prospective employers these days. Acquaintences of mine have quit jobs just to avoid being put into this position.

Re:Functional Programming: its above our heads

I think the real reason Java and Perl have been successful is that they were all carefully designed to resemble established, popular languages. Stroustup's stated goal in designing C++ was compatibility with C. Java is basically a simplified C++ with garbage collection. Perl is based in awk, sed and unix shell. All of these languages have marginalized languages that are technically superior in many ways - C++ vs. Ada or Modula, Java vs. Smalltalk, and Perl vs. Python.

Unfortunately, most of the obstacles to the acceptance of a new language are social rather than technical. Backward compatibility and the support of a powerful company are key. A new language faces the same resistance that a new operating system does. Corporations and programmers have made substantial investments in their current toolsets and skills and are very reluctant to throw that time and money away. Something like Java, that looks and feels very familiar, is palatable, but something like Haskell causes panic.

Open source programmers are lucky, though, because there are far fewer constraints on the tools and languages they use. We pride ourselves on making design and implementation decisions on a strictly technical basis, and there's no reason we shouldn't make our choice of languages any other way. There are a number of high quality free implementations of functional languages out there.

I've spent the last few years studying functional programming in my spare time. While I'm not sure that I'll ever use a functional language professionally, there's no question that I'm a much better programmer than I would be otherwise. Libraries like the C++ STL and language extensions like Java's anonymous inner classes make a lot more sense if you've been exposed to closures and generic functions. Studying CLOS makes the limitations of single-dispatch OO systems like C++ and Java clear. But most importantly, functional languages help you see the larger picture - to focus on the architecture of a system without getting lost in implementation details. My experience with functional programming has taught me more about software design than the shelves of OO design pattern books and UML bibles I've waded through.

Any programmer that really loves the craft of programming owes it to themselves to take a walk on the wild side with a functional language or two. I'd recommend Ocaml [inria.fr], a mature, full-featured system that comes with a blazingly fast byte-code and native code compiler, a debugger and profiler, a first-class YACC-like compiler generation tool, a full-featured standard library, and a growing collection of contributed code [www.npc.de]. If you really want your mind blown, read SICP [mitpress.com].

RPN calculator analogy / Beer

I think imperative programming languages tend to be more popular than functional programming languages for the same reason that reverse [whisqu.se] polish [cam.ac.uk] notation [ucl.ac.uk] calculators are less popular [palmtoppaper.com] than those using standard notation. . A standard notation calculator should fill a good number of common needs, but when the going gets hairy, there's nothing like an RPN calculator to do the job quickly.

The same applies to programming languages. For many programming tasks, the imperative model will serve you well, but there are times -- especially when repetitive, recursive or just plain mathematically complex tasks are involved -- that a good functional language is exactly what you need.

P.S. While probably not the best way to compare languages, you might want to check out this web page that compares how you'd get verious programming languages to output the complete lyrics to the "99 bottles of beer" song [ionet.net]. (At last, an almost on-topic posting about beer!)

Network Functional Programming

Cutting to the chase:

An appropriately conceived relational calculus is more powerful than a similarly conceived functional calculus because functions are special cases of relations. [geocities.com]

When I was manager of interactive architectures at the precursor to Prodigy [geocities.com] I spent about a year pursuing functional programming languages as a possible public standard for the network programming language. By network programming language, I mean a language used to make programming distributed applications as transparent as possible with dynamic redistribution of functions based on load leveling and security requirements.

I chose functional programming because the dataflow graphs provided a natural network map, the nodes of which could be redistributed on the physical network without altering any of the logical analysis that went into the writing of the program. The inspiration for this work was my prior experience with the Plato network where I had pushed the creation of a mass market version of that product. (Worthy of digression is the fact that middle management killed the release of that product and may have, thereby, killed Seymour Cray's first company, Control Data Corporation along with the Midwest's chances to be the locus of the network revolution -- 20 years earlier than it finally happened.) I realized that a widely distributed mass market Plato network needed parallel distributed authoring tools for novice programmers. Combined with the Turing Award Lecture [chungnam.ac.kr] by John Backus of BNF and FORTRAN fame [pitt.edu] I was inspired to pursue functional programming when I left Plato to join with AT&T and Knight Ridder in their joint venture mass market information service experiment.

While authorized to pursue this vision by AT&T and Knight RIdder, I initiated working groups involving computer telecommunications departments from Bell Labs, Atari, Apple, Xerox PARC, MIT, Software Arts and Knight-Ridder News to explore a staged evolution from tokenized FORTH-based programmable graphics communications protocol that would fit in the earliest Videotex terminals being produced by Western Electric (which became PostScript) through distributed Smalltalk based on a FORTH VM, and on to either functional programming with data abstraction or possibly a more radical revision of Codd's work in relational programming. During this time of intense activity, I was fortunate to actually meet Alonzo Church and Haskell Curry at the 1982 ACM conference on functional programming at Carnegie Mellon shortly before Haskell's death and at least get them to sign my conference proceedings and personally thank them for their contributions.

The closest I came to finding a working foundation for distributed functional programming (with object semantics) was a synthesis between David P. Reed's distributed file system transaction protocols and Arvind and Gostellow's U-Interpreter for dataflow computations (see the special "Dataflow" issue of IEEE "Computer", I believe it was December 1980). It turns out that Reed, Arvind and Gostellow had come, from two distinct directions, on virtual machines to describe their programming systems that were isomorphic to one another. Reed's distributed transaction file system was based on the object oriented CLU programming language developed for OO research at MIT, and Arvind and Gostellow had come at theirs from the work on dataflow computers arising from the excitement inspired by Backus's previously mentioned Turing Award Lecture. Reed's system was particularly important for funcitional programming enthusiasts because he was directly addressing the concept of network state, transaction mechanisms and the practicalities of network timeouts, faults and other real-world difficulties. Unfortunately, although Reed would go on to become chief scientist at Lotus Corporation, where some collegues of mine from the Plato project were developing a distributed programming system called Lotus Notes, Reed never actually pursued his conception of network state within the context of functional programming, nor even within the context of Lotus Notes! Perhaps this was my fault for not attempting to beat Ray Ozzie over the head with Reed's thesis, but Ray was pretty cagey about what he was up to at Iris Associates back in 1984. By the time I found out Reed was Ray's chief scientist, I assumed he and Reed were working on something related to Reed's thesis. Imagine my surprise to discover Notes was not only a distributed file system of sorts, but that Reed's primary theoretic expertiese was never actually discussed as a foundation for Notes! But it gets better: the most ironic twist is that Reed and Arvind were both at MIT's Laboratory for Computer Science when I discovered their respective works. When I went to visit them at MIT's LCS, I walked up the stairs from Arvind's office to Reed's office to discover that they had no idea that their respective VM's were nearly identical despite being based on entirely different approaches -- and that neither of them were particularly interested in talking to the other about a synthesis between their works!

Academics...

In any case without a good foundation for handling network state in distributed functional programming, I was left facing the same sort of problems faced by John McCarthy when Marvin Minsky et al took off and started to kludge in all kinds of arbitrary state handling "formalisms" into McCarthy's mathematically pure implementation of Church's lambda calculus: LISP. I saw where that road led...

While a degeneration of Reed's approach was actually tried on the Intel 432 project under the iMAX operating system's distributed OO file system, to the best of my knowledge, the only other attempt to implement his system was a distributed archive object base that I prototyped a few years back at Filoli Information Systems (formerly Memex -- the company that bought out Xanadu Operating Company and attempted to resurrect hypertext after Autodesk dropped support when John Walker was displaced as CEO from that company and ultimately from the entire country).

However, I've never really been happy with the functional approach because functions are a degeneration of relations. That's why I've always been more interested in advancing the state of relational programming than that of functional programming. The problem is, functional thinking is embedded in our mechanistic views of time and causality -- sort of the way up and down are embedded in our physical structures due to having evolved on the surface of a planet. If we're going to deal with distributed persistence and transaction problems, we may as well handle the more general case -- especially since relational programming is at the root of the relational database industry, and it appears a relational formulation of time based on a revision of Russell and Whitehead's Relation Arithmetic, may end up dominating the future of physics.