Lambda the Ultimate

Java started because it was the only way to program applets. And because it had appeal to, once you had programmed an applet, you might also be thinking about doing something else with it.

Thus people went from C to C++ because C++ was a superset of C and they could always just fall back. And Java is so very close to C++, and OOP was already widly known when it came out. Python uses a different syntax but similar semantics, familiar to people who know OOP and have used DT PLs. And so on.

The problem with many FPLs, especially of the pure variety, as that they are just so different. And they require a whole new way of thinking. A good way but a new way. Thus experienced programmer end up feeling stupid when first they use them, and most people don't like feeling stupid, so they blame the PL instead.

Another issue is that, unlike people on this board, most programmers don't switch PLs because it's fun and they want to experiment and learn. They switch PLs because they have to. Thus people will generally only switch to PLs that provide all the tools required to "get the job done", tools that are often not a part of the PL itself, e.g. an IDE (at least a debugger), a good compiler for Windows (or for a VM that runs on Windows) or Linux (or a VM that runs on Linux), a UI designer, code sample, and the rest.

It's therefore my opinion that the best way to introduce programmers to FP is to provide FP features in imperative languages. Happily this is already happening, at least to an extent.

P.S. Obviously if a new PL is too close to an older PL there is no point in switching because they are essentially the same thing.

Also, C# is an exception to this closeness rule since it's a popular new PL that is totally unique and not similar to any existing PL ;-)

Daniel: Gasp! So people were forced to use Perl?

I think the "forced to use" aspect (and this applies to Perl) is what is often known as the "killer app" effect.

People discover that the new language makes it easy to do X, and soon that becomes "just the right way" to do X. Then everybody who wants to do X learns the language. (It helps if X is something a lot of people want to do. ;-))

For Perl, it was two things: CGI and the need to transcend the limits of UNIX shell scripting, especially for networked apps (related of course).

For Java, I don't think it was Applets, but server-side distributed computing and n-tier apps.

Pure FPLs (or rather a particular pure FPL) may have their killer app already, it is just that their X is not something with wide appeal. Or it may yet lie in the future.

If "real world" computation continues to get more complicated, the simplifying aspects of FP may win out over the perceived "more complicated" aspects.

Or maybe not. ;-)

I think this is a central idea. People seem to be willing to adapt to any kind of new semantics as long as they *think* they think they are in familiar territory.

Python's lambda, map, reduce and so on make a sort-of functional style possible in a language with C-like syntax. Similarly, perl 6's new subroutne features would make it possible (albeit painful) to do FP-like code in perl.

But I guess this is the opposite of (or maybe orthogoanl to) what we are talking about here: a real FPL with familiar syntax. So, to get back to where I started, what would such a beast look like?

To start the ball rolling, how about C with a built-in type "function", and maybe "list", with lambda, map etc. No "void" type so every function returns something. Hmm, sounds like a cross between C and Python... I'll need to think some more. Can somebody else *please* make a better suggestion?

Nobody mentioned DrScheme yet? Righty-oh.

I remember reading a few years ago that Microsoft conducted a survey asking existing users of MS Word what features they would like to see added to the next version of that product. A large percentage of the responses identified features that were already present in the current version. I feel much the same way about DrScheme at the moment. Every time I start thinking, "yes, this is great, but what about X", it turns out that X is already available.

What FPLs need is nothing more or less than a large marketing budget, IMHO. When you look at the things VB6 programmers (that includes me, btw) or VC++ programmers using MFC have been prepared to put up with in order to Get Things Done, the obstacles to acceptance posed by "stupid parenthetical syntax" seem trivial - given sufficient marketing push.

<jocularity strength="weak">

One might start by renaming a few things:

Non-determinism sounds like something that breaks out in the office when the manager goes away for the week. Why not call it "Enterprise Intelligence" instead? "Programmers can now concentrate on defining possible scenarios, and let the language itself choose the correct outcome". Brilliant!

Higher-order functions? Sounds scary and mathematical. How about "Flexi-code"? "Programmers can now combine program features with unprecedented flexibility and power. The possibilities are endless!"

And as for those parentheses: "research has shown that curvy brackets are easier on the eye than angle brackets. Consequently, Scheme programmers need to take 15 percent fewer breaks than XML programmers. Plus, their monitors don't wear out as quickly..."

</jocularity>

Goal Directed Evaluation is a also a good name for this.

I once had an idea to demonstrate this idea: design two languages, AntiML and CoJava. (Or was it CoML and AntiJava?)

AntiML would be a functional language, ML if it had been badly designed. It would have no type inference, or principal types property, and the type system would be unsafe. The syntax would be verbose, and it would have statement blocks rather than a binary semicolon operator. Maybe it would allow allocating values on the stack, and unsafe operations. Or maybe when a language design issue arised which looked moderately complicated, I would punt it and throw in some dynamic typing. I think the result would be a language which is largely indistinguishable from C or Objective C.

CoJava would be an object-oriented language, Java if it had been designed by an algebraist. I would base the OO semantics on coalgebras, so you would have codatatype declarations dual to ML's datatype declarations. The language would support type inference and principal types; it would be safe. There would be no inheritance. I'm not sure if I would allow subtyping; if I did it would let one type be a subtype of the other when there exists a canonical injection. Perhaps there would be a module system like ML's, or a sophisticated type system like Haskell's. It would allow user-defined infix operators, and have an `expression-based' syntax. It would allow imperative update either in an uncontrolled way like ML, or perhaps in a controlled way like Haskell, but the focus would be on pure functional computation.

And so on...

I think you are right if you consider syntax and the superficial semantics. I think that programming in the functional style, which what you mostly do even in "impure" FP languages, is quite a major change of thinking and approach.

Procedural style has a familiar mental model: everyone knows how to follow a recipe or follow instructions for an IKEA shelf (OK, maybe not... ;-) ) Step-by-step changes of state is a normal, everyday approach to complex problems solving.

Functional style has a more algebraic model which is more elegant and general in many ways, but even many computer scientists are not that comfortable with abstract algebra. (Very strangely, my local university, though quite reputable in CS, only requires calculus and linear algebra for a CS degree; abstract algebra courses seem to be optional).

The terror inspired in newbies by the words "closure", "continuation", and "monad" demonstrate this. ;-)

I would base the OO semantics on coalgebras

I've been meaning to ask you more about this. I read the first of the papers you mentioned (Jacobs), and, though I found it interesting, I kept wondering why OO really needed the co-algebraic treatment.

If I understood him correctly, his main motivation was to model information hiding, and his co-algebraic operations seem to be a "type-theoretic abstract state machine" to handle this.

I'm not so convinced that information hiding is that crucial to OO; though there are stylistic and practical reasons to keep data elements private, it is perfectly OK (and common) to have public accessors for these.

It seems to me that you could model objects much as you do tuple types, as products, with accessors as the projection morphisms. You could add a "class index" to the product to separate otherwise identical tuple types of different "classes", etc. Obviously, there is more to work out.

Am I missing something here?

Popularity has been a very popular theme on comp.lang.functional
- Why FP will take over the world and C will die
- The Imperative Strikes Back
- Learning from C++'s success ( was C++ briar patch )

Crossing the Chasm: A S&T Transition Strategy

DrScheme is a very nice tool, but that's like saying that Eclipse or jBuilder were fundamental to Java's success.

They certainly aren't harming it; and my first encounter with Java was in the context of an IDE with a GUI-builder, Symantec's (IIRC) Java Cafe. I thought it was pretty cool, at the time.

MzScheme, plus assorted libraries distributed with DrScheme, plus some others that are not hard to find, plus "Teach Yourself Scheme in Fixnum Days", etc., comes the nearest of any FPL I've seen to Python's full-featuredness in terms of libraries and documentation...

I don't know which has to come first: the community sites or the community. There obviously is a Scheme community; it apparently isn't the sort that has message boards where people post questions about how to do date-time manipulation in a CGI script.

But I like the idea. I'm at about the stage with Scheme where I would benefit from a reasonably broad set of "cookbook" examples and developerWorks-style articles on how to make cool stuff happen. If I persevere, I'll get over this stage without having to rely on such things; but they would still be nice to have.

Boy, you just can't resist those cognitive factors, can you? :)

FWIW, I don't believe the `procedural is natural/familiar while declarative is strange/exotic' argument. Planning a task requires both procedural and declarative thinking, and indeed I think there is a duality there related to CPS transformation.

I'm not so convinced that information hiding is that crucial to OO

The problem is partly that "OO" is not very well-defined. In fact, I think people like to keep it that way because then, when they see some language feature they like, they can say, "That's so OO!", and when they see something they hate, they can remark, "The problem there is it's not OO enough." That way "OO" can always remain the rosy ideal everyone wants it to be.

As soon as you fix a particular meaning for OO, it becomes vulnerable to objective analysis, and people don't want that. (The situation reminds me of the situation with programs and program specifications.)

It seems to me that you could model objects much as you do tuple types, as products, with accessors as the projection morphisms. You could add a "class index" to the product to separate otherwise identical tuple types of different "classes", etc. Obviously, there is more to work out. Am I missing something here?

I think what you are missing is that a) products are a trivial kind of coalgebra, and b) you need something like a fixpoint to model the fact that classes can reference themselves. Put those two together and you get coalgebras in general.

Special indices are unnecessary. You can distinguish `otherwise identical tuple types' by choosing them to be distinct products (since there are in general many ways of forming the product of two types, all isomorphic).

Well, at least I'm trying to be more principled in their use... ;-)

Part of the problem is that (as I think I failed miserably to explain in the previous threads) I think "cognitive factors" are lurking in a lot of principles that seem "solid".

For example, if we say "the primitives in a language should be few in number and orthogonal with respect to each other". Nobody is likely to argue with that (hmmm... maybe Larry Wall ;-) ), and it offers an "objective" criterion to work with, but scratch the surface of it, and it really is saying "...because it is easier to reason about", which is, if you think about it, a "cognitive factor".

I don't believe the `procedural is natural/familiar while declarative is strange/exotic' argument.

Put that way, I don't think that I do either. ;-) I do take it for granted that when I do more declarative style thinking (say reading an abstract math text) I will have to "think harder" per unit of text. I don't think it is so much a fundamental difference of kind, as one of degree, a kind of "higher density".

This also may vary across individuals. (Pretty likely, really.)

The problem is partly that "OO" is not very well-defined.

I have to agree. For me right now, it is mostly a style for organizing the solution-space rather than some profound theory. Seems useful though.

products are a trivial kind of coalgebra

I had to think about that for a bit (darn cognitive factors ;-)), but I see what you mean. The parallel with algebraic data types being expressed as sums seems pretty obvious after the fact.

you need something like a fixpoint

On this one, I'm not sure how you wouldn't need this with recursive algebraic types too.

You can distinguish `otherwise identical tuple types' by choosing them to be distinct products

Ah, of course. Some nasty non-CT thinking crept in there. ;-)

I really must take my "cognitive factors" into the shop for some repairs... ;-)

Some FPLs seem to have transitioned from Innovators to Early Adopters (LISP in AI days, Erlang) and some haven't (Haskell? - aren't many FPLs vehicles for language design research - why would we even expect them to be popular?)

Have any FPLs formed a base amongst Early Adopters that would allow them to make the next transition? There are scattered examples of early adopter use being eroded (Lisp at JPL, Yahoo Store). Without a base of Early Adopters is it the right time to go after Early Majority Joe Programmer?

big enough group of programmers has to be forced to use the language / most programmers... They switch PLs because they have to
Yes, unlike Innovators, even Early Adopters need a non-technical reason for adopting a new technology.

Moreover, ya gotta hype:

A primary component of successful heterogeneous engineering is to convince the world that the future is destined to be dominated by the technology. Effectively executed, this will have a profound psychological impact and will actually create a self-fulfilling prophecy. MacKenzie asserts that “if it comes to be believed that there is only one way to advance a technology, then that one way has at least a chance of becoming a reality. The others do not.”
Symbolics, Inc.: A failure of heterogeneous engineering

And Java is so very close to C++
"by designing Java’s syntax to be extremely similar to that of C++. James Gosling once joked that he tricked programmers into a paradigm shift by making the system the same" - apocryphal from a student term paper.

Niklaus Wirth was astounded that industry ignored "the elegant and powerful language", "compact and fast compiler", "modern, flexible development environment for workstations, complete with window system, network, document and graphics editor, neatly fitting into about 200 Kbytes of memory, the compiler alone taking less than 50 Kbytes" that was Oberon.
He noted that "In contrast to Pascal, Modula and Oberon did not appear at a time when computing reached new segments of the population". Perhaps we could say "In contrast to Java".

Find the New New Thing and hype your chosen FPL as the way to program it.

From comp.object- "It is taboo to ask what OO is in this group, because it starts a big fat juicy battle that never seems to end :-)"

In contrast, from the clf faq- "Opinions differ, even within the functional programming community, on the precise definition of what constitutes a functional programming language. However, here is a definition that, broadly speaking, represents the kind of languages that are discussed in comp.lang.functional..."

As for the people who "when they see some language feature they like, they can say, "That's so OO!", well, these people will never understand the formal definition anyway. Just ignore them.

Accept that "OO", like "beauty", is in the eye of the beholder.

If you want to do an objective analysis of something, define what that something is and do the analysis. But don't expect to claim that these results apply to "OO" generally. It has no meaning and is not a battle you can win.

Moreover "Often the seeds for the environmental change are planted by the pioneer who plants the idea that a technological solution is possible: How necessary to the process is the failed pioneer?"

Yes, but observing that it is a cognitive factor does not help you design (or use) a programming language.

Furthermore, almost any principle can be supported by nebulous arguments about cognitive factors. For example, no procedure should have more than seven parameters, because the average size of a person's short-term memory is seven. No, no, wait, there should be no more than five parameters, because on average (I'm guessing) there are two local variables allocated in a procedure body. No, no, wait, there should be no more than three, because there will be on average two global variables which affect a procedure's result. No, no, wait, each procedure should have as many parameters as possible, because then the total number of procedures will be less.

If you really want to make arguments based on cognitive factors, then you should be prepared to do some experimental science, like GOMS testing in HCI, or at least point to a specific experimental study.

I wrote: you need something like a fixpoint Marc wrote: On this one, I'm not sure how you wouldn't need this with recursive algebraic types too.

You do need it for algebraic datatypes. I was pointing out in the context of OO that you need some recursion to handle self-reference, and a product is not recursive, so something is missing there.

So it is more helpftul to just take it as an unanalyzed axiom?

almost any principle can be supported by nebulous arguments about cognitive factors

Well almost any principle can be supported by any sort of nebulous argument. ;-) The challenge is to make the arguments less nebulous. (And I must admit, I think some of my earlier ones were too nebulous.)

For example, no procedure should have more than seven parameters

So do you think that the number of parameters is irrelevant? If not, on what grounds would your position. I know that I have a definite position about the issue, based on my prefered design criteria and experience, but I can't think of decent objective way to prove it "right".

After our previous discussion on "human factors", I did some cursory research on the topic. What I found seemed to fall mainly into two categories:

- a prescriptive approach justified either by a general learning model or "because they say so". e.g. this

- experimental approaches, though , as e.g. this site points out, of somtimes dubious or limited result.

You might feel that this proves that we don't know enough to invoke "human factors" in our study of PLs But that still leaves us with such desiderata as the "orthogonality principle" as unjustified axioms or, if we are unwilling to accept it as an axiom, a meaningless arbitrary prescription.

be prepared to do some experimental science, like GOMS testing in HCI, or at least point to a specific experimental study.

For the limitations on this, see second site mentioned above.

I wonder how many PL designers do this kind of testing on their features? Should the designers of Haskell be castigated for introducing layout, a device to make it "easier to read", without providing evidence that it in fact accomplishes this? Or do we just have to accept this, because it is "their language" to do with as they please?

It seems that in language design there are a lot of issues that might fall into this crack.

For the limitations
Richard Gabriel (Productivity: Is there a Silver Bullet) mentioned an additional limitation - the difficulty of finding funding for this kind of research "projects aimed at economic improvement in the software area — and there was $20 million to $200 million available per year for it. However, the requirement was that there be a technological barrier to the improvement... the ultimate goal was enviable but ultimately aimed at funding the same old tinker-toy sorts of technology-busting boondoggles... sometimes it’s a people problem, not a technology problem."

how many PL designers do this kind of testing
There are tiny steps - Evaluating a new programming language. What would happen if we discovered that "what they consider important for languages is trivial or counterproductive"?

without providing evidence
A healthy dose of skepticism is required.

If we are trying to put "human factors" on objective ground, aren't they the same thing? ;-)

I think though, as your comment suggests, that aesthetics plays a bigger role in PL design and evaluation than we can comfortably ignore.

What would happen if we discovered that "what they consider important for languages is trivial or counterproductive"?

I suspect that many of them would either lose interest in PL design, or stick to their guns and lose interest in objective evaluation. ;-)

There is more to it than aesthetics.

In the kind of work I do, I have to do interpretations of programming languages in some semantic category. If the primitives of the language are orthogonal, than this is a lot easier than if they are overlapping, because if they overlap then either I have to ensure that the semantics agree on their intersection, or I have to find a normalization algorithm, because then the normal forms are all orthogonal.

As a simple example, consider the language of monoids. To assign a semantics to a monoid expression, I have to specify a homomorphism of monoids, which means that I have to make sure that I interpret the multiplication as an associative function, for example, else the semantics is ambiguous. Checking associativity is a proof obligation which arises because the monoid terms are not orthogonal: there are equations between them.

An alternative is to specify a set of normal forms, for example by choosing a left-associative representation. Then I only have to give what amounts to a list algebra, and there is no proof obligation because lists do not satisfy any laws.

Another example is coordinatization of vector spaces. If I pick a basis which is not orthogonal, then whenever I (syntactically) specify a linear transformation using that basis I have to check that it is consistent, i.e., that it behaves the same way on a point no matter how it is represented. A simple instance of this is integer representations on a computer. Sometimes these allow you to represent zero in two or three ways: 0, -0 (and maybe +0). So when you specify an integer function f you better make sure that f(0) = (f-0) = f(+0).

This is more than just a mathematical issue. It's actually a real issue in programming that I do every day.

I am not saying, mind you, that we should deal only with lawless or orthogonal languages. That's nonsense, because in many languages computation IS normalization, and a normal form is a value. But, if you have lots of overlapping primitives, then there better be a good reason for it, and it should not be left to users to puzzle out exactly what the nature of that overlap is.

This is precisely why languages intended for computers should be (strongly) normalizing; because then you have the best of both worlds: a convenient, non-orthogonal set of primitives (for example typed lambda-calculus); an orthogonal set of primitives (the normal forms); and an equivalence between them (the normalization algorithm).

And let me also note, that it is situations like these which make so leary of your "cognitive factors". You say orthogonality is an aesthetic issue, which implies that there is no objective reason to prefer it. Yet I just gave you an analysis which demonstrates, I hope, very clearly that there are objective reasons to prefer orthogonality, and also objective reasons not too. Furthermore, that analysis touches on very important principles of computation, such as normalization, laws and congruences.

Now, if you had convinced yourself that the orthogonality issue was completely subjective, do you think you would ever have seen its deeper relevance and all the issues it touches on? I bet not: instead you would only descend deeper and deeper into the `cognitive quagmire' as you require more and more mystical explanations to support your hypothesis. This is precisely why I think all the emphasis on cognitive factors is counterproductive.

Let me paraphrase what I believe your argument is as a pseudo-syllogism:

- the best way to evaluate PLs is to prove properties about them. - having fewer conditions on primitives (e.g. less interdependence) makes it easier to prove properties of PLs. - therefore fewer conditions on primitives are objectively better feature of PLs.

I will agree with you this is a very reasonable and principled statement of position.

I will grant that the first statement is objective precisely in the sense that if someone else accepts this premise, and is prepared to use the same mathematical rules, they will be able to derive the same results as you.

If someone wants to substitute a different premise, such as "the best way to evaluate a PL is to see how many large production systems have been built with it", your positions will be incommensurable, i.e. subjective relative to each other.

Now for the really controversial aspect of my position ;-): I think the second statement is a "cognitive factor", for two reasons. One: is "easier to reason about" in a proof context really different from "easier to reason about" in a learning or using context?

Two: if you have lots of overlapping primitives, then there better be a good reason for it

Deciding when a reason is good enough to make an exception to the rule is subjective unless you can come up with an equally objective measure of "good reason".

Now, my goal in pointing out these weaknesses in your position is not to demolish it. I think it is a reasonable and useful position, and it has and will continue to produce valuable results in PL research.

Instead, I want to argue that some of the "cognitive factors" are no less worthy of consideration, so long as we can find similarly "objective" models with which to discuss them. (I think Ehud's work is in fact a step in this direction.)

I think our discussion so far shows that it is far harder to do this, which I think is the basis of your rejection of such reasoning, but there is a significant risk of throwing the baby out with the bath water if we reject them wholesale.

It is easier to reason formally about stateful, procedural systems (hereafter procedural)than stateless, declarative ones (hereafter declarative).

Axiom: (Thesis) It easier to reason formally about a system if it can be described with fewer elements and fewer conditions on those elements.

Claim: (Antithesis) A procedural system has fewer elements and fewer conditions at each point in time than a declarative one.

Proof: 1) at each point in time, a procedural system need only consider its current state and the conditions required to transition to its next state.

2) at each point in time, a declarative system must be able to ensure conditions across all states at all times (or, minimally, all states from the initial one up until the present time).

3) mathematicians who reason about declarative systems (e.g. algebraic structures) implicitly recognize this difficulty by "proceduralizing" declarative systems, i.e. identifying generators and simple conditions on generators that can be used to generate successive closures ("states") until the whole structure is defined.

Result: (Synthesis) It is easier for humans to reason using procedural rather than declarative systems at successive points in time.

However, if you are really concerned about the global state-space of a system independent of time, you have the same problems both ways, and you are probably better off using declarative approaches. ;-)

There is more to it than aesthetics
Maybe language designers just assert aesthetics to avoid the tedium of explaining why they really came to a decision?
Anders Hejlsberg: "Ultimately, good language design boils down to assembling a team of people who have good taste. It boils down to programming aesthetics"

the emphasis on cognitive factors
Has there been much emphasis on cognitive factors in programming language design? The weakness of "arguments based on cognitive factors" seems to stem from lack of research and lack of interest.