Beautiful Code

September 11, 2009

In their book The Practice of Programming, Brian Kernighan and Rob Pike present this code for matching simple regular expressions consisting of literal characters, a dot matching any character, a star consisting of zero or more repetitions of the preceding character, and a caret and a dollar sign representing the beginning or end of the search string:

/* match: search for re anywhere in text */
int match(char *re, char *text)
{
   if (re[0] == '^')
      return matchhere(re+1, text);
   do { /* must look at empty string */
      if (matchhere(re, text))
         return 1;
   } while (*text++ != '\0');
   return 0;
}

/* matchhere: search for re at beginning of text */
int matchhere(char *re, char *text)
{
   if (re[0] == '\0')
      return 1;
   if (re[1] == '*')
      return matchstar(re[0], re+2, text);
   if (re[0] == '$' && re[1] == '\0')
      return *text == '\0';
   if (*text!='\0' && (re[0]=='.' || re[0]==*text))
      return matchhere(re+1, text+1);
   return 0;
}

/* matchstar: search for c*re at beginning of text */
int matchstar(int c, char *re, char *text)
{
   do { /* a * matches zero or more instances */
      if (matchhere(re, text))
         return 1;
   } while (*text!='\0' && (*text++==c || c=='.'));
   return 0;
}

Many readers commented on the beauty of the code, and in a later book, Beautiful Code by Andy Oram and Greg Wilson, Kernighan explained the history of the code.

Your task is to port the code to your favorite language. You should use the features and idioms of your language, while simultaneously preserving the beauty of Rob Pike’s regular expression matcher. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

7 Responses to “Beautiful Code”

  1. [...] Praxis – Beautiful Code By Remco Niemeijer Today’s Programming Praxis is about beautiful code. Specifically, it concerns a bit of C code that can [...]

  2. Remco Niemeijer said

    My Haskell solution (see http://bonsaicode.wordpress.com/2009/09/11/programming-praxis-beautiful-code/ for a version with comments):

    import Data.List
    
    match :: String -> String -> Bool
    match ('^':r) = matchHere r
    match r       = or . map (matchHere r) . tails
    
    matchHere :: String -> String -> Bool
    matchHere (c:'*':r) xs  = matchStar c r xs
    matchHere "$"       xs  = null xs
    matchHere (r:rs) (x:xs) = (r == '.' || r == x) && matchHere rs xs
    matchHere r      _      = null r
    
    matchStar :: Char -> String -> String -> Bool
    matchStar _ r xs     | matchHere r xs = True
    matchStar c r (x:xs) = (c == '.' || c == x) && matchStar c r xs
    matchStar _ _ _      = False
    
  3. Tordek said

    Assuming strings as lists of characters (They’re usually atoms, so they should be transformed):

    Prolog solution.

    match(['^'|Rs], T)          :- matchHere(Rs, T).
    match(R, T)                 :- matchHere(R, T).
    match(R, [_|Ts])            :- matchHere(R, Ts).
    
    matchHere([], _).
    matchHere(['$'], []).
    matchHere([R,'*'|Rs], T)    :- matchStar(R, Rs, T).
    matchHere([R|Rs], [R|Ts])   :- matchHere(Rs, Ts).
    matchHere(['.'|Rs], [_|Ts]) :- matchHere(Rs, Ts).
    
    matchStar(_, Rs, Ts)        :- matchHere(Rs, Ts).
    matchStar(R, Rs, [R|Ts])    :- matchHere(Rs, Ts).
    matchStar('.', Rs, [_|Ts])  :- matchHere(Rs, Ts).
    matchStar(R, Rs, [R|Ts])    :- matchStar(R, Rs, Ts).
    matchStar('.', Rs, [_|Ts])  :- matchStar('.', Rs, Ts).

  4. My Common Lisp solution:

    (defun empty (seq)
      (declare (inline))
      (= 0 (length seq)))
    
    (defun match (re text)
      "search for re anywhere in text"
      (if (and (not (empty re)) (char= #\^ (elt re 0)))
          (matchhere (subseq re 1) text)
          ;; must look at empty string
          (cond ((matchhere re text))
    	    ((empty text)
    	     nil)
    	    ((match re (subseq text 1))))))
    
    (defun matchhere (re text)
      "search for re at beginning of text"
      (cond ((empty re))
    	((and (< 1 (length re)) (char= #\* (elt re 1)))
    	 (matchstar (elt re 0) (subseq re 2) text))
    	((and (char= #\$ (elt re 0)) (= 1 (length re)))
    	 (empty text))
    	((and (not (empty text))
    	      (or (char= #\. (elt re 0)) (char= (elt re 0) (elt text 0))))
    	 (matchhere (subseq re 1) (subseq text 1)))))
    
    (defun matchstar (c re text)
      "search for c*re at beginning of text"
      (cond ((matchhere re text))
    	((and (not (empty text))
    	      (or (char= c (elt text 0)) (char= #\. c)))
    	 (matchstar c re (subseq text 1)))))
    
  5. Michel said

    My Clojure solution. Clojure uses Java strings, which are immutable, so taking substring would be too expensive. Instead, I made match-here and match-* internal functions, and give them indices rather than strings to work with.

    Solution, on GitHub

  6. Lautaro Pecile said
    from operator import truth as not_empty
    
    is_empty = lambda s: not not_empty(s)
    
    def iterate(f, string):
        s = string
        while not_empty(s):
            yield f(s)
            s = s[1:]
    
    def match (re, text):    
        if re.startswith('^'):
            return matchhere(re[1:], text)
        return any(iterate(lambda t: matchhere(re, t), text))
            
    
    def matchhere(re, text):
        if is_empty(re):
            return True
        if re.startswith('*', 1):
            return matchstar(re[0], re[2:], text)
        if re.startswith('$'):
            return is_empty(text)
        if (not_empty(text) and (re.startswith('.') or re[0] == text[0])):
            return matchhere(re[1:], text[1:])
        return False
        
    def matchstar(c, re, text):
        while True:                
            if matchhere(re, text):
                return True
            text = text[1:]
            if is_empty(text) or not (text.startswith(c) or c == '.'):
                break
        return False
    
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 613 other followers

%d bloggers like this: