Lambda the Ultimate

I would like to call the attention of LtU readers to some ongoing language design efforts in the XQuery standards community. Regardless of my ridiculous opinions about current proposals (some of which I've shared below) I think we can all see that this community-based language design effort is likely to have huge impact: many important systems will be built using the language design that emerges. So, the zero-order point of this post is just to offer some hopefully orienting links, and then I'll opine a little bit, hoping to add something new:

It all starts with the XQuery 1.0 standard. If you are utterly new to it, like I was not long ago, there is a product manual that rewards a quick skim with the gist of what XQuery is about. It is an Introduction to Berkeley DB XML (an open source product).

XQuery is a pure, functional language taking XML types (hereafter "XDM" for XML Data model) as its value typing system. It (mostly) lacks higher-order functions. It is an expression language with expressions taking and returning named tuples or anonymous lists of values. Tail call optimization is provided. Closures and continuations are not. That is where recent developments start.

Three proposals have come to my attention. All are very nice in their ways (though, I opine below, each is a mistake). These proposals are:

1. XQuery Update Facility which introduces a monadic style of I/O to XQuery, mainly by adding new value types which functions may return (the type of "pending update" values).

2. XQueryp which introduces sequencing operators (operators to control execution order in this formerly pure language).

2. (D. Chamberlain, K. Beyer, L. Colby, F. Ozcan, H. Pirahesh, and Y. Xu) Extending XQuery for Analytics. Proceedings of the 2005 ACM SIGMOD Conference, Baltimore, June 2005. which adds an interesting ad hoc kind of list comprehension to XQuery, inspired by SQL's "GROUP BY" and related constructs.

So, free of my opinions: it seems that there's a fairly serious effort afoot to turn XQuery into a general purpose systems programming language for web applications. I sense from the literature that the crossover of db-expert and language design experts hasn't been all that strong, in this area. I hope that among the audience of LtU, some language design experts might help change that.

So, my opinions, which are naturally unjustifiably critical and self-promoting:

I think that the proposed sequencing constructs and update facility are superfluous. Without any changes at all to XQuery 1.0 I was able to add monadic I/O along with a generalization of closures and continuations in XQVM. My solution is a non-intuitive way to achieve the same aims but I'm finding that it works out very nicely.

The addition of a "group by" construct to XQuery seems a mistake to me. It is just syntax -- it can be trivially translated into strict XQuery 1.0 in a way that implementations should have little difficulty optimizing. The literature around the issue has just been overlooking that transformation. (They are just about all assuming that the transformation should use the "fn:distinct-values" operator and the optimizer will have to cope with that. If they tried solving the same problems without using that operator, they'd probably discover the transform I have in mind.)

My opinions aside: what should really happen to XQuery? What are other takes on these new developments?

I was watching the interview with Dave Thomas. Dave mentioned very early in the interview Smalltalk has a "keyword syntax" which makes it easy to implement (embedded) DSL.

What's "keyword syntax"?

And, what makes a language a good platform for (E)DSL?

I know Haskell has been a good platform for doing EDSL. It looks like to me its Type Class and high-order functions enable us to implement EDSL. But, are they essential? LISP doesn't have type class, but i think it's also a common candidate for EDSL. So, what are the essential language features for EDSL?

Luke Simon, Ajay Bansal, Ajay Mallya and Gopal Gupta Co-Logic Programming: Extending Logic Programming with Coinduction 2007

In this paper we present the theory and practice of co-logic programming (co-LP for brevity), a paradigm that combines both inductive and coinductive logic programming. Co-LP is a natural generalization of logic programming and coinductive logic programming, which in turn generalizes other extensions of logic programming, such as infinite trees, lazy predicates, and concurrent communicating predicates. Co-LP has applications to rational trees, verifying infinitary properties, lazy evaluation, concurrent LP, model checking, bisimilarity proofs, etc.

It is nice to see that coinduction is making its way into Logic Programming.

I couldn't find a free link to this paper [Edit: The link now points directly to the paper], but I found the following useful slides on Gopal Gupta's webpage. Slides from ICLP'07

I wrote a tutorial a couple months ago on programming models for shared-memory concurrent pseudorandom number generation:

http://www.cs.berkeley.edu/~mhoemmen/cs194/Tutorials/prng.pdf

It was meant for upper-division computer science undergraduates, but I was wondering if you all think it has potential to be adapted for more general use.

The article argues for making PRNGs efficiently thread-safe by choice of programming model, and offers examples of how different kinds of parallel PRNGs fit into the offered models.

mfh

Solomon Feferman. Gödel, Nagel, minds and machines. Ernest Nagel Lecture, Columbia University, Sept. 27, 2007.

Just fifty years ago, Ernest Nagel and Kurt Goedel became involved in a serious imbroglio about the possible inclusion of Goedel’s original work on incompleteness in the book, Goedel’s Proof, then being written by Nagel with James R. Newman. What led to the conflict were some unprecedented demands that Goedel made over the use of his material and his involvement in the contents of the book - demands that resulted in an explosive reaction on Nagel’s part. In the end the proposal came to naught. But the story is of interest because of what was basically at issue, namely their provocative related but contrasting views on the possible significance of Goedel’s theorems for minds vs. machines in the development of mathematics.

This is not directly PLT related, and more philosophical than what we usually discuss on LtU, but I think it will be of interest to some members of the community.

While the historical details are interesting, I am not sure I agree with the analysis. It would be interesting to here what others make of this.

To make this item slightly more relevant to LtU, let me point out that both the LC and category theory are mentioned (although they are really discussed only in the references).