Tree programming languages

Maybe I just don't know the magic words to type in, but I was curious if there are any languages which are designed to specifically operate on or describe trees.

Of course, I'm aware of XSLT, but I can't help but think there's more. Unfortunately thats all it seems I can find that comes close. I would really like to know what alternate approaches there are, and as always, any good theoretical justification for the constructs would be nice too.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Rewrite systems

The magic words are "term rewriting systems". Check out Stratego, for example. Also, take a look at "attribute grammars". A good book of string processing algorithms is Algorithsms on Strings, Trees, and Sequences by Dan Gusfield.


You might find TXL interesting.

Language for Bi-Directional Tree Transformations

I found this intriguing.

there's some interesting theo

there's some interesting theory from bird, iirc, on consuming and generating trees (maybe this, although i got a (free) copy from the web somewhere?). i was tidying my desk at home a few days ago and found a paper of his i'd only ever got half way through. i can't seem to find it via google, though. sorry.

there's a whole pile of work related to abstract syntax trees - see here or what lyle said.

graphical concurrent tree rewriting:

The usual suspects

For what it's worth, lists are 1-ary trees. That makes most list based languages essentially tree based languages. e.g. Lisp, Scheme. (I realize the logic went from specialisation to general case, but I think the example cases prove correct).

1-ary or k-ary?

Couldn't a list of lists be considered a k-ary tree?

One branch per node

The arity of a tree is the number of branches per node. There is only one branch per node with a list.