I suspect that using a clean, minimalistic language basis felt right for building a new language. And PLT is well ported all over the place.
But actually, I predict that we'll eventually start to see lots of arc implementations riding on top of lots of different Lisp implementations: sbcl, but also gcl, guile, chicken, maybe abcl, sisc . . . And that sounds cool to me!
I hope that arc keeps a canonical and authoritative implementation. One of the big problems keeping many people from deploying Lisp applications is the uncertainty and difficulty in choosing a particular implementation. It can also end up fragmenting developer time and you will inevitably end up with incompatible but extremely similar arc implementations everywhere.
One or two canonical implementations is fine, but there should be one authority for the language and it should be a fairly good implementation.
I think the axiomatic approach is intended to stop this. Lisp suffered because the spec was complex and ambiguous. To port Arc, just port the axioms, run the "spec" et voilà, you have a conforming implementation.
It should be noted that pg intends to implement more of Arc in Arc, when he gets the time.
In fact I have an implementation in SBCL half way (it basically can load arc.arc, but I haven't bothered with network/thread functions yet). To solve the call/cc problem I got to the point of doing a CPS transform, and since Arc has only 4 special forms (very few axioms, as you say) this was 'easy'...
It's not theoretically impossible that Arc could eventually be metacircular (by writing the Arc compiler in Arc). I think that would be even cooler than implementations in SBCL, etc. This would also maintain the authority of the canonical implementation.
Why do you think CL is easier to optimize that Scheme? This isn't a hostile question; I'm just curious. Intuitively, I feel like "purer" languages should be easier to optimize.
First, CL has in the standard many possibilities for making declarations reagrding optimization : for the functions you want, you can compile code, declare types (e. g. this var only holds fixnums), declare you want to optimize the speed and ignore type safety, etc. This way, you end up writing code the way you would write it in C. There is no such thing in the Scheme standard. Individual implementations could, of course, but as far as I know no one does.
Abother example is call/cc. This is a very interesting beast, only existing in Scheme. But it is hard to implement efficiently.
The last example I can think of is 'nil. Using nil as false and the empty list is very interesting in this regard : you can implement nil as the NULL pointer, which is also 0, the false boolean. Less manipulations to do on the bare metal. Distinguishing between #f and '(), on the contrary, implies making more tests at the lower levels.
re: call/cc - I think a bit of the lambda the ultimate series of papers eventually boils down to the realization that a machine language jump-to-subroutine is equivalent to a call/cc, and the target of the call/cc just has to access the return address on the stack as a function address.
I don't get it. There's the whole stack copying for call/cc, so call/cc is much more expensive.
(I read the "Lambda the ultimate GOTO" paper you referenced earlier; it's about goto vs structured programming, not call/cc. As an aside, it's very interesting to reflect on just how controversial structured programming was.)
Implementing call/cc efficiently has been well-reasearched in the Scheme community. For a very well-written account of a non-stack-copying implementation see
Then continue at ReadScheme at "Compiler Technology/Implementation Techniques and Optimization"
to see further developments (Look especially for Clinger's papers).
In a function call, the state (the current computation being done) is saved anyway, and therefore "copied" if that is your preferred term. So ideally, call/cc should have the same overhead as an ordinary function call; the only difference is that in call/cc the continuation state is the value given to the function, while in a function call it's just one of the values given to the function.
Note however that much of the theoretical analyses of call/cc make a basic assumption of a "spaghetti stack", which would mean that partially unwound stacks would be saved implicitly as long as any continuation exists which refers to that stack, and all stacks themselves are subject to garbage collection. Most machines don't actually have a spaghetti stack and can't make a spaghetti stack anyway ^^. That said a spaghetti stack could be implemented as a simple list, with push == cons and pop = cdr.
Alternatively store the local variables on a garbage-collected heap, and include a reference to the local variables with the continuation/return address (you'll probably need to save the pointer-to-local-variables anyway, since the target function is likely to use that pointer for its own locals). Again, no additional overhead over plain function calls, except perhaps to restructure the return address and the pointer-to-local-variables.
Don't know about MIT Scheme, but if I were to implement call/cc on stock hardware and compiling down to machine language that's what I'd do ^^
I'm still totally not understanding your claim that call/cc should have the same overhead as an ordinary function call.
I read the Clinger "Implementation Strategies for Continuations" paper and they found call/cc about 10 times slower than function calls on the tak/ctak tests. I tried those tests on PLT Scheme and the overhead I saw is even worse: .7 seconds with function calls vs 51.8 seconds with continuations on (tak 24 16 8).
Clinger says about the stack strategy: "When a continuation is captured, however, a copy of the entire stack is made and stored in the heap. ... Variations on the stack strategy are used by most implementations of Scheme and Smalltalk-80."
Components of function call: (1) put arguments somewhere (2) put return address somewhere (3) jump to function.
Components of call/cc: (1) put return address as argument somewhere (2) put return address somewhere (3) jump to function.
That said, continuations generally assume that "put X somewhere" means somewhere != stack. Yes, even return addresses are not intended to be on the stack when using continuations. The main problem is when compiling down to C, which always assumes that somewhere == stack. If you're compiling down to machine language where you have access to everything, then you can just ignore the stack, but not in C, which inherently expects the stack.
Ah, I get it. I suppose typing is one of the big issues affecting speed. If the language standard insists on dynamic typing, there might be no way to get certain kinds of optimizations.
And yeah, call/cc is probably always going to be a bear. But man is it cool. :)
I suppose this goes against what a few of us (including me) were saying above -- that the language and the speed are really separate issues. Or maybe it's more coherent to say that language standards (as opposed to "languages" generally understood) can have a profound effect on speed. If they don't give implementors a lot of choice, they can box people into certain corners.
It's interesting that Scheme actually mandates optimization in at least one case (tail recursion). I don't know how many language standards make those kinds of demands, but I suspect there aren't many.
Tail recursion is interesting as it is not especially an optimization for speed but as a way to make programmers rely primarily on functional programming : if you don't have it, functional programming is rapidly a dead-end as you can make the stack explode really fast. As a bonus, it is faster :)
You're absolutely right: speed is a property of programs/compilers and not languages. And because of this, there's really no reason why we couldn't have an implementation of Arc that compiles to C (using, perhaps, Chicken Scheme's astonishing method), one that targets the JVM, one that's designed to be embedded, and so forth.
But this is really a socio-political decision, is it not? Do we (either PG or this burgeoning community of fans) prefer a benevolent dictatorship of the sort that governs languages like Perl and Ruby, or do we prefer the ramified computational episteme of modern Scheme?
There are good arguments on both sides, but I really think that letting a thousand flowers bloom (as the Scheme community has done) has great advantages. We get to use Scheme in lots of varied environments, with lots of different hardware, and with implementations optimized for lots of specialized tasks. This abundance is in part facilitated by Scheme's minimalistic standard, of course, and that has its own drawbacks -- code portability being the most serious one.
Personally, I'm not sure I'm down with the idea of a lisp optimized for "web applications" or "exploratory programming." It seems to me that the strength of Lisp lies precisely in its ability to become a language for "x programming." Ironically, PG himself has made some of the most eloquent arguments out there for this idea.
It seems to me that implementors are the ones who should take Arc and turn it into a "language for hacking cell phones" or whatever. Some domains will put a premium on speed, others on "smallness," still others on "embededness" or what have you. Nothing in the language should foreclose these options, but as you said, it's not clear that languages ever do. In the case of Lisp, we could write a compiler in which every function and macro is converted directly into highly optimized assembly. I don't think there's anything in Arc or any other language that would prevent that.
As I have no doubt that it is possible to create an Arc implementation that delivers fast execution, it is precisely the socio-political issue that I intended to address in opening this thread.
As long as Arc is implemented in MzScheme, the best it can do is asymptotically approach MzScheme's performance. The discussion in this thread suggests that Arc will not forever be implemented in this way, so the limitation will be lifted. Just how much interest there is in greased-lightning performance is not clear to me.
I'm an English professor who does various kinds of computational analysis on large text corpora (so things like string handling, XML, and regex are really important to me). I've been known to write programs that take three weeks to run in Java, so I'm always looking for ways to make my programs fast without resorting to C. Nothing against C. It's one of my favorite languages. It's just not a lot of fun for string processing.
Basically, I always want to go high and fast with my languages, and that's one of the reasons I like Lisp. It's a super high level language, but (in my usage patterns) it outperforms languages like Ruby (which I adore) and Java (which I find increasingly annoying).
Now, my particular usage is perhaps a bit obscure, but it may generalize to other areas. I can't believe I'm the only one doing lots of text processing who wants a fast, high level language. In the end "web application programming" is really just a special case of text processing, so it may align with PG's goals at some more fundamental level.
