Lambda the Ultimate

Yes. I agree that XQuery is much more than most DSLs. But to me, it is more equivalent to PL/SQL, rather than a general purpose language like Python. The major missing things are multi-threading/async support, general I/O support, OOP support, and event-driven GUI support.

Thanks Thomas, for your comments and questions. They are all very solid questions.

The "put"/"get" feature in Candle is referential transparent if you consider the global variables in XSLT referential transparent. The functions in Candle can only shadow the values in this named stack, not modifying them. XSLT also supports tunneled variable. Candle is slightly more dynamic by allowing the name to be dynamic. Another way to understand "put"/"get" is to imagine that ALL functions in Candle or XQuery are required to pass one argument called $named-value-stack around, then the "put" statement just wraps this $named-value-stack with one more pair of name-value before passing it to functions in the statement block. And "get" is just a function that unwinds the $named-value-stack and returns the first value with matching name.

The document store or database mechanism is missing in current implementation of Candle. And it's not easy to implement one, so there won't be transactional support in Candle in the next few beta releases, but it should be in the final formal release.

Candle's going to implement a "directory" concept in the next beta release. So that you can query and update a file system just like you query and update XML. I think that's more useful than the abstract "collection" concept in XQuery.

The update mechanism in Candle is quite different from XQuery Update. It's more like PL/SQL. I'll write a separate reference doc on that.

Routines shall be first-class in next beta release of Candle.

Candle has not implemented tail-recursion removal. But that's just an optimization. "put" does not affect tail-recursion removal. You can think of it as one extra parameter passed along implicitly by the system.

Candle already supports making HTTP request. I'll expand the current ref doc and write a tutorial on that.

There's no asynchronous processing support in Candle at the moment. There might be some preliminary threading support in next beta release.

And next beta release should be in about 2 to 3 months time.

I think that the allegedly pure functions in Candle are not actually pure. I think the following is a mistake (and I might be wrong):

The "put"/"get" feature in Candle is referential transparent if you consider the global variables in XSLT referential transparent. The functions in Candle can only shadow the values in this named stack, not modifying them. XSLT also supports tunneled variable. Candle is slightly more dynamic by allowing the name to be dynamic. [emphasis added]

Here is a proposed test of referential transparency:

Assume that there are constructs which can determine the binding of a name (assignments) and, on the other hand, there are constructs which produce the value of a name (references).

And, let's consider a class of programs that contain no "dead code" -- every apparent control flow path in these programs can be taken, depending on input. We don't need to be able enumerate the set of no-dead-code programs, which is good, because of course we can't. But we know that every program is either in this class or it isn't.

We can ask: given the text of a program, considering the no-dead-code programs, can we compute for each reference to a name, the exact set of assignments to that name which can determine the value at the time of the reference?

More specifically, I need some algorithm A, which given any program, will compute for each reference a list of assignments that might determine the value when that reference is evaluated. If a program happens to be of the no-dead-code variety, A must provably produce exactly the list of assignments that effect each reference.

If that computation can always be made in some amount of time that is bound by some function of the textual length of the program, then the language is referentially transparent.

On the other hand, if that computation can't (in general) be made in any less time than it takes to actually run the program itself -- then the language is not referentially transparent.

By that test, XSLT with its version of tunneled variables is referentially transparent. It is a functional language (as designed).

By that same test, the allegedly functional subset of Candle is not referentially transparent (and so I would say misses its design goal of being a truly functional subset).

The last paragraph of this article states:

A more subtle example is that of a function that uses a global variable (or a dynamically scoped variable, or a lexical closure) to help it compute its results. Since this variable is not passed as a parameter but can be altered, the results of subsequent calls to the function can differ even if the parameters are identical. (In pure functional programming, destructive assignment is not allowed; thus a function that uses global (or dynamically scoped[citation needed]) variables is still referentially transparent, since these variables cannot change.)

The put/get in Candle is just the dynamically scoped variable. It's value is not destructively assigned but only shadowed during the evaluation, thus it is referentially transparent.

Here's another way to understand it or test it. We can transform Candle functions into a set of equivalent functions without the put/get statements using the approach I mentioned in the previous article. If all the result functions are referentially transparent. Then we can say the original functions are referentially transparent.(That's my invented way of proving referential transparency. It self needs to be proved. But my gut feeling tells me it should work. :-)

The article you quote is wrong with respect to 'dynamically scoped' variables. That happens.

Ability to 'transform' into a referentially transparent language is irrelevant. Consider: one way of interpreting C code is that it does not destructively alter anything... rather, it just creates a new environment and passes it to the next statement. This 'environment passing style' interpretation works until we add concurrency. But we would still not call C 'referentially transparent'.

In Haskell, we get similar with a State or ST monad. The overall 'runState' or 'runST' computation can be said to be pure, deterministic, referentially transparent - but within the monad, the abstraction developers have is of changing state. And statements cannot be said to be referentially transparent since they must be concerned about the implicit referential context of each statement.

RT must be understood syntactically - at the level of statements and expressions. It really does make a difference whether the environment - the referential context - is 'explicit' vs. 'implicit'.

May be I can agree that functions in Candle which call get() are not referentially transparent judging by the inputs they take.

But on the overall Candle is always referentially transparent, i mean the top-most function main(). Because the main() only depends on the inputs, and when the program starts, the named stack is always empty.

And if someone wants to analyze functions in Candle in a pure referentially transparent way, they can always transform the functions in Candle using the approach I mentioned above.

And XSLT functions using tunnel parameters are also not referentially transparent judging by the same criteria.

Say template A pushed one tunnel parameter, then calls template B,C,D,E...X,Y and finally template Z which pops the tunnel parameter. Then in this call chain, templates B,C,D,E...X,Y are not referentially transparent, because they depend on the pushed tunnel parameter, not just the parameters of the templates.

Below is how XSLT 2.0 Spec explains its tunnel parameter:

Note:
Tunnel parameters are conceptually similar to dynamically-scoped variables in some functional programming languages.

Candle is just one of those functional programming languages.

You said something earlier that is the crux of why XSLT is referentially transparent and Candle's allegedly functional subset is not:

Candle is slightly more dynamic by allowing the name [of a tunneled variable being assigned or referenced] to be dynamic.

I understand you to mean that "put" and "get" can be used to bind or reference a dynamically computed name. The name used can also occur statically in the program.

Here's a consequence of letting names be dynamic like that:

Given a reference to a tunneled variable in XSLT, by examining the program, I can always list a set of binding locations in the source code such that: my set includes all binding locations that can impact that reference; and my set contains no other binding locations except, maybe, some "false positives" which are related only by dead code paths.

In Candle, because the name of a tunneled variable can be dynamic, the same computation is impossible.

In that sense, the meaning of names in XSLT are statically apparent in a way that the meaning of names are not in Candle.

That proves that Candle's allegedly functional subset is not referentially transparent: the fact that that computation about bindings and references is impossible. Probably, if you did not allow the names to put/get to be dynamic, the allegedly functional subset of Candle would, then, be functional. (But see further below.)

In other words, the similar operational model of a binding stack doesn't make or break referential transparency -- that's not relevant. What matters is whether you can statically analyze the relation between binding sites and reference sites with precision (modulo dead code).

Suppose that Candle were changed to only allow static names to put/get. Now there is a chance that the allegedly functional subset is truly functional. I still have another concern:

How do you treat the function "now()", to name one example?

In XSLT, a program can call a putative time function like "now()" many times. Each time it returns the current time. The catch is that in XSLT now() is a constant function that always returns exactly the same value each time it is called in a given run of the program.

If that were not true, then XSLT would no longer be referentially transparent.

So, how does "now()" behave in Candle? I ask because I think for the non-functional parts of Candle, you'd want the value of now() to change over time ... but for the allegedly functional parts, you want it to remain constant. How does Candle reconcile that tension?

Thomas, thanks for your detailed analysis.

I'm thinking in the same way that, in next beta release of Candle, I'll make names of put statement static. Syntax of put statement shall be made similar to the let statement, put $var as type = var { ... }, so that put can weave with FLWOR statements.

The treatment of now() and random() in current beta release of Candle is a bit incomplete. In next release, they'll be split into two versions:

function now() !! same across the entire query evaluation
method now() !! changes on each evaluation
function random(seed, cnt) !! based on the seed, returns a series of random numbers
method random()


I'm pretty sure Scala supports queries (through comprehensions) and node pattern matching (via...pattern matching).

But isn't XML dead/dying anyways as a web interchange format? These days, JSON seems increasingly preferred given its simplicity (untyped...) and integration with JavaScript. JSON benefits from language support also (like through C#'s dynamic typing).

I've updated my table based on your input on Scala.

XML, JSON or even BSON are just different syntax for hierarchical data. The above discussions are really about hierarchical data processing. They applies to both XML and JSON.

I disagree, at least on JSON. JSON is all about coomunicating with JavaScript structures, i.e., plain old simple associative arrays. With JSON, all the craziness of XML goes away and I don't really need any special language. But you also have new problems, like data dependant union types, things not easily expressed in a static type system. You must really embrace dynamic when using JSON.

Now, JSON is not useful for real HTML-like doc markup, and in that case, you do want something like XML. But then I still don't see much point to something like candle, outputting markup is easy enough with literals while the read/parsing problems aren't very solvable regardless.

But you also have new problems, like data dependant union types, things not easily expressed in a static type system. You must really embrace dynamic when using JSON.

Could you elaborate a bit? While I assume the description of any general predicate over a data format may indeed require dependent types (and I remember seeing dependent types when glancing at the paper "The Next 700 Data Description Languages"), I had the impression that most actual dependencies where of the kind "the union case is determined by an accompanying tag value" that are very well modeled by standard algebraic datatypes. Of course, things like indefinite nesting or selector lookup may require more elaborate type system like {C,X}Duce regular types, but I'm not aware of any practically relevant case that would give a hard time to the existing type technology.

Its hard to say how people actually use JSON in practice, since I've observed its very diverse (I've dealt with Facebook, Foursquare, Yelp, + lots of others). Sometimes they use tags, sometimes the element is just their or not depending on some hidden value that you can't see at all. I had this discussion with Don Syme about type providers (typed F# wrappers around web data); it just seemed that the approach had lots of challenges to handle JSON.

It wouldn't be a big deal if JSON wasn't becoming the standard for receiving/sending web data. But XML is becoming increasingly rare in public APIs. Some sites offer both, but many are just bypassing XML altogether.

XML is getting hammered on reddit today, rightly so for anyone who has tried to work with it. The niche where XML works well is much smaller than was thought two years ago.

The niche where XML works well is much smaller than was thought two years ago.

citation?

Sorry, I was referring to data in the original source article.

So, what that data suggests is that fewer (percentage-wise) people are choosing XML, not that what they are doing instead works well in comparison.

I guess we'll see how many XML technologies are reinvented with the JSON brand. ;)

To a first approximation, if you are using free software components rather than paying to license proprietary ones, the odds are very good that you are stuck using James Clark's parsers. If you want XSLT you are probably stuck using xsltproc. For XQuery, you are stuck with with Berkeley DB/XML nowadays provided by Oracle.

None of that software is especially terrible and it's all stronger than all the other free software alternatives I've seen. (If anyone wants to prove me wrong and point out better free software tools, bless them!)

None of that software is especially terrible but neither is any of it especially great. There are missing pieces, awkward interfaces, performance problems, and so on. I've really enjoyed using all of those components and getting things done with them - at times - but I've always been constantly reminded by frustrations how they are really not nearly as robust and efficient as the problem domain really demands. None of the free software XML foundation has really been lavished with as much serious and sustained development effort as you'd wish.

So, now, what happens when I want to build an application? I have a choice. I can use huge and slightly tricky to understand XML libraries but, because of the limits of the free software implementations, my application will have some flakiness, inefficiencies, and/or functionality gaps. Or, I can use the lower tech stuff like JSON and because of the *design gaps* in that lower tech stuff, my application will have some flakiness, inefficiencies, and/or functionality gaps. (Or, I can resolve to go off and, "step 0", build better XML tools but then you'll likely never hear from me again after my boss fires me for turning a 6 month project into a 6 year project.)

For XML to really take its rightful place, it's going to be necessary to substantially raise the robustness, efficiency, and completeness of the foundation of free software XML components. By observation of the high quality proprietary software components I infer that this is going to take a lot of well organized labor and a sophisticated leadership -- exactly the kind of thing the free software world is historically lousy at doing.

It's kind of a bummer because if you could put a dollar figure on the development costs needed I think it would be nearly peanuts compared to typical large corporate budgets. Enough that individuals can't do it and typical middle managers can't risk it ... but peanuts in the grand scheme of things that would help juice the software economy.

My impressions of XML haven't been so positive. OTOH, most of my complaints would also apply to JSON.

I would like to see models that focus more on sets, streams, updates (patches), laziness, map-reduce, and data fusion. Honestly, I'd think we'd be better pursuing more heavily in the direction of relational programming with live queries (i.e. temporal inserts/deletes come across the line). (XPath and XSLT queries and their like seem sort of hacked onto XML - they're good, but maybe we could do better if the underlying data model were designed for it.)

And I also like how David Ryan's Argot simply negotiates the shared types at the beginning of every file or stream, in a compact way. Structured editing wouldn't require XML's obtuse format if we have such types.

Making XML technologies more efficient and robust would maybe help for a lot of projects. Maybe. But I still feel the technology itself has a lot of design gaps. What is its 'rightful place'?

In my own experience, its that the most important APIs are either dual XML/JSON, or JSON-only. So you still have a bunch of mature APIs that were designed with XML and are no longer evolving (maybe since they aren't very popular, and if its not broken don't fix it), and you have the popular APIs that developers are using en-mass that are more volatile and more likely to be JSON.

A new web API today is more likely to be based on JSON. The static checking capabilities of XML are just too difficult to deal with, both on the provider and consumer sides. Perhaps if there was better technology to make XML more usable, say in the form of F# type providers or something like Candle, the momentum might swing back to XML. And, of course, XML is meant for more than data interchange, that it is becoming less popular in this one niche doesn't mean that it is becoming less popular in its other niches.