Re: Composing language descriptions: tree automata and language design?

Paul Prescod (
Sun, 1 Mar 1998 19:30:33 -0500 (EST)

Date: Sun, 1 Mar 1998 19:30:33 -0500 (EST)
From: Paul Prescod <>
To: Dan Connolly <>
In-Reply-To: <>
Message-ID: <>
Subject: Re: Composing language descriptions: tree automata and language design?

On Fri, 27 Feb 1998, Dan Connolly wrote:

> 	But you can't just take a CFG from Joe and another
> 	from Bob and slap them together. At least I haven't
> 	seen any well-studied way to do it.

That's true. I always presumed that we would in some way, shape or form, 
get to parameterized types and declaration sets. Even OOP is a form of 
parameterization ("supply your own functions *here*"). I've been pushing 
for something like the Toru Takahashi proposal for months.

And I also happen to think that tree automata is really important. But I 
must admit that I don't see a big connection there yet. Combining DTDs 
through parameterization can be described almost entirely in terms of 
structural "cut and paste" as it is in C++, Modula-3 and Sather. The 
result of the declaration cut and paste is a CFG that obeys all of the 
properties we expect it to. Maybe I'm a formalism-wimp for considering 
that "good enough."

By analogy: are you uncomfortable using Common Lisp generics until you 
understand the result in terms of the Lambda-Calculus?

> Am I the only person who's been studying language design for
> the last few years who hasn't studied tree autonoma?

No, I first heard of it at SGML/XML 97. My interest now is in arbitrary 
transformations of DTDs and instances as is demonstrated in the paper. I 
hope Murata-san can provice examples of more advanced transformations. 
The paper only has renaming-in-context, which is not too difficult 
without tree automata.

> (but to do it justice, you need to read chapter 8,
> "How the Language Got its Spots" from
> System Programming with Modula-3 Edited by Greg Nelson Prentice Hall
> Series in Innovative Technology ISBN 0-13-590464-1 L.C. QA76.66.S87 1991 

Is Modula-3's generics facility special in some sense, other than being 
really verbose and annoying (as I recall it from several years ago).

> The classicist in me had just about given up hope of finding
> a good model for composing DTDs before I saw this. I thought
> we were going to have to just swim around in loosely defined
> XML-based languages (where the instances were well-formed
> but couldn't be machine-checked beyond that) for some time.

I still don't understand why you had given up on parameterization, or why 
you changed your mind on it.

 Paul Prescod