Lambda the Ultimate

Same VM as used by Mozart/Oz, indicating the software libraries should be interoperable.

Alice ML is the future for Oz/Mozart if you ask me. It's wonderful work. The problem is that SEAM drains the effort. Alice ML should have back-ended SEAM on LLVM, instead of going it alone. SEAM consumes precious time and will continue doing so to the detriment of actual language work.

Alice ML should have back-ended SEAM on LLVM, instead of going it alone

LLVM has been mentioned a few times recently, but unless I'm missing something, it doesn't really seem to be a good fit for functional languages at the moment. For a start, it apparently has self-tail-call support, but no general tail-call optimization, which is pretty important for languages like ML.

Also, LLVM's "low level" nature means it doesn't deal with things like nested lexical scoping at the VM level, so functional languages have to treat LLVM in the same way as they would a native target, but with a more limited range of possibilities, afaict. Granted, they achieve some portability in return.

VMs for functional languages are typically higher-level, supporting e.g. a 'closure' instruction which handles all of the issues related to nested lexical scoping, and the management of activation frames. There are a lot of advantages to this from the perspective of the language developer, including e.g. easier integration with debugging tools.

So it seems to me that using LLVM as a target for a functional language right now could present quite a few challenges. At the very least, it seems far from clear that it's a no-brainer choice for a functional language implementor. The only "real" languages that compile to LLVM right now are C and C++. The sample Scheme implementation that's available isn't realistic enough to draw any (good) conclusions from.

Sigh. You like to argue with me, Anton. Let's not have this argument again. Even accepting at face value all the assertions just made, my position remains that is easier to build such capability on top of LLVM than construct Yet Another VM from scratch. (LLVM plans on doing it, I am sure.) It boggles me why this fact is not obvious to everyone. Sure, there may be challenges, but they are far less than the DIY approach.

The whole point of LLVM's low-level design is to permit arbitrary constructions on top of it in a portable way. It is an advantage over other VMs, not a defect. You can do things with LLVM that would, er, force you to design your own VM without it. Why would LLVM not be superior to Intel x86 assembly as a target? Does Intel x86 support nested lexical scoping or general tail-call optimization? I think not. Given then that one has to build it, the cooperative approach benefits the open source ecosystem, the Alice project, and LLVM, and gets things done faster for everyone in the bargain. It is win-win-win-win.

Sigh. You like to argue with me, Anton.

Happily, I can prove that I'm picking on LLVM, not you, because I recently made a case against LLVM for functional languages on comp.lang.scheme (others in that thread made similar objections).

I've got nothing against LLVM, either, except that it seems not to be technically well-suited for implementing functional languages right now. The links to LLVM notes about tail calls and stack frame management in my c.l.s. post provide some evidence in this respect.

Why would LLVM not be superior to Intel x86 assembly as a target?

Because LLVM imposes constraints not suited to the implementation of functional languages, which assembly or machine languages don't impose. In that respect, LLVM somewhat similar to C — the problems of translating functional languages to C are well-known, and LLVM has been designed first to implement C-like languages.

Also, when comparing against implementing a high-level VM, the alternate choice isn't necessarily Intel x86 or some other native target. VMs are often implemented largely in C, which is why many VM-based languages are so portable. I notice SEAM is implemented in C++. Note that it's probably possible to implement a reasonably high-level VM using LLVM, but then the question becomes why not just do it with C?

Does Intel x86 support nested lexical scoping or general tail-call optimization?

First, it doesn't do anything to inhibit implementation of these features. Second, the point is that implementing a VM allows those issues to be handled in a way most suitable for the source language. Using an existing VM without the necessary features just makes things unnecessarily difficult.

The whole point of LLVM's low-level design is to permit arbitrary constructions on top of it in a portable way. It is an advantage over other VMs, not a defect.

The points I've raised indicate that LLVM has not yet achieved this goal, with respect to functional languages.

An additional point which I touched on in my previous post is that traditional higher-level VMs provide benefits to the language implementor by having semantic similarities and closeness to the language being implemented. If these benefits are to be discarded, then the least one would want in its replacement is that it doesn't inhibit the implementation of critical features.

Summarizing, there are two major questions here:

First, is LLVM a suitable target for functional languages now? The answer seems to be no. Might it be suitable in future? Sure, but the follow-up question a language implementor would want to ask is when it'll be ready, and how well it'll work. You can't kick the tires if they're not inflated yet.

The second major question is whether a low-level VM is a better approach than high-level VMs. All the existing, successful VMs are high-level. That leaves the low-level approach at a disadvantage — it has a lot to prove, and no good contenders yet ready for prime time, when it comes to functional languages.

In light of all this, no boggling is necessary about why functional language designers aren't jumping on the LLVM bandwagon.

I really have no interest in getting into a big argument here, so I'll point out the following major points w.r.t. language implementation:

RE: Emitting LLVM vs emitting C: One thing that LLVM immediately gives you that C does not is JIT support. There is just no non-laughable approach to getting JIT compilation working with a language that emits C. LLVM can currently JIT compile for 3 targets (X86, PPC, Sparc), has a retargetable and modular code generator (allowing new targets to be added easily), and has an interpreter (for use as a last resort). In addition, LLVM exposes a lot of functionality that is really inefficient if done through C (stack unwinding for exceptions, GC support, source level debugging information, etc).

RE: Tail calls: You're right, LLVM currently does not support "guaranteed efficient" tail calls of the sort required by Scheme and other languages. Strangely enough, you sited the exact documents laying out how they will be added to LLVM when the time comes. The only reason they are not supported currently in LLVM is that they are not on the "critical path" of anyone currently working on LLVM. If having tail calls in LLVM is the one big feature that is preventing you from using LLVM, complain on the mailing lists and someone will help you implement it, or may be convinced to implement it for you.

RE: High level virtual machines: If something like CLR or JVM is a reasonable match for you, go ahead and use them. LLVM was created EXACTLY BECAUSE these systems often are not a good match. They force you to meld to their type system, their runtime, and generally their world view. If your language does not match this world view (most interesting ones don't), all sorts of contortions must be done to deal with the VM. These are no worse than those required for LLVM, and in fact it is possible to implement Java and MSIL on top of LLVM. In many cases, targetting LLVM is much easier than targetting either JVM or MSIL, depending on how different your language is from Java or C#.

To me, the only other plausible option is to write an entire VM/runtime that is specific to your system. Please believe me (from experience) that this is a non-trivial exercise if you plan to do an even somewhat decent job.

I agree with Mark: "bang for the keystroke" is one of LLVM's main compelling features. We have several companies using, building on, and extending LLVM (for example, using LLVM to JIT compile shaders for 3d programs, to build code generators for reconfigurable logic devices, to build next-generation extensible programming languages, etc) and a wide range of academic users. LLVM continues to improve at a breakneck pace, and there are no plans for it to slow down.

-Chris

First, I want to again make clear that I'm not criticizing LLVM per se, only its appropriateness in a particular context. I'm sorry that my comments have appeared negative towards LLVM. The only reason LLVM comes in for negative feedback is if it's promoted for a purpose for which it isn't suited, and that's what I originally responded to in this case.

While I understand that you want to defend LLVM here, for the sake of the clarity of the original discussion I need to point out that most of the information you've given isn't really relevant to that discussion. The specific context is the appropriateness of having a project like Alice somehow make use of LLVM. The Alice project chose to implement its own high-level VM, SEAM. Some of the reasons for that choice have been discussed in this thread.

The point I originally made is that as of right now, LLVM is not well-suited as a VM for functional languages. There are at least two aspects to this point, summarized in my first message above, entitled "Ob. grinch...". One aspect is the question of tail call optimization, which as I've acknowledged could be addressed in future, even though LLVM currently doesn't support it.

The other aspect is the question of the "fit" between the high-level requirements of a higher-order functional language, and a low-level VM. Alice and SEAM provides an excellent example here: at what level would its high-level services be implemented on top of LLVM, and what would the tradeoffs be, vs. the current Alice/SEAM approach? Given the need for these high-level services, do you think there are no benefits to a high-level VM, or are those benefits somehow entirely outweighed by other benefits which LLVM provides? My assessment is that the benefits to a project like Alice aren't likely to be worth the effort required to use a low-level VM, especially in initial versions.

Again, for the sake of clarity, I'll respond on your specific points:

RE: Emitting LLVM vs emitting C:

RE: Tail calls: ... Strangely enough, you sited the exact documents laying out how they will be added to LLVM when the time comes.

RE: High level virtual machines: If something like CLR or JVM is a reasonable match for you, go ahead and use them.

To me, the only other plausible option is to write an entire VM/runtime that is specific to your system. Please believe me (from experience) that this is a non-trivial exercise if you plan to do an even somewhat decent job.

I agree with Mark: "bang for the keystroke" is one of LLVM's main compelling features. We have several companies using, building on, and extending LLVM (for example, using LLVM to JIT compile shaders for 3d programs, to build code generators for reconfigurable logic devices, to build next-generation extensible programming languages, etc) and a wide range of academic users. LLVM continues to improve at a breakneck pace, and there are no plans for it to slow down.

I don't doubt LLVM's utility in general. I'd note that those applications of LLVM which you mentioned are presumably not using higher-order functional languages.

If I'm wrong about any of this, the best way to demonstrate it would be to show that there are serious functional languages implemented successfully on LLVM. If there aren't any, I submit that the points I've made are likely to be a factor when anyone does consider such an implementation. The comp.lang.scheme thread which I referenced in an earlier post shows that there are Scheme implementors with this perspective. However, the issues in question extend beyond Scheme, to any higher-order functional language.

The usual requirements of FPLs aside, the design of Alice relies on two central services that have to be provided by the VM:

• Pickling: a universal marshalling mechanism that includes code and supports configurable import/export transformations is absolutely crucial to the whole framework. Compiled components are actually pickles, and all distribution uses pickling. Basically, pickling has to be implemented on the same level as GC.

• Transients: are the generic, low-level representation of futures and support implicit data-flow synchronisation. Concurrency, laziness, dynamic linking, and just-in-time compilation all rely on this mechanism. For efficiency, VM and GC must be aware of transients and encapsulate them as far as possible. Transients also interfer with pickling.
  

Unfortunately, AFAIK, no existing VM or VM framework (besides Mozart) supports either of these features appropriately. LLVM wasn't even available when development on Seam started (in 2001).

Same VM as used by Mozart/Oz, indicating the software libraries should be interoperable.

Unfortunately, that is only true for versions <1.0. The Seam VM used in the newest release is different from and incompatible with Mozart.

While I'm in no way associated with the project or familiar with how the decisions were made, I do know something about what SEAM actually does.

To someone in need of a VM with requirements such as those of Alice (described elsewhere), LLVM doesn't look like a solution that's "close, but missing minor features". It doesn't even look like a VM - it's just a small part of one. I wouldn't even call it a VM; I'd call it a JIT-capable compiler back-end. The most important concerns aren't just "not currently implemented" in LLVM, they're entirely outside of its scope.

Interfacing a language such as Alice to LLVM probably wouldn't reduce the work involved in the project significantly (compared to SEAM, it would probably increase the amount of code that would need to be written; seriously, look at the SEAM source code before accusing them of wasting effort, being written over a period of 3-4 years is different from taking 3-4 years of effort to write).

If you're going to assert that "project X shouldn't waste their time doing Y, they should be doing Z", you should be prepared to demonstrate that you have a detailed understanding of what they really have been doing so far and what your suggestion would involve.

Some of the worst project management decisions are of the form "lets use this third-party technology - it seems close enough (if we ignore most of the details)".

LLVM is certainly worth considering as a compiler back-end, especially for projects that currently generate C. But as a VM framework, I have a hard time seeing it as anything but unproven (especially given past exaggerated claims).

Even as a compiler back-end, I'd be cautious including something as massive as LLVM into a project as anything other than a replacement for a C-based back-end. Compared to a simple native code generator (e.g. the OCaml native back-end), the performance advantages would probably be in the 10-20% range, while the increase in code generator size would be an order of magnitude.

Anton's line of thought is obtuse.

LLVM is lower level than C, the language in which other existing, successful VMs are developed.

The root of the confusion is in this very first sentence. LLVM is not a system designed for implementing VMs, it is a (kind of) VM itself, so the comparison to C here is misleading. The fact that C has been used to develop successful VMs for functional languages has little bearing on LLVM's usefulness as a VM for functional languages.

This feature makes compiler optimizations easy.

Yet it supposedly imposes constraints not found in x86 assembly.

LLVM imposes constraints if you are attempting to compile a functional language directly to LLVM. Those constraints exist because LLVM was apparently not developed with functional languages in mind. If you read the LLVM notes I linked to, it's pretty clear that the plans for functional language support are an afterthought.

LLVM may be lower level than C, but it still implements a traditional call stack, more or less the same way that C does. In that respect, LLVM is higher-level than any assembler, and C-like, which becomes a problem if you're trying to do something other than C-style function calling. These constraints certainly don't exist for any assembly language.

You're damned if you do, damned if you don't: VM authors are happy with C on one side, and happy with x86 on the other, but cannot be happy with LLVM in the middle. I don't buy it.

VM authors are "happy with C" (to an extent) as a language for implementing VMs. For that purpose, LLVM doesn't buy them anything. Again, LLVM is not a language for implementing VMs, it is a VM, and one with a feature set which is currently lacking with respect to implementing functional languages.

Assembly languages are rather irrelevant here: at some level, whatever happens has to reach machine code, and the point is that assemblers and machine code don't impose the kinds of constraints that C or LLVM do.

Meanwhile it's not even contemplated that one can implement a high-level VM on a low-level foundation, because why not just do it with C.

Well, I guess we no longer care about the problems of translating functional languages to C.

Translating a functional language to C, and "implement[ing] a high-level VM on a low-level foundation", are two different kinds of projects, with different requirements and constraints. For example, when implementing a VM, you get to exercise a lot of control over the resulting VM's behavior, such as how it deals with its call stack. We still do care about some of C's problems, but LLVM doesn't currently offer any solution to those problems, so offers no benefits here.

The fact that some things haven't yet been done with LLVM is not a constraint against doing them. Anton gives assertions about constraints, assertions about LLVM design that I do not buy.

My point isn't technical anyway. It's project management. I tried to make that clear in my last post. Open-source people talk about missing features as if the only choices were to wait for them to show up or write them from scratch in a new project bubble. The missing third choice is to contribute code deltas to another project that is close(r) to the goal.

My point isn't technical anyway. It's project management. I tried to make that clear in my last post. Open-source people talk about missing features as if the only choices were to wait for them to show up or write them from scratch in a new project bubble. The missing third choice is to contribute code deltas to another project that is close(r) to the goal. That's my argument. Adding (relatively minor) missing features to LLVM, or building on top of LLVM as the case may be, takes less work than writing (relatively major) JITs and VMs from scratch, and yields much more bang for the keystroke.

The claims of "relatively minor" and "less work" are speculation at best, and a good project manager would want to back that up with some solid technical information.

One important factor being ignored here is that SEAM and LLVM actually have few goals in common. The fact that both can be referred to with the acronym "VM" is perhaps misleading. SEAM concentrates on high-level services, which fall outside LLVM's scope, and would have had to be developed anyway to support Alice. SEAM development seems to have been done in C++, so it's not as though the SEAM project is spending a lot of time worrying about e.g. native code generation.

This leaves me wondering what, specifically, is the synergy that you're seeing between these two projects? How do you see Alice's high-level services being implemented in a combined project — at what level? Have you thought about the implications for the Alice compiler and runtime system? Overall, I'm seeing a lot more work for no clear benefit.

If SEAM was started in 2001, then it has taken 3-4 years to write. That's a lot of opportunity cost for the Alice language.

With all due respect, among the initial investigation that Anton has discussed and linked to, the lack of addressing of Anton's issues in the replies, and the tone of "we built the perfect universal machine; you're stupid not to use it," I'm afraid that I've lost all interest in learning more about LLVM. I'm sure it's a very nice new back end for C and C++, but to put forth a Scheme implementation that doesn't actually implement Scheme due to limitations imposed by LLVM and then browbeat other people implementing extremely advanced functional language systems for not using LLVM takes what my wife would politely call "chutzpah" and what I'm inclined to call "big brass balls." I prefer to continue to investigate C--: at least Ramsey and Peyton-Jones are intellectually honest about what shortcomings C-- has.

Thanks, Paul.

Since I raised the issue of limitations with the Scheme implementation for LLVM, I should also point out that it is provided by a user of LLVM, and isn't an official part of LLVM. The web page makes it clear that it's a toy implementation. However, the page doesn't mention the specific limitations relating to tail-call optimization, which can be a bit misleading if you only read the web pages (that's unintentional, I'm sure). The fact that a more complete and correct implementation of Scheme (or ML, Haskell, etc...) could be quite challenging is not immediately obvious.

However, I definitely didn't intend to create a negative impression about LLVM in general. A little while back, I promoted Chris' LLVM 1.4 announcement to the home page, because I think it's an interesting system with plenty of potential, and clearly relevant to LtU's scope.

But I think Ville-Pertti Keinonen put it well: LLVM and SEAM are pretty much orthogonal. I would add that something similar is likely to apply to other high-level VMs for functional languages. I have no doubt that LLVM could be modified to support compiling a functional language with tail-call optimization, but that still wouldn't address the sorts of issues that SEAM and Alice address.

The technical point which hasn't been discussed in any depth is what place something like LLVM would have in the presence of a sophisticated runtime environment of the sort which Alice & SEAM provide. The answer to that isn't obvious to me, but in the absence of a clear vision for the benefits of integrating the two, it seems premature to me to be concerned with it.

BTW, I agree that C-- is promising. The fact that it's specifically intended to support the implementation of functional languages is important. The papers about C--, like C--: a portable assembly language that supports garbage collection, provide some insight into some of the issues that have been raised in this thread.

Consequently, my strongly-worded previous post was intended more as a response to the style of the LLVM developers' posts here than as a reaction to whatever technical limitations LLVM may or may not have: the tone struck me as an extremely unpleasant cross of proof of suitability by repeated assertion coupled with neglect of attention to the stated objectives of the Alice/SEAM team or, for that matter, anyone else who may deem it necessary to develop a new virtual machine in support of their language design goals. I've already felt the need to abandon participating in an initially-promising open source project once over the past year due to social issues. Unfortunately, my perception of LLVM is now tainted by similar considerations due to its representation here. It really is a shame: LLVM as technology still has considerable notional appeal thanks to its emphasis on full-lifecycle optimization strategies and its improving support of the PowerPC processor family. But the argument over Alice and SEAM leaves me wondering whether those who have chosen to represent LLVM here really understand functional language or virtual machine design or, even more importantly, how to make whatever case they have to an understandably, and I would say in the case of Oz/Alice, correctly, skeptical audience.

Finally, I should admit that part of what appeals to me about C--, apart from coming more from the functional community, is an emphasis on rigor. I like that C-- has a formal semantics. In fact, given that it does and is written in O'Caml, I wonder if there isn't some way to combine MetaPRL, C--, and Confluence to arrive at provably-correct-from-source-code-to-processor software/hardware development.

AOL and so on, you're correct, I should have added a bit more information on my web page. I just didn't believe that anyone would look at it, modulo for educational purposes learning LLVM-assembly or something.

Last week I tried out Seam, and now I ran into this thread. Seam feels like a nice code base for implementations of HLLs. It's not so well documented, but the code is easily readable. Since I like learning by implementing, I've made a small Scheme-interpreter for Seam (there is a scheme interpreter included in Seam source as well, but it wasn't in sync with the rest of the system), I've linked it from the infamous llvm-scheme-page, but nah, don't look at it yet, it's Ugly :). Note that there isn't any VM-language in Seam, only the datastructures needed for stackframes, threads, GC, etc, which makes it a bit wierd to directly compare to LLVM. So one could maybe use LLVM as the compiler to instantiate native code in Seam instead of using Lightning which I think they use for Alice right now.

LLVM is a well written system as well, but its size makes it feel a bit unwieldy to use. llvmc probably makes it a bit more comfortable. They will probably need some people working on GC and some of the optimizations mentioned before any HLL implementor dares to use it as its target VM/language. But I hope that LLVM will continue to be developed considering the amount of work put into it, and maybe especially interested in the automatic pool allocation algorithms described in publications which I hope will be included in LLVM someday. I wish that LLVM will be the future GCC someday..

To make a complete scheme LLVM-implementation would probably be quite challenging, as hard to compile to any "low level" intermediate language. When I used the system, there wasn't any existing GC, and the framework for GC was a bit sketchy, but maybe that's solved now. I don't think LLVM have any support for VM-threads, if you want to easily implement an Alice/Oz-like language.

As summary I would like to say that there is a big advantage with the S in Seam.

(first post at this forum :)

Mark, I'm saying that not only are there are solid technical reasons why LLVM is not currently an attractive choice for the ways in which you'd like to see it used, I'm also predicting that this won't easily be resolved in future. When I suggested that "it might be suitable in future", I was saying that as a theoretical possibility, i.e. I wouldn't rule it out entirely. However, I don't believe that attempting to retrofit functional language support into LLVM would have saved either the Alice/SEAM or Mono teams any time at all — instead, I believe it would have cost them significant time, perhaps also slowing down LLVM development because of conflicting requirements.

You've been wondering why no-one is doing what you suggest, and arguing that they're all wrong and you're right, all the while ignoring the simple explanation: it's not technically very appropriate, and for that reason, not appropriate from a project management perspective either. You apparently don't believe that, but you haven't even attempted to address the point from a technical perspective.

You've made some broad claims, such as "the basic fact that cooperation beats duplication to hash technical minutiae" - which assumes that we're talking about minutiae, when my whole point is that that's not the case; and "SEAM would have been done faster", which is an unfounded assertion for which you have given neither evidence nor any argument beyond the general idea that, essentially, larger projects are better. I can understand how you've gained that impression from watching the development of open source software, but it's not a law which can be applied indiscriminately to any two somewhat related projects.

As for Mono, the common thread between the two discussions is that in both cases, you were pushing LLVM and criticizing the choices made by some very competent people working on successful projects, while showing little grasp of the technical issues that made LLVM inappropriate for those cases. For the record, I don't consider .NET, and by implication Mono, an ideal target for functional languages either. Mono and LLVM weren't a great match for other reasons.

[P.S. The argument that "If it can be built from scratch, then it can be built into system X" is hilarious. Surely that's not intended seriously. I take it you don't believe that software architecture or design are important disciplines?]

Anton has done an excellent job of examining LLVM and providing concrete references as to why it wouldn't be an appropriate fit for Alice today, let alone four years ago. I rather strongly suspect that he could do the same for C-- or Mono or the JVM (shudder) if he felt inclined to waste the time.

Thanks again. I think C-- could have been a much more promising target, had it been sufficiently far along at the time (did it even exist then?), for the simple reason that it is explicitly designed to support functional languages.

Another point which hasn't really been discussed is that Alice is a research project, or if that's too simple a characterization, research is certainly one of the major motivations behind it. That makes its goals quite different from those of the average non-research open source project. The freedom to design their language's core to do what they need it to do is important, and it would be very unfortunate to see that compromised because e.g. LLVM needs to remain a pragmatic choice for the compilation of C++. I think situations like that would have been quite likely to occur had they joined forces — the flip side of the big collaboration model is that it often makes for bigger compromises.

As for Mono/.NET and the JVM, it's well-known that they can support functional languages, but also that they're not ideal platforms for them. The main point that makes LLVM any different from these platforms, for the purposes of this discussion, is that functional language implementations don't yet exist for LLVM to demonstrate the point either way — other than that toy Scheme, which demonstrates some of the current limitations of LLVM for functional language compilers.

Once again, I feel the need to say that LLVM seems like an excellent project for the purpose of implementing C-like and other imperative languages. Nothing I've said is intended to detract from its suitability or worth in that context, and I apologize to Chris Lattner and other LLVM authors for the negative-seeming discussion.