Gerald Sussman on Rewriting Systems

I wrote something similar to what he describes at 17:45 in Standard ML using parsers defined to work on quasi-quotations specifying the rewrite rules. See this example, which is a kind of simplifier for C language type declarations. Terms like specifier-qualifier-list and declaration-specifiers are terms that come from the C language grammar originally written by Brian Kernighan and Dennis Ritchie. 

The guts of the rewrite engine are here: https://github.com/IanANGrant/red-october/blob/master/src/dynlibs/ffi/GrammarSyntax.sml but there is a lot of other code to allow the quasi-quotations to be written in a user-friendly syntax. There are a lot of better ways to do this, witnessed by the debugging infrastructure I had to build in just to get the f*cking thing to work!

These kinds of rewriting systems are capable of evaluating expressions, so this language is a programmable evaluator for interpreted languages.

19:32 But I never thought of it as a biological process! See Stuart Kauffman on Irreducible Systems. I did however see it as a musical process, where things like key changes and chord resolutions were programmed to evolve as a phrase develops and other instruments and voices enter the composition.

35:33 Such term rewriters were called expert systems back in the late eighties, ... It's funny how much more interest the students have after he says they're worth a few megabucks each.

The next level is using a rewriter like this to rewrite the rewrite rules themselves, using something like Knuth Bendix completion to produce convergent rewriting systems. See Gerald Sussman on Using Languages To Construct Continuous Solutions.

Subscribe to MIT Open Courseware.