Lambda the Ultimate

Not that I possess any knowledge about this particular case,
but this is exactly the argument that we usually hear from
the C++ crowd - "just give us enough time and enough
brilliant programmers, and we're sure that we'll beat
the performance of your program". (:

It is certainly interesting to look at why performance
and scalability was not sufficiently good in the previous
solution, but perhaps it was simply easier to design a
scalable back-end in Erlang than in Lisp? If they had
started with Erlang, they might have run into trouble with
the AI logic instead, and chosen to migrate to Lisp,
porting the scalable architecture while re-writing the
logic?

/Ulf W

Perhaps we could instead focus on the actual issues, such as: was the problem, as I strongly suspect, that the Lisp was using OS threads and Erlang wasn't, and the server spawns at least one thread per player? Could we encourage another experiment, rewriting the server in Oz? :-)

To me, one of the great lost opportunities of Lisp was to say something interesting about concurrency. Well, I take that back—one of the great tragedies of Common Lisp and Scheme has been to fail to say anything interesting about concurrency. MultiLisp didn't suffer this defect. :-)

I love up a rumble as much as the next guy, but in this case I decided to contact the Guild Software dudes directly, and hopefully they'll answer. In the meantime, I'd really like to know why people don't use functional programming? *cough*

Here's a comment from the game developers:

The problem [of the Lisp version], in a nutshell, is that *something* isn't getting garbage collected despite the fact that we can't seem to find it from the root objects (which is how the garbage collector is supposed to find out what's garbage too, hence the confusion).

via the reddit comments.

Paul Snively: To me, one of the great lost opportunities of Lisp was to say something interesting about concurrency.

For reasons I won't specify, I need a spec for what Lisp should say about concurrency. So I'd be interested in what you wished such a spec said. I was thinking along lines of an Erlang style model, with a message based shared-nothing style of interaction. (Ie, different threads can't directly see shared mutable state that appears mutable without asking an intermediary.)

In the early/middle 90's I had a very short conversation at Apple with Ike Nassi, who was then in charge of the Dylan team. I asked him a question very much like, "So how do you like Dylan?" -- or words I intended to that effect. But Ike replied as if he had heard the question, "What's not done yet in Dylan?" He said he wished Dylan had specified a thread model, and that the absence of one made him concerned. His response struck me as singularly interesting at the time, since I had trouble seeing the issue as central to language design.

But I hadn't yet graduated to systems (such as scaling servers) complex enough to start managing their resources like a little operating system. Eventually everyone has to figure out how asynchronous concurrent behavior gets coordinated. I happen to like simple message based approaches, because it leads to reasoning similar to how one processes paper messages in the real word. (A message received is evidence something happened concurrently somewhere else; everything else is just evidence based reasoning, which assumes less than global knowledge reasoning.)

If you have time to think about a spec you'd like to see embodied, and care to articulate any details, it'd be best if language specific factors could be avoided in definition. I'd rather the same thing worked equally well when the language looks like Smalltalk, Scheme, Python, or Ruby, etc.

How many more mechanisms are needed to get concurrency you'd like beyond the ability to spawn independent flows of control with means to send messages? Would it simply look like a process model? One that might or might not map onto operating system processes, or something lighter weight?

(I appreciate someone reading this might cite a paper or book elsewhere from which a very brief spec might be distilled after some reading and thought. But it would be most useful if a distilled half page spec were simply post here by a respondee his or herself, in plain language. It's a kind of test of really useful and yet simple things: it must be possible to summarize them briefly.)

Regrettably, I don't have a concrete spec in mind. I wish I did. About the only thing I have to say is that I don't think it's strictly accidental that the great message-passing concurrent languages—which I feel to be Erlang, E, and Oz if you want it to be—are all dynamically typed. That is to say, if your language is dynamically typed, you really haven't left yourself a broad range of good answers to avoiding deadlock and race conditions at the language level; the best approach in such a case is probably message-passing, unless you're willing to go the Oz route and support actual logic variables with dependency tracking, blocking etc.

But truthfully, prior to the introduction of STM, the alternatives in statically-typed languages haven't been any more appealing to me. TyPiCal gets high marks for its encoding of the Pi Calculus in the type system—I remain a big fan—but convincing non-PLT-steeped programmers to use something like that seems exceedingly unlikely to me. The appeal of STM is precisely that it "looks like" good old-fashioned object/imperative code and fits nicely into the now long-established tradition of composability and lexical scoping that we all rely on every day. To me, not having to spend a lot of time worrying about nesting transactions across function/method boundaries is a "killer app," if you will. Yes, the overhead can be rough at around 2-4x, but as Tim Sweeney pointed out, if it means that you really do get to use both cores in both processors (or more), it's worth it.

So I guess I'm saying that I've come to care that whizzy new languages are approachable by C, C++, Java, C#, Python, Ruby... programmers, and that I tend to favor architectures and idioms that support the intuitions that people bring with them--even if, under the hood, that surprisingly Java-esque language acts quite a bit more like Haskell on acid. I'm drawing again on Tim Sweeney's comments a lot here, but let me be clear that Tim has said very cogent things; all I'm doing is riffing irresponsibly on them.

Perhaps we could instead focus on the actual issues

Quite.

Well, I take that back—one of the great tragedies of Common Lisp and Scheme has been to fail to say anything interesting about concurrency.

Maybe "nothing interesting" is a bit too harsh when discussing Scheme and concurrency? Sussman and Steele say in The First Report on Scheme Revisited that Scheme was the result of trying to understand and implement the actors model.

By the way, the above paper is short, easy to read, and enlightening for those who haven't read it. I did a search and have only found one mention of it on LtU in 2004, with no discussion.

Jeff Nowakowski: Maybe "nothing interesting" is a bit too harsh when discussing Scheme and concurrency? Sussman and Steele say in The First Report on Scheme Revisited that Scheme was the result of trying to understand and implement the actors model.

Right... and the take-away was that Hewitt's actors were, at the end of the day, lambda expressions, as Steele says explicitly in his DanFest keynote. And there things have remained—in none of the RnRS reports, nor in the IEEE standard, do you have anything other than an impure strict lexically-scoped dynamically-typed functional language with tantalizingly-interesting, mind-bending full upward continuations, and the observation that those are equivalent to Landin's "J" operator; that is, you have everything you need to express any expressible control operator. Period. So I guess, in an important sense, you're right; Scheme says "Here you go; knock yourself out." It's the assembly language of the Lambda Calculus, if you will.

But I was looking for something more, e.g. MultiLisp and futures, or the Connection Machine's road not taken, or Oz's concurrent constraints, or GHC 6.6's STM. That is, I want a language that goes beyond tossing a bunch of building blocks my way—particularly ones that are wont to blow up in the tossing, nitrogen tri-iodide-style—and actually takes a stance on solving the tough problems of avoiding deadlock and race conditions, scaling, etc. That, I think, is where Common Lisp and Scheme lost the plot, although in Scheme's case the argument that you can build all of those things with enough macro-and-call/cc magic is relatively compelling. CL has, I think, less excuse. But it also has Screamer, so it's partially redeemed itself. :-)

Update: Somewhere along the line I missed the fact that Gambit Scheme, long a favorite implementation of mine that I've neglected since discovering DrScheme, has been tackling Erlang-style concurrency in conjunction with the etos and Termite projects. Nice!

[...] that is, you have everything you need to express any expressible control operator. Period.

More of a semicolon, I think. Don't forget all the subsequent work around delimited continuations, for example, which is still ongoing [edit: and is quite important to real-world use of continuation-based approaches]. BTW, I assume you're aware of the control operator library in PLT Scheme.

I think I'm on safe ground: sure, people keep creating new control operators, but I was definitely thinking of the result that call/cc plus a single mutable cell is sufficient to implement all four *F* operators. But I imagine that your point is that delimited continuations have been proven to be more expressive than undelimited ones, and that's a good point.

I actually was not aware of the control operator library—thanks!

Luke, I agree. I think they've built a really cool product, and that they are using great tools to do it is makes it even better.

/U

The linked comment by Michael/momerath42 included an interesting summary which I think worth quoting here, since it describes an approach which I know is favored by at least a few LtUers:

We chose common lisp primarily for its rapid-prototyping capabilities. In CL, it is very easy to define 'mini-languages', which is what I've done for missions, objectives, senses, reflexes, state-machines, business-models and more. All the code written in these special languages will remain untouched, and be auto-translated (by CL code) into erlang. As I develop new missions, reflexes, etc, I will continue to use the mini-languages; the processes they describe will simply be running on a distributed, fault-tolerant, erlang-based platform instead of the simplistic single-threaded one they have been running on. We had hoped for the simplistic system to continue to serve for a while yet, so that we could focus on player-visible features, but we always knew it would need to be made more scalable at some point.

Yes, if I'm going to credit Gambit, I need to credit Kali as well.

But my principal point, which was that Scheme per se doesn't address concurrency, stands—after all, MultiLisp, which I also cited, was itself layered atop Scheme. So all of these examples reinforce my point, which was precisely that Scheme is a very low-level layer upon which people have come up with different approaches to concurrency.

Still, at least we do have MultiLisp, Gambit, Kali, etc. in Scheme. Most CL implementations seem to be busily trying to take POSIX threads on board. *sigh*

etos is an Erlang compiler too incomplete to actually compile an erlang program.

Termite is an ultra-thin wrapper around Gambit threads which look the same as pthreads to me.

Kali is a distributed system based on the assumption that no node will ever fail.

Your *sigh* is wasted on me..

Luke Gorrie: etos is an Erlang compiler too incomplete to actually compile an erlang program.

The point was that it took a position ("let's compile Erlang to a good Scheme implementation"), not that it was a good implementation of Erlang. :-)

Termite is an ultra-thin wrapper around Gambit threads which look the same as pthreads to me.

Gambit 4.0b20, at least, exposes both a POSIX threads-like API and "mailboxes" for message-passing concurrency. And from the papers I can find (the main Termite site seems to have disappeared), Termite uses message-passing concurrency exclusively. In any case, the actual implementation doesn't use OS threads, and so, like Erlang or Oz, scales to millions of running threads. So my point was that Gambit has built-in support for, and Termite extends and, as far as I can tell, exclusively uses, highly-scalable message-passing concurrency.

Kali is a distributed system based on the assumption that no node will ever fail.

Which just means that it didn't tackle the same objectives as, say, Erlang or Oz. I'm not quite sure what your point is here.

Your *sigh* is wasted on me..

It's based on the observation that Lisp has a tradition of breaking new ground in many respects, so for the community to punt and just reflect OS threads, and not even do that well/consistently, is disappointing to me, just as I get the impression that the fact that none of the systems I wrote about was Erlang is disappointing to you. :-)

I'll have to discuss Scheme with a therapist one day but until then I'll try not to blow my top in public quite so often. Thanks for the measured response Paul :-)

I probably came across like I was promoting Scheme at Erlang's expense, which wasn't my intention at all. On the contrary, it's quite apparent to me that many members of the Scheme community take Erlang extremely seriously, as does the Oz community.

I also agree that the observation "This is a story about a switch from Lisp to Erlang, vs., say, C++ to Java, which seems very significant" is a good one.

Finally, heaven knows I have a couple of years' worth of vastly more inflammatory comments of my own to atone for, so if I've taken some small step in that direction, I'm gratified. Besides, yours are among the comments that I actively seek out here—an eye-roll or two isn't going to change that. :-)

For mean, to be *based on* the assumption that no node will ever fail suggests that it would be intolerably difficult or contrary to the spirit of the system. That doesn't seem to be the case. While the paper "Higher-order distributed objects" explicitly points out that, in that paper and in their implementation as of that paper, they have neglected fault tolerance and security, doesn't mean that the former, at least, is not straightfoward to add. Indeed, if you look through the paper, you'll see how Erlangy it is (there's even a supervisor like example or two). Certainly, it's pretty straightforward to see how a master thread could monitor child ones, and replicate children that have gone silent for too long (and if the children awaken, then the parent could kill it easily)).

It's just an interesting system.

Just to clarify about Gambit threads: they're built on top of first-class continuations, and scale to similar levels as Erlang processes, at least according to benchmarks. The important take-home message from this is that continuations can be used effectively and competitively in this way.

The Erlang process model isn't the only concurrency model anyone will ever need. A language which can provide effective support for continuation-based concurrency approaches has the potential to support a great deal of progress in the concurrency space. It's relatively straightforward to come up with a fixed high-level concurrency model, as Erlang has, and then implement a language with that model baked in. However, that leads to having to choose a different language to get a different concurrency model, which doesn't scale well across the entire application space.

I suspect that's one reason we haven't already seen more languages with similarly high-level approaches to concurrency: for a new general-purpose language, having a single hardwired high-level concurrency model is likely to limit the possible applications that the language is considered suitable for. Erlang may be a demonstration of this.

So, a better foundation on which to build concurrency solutions would be useful. Something better than traditional threads but lower-level than Erlang processes. A foundation like that isn't going to be instantly capable of replacing a mature industrial language like Erlang, though, and anything which implies otherwise perhaps has to do with the pursuit of funding, or something along those lines.

From my own admittedly limited experience Erlang is great for solving the underlying server scalability issues, but a bit less conducive to knocking out biz logic, AI etc.

That's a fair assessment. Partly this is because I don't think most people have experience solving these kinds of problems in a functional language. I've done a lot of experimenting here, and it has taken me time to wander around, try things, and get a feel for how to approach traditionally non-FP problems in an FP manner. Is there a strong benefit over using an imperative language? Sometimes yes, sometimes no.

I seem to see "rules" mentioned a lot in articles on "business logic". Seems like "rules" would be very declarative, which should be mappable to functional langs. Presumably there's more needed than just rules to cover all of business logic?

I'd be interested to hear your insights into what things don't seem to readily map to FP.