Lambda the Ultimate

But then, in 1994, I had an illumination. Why should I work so hard for the computer? Shouldn't the computer work for me? I realized that, in almost all cases, expressiveness is much more important than speed, as long as the speed is reasonable. In the Oz philosophy, we have an informal design rule: "any new concept should be *both* efficiently implementable and easily formalizable". That is, efficiency is important but it is only part of the story.

Have any of you had similar realizations?

What's behind that website? Perl, Python, Lisp or C? Can you tell? Write a file server in your favorite "expressive" language, host it on a fairly fast CPU and connect to it via 100Mbit ethernet. Guess what, the network link is so slow, you can't tell Erlang from Tcl from C.

Measuring a language's performance using CPU based tests (execution speed) is archaic in a networked world where super fast servers with gobs of memory cost under $2000.

I have similiar, but more elaborate, servers in production.

proc accept {logfd chan addr port} {
  fconfigure $logfd -buffering none
  fileevent $chan readable [list handle_input $logfd $chan $addr]
  puts $logfd "[clock format [clock scan now]] ($addr:$chan)Connected!"
}


proc handle_input {logfd chan addr} {
  if {[eof $chan]} {
    puts $logfd "[clock format [clock scan now]]($addr:$chan) Disconnected!"
    catch {close $chan}
    return
  }
  puts $logfd "[clock format [clock scan now]] ($addr:$chan) [gets $chan]"
}


socket -server [list accept [open "./clients.log" w]] 6667
vwait ::forever;			# wait forever...

Sigh, it does have one global variable "::forever"...

I mainly program in Javascript, and most projects are XML related. When I need speed, I switch to XSLT. Xpath expression are both more expressive and also very fast.

As another example: I can also imagine that adding sets to the core of a programming language adds both expressiveness and speed.

I realised that with a GUI-based program, my computer spent most of its time waiting for the next keystroke or mouse movement. So why exactly was I trying to scrounge cycles?

Now I work for a company which makes high-performance database servers for clients whose machines are loaded most of the time. All of a sudden, execution speed is critical. A cycle saved here is a cycle that can be spent doing useful work elsewhere. However, at least I know that this is one of the few situations where it really does matter.

On how easy optimisation is: It can be easy and it can be hard. I agree with Ian that most of the time, once you have hard data (i.e. profiles), the solution is usually obvious. Cache a value here, change a data representation there, maybe change your algorithm.

Then there are the hard cases. Why am I always getting a cache miss in the middle of this loop? Why am I drowning in lock contention? This is complex stuff, and it occasionally requires understanding of the machine on all levels, from the cache coherency protocol that the motherboard uses, right up to the highest level of abstraction.

I'm in full agreement with PVR on this subject, and yes I remember MacApp. In support of PVR's remarks I will add some footnotes. Performance is not always in the hands of the programmer or the program. Selecting good algorithms is important; optimization is sometimes worthwhile; but tuning a program may be less important than realizing:

Unfortunately in Alice one simply cannot reasonably expect it to be compiled to machine code. Reason? Simple we allow for code (in fact packed structures (that includes functors)) to be pickled, transmitted over the network... and executed in another process, who couldn't possibly know anything about the structure beside it's signature.

But there is hope: The currently under development new virtual machine for alice called SEAM (it's actually a generic VM service provider) does jitting and is a lot faster than the current mozart based release ;-)

Prolog is very high level, and you claim to have produced very efficient machine code. So you can sqeeze cycles and still write very high level code, no?

On a borader scale, it would be interesting to hear your take on Prolog. Classic Prolog doesn't sclae (modules, type checking etc.) It can also be quite hard to implement whole systems in Prolog (GUIs etc.) Shoud Prolog still be considered a general purpose programming language?

Of course you can! But Prolog is nice because its semantics allow the generation of efficient code (up to a point). My experience with Prolog gives me some hints on how to change the language so that it can be compiled even more efficiently without reducing its expressiveness for general programming. The first thing is that predicates should be deterministic. Naive Prolog compilers often can't find this out for themselves, so they create choice points only to have them removed with cuts a little farther on. The second thing is proper use of registers together with tagged data. Unboxing is nice, but not always possible or easy. A little bit of hardware support can go a long way there. In Despain's group at Berkeley we designed and built a RISC microprocessor with support for Prolog. The support was actually quite minor, but it gave (around) 50% performance improvement for Prolog, even with a very good compiler (which can obviate the need for hardware support, a lesson that the Lisp machine people learned the hard way!).

Modern Prologs (like SICStus) are not bad. They have a lot of good functionality and you can build whole systems in them with no problem whatsoever (e.g., SICStus has modules, objects, and GUI support). They are especially nice for constraint programming. SICStus, e.g., is world-class regarding its constraint-solving abilities. (Constraint logic programming is one of the great successes of the Prolog community.)

But Prolog is an old language. Using it nowadays, it really feels old. As soon as you get away from the clean logical core, it is full of curiosities and limitations. For example, it is completely flat (no lexical scoping, not compositional at all). It is first order, with some funny built-ins (like call/1 and setof/3) to get around the most glaring limitations of being first order. It is sequential with global backtracking, using funny operations (like 'cut') to prune the search. The freeze/2 built-in gives some flexibility to execution order, but the whole thing is still limited by the globalness of the backtracking.

Mercury fixes some of Prolog's limitations: it is higher order and it has static types and modes. But my opinionated view is that is that it has thrown out the baby with the bathwater: it has no logic variables or constraints. (Note: there is recent work on bringing the constraints back, in a language called Hal. I don't know how far they have gotten.) IMHO, the essence of Prolog, what makes it special, is not Horn clause syntax but rather computing with partial information, i.e., logic variables and constraints. Leaving them out, whew, what a loss!

A glimmer of success came first with the work of Michael Maher, who in 1987 in a famous paper started the idea that a logical condition (like entailment) could be used to modify control flow. E.g., a program could suspend until a given constraint was *entailed* by the store. The breakthrough then came in 1990 when Vijay Saraswat introduced the concurrent constraint model, with its famous 'ask' and 'tell' operations. (For that he won the ACM Distinguished Dissertation award.) This model gave the foundation that was needed for the synthesis of the two great families.

The synthesis was finally achieved in the AKL language, designed by Sverker Janson and Seif Haridi, around 1990-91 (note that they were close on the heels of Saraswat's more theoretical work!). AKL introduced the concept of 'encapsulated search', which allows Prolog-style problem solving within a concurrent environment.

Oz is a direct descendant of AKL and another language called LIFE, designed by Hassan Ait-Kaci in the late 1980's. Oz was designed primarily by Gert Smolka and his students. Unlike AKL and LIFE, Oz breaks with the Prolog tradition: no more Horn clause syntax (a heresy in the Prolog community!), compositional, higher-order, looking much more like a traditional language. Yet, in some sense Oz is still a logic language in the Prolog tradition (and this is now recognized by the Prolog community).

Since then, Oz has been getting steadily simpler and more expressive over the years. See, e.g., Smolka's 1994 article on the Oz kernel language and compare it with chapter 13 of CTM. See, e.g., the concept of 'computation space', invented by Christian Schulte, which crystallizes the idea of encapsulated search into a simple yet very powerful abstraction. The current semantics of Oz is much simpler than before, yet the language is a lot richer.

My understanding was that, like Prolog, Mercury uses unification rather than matching (in the absence of any mode declarations). In what sense, then, does it lack logic variables?

And I guess I don't understand what you mean by `constraints' either. What does Mercury lack here that Prolog supports?

Benedikt Grundmann: Unfortunately in Alice one simply cannot reasonably expect it to be compiled to machine code [because] code [is] transmitted over the network ... and executed in another process, [which] couldn't possibly know anything about the structure beside it's signature. But ... currently under development ... SEAM ... does jitting ...

Several flavors of ML are compiled to native machine code, so I expect that Alice could too. Not all the code, all the time, is hopping across networks. (Those instances could be JITted in isolation, I suppose.) Besides, as others have noted, networks constitute a bottleneck in their own right. Compilation then fades in significance behind network speed, latency, and data synchronization.

Most programs are un-networked. Alice ML would enjoy better marketing momentum with a native machine code compiler. Large classes of programmers avoid alternative modes of compilation. VMs and JITting don't cut it for them. Microsoft may be altering this landscape somewhat with its C# and .NET marketing steamroller. Yet many of the unwashed programming masses regard "academic" languages (defined as anything != C/C++) as performance dogs. That's why I mentioned MLRISC on the Alice wiki. There, it was explained that platform independence is the reason for JITting, but I think MLRISC buys just as much of it.

An Alice ML code snippet demonstrating what you mean would help the readers, since networks can transmit any kind of data, including binary machine code; the point is not obvious.

To rephrase my remarks a bit, I mean that we should not feed prevalent illusions that advanced (expressive) language designs must necessarily suffer poor performance. If we're trying to influence the mainstream, then we owe it to ourselves to shatter those illusions.

Developing languages that do so is a more certain route to the kind of outcome PVR seeks than merely arguing that expressiveness outweighs performance. I agree with that outlook, but others don't, and my overall point is that such debate serves no purpose: the truth is, to a first order approximation, that we can have both. However the academic world has not promulgated this fact very successfully.

Mercury doesn't implement the full unification algorithm, e.g., it can't do variable-variable unification (making two logic variables equal) or calculate with data structures that have "holes" embedded in them (i.e., unbound logic variables). It can only do limited forms of unification: binding unbound variables with values.

And I guess I don't understand what you mean by `constraints' either. What does Mercury lack here that Prolog supports?

By "constraints" I mean what is usually meant in constraint logic programming: relations with an efficient incremental algorithm for determining satisfiability. Prolog's usual binding can be seen as equality constraints over rational trees. This can be generalized in many ways, e.g., to linear or nonlinear equations over integers (what are usually known as "finite domain constraints"), etc. Mercury does not support this.

Some more historical perspective is given in the papers Logic Programming in the Context of Multiparadigm Programming: the Oz Experience, and Programming Languages for Distributed Applications, both available near the bottom of this page.

And if you want (part of) the history of Prolog itself, check out the paper 1983-1993: The Wonder Years of Sequential Prolog Implementation, available near the bottom of this page.

That was the original motivation for my work on Aquarius Prolog. But it didn't have the effect I hoped at the time (that Prolog would become much more used). I think that performance is only one of the impediments for getting advanced languages to be more used. Performance can only have a negative effect, i.e., bad performance keeps them from being used, but not a positive effect, i.e., good performance does not necessarily mean they will be more used. As Seymour Cray used to say, once you get rid of one bottleneck, there is another one lurking just behind! He was talking about supercomputer performance, but I think the analogy also holds for influencing the mainstream.

For example, I know people who object to OOP beacuse run time dispatching is an overhead they are not willing to accept. When they were asked to include OOP features in their programming languages, they simply ruled it out. Ten years passed, OOP became a standard feature, one that people are use to, and expect to be able to use, and suddenly theoverhead was seen as less important.

A similar thing happened with the attitude towards garbage collection. GC has a definite overhead, and recent advances in the field haven't reduced it enough -- but where as a few years ago the common attitude was "GC is to costly, and manual memory is something Real Programmers know how to do" the common attitude now is "GC is crucial, it prevents many nasty bugs; the efficiency overhead is usuall less important, and should influence the design only when it can be shown to be significant enough to make the program unusable."

In general I like the Ada approach: Strive for expressiveness, but be careful when adding features to make sure they allow efficient compilation. Alas, there are cases where this approach can be seen as too conservative (e.g, Ada needs a standrad garbage collected "storage pool").

The quickest way to get an implementation of a new logic language is to write an interpreter in Prolog.

The mainstream (I'm not even sure that means C/C++ any more - isn't it Java?) is starting to realise that performance is not critical. I work in a speed-critical area (processing large quantities of scientific data) and it's well accepted that we already have the numeric stuff as fast as possible in C and Fortran libraries. What's important now is distributed/grid computing, and the problem there isn't speed but abstraction. It's easy to call the hand-optimised number crunching code once everything is set up and ready to go - what we need are tools for managing distributed processes/data. For those tasks (processing) speed is largely irrelevant.

The problem is more that the mainstream just don't know what is out there - the hot new thing is still OO and one of the smarter people round here is just starting to enthuse about garbage collection in Java after having used C++! Distributed processing means CORBA - the reason isn't speed, it's just all that people know...

http://www.vitanuova.com/solutions/grid/demogrid.html (Click on camera, lego clock... on the left for schematics of the "file system" tree offered by each device.)

Shouldn't everything implement 9P/Styx? (9P man pages)

We got the job of building a WLAN-security product. This is a device you put between your intranet and a wireless network, which acts as a firewall and VPN. You can install several of them in a cluster, each connecting a different segment of access points to your network (e.g. on a particular floor or in a particular building).

The feature that I implemented is the "roaming" mobility part, that lets a wireless user wander between different networks/buildings without losing connectivity or needing a new IP address or anything like that. Early on we fleshed out a design for this whereby the machines in the cluster would act as a "distributed ethernet switch", so that every host everywhere would have ethernet connectivity. This works even when the networks have IP routers between them, because our boxes tunnel ethernet packets through the IP network in sort-of "virtual ethernet cables". [It turned out that just about everybody else built their products this way too.]

Anyway. We build our stuff on Linux, and Linux has an astonishingly powerful set of networking features. It turned out that we could implement pretty much the whole mobility thing with fancy configuration, and the only significant piece of software we had to implement ourselves was a virtual ethernet device that tunnels everything in IP to another machine. The "obvious" way to do that would be to write a kernel module, but we only had about three months to build the whole product, so this wasn't very attractive -- better to get something simple working reliably right away so that I'd have time to figure out all the other inevitable subtle details.

So I used another marvellous Linux feature called a 'tap' device. This is a virtual network device that is written as a regular user-space program. In no time at all I was able to write such a program in Erlang that wraps ethernet packets in UDP and shuffles them between machines in the cluster. This did leave time to sort out all the "other details", of which there were plenty.

Towards the end of development we tested the performance, and found it fairly low but tollerable. I considered a quick port to C, but by seeing that most of the time was being spent in kernel-space and 'strace' said that Erlang was making a reasonable pattern of system calls, I concluded this wouldn't buy much. It would be better to hold off and make a kernel module later to get performance.

The Erlang implementation worked just fine and we shipped it.

After that it was time to do a kernel port. The approach was very straight forward, thanks to Linux: just replace the 'tap' device with a custom kernel-implemented version. At this stage we understood the issues perfectly, and it was just a day's fun hacking to port into the kernel. This pushed performance up by a factor of 6, and we lived happily ever after.

This seems to be a common pattern for me. Make it right, and as simple as you can, and then find what needs to be optimized and do it. It usually turns out to be very easy, and really it's only once or twice a year that any program I write actually needs high performance. In short, I've adopted Joe Armstrong's motto: "I must program as inefficiently as possible." I don't make any concessions to performance anymore until it proves that I have to, and that's surprisingly rare in practice.

The pleasure I used to get from writing unnecessarily efficient code, I now get from writing eye-wateringly inefficient code in programs where I know that it doesn't matter. :-) Another advantage is that by erring on the side of inefficiency, you get discover exactly where performance does and doesn't matter - which can be pretty surprising.

Suppose an application wishes to establish a connection over TCP/IP to www.bell-labs.com. The first task is to translate the domain name www.bell-labs.com to a numerical internet address; this is a complicated process, generally involving communicating with local and remote Domain Name Servers. In the Styx model, this is done by opening the file /dev/dns and writing the literal string www.bell-labs.com on the file; then the same file is read. It will return the string 204.178.16.5 as a sequence of 12 characters.

Once the numerical Internet address is acquired, the connection must be established; this is done by opening /net/tcp/clone and reading from it a string that specifies a directory like /net/tcp/43, which represents a new, unique TCP/IP channel. To establish the connection, write a message like connect 204.178.16.5 on the control file for that connection, /net/tcp/43/ctl. Subsequently, communication with www.bell-labs.com is done by reading and writing on the file /net/tcp/43/data.

8^)

I am only 1/2 kidding.

Peter: That was the original motivation for my work on Aquarius Prolog. But it didn't have the effect I hoped at the time...

Andrew: The problem is more that the mainstream just don't know what is out there...

Ehud: A language is accused of being inefficient, you prove it isn't, and then it turns out that nobody cares. That's one of the main reasons why expressiveness should come first.

Peter, Ehud, and Andrew all make good points that slightly miss mine. I agree that expressiveness comes first. Let's call my position on performance "necessary but not sufficient." Peter's disappointment was a shattered expectation of "sufficient." That is not my expectation. Peter now says that he's with me in the necessary-but-not-sufficient camp: "Performance can only have a negative effect....performance does not necessarily mean [acceptance]." So we are agreed. Addressing Andrew, companies regularly reject Java for C++ over performance issues. Furthermore the slow performance of Java casts a bad light on more advanced languages, which are thought, often rightly, to share its flaw - a VM basis. However, let me tie Andrew's remark about ignorance to Ehud's "you prove it isn't [but] nobody cares," which merely rephrases necessary-but-not-sufficient.

Some of the ignorance out there is intentional. There is active opposition to expressive languages. Some of it is rational: business risk calculations pertaining to language novelty or obscurity; cross-platform portability concerns; lack of libraries. Some of it is irrational: die-hard C hackers, comfortable software staff not keen on new modes of thought, proud engineers with decades invested in skill sets (e.g. MFC) the value of which determine their salary. We have active opposition that quickly hoists the performance banner every time it feels under threat. If we want good concepts to pass that naval blockade, we had better get out the big guns and go for compiled performance as well as undeniable, problem-solving expressive power.

A final thought. Useful libraries are part of the sufficiency equation. And here we can fell two birds with one stone. Just having libraries at all makes a language more attractive. Libraries can also showcase the power inherent in the language.

P.S. Luke, I'm doing wireless LAN work too!

Yes, there is active opposition. My attitude now is one I first heard from Helmut Simonis: I don't care about converting the gray masses who learned programming the wrong way and who (for many possible reasons) will not learn anything else, it's too late for them anyway. I care only about two groups of people: students and smart programmers. That is the raison d'être of CTM: it targets those two groups explicitly.

1. Students want to learn the lang de jour, and pressure schools to accomodate.

2. Faculty people specializing in other fields of CS (e.g., complexity, networks) and not interested in PL are likley to belong to the masses who learned programming the wrong way, that you wrote about.

The combination of these two factors can be very dangerous when decisions need to be made about which languages to teach.

There are several counterarguments to the "langue du jour" argument that can work with ignorant faculty. For example, students graduate in three or four years, and the langue du jour may have changed by then. Universities have to stay ahead of the curve, not lag behind. Another argument was given by Joe Armstrong during my panel at SIGCSE 2003: companies (especially small ones) often seek people with complementary skills, not clones. See the last slide of my position statement, which gives Joe's argument. Joe's argument carries weight because of his industrial background and because he has been involved in startups.

Another approach that may work is to argue that languages are not skills, they are tools. What we need to teach are the skills that allow you to use the available tools effectively.

"The advantages of using files as a central concept in the system are:

• File systems have simple and well understood interfaces across a wide variety of operating systems. Interfaces to the files generally consist of a small set of well-defined operations such as open, read and write

• Reliance on file systems reduces the amount of interface code and keeps the Inferno system small, reliable and highly portable

• Naming conventions for files are well known, uniform and easily understood

• Access rights and permissions to files are simple, yet can be used to ensure multiple levels of security"

Inferno Design Principles

(Ummm can we have some alternative to ACLs please?)

Peter: My attitude now is ... I don't care about converting the gray masses ...

Ehud: Another approach that may work is to argue that languages are not skills, they are tools. What we need to teach are the skills that allow you to use the available tools effectively.

Actually, the concern is not converting anybody. The concern is an ability to select appropriate tools in the workplace. (If others want to suffer in ignorance, let them suffer.) That is my uphill battle, but the gray masses affect it in the sense of influencing management thinking. Getting permission for Obscure Language X can be difficult. So it would help my cause to have at least some of the gray masses see the light. How's that for Machiavellian.

Besides, getting performance requires no change in fundamental philosophy. Very simple steps can lead to great gains. For example, just using Digital Mars C++ instead of Microsoft Visual C++ is a big leap forward. It costs nothing in time or money, but yields a factor of two (easily). Compiling seems simpler than JITting, too, especially with tools like MLRISC lying around. So I agree with Peter, but think performance is easily rolled into language designs and should be to the extent that statement holds, even though not as a driving design factor.

Ehud makes a very excellent point. If only the HR world were not so keen on resume databases and keyword skill searches. What HR wants to know is, "how many years of experience do you have in Language Y?" Trying to explain Ehud's point to them is a lost cause.

Trying to explain Ehud's point to them is a lost cause
For entry-level the industry will hire for potential; for mid-level it hires for existing knowledge-of-tools; for expert-level it hires for demonstrable skills.

For the mass of mid-level positions, there's no budget for training skilled candidates in specific tools: they must know most of the tools merely to qualify as a candidate. Actually, there's no need to budget training for those mid-level positions as-long-as you can find qualified skilled candidates. The problem is separating out the unskilled qualified candidates from the skilled - and if anyone figures out how to do that, they can access the pool of skilled but unqualified candidates.

I like the idea of offering information using generic and simple structures, which filesystem trees and s-expressions are (and XML trees are not.) What I like especially about filesystem trees is that we have a common, quite ergonomic vocabulary for moving around in them, and manipulating them, for example the UNIX commands mv, cd, ln etc.

I recently used these commands in a command language (running in the O'Caml shell) for manipulating general graphs. It worked very well, and brought me to the idea of "exporting" program objects and their interconnections as files, directories, and pointers between them. Then running programs can instantly be explored through common tools like command line terminals and file navigators, and manipulated through APIs supported by every programming language.

The Plan 9 protocol and libraries encourage definition of userland file servers for arbitrary data. I think Plan 9 contains dozens or even hundreds of custom file servers offering services in the tangible and easily explorable form of filesystem trees. In many Plan 9 documents, and when using the system, I have observed very enjoyable synergy effects achieved by this simple mechanism, similar to the use of s-expressions makes lisp so nice.

While "everything is an object" has obvious (to me) benefits, "everything is a file" does not. ...

And if I am going to read and write to a file for my "API" then I'd rather use a rich format like S-expressions than flat text.

I think for the creators of Plan 9 the files are objects, because they, coming from the C tradition, just don't mind with writing (yet another) ad-hoc parser when it comes to defining an interface. Where others define a message-based API they define a (filesystem) structure + text based one, but their intent is the same, and while some generality is lost, they offer the same level of abstraction, methinks. Using s-expressions on top of the Plan 9 protocol is then the icing on the cake. :)

Isaac, the recruiting game is more slipshod than that. When an interview comes my way through non-HR channels, such that I speak with a real engineering manager before HR, the question I get is totally different: "Where have you been all my life, and why didn't our HR department find you?" Managers with technical knowledge understand and share more of Ehud's philosophy than overly conservative HR. After all, how long does it take the average LtU reader to grok a new language - days, a week, maybe two at the outside? The term "training" implies some sort of years-long medical residency. A better analogy might be re-certification in an already known specialty, be it embedded systems, enterprise databases, user applications, etc.

My philosophy is to look for jobs at places that know how to hire. For the long run it's your best bet. The exact same rule should go when you decide which company shares to buy...

I am not sure what this thread has to do with the title any more, but let me give another advice: use generic terms. Write: "I excellent at OOP" instead of "I know C++." For HR personell benefit write "Five years experience at being excellent at OOP"; "Previous work tite: Guru"; "Currently: Self employed, 'Guru at large'"

Yes, then every process could look like...

(let ((port ...mouse or socket or device or...))
    ...
    (let loop ((message (read port)))
        ...pattern match on the message...
        (loop (read port))
        ))

...which happens to be Erlang-like. These concepts all complement each other pretty well.

On the other hand the files could all read/write XML. But that's another thread of discussion!

Thanks Ehud, but I'm not looking, and already know how to present myself (good advice though!). The relevance to the title is that business concerns elevate performance considerations higher than academic or hobbyist interests.

Yes, and this gets to a key aspect of Plan 9 beyond just a hierarchical naming system. And that is, a hierarchical naming system per user, i.e. I don't necessarily see the same tree you see, and for those names we see in common, I don't necessarily see the same object associated with it as the object you see.

This is better than simply seeing the same tree with the same objects, and relying on ACLs to keep me from doing what you can do with that tree.

http://www.skyhunter.com/marcs/capabilityIntro/solmodel.html

what's the point of having names if they're in a private language? how do you share code that uses those resources?