Lambda the Ultimate

I agree with many of your points. I'm not advocating Fortran, but a more modern language like (modern) Scheme or O'Caml, perhaps with some domain specific tweaks. These language have several advantages: they make compiling them easier, and speed is always a problem in my experience, and high-level operations (such as pattern matching and array comprehensions) make algorithms clearer and hence raises the bar for what is 'obviously' correct.

Right, so, like I said: 99% of R users don't care about ease of compilation or " 'obviously' correct" algorithms. For the most part they care about getting their job done. At best the things that make language designers and researchers happy are orthogonal to this task and a hindrance at worst. Nobody ever says "wow, language X's ease of compilation made fitting my non-linear model a breeze!" The only compelling reason for switching away from a special-purpose statistical language to a more general purpose language is to take advantage of the libraries available for the language, not because it makes data analysis any easier.

I disagree with practically every statement you make:

R users don't care about ease of compilation or " 'obviously' correct" algorithms

In the statistical work I've done (e.g. clustering HMMs) speed is really important. If something takes a week or more to run and I can make it run faster with very little effort I'm really happy. Other people I know in the area (statistical machine learning) have the same problem. A high-level language that can be easily compiled would be a real boon. Furthermore, as you say "Anything the statistician codes is, in some sense, suspect since there's no assurance that the results you get aren't due to a bug in the code" so anything that raises the bar for 'obviously correct' algorithms is a big win as well. This is "getting their job done."

At best the things that make language designers and researchers happy are orthogonal to this task and a hindrance at worst.

I've used R and I've used Matlab, and if they had pattern matching and array comprehensions it would be a lot easier to write complex algorithms in them. If they had clean semantics they could be easily compiled; see above.

So in conclusion I argue that a better language makes development faster (less code must be written; code has less bugs) and gets results faster (code runs faster). Besides, the so called "special-purpose statistical languages" aren't really that special (with the exception of Mathematica) from a PL point-of-view. Sure they tend to have some nice notation for arrays-slices, and overloaded operators for arrays, but that could be easily accommodated in a modern general-purpose language, and modern languages have features far in advance of that in, say, R.

It's reasonable to disagree with the reasons why R has the primary marketshare among academic statisticians (among whom I'd include myself). And I wish the situation was different, but if you want to understand the social reasons for why the situation is as it is, I would back Byron up by seconding the opinion that R has so many users because (1) those users could easily "port" legacy code / coding practices (e.g. syntax) from S into R (2) for the most part they don't implement CS-style algorithms from scratch; much of the day to day work is ad-hoc data analysis and so an interactive language with access to a wide array of statistical libraries is paramount.

There are, as you explain, many reasons why it would be good for the statistical community to shift to syntactically sugared version of OCaml or Haskell or Lisp/Scheme/Qi. But the way to get this to happen is to make it easy for non-specialists to run their code in the new system and only gradually enforce type-safety / side-effects control.

For these reasons transitioning to something like Qi (possibly with even more syntactic sugar, so it looks more like Javascript/R) would be a good first step, in my opinion. And the way to get that to happen is to form a community of motivated statistical programmers to build the language / libraries that would make it possible. And this is also sociologically hard, especially in the face of good alternative half-measures, like SciPy, which is doing a good job of drawing its own (more matlab-esque) community.

I'd be happy to discuss things more with anyone interested in a serious effort to develop a serious alternative to R, or lend some of my time to the effort.

But, by printing do you mean formatted output as in srfi 48?

I know that R needs a better implementation, preferably a high-quality incremental native-code compiler. An R to Lisp or R to Scheme compiler could fit that bill, assuming the Lisp or Scheme compiler is suitable.

The paper harps on the pass-by-value semantics as a reason to move to an entirely new model, but I'm not convinced that this is an insurmountable obstacle to a high-performance implementation of R.

Does R currently copy it's values lazily? That way it's just pass-by-reference if you never mutate the structure, and (possibly parts of) values only get copied if they get mutated. I haven't thought this through carefully enough, and I think parts of this scheme would get rather hairy, but I would guess that a good lazy-copy technique would largely ameliorate the overhead of copying.

There have been some efforts to create a native-code compiler or bytecode compiler, but as far as I know, they've never really gotten off the ground very much. They've seemed promising, but haven't seemed to get past the experimental stage.

I know of at least two of them:

1. RCC, something that seems to have been based off of John Garvin's Master's Thesis, and

2. Some experimental work by Luke Tierney (again, of Lisp-Stat). He has some stuff on his website (http://www.cs.uiowa.edu/~luke/R/bytecode.html, and http://www.stat.uiowa.edu/~luke/R/compiler/), and an interesting conference paper, but as far as I know it never got any further. In newsgroup posts, he seems to indicate that usable compiled R isn't likely to appear from him anytime in the forseeable future.

In general, I get the impression that the R community is focusing on parallelizing things as a way of improving performance. I would go so far as to say that this approaches the level of "we will parallelize things, and that will address the speed issue," but that's overgeneralizing. In their recent paper, Ihaka and Lang discuss why parallelization is not going to solve all of R's performance issues.

Ehh... there are many reasons to parallelize something, but I seriously question the wisdom of focusing on parallization for purposes of performance when there are significant scalar gains left on the table.

I've seen both of those experiments. A less conventional approach would use Lisp or Scheme as the target language. ETOS, an experimental Erlang to Gambit Scheme compiler showed some promising initial results.

Obviously you'd want a Lisp implementation that has particularly efficient floating point support, and a significant portion (a majority?) of the effort would go into providing high performance, high quality numerical algorithms.

Formally speaking, I believe R evaluates arguments lazily and sends promises/thunks as arguments. On this basis, perhaps a translation into monadic Haskell with sutiably defined universal types to account for the dynamic-type coding style would be more direct. Can anyone comment on this from a technical perspective?

Nevertheless, I think an R to scheme compiler (extending Tierney's work) could fill a useful niche, especially because I think the great majority of *user* R code is compatible with a strict, call-by-value evaluation semantics which would translate well into scheme. As you mention, if a function "modifies" an argument, it actually modifies a locally-scoped copy of the argument (except for environments which are passed by reference only), but this seems like something that could be translated accordingly.

A somewhat messier aspect, from the scheme perspective, is that many of the common library functions operate like special forms, because they textually inspect, delay the evaluation of their arguments, or modify their evaluation environment. Additionally, in R terminology, many functions are "generic," which means that they dispatch based on the class of their argument (and there are S3 and S4 object orientation systems in R). I presume that this could be translated, but I don't know how messy it would be.

So, for example, the plot function will look at the class of its arguments to dispatch the right plotting code and at the text of those arguments to label the plot. Similarly, statistical modeling functions, like lm for linear models, use a "formula" language so one can say lm(y~x, data=mydata), to mean to regress y on x using the data in mydata (which could be a data-frame (i.e. table) or an environment, which are themselves first-class).

R functions that need some of these special-form type features might benefit from a little manual annotation (regarding which arguments aren't strict) and a customized translation of common idioms. This might be a fairly large undertaking when you consider all the contributed library code.

As far as formal translation goes, though, R uses lazy evaluation ("promises") and allows for a lot of introspection and modification of evaluation environments. In this sense, properly speaking, R functions really are functions and not special forms its just that the evaluation semantics are different. In principle, I suppose, one could turn everything into a thunk and emulate the environment structure with scheme data structures and on and on.... I could be wrong, but if one really made literal and completely general translations of these language features, my suspicion is that there would be a substantial amount of overhead involved so that the benefits of translation might be disappointing.

Accordingly, a complete translation might be possible, but actually I think the most powerful/practical approach would be to let the programmer select different translation protocols for different blocks of code.

So a good short-term step might be to embed a scheme compiler into R (guile?) and allow an R user to annotate blocks of code for translation into scheme, compilation, and subsequent execution within the R run-time environment. Blocks of code that the programmer certifies will only operate on objects of certain types or obey certain semantics (e.g. strict evaluation, no side-effects on external environments) could be given especially efficient translations.

What do you think?

Guile is an interpreter, and one that doesn't perform very well at that. So that seems like a rather pointless endeavour to me. I'd stick to an incremental compiler such as Larceny or Ikarus.

I don't believe that Haskell's lazy evaluation could be leveraged very effectively here, due to R's ability to combine promises with side-effects, even if the side effects are local.

Honestly, I've only played with R in a rather cursory fashion, though I have promised a friend to learn more R over the next few months for a possible collaboration we've been kicking around.

Objects and promises shouldn't be too hard. I'm a little less clear what exactly your third point entails, something like macros but not exactly. It sounds like they involve run-time computations, which I would not know how to deal with very well.

After a quick stroll through R's somewhat sketchy language "definition", what worries me is the environment and stack introspection facilities. I'm not clear how R uses the environment introspection to do something akin to macros, or if you are referring to something else entirely.

In my estimation, this would be quite an obstacle to an efficient R to Scheme translation.

I also don't know R at all well (I've played with it a little, but that's it). But the notion of environment introspection makes me wonder if a language like Lua would be a better target than a language like Scheme. The "everything is a dictionary" mentality which is so prevalent in Lua (and Python, Ruby, etc.) is very much absent in Scheme.

Hmmm. I'm not sure, although I see your point. R environments do seem analogous to Python /Lua dictionaries. Surely there's a scheme way to express this too, right? (mutable hash-tables) Oh, but your point is that then you wouldn't be able to inspect the global environment and such without additional overhead (to maintain the imitation global environment as a scheme-level object after every assignment), unless the scheme implementation exposed its own environment-based implementation directly. Do any schemes do that?

I should clarify, though, that most user-level programmers don't use environments. And, except when it's really necessary, environments would be used, not for introspection into the system environment, but just as a data-structure. For this reason I still think most user-level code would translate nicely into scheme. It might not be *decidable* that naive translation would correctly copy the semantics, but the author of the code could stipulate that they didn't do anything "evil," and then it would.

(R environments also have parents that they "inherit" from, so I think technically they'd map onto Python classes better than dictionaries as far as that goes; I'm not sure about Lua.)

Idiomatic R code mainly uses "list" data structures anyway which operate like a dictionary (they can map keys into values), but they are immutable (I guess copy on mutate would be a more precise way to explain it). It's confusing because the syntax is so similar, so I'll give an example.

Python:
>>> d1={'a':1, 'b':2}; d2=d1; d1['a']=3;
result: d1=d2={'a': 3, 'b': 2}
R using lists: (different semantics, despite similar appearance)
> l1=list(a=1,b=2);l2=l1;l1$a=3;
result: l1=list(a=3,b=2), l2=list(a=1,b=2)
R using environments: (like Python)
e1=new.env();assign('a',1,env=e1);assign('b',2,env=e1);
e2=e1;assign('a',3,env=e1);
result: e1=e2 and e1$a=3 and e1$b=2

R environments do seem analogous to Python /Lua dictionaries.

Well, I don't know enough R or Lua to really say... but an efficient translation from R to Lua would be little more than an academic exercise given the current Lua implementation. Although somebody's working on an LLVM-based implementation of Lua, so this might someday be practical. It sounds like they are currently up against similar kinds of challenges to those we are discussing.

Do any schemes do that?

I suspect we are on the same page when we use the word "environment", but just to be sure, environments map variable names to values. A naive environment-passing interpreter might construct a new environment on entrance to a function, and restore the previous environment when a function returns, say by using a stack of hash tables, or a persistent association list or tree.

Yes, some Schemes do actually work this way, but they are toys that aren't really worth using. Instead of representing environments via explicit data structures, good compilers represent environments implicitly: some values are represented on the stack and others are stored in optimized, heap-allocated closures.

You could write a naive R to Scheme compiler that explicitly uses hashtables to maintain R environments, and run a fancy compiler on the result... but then you've destroyed one of the biggest reasons to use the fancy compiler.

R6RS does have some support for environments as first-class values, but they are limited. Their intended purpose seems to be for creating custom REPLs and extending applications in Scheme via "eval". Chez has something similar.

But, as I understand R, (and please do elaborate or correct me!) it sounds like you can basically get ahold of the environment you are currently in, as well as the environment of the calling function, and so on up the call stack.

There is one deliciously evil hack that occurs to me: abusing a built-in debugger that you can get programmatic control over. With a little luck, you could support introspection without paying the price until you actually use it. This might enable one to implement environment introspection while still making good use of the implicit environments a fancy compiler generates.

Chez includes a good debugger, and it might have enough features to support this kind of misadventure, but Chez is proprietary and very expensive. I don't know about Larceny, and Ikarus is new and doesn't have a debugger yet.

I should clarify, though, that most user-level programmers don't use environments. And, except when it's really necessary, environments would be used, not for introspection into the system environment, but just as a data-structure.

I guessed as much, and one could legitimately ask whether or not we could get away with dropping support for introspection... after all, we are translating to scheme, so it's likely that we'd support TCO and thus change the semantics of stack introspection. (although not doing TCO when using compiler that does TCO is easy enough.)

But, from a sociological point of view, the more drop-in the replacement is, the better. Prospective users need their extension packages... and while it may or may not be realistic to support the same foreign API, it would be nice that "pure" R packages would just work.

Another possibility would be a conservative, static analysis for when code won't use introspection, and choose a translation strategy accordingly, but due to R's object-oriented method dispatch, I don't think you could make the analysis accurate enough to be useful without also making it unsound.

R allows people to write imperatively, while prohibiting some of the worst trangressions. The current implementation does have the curious sociological benefit of encouraging users to learn to write more functionally by severely penalizing imperative code. In all fairness it penalizes some functional idioms too.

Any opinions on Lush (especially regarding string processing)?

The location for the PDFs seems to have changed slightly, but they are still freely available. Just go to http://jstatsoft.org/v13 for the issue's table of contents, and use its links to individual papers.