Home » forums » LtU Forum

McBride Derivative paper

Having stumbled across Brzozowski's paper on partial derivatives of regex's I went looking for similar papers and have found manay mentions of McBride's The Derivative of a Regular Type is its Type of One-Hole Contexts, often with a URL.

Unfortunately, all these references I've found so far are 404 links that seem to be assorted misspellings and minor variations of http://www.dur.ac.uk/~dcs1ctm/diff.ps (which is itself 404). Anyone have a good link to this paper, or even just a softcopy?

Ta.
Keith

By keithb at 2006-02-27 16:29 | LtU Forum | previous forum topic | next forum topic | other blogs | 10979 reads

Comment viewing options

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

Try here

Try here. I was just able to successfully grab the paper in question.

By Allan McInnes at Mon, 2006-02-27 16:49 | login or register to post comments

When you've read both of those papers...

...say something about the connection, if any. I can see a thread linking them: conceptually the derivative of a regular expression is a regex with a character already matched and removed and the derivative of a datastructure F[X], wrt X, is one with one of its X's removed to leave a hole, but it's fairly tenuous. Also check out papers on differential lambda calculus and differential categories.

By sigfpe at Mon, 2006-02-27 18:46 | login or register to post comments

Species

The common link is through category theory, mainly the theory of species, as far as I am concerned. I have posted links to this before, but I particularly like Marcelo Fiore's invited address at Fossacs 2005. Warning: not an easy read!

Note that the derivative is does not correspond to *removing* an element and leaving a hole, but rather to *adding* a hole where an element could go. In other words, the derivative an something with n elements is a structure on n+1 items, one of them being a ``hole''. There is a wonderful, readable explanation of this (for species) in the book by Bergeron et al.

There is a non-trivial link with Huet's Zipper.

By Jacques Carette at Tue, 2006-02-28 02:53 | login or register to post comments

Note that the derivative is

Note that the derivative is does not correspond to *removing* an element and leaving a hole, but rather to *adding* a hole where an element could go.

Well that depends on your point of view. If X^2, say, is pairs of Xs then the derivative, 2.X=X+X corresponds to either an X in the left of the pair or an X on the right with a hole in the other half. I'd call that a pair with a removed element. But there's probably some dual perspective.

The Bergeron book has been on my wish list for a while now. But unfortunately it's a bit pricey :-(

By sigfpe at Tue, 2006-02-28 06:18 | login or register to post comments

is the Brzozowski paper

is the Brzozowski paper online anywhere?

By andrew cooke at Mon, 2006-02-27 23:30 | login or register to post comments

Probably not

It's a pretty old paper...

By Leon P Smith at Tue, 2006-02-28 15:36 | login or register to post comments

yeah, i saw the date. i was

yeah, i saw the date. i was wondering whether it might be an acm classic or something similar.

By andrew cooke at Tue, 2006-02-28 16:28 | login or register to post comments

I'm not sure if ACM links to

I'm not sure if ACM links to papers are kosher on LtU, but:

http://portal.acm.org/citation.cfm?doid=321239.321249

EDIT:

Also, I have written a (soon to be released) lexer generator for SML using RE derivatives. The implementation notes describe Brzozowski's notion of derivatives and how to use them for DFA construction. The notes also discuss issues with Unicode and RE canonicalization related to using derivatives in practice.

By Aaron Turon at Tue, 2006-02-28 17:41 | login or register to post comments

thanks. don't have acm

thanks. don't have acm membership (actually, i might via work - i should check it out), but page 4 of your notes was great. cheers.

By andrew cooke at Tue, 2006-02-28 23:33 | login or register to post comments