I find ed to be the perfect program to test a new programming language. It demands good support for strings, regexes and data structures while being reasonably sized to be completed in under a week. I polished my C skills as I was learning it by writing this from scratch[1].
[1] Shameless plug, here it is: https://github.com/bojle/edd