17 Extended Lab Regexps

This chapter is a single (staged) exercise designed to provide an experience working with language-oriented programming (LOP) in Racket. While the nominal goal of the exercise is to build a language for matching regular expressions to strings, the actual goal is to help you understand language-oriented programming in Racket. Thus, do not be too concerned if the regular expression language seems impoverished or unrealistic as the language-oriented programming issues required to solve this exercise cover a lot of ground.

That said, building from a solution to this exercise would indeed result in better support for regular expressions in Racket than currently exists. Specifically, the built-in support for regular expressions does not have a type-system (something this exercise covers) nor is the regular-expression sublanguage macro-extensible (something this exercise does not cover, but this exercise is a prerequisite to adding macro extensibility).

The exercise is structured in a series of parts that highlight different aspects of language-oriented programming. Untyped, Slow Regular Expressions starts with a basic implementation of a regular expression matcher. It is has limited expressiveness, is slow, and does not have a type system. A Weak Type System shows how to extend it with a type system that rejects too many programs and A Better Type System improves the situation by adding a new construct to the regular expression language that makes the type system more flexible. Better Performance through Smarter Compilation returns to the first language and offers a way to do more work at compile time that significantly improves the performance of the matcher. Finally, Improving Repeat to Produce Lists encourages you to revisit you previous solutions to improve the expressiveness of the regular expression matcher. This last section is designed to give you some experience maintaining language-oriented programming code.

The exercise is substantial and not intended to be finished in a single sitting (or even in a single week or month, in fact). Enjoy taking your time to work through it; I certainly did!