Lambda the Ultimate

You need to build it into the compiler, so Haskell, Ocaml, or PLT Scheme won't do.

It's a proof that specific implementations (compilers) are not good. This does not mean trivially that these languages are not good (for this "extraction" of SQL/JS out of the Haskell, Ocaml, Scheme code).

Also, a nit: the emphasis on needing compiler support for these things seems to be predicated on not having macros. In fact, Scheme and Lisp can do at least (a) and (b) above in an integrated fashion. SchemeQL is a good example of this.

Although I'm fairly sure it wasn't his intent, Philip is in fact making a great argument for the necessity of macros. :) This is particularly true if there's any interest in delegating significant tool-creation capability beyond the designers of a language.

Of course, the argument can be made that macros make Todd mad, and that most programmers want more syntactic sugar than a regular syntax offers, which means that compiler support is in fact wanted to satisfy this perception of market requirements.

[P.S. I'm not arguing against the potential value of a language like Links.]

HaskellDB doesn't yet, but could and probably will one day, generate optimized SQL for different environments. It abstracts away from SQL by acting as a compiler for an embedded relational query language. I imagine that something similar could be done with XQuery and Javascript - make the different platforms different targets of a retargetable compiler.

From my experience, you will always need a way to get at the raw SQL generated and tweak that. Databases are strange beasts, and optimizers change query path constantly. What used to be an optimized query suddenly runs slowly. Even as table sizes change, the optimizer changes the query path. I have found just re-arranging the order of statement elements radically (order of magnitude) changes performance (and of course it should not - but optimizers are written by mere mortals).

...of how a Links is supposed to know when it would be appropriate to build some indices, and on what. I suppose that, in the limit, it could periodically do an "EXPLAIN" and attempt to do some inference. That would be very interesting to see.

it could periodically do an "EXPLAIN" and attempt to do some inference

I think this underlines my qualms with the idea: in order to make the SPECIFICATION (language design) work, we are already pretty deep into IMPLEMENTATION issues.

This suggests the problems don't live at the language design level.

...No, because a language that has the explicit goal of interoperating productively with existing "relational" databases has no choice but to finesse the interaction with SQL somehow.

Yes, because it's not clear that this "finessing" can't consist of having the usual kinds of support for extensible control-flow coupled with a good syntactic extension mechanism. Ehud recently reminded us of SchemeQL, which seems like an excellent example of the latter. I'm also reminded of Oleg's work on database interfacing in Scheme.

From my experience, you will always need a way to get at the raw SQL generated and tweak that

It's sometimes necessary to get at the output of a C compiler and tweak that, too. Sometimes, but rarely. I think a relational query language compiler targeting SQL could get it right enough of the time to be useful. But I agree that it's important to be able to access the lower-level representation from time to time.

Obviously my exepriences are not "statistically significant". I have, however, been using Oracle, SQLServer and others for over 15 years. Rarely is not the term from my experiences. Regularly might be the term I would use.

Why, for example, do databases offer "hints" as a SQL facility? Because they know the issue is significant.

Because they're committed to supporting a crude language in which trivia such as order of operands are significant, and are used to determine performance. A better approach would be to take the existing core engine and mate it to a more sophisticated language, one whose interpreter would do performance analysis on the fly to respond to the changing conditions in the core.

I've written a compiler targeting SQL, and getting the generated code to perform was indeed the hard part. I had serious DB experts advising me on how to improve the output, but the problem was generalizing that advice. The improvement added to make customer A's code perform later turned out to hurt customer B; and the information to distinguish the two cases just wasn't available at compile time. I had a design laid out to let runtime performance data feed back to compile time, but never got a chance to build it before the company imploded.

Why databases offer "hints"

Thus it has to be specified externally.

One problem with current state of affairs is that this information must be provided in wrong form by wrong people at wrong time (SQL hints by developers at time when a statement is prepared). One cannot easily decouple this costs/benefits information from SQL statements in both space and time.

Probably, Links will provide a separate life cycle for costs/benefits specifications.

Perhaps what we need are database query optimizers that learn?

Optimizers often produce query paths that are nonesensical, taking one or more orders of magnitude to do the query than is necessary. The current solution is either hints or humans re-arrange the queries.

If we had query optimizers that learned, we could either:
* Tell the optimizer to try again (offline - while tuning)
* Have the optimizer use idle time to experiment with the last periods queries to find better paths, and remember

I've been having problems on the stored proc side where the compiler will figure out the plan based on the current inputs. Once compiled, the proc doesn't need to be recompiled until the conditions change or a recompile is needed.

Problem is, that the parameters used in the first call may or may not be representative of the data as a whole. Means that you can get a very small dataset which might perform a microsecond better doing one path, but that same path can take minutes to complete for the larger sets.

Haven't really figured a good way around the problem other than dropping hints and trying to force a compile on the worst case datasets.

Database Optimizers that Learn

Even if we forget about economical values: DBMS can optimize locally - in the scope of the database, but not in the scope of the whole system, because nobody tells them about outcomes at the level of the whole system.

Even a "local" optimization is better than none?

A query that should take under a second with a good plan often will take several minutes. This one requires little knowledge of context.

Even a "local" optimization is better than none?

A query that should take under a second with a good plan often will take several minutes. This one requires little knowledge of context.

Granted, "with a good plan" does not necessarily means harming "utility" for other queries - it may be a win-win. But a classical DB dilemma - to index or not to index - is an example of a trade-off decision, which cannot be meaningfully taken locally.

For security, you could encrypt the state held in the client?

The only secure way for the client to modify the state then would be to have it pass to the server for modification. Hardly a performance win.

The client could always modify state locally and pass the a trace of execution back to the server for verification. If the server detects an something is off the client would have to roll-back the changes made.

If the server detects an something is off the client would have to roll-back the changes made.

What if the change being made is to upgrade the security access of the client?

While less egregious, this is still egregious. What benefit does this scheme provide over having the master copy of the state on the server?

Scalability. If the session state lives on the server, then you have to either store it in the DB or tie the client's session to a single Web server. If it lives in the client, then it comes back from the client on each request, and any Web server can handle the request--no application server needed. (Plus, the Back button doesn't break the app, since going Back unwinds the session state.)

I've built a calendar app like this. Simulated load showed one million users on something like $10,000 worth of hardware.

Efforts to directly support XML types in a programming language has definitely produced cool results, many of which will find new applications. However, is the original goal misguided?

I feel that the reason XML is difficult to deal with in conventional languages is because it is a bad format. Regular expression-based typing, while "neat", results in confusing data structures. They're great for matching data, but not so great for structuring that data. (That's why a parse tree only used for matching. Once the pattern has been matched, the data is put into an AST, which is usually a more conventional data structure).

The standard list/tuple/variant data types of Haskell and ML are much better than XML.

• JavaScript as a real programming language (not just for simple web pages but for serious development, which is quite different).
• The XUL XML dialect, for client-side user interface description (and inspiration for Microsoft's upcoming Xaml).
• The XBL XML dialect, for XML object-oriented (yet mostly untyped) programming.
• Mozilla's XPCom component architecture (C++-based, dynamically yet manually typed, with half-automatic half-manual reference counting, without exceptions or return values).
• And a few other things such as XmlHttpRequest's arcane usage, Mozilla's half-documented XPCom libraries, several specialized XML-RDF dialects...

In addition to this, in my experience, XBL and JavaScript programs typically require at least 3 times more lines than OCaml counterparts, while XPCom-based programs require 4 to 5 times more lines. As you say, the number of line is not really the matter. However, most of these lines are not just syntactic sugar but opportunities for Segmentation faults and silent failures. Counting from all the errors I commit or see discussed, I would say that most of the errors should be handled by the language. Indeed, at least 95% of these errors would be caught by the compiler in OCaml or Haskell (for the components) and in XDuce or CDuce (for everything Xml) [1] and at least 50% of them would actually be syntactically impossible, by language design [2].

Bottom line: I believe that there is a place for a good web client-server DSL. Perhaps, as many of the good languages available, it will not be used. But I believe it would be worth learning and using. And it does not have to be more complex than Python or Ruby [3].

Heck, I would even volunteer to contribute to such a language, at the expense of some of the time I spend on my own projects.

1. Note that I have not tried XDuce and CDuce and am speaking from mere readings of the manual.
2. Statistics might be different in more algorithmically-challenging projects.
3. I find that Python and Objective Caml are as easy to learn, with the difference that Objective Caml error messages are sometimes more obscure but also more useful in the long run. I have never learnt Ruby. Heck, I'm supposed to be a theoretician :)

Javascript is a good temporary target, but I hope the architecture keeps the target interface abstract. I.e. if I write a Links application the I hope that it's as easy to create an interface for your cell phone, your a native windows desktop, and your home X10 home appliance network as it is for your browser.

So do I. In addition, there is the upcoming war between Html-based, Mozilla's Xul-basedand Microsoft's Xaml-based user interfaces for web/desktop applications.

Links could get tons of publicity and support if it integrates with Firefox and Thunderbird out of the box.

I concur.

Some of the problems you address--scanning and parsing--are pretty much done with standardized tools. Others, of course, aren't--in part because there isn't agreement on how ASTs for example should be structured; or how to deal with semantic anaylsis (attribute grammars?).

Machismo may be part of it, too. There is a longstanding prejudice (justified or not) that a (domain-independent) language isn't worth talking about unless one can write a compiler for said language in itself; guess what is often written first? Obviously, you can't use existing tools if you're bootstrapping a new language.

That said, toolkits like you mention do exist. If anything, there are too many of them...depending on what host language you choose to use.

I think host language and platform matter quite a bit, and a good deal of effort goes into building that stuff.

Any real-world compiler needs to be able to do things like crack apart .class files, or introspect a .net assembly, or pull apart a .lib file. At the end of the day you need to be able to flatten, linearize, emit bytecodes, assembly, whatever.

The middle-most parts of a compiler can get specific to the language and have a fair amount of complexity. Those outer parts, though, are pretty generic. Just about every compilation-based language for the Java VM needs to implement classpath reading, cracking, lazy instantiation, and so forth...

Choosing a host language is really part of the problem -- phases are necessarily written in one or more languages, but a compiler as a whole need not be homogenous.

Imagine a "compiler" that did a tokenize/parse, then wrote the results down into an XML (or whatever structured representation) file. Another program then performs the next phase and writes its results...just like in the very most ancient days of compilers. If we have a well-defined basis for representation phase logic can come from many places.

Scanning and parsing just isn't as hard as it used to be; plenty to help us there.

Ultimately this is about making software assembly easy, or even automatic. There's not much different between backwards-chaining compiler/transform assembly and performing the same task in other domains (pulling together software transformations written in multiple languages and models).

The MetaEnvironment includes many tools and interfaces with even more:

• stratego - a tree transformation language
• ASF - A term rewriting language with interpreter and compiler.
• SDF2 - a parser definition language
• ATerm - a general and efficient abstract syntax tree representation

MetaEnvironment also includes ToolBus for communication among components, TIDE as a generic debugger, and more.

There's CTK, the Compiler Toolkit, and CTKlight for lightweight applications. (CTK's fast lazy lexers are particularly nifty.)

GCC-XML dumps intermediate structures to XML. David Himmelstrup is using that in Hacanon for example.

There are lots more language/compiler/interpreter tools and frameworks available, these are just the ones I can think of off the top of my head.


--Shae Erisson - ScannedInAvian.com

so I will start looking at what you've suggested! thanks for the pointers.

(Now if anyone can get the MetaEnvironment to build in Windows, please let me know how you did it. I've been wanting to experiment with their software for a long time now, and have repeatedly been thwarted in my attempts to build for Cygwin.)

I've gotten as far as mostly getting graphviz to build -- there's a few extra packages you have to get installed into cygwin (curl, gd, and I can't remember the other ones).

Sure wish there was an ebuild for Gentoo. ;)

In any case, thanks to Shae for the pointers. My head is now on the verge of detonation from reading all these papers.

There are official Debian packages for most of the MetaEnvironment, you may want to try those if you have the option.

--Shae Erisson - ScannedInAvian.com

I'm the maintainer of the Stratego/XT packages in Gentoo. We have the entire XT environment available, and it is usually fairly up to date.

We don't have the MetaEnvironment, but if people are persuasive, I can add it. Just open a bug at bugs.gentoo.org and assign it to me, karltk@gentoo.org, then I'll see what I can do for you.

We are using Stratego/XT to embed XPath in Java using java-front. So there's no need to create a new language (since all the DSL's are already in place). Stratego has one bad thing: it's error reporting. Not considering this, it's pretty good.

I'm one of the developers of Stratego, so maybe I can help a bit. First, Stratego is not part of the MetaEnvironment. Let me explain the structure of all this work a bit.

First, there is SDF. SDF is a modular language for syntax definition. SDF simply rocks and kicks the ass of any language for syntax definition I know about (sorry to be informal and subjective here, I reserve formalities for our publications). SDF integrates lexical and context-free syntax and can supports arbitrary context-free grammars, as opposed to subsets, such as LL, LR or LALR. All these subsets cannot be modular, because the are not closed under union. Our Concrete Syntax for Objects paper at last year's OOPSLA explains why modular syntax definition and scannerless parsing can be very important for some projects (e.g. embedded DSLs). SDF is easy to install. At syntax-definition.org we provide binary distributions for most platforms (RPM, Cygwin, Mac OS X, sorry no native windows yet.) of all the tools that you need to use SDF.

Second, there is ASF+SDF, which is a first-order term rewriting language that employs SDF to allow rewrite rules to be written in concrete syntax. The ASF+SDF MetaEnvironment could be described as an IDE for ASF+SDF. I'm not a maintainer of ASF+SDF, so I don't know much about the available distributions.

Third, there is Stratego/XT. Stratego is a program transformation language and XT is a set of tools for implementing complete program transformation systems. Stratego/XT also uses SDF for syntax definitions, in particular for providing support for using the concrete syntax of the object language in your meta programs. Stratego/XT is a plain set of command-line tools (say, SDK): compiler, interpreter, etc. There is no full-featured IDE available, just some syntax highlighting stuff for Emacs and Nedit. Stratego/XT distributions are available in source are binary form for RPM distributions, Cygwin and Mac OS X. Please don't use the Debian distributions: these have not been created by us and don't seem to be maintained. The available version is completely out of date.

I hope this makes things a bit more clear and I hope you enjoy these tools if you start using them. Stratego and ASF+SDF are rather domain specific, but SDF and Scannerless Generalized-LR can be applied in a lot of different projects, particularly if your parsing needs are getting to complex or you need to prototype some language.

Sorry that might sound like a commercial break, but shapr referred to our tools and I want to make it as clear as possible to new users what they should download :) .

That's perfectly alright, Martin. I am sure many here are interested in your work. I, for one, am always glad to hear more about it.

Thanks for the clarifications -- I am poring over SDF, and your note indicates I should be looking heavily at the Stratego/XT toolset as well.

You may find this http://www9.org/w9cdrom/342/342.html of interest.

I remember seeing a presentation on SmartTools, which provides much of what you are asking for. It allows the description of a new DSL, and generates both the IDE and the compiler for it. The main target is an AST on which visitors can apply the transformations of your choice.

Once I get tokenizing out of the way, I can put build my AST in something somewhat standardized like, say, an XML DOM tree. Yuck, you say, and I agree, but it's good enough for attributed trees and the whole point is to be able to talk about trees in a standardized way. It's also good to be able to transform them. In the slow slow compiler you could build a transformation phase with XSLT.

source code -SableCC parser->
parse tree  -SableCC->
XML dump of parse tree -XSLT->
AST in XML representation -DTD->
Java Class representation of AST & validity check(!)

Manual steps: writing the grammar, tree transformation rules (XSLT), and DTD, everything else was generated.

Using XSLT instead of Java for tree tranformations was a big win (declarative, faster to write, more concise, easily changed later on in the project). Also, the DTD is a spec for the AST, allowing other tools to rely on its structure.

Some example applications that I'd like to see:

• A wiki engine. Better yet, several experimental wiki engines with different design trade-offs. If the language is powerful enough that I can easily whip off different prototype frameworks for some particular web application, then I might say, "that's something I can't do with any other technology."
• A blogging engine. Same deal.
• Forget meta-circular compilers, I want to see a meta-circular LinksDoc tool for generating API documentation web pages!
• A homework submission server.
• CiteULike.

Anton and Ehud, was there web development gripes you had setting up the new LtU? Would integrated XML/SQL have made your lives significantly easier setting up and maintaining this site?

It wouldn't have helped directly, because we didn't do much of that work — we used an off-the-shelf tool, Drupal. Drupal is a pretty well-designed system — its founder, Dries Buytaert, is a CS PhD student. However, it's implemented in PHP, and I'd say the biggest single problem with it is that customization tends to require directly modifying the relevant code, i.e. beyond Drupal's web admin interface, it's not nearly as heavily driven by templates and config files as some such systems are. That was apparently a conscious design choice — there's been some debate in the PHP community about which approach is preferable. One of the arguments against the more data-driven approach boils down to a pragmatic attitude which might be described as premature abstraction being evil, i.e. don't try to anticipate too much how users might want to configure the system, but make the code easy to modify.

If there were a more powerful language which was popular enough to have supported the development of a highly capable tool like Drupal, we might have benefited from improved abstraction capabilities. OTOH, I've noticed that one barely has to know PHP to modify a program which uses it — superficially at least, it's perhaps one of the least surprising languages I've come across (assuming one has a certain familiarity with the usual mainstream languages). How much of PHP's success has been driven by this effect? A more "advanced" language, especially one with a modern static type system, might have difficulty replicating that quality. For development of systems in which a major part of their value resides in the collective effort that's gone into filling in details, that ease of use is likely to be a major success factor.

I'm not sure that has to be a problem for something like Links, though. I wouldn't have thought Links would really want to replace PHP — there's more interesting fruit a little higher up the tree, closer to the region in which Java and C# play. (Cue inter-language flamewar — stereotypes used for communication purposes only.)

I take it that what's meant here by keeping state in the client is that continuations are serialized and then echoed back and forth (with the server issuing a new continuation-representation each time the computation advances). See Anton von Straaten's Continuations continued: the REST of the computation for a discussion of some of the issues relating to this approach.

You seem to have left out the scheme/lisp/smalltalk solutions.

why then didn't the javascript server/client combination become popular?

They still had a benefit of the same language for business logic on both client and server, and that was indeed good. OTOH, a boundary between business logic and infrastructure became socially inpenetrable - BTW, this is not different from EJBs, where a developer of a bean cannot go and hack the container. For a proprietary frameworks, though, this property was not economically attractive (the whole point of keeping a proprietary framework is flexibility).

So this framework was replaced by Java-based one.

But isn't Links about XML, SQL and other server-side stuff, while Ajax is about heavily Javascripted client-side interfaces (plus GUI, so lots of CSS and JS)?

Maybe the killer technology would be a Common Lisp in JavaScript and a declarative layout language that compiles to CSS :)

(yes, I've tried size-independent layout with CSS; it just doesn't work; sometimes 10px might be understood, but 1% isn't and stupid stuff like that)

Ajax is mostly client-side, but it still needs to make server requests, and deal with the local DOM, etc., so if Links provides an excellent framework for doing Ajax software development (i.e., JavaScript, CSS, XMLHttpRequest, etc.), that should be a definite win.