Positioning Hypertext in Chomsky's Hierarchy of Grammars

Positioning Hypertext in Chomsky's Hierarchy of Grammars

Jim Rosenberg

Jim Rosenberg sends a shot of grammar straight across the bow of Nick Montfort’s controversial Cybertext review, adding volume to a volley already in progress

Nick Montfort’s review of Espen Aarseth’s book Cybertext, “Cybertext Killed the Hypertext Star,” ebr 11, has much to say about cybertext which is useful. I have found the concept of cybertext to be a useful generalization of hypertext and many other forms of electronic writing, and have taken to using the term a good deal myself. I’m not sure I disagree with Montfort on the fundamentals of cybertext. However, Montfort’s essay contains numerous assertions on the “location” of hypertext on a scale of technical complexity which are either flawed or just plain wrong. It is important that these points be corrected.

First of all, Montfort’s characterization of hypertext is a straw-man version that ignores decades of research in the field using alternative models to the stereotype node-link model. It certainly is true that node-link hypertext is the preponderant structural mode of hypertexts actually done, but in truth almost from its inception researchers were raising the banner of “Don’t link me in” Parunak, H. Van Dyke, “Don’t Link Me In: Set Based Hypermedia for Taxonomic Reasoning,” Proceedings of Hypertext `91, ACM, New York, 1991, pp. 233-242. , and lately I believe you will find a great deal of the research in hypertext is going into spatial hypertext, which Montfort doesn’t even mention. Sets , relations Marshall, Catherine C., Halasz, Frank G., Rogers, Russell A. and Janssen, William C. Jr., “Aquanet: a hypertext tool to hold your knowledge in place,” Proceedings of Hypertext `91, ACM, New York, 1991, pp. 261-275. , Petri nets Stotts, P. David and Furuta, Richard “Petri-net based hypertext: Document structure with browsing semantics,” ACM Trans. Off. Inf.Syst., 7, 1, (January), 1989. , spatial aggregates Marshall, Catherine C., Shipman, Frank M. III, and Coombs, James H., “VIKI: Spatial Hypertext Supporting Emergent Structure,” European Conference on Hypermedia Technology 1994 Proceedings, ACM, New York, 1994, pp. 13-23. – all have been used as structural models of hypertext.

On the subject of the relationship of generalized algorithms and hypertext, this has been written about before, in my own Hypertext 98 paper, “Locus Looks at the Turing Play: Hypertextuality vs. Full Programmability” Rosenberg, Jim, “Locus Looks at the Turing Play: Hypertextuality vs. Full Programmability,” Hypertext `98: The Proceedings of the Ninth ACM Conference on Hypertext and Hypermedia, ACM, New York, 1998, pp. 152-160, http://www.well.com/user/jer/LLTP_out.html. . This paper talks about quite a range of cybertexts, including many Montfort doesn’t, such as Balpe’s generator poetry and the French poésie animée school.

* * *

Now about Montfort’s mathematics. It is worth pointing out that the Chomsky hierarchy of grammars has come up before in the context of hypertext: see the ht_lit thread “Syntax, Linearity, and Experience” Rosenberg, Jim, “Syntax, Linearity, and Experience,” Internet mailing list ht_lit, May 5, 1996, ftp://consecol.org/pub/ht_lit/ht_lit.9605.gz.. First a quibble. The discussion of the “Chomsky-4” level was almost right but not quite. Chomsky’s 4th level in the hierarchy of grammar types was Unrestricted Rewrite Systems. It is absolutely correct that this did indeed turn out to be equivalent to recursive enumerability – a theorem due to Chomsky himself, if I’m not mistaken. But the “mechanism” by which recursive enumerability is usually defined is quite different in character from a formal grammar, whereas the unrestricted rewrite systems are visibly grammars. That unrestricted rewrite systems should turn out to be equivalent to recursive enumerability was surprising and not at all obvious. There are some interesting things here which Montfort doen’t mention. At what level in the Chomsky hierarchy does natural language fit? I don’t know what the current research on this is; some years ago there was a strong feeling among many researchers that recursive enumerability was in fact too strong. Where do computer languages fit? Syntactically, in fact, they are all context-free: Chomsky-2! (If computer languages were not context-free, building practical interpreters and compilers would be impossible.) This clouds Montfort’s picture somewhat. Shall we disparage all computer languages because they are “only at Chomsky-2”? Shall we disparage all cybertexts because they are implemented by software written in context-free languages? We should be a bit careful about assuming that where something fits in the Chomsky hierarchy has anything at all to do with evaluation.

But, as I say, the above is in the nature of a quibble. This paragraph is not. I think Montfort’s conclusion that hypertext fits at level 1 in the Chomsky hierarchy is flat-out wrong. The point he missed concerns how the transitions at the nodes occur. In a finite state diagram, there is a deterministic matrix that gives for a given input character and state exactly one link. Montfort seems to have looked at the fact that a finite state machine can be described by a node-link diagram, takes node-link as all there is to hypertext, and Q.E.D., level 1. But even taking the subset of hypertext which is rigidly node-link: without knowing what the rules are for what links are followed under what circumstances, you simply cannot conclude that hypertext “is” a finite state machine.

In fact, this subject has been researched. If I read it correctly, Seongbin Park’s theorem Park, Seongbin, “Structural Properties of Hypertext,” Hypertext `98: The Proceedings of the Ninth ACM Conference on Hypertext and Hypermedia, ACM, New York, 1998, pp. 180-187. places node-link hypertext at Chomsky-2. Park’s paper is quite difficult and likely unreadable by those without mathematical training. He proves that “link followings” form a regular set (Chomsky-1) but that “link-following outcomes” form a context-free language (Chomsky-2).

But there is a much larger issue here: Montfort doesn’t discuss at all the subject that following a link may trigger an algorithm which generates the node viewed (or mediates behavior in some other way). This vaults hypertext all the way to Chomsky-4. In fact, hypertext has been extensible by fully Turing-complete languages literally since its inception. Doug Engelbart’s system NLS/Augment is credited by most hypertext scholars as the first fully implemented hypertext system. It was built atop a specially constructed programming language called L10 with interface components in a language called CML Watson, Richard W., “User Interface Design Issues for a Large Interactive System,” AFIPS Conference Proceedings, Vol. 45, National Computer Conference, June 6-7, 1976, pp. 357-364. . (L10 is a fascinating language that in many respects resembles perl; the syntax base is very like Algol, but like perl it contains built-in regular expression handling.) NLS/Augment was fully extensible at a Chomsky-4 level – in 1968! (See for a brief review of hyptertext extensibility.)

The whole crux of my Hypertext 98 paper revolved around this: Surely we don’t mean to imply that hypertext is coequal with all of software, so just what kind of algorithm is hypertext, anyway? Much of the discussion concerned such issues as localization and user/algorithm relationships. I believe this is a much more fruitful basis for analysis than the level at which something fits in the Chomsky hierarchy. John Cayley has some papers that are relevant here also; see for instance Cayley, John, “Pressing the Reveal Code Key,” EJournal, Volume 6 Number 1, 1996, http://www.hanover.edu/philos/ejournal/archive/ej-6-1.txt. .

* * *

Finally, concerning Markku Eskelinen’s pronouncement that “Hypertext is Dead”: this is a particular manifestation of a widespread phenomenon I call Postism. Postism is the compulsive desire to measure where you are by what you are leaving behind. It is a view of life through the rear view mirror. Speaking personally, the only form of postism I find useful is post-postism.

Speaking as a certified card-carrying ghost, I am reminded of Cage’s manifesto, which is now something like a half century old:

Nothing is accomplished by writing a piece of music. Nothing is accomplished by playing a piece of music. Nothing is accomplished by listening to a piece of music.

– Our ears are now in excellent condition.

Let’s write!