I recently used a regexp library in Scheme for lexing. The result was O(n^2) on the number of tokens in the input stream. I searched for ages to find where I ha

I recently used a regexp library in Scheme for lexing. The result was O(n^2) on the number of tokens in the input stream. I searched for ages to find where I had gone wrong and finally realised it was the regexp library itself. I switched to Common Lisp, which has a greater choice of regexp libraries. The same library exists there too, with the same problems, but switching to the cl-ppcre library made the problem disappear instantly. One problem with Scheme itself appears to be that there is no way to examine a portion of a string. The substring function actually makes a whole new copy of the part you want to examine (which may be the remainder of the input string after the token you just lexed, as it was in my case). Most of the string functions in Common Lisp are set up so that you can specify a starting index in a string so that it is possible to examine portions of a string without making a whole new copy.