peteg's blog

XSLT is Turing Complete. So What?

/hacking | Link

There are several proofs of this fact, such as this one from 2006. So, why would IBM's DeveloperWorks publish an an article that apparently says otherwise [*]?

Finally, XSLT is the familiar technique that, in a sense, best matches the structure of XML. Perhaps reflecting this match, XSL documents are themselves XML document instances. XSLT is a special-purpose functional programming language that allows you to specify transformations of XML documents into other things (especially, but not only, into other XML documents). Aside from the somewhat annoying verboseness of XSLT, it is limited in its expressiveness — the things you can say are expressed rather clearly (and functionally, not procedurally), but you quickly bump up against all the things that you simply cannot say in XSLT.

OK, so there is an appeal to a Turing tarpit argument, but how about that last phrase, the worrying ... all the things that you simply cannot say in XSLT? Let's keep reading:

The problem comes as soon as you want to filter or compute something for the output — something that is not included in the few comparisons available to XSLT. For example, maybe you want (in a numerological spirit) to display only the even-numbered hexagrams, or only the prime ones. With XSLT, you are out of luck for something this simple.

So, what we have here is something like control completeness — it has enough in the way of control flow constructs — but data-incompleteness — you can't munge your data in all the ways you'd like to. This has always bothered me: how do you prove that you have provided enough operations for your datatype? I'm sure there are people studying algebraic data types and algebraic specification who have some answers for that.

[*] As this article should make clear, the claim of Turing Completeness is weaker and slipperier than most people seem to think.

Halfway through the project, I begin to talk about the project.

/AYAD/Project | Link

So the game here is to build a CMS-style website for DRD, who are presently using an unmaintainable ASP mess. (Heh, I think that's the old ASP, not ASP.NET, but what would I know.) I decided to renovate Björn's Haskell effort, HOPE, which looked, superficially at least, pretty hackable.

Activity for these past few months:

  • I tried to fix the concurrency issues. There was/is [*] a lot of confusing code that looks like it might be safe, but wasn't. It might have worked if the DBMS provides coarse enough concurrency, and traffic is sufficiently light. (I don't claim to have fixed everything yet, and there are limits to what we can do.)
  • As part of the above I hacked the daylights out of HaskellDB and HSQL, but only conforming their PostgreSQL backends with my higher-level changes [**]. Specifically I tried to extend their notions of a relational database to encompass constraints [***], and add support for the serial datatype.
    • HSQL seems adequate as a low-level SQL interface, at least as far as these things go in Haskell [***], so I don't know why anyone would reinvent that wheel (ask them).
    • I would strongly recommend against trying to use HaskellDB, despite the heroic efforts of Björn et al. It's nice in theory but quite limited and very complex in practice. If I were to do this project over, I would drop HOPE's dependency on HaskellDB.
    • I am now painfully aware of the semantic gap between Haskell and SQL databases. What we really want is serialisation and querying of algebraic data types, that is, something closer to XML technology. The only group I know that is taking persistence seriously at the typed, higher-order, etc. programming language level is the mob working on Alice/ML, and if I had a spare life I'd marry that with Benjamin C. Pierce's work of the past ten years or so and develop a mergeable, distributed, queryable storage manager for a decent language.
  • Added a lot of I18N support. This is as-yet incomplete, of course, and I'm not very happy with how I've done the dynamic part of it. One major outstanding issue is how best to support multi-lingual tagging.
  • Shifted away from Björn's home-brew and somewhat buggy hmarkup to the Windows-user friendly FCKeditor. I have my qualms about this, but I've got to consider my user-base.

Some of the abstractions in HOPE are fantastic, and others are head-scratching, tantalisingly close to being so. If I have the time and enough brain capacity, I'd really like to re-do the notion of resource so we can (for example) generate site maps and have fewer URL paths scattered through the code. So, good effort Björn.

If you're interested in any of this, you can take a look at the darcs repos at Please note that everything there should be considered alpha quality and under chaotic development.

[*] My changes are so pervasive that it's better to think of my version as a fork rather than a continuation. The database schema is quite different and currently requires PostgreSQL, so I doubt it is useful to any current users.

[**] This has some nasty ramifications. One is that it is unlikely that my code will be merged into the mainstream darcs repos, as I have no interest in or time to fix the other backends. (I refuse to encourage anyone to use speed-over-correctness software like MySQL.) Due to this, I doubt one can use the shiny-new cabal-install to suck down the myriad dependencies of my version of HOPE, as you'll need some stuff from my repos, and other stuff may as well come from the official places.

[***] Somewhat ironic to me is that all the low-level Haskell SQL bridges I've seen have a very limited view of what a relational database is; usually the bridge just ships SQL one way and gets a list of rows back, and provides a very basic table description mechanism. I haven't seen any support for defaults, triggers, constraints (foreign keys, primary keys, uniqueness, etc.), and while there is usually support for transactions, it is difficult to figure out what that means as the bridges all try to be backend-agnostic. Conversely there are a lot of attempts at making rows and queries type-safe.

Paths of Glory

/noise/movies | Link

Trung Nguyên, 42-44 C10 Nhiêu Lộc 2, District Phú Nhuận.

/AYAD/HCMC/Cafes | Link

A fancy place just near Mike's apartment building, which is clearly marked on this map (the orange-red thing on the far right). Very comfortable and not too smokey for an indoors joint.

Trung Nguyên, 272B Xô Viết Nghệ Tĩnh, District Bình Thạnh.

/AYAD/HCMC/Cafes | Link

On the north-western corner of the monster roundabout at the intersection of Điện Biên Phủ and Xô Viết Nghệ Tĩnh (the big fat highway heading north of Hồ Chí Minh City). There's a massive Trung Nguyên sign out the front, but it's otherwise unimpressive.

Love and Human Remains

/noise/movies | Link

I first saw this strange and wonderful movie about ten years ago with Pete R.. It's a Canadian Naked, albeit not as dense.

/noise/politics | Link

The ALP has pulled out all the stops to win this election; Sydney gets a spray from Paul Keating, and Melbourne one from RJL Hawke.

An Economist visits South East Asia.

/AYAD | Link

Megan McArgle skillfully articulates some keen observations about the economic situation in Cambodia and Vietnam, and in particular how difficult it is to bridge the chasm of cultural norms.

v-heart, a workshop for people with Down Syndrome or Cerebral Palsy in Gò Vấp.

/AYAD/Disability-Projects | Link


Loan found out about this project from Yumiko-san of the spinal injury project at Cho Ray Hospital. In essence the participants are trained in the use of a loom that looks to my eye almost identical to this picture (that I nicked from Apple's already-excellent and now much-enhanced It's funded by a Japanese group.

Trung Nguyên, 1A Phạm Văn Hai, District Tân Bình.

/AYAD/HCMC/Cafes | Link

A large night-clubby kind of place, with big comfy couches and that special kind of dinginess, quite close to the airport. I went there with Loan after visiting the v-heart project.

The Mac OS X 10.4.11 Upgrade Killed My MacBook.

/hacking/mac | Link

That's a first, a Mac OS X update that screwed things up so badly the MacBook ceased to function. Oh well, I now know where an Apple store is in Hồ Chí Minh City; I went to:

Thuan My Co. Ltd - Apple Authorised Reseller
98 Nguyễn Công Trứ, District 1, Hồ Chí Minh City.
Tel: 84 8 8218936, 8218937
Fax: 84 8 8218937

and tried to buy a copy, nay a licence, of Leopard. I'll spare you that story. The "update" function failed to work any magic (or didn't like the cafés I went to), but the "archive and install" thing did the trick. I get the impression that some database in my old 10.4 installation got trashed.

Here are some fix-ups for Leopard from around the net (sorry for the lack of attribution). Let's fix the Dock (make it look more like Tiger's):

defaults write no-glass -boolean YES
killall Dock

and the transparent menubar (cut and paste this line, then — eek! — reboot):

sudo defaults write /System/Library/LaunchDaemons/ 'EnvironmentVariables' -dict 'CI_NO_BACKGROUND_IMAGE' 0.63

Time machine claims to have done something but I haven't tried to use it yet. Spaces is clunkier than I'd expect; using an app that sprays windows around like Finder and expecting some kind of mid-90s "raise" functionality is apparently asking too much. The wifi widget on the menubar finally works like what every user of open networks wants it to. Worth the money? Probably not, but heh, anything to get the MacBook back on its feet. That's the last time I travel without a Mac OS X DVD.

/noise/politics | Link

I voted in the Australian Federal Election at the Consulate just now. According to the lonely Kevin07 guy out the front, that 45 people lined up on Monday morning to vote signals a change of government.

The Dirty Three Doco.

/noise/music | Link

Who'd've thunk it? I just hope it's not another I'm Your Man, where "luminaries" share their uninsightful "insights". Their music speaks for itself.

Blade Runner

/noise/movies | Link

Peter Andren, R.I.P.

/noise/politics | Link

And here was I hoping to see how his Senate campaign unfolded...

That about wraps it up for Blake's 7.

/noise/movies | Link

What started as a promising politico-scifi Doctor Who-for-adults headed for the crapper somewhere around the beginning of Season 2. Actually, if I could be arsed I'm sure I could pin-point the exact moment when it ceased to be interesting. The final iconic episode is shamed by some of the most unbelievable tosh in the entire genre. What a wasted opportunity.

Café Trung Nguyên, 53A Phù Dổng Thiên Vương, Đà Lạt.

/AYAD/HCMC/Cafes | Link

An incredibly cute three-story house that would be right at home in the Blue Mountains in Australia. A cà phê sữa đá #5 costs just 13 kilođồng, fully 7 kilođồng less than in Hồ Chí Minh City.

Trung Nguyên, 114 Lý Tự Trọng (corner of Thủ Khoa Huân), D1.

/AYAD/HCMC/Cafes | Link

Just up the road from Bến Thành Market, cunningly concealed on a corner facing away from the traffic streaming down both one-way streets. This one's a cosy little "brown café" that wouldn't be out of place in Amsterdam.

The Pervert's Guide to Cinema

/noise/movies | Link

What a strange little movie. Slavoj Žižek's stream of consciousness is not even internally consistent, let alone coherent. It's the decrepit vehicle of psychoanalysis smashing into the 21st century, with all the fascination of a staged car crash.

Revealingly, his wikipedia page says:

One of the problems in outlining Žižek's work and ideas is that for the layperson he seems to change his theoretical position (for instance, on the question of whether Lacan is a structuralist or poststructuralist) between books and sometimes even within the pages of one book. Because of this, some of his critics have accused him of inconsistency and lacking intellectual rigor. However, Ian Parker claims that there is no "Žižekian" system of philosophy because Žižek, with all his inconsistencies, is trying to make us think much harder about what we are willing to believe and accept from a single writer.

I reckon he's fallen off the narrow ridge of helping people to think critically and fallen into the chasm of intellectual stupor. Then again, his tradition is rife with the same, and the public demands its cranks.

The Third Man

/noise/movies | Link

I am perplexed that this is rated at 48 in IMDB's top 250. The acting, cinematography, sets, etc. etc. are fine, but the plot is threadbare. This is no Casablanca. Orson Welles.

Trung Nguyên, 346 Nguyễn Trãi, D5.

/AYAD/HCMC/Cafes | Link

The twin of the paradigmatic one on Trần Hưng Đạo in District 1. It's a bit more austere and hence less atmospheric, but the coffee is just as good.

Việt Nam News: Golden Autumn

/noise/books | Link

I bought this collection in the shadow of the doubts created by the short stories in the Sunday edition of Việt Nam News. Apparently:

Golden Autumn, a selection of short stories from our monthly Outlook magazine, talks about contemporary Viet Nam through authors who offer a variety of intelligent and colourful perspectives on our ever-changing country. Here, ordinary lives, struggles and successes are examined within the backdrop of the nation's emergence from war.

I found most stories to be stultifyingly conventional, and irritatingly politically correct: the women are rarely more than objects to be wronged or righted, and the men are continually evading the forces of the South. One could read this and believe that not much has changed since 1975.