Lambda the Ultimate

Could be that the reason that higher-level languages are not more commonly adopted is that the people who understand and love them don't have the motivation to work on all the systems-level infrastructure that's required for them to be usable.

Maybe a language needs to be able to "boot" itself by having a group of enthusiastic early adopters sufficiently embedded in systems programming to do the things like compilers / virtual machines / editors and libraries that are necessary for them to become interesting to a wider audience.

Either that or the language needs to be good for creating that infrastructure.

Rather uncalled for.

Those who need FP already use it, don't they?

But most of the computing problems in IT is about input, processing and management of a company's data,

which mainstream imperative programming languages already can do in great success.

Why bother with FP is the project is trivial?

The overuse of state seems to be at epidemic levels in our industry.

Indeed. Many fellow programmers are unable to think of a solution to a problem as a computation.

But does it really matter? most problems are so trivial, that using state or not does not really make any difference.

Generally speaking, all problem solving is about input, processing, and output.

I meant that most projects are about forms and databases: input data in a form, store it in a database, retrieve data later, do some form of trivial processing.

Depends upon what criteria one uses for evaluating success.

I don't disagree that using FP languages would have some benefits in the end result.

But look the overall process of software: I have a contract, and my clients demand certain functionalities from me. The problem is trivial: lots of different input forms, a database back end, a client server architecture, and a minimal set of web pages.

Under this light, why should I choose (for example) Haskell? I'll go with Visual Basic, which can help me deliver the forms very quickly, has tones of tools, documentation and examples, and I can find plenty of programmers to help me deliver the product.

Well, if the problem is trivial, the solution should be trivial as well.

Indeed. Perhaps a client-server DB application would be very easy to write with Haskell, perhaps as easy as Visual Basic. But since I know Visual Basic, why should I waste time migrating to Haskell?

On the other hand, If I was writing an air-traffic control system, or a power-plant control system, or a multi-million dollar bank system, I may consider Haskell or Erlang or another functional language. But most of the projects around me certainly are not as big as that, and they don't justify migration to a functional language.

EDIT:

The last few years I have been working on the training system for the simulator for Crotale NG. The main system is in ADA and the training part is in C++. How would I benefit from using Haskell, for example? most of the bugs in the system are logical bugs, none of which Haskell is able to catch. The term 'logical bugs' refers to requirements not being complete, not fully understood, not being consistent or concise. I really doubt there would be any benefit from using Haskell or any other functional language.

I've had plenty of logical bugs per your definition effectively caught by the fact there wasn't a well-typed way to translate the specification. If you start needing to pile up hundreds of lines of kludge just to outline what the system looks like this tends to be a strong hint.

Can you please show me some examples of the kind of logical bugs you are talking about (and perhaps the solution)? just to get an idea of how FP can help in this way.

The best way to get such an idea is to actually write some non-trivial programs in a typed functional language.

I haven't been a part of this conversation yet, but I've been following it for a while. It's migrated well afield from the OP, but to my eye it currently appears thus:

First person: "I'm not well-versed in functional programming style, and I'm considering whether it would be a good investment of my time to learn it more thoroughly. Can someone point me at some examples of non-trivial functional programs within one of these several problem domains (with which I'm familiar) so that I can read them? I'd like to see how functional programming addresses the kinds of issues I usually face."

Second person: "In order to see how FP relates to these particular areas, you'll have to write the solutions yourself in FP style."

While I don't doubt that writing the code would provide many valuable insights, I believe some people in this thread are actually asking for code to read. If they (or I) could indeed already write non-trivial functional programs within these problem domains, I suspect they (I) wouldn't be asking for pointers to examples.

Are there any open projects using FP languages within the domains mentioned (I believe that so far they are interactive database access and interactive games), or other similar domains? Reading code is a great way to learn, in my opinion, and I'd love to be able to do that in this situation.

(My partner, on seeing this, offered me a link to "Space Invaders in PowerShell". PowerShell isn't a functional language, and the program is entirely in imperative style, but it's the kind of thing I'd love to see in, say, Haskell.)

I don't agree with your summary of the conversation. Achilleas' main theme seems to be "Why bother with FP is the project is trivial?" I'd agree that this perception is certainly a reason why most people don't start looking for better solutions the first time they have to write, say, a simple web app using PHP, but up until now I haven't responded on that aspect of the discussion.

However, a pretty much unrelated subthread arose, in which it was asked how Haskell might help catch "logical bugs" in the development of software for the Crotale NG Multi-Mission Air Defense Missile System training system simulator. This is a rather different question than "Why bother with FP is the project is trivial?"

Philippa's response referred to a phenomenon which occurs when translating a specification into a typed functional language: many cases of "requirements not being complete, not fully understood, not being consistent or concise" are exposed quite relentlessly. Merely reading code, in an unfamiliar language, is not going to help anyone understand why this is the case: you need to try to express your own problems, so that you experience what happens in the case of such a logical bug. There's a phrase in the LtU policies, taken from a comment of Ehud's, "You cannot learn swimming by debating the color or shape of pools". In this case, staring at the pool won't help either. You have to get wet. That was, in part, where my response was coming from.

A paper that analyzed this logical-bug-catching phenomenon and examined examples might be interesting; I'm not aware of such a paper. I think it's a bit much to expect that someone is going to give such an analysis in a comment on LtU, although it would be welcome.

Another factor is that this site is dedicated to the study of programming languages. You can't get very far in even the most basic introductions to that topic, such the books and papers mentioned in the Getting Started thread, without learning quite a bit about functional programming, because functional programming is the metalanguage of programming language theory[*]. Someone who's wondering whether there's anything in FP for them is not thinking in terms of studying programming languages, and might find better answers to such questions in some other forum.

[*] Being metalanguages is a big part of what makes them good at expressing specifications, and catching bugs in specifications.

Actually, your point about studying programming languages returns, I think, to the beginning of this thread: "Why people don't use functional programming?".

There's a subtle distinction there: the question isn't "why don't people learn about functional programming?", but more along the lines of "why don't they use it, directly and obviously, in more everyday projects?" I don't question the utility (even the importance) of studying functional programming. But the academic subject must become the practical technology at some point. I interpreted the theme of the original post as an inquiry into whether that has happened with functional programming, and if not, why.

Again, I'm entirely with you on the idea that learning about functional programming is valuable. But it's almost a cliché to hear, in almost any discussion of the practicality of {PLT concept}, someone say "learning about {PLT concept} makes you a better programmer, even if you never actually use {PLT concept} directly in your work." That may be true, certainly, but it doesn't answer the question "why don't people use {PLT concept} directly in their work?"

It ends up looking rather like Latin. Learning Latin might be A Good Thing in academics (at least, it used to be), but it's not really a technology you can apply much in your daily life (except in certain rarefied fields). Were someone to ask, "why don't people use Latin?", a reasonable response might be "Latin is not intended for practical daily use, but instead as a piece of your general academic foundation. It can make other study easier or more obvious, but it's not likely to be a primary skill."

I don't doubt that this analogy doesn't hold for functional programming. But it certainly seems sometimes that it does, and in no small part due to the dearth of examples of its concrete utility.

"why don't they use it, directly and obviously, in more everyday projects?"

That's been discussed quite a bit on LtU in the past. There are a lot of reasons for it, and I believe that the (relative) lack of examples are a consequence of those reasons, not a primary cause. One could go on for pages, if not chapters, about the various network effects at play. I described one class of such reasons in a comment about some of the ramifications of the C hegemony.

While I do not disagree with the basic promise of your argument, I asked for a demonstration of 'logical bugs' because I suspect the term has (slightly) different meanings for each one of us.

Someone who's wondering whether there's anything in FP for them is not thinking in terms of studying programming languages

But the issue at hand is not about studying programming languages but about using programming languages, i.e. applying the knowledge into everyday practical problems. The thread's title is 'why people don't use functional programming'.

But the issue at hand is not about studying programming languages but about using programming languages, i.e. applying the knowledge into everyday practical problems. The thread's title is 'why people don't use functional programming'.

The topic post requested pointers to papers on the subject, it wasn't a call for personal testaments of FP skepticism. If a new member had posted the same question, I would have posted a less terse response, along the lines of my explanation to Wolf, with a link to the Getting Started thread.

As to whether our definitions of logical bugs are different, I agree with Philippa that by the definition you gave ("requirements not being complete, not fully understood, not being consistent or concise"), that expressing a problem in a typed functional language like Haskell or ML will indeed catch many such bugs, and help improve your specification. The only practical way I can think of for you to verify that for yourself is to actually try it, as I said, unless the Koenig article that was linked to answers your question.

The topic post requested pointers to papers on the subject, it wasn't a call for personal testaments of FP skepticism.

Papers can offer information, but sometimes it might be equally interesting to hear what people say. I don't see why we should not discuss about it.

that expressing a problem in a typed functional language like Haskell or ML will indeed catch many such bugs

But there is always a class of bugs that Haskell can't catch...

Anyway, if you don't want people to talk about this subject, that's ok by me...

As to whether our definitions of logical bugs are different, I agree with Philippa that by the definition you gave ("requirements not being complete, not fully understood, not being consistent or concise"), that expressing a problem in a typed functional language like Haskell or ML will indeed catch many such bugs, and help improve your specification.

To a certain point this may be true. Prototyping a solution in a FP language may give great insight into the inconsistancies and incompleteness of the specification. I know that there are advantages to getting a prototype up. However, in my day job of solving my clients business problems, many more of these incomplete specifications are determined not in the practice of programming in a language but the practice of providing a business design (review and redesign in many cases).

It is more about recognizing the simple fact that people do things for reasons (good or bad) and that much of this doing (and why) is actually held in the heads of those who do it. I would expect that someone who is intending to provide a solution (using computers and programming languages - irrespective of the type) to be capable enough to help the client develop a functional design in the first place.

[An Aside to This is that many projects try to do everything all at once instead of actually seeking to fill the actual needs of the various sections of the business. These needs may not be able to be put into the same basket in the short term.]

The programming language ultimately used and the systems associated will be a result of the business imperatives and the whatever freedom of choice is given to the developers (which may be none).

When I have the choice and oppurtunity, I'll use what I feel is appropriate for the business that is using my services. If I have the freedom to use whatever I need, I'll use whatever I feel is appropriate to the problem at hand.

After watching many discussions and reading the various papers the members of LtU point to, I have come to feel that there are many in the IT industry as a whole who seem to be looking at the tool first instead of looking at the problem first (I see this as the case very much so in the commercial [non-IT] market). I myself have fallen into this trap many times over the years. These days, it is a matter of trying to understand the business imperative and needs of the clients first before developing a solution.

In having raised a couple of questions here myself, there have been a couple of very helpful people who have given examples of solutions in their "favourite" language that have given me a very good insight into the uses of the various FP languages and how they may be usable in a business context.

Ralf Lämmel has written a paper which exposes a number of type errors in the Mapreduce paper from Google. Those type errors are logical bugs, and definitely included in what this thread has been talking about.

Discused here.

To be fair, a lot of the advantages can also be apparent in strongly-typed languages of declarative inclination that isn't functional as such. Either way, inconsistencies in the spec rapidly become inconsistencies in the code - ones which can be exposed to and caught by the type system. In particular, inconsistencies in data flow will be exposed where a language like C++ would all but encourage you to brush them under the carpet - this being the advantage of maintaining a pure-by-default approach. Similarly, if the requirements are incomplete or incompletely understood, sooner or later you'll end up with a piece of code approximately like so:

foo = ... bar ...
bar = undefined -- WTF am I supposed to do here, anyway?

because there isn't a natural "just gets it done" translation, however badly-performing it might otherwise be, whereas if the spec is complete and understood then you'll instead stop expanding things out when you're down to library structures, types and operations you've already defined and perhaps a range of tasks that're known to be understood sufficiently ("insert CRUD form here").

In fact, if you allow a little bit of metapseudoprogramming along the lines of "map makeCRUD descriptions" in the first pass then even conciseness can be attacked. There was an incident on IRC a while back when someone commented you'd have to be insane to write more than 1000 lines of Haskell, to which the reply came that this was true because you shouldn't need 1000 lines for anything - while not literally true (GHC being a perfect example), if you can't on some level translate the spec into a comparatively small piece of code in the kind of style I'm referring to plus a pile of data then there are fairly good odds you've got a rather heavy spec to work with. You might even use this code sketch as a first pass at refactoring the spec!

An anecdote about ML type inference

Indeed. Many fellow programmers are unable to think of a solution to a problem as a computation.

But does it really matter? most problems are so trivial, that using state or not does not really make any difference.

I meant that most projects are about forms and databases: input data in a form, store it in a database, retrieve data later, do some form of trivial processing.

Anyhow, I think you trivialize the amount of complexity involved in database-to-user-form apps. Designing a good database schema is very hard. Designing a good UI is even harder. Perhaps the apps you work on can get by with Client-Server. Most apps I work on these days demand the web interface be either the sole means of access, or at the same level of capabilities as a sister desktop application. Users want access to their data at all times and all places. Many of the client-server apps I've been involved with lately also involve cache clients, where the user can go off-LAN and have the full power of the app built into the client - synchronizing when the user gets back on-LAN.

I don't disagree that using FP languages would have some benefits in the end result.

Or put another way. Perhaps most programmers will need to fall back on state, but that doesn't mean that it should pervade every line of code that we write. Personally, I think that even more important than functional programming is the declarative paradigm (though the two tend to overlap). Those databases that you refer to are quite declarative in nature - everything from the schema on down to the retrieval and updates. The question is why is it we don't use the same techniques to build our forms. Forms are mostly declarative in nature. Yet the tools and languages we use fight the separation of the declarative portions from the procedural portions.

Under this light, why should I choose (for example) Haskell? I'll go with Visual Basic, which can help me deliver the forms very quickly, has tones of tools, documentation and examples, and I can find plenty of programmers to help me deliver the product.

Indeed. Perhaps a client-server DB application would be very easy to write with Haskell, perhaps as easy as Visual Basic. But since I know Visual Basic, why should I waste time migrating to Haskell?

How would I benefit from using Haskell, for example?

I'm probably in the minority but I tend to think of most programmers as smarter than many give them credit.

I do not know, but from where I stand, it would be easy to counter your argument. And sites like thedailywtf show many examples of bad programming.

A common assumption is that this domain represents the bulk of manpower requirements for programmers.

Well, most projects I have worked on, seen, discussed about in this and other companies in all the 10 years of my professional career are about forms and databases.

Anyhow, I think you trivialize the amount of complexity involved in database-to-user-form apps. Designing a good database schema is very hard. Designing a good UI is even harder.

I was talking about the complexity of code. DB and UI design are certainly hard, but not really that complex.

Perhaps the apps you work on can get by with Client-Server. Most apps I work on these days demand the web interface be either the sole means of access, or at the same level of capabilities as a sister desktop application. Users want access to their data at all times and all places. Many of the client-server apps I've been involved with lately also involve cache clients, where the user can go off-LAN and have the full power of the app built into the client - synchronizing when the user gets back on-LAN.

Web apps are still client-server, be it 2-tier or 3-tier.

The complexity of web apps comes from the erroneous concept of browser and hypertext documents used for interactive applications, not from the complexity of computations or the number of states of the system.

Well, as near as I can tell you equate functional programming with Haskell (and perhaps Clean). I think ML, Oz, Scheme, Erlang and just using FP with current languages (like Boost) also deserves attention. Is it really necessary to chuck the concept of FP simply because one can't see programming in a pure language like Haskell?

I usually write about Haskell because it is the favorite around here :-). But I agree with you, and I already have written elsewhere that I would like to see more FP in mainstream languages.

Perhaps most programmers will need to fall back on state, but that doesn't mean that it should pervade every line of code that we write.

I couldn't agree more.

I think that even more important than functional programming is the declarative paradigm (though the two tend to overlap). Those databases that you refer to are quite declarative in nature - everything from the schema on down to the retrieval and updates. The question is why is it we don't use the same techniques to build our forms. Forms are mostly declarative in nature. Yet the tools and languages we use fight the separation of the declarative portions from the procedural portions.

You've described the problem correctly! here is my comment on Java's Swing app framework.

Here is another comment I made on allegro.cc about Ajax and ASP...guess what answer I got: "stupid LISP is not ASP", although a simple declarative language could reduce an 1-hour effort to 5 minutes.

But that's different from saying that Haskell doesn't have a place for a significant number of projects that do require a bit more programming discipline. Personally, I think the number of PLs in active use will continue multiplying. The days of a single language (which probably never existed) are numbered.

Ooops! unfair comment :-). I've stated that in my opinion Haskell and other languages are better for other types of projects, even necessary.

But the topic is that 'why people don't use FP' and my reply is 'people that need FP already use it'.

As people are probably getting tired of hearing by now, multi-core architectures mean that new programming models are desperately needed. There is an enormous economic imperative to find some way, any way, to allow average and below-average programmers to cleanly and safely utilize multi-core machines at reasonable efficiency. The industry absolutely will be spending tens of billions of dollars on this problem one way or another, and it would be nice if the end result was something decent. Many of the ideas from current functional programming languages will be necessary to this effort, even if the actual languages themselves probably won't.

Suppose that we have a fully pure FP program of many lines of code. Ideally, every little expression of the program could be executed in parallel. But almost in every expression the result must be passed to another expression! How is this program going to be automatically parallelized?

Obviously the parallelization can not take place in compile-time, because neither the size of data nor the availability of threads/CPU slots can be determined at compile-time. The scheduler needs to exist at run-time. How is the run-time scheduler supposed to work? how is the scheduler going to be able to understand how to best allocate resources to threads?

Furthermore, access to the memory manager should be synchronized. Since FP programs do lots of heap memory allocations, the number of synchronization attempts would have a big impact on performance.

Your failure to imagine it doesn't mean that it cannot be done.
LLNL's Sisal language was competitive with Fortran over 15 years ago.
Robert Bernacky also wrote an APL compiler that did exactly the optimizations you mention.
None of the other problems you mention are unique to functional languages. OpenMP, for example, has runtime scheduling.
(edited to mention APL)

SISAL looks fairly neat. Anybody know how popular it is, or how it feels to use vs. say Erlang?

I wonder if there can be a compiler which automatically parallelizes FP code, without special semantics.

I actually wasn't thinking about automatic parallelization, but rather manual parallelization. Programs written without mutable state (or with localizable state) are much easier and safer to manually parallelize than programs with global state. Google's map-reduce works on this principle, with junior developers able to slot their more-or-less functional programs into a massive parallel/distributed backplane.

Furthermore, access to the memory manager should be synchronized. Since FP programs do lots of heap memory allocations, the number of synchronization attempts would have a big impact on performance.

This is a long-solved problem (>30 years solved, IIRC). Modern memory managers for GC'ed languages allocate thread-local memory pools. Accessing those pools for allocation requires no synchronization, unless the pool needs refilled.

Data Parallel Haskell and Haskell on a Shared-Memory Multiprocessor might be of interest to you.

For your scheduling problem - how does your scheduler work today? How does your OS understand how to best allocate resources to the programs you run?

The problems you highlight with concurrent memory allocation and garbage collection have had a fair amount of research on them, people are very much aware of the problems.

Just a quick word: functional programming in functional languages is based on lambda-calculus and lambda-calculus translates quite naturally to pi-calculus. In turn, behavioural theory of pi-calculus defines quite well how to perform transformations (read "increasing parallelism") without altering the semantics of a term.

While this is not a decisive argument, it does suggest that functional programs may be easily translated to quite optimised parallel code.

This is definitely not my cup of tea, but a different approach is The semantic layers of Timber that describes a stratified semantics of a language with one layer closely resembling process calculus.

In general the need to exchange data over the internet strongly suggests list structure, as does all communication.

I think that the more general structure you're getting at is the algebraic data type and more specifically recursive types, of which lists are merely the simplest example. Functional programming languages are designed to handle such types, and do so very well.

The FP with Bananas & Lenses paper shows how the definition of lists can be generalized to recursive types, and how fold, unfold and related operations can be used to relate and translate between different recursive types. The paper is quite mathematical, but its basic message can be gleaned without following all the math. (For some advice on one way to work up to this paper, see the last paragraph of this comment by Dominic Fox in the Getting Started thread.)

The Universality of fold tutorial, while it focuses on lists, covers the important, general properties of fold, which can be generalized to recursive types as described in the Bananas paper. Both of these papers are mentioned on the LtU papers page, for good reason. There's more to it than lists!

For me, writing such a program in a purely functional manner would be a lot more of a puzzle.

But most functional programming languages are not pure! I do think, though, that the very existences of pure functional programming languages acts as a kind of bogeyman for many people. Perhaps they suspect that the impure functional languages are just there to lure them into doing the hard stuff -- a gateway drug. You start out using fold, and end up mainlining monads...

I think it's much more productive to think of purity as a way of understanding why we use impurity (at least when starting out, i.e. while you're just doing pot). Purity is also, of course, useful when dealing with programs mathematically, so my comments about FP in PL Theory apply here.

Agreed, but then what's the point, really? If purity doesn't really matter, there's a lot to be said for the "people have taken what they want from functional programming languages and rolled it into other languages" point of view.

I didn't say purity doesn't really matter. Even experienced imperative programmers know that it matters a lot, but that doesn't mean that achieving complete purity in e.g. the Haskell sense should be an overriding goal for every system. However, the kinds of systems you mention can still benefit from a more disciplined approach to mutation.

If doesn't really matter, there's a lot to be said for the "people have taken what they want from functional programming languages and rolled it into other languages" point of view.

There's a lot to be said, but I'm not sure that very much of it is good. Very few languages other than the ones usually identified as functional are able to exploit functional style to any significant degree. Purity is far from being the only feature of functional languages that hasn't yet been rolled into other languages. Even something as fundamental as dealing with recursive types hasn't yet been credibly dealt with in any non-functional language that I can think of, which is a pretty serious limitation on exploiting functional style. One might propose that OO is the mainstream answer to that, but there are plenty of problems with that idea.

Now I'm seeing my previous posts weren't worded all that well, but anyway...

Programming in Python (for example) is a lot more value-oriented than programming in C. Strings are immutable. It's common to create complex structures on the fly. There are list comprehensions, map, filter, and a limited form of lambda expressions. There's garbage collection. From my personal experience, these are things I associated with early functional languages like Hope, and now they're standard in various scripting languages. Yay!

Other things from functional programming are not standard: absolute purity, recursive types, monads. I think those are generally viewed as less useful. (Note: I'm not knocking functional programming at all. I use Erlang quite a bit, and have gone further than I suspect most people have in terms of purity.)

There's certainly been feature migration, but it's piecemeal, and misses some of the main benefits of FP. That's to be expected, and isn't too much of a problem as long as the migration is an ongoing process. But it's a mistake to think that the important migration has essentially all already happened.

(Individual feature migration between languages/paradigms can be a sort of "ducks swim well, so let's glue their feathers on our swim trunks" approach. While it might give some useful capabilities, it doesn't capture the full benefits by any means, and in fact it can be counterproductive — "well, those duck feathers didn't work out so well, guess those ducks aren't such good swimmers after all.")

Recursive types may very well be "generally viewed as less useful", but that view is wrong: they're critical, and the links in my comment Lists generalize to recursive types help to explain why. Without good support for such foundational features, it's not really possible for the non-functional languages to exploit functional style properly.

You also mentioned absolute purity again, but it's really providing disciplined ways of managing impurity that's important, even in Haskell. I don't agree that such capabilities belong in the "generally viewed as less useful" category: most mainstream programmers regularly deal with the issues created by impurity, and many techniques, ranging from ad-hoc to language-embedded (e.g. 'const' declarations) are used to help deal with it. The problems created by impurity are recognized by many, but mainstream approaches like OO are heavily skewed towards a dependency on mutation. Functional programming and languages still have a lot to teach in this area.

Games are getting more complex, though, and in the past ten years or so there have been many "Engines" developed. I suspect this has to do with the increasing complexity of the physics, AI, rendering, etc.

As discussed previously, there is a perception that FP could make this a lot less tedious.

There are still no examples of a large commercial game written in a functional manner, whereas there are thousands and thousands of games written with the most primitive of tools (including Apple II games developed entirely with the built-in ML monitor and no true source code).

I vaguely remember reading ages ago that the Crash Bandicoot games were written primarily in a Lisp dialect (I think - it might have been Scheme), with only a few core routines written in C for speed. I suspect there are more examples out there too, it's just that you don't get to hear about that aspect of them.

Actually, a quick bit of googling turned up this...

Naughty Dog wrote custom Lisp-like languages (GOOL, then GOAL), but they're not FP-oriented. There's a pretty good description in Wikipedia. It's still a very cool and very successful project, in any case.

Typically, functional languages focus on a higher level of abstraction so the ability to declare data of a certain length or do bit level operations is not as omnipresent. However, I see no reason that a functional language couldn't implement those features and I'd be a tad surprised if no such language exists. The GC may be a bit more of a valid concern for apps such as games but GCs are getting better all the time and some languages allow for you to shut them down and do explicit GC cycles at specific times.

There's a separate thread on the definition of a closure so I don't want to stray too far on that here but closures usually exceed the definition of a C struct in that they have visibility to parent scopes (lexical scoping). Granted, you can build data structures out of closures that you may use structs for in C. However, there are constructs you can build out of closures that you can't build out of C structs alone.

For applications that are very performance intensive, like games, you can always use a traditional language for the engine and a functional language, if appropriate, for other modules such as scripting. For instance, WoW uses (at least I'm pretty sure) C++/C for the main engine and Lua for scripting. Although Lua is certainly not a purely functional language, it does support first class functions and closures so you can use functional style if you want.

I just saw mention of Embedded ML in another forum thread.

Seems like all links are broken. Is this project dead?

It uses pattern matching syntax against binary data. In the little bit of time I spent with erlang, that was one of my favorite features. It worked a lot better than manually applying a bunch of bitwise ands and shifts to extract data, which is the way most 'system-level' languages let you deal with the data.

I certainly don't mean my comments in an insulting manner but it seems that the cons you are pointing out are not actually cons but simply questions you had about FP and never investigated.

Bit manipulation is possible in the limited FP's i have taken the time to really look at. Being efficient with memory is hard to say, it depends on what you are doing and if that is just something you feel is necessary or is an actual bottleneck. Some languages offer this fine grained control, others don't. so I'm not sure if that can be considered a con against FP.

Your issue in terms of GC suggests a lack of really questioning ones self when it comes to this. Can you give a reason why you want to manage your own memory? What is the benefit? Is managing your own memory just one of those things you 'feel' is right and has been so deeply en grained in your idea of programming that you feel something is wrong if you aren't managing your own memory? In situations like this it may be valuable to really investigate why you feel manual memory management is necessary and challenge your belief. Now that is not to say that GC is *always* superior, but the number of situations where a GC is lacking is rather small comparatively.

No insults taken. :)

it seems that the cons you are pointing out are not actually cons but simply questions you had about FP and never investigated.

I have attempted to delve into FP and learn what all the fuss is about, and so far I'm not excited. It could be because I just don't "get it" yet. I'm willing to admit that. Perhaps more people don't program in "functional languages" because (as far as I've looked) there's not a lot of places that convincingly explain what we're missing.

I've seen examples about infinite lists, lazy evaluation, closures, etc. And none of them have struck me as extraordinary. Because of speed and efficiency and the type of programs I enjoy creating, none of those things would be a benefit.

Your issue in terms of GC suggests a lack of really questioning ones self when it comes to this. Can you give a reason why you want to manage your own memory? What is the benefit? Is managing your own memory just one of those things you 'feel' is right and has been so deeply en grained in your idea of programming that you feel something is wrong if you aren't managing your own memory? In situations like this it may be valuable to really investigate why you feel manual memory management is necessary and challenge your belief. Now that is not to say that GC is *always* superior, but the number of situations where a GC is lacking is rather small comparatively.

I program heavily in C and so a GC to me seems lazy. Why not just not leak memory yourself? If you're organized and have a good coding style it's not that difficult to manage your own memory. I don't use GC in production work because I can easily write code that doesn't leak memory. (valgrind backs me up). So my benefit of no GC is smaller faster code.

I don't question the benefit of GC for other types of programs, nor their efficiency of doing what they do. I sometimes venture away from C and enjoy programming in "higher" languages. They allow you to program with less worry (like in our discussion, not worrying about memory usage), which is really nice.

However, I enjoy producing programs that are really small and really fast. If my program is more for fun and experimentation, I would have no problem using a GC, but in most my cases size and speed do matter, so I don't use GCs.

Of course, "small", "fast", "easily" are all subjective terms. YMMV. :-)

Actually, the allocation using a decent GC is often way faster than using "traditional" and "fast" manual memory management, i.e. malloc.

The reason for this is that in order to allocate space, malloc searches a list of free memory until it finds an unused block of memory big enough to fit the allocation. Instead GC (for example generational GC) simply increase the "current memory pointer" and check if there is still any memory left. If there's enough, that's all the work that is done, but if there isn't, a garbage collection cycle is triggered. Nevertheless, in general GC allocation is way faster than malloc.

I would say "in some cases, for some malloc implementations," not "in general." Can you point to any papers that support your claims "in general," i.e. using a respected malloc over a variety of significantly-sized programs?

A recent paper or presentation I read summarized it nicely:

If your program does:

* lots of small allocations, GC is often faster
* fewer, but larger allocations, than manual allocation is faster

Most research places GC runtime overhead at 5-20%. The best analysis I've seen places generational GC on par with manual allocation only when the heap is 5 times the size of the live data; smaller heaps mean higher overheads due to more frequent collections. A heap of only twice the live set resulted in 40% overheads IIRC.

Of course, GC is also much safer than malloc/free, which is often more important for us lowly developers. :-)

The fast allocation by pointer bump you mention is only for copying GCs, which aren't widely used nowadays. I don't see how mark and sweep allocation could be much faster than malloc.

Further, manual allocation can be customized to the particular application, so it will *always* be faster in one particular incarnation or other. Question is: how much effort are you going to spend implementing and debugging this manual memory allocator? It takes significant effort to implement non-trivial memory management allocation strategies.

So GC tends to be an overall engineering win, but it's by no means a winner in every category (yet).

A recent paper or presentation I read summarized it nicely:

Saying this without providing a title or a link is grounds for an LtU demerit. ;-)

The best analysis I've seen places generational GC on par with manual allocation only when the heap is 5 times the size of the live data; smaller heaps mean higher overheads due to more frequent collections.

That sounds like Quantifying the Performance of Garbage Collection vs. Explicit Memory Management. Someone summarized it here.

Sweet paper -- thanks for the pointer. That, or something like it, should be required reading for anyone who wants to claim that GC is either "too slow" or "as fast as manual allocation."

Saying this without providing a title or a link is grounds for an LtU demerit. ;-)

I know, but it was late! :-P

I think this was it.

That sounds like Quantifying the Performance of Garbage Collection vs. Explicit Memory Management.

Yup, that looks like the right one. I don't have the earlier papers I've read up on my Interesting Research page (mostly GC stuff). Thanks for the link. :-)

I'm not disagreeing with any part of naasking's remarks. I'm just suggesting a strong either-or opposition of gc or manual allocation is not necessary in a mixel model environment. Not that I can easily point you at one; but it's the model I've been planning around for a while.

Hybrid solutions (both gc and manual allocation together in some mix) can target different approaches for different parts of an application. Getting a nice mix, though, would require a mixed language model, with gc at some higher level and manual allocation at a lower one.

But with a mixed approach you can segregate your data according to purpose. The really large data sets with predictable lifetimes can use manual allocation. And the painfully hard-to-predict, ambiguous flow of control parts can use gc. A division like this would allow you to make gc memory a minority of total application footprint involved, so having five times (or more) available gc space than live data would be easy to arrange for the smaller gc minority.

Presumably the interface between the two would occur at the level of "primitive" definitions, from the point of view of a high level language. You'd be free to push some parts of an application down a lower level to manually control exactly how memory works. For example, you wouldn't really want to do network i/o in memory with non-C semantics anyway.

The ideal I'd prefer is a copying gc model in the high level language using full continuations, and a mixed reference counting and vanilla C model at the bottom for primitives, when I really have to control where things go and when. A copying gc can easily have a nice interface to "externally" allocated memory, because a copying gc can easily tell an address lies outside the space of memory managed by copying, and thus should not be copied or changed in any way.

Anyway, the gc parts can use the fast pointer bumping style of allocation, and get efficiencies from lower block fragmentation (less bookkeeping is needed) and low enough overheads by having a big enough ratio of free space to live gc data in the part of the address space that's collected.

Time pressure in development is big enough that faster development with gc first would be a win, especially when incremental shifts to manual allocation later can optimize exactly those parts most crucial to performance, without introducing a big upfront design requirement before getting a first version done.

We shouldn't forget about region-based memory management[*], as in MLKit and Cyclone. That ought to change the performance equation, but I don't have any numbers. It can be used on its own, without a garbage collector, or in conjunction with GC. There are some related links here.

[*] Old enough to have a retrospective.

You might be interested in Dylan's "Memory Pool System" then:

The Memory Pool System (MPS) is a very general, adaptable, flexible, reliable, and efficient memory management system. It permits the flexible combination of memory management techniques, supporting manual and automatic memory management, in-line allocation, finalization, weakness, and multiple simultaneous co-operating incremental generational garbage collections. It also includes a library of memory pool classes implementing specialized memory management policies.

The Real-Time Java specification includes support for defining memory regions, including different gc semantics for different regions. Arguablye this isn't quite what you are looking for (you can't explicitly free an object, just a region), but it covers the use cases you describe quite well.

naasking: The fast allocation by pointer bump you mention is only for copying GCs, which aren't widely used nowadays.

It's also applicable to generational GC, which seems to be the predominant form of GC these days.

It's also applicable to generational GC, which seems to be the predominant form of GC these days.

Generations are a heuristic optimization, not a collection technique in their own right. As far as I know, pointer bump is only possible with copying collectors, generational or not.

Just came across mark-copy GC which looks promising: reduces generational mark-sweep space overheads by ~80%.

Well, technically you are right. However, in practice most GGCs are copying, at least with respect to promoting from the youngest generation.

When you look at RT apps, GCs don't seem so appealing, same with embedded usage with little memory available.

The problem with GCs is that there are some brilliant GCs such like the new one from IBM, but you don't necessarily have access to them..

When people say "functional programming" or "functional programming language" these days, I think the definition is fairly narrow. Usually it means Haskell-like or ML-like. Almost always it means "languages based on the lambda calculus."

But Iverson and Hui's J actually gets a significant amount of use in industry (financial and actuarial work), and yet it is rarely mentioned in discussion about commercial uses of fp. Some would argue that J is "function level" instead of "functional," but that's a nit.

A reasonable question is "has the fp language community painted itself into a corner"?

In Haskell, again, the compiler has the equivalent of a Prolog system in it to do type inference/checking -- but you can't use its power as a programmer.

I wonder what this statement means?

The obvious interpretation is just as obviously wrong (after all, type inference, etc. does work) and, as has been demonstrated several times (Oleg Kiselyov's Number-parameterized types is the example that springs to mind), the Haskell type system can do all sorts of things that Prolog can do including arithmetic and various data-structures (I seem to recall reading about lists and trees, though I can't recall where, pointers welcome).

You don't mean "obvious", you mean "vacuous". If I had meant to say that the type system doesn't work as a type system, I would have said that.

The really obvious interpretation of what I said is that you can't do Prolog-like things (implicit search, backtracking, logical variables) in a Haskell program -- even though the Haskell compiler contains the better part of a Prolog interpreter to operate on the types.

Josh

This isn't really true. Yes, you can't program in Haskell *exactly* the same way you would program in Prolog, but you can emulate these features you speak of fairly easily with monads (like [] and others). You might also want to take a look at:

http://okmij.org/ftp/Computation/monads.html#LogicT

In fact, I recently was programming part of a theorem prover for intuitionistic logic in Curry (like Haskell, but with Prolog features -- it's a functional logic language), and was taken aback by how much shorter some of my solutions in Curry were versus the same in Haskell. However, after a little encouragement from one of my professors who is a big Haskell guy, I decided to try again in Haskell, and in the end, all it took was a little extra bit of ingenuity (not very much) to get almost exactly the same kind of solutions in Haskell using monads.

For what it's worth, if you really do need "Prolog-like things" in Haskell, you should probably just use Curry, and that way you get the best of both worlds.

So not only is it misleading that you can't do "Prolog-like things" in Haskell at the program level, but even if you have to do it at the language level, there are in fact solutions (Curry).

By the 'googling on language name + programming' metric, Links is more popular than any of the other languages Josh listed, with a grand total of 229 million hits :-)

Indeed, a little further research shows that the most popular programming languages are "a" and "i".

:^)

Josh

That is an interesting comment but your view is that Scheme is more popular than Haskell because ...?

...You can write a program in Scheme without making the types explicit? Will it compile the first time if you made typing errors? Or do you mean that naming types is too demanding?

Would Haskell meet your criteria of a "programmer's language" if type declaration was optional?

... of a "programmer's language" if type declaration was optional?

Good question; I don't know. My impression is that there are several other aspects of the language (and all the mainline ML-like languages) that are awkward.

The bottom line is there are two vastly different basic philosophical approaches to programming language design. The key difference is whether the language designer / compiler writer thinks he understands what the programmer is trying to do, better than the programmer himself does.

Now for programmers in the bulk of day-to-day applications work, this is probably true. But the cutting edge, it's not, and the assumption means that the more sophisticated the programmer, the more time he spends fighting the system.

Scheme otoh has the philosophy that the programmer is in charge, and we'll give him all the rope he wants, and if he hangs himself that's just tough. People on the frontier, programming new kinds of things, inventing new algorithms, find this a more congenial mindset.

Josh

Scheme otoh has the philosophy that the programmer is in charge, and we'll give him all the rope he wants, and if he hangs himself that's just tough. People on the frontier, programming new kinds of things, inventing new algorithms, find this a more congenial mindset.

Around LtU, people won't give much credence to unsubstantiated (and semi-insulting) claims like this. There are a lot of innovative people who do prefer staticly typed languages. I could list several, but I won't, because I Don't Feed the Trolls. If you want to paint with broad strokes, you need to bring your evidence to the table. And I'm not talking about giving us a list of people who are on the cutting edge and also use Scheme, I'm talking about some evidence that the well-respected people who do prefer staticly typed languages are not quite as brilliant as we think they are.

No insults intended. My point was that obligatory declarations, useful in some contexts (e.g. production programming environments) are an impediment in others (research programming).

Here's an anecdote: A few years back, I was responsible for (and wrote version 1 of) two programs for a CAD startup. One was in Python and the other in C. The Python one was larger and did real-time interaction, and was the first substantial Python program I'd written. Not a declaration in sight, of course. The C program was festooned with them, as required, and I've been programming in C for decades. Guess which one had more bugs? Same programmer, remember.

Josh

Comparing Python to C isn't exactly a fair comparison. You should just as soon compare Forth to Haskell to make general conclusions about type systems.

... namely that it is the ontological level of the language, rather than something like static-vs-dynamic typing, that is the biggest factor in its ease of use.

So to pull the threads back together, I claimed that the preoccupation of the FP community with type systems has had a chilling effect on (and diverted effort from) the development of more powerful data ontologies.

Josh

Have you ever used any of: Haskell, Clean, SML, Objective CAML, or Mercury?

I've tried all of them except Clean, and I've tried Oz/Mozart as well. Most my current experimental programming is in Prolog, with a little in Scheme. I've written an APL interpreter in Lisp, and a Lisp interpreter in APL. I've written an APL compiler in APL, and I wrote the first DECSystem-20 Common Lisp compiler (in CL of course). I've written a CAD system in J, and another one in Python. I contributed code in MIDAS to MIT Teco that the original Emacs was implemented in. (writing in J and Teco are similar experiences.) I would guess that overall, I've written programs in 50 languages (for real, not just exercises), ranging from PIC assembly code to Javascript. Trying new languages doesn't bother me. It needs to get a lot of things right for me to stick with it, however.

Josh

...but "try", "play" and "dink with" would be synonyms in my case. :-)

That said, I don't understand what you're trying to say in terms of the study and implementation of type languages interfering with the discovery of more meaningful research avenues for PLs (ontologies). Before beginning that discussion, it might help to agree on what the problem with current programming languages happen to be. I think we can agree that the problem is not that we have too few programming languages.

One problem would be that we have no way to rigorously examine the properties of the programs we write, a kind of guiding principle for type theory. Another problem would be that we are limited in the ways that we can express solutions - i.e. there are problems that currently rank as hard-to-intractable. Or perhaps the problem is that programming languages are error prone and hard to use as a means of communication - i.e. there has to be a way to make us more productive and less prone to mistakes. Or perhaps just a combination of these and many other problems that we currently have to put up with.

Anyhow, what fundamental nature of PL's do you think is currently getting short shrift on the R&D end of the scale?

An excellent question, and one that deserves more thought than I'm going to give it here :-)

I'd say one big lack is seamless integration of the many powerful paradigms that have been discovered. This is a well-understood moral hazard of academia, since you don't get tenure for doing integration work on other people's ideas. There is Leda, but multi-paradigm stuff is few and far between.

A related lack is IDE's and debuggers. Not too much hay to make as a theoretician, but there's a great need for the best and brightest of language mavens to contribute ideas here.

But the biggest lack is ontologies, in datastructures and the operations provided to manipulate them. I think that language designers today are way too ready to provide OO capabilities and punt the issue to the programmer, but that's just a way of ducking the problem. Coming up with a set of datastructures and an integrated set of well-matched operations that combine flexibly to allow the elegant specification of a wide range of representations and methods is very hard work, and the languages community has virtually ignored it for decades.

Because of this, languages have been stuck at a ground level of semantics for the same period. Here's an example: it was easy to write a sort in APL with a matrix expression that compared each element with every other one. Nobody would use that because it's N^2 -- and yet it was simpler and easier to understand than any N log N sort. Suppose instead language research had decided to concentrate on (a) finding ways for the programmer to specify, completely formally, but always more concisely and elegantly, what needed to be done, and (b) finding a way to compile it as efficiently as the state of the art knew how to do?

Josh

ps -- BTW, I do know that there has been some research along these lines, in areas like CLP and as someone above mentioned, Curry, which is a very neat system. But I still opine that we'd be better off if say 75% of the effort that has gone into types had gone along those directions instead.

but multi-paradigm stuff is few and far between.

Have you not read CTM or any of the voluminous discussion it has generated here on LtU?

All the work being done with OCaml also seems to contradict this notion that multi-paradigm issues have been ignored by academics and PL designers.

But the biggest lack is ontologies, in datastructures and the operations provided to manipulate them

Again it seems to me that there is all kinds of work done on data-structures and their signatures (some of it under the umbrella of the type-system investigations you seem to be impugning). Do you have some specific problem in mind that you think needs to be solved via PL research?

punt the issue to the programmer, but that's just a way of ducking the problem

PLT already gives the programmer who takes the time to study it plenty of tools to help him solve his problems (which are too varied for all of them to be anticipated by the PL designer). Very often not finding the "right" solutions is a sign that one is not asking the right questions.

The responsibility of academia is to advance human knowledge in all available directions. The reponsibility to understand the new knowledge so generated, and to use it to solve more immediate problems, lies with the practitioner.

PLT already gives the programmer who takes the time to study it plenty of tools to help him solve his problems (which are too varied for all of them to be anticipated by the PL designer). Very often not finding the "right" solutions is a sign that one is not asking the right questions.

What does PLT have to say about ease of debugging? Ease of maintenance? Requirements traceability? The sad answer is "a lot less then it probably could". There appears to be a decided lack of interest in the PLT community in the sort of software engineering issues where programming language improvements could do the most good.

The responsibility of academia is to advance human knowledge in all available directions. The reponsibility to understand the new knowledge so generated, and to use it to solve more immediate problems, lies with the practitioner.

This would work if academia actually had the resources to explore "all available direction". They don't. Tradeoffs get made, and unsurprisingly those tradeoffs don't always have the best interests of non-academic programmers at heart.

Dave, you're exactly right.

Business isn't interested in PLT. Most of it isn't even interested in software. It's just a means to an ends. And that means is represented by software engineering and not PLT. That's why it takes something like Sun or Microsoft to bridge that academic, real-world-business-interests divide.

A first step is to develop IDEs or plugins that have the same level of support that C# and Java get with VS, Eclipse, IDEA, Netbeans, etc...

What does PLT have to say about ease of debugging? Ease of maintenance? Requirements traceability?

What do you think PLT should say about these?

Debugging is mostly an implementational issue, though various kinds of semantic modelling can help work out a good system.

Ease of maintenance is enabled by all the abstraction mechanisms that are already provided. Very often programmer skill is the limit there.

Requirements traceability is probably a lost cause in general or else perfectly adequately handled by existing documentation methodologies, depending on your inclination. What makes you think PLT should and can make a difference there?

Tradeoffs get made, and unsurprisingly those tradeoffs don't always have the best interests of non-academic programmers at heart.

I would wager that more work gets funded specifically for industry-oriented work than gets neglected by "effete theoretical concerns".

Nonetheless, why do you think that academic investigators have a moral responsibility to investigate the problems that happen to seem reasonable to industry programmers? There is plenty of applicable work that already exists that industry continues to ignore for years to come, due to its own predilictions and blind-spots.

Please keep in mind, I'm speaking as an industrial programmer here, independent of my theory-wonk hat. The latter interest merely allows me to know that there is a lot of work that is done that speaks directly or indirectly to software engineering issues, but because it isn't all framed as pithy solutions to pre-conceived problems, it gets perceived as "irrelevant".

Ultimately, this whole critique of academia as out of touch with "real" concerncs is baseless until one has done one's homework and knows what knowledge has already been investigated, and has applied this knowledge in practice.

Surely, the academic/industry exchange has to be a two-way street?

Debugging is mostly an implementational issue, though various kinds of semantic modelling can help work out a good system.

So programming language theory has nothing to say about observability of program state, validity of state transitions, and abstraction of observational patterns? Have we reduced the subject to literally nothing but types?

Ease of maintenance is enabled by all the abstraction mechanisms that are already provided. Very often programmer skill is the limit there.

There's very little difference from this statement and "our current abstraction methods aren't very useful at easing program maintenance".

Requirements traceability is probably a lost cause in general or else perfectly adequately handled by existing documentation methodologies, depending on your inclination. What makes you think PLT should and can make a difference there?

I would have thought that matching specification to implementation (and understanding the transformations involved) would be well within the scope of programming language theory.

Nonetheless, why do you think that academic investigators have a moral responsibility to investigate the problems that happen to seem reasonable to industry programmers?

I certainly never indicated any such thing. There probably is a good moral argument to be made that, in the face of an enormous social problem ("The Software Crisis", broadly defined) that uniquely-skilled academics have some responsibility to target at least some of their researches toward understanding and alleviating it, but I am explicitly not making that argument.

So programming language theory has nothing to say about observability of program state,

The basic PLT constructs of environments, continuations and stores seem pretty relevant here. Provide inspection of those structures, along with single-stepping and you've got a debugger. Here's just one randomly googled link to some work by the PLT Scheme group on object debuggers. They also have MzTake. Is there some particular aspect of debugging theory that you've looked for information on, and haven't found anything? Perhaps a query on LtU could help.

I must admit I feel sorely tempted to weigh into the overall argument with a long screed, but I doubt it'd do any good. I'm with Marc. It's much easier to criticize than do homework.

The basic PLT constructs of environments, continuations and stores seem pretty relevant here. Provide inspection of those structures, along with single-stepping and you've got a debugger.

More precisely you've got the building blocks of what a debugger currently looks like. You don't have any of the analysis of the deeper semantics of those constructs, what properties might be proved, how they might be abstracted and improved, variations and enhancements that might be traded off, and all the other sorts of things we look to academic work for. Work on types (and concurrency, and a few other things) generate reams of academic work along those lines.

The MzTake link is interesting. The lack of interest in the LtU thread on it is also interesting.

It's much easier to criticize than do homework.

Sounds like someone's spoiling for an argument. Please find someone else to play my side. You're unlikely to change my lived experience, both in academics and out.

What does PLT have to say about ease of debugging?

I certainly have seen papers on replay debuggers, etc. and I don't even like debuggers. Development and acceptance of debuggers, IDEs, etc. also have a psycho-social dimension and I don't think PLT alone can give the answer.

Ease of maintenance?

How do you define "easy" in CS terms? Most of our practices for maintainability such as commenting code properly, using a consistent style, decoupling components, automated testing, portability, etc. are purely human intuition (when does some coupling become excessive coupling?).

Requirements traceability?

Probably not until requirements specifications take some mathematical form. In some circles this can be considered already being done such as with proof carrying code.

Most of our practices for maintainability such as commenting code properly, using a consistent style, decoupling components, automated testing, portability, etc. are purely human intuition (when does some coupling become excessive coupling?).

Right. That's what happens when there isn't much in the way of solid theory available, but problems urgently need solved anyway. People fall back on intuition, rules of thumb, and folk wisdom. It's a sign that there's a lot of scope for good foundational academic work that simply hasn't been done yet.

How do you define "easy" in CS terms? Most of our practices for maintainability such as commenting code properly, using a consistent style, decoupling components, automated testing, portability, etc. are purely human intuition (when does some coupling become excessive coupling?).

It is perhaps instructive to look at languages that were designed with maintenance specifically in mind to get a bearing on what can be done in the way of maintainability. Consider Eiffel, which provides contracts as a basic language construct which helps both with documenting code properly and with automated testing. Further the language itself enforces consistency of style. One could even argue that given an appropriate system to assist (like, say Daikon or similar) contracts and invariants could aid in finding suitable decoupling lines. And all up that's just a limited set of features for a particular language paradigm with plenty of spce for better research into how to handle things (like, for instace, using contracts for concurrent programming). I could imagine plenty of scope for more work for other programming paradigms were maintainability to be taken seriously as an issue.

Thank God for those down to Earth Haskellers with things like this, this, and this.

And then there's this guy. (Oh look, he's done some stuff while I've been away. I love this guy!)

The talk "Weird things that surprise academics trying to commercialize a static checking tool." is very entertaining and very thought-provoking (especially if you're not already familiar with the author's work.)

edited:
The previous comment was vague and relatively meaningless as was pointed out in the reply. Most of the points I wanted to express have already been made more eloquently so I have opted to remove it.

Researchers have introduced many languages that are a significant improvement on the state of the art

What's the state of the art and what are the languages that are the improvements?

At each point, industry has chosen terser syntax and ad hoc semantics.

Java and C# are terse? That's a new one to me.

It is quite frustrating to see people demanding a new language when the problems they are currently having were solved years before.

Who is demanding what language and who doesn't know about these solved problems?

Please clarify your thoughts on how it relates to software engineering.

[All this fascination with bondage-n-discipline does is get in the way of more useful tools.]

[All that power is wasted because nobody wants to look at how to restrain the excess.]

Sigh.

I accept CTM as good example of your point, but I'll throw the OP back at you: my "google test" shows Oz/Mozart programming at the same level as Haskell, 1M refs. It's been around for a while, why not more popular?
This would show that I was wrong to the extent that lack of multiparadigm per se isn't the problem, or at least the whole problem. I'm open to other suggestions.

Josh

Popularity has very little to do with how good something is or how long it has been around. People will stick with what they know. They might migrate to something different, if it's not *too* different and if they are convinced it will help them and if it's socially acceptable. Migration takes time and effort; if people migrated to a new language on every little improvement then they wouldn't have time to do much development.

I am reminded of Stanislaw Lem's theory of the orders of genius (in "A Perfect Vacuum" -- a collection of book reviews of nonexistent books). Geniuses of the first order will get fame and acclaim in their lifetime -- they correspond to changes that are understood. Geniuses of the second order are ignored in their lifetime, but eventually get discovered when society has advanced enough to understand them -- they correspond to changes that are too different. (And finally, there are the hypothetical geniuses of the third order: they are so different that they will never be discovered!)

Or, as Machiavelli put it,
"...there is nothing more difficult to take in hand, more perilous to conduct, or more uncertain in its success, than to take the lead in the introduction of a new order of things."

(I first saw that quote in Knuth Vol.III, Sorting and Searching :^)

There's definitely the "nobody ever got fired for choosing IBM" (nowadays Microsoft) phenomenon... but there's also the problem that if you're smart and insightful and so forth -- a Lem genius of the 2nd order -- and you pick, say, Haskell, as the implementation language for a project, you're going to be very hard pressed to find people to hire to use it.

I spent the '80s (and $1M of taxpayer's money) developing hardware associative memory, including a very nice programming model and language. I couldn't even get the AI researchers at Rutgers to look at it (though there was strong interest from the database mining area). So yeah, you can lead the horses to water but they'll die of thirst while looking at you quizzically and saying, "You're wierd."

Josh

...considering that type systems are precisely about exploring the relationship between logics and types, and that in the limit the distinction between programming-language-and-type-system vs. theorem-prover-and-logic(s) gets very blurry indeed! Heck, I'm not persuaded that talking about "data ontologies" without talking about type systems is even coherent.

OK, implement this language: it's kind of a functional Perl; every value is a string. Your function type declarations still give the argument and result types, but each specification is a regex (which can contain variables referring to other regex/types, and is thus a nice polymorphic formulation.

Why hasn't somebody at least tried this????

Josh

every value is a string. Your function type declarations still give the argument and result types, but each specification is a regex (which can contain variables referring to other regex/types

I'm reading a use/mention confusion here. It is unclear what benefit you get by collapsing the string encoding of a type with the semantic specification of the type itself.

If I'm misreading you and instead you mean that the data-structures are to be semantically described as regexes, then you are limiting yourself to data-structures that can be described with a linear encoding. Trees, for example, would not be specifiable.

Either way, without some further elucidation that I'm missing, the idea doesn't seem to offer any coherent advantage, which might explain why no one has investigated it (assuming no one has, and not that we just may not be familiar with that work)

He said "which can contain variables referring to other regex/types", so if that includes variables referring to the same regex, ie recursion, trees would be specifiable as well.

so if that includes variables referring to the same regex, ie recursion, trees would be specifiable as well

A "recursive regex" that could represent a tree wouldn't be a regex. Regexes can only represent linear grammars; tree recursion is by definition a context-free grammar (at least).

If your not familiar with the Chomsky Hierarchy, consider what a recursive regex embedded in a recursive regex embedded in a regex would look like...

For the record, "not regular" is a canard, as "regular expressions" haven't been regular in decades (because of back-references, if nothing else). The Perl-compatible "regexes" that most people use aren't regular at all. Both Perl and PCRE feature recursive patterns, and the next version of Perl will have something like full Prolog-style backtracking search in its "regex" engine.

The Perl-compatible "regexes" that most people use aren't regular at all. Both Perl and PCRE feature recursive patterns, and the next version of Perl will have something like full Prolog-style backtracking search in its "regex" engine.

And if you are going to propose a "regular expression" typing that is at least context-sensitive, if not unrestricted, what design advantage does this provide over a more coherent type-system based one?

To quote Jamie Zawinski:

Some people, when confronted with a problem, think “I know, I’ll use regular expressions.” Now they have two problems.

I actually think "regex typing" would be a terrible idea, but conflating modern regexes with regular languages leads only to confusion. And while I love the Zawinski quote, jokes aren't arguments.

Er... isn't this an exact description of CDuce (or OCamlDuce)'s type system ?

Hardly exact :^)

CDuce does appear to have regexes among the other stuff in tis type system, and thus forms a nice example of why someone would want to do this. In fact I'd say that it was a good example of a language designed around programmers' needs instead of from theoretical concerns.

Thanks for the pointer.

Josh

I love the quote.

To my mind, you answered your own question in your title: the scheme I proposed would constitute duck typing on strings. How useful would it be? I have no clue -- it was just an offhand idea. Whatever people use Perl for, presumably. But it would be a goldmine for language research -- consider writing a compiler that could

• optimize the code for a function using the knowledge that the input string matched the guard regex

• decide when a test was necessary, and optimize the test, of the string to make sure it matched the regex on input. This could involve being able to compare regexes and tell when the language accepted by one was a subset of the language accepted by the other

• automatically determine if the result of the function code would match the output regex

• optimize the search generated by using the guard regexes for pattern-directed function invocation

• etc. galore!

They have, only without characters as a primitive building block. They're called algebraic datatypes, using lists for *.

Two almost unrelated issues seem to be being conflated here. A question was asked upthread about whether Haskell would "meet your criteria of a 'programmer's language' if type declaration was optional". Of course, type declarations in Haskell are optional, so exactly what is meant here needs to be clarified. I suspect the original question may have had to do with whether a program needs to have a statically checkable type scheme. That's only slightly related to whether type declarations are optional or obligatory.

Either way, drawing any general conclusions about properties of type systems from anecdotes about C is questionable at best. C has many unsafe properties that have little to do with its type system, except in the sense that its type system is too weak to prevent many kinds of severe bugs. It's a safe bet that those unsafe properties were a major source of the mentioned bugs.

As far as research programming goes, prototyping with types can be a very powerful technique. Any characterization of which approach is better would have to take a lot of context into account, including programmer preference and bias, and specific properties of the languages being compared.

Josh wrote "you aren't really going to be the kind of person to use a theoretically sophisticated language of extreme expressive power anyway."

Whilst I understand this comment, I don't entirely agree with it, because I think it confuses sophistication with syntactic complexity.

Type inference is a good example of what I mean here: type inference engines are quite sophisticated, yet their very purpose is to relieve the programmer of the need to supply type annotations.

I believe the average C++ programmer would welcome the proposal to use the auto keyword for this purpose, for example:

  auto x = 1;

Similarly, I believe a programmer would welcome the advent of "sophisticated enough" automatic theorem proving capability, that this technology could be deployed in a production programming language to help establish correctness.

Type INFERENCE is a wonderful thing, and every language should have it, and every IDE should pop up a bubble with the type whenever the cursor rests on any expression, etc, etc.

A major problem with algebraic types, however, is that having the ability to do sound-and-complete inference with them has stunted language developers' desire to experiment with more useful specifications of the values a variable might contain (e.g. "X is congruent to 3, 7, or 11 mod some 19-digit prime"). You can't have a sound-and-complete inference for such a general form (see Gödel), but you can have plenty of very useful heuristics.

Existing type systems don't let you say, or the system infer, useful things about your values. Thus they form a layer of useless boilerplate (like requiring a BCPL programmer to declare every variable "machine word").

I claim that the inference machinery necessary for any given level of type safety could have been more usefully employed as a language feature that would make whatever manipulation it was checking, unnecessary to program in the first place.

Consider for example Andy Koenig's "ML type inference anecdote" which I presume is familiar to this audience. He forgot a termination test in a sort routine and the type inferencer essentially figured out the program could never terminate.

What it did instead of saying "Your program recurses infinitely", though, was to label his function a wierd type, from which after some head-scratching he was able to deduce meant that, yes, it would recurse infinitely.

My claim is that the same amount of inferencing smarts in the compiler would allow it to supply the termination test automatically, if it had been designed with that in mind.

Josh

A major problem with algebraic types, however, is that having the ability to do sound-and-complete inference with them has stunted language developers' desire to experiment with more useful specifications of the values a variable might contain (e.g. "X is congruent to 3, 7, or 11 mod some 19-digit prime"). You can't have a sound-and-complete inference for such a general form (see Gödel), but you can have plenty of very useful heuristics.

Just Monday, I demonstrated to my students how to do something like this. Well, actually, I demonstrated something weaker (in OCaml), but still pertinent: how to add an abstract data type for sorted lists so as to allow safer writing of sorting code. The verification combines compile-time checking (you can't accidentally concatenate a non-sorted list and a sorted list without manual conversion) and assert-time testing (claiming that a list is sorted requires verifying that the list is indeed sorted).

Okay, I grant you, this isn't purely fp thinking, nor purely static thinking. But I believe it's still an interesting approach. And this kind of approach is quite easy with OCaml.

My claim is that the same amount of inferencing smarts in the compiler would allow it to supply the termination test automatically, if it had been designed with that in mind.

It's an interesting point. However, there are numerous cases in which 'a -> 'b is a valid type. Here are a few :

• marshalling
• exceptions
• daemons and other "main loop" constructs.

So I doubt a one-size-fits-all heuristics would, well, fit.

My mindset can be summed up as

"Type inference is just a special case of partial evaluation."

I think your sorted-list predicate is a splendid example of the kind of thing I'm thinking of.

You can construct complex numbers, ultimately, from raw set theory. Similarly you could probably get close to describing many of the desired attributes of a program with algebraic types if you work hard enough. But you don't hand set theory to someone trying to do quantum mechanics and say, "This is in theory capable of doing all the calculations you need." Similarly, meta-reasoning and analysis of programs for real-world applications need to be couched in terms much closer to the actual concerns of the programmer.

Low-level type theory is great for academic theory (and will likely be needed to implement the kind of thing I'd like to see), but the OP asked about widespread adoption of the languages...

Josh

There is a type system that subsumes any specific inference you could name. The paper Sets in Types, Types in Sets demonstrates that the Calculus of Inductive Constructions has more or less the same logical strength as set theory (give or take some inaccessible cardinals). Of course Gödel still applies, but matching the power of set theory (as the cabal would have it) is pretty good. What language feature could eliminate the need for any manipulations checkable with set theory?

For a great example of using a type system to check interesting things, see Adam Chlipala's work on certified program verifiers, where the Coq type system essentially provides an analysis checking that one of his verifiers will e.g. only accept a chunk of x86 instructions if they actually are a program with some safety properties (being a well-behaved browser plugin, for example). Even without the full power of dependent types it's often at least possible to use types to amplify a little bit of manual reasoning about the contents of a module to some nice guarantees about a whole program, e.g. Tom Moertel's blog post about a solution to the "strings problem", or indeed the LCF approach for which ML was invented.

Similarly, I believe a programmer would welcome the advent of "sophisticated enough" automatic theorem proving capability, that this technology could be deployed in a production programming language to help establish correctness.

I'm not sure this is true - or at least, it doesn't seem to have worked out in general. There exist systems that provide "sophisticated enough" theorem proving for production languages. Specifically I'm thinking of JML with ESC/Java2 (for Java), and Spec# (for C#). While these have been welcomed by some programmers I don't think they've gotten any wider adoption than, say, FP. Perhaps pragmatic systems like this will eventually gain wider acceptance (they're both still young), but in general the contract based system they use seem no more acceptable to the "average programmer" than using functional languages.

Most younger languages are influenced by older. I hope we can agree on this.
APL influenced a few languages which are still used. Among those: A+, k and q, all written by arthur withney.
So, saying that APL is dead is partially wrong and partially true.

I've had the "it just works" experience with ML, but I'm always hesitant to make claims about the type system catching these errors. For example, what if you said "value * 4" when you meant "value * 8". That could cause a crash, too, depending on what happens with those values (they're fed to the engine, etc.), and it's perfectly type-safe.

James Hague: I've had the "it just works" experience with ML, but I'm always hesitant to make claims about the type system catching these errors. For example, what if you said "value * 4" when you meant "value * 8". That could cause a crash, too, depending on what happens with those values (they're fed to the engine, etc.), and it's perfectly type-safe.

Unless the type of the context expecting the result of "value * 4" is expecting a value of a type constrained in such a way that "value * 4" is of that type and "value * 8" isn't. It's true that passing integers or strings around willy-nilly is a good way to run into trouble; it's also true that SML, O'Caml, and Haskell support several ways of avoiding that kind of trouble; see Lightweight Static Capabilitites for further discussion, and Martin Jambon's Opaque module for one implementation of type-differentiated ints/strings.

I think there's a valid general criticism of many of us in the ML/Haskell communities, though, that we aren't clear enough that when we say ML/Haskell can avoid these problems, we're talking about fairly involved "typeful programming," vs. what you get "for free" just by programming in ML/Haskell. Yes, you really can have array-in-bounds etc. code statically in ML or Haskell... but you do have to do some work to get it.

For example, what if you said "value * 4" when you meant "value * 8".

I suppose this is getting offtopic, (being related to a previous post), but I wonder if anyone has studied which problem domains have a higher prevalence of magic numbers, and if this correlates with bug density at all.

Osprey issues an error that the unit of the return value (meter) does not match the unit of x*1682 (meter*1.045). Indeed, unit factor for converting mile to meter is around 1609.344, but the code above uses 1682 instead. The ability to discover incorrect unit conversion factors is a distinctive feature of Osprey. To the best of our knowledge, no other tool has this capability.

Damn right. In the case mentioned, it was pure stupid system design that caused the problem. What genius decided that the operation of the navigational system should depend on the local expression of time, instead of, say, Universal time (or a hardware clock)? (The planes crossed the international date line, and all their nav systems went out; they had to visually follow their tankers back to base.)

Type systems often enforce bad programming practices as well as making the programmer's job harder. Here's a case I was just tangling with: in Ocamlyacc, the tokenizer is passed in to the parser as a function along with the stateful buffer object it is reading from. My application requires reading the whole buffer and preconditioning it, keeping the tokens as a list. I should be able to give the parser a "pop" function as the token reader and the list as the stateful object, but no, the parser is written to require an object of type "lexbuf" as the stateful thing. So I have to introduce a global mutable and write a pop function that uses it and ignores its lexbuf arg.

Josh

J Storrs Hall: Type systems often enforce bad programming practices as well as making the programmer's job harder. Here's a case I was just tangling with: in Ocamlyacc...

I can't help but wonder if your problem isn't with the design of OCamlYacc rather than static types. Are you familiar with dypgen, ocaml-packrat, the parser combinators from OCNAE, or the ostap parser combinators?. Since all of these are in O'Caml, they're all statically typed, but particularly with the combinator libraries, it seems more than likely that you could implement the behavior that you want.

The upshot, I think, is that finite-state automata-based parsing, hopefully to no one's surprise, is a poor fit for a functional language—even one with explicit state such as O'Caml, because design decisions about what entities own what state almost invariably percolate up to the API. With a good combinator library, or perhaps by taking advantage of the "G" in a GLR parser generator, you can avoid suffering from the overcommitments of the parser generator. Types, or the lack thereof, really have nothing to do with it, IMHO.

I think it's clear that there is an infelicity with the design of OCamlYacc, and I'd guess that it was copied directly from Yacc and/or Bison. Definitely not what I'd call a design in the functional paradigm...

A couple of points: first, to get back to the question of why people don't use functional programming, the alternatives you mention are probably better and/or more congenial to the FP mindset, but Ocamllex and Ocamlyacc are in the main OCaml manual and the others aren't. OCaml itself is actually a neat, powerful, concise language with a very good compiler, producing code that rivals C++. If any functional language should be threatening the standard imperative ones, it should. But the experience of building something in OCaml is a lot like being a contestant on Junkyard Wars, because of the state of the documentation. About half of the info I've needed so far has been found in google searches for code, or from helpful suggestions on bulletin boards like this (and thanks!).

The other point is that OCaml, and this carries over to the other functional languages, is a lot more language and a lot less function. The programmer-oriented languages of yesteryear, such as APL and SNOBOL, had simple syntax, simple but general datatypes, and a rich, powerful function set that allowed for easily composed operations. Today's bigger, more complex languages have poorer, less composable function sets (more functions, but too many datatypes, with no interoperability). People expect to build a basic language and then have libraries add on the functionality -- but this leaves the design of the functionality, to my mind the more important part, up to chance.

Which of these books do you own: An English dictionary; an English grammar? If both, which do you use more often?

Josh

Type systems often enforce bad programming practices as well as making the programmer's job harder.

I can see the latter under some circumstances, but the former I don't buy. Care to give an example?

In any case, "often" seems to be a wild exaggeration.

the parser is written to require an object of type "lexbuf" as the stateful thing

I fail to see how this has anything to do with types. In absence of a type system you could not pass a pop function either when the parser expects a record-like buffer structure. You just wouldn't find out before you run it, and probably be confronted with incomprehensible runtime errors raised by generated code.

Type systems often enforce bad programming practices as well as making the programmer's job harder.

I can see the latter under some circumstances, but the former I don't buy. Care to give an example?

I thought that was an example. It's not generally a good idea to use global mutable references if you can avoid it.

I fail to see how this has anything to do with types.

If I'm understanding what's going on, OCamlYacc is primarily handing the lexbuf to the token function at each invocation, relying on the token function to update it. It doesn't actually manipulate it.

The reason this has to do with types is that the reason the lexbuf argument isn't completely polymorphic is probably that OCY dips into it somewhere deep inside, in the error locating code or something. If the language were dynamically typed, ordinary usage would never hit this, and I could hand OCY my list ref as the lexbuf parameter, and all would be fine. I'm catching errors and handling them myself anyway.

BTW, it wouldn't be all that hard to have designed OCY to take a closure instead of handling the state explicitly, and maybe also a function to call with errors or whatnot. But it wasn't. One has to evaluate type systems, as well as functional programming as a whole, in the real world where systems are misdesigned more often than not, legacy subsystems are ported and hammer-fit to the new language (some of the OCY docs still refer to it as "Bison" ... hmmm...), module/build systems are finicky to dependencies and brittle as hell, etc ad nauseum.

Josh

I thought that was an example. It's not generally a good idea to use global mutable references if you can avoid it.

I agree, but I don't see the connection to types.

The reason this has to do with types is that the reason the lexbuf argument isn't completely polymorphic is probably that OCY dips into it somewhere deep inside, in the error locating code or something. If the language were dynamically typed, ordinary usage would never hit this, and I could hand OCY my list ref as the lexbuf parameter, and all would be fine. I'm catching errors and handling them myself anyway.

Now you've given a perfect argument why not to use untyped languages - there might be programmers like you around that fiddle with abstractions, are seduced to breaking them, and because the language lets them and the result seems to work in "ordinary usage", they think it's perfectly fine. ;-)

If the parser did not rely on a certain argument type then it would indeed be polymorphic. But it isn't. Unless the developers were stupid (which I consider highly unlikely in this case), there is a reason. It uses it for something. Because the parser is an abstraction, you should not make any assumptions about this use - short of understanding its implementation in detail you might be wrong. Or it might change in the next version. Murphy's law tells you that the unforeseen will happen, when you least expect it. That is, probably at your customer's site.

Types don't solve this problem in general, but used carefully, they can avoid quite a substantial bit of it. In this case, contrary to what you seem to be thinking, they successfully prevented bad programming practice on your side.

Edit: Sorry for the slightly sarcastic tone. I hope I did not sound too offensive.

... if you read my comments above, you'll note I opined that type inference was a wonderful thing, and that the hitch that was forming an entry barrier to FP was type declarations a la Haskell. OCaml doesn't require them, so it doesn't fall under my critique anyway.

For the specific case of OCamlYacc, I insist that the misfeature is in the design of OCamlYacc, (and people have been saying so since 1999).

My personal experience is that type inference doesn't particularly affect the code I write, but does influence the amount of testing I do (for the worse). It's a lot harder to write half a function and test it on the one case you've implemented. Thus you tend to try to write the whole thing "dry", and rely on the compiler/inference rather than actual run-testing each case as you write it. It remains to be seen which actually catches more bugs. --but this has wandered off the point of why people don't use FP. It's clear that anyone who has spent any time fighting the hideous gackfulness of C++ isn't going to be put off by Haskell or Ocaml.

Josh

I opined that type inference was a wonderful thing, and that the hitch that was forming an entry barrier to FP was type declarations a la Haskell.

Are you thinking of the type declarations necessary in Haskell for polymorphically recursive functions? Or something else? Is it possible to write the code below in O'Caml?

data Twist a b = Cons a (Twist b a) | Nil

len :: Twist a b -> Integer
len Nil = 0
len (Cons x xs) = 1 + (len xs)

list = Cons 1.0 (Cons "abc" (Cons 2.0 Nil))

main = print (len list)

Maybe you could provide a code snippet as an example of what you mean by "type declarations a la Haskell" "forming an entry barrier to FP".

Here's how I'd like to code that example:

list <- 1 "abc" 2
len list


all that other stuff is useless boilerplate. It's crazy to have to write a whole new version of "length" for each new pattern of contents of a list. There should be a type "list" that doesn't care what the contents are, as there are plenty of operations on lists that don't depend on the types of the elements.

Type checkers are a bit like spelling checkers for natural language text. If you're a serious writer you don't tend to misspell that many words; a checker is a minor, not a major, help.

However, as I mentioned, I'm coming to the conclusion after this discussion that declarations are not the major entry barrier to FP for the general run of programmers; they're just an entry barrier to me for some FP languages.

I do continue to feel, however, that the tendency in the academic world to conflate FP and type systems is a detriment. I'd point out that Scheme is far and away the most popular FP language, closer on a log scale to the mainstream than to the other FP languages. If you're wary about Google refs as an indicator, look at the number of implementations.

If people in the FP world want to increase the usage of functional languages -- and it's not necessarily obvious that this should be a priority -- they should (IMHO)

• Define a simple FP language with a usable core that can be learned in a day. This means less than ten new concepts, including both syntax and semantics!
• Provide a good interpreter/IDE for debugging and compilers for several architectures that produce code competitive with C. In particular the code produced for functional constructs (e.g. closures) should not have any performance penalty.
• Write a good manual/textbook (e.g. SICP).
• Get a few major universities to use it in intro programming courses.

Josh

... why isn't this O'Caml? I was certainly productive with it on my first day of use. Indeed, one of the things that I appreciate about it is that it's deceptively like other functional/imperative/object languages, except that when you want to do genuinely tough stuff, you can, at points where the other languages tend to break down. Jason Hickey at CalTech has written a very nice tutorial for it, and when you're ready for the rabbit hole, there's stuff like Code reuse through polymorphic variants; delimited continuations; monads, complete with do-style notation; dynamically-scoped variables; resumable exceptions; etc. And that's just in O'Caml, without appealing to MetaOCaml, Flow Caml, GCaml...

Those of us who are interested in static type systems are interested in proving properties of our programs before they are released into the wild. We're trying to make those proofs cheaper by making them possible to do by "ordinary compilers." I think it's interesting that there's another move afoot tackling the issues from the other direction, as described here: maybe some of the really good proof assistants with extraction, such as Coq, are already useful to programmers.

Finally, of course, the really exciting stuff is happening around dependent types, abstract interpretation, multi-stage programming, online partial evaluation, etc. where the concepts of "compile-time" and "runtime," let alone "static type" and "dynamic type," get quite blurry. I remain convinced that we can all have our cake and eat it, too, but clearly there's a lot of research and development yet to be done. In the meantime, reasonable people (which I am not) can reasonably disagree as to where to focus their energies. The rest of us can continue to be partisan fanatics. :-)

From Paul Snively's "Road to Lisp Survey":
"Thankfully, Scheme is a sufficiently small, simple dialect that a non-toy implementation would run on my trusty [TRS-80]."

In all sooth, I was thinking of OCaml and Scheme when I wrote that plan for Functional Programming World Domination. I think that each one covers (a different) 80% of the desiderata. The specific places where OCaml falls short are the complexity of its syntax, the overabundance of types, the complexity and brittleness of the build system, and the fact that all the documentation is in French (just kidding on that last).

As has been mentioned, Scheme could be called a mainstream language without too much of a stretch. What's your sense of whether OCaml is gaining ground? I can't make an objective estimate myself, since I've recently been looking for OCaml info which skews the amount of it I see...

Thanks greatly for the pointers; very useful.

Josh

...that the answers would be along these lines. I'm the wrong guy to ask about O'Caml gaining ground precisely because I'm one of the local O'Caml zealots. Re: syntax, I'm curious as to what you think of the "Revised" syntax. Personally, I think that designing a "simple" syntax for a combined functional/imperative/object language is an interesting challenge; given that, I'm equally curious what you think of Oz.

Also, what build system are you referring to? FindLib? GODI? OMakefile? omake? I really like omake!

Having said all of that, sure, it'd be nice to have a small, simply, regular language like Scheme but with an expressive type system that's fully inferred everywhere. Unfortunately, I strongly suspect that such a beast is impossible—at least until we've gotten farther down the abstract interpretation/multi-stage programming road.

Re: syntax, I'm curious as to what you think of the "Revised" syntax. Personally, I think that designing a "simple" syntax for a combined functional/imperative/object language is an interesting challenge; given that, I'm equally curious what you think of Oz.

I haven't tried the revised OCaml syntax, but I'm finding the old one surprisingly usable. (Surprisingly in the sense that the BNF makes it look overcomplicated, but in practice it's easy to read, the precedences tend to do what you expect, etc.) This is one of the areas where design of a language is a lot more art than science, IMHO.

Oz is very nice but it's moving in a different direction than I'm trying to go, so I haven't spent too much time with it. In particular, the design I'm working on is purely functional and thus expression- rather than statement-oriented. So I can't say much about Oz.

One thing I do feel has great potential is 2D syntax. Haskell gets points for this; I'm a bit surprised more ML-derived languages don't have it, since Landin had it in ISWIM in 1966.

Also, what build system are you referring to? FindLib? GODI? OMakefile? omake? I really like omake!

Just regular vanilla make...

Josh

One thing I do feel has great potential is 2D syntax. Haskell gets points for this; I'm a bit surprised more ML-derived languages don't have it, since Landin had it in ISWIM in 1966.

True, but ISWIM was never actually implemented. And I'd guess that that the technical issues with off-sides rules (trickier lexing/parsing, the whole space/tab issue, and so one) probably presented enough of an annoyance to the implementers of languages like ML that it outweighed the benefit of including it (plus there's the whole "it's just syntax" so it can't be that important aspect).

Still, it is available for OCaml these days in a bolt-on form via The whitespace thing.

Just regular vanilla make...

Durak and Pouillard talk a bit about these issues in an appendix of the user's guide for ocamlbuild, an ocaml-centric build system that'll be rolled out with the next release (in beta as iI type this).

I do continue to feel, however, that the tendency in the academic world to conflate FP and type systems is a detriment. I'd point out that Scheme is far and away the most popular FP language, closer on a log scale to the mainstream than to the other FP languages.

Err, aren't you contradicting yourself? Scheme is very popular in academia. You seem to have this boogey-man view of type systems, ignoring all the untyped work that goes on in academia. It's a big tent. Lots of people find static, comprehensive types useful. Lots of people do not. This has been debated to death on LtU. Perhaps you can review the many, many threads that have already taken place instead of rehashing?

Err, aren't you contradicting yourself? Scheme is very popular in academia.

Certainly -- that'e exactly what I was saying. And yet -- getting back to the OP once again -- there is a tendency in the theory community to conflate "functional programming" and "type systems." If the original poster were thinking of Scheme, I don't think the topic would have been named "Why don't people use functional programming," because, as I pointed out, Scheme is used widely enough to be considered a mainstream language.

Josh

ps -- I don't have a boogey-man view of type systems, I have a boogey-man view of academia :^) ... There is a strong tendency to complexify for complexity's sake.

"[P]ublicly expressed beliefs advertise the intellectual virtuosity of the belief-holder, creating an incentive to craft clever and extravagant beliefs rather than just true ones. This explains much of what goes on in academia."
--Steven Pinker, So How Does the Mind Work?

Scheme is used widely enough to be considered a mainstream language.

I don't see that. It's mainly used in academia, which is why I think that statements like "the tendency in the academic world to conflate FP and type systems" is just plain wrong. You are conflating FP and types systems, not academia. You are focused on functional languages like Haskell, and then ignore languages like Scheme. They are both academic languages.

I don't have a boogey-man view of type systems, I have a boogey-man view of academia :^) ... There is a strong tendency to complexify for complexity's sake.

Obviously the people who work on or use such type systems don't agree, and this just comes back to the same old debate. There's no need to rehash it. Not so long ago arguments like this were bogging down LtU, which led to a written policy. Since then things have been pretty quiet on the debates best left for comp.lang.misc or Slashdot. Your profile says you've been registered only for six weeks. Welcome aboard, but keep in mind LtU isn't really about functional programming advocacy or continued debates on the merit of strong/static typing. A search of "dynamic typing" on LtU will show that it's all been said before.

• Why type systems are interesting
• Why type systems are interesting - part II
• Why type systems are interesting - part III: latent types
• Static Typing Where Possible, Dynamic Typing When Needed
• Weak vs. strong typing
• Advantages of Soft Typing
• On the Revival of Dynamic Languages

LtU isn't really about functional programming advocacy or continued debates on the merit of strong/static typing. A search of "dynamic typing" on LtU will show that it's all been said before.

I think Mr. Nowakowski is reading something into my remarks that I never said. I have specifically stated that I think type declarations have a valuable place, and that type systems are useful.

I have been trying to analyze the question of "Why people don't use functional programming?" in view of the fact that Scheme appears to have an order of magnitude more usage than other functional languages. Note the term "usage", which is not the same as "worth" or "value" or "goodness" but is specifically the question in the topic title. A second piece of suggestive supporting evidence for the hypothesis that dynamic typing may have something to do with rates of popularity lies in the fact that scripting languages had such a strong showing in my informal survey.

Other people here have made thoughtful, informative, and responsive comments, with pointers to available systems and the literature, which have illuminated the issues. Kudos to them.

For the record, I'm a strong proponent of functional programming: I was the first person to give a talk on the subject at Rutgers, in 1978 (about Backus' FP, of course). I'm keenly interested in the question of why it hasn't taken the world by storm in the meantime.

I have some ideas on how type systems could be improved, and they are not merely opinions, but form the basis of my full-time research effort at the present. I've found the discussion here quite helpful, and if I've occasionally phrased my remarks in such a way as to provoke someone into including nine references in a single response, I consider myself to have struck gold.

Josh

The fact that Scheme is a comparatively old language derived from one of the oldest languages still to be in regular use today may have a lot to do with it. The ML family and Haskell just have not been usable in the same way for anywhere near as long, and that has impact.

As much as I'd like to keep quiet and just accept this new Google-found mainstreamness of Scheme, I feel compelled to note that Scheme is really easy to implement, at least up to a point that's usable in a real project. That's a big reason that there are so many implementations, and also why it's used as a scripting language in various projects, which in turn is a big part of any relative prominence it enjoys.

So there's an obvious adoption benefit, in certain areas, to the simplicity of a small yet powerful untyped language with a small standard library (cf. Lua). But that only takes you so far. Monster.com isn't filled with ads for Scheme programmers, for example.

Point, I'd been half meaning to mention this as well. Certainly I don't see Scheme as particularly mainstream, and Lua seems to've won out for scripting purposes in the fields I'm familiar with.

Scheme isn't quite small enough that I personally would knock one up in a day, but it's not far off it and I certainly wouldn't be daunted if asked to implement one... implementing a small un/dynamically-typed haskell- or ML-like language isn't necessarily that tough either though, and parser aside it can arguably be less work.

The fact that Scheme is a comparatively old language derived from one of the oldest languages still to be in regular use today may have a lot to do with it. The ML family and Haskell just have not been usable in the same way for anywhere near as long, and that has impact.

A reasonable hypothesis that deserves some consideration. I would note, in dissention, that ML appeared in 1973 with roots going back to Landin 1966 and Scheme only in 1977. It might be supposed that the greater popularity of Lisp in the 70s contributed to Scheme's user base, but I'm not sure. I was a Lisp user through the 80s and I never used Scheme until the 90s.

In the 70s, C was a boutique Bell Labs language -- more people used SNOBOL. Most serious systems work was done in assembler. Fortran was used for science/numerical, and Cobol for most business applications.

ML had just as legitimate a shot at being the next language of choice as any.

Josh

Lisp's greater popularity will have contributed to more than just the user base - Scheme was born ready to rock, with a significantly richer heritage in ways of getting things done. The statically-typed languages have been significantly more dependant on research providing ways of getting more things done, with Haskell in particular only recently having hit a sufficient level of usability - I'm sure present-day MLers can point to plenty of developments involving types in the 80s and 90s that they consider necessary to their day-to-day coding as well.

I don't see why a strict non-pure ML couldn't have copied the greater part of Lisp's pragmatic repertoire in a very direct transliteration. The main thing Lisp had going for it was a very debugging-friendly interpreter, in many implementations, with program inspection and analysis features that didn't show up in other IDEs for decades. The Lisp tradition of having program = data significantly enhanced the ease with which this was done...

Josh

ps -- the subject line is a reference to

(bruce string-stream)


The consequence of adding Lisp-style program=data when ML was born would've been to surrender the idea that well-typed programs don't go wrong. It would've negated ML's very reason for being! I agree entirely that this was very much a point in Lisp's favour - it's taken strongly statically typed languages decades to reach a point of being nearly as flexible in that regard, though in doing so they become in a number of ways more powerful than a lisp.

The consequence of adding Lisp-style program=data when ML was born would've been to surrender the idea that well-typed programs don't go wrong. It would've negated ML's very reason for being!

As I understand it, the "meta-ness" of ML, from ISWIM, was that it was to be a unified framework for a family of specific application-oriented languages (hence "the next 700 programming languages"). I should have thought that a family member oriented to the description and manipulation of programs would have been right up its alley.

In fact Landin states: "ISWIM can be looked on as an attempt to deliver Lisp from its eponymous commitment to lists, its reputation for hand-to-mouth garbage collection, the hardware dependent flavor of its pedagogy, its heavy bracketing, and its compromises with tradition."

The development of ML per se by Milner & co. as a vehicle for a theorem prover for a typed lambda calculus for reasoning about programs had a longer self-referential loop than eval/apply, but one that was just as fundamental to the enterprise.

Josh

...didn't really arrive until MetaML hit the scene, and arguably no one knew about it until MetaOCaml started getting attention. .<...>. and .~... give you your parameterized code-as-data type, e.g. "int code" for a fragment returning an int, and .! executes these code blocks, and it's all statically typed. It's pretty tricky to get this stuff right, and certainly wasn't being done in the 1970s. In other words, there's more to typeful program=data than having a REPL.

MetaOCaml is pretty cool (he says after spending several hours reading up on it...) The question is to what extent has it been used to write the kind of programmer's toyboxes seen on the Lisp machines of the 80s?

I haven't gotten to it deeply enough to be sure yet, but at first blush the code, splice, and eval constructs (with their associated types) seem to mesh with functions a lot better than simple macros do. One of my big gripes about Lisp was that you'd try to use a higher-order function (e.g. map) with something and only then would you find out the something was a macro and couldn't be used that way.
Too much ball of mud, not enough diamond.

Josh

...but I think the building blocks are beginning to fall into place, e.g. Oleg Kiselyov's Generic Printer for MetaOCaml. But we're really off-topic now; if you'd like to discuss this offline, please feel free to e-mail me at psnively-at-mac-dot-com.

I always wondered about that. As macros are evaluated att compiletime why would you need to type check them before they are evaluated? Cant you just apply the macros and typecheck the results? Its still att compile time.

error messages would likely be completely incomprehensible.

In the 70s, C was a boutique Bell Labs language -- more people used SNOBOL. Most serious systems work was done in assembler. Fortran was used for science/numerical, and Cobol for most business applications.

ML had just as legitimate a shot at being the next language of choice as any.

That overlooks an enormous amount of relevant context. Just one example would be the state of automatic garbage collection in the '70s. ML didn't even remotely have "just as legitimate a shot" as C at that time. C won out because it's a simple, close-to-the-machine model, essentially an incremental step up from assembler, that doesn't introduce any abstractions that don't have straightforward translations into native code.

The big barrier to adoption for FP is that most programmers learn programming in terms of an idealized physical machine, that is inherently imperative. Abstractions that don't map neatly and obviously to this Turing / Von Neumannish machine model are more difficult for programmers to reason about than would be the case if they used a less arbitrarily physical mental model.

It's as if we tried to teach math in terms of the operation of an abacus, mapping our understanding of numbers onto beads. At a certain level, such as simple arithmetic, this is a useful mapping, quite fundamental to the meaning of numbers, but for most purposes it's completely irrelevant to the problems being solved.

When your only mental model is that of the abacus, there's a limit to the higher math you're going to be able to learn or perform. It's necessary to abstract beyond that level, and forget about the beads. That's why in an aside in another comment, I suggested that lambda calculus needs to be taught at the high school level, alongside algebra which also relies on substitution. Until that kind of abstraction is basic knowledge that everyone (who needs to) can rely on, weaning people off their machine models is going to be an uphill battle.

The reason paradigm shifts are both difficult and enlightening is that before you can truly understand a language that depends on a new paradigm, you have to internalize the paradigm's model. The usual model for the imperative paradigm is the machine mentioned above. The model for the functional paradigm is a generalization of the lambda calculus. While the latter model has some very clever and efficient translations to the machine, those translations are not very effective ways of grasping the paradigm -- no-one tries to teach functional programming in terms of compilation through CPS, for example.

The shift to functional languages requires letting go of the physical machine model, and embracing lambda abstractions as a primary mental model. That's never going to happen on a large scale as long as everything programmers are initially exposed to is imperative and machine-oriented, which of course is a catch-22. The way change will happen is the way it's already happening: because of pressure for greater expressiveness, language designers will slowly adopt abstractions which aren't easily explained or reasoned about in terms of the usual machine model. The machine model will start to become a more obvious detriment to reasoning about programs.

The results initially will be some sort of ungodly functional/imperative/OO hybrid, as we already see with C# and to a lesser extent, Java. A similar hybridization is happening with languages like OCaml, Scala, Oz, and (in the major implementations) Scheme. As these languages converge in terms of gross features, the languages from the academic side will start to seem more ordinary, relative to the mainstream languages, and they'll become an easier sell.

This general pattern, of focusing on machine models first, goes all the way back to Turing and Church at Princeton in the 1930s. The whole of computer science originally jumped on the Turing machine as a model of computation, even though the lambda calculus was proven early on to be equivalent. The Turing machine seemed more relevant partly because of the physical analogy to real machines. That analogy was useful for the purposes of reasoning about "effective procedures", for example, for the purpose of the Church-Turing thesis. But very little of the theoretical development around programming languages used the Turing machine, because it just wasn't effective. The obsession with machine models is just a childhood phase in the development of thinking about computation -- machine models are security blankets, and separating from them creates anxiety.

That overlooks an enormous amount of relevant context. Just one example would be the state of automatic garbage collection in the '70s. ML didn't even remotely have "just as legitimate a shot" as C at that time. C won out because it's a simple, close-to-the-machine model, essentially an incremental step up from assembler, that doesn't introduce any abstractions that don't have straightforward translations into native code.

C and ML weren't competing for the same niche. C, as you point out, was basically a portable assembly language. It is a source of continuing amazement to me that C went on to become the general purpose language it did. There's presumably some evolutionary phenomenon at work. (My notion that FP ought to have a have a horse in the race that's simple but fast, suitable for embedded and systems work, is based partly on this.)

ML was competing with Lisp, APL, SNOBOL, and so forth. There's no reason its storage management couldn't have been as good; without evidence to the contrary, I'd assume it was. It should have been faster, actually, given the static typing. The inferencing in the compiler should not have been a major speed problem, either -- Prologs of the day were quite competitive with Lisps in execution speed.

It wasn't really a question of machine-oriented paradigms, I don't think. There were lots of languages out there based on mathematical abstractions, ranging from APL to Prolog. Relational algebra took over the database world from a much more machine-oriented mindset. There was a thriving automatic programming community with strong links to the theorem-proving community. And of course Lisp itself was very protean, readily being used in recursive, functional styles as well as meta-programming styles where programs created new programs.

I'd say that on a percentage basis, CS departments in the 70s were less machine-model oriented than they are now, because most CS people were transplantees from some other field, typically math (I was), whereas today most are from a pure CS background.

As far as I can tell, the main reason ML didn't take over from Lisp was that it didn't have a community that was using it as a vehicle (as Lisp had AI) and thus feeding back requirements (and money!) into the development process. There were even companies building Lisp-specific machines. [Personal note -- during the 80s I consulted with ITT Labs on a project to build an APL machine, complete with data-parallel processor based on the ICL DAP, to compete in that market, but our pig didn't have enough wings...]

Josh

It is a source of continuing amazement to me that C went on to become the general purpose language it did. There's presumably some evolutionary phenomenon at work.

I'm conjecturing that the phenomenon in question is the one I described in the grandparent comment. You're right that were lots of languages based on mathematical abstractions, but no such general purpose language thrived in industry, because industry wasn't ready to move away from the machine model. The only exception was certain constrained cases such as relational databases, where the more abstract functionality was constrained to a specific subsystem.

By "machine model", I don't just mean C's closeness to memory locations etc., but also the entire imperative paradigm embodied by the Turing machine, which underlies even much higher-level languages. That's limiting as a primary model for programming languages, and its wide influence has inhibited the adoption of languages that provide different kinds of abstractions.

As far as I can tell, the main reason ML didn't take over from Lisp was that it didn't have a community that was using it as a vehicle (as Lisp had AI) and thus feeding back requirements (and money!) into the development process.

It has type theory now. :)

It is a source of continuing amazement to me that C went on to become the general purpose language it did.

C had UNIX to push it into popularity and into the general purpose realm. UNIX was C's killer application. Ruby is getting a similar push now via Rails.

The other item I see on this whole debate is the machines we had in college. I went to University of North Dakota and graduated in 1991. The programming languages were limited to what the IBM mainframe and the VAX could run. Lisp crushed the VAX (I was told it was the poor quality of the implementation taking so much RAM (5megs per instance on a 4 meg machine)). Most courses were Modula-2 (switching from Pascal) and C with Ada used for the software engineering class. I really believe that UND was not alone in having machine limitations directing teaching. PC use for programming was just being phased in. I learned about Lisp, Scheme, etc. but really didn't get to experience them to the fullest.

ps -- I don't have a boogey-man view of type systems, I have a boogey-man view of academia :^) ... There is a strong tendency to complexify for complexity's sake.

Academia's a big place. The simple and useful theories are out there, and you don't even have to look very hard for them. If you look for something to criticize, you can certainly find it. But if you're going to criticize, at least make it interesting and meaningful, which means you have to be a lot more specific than "strong tendency to complexity", etc. (The LtU policies have more on this subject, particularly point 4.)

In the PLT field, there's significant inherent complexity. In my experience, PLT really helps in dealing with that complexity, in the "real world". The perception of unnecessary complexity can have at least two explanations: you've given one, but the other is simply that before one has understood something, it often seems unnecessarily complex. My counter to the Pinker meta-point is that people use all sorts of excuses to justify not investing the effort to learn about something. And unfortunately, the only way you can tell whether something does in fact have unnecessary complexity is by learning about it. Having done that, if you really do find unnecessary complexity, well heck, publish a paper giving your simpler approach, and a lot of people are going to appreciate it.

On the subject of type systems, there's a lot of emphasis on them because they deal with the static properties of programs. If you're an ordinary programmer, you can certainly get away with just reasoning intuitively about those properties, so you don't even need a language with a non-trivial type system. But if you're studying programming languages, you can't get away with that.

The importance of type systems goes beyond programming languages, into mathematical logic, proof theory, etc. Girard discovered System F as a second-order logic while Reynolds discovered it independently as polymorphic lambda calculus. Part of the reason that type theory is a big field is that it's not just concerned with programming languages. Of course, programmers are egotistical, and tend to imagine that everything going on in computing science should be about them, so it's a little confusing to come across a discipline so closely related to programming languages that would still be almost as interesting if programming languages didn't exist.

Which also has a lot to do with why functional languages haven't taken over the world. The fact that all this theory has produced some amazingly powerful programming languages is a kind of predictable side effect of the theory. Adapting those languages to consumption by average humans, many of whom insist that they don't actually want to crack open a user manual, let alone a textbook, is not the core problem of PLT, and nor should it be.

That's not to say that that problem shouldn't be addressed, but it needs to be addressed at a different level (e.g. teaching elementary lambda calculus alongside algebra in high school...) The fault doesn't lie with the theories that have been developed. One can certainly make the case that there are important theories of a different nature that haven't yet been developed, that need to be, but that work has to be done by people who are interested in and suited to doing it. There are some pretty giant shoulders out there waiting to be stood on. The next step is up to us.

Apologies for violating the policies with a mild rant. :)

There should be a type "list" that doesn't care what the contents are

{-# OPTIONS -fglasgow-exts #-} 

data Any = forall a. A a
foo = [A 1, A "string", A 2.0, A sqrt, A foo, A [1,2,3]]

main = do print $ map length [ foo,
                               (tail foo),
                               (A 'x' : foo),
                               take 2 foo,
                               drop 3 foo,
                               foo ++ foo ]

as there are plenty of operations on lists that don't depend on the types of the elements.

A list like that doesn't seem all that useful. Maybe I'm missing some interesting operations?

as there are plenty of operations on lists that don't depend on the types of the elements.

A list like that doesn't seem all that useful. Maybe I'm missing some interesting operations?

From APL: compress, expand, indexing, rho (both monadic and dyadic), catenation, lamination. (In my vague recollection of the static analyses of my APL code of yesteryear, these account for more than half the instances of functions in my code.)

Assuming only an equality function which can take objects of any type, dyadic iota (search), member, scalar equality and inner and outer products using it. Nub from J.

Re the Haskell example: cool. can I write

foo = map A [1, "string", 2.0, sqrt, foo, [1,2,3]]

?

Josh

From APL: compress, expand, indexing, rho (both monadic and dyadic), catenation, lamination.

For that example, indexing is essentially worthless, since you don't know anything about the type of the element, and therefore can't use it for anything.

Re the Haskell example: cool. can I write

foo = map A [1, "string", 2.0, sqrt, foo, [1,2,3]]


No.

As for book recommendations, I liked The Haskell School of Expression, ML for the Working Programmer, and Types and Programming Languages.

For that example, indexing is essentially worthless, since you don't know anything about the type of the element, and therefore can't use it for anything.

Try writing an AI sometime. The essential operation of intelligence is taking formless data and inducing theories of structure about it. See for example Solomonoff on machine learning or Marcus Hutter's AIXI or the C-prize.

In a more pedestrian mode, consider a router, which is responsible for getting packets of data to the right place in the right order, but cares nothing about what they contain. There are many parts of operating systems and databases that have the same character.

I think there's probably some philosophical disconnect going on here. The reason I don't like Haskell is that I tried for a week to adapt a project into it, with no success. 90% of what I tangled with in that week was "gruesome boilerplate" -- a phrase I first saw in some of the Haskell sources describing the purpose of the file. In contrast, I've just spent a week porting my current project to OCaml, successfully (4 months Prolog programming --> 1 week OCaml, although it's not a fair comparison). About 1 day of that process accounted for boilerplate issues, and most of that had to do with Makefiles and OCaml's plethora of filetypes.

For what it's worth, I tried Haskell first...

Cheers,

Josh

I think there's probably some philosophical disconnect going on here.

Probably. I only gave the example of existential types as a concrete program that you could play with of a list of elements where we have absolutely no information about their types. Now if those elements have tags that describe the contents, or we know they're delimited chunks of 8 bit bytes , or there're made up of US-ASCII characters, that's a different story. I don't think anyone would be surprised by the relative lack of success of adapting an existing project to Haskell, with one week of experience under the belt.

Now if those elements have tags that describe the contents

To me, that seems to be the core of the criticism, that the values arent taged, so that you cant use any typecase like mechanism on them. The answer to that seems to be that the typing of typecase would require untaged union types. And that you cant implement them (untaged union types) efficiently.

But how about dependent types? If you add them to for example Haskell, wouldnt that make the existant patternmatching into a kind of typecase? How do you handle that?

GADTs effectively do this - pattern matching can refine a type. But you still have to define the datatype to start with - you still have tags.

Actually ... if you read my comments above, you'll note I opined that type inference was a wonderful thing, and that the hitch that was forming an entry barrier to FP was type declarations a la Haskell. OCaml doesn't require them, so it doesn't fall under my critique anyway.

I'm not sure what this is getting at, but Haskell does not require declarations for anything OCaml can do. Yes, Haskell's overloading requires type declarations, but OCaml can't do overloading (as such), so that's hardly a fair comparison.

The same goes for rank-n types.

It's a lot harder to write half a function and test it on the one case you've implemented.

A lot harder? `undefined' has type a in Haskell, and `fn () => raise Fail "undefined"' has type unit -> 'a in SML.

the hitch that was forming an entry barrier to FP was type declarations a la Haskell. OCaml doesn't require them

Mh, Haskell does not require type declarations any more than OCaml does, so I don't understand what you're getting at.

I insist that the misfeature is in the design of OCamlYacc

I agree, but still it is a bad idea to mess with the abstraction it is based on, no matter how decent it is. You cannot blame the type system for that.

It's clear that anyone who has spent any time fighting the hideous gackfulness of C++ isn't going to be put off by Haskell or Ocaml.

Actually, I'm not at all sure about this. People tend to just take the former for granted, and with enough tunnel vision often don't even realise how gackful it is - everybody is using it, so it is percepted as "normal".

Mh, Haskell does not require type declarations any more than OCaml does, so I don't understand what you're getting at.

I think he's getting at the use of extensible records and variants in place of predefined datatypes.

Since the actual bug has not been reported, this is pure speculation. I suspect that local time is not the problem as aircraft, especially military ones, always use Zulu time. Rather, I suspect that the geographical discontinuity across the International Date Line (-180 degrees to + 180 degrees) is the problem. I have seen this several times as programmers insist on working with latitude/longitude coordinates. Discontinuities are evil! It usually takes several attempts to get the special casing right (if ever) and until then, the geometry fails across that boundary. The real solution is to work with (x, y, z) coordinates and only use lat/long, MGRS, UTM, etc. for display purposes.

sounds like there should be a type "number mod X" where the wraparound, arithmetic, etc, happen automatically. I can think of lots of places it's be useful. Surely somebody's done it somewhere?

Josh

Ada does have modular types. This doesn't help this particular situation. For example, rate of distance change ('velocity') in degrees per second is dependent on direction of travel. By the time one has finished dealing with this, there are usually a bunch of independent ad-hoc implementations which effectively traverse through (x, y, z) coordinates. We are starting to get off topic here; however, this is really a number crunching issue combined with geometric proofs of validity. Fortran + Coq?

See here, and/or google "lightweight dependent types." This is a prime example of the "typeful programming" approach that I've written about elsewhere: a lot of us advocates of ML/Haskell—myself regrettably included—have been guilty of acting as if you get all of ML/Haskell's possible bennies "for free" just by using the language. Not only is it not true, but the realization that you don't necessarily need a full-on dependently-typed language and can actually do things like statically-guaranteed modular arithmetic today, in O'Caml or Haskell, is quite recent, and still fairly involved if your name isn't Oleg Kiselyov. :-)

Just choose the unit of angles to be 2pi/2^32 and use 32 bit words.

But that doesn't solve the problems. Given longitude and latitude developers may be tempted to compare pairs of positions using the usual real number comparison operators. If these numbers wrapped modulo 2pi, say, then there's the risk that users will compare x and y to get one result, and later compare x+epsilon and y+epsilon, say, expecting to get the same result. But they may get a different result because adding epsilon causes a wraparound in one of the variables. In a sense, this problem doesn't have a 'local' fix, and it needs a 'global' one, like working in 3D, or using a type that abstracts away completely from coordinates.

I sincerely think...

Unfortunately forum moderators can't tell what you think unless you tell them. But you only wrote one line and didn't give people an opportunity to judge your line of thought. That's a pity because I would have enjoyed reading a paragraph or so on how the right type system might have prevented this error.

Perhaps this issue is also related to a lack of exposure to FP (during university/college years)

I agree that teaching only Java is a crime, but I started with Scheme (Felleisen camp), and don't use any functional languages for serious work nowadays. For me it's a matter of libraries (Perl, Octave), domain specificity (Octave, Perl), raw performance (including memory footprint) (C, C++), and easy communication with colleagues (Octave). I still check out the Haskell, Lisp, and Scheme offerings from time to time, and am impressed by e.g. GSLHaskell elegance and Bigloo's tight C integration. However, the support isn't quite there yet, and I have only limited time for reimplementing existing functionality in a new language.

These things just take time and/or money. Functional languages aren't dying, so I see no great cause for concern.